Gradient Descent and Numerical Optimization › Formula

Let $\theta\in\mathbb{R}^p$ be the parameter vector and let $J(\theta)$ be the real-valued objective to minimize. We begin with a local approximation to $J$, then use quadratic examples to determine exactly when repeated updates converge.

The entries of $\theta$ are the quantities we fit. In the regression example they will be an intercept and slopes; the objective is half the mean squared prediction error. Unless stated otherwise, the derivations concern differentiable objectives on an unconstrained parameter space.

The first thing we need is a compact summary of how $J$ responds to a nudge in any of the $p$ coordinate directions. That summary is the gradient, which collects all first partial derivatives into one vector:

$$\nabla J(\theta) = \begin{bmatrix} \dfrac{\partial J}{\partial \theta_1} \\[6pt] \dfrac{\partial J}{\partial \theta_2} \\ \vdots \\ \dfrac{\partial J}{\partial \theta_p} \end{bmatrix}$$

Read the vector one entry at a time and each entry asks the same question in a different coordinate: if we nudge only $\theta_j$ by a tiny amount and hold the other $p-1$ parameters fixed, how fast does $J$ change, and in which direction? Stacking those answers into a column vector turns $p$ separate one-dimensional sensitivities into a single object that encodes both the steepest direction and the steepness itself. Two facts about that object carry everything that follows:

1. For a nonzero gradient, its negative gives the steepest directional decrease among directions of unit Euclidean length. This is a first-order statement about a small displacement, not the best destination at an arbitrary finite distance.
2. The gradient norm measures the first-order residual in the chosen units. A differentiable unconstrained local minimum has zero gradient, but a small norm alone does not measure distance to a minimizer or certify that a point is a minimum.

A direction alone does not tell us how far to move. The learning rate supplies that scale.

Let $d$ be a direction vector and $t$ a scalar step multiplier. A first-order Taylor expansion around the current point says

$$J(\theta + t d) \approx J(\theta) + t\, \nabla J(\theta)^{\top} d$$

The left side is the objective after moving by $td$. The right side adds a first-order prediction of that change to the current objective. The dot product $\nabla J(\theta)^{\top}d$ is the directional derivative along $d$. When both vectors are nonzero, it is negative if their angle exceeds ninety degrees. Among unit Euclidean directions, Cauchy-Schwarz gives the smallest dot product at $d=-\nabla J(\theta)/\|\nabla J(\theta)\|$, provided the gradient is nonzero. Absorbing the step length into a positive scalar gives the gradient-descent update

$$\theta_{k+1} = \theta_k - \eta \nabla J(\theta_k)$$

where:

• $\theta_k$: the parameter vector at iteration $k$
• $\theta_{k+1}$: the updated parameter vector after one step
• $\eta > 0$: the learning rate, controlling how far we travel along the negative gradient
• $\nabla J(\theta_k)$: the gradient of the objective evaluated at the current parameters, pointing in the direction of steepest increase
• $k$: the iteration counter

Reading it plainly: the new parameters are the old parameters, shifted a small distance against the gradient. In scalar form, component $j$ obeys $\theta_{k+1,j} = \theta_{k,j} - \eta \, \partial J/\partial \theta_j$, where $\theta_{k+1,j}$ is the $j$-th component after the update, $\theta_{k,j}$ is the $j$-th component before the update, $\eta$ is the learning rate, and $\partial J/\partial \theta_j$ is the partial derivative of the objective with respect to the $j$-th parameter. This component form is often easier to reason about when we implement it.

The displacement has Euclidean length $\eta\|\nabla J(\theta_k)\|$: the learning rate multiplies the gradient rather than directly specifying a distance. For example, when fitting a likelihood model we minimize its negative log-likelihood and differentiate that objective. A local linear approximation need not remain accurate over a large displacement, so the step length requires a separate choice.

For the scalar quadratic $J(\theta)=a\theta^2/2$ with $a>0$, the gradient is $a\theta$. Substituting it into the update gives

$$\begin{aligned} \theta_{k+1} &= \theta_k - \eta (a\theta_k) \\ &= (1 - \eta a)\theta_k \end{aligned}$$

where:

