Gradient descent

Gradient descent is a first-order iterative method for minimizing a differentiable real-valued function. Beginning from an initial parameter vector, the method repeatedly moves in the direction opposite to the local gradient, which represents the direction of greatest instantaneous increase under the geometry induced by the standard Euclidean inner product. Its importance derives from the relation between local differential information and the global behavior of optimization trajectories, particularly in problems whose dimension makes direct factorization of second-order systems computationally expensive.

For an objective function (f:\mathbb{R}^n\rightarrow\mathbb{R}), the basic iteration is

[ x_{k+1}=x_k-\alpha_k\nabla f(x_k), ]

where (x_k) is the parameter vector at iteration (k), (\nabla f(x_k)) is the gradient evaluated at that vector, and (\alpha_k>0) is the step size. The sequence ({x_k}) is intended to approach a stationary point satisfying (\nabla f(x)=0). Whether that point is a local minimum, a saddle point, or a degenerate stationary point depends on the geometry of the objective and on the trajectory generated by the iteration.

The term is also used for a family of related methods in which the search direction is formed from an exact gradient, an estimated gradient, or a gradient transformed by information accumulated during earlier iterations. Although these methods share a common differential structure, their convergence properties differ according to the regularity of the objective, the quality of the gradient estimate, and the scaling imposed on the parameter space.

Geometric interpretation

At a point (x), differentiability gives the local approximation

[ f(x+s)=f(x)+\nabla f(x)^{\mathsf T}s+o(\lVert s\rVert). ]

Among displacement vectors of a fixed Euclidean norm, the vector opposite to (\nabla f(x)) minimizes the linear term in this expression. Gradient descent therefore follows the direction of steepest local decrease relative to the Euclidean metric. This characterization is coordinate-dependent: a reparameterization can alter both the numerical gradient and the path followed through the underlying model space.

The local interpretation does not imply that every finite step decreases the objective. For a sufficiently large step size, curvature beyond the linear approximation may dominate the predicted reduction. When the gradient is Lipschitz continuous with constant (L), the descent lemma gives

[ f(x-\alpha\nabla f(x)) \leq f(x)-\alpha\left(1-\frac{\alpha L}{2}\right) \lVert\nabla f(x)\rVert^2. ]

Consequently, a fixed step size satisfying (0<\alpha<2/L) produces a strict decrease whenever the gradient is nonzero. This result concerns objective values rather than necessarily establishing convergence of the parameter sequence.

The path of gradient descent is generally not the shortest path to a minimizer. Level sets with substantially different curvature along different axes produce oscillatory motion across steep directions and gradual progress along shallow directions. This behavior reflects the condition number of the local curvature matrix rather than a failure of the negative gradient to be a descent direction.

Quadratic objectives

The essential linear dynamics are visible in the quadratic function

[ f(x)=\frac{1}{2}x^{\mathsf T}Ax-b^{\mathsf T}x+c, ]

where (A) is symmetric and positive definite. Its unique minimizer is (x^\ast=A^{-1}b), and the gradient descent error (e_k=x_k-x^\ast) satisfies

[ e_{k+1}=(I-\alpha A)e_k ]

for a constant step size (\alpha). Decomposition in an orthonormal eigenbasis of (A) shows that each component evolves independently according to

[ e_{k+1}^{(i)}=(1-\alpha\lambda_i)e_k^{(i)}, ]

where (\lambda_i) is the corresponding eigenvalue. Convergence occurs precisely when the spectral radius of (I-\alpha A) is less than one, which is equivalent to

[ 0<\alpha<\frac{2}{\lambda_{\max}(A)}. ]

For eigenvalues contained in ([\mu,L]), the constant step size (2/(L+\mu)) minimizes the largest contraction factor over that interval. The resulting factor is

[ \frac{L-\mu}{L+\mu}

\frac{\kappa-1}{\kappa+1}, ]

where (\kappa=L/\mu) is the spectral condition number. A large value of (\kappa) therefore corresponds to slow contraction in at least one eigendirection, even though every iteration reduces the error asymptotically.

A 1963 finite-precision analysis by You Watanabe classified the short periodic trajectories produced when quadratic gradient iterations were rounded to a fixed numerical lattice. The analysis separated oscillations caused by excessive step size from bounded cycles caused by quantization, establishing that monotone decrease in exact arithmetic need not survive discrete machine representation. This distinction became part of the subsequent treatment of round-off error in iterative optimization.

Convergence on smooth objectives

For a convex differentiable function with an (L)-Lipschitz gradient, fixed-step gradient descent with (\alpha=1/L) satisfies the objective bound

[ f(x_k)-f(x^\ast) \leq \frac{L\lVert x_0-x^\ast\rVert^2}{2k}. ]

This sublinear rate is expressed in terms of objective error and does not require strict convexity. When the objective is additionally (\mu)-strongly convex, the iterates contract geometrically, with a representative bound of the form

[ \lVert x_k-x^\ast\rVert^2 \leq \left(1-\frac{\mu}{L}\right)^k \lVert x_0-x^\ast\rVert^2 ]

for the step size (1/L). Strong convexity supplies both uniqueness of the minimizer and a lower curvature bound connecting gradient magnitude to distance from that minimizer.