• $\theta_k$: the parameter at iteration $k$
• $a > 0$: the curvature, the second derivative of $J$ with respect to $\theta$
• $\eta > 0$: the learning rate
• $(1 - \eta a)$: the signed multiplier of the scalar parameter at each update

The quantity $1 - \eta a$ multiplies the parameter anew at every iteration, which means after $k$ steps

$$\begin{aligned} \theta_k &= (1 - \eta a)^k \, \theta_0 \end{aligned}$$

where $\theta_0$ is the starting value at iteration zero.

For every starting value, convergence to zero occurs when $|1-\eta a|<1$, equivalently $0<\eta<2/a$. At $\eta=1/a$, a single update reaches zero. For a nonzero starting value, $\eta=2/a$ produces constant-amplitude sign changes, and $\eta>2/a$ produces divergence. A start already at zero stays there for any finite learning rate. These exact recursions use the constant curvature of this quadratic; a general smooth objective needs a separate local or global analysis.

The relevant step scale is reciprocal curvature. For $a>0$, larger curvature narrows the stable interval $0<\eta<2/a$. This explains why a rate that works on one quadratic may be unstable on another. It does not imply that every small rate is equally efficient.

For a quadratic with a constant symmetric positive-definite Hessian $H$, all eigenvalues satisfy $0<\lambda_{\min}\le\lambda_i\le\lambda_{\max}$. Write the error relative to its unique minimizer in the orthonormal eigenvector basis of $H$. Each error coordinate is multiplied by $1-\eta\lambda_i$, so the Euclidean error contracts by at most $\rho(\eta)=\max_i|1-\eta\lambda_i|$. Convergence from every start requires $0<\eta<2/\lambda_{\max}$. Balancing the two extreme multipliers gives the optimal fixed rate $\eta=2/(\lambda_{\min}+\lambda_{\max})$ and its worst-case parameter-error contraction factor

$$\frac{\kappa - 1}{\kappa + 1}, \qquad \kappa = \frac{\lambda_{\max}}{\lambda_{\min}}$$

where:

• $\kappa$: the condition number of the Hessian, defined as $\lambda_{\max}/\lambda_{\min}$, which measures how differently the objective curves across directions
• $\lambda_{\min}, \lambda_{\max}$: the smallest and largest eigenvalues of the Hessian $H$, the curvatures along the shallowest and steepest directions respectively
• $(\kappa - 1)/(\kappa + 1)$: the worst-case per-iteration error contraction factor for the optimal fixed learning rate

When $\kappa=1$, this quadratic has equal curvature in every direction and the optimal fixed rate reaches the minimizer in one update. At $\kappa=100$, the factor is $99/101\approx0.980198$; the worst-case parameter error needs 116 updates for a tenfold reduction because $(99/101)^{116}<0.1$. This comparison uses relative parameter error and the optimal fixed rate. Objective gaps along an individual eigenmode contract by the square of that mode's parameter multiplier.

For $\mathrm{SSE}(\theta)=\|y-X\theta\|^2$, differentiation gives gradient $-2X^{\top}(y-X\theta)$ and Hessian $2X^{\top}X$. Here $X$ has $n$ rows and $p$ columns, $y$ has $n$ entries, and $\theta$ has $p$ entries. If $X$ has full column rank, the Hessian is positive definite and its spectral condition number equals the square of the design matrix's spectral condition number. Rescaling feature columns changes this geometry. Standardization often helps when unequal feature scales cause poor conditioning, but it does not remove collinearity or guarantee fast convergence. With rank deficiency, the Hessian is singular and the positive-condition-number formulas above do not apply.

When $J(\theta)=n^{-1}\sum_{i=1}^n\ell_i(\theta)$ is a finite mean of differentiable example losses, differentiation gives $\nabla J(\theta)=n^{-1}\sum_i\nabla\ell_i(\theta)$. The full-batch method computes this complete average before an update. Its work is $n$ times the cost of one example gradient; for the dense linear model here that is $O(np)$.

A single-example update uses one loss gradient. If a fresh index $i$ is sampled uniformly and independently of previous updates, its gradient at the current fixed parameters has conditional expectation equal to the full gradient. The update is

$$\theta_{k+1} = \theta_k - \eta_k \nabla \ell_i(\theta_k)$$

A single-example gradient can vary around the full gradient, so individual updates need not decrease the full objective. Persistent noise near an optimum can leave fluctuations when the step stays constant. Positive schedules satisfying $\eta_k\to0$, $\sum_k\eta_k=\infty$, and $\sum_k\eta_k^2<\infty$ are used in convergence analyses together with assumptions on the objective and noise. A smooth strongly convex objective, conditionally unbiased bounded-variance gradients, and stable iterates are one such setting; the schedule alone is not a guarantee for an arbitrary objective. Noise can also vanish at the solution, in which case convergence with a constant step is possible. Our implementation uses random reshuffling, whose adaptive updates are not automatically covered by the fresh-index unbiasedness calculation.

Mini-batch descent sits between the extremes, using a batch $B_k$ of size $b$:

$$\theta_{k+1} = \theta_k - \frac{\eta_k}{b} \sum_{i \in B_k} \nabla \ell_i(\theta_k)$$

At fixed parameters, averaging $b$ independent example gradients divides their covariance by $b$. Sampling a subset without replacement has a different finite-population factor and gives zero sampling variance when the batch contains all $n$ examples. Batch size also changes the number of updates per pass and the available vectorization. We use 32 as one illustrative mini-batch size below; it is not a universal optimum.

If curvature is the problem, we can use it. Rather than guessing a step size that survives the worst direction, expand the objective to second order around the current point:

$$J(\theta + d) \approx J(\theta) + \nabla J(\theta)^{\top} d + \tfrac{1}{2} d^{\top} H(\theta)\, d$$

The Hessian $H(\theta)$ is the matrix of second partial derivatives. The new quadratic term models how the slope changes over the displacement $d$. When this Hessian is positive definite, the quadratic approximation has a unique minimizer. Differentiating that approximation with respect to $d$ and setting its gradient to zero gives

$$\nabla J(\theta) + H(\theta)\, d = 0 \quad\Longrightarrow\quad d = -H(\theta)^{-1} \nabla J(\theta)$$

So the Newton update is

$$\theta_{k+1} = \theta_k - H(\theta_k)^{-1} \nabla J(\theta_k)$$

The displayed rule is the full Newton step, with step multiplier one. In practice we solve $H(\theta_k)d=-\nabla J(\theta_k)$ rather than explicitly forming an inverse. On a positive-definite quadratic this reaches the minimizer in one update in exact arithmetic. Local quadratic convergence for a nonquadratic objective is guaranteed under a sufficiently close start, a nonsingular Hessian at the solution, and a Hessian that is locally Lipschitz, meaning its changes are bounded proportionally to parameter displacement nearby. These sufficient conditions are stronger than smoothness alone.

A dense direct solve typically costs $O(p^3)$ arithmetic and stores a $p\times p$ matrix; forming the Hessian has an additional cost. Newton-type methods can also use iterative solves or Hessian-vector products, so explicit dense storage is not universal. An indefinite Hessian can produce an uphill direction. A shift must be large enough to make the modified Hessian positive definite; at a nonzero gradient that provides a descent direction. A line search can then shorten a descent step to achieve sufficient decrease. Shortening an uphill direction alone does not repair its sign.

For stopping, we need honest criteria rather than a fixed iteration count. Three are standard, and they answer different questions:

• Absolute gradient norm $\|\nabla J(\theta_k)\| < \epsilon_g$ checks an approximate first-order stationarity condition in the current units.
• Relative objective change $|J(\theta_k) - J(\theta_{k-1})| / \max(1, |J(\theta_{k-1})|) < \epsilon_J$ asks whether progress has stalled.
• Relative parameter change $\|\theta_k - \theta_{k-1}\| / \max(1, \|\theta_{k-1}\|) < \epsilon_\theta$ asks whether the iterates have settled.

Each can misfire alone. A tiny objective change may reflect a flat but nonoptimal plateau, and a small gradient norm may occur at a saddle. Report more than one diagnostic alongside the objective value at the returned point. A finite-difference estimate provides a separate check on a hand-derived gradient: it can expose a sign, normalization, or indexing mistake before we interpret the training curve.