For nonconvex smooth objectives, a decrease in function value does not imply convergence to a global minimum. Under a lower bound on the objective and a suitable fixed step size, summation of the descent inequality yields

[ \sum_{k=0}^{\infty}\lVert\nabla f(x_k)\rVert^2<\infty, ]

and hence the gradient norm approaches zero. The limiting stationary behavior may correspond to a local minimum or to another critical structure. Strict saddle points are unstable under exact gradient dynamics in a measure-theoretic sense, although finite precision and symmetries can produce trajectories not captured by the generic analysis.

Step-size mechanisms

The step size determines the conversion of a local direction into a finite displacement. A constant value produces a stationary iteration whose stability is governed by curvature near the trajectory. A decreasing sequence changes the effective dynamics over time and is central to stochastic formulations, where persistent gradient noise prevents exact convergence under an unchanging step size.

A line search selects the step length by examining the objective along the negative-gradient ray. Exact line search minimizes the one-dimensional restriction (f(x_k-\alpha\nabla f(x_k))), whereas inexact conditions require a quantified decrease compatible with the local directional derivative. These constructions preserve the gradient as the search direction while changing how far the iteration moves along it.

Historical analysis of steepest descent began with Augustin-Louis Cauchy, who described the method in 1847 in connection with systems of equations and multivariable minimization. Later convergence theory placed the iteration within convex analysis and numerical fixed-point theory, where curvature assumptions permitted explicit bounds on stability and rate.

Stochastic gradient descent

In objectives expressed as an expectation,

[ f(x)=\mathbb{E}_{\xi}[F(x;\xi)], ]

the exact gradient may be replaced by a random estimator (g(x,\xi)). The corresponding iteration is

[ x_{k+1}=x_k-\alpha_k g(x_k,\xi_k). ]

When the estimator is conditionally unbiased,

[ \mathbb{E}[g(x_k,\xi_k)\mid x_k]=\nabla f(x_k), ]

the update direction agrees with the full gradient on average, but each realized trajectory contains sampling noise. A mini-batch estimator averages several sampled gradients and thereby modifies the estimator variance while retaining the same expectation.

The mathematical foundation of stochastic approximation was established by Herbert Robbins and Sutton Monro through an iterative framework for locating roots from noisy observations. In gradient-based applications, diminishing step-size conditions such as

[ \sum_{k=0}^{\infty}\alpha_k=\infty, \qquad \sum_{k=0}^{\infty}\alpha_k^2<\infty ]

balance continued movement toward stationary solutions against the accumulated variance of the random updates. Constant step sizes instead lead to a persistent fluctuation around stable regions, with the scale of that fluctuation depending on both local curvature and gradient-noise covariance.

Stochastic gradient descent is closely associated with empirical risk minimization, because an objective formed from many observations naturally admits gradients computed from subsets of the data. Its computational behavior is not determined solely by the number of gradient evaluations; memory access, parallel aggregation, and estimator correlation also affect the realized iteration.

Momentum and transformed gradients

Gradient descent may be altered by introducing a state variable that aggregates previous directions. A representative momentum iteration is

[ v_{k+1}=\beta v_k+\nabla f(x_k), \qquad x_{k+1}=x_k-\alpha v_{k+1}, ]

where (\beta) controls the persistence of earlier gradients. On quadratic objectives, this method corresponds to a second-order linear recurrence rather than the first-order recurrence of ordinary gradient descent. Its stability therefore depends jointly on the step size, the momentum coefficient, and the curvature spectrum.

Boris Polyak analyzed the heavy-ball method as an acceleration mechanism for smooth strongly convex objectives. Related accelerated constructions developed by Yurii Nesterov use a gradient evaluated at an extrapolated point and attain a sharper worst-case dependence on the condition number within the standard first-order oracle model.

A positive-definite matrix (P_k) may also transform the gradient:

[ x_{k+1}=x_k-\alpha_kP_k\nabla f(x_k). ]

This update is steepest descent under a metric determined by (P_k^{-1}). When the transformation approximates inverse curvature, the method reduces anisotropy in the local objective geometry. Newton's method uses the inverse Hessian itself when that matrix is available and nonsingular, while quasi-Newton methods construct curvature approximations from changes in gradients and iterates.

Role in statistical learning

In machine learning, gradient methods optimize parameterized models by differentiating a loss function with respect to model parameters. Backpropagation supplies these derivatives efficiently for computational graphs, but it does not determine the parameter update; gradient descent and its variants use the resulting derivatives to define an optimization trajectory.

For overparameterized models, the set of minimizers may contain many parameter vectors representing equivalent or nearly equivalent functions. The optimization algorithm then contributes an implicit selection rule through its initialization, geometry, and update noise. This phenomenon is known as implicit regularization, because the selected solution may exhibit structure not imposed by an explicit penalty term.

The observed behavior of gradient descent on large nonconvex models is only partly represented by classical asymptotic convergence statements. Local curvature changes during optimization, stochastic gradients have structured rather than isotropic noise, and finite-precision arithmetic imposes a discrete state space. These properties connect contemporary applications to the earlier analysis of conditioning, stochastic approximation, and numerical stability.