Gradient descent is a first-order algorithm for mathematical optimization that seeks to minimize a differentiable objective function through successive updates in the direction opposite to its gradient. Each update uses local derivative information rather than an explicit model of second-order curvature. The method is a foundation of numerical optimization and is widely used in machine learning, where the objective is often a loss function measuring prediction error. Its behavior depends on the objective’s geometry, the initial point, and the chosen step sizes. (stanford.edu)
Mathematical formulation
For a function (f:\mathbb{R}^d\to\mathbb{R}), the standard update is
[ x_{k+1}=x_k-\eta_k\nabla f(x_k), ]
where (x_k) is the current parameter vector, (k) indexes iterations, and (\eta_k>0) is the step size, often called the learning rate. The gradient collects the partial derivatives of (f) with respect to its coordinates. In one dimension, the update reduces to (x_{k+1}=x_k-\eta_k f'(x_k)). (d2l.smola.org)
The underlying principle comes from calculus. For a small displacement (h),
[ f(x+h)\approx f(x)+\nabla f(x)^\top h. ]
Among directions of unit Euclidean length, the negative gradient gives the greatest decrease in this linear approximation. Thus, gradient descent is also called steepest descent in Euclidean geometry. With other norms, the steepest-descent direction can differ. The gradient indicates a locally favorable direction, not necessarily the direction toward a global minimizer. (stanford.edu)
Step-size selection and stopping
A fixed step size makes the method simple to implement but must accommodate the objective’s curvature. Small steps can produce slow progress; excessive steps can overshoot a minimum or cause divergence. Alternatively, line search selects a step at each iteration. Backtracking line search repeatedly shortens a trial step until a prescribed sufficient-decrease condition is met. (d2l.smola.org)
A common stopping criterion is (|\nabla f(x_k)|_2\leq\varepsilon), for a specified tolerance. Implementations may also limit iterations or monitor changes in objective value and parameters. A small gradient indicates approximate first-order stationarity, but without additional assumptions it does not establish that the point is a minimum. (stanford.edu)
Convergence and limitations
Convergence guarantees require explicit assumptions. Suppose the gradient is Lipschitz continuous with constant (L), meaning
[ |\nabla f(x)-\nabla f(y)|_2\leq L|x-y|_2. ]
Then a fixed step (0<\eta\leq1/L) satisfies
[ f(x_{k+1})\leq f(x_k) -\frac{\eta}{2}|\nabla f(x_k)|_2^2. ]
For a lower-bounded objective, this yields progress toward small gradients, but not a general guarantee of global optimization. (cs.cornell.edu)
For a smooth convex function with an attained minimum, gradient descent with an appropriate fixed step achieves an objective-error bound of order (O(1/k)). If the function is additionally strongly convex, the error decreases geometrically, often described as linear convergence. In nonconvex problems, stationary points may include local minima, maxima, and saddle points; initialization can affect the resulting trajectory. (ernestryu.com)
Poor conditioning can make progress slow. On an elongated quadratic surface, the method may oscillate across a steep direction while advancing slowly along a shallow one. For quadratic objectives, this behavior can be analyzed through the eigenvalues and eigenvectors of the curvature matrix. (github.com)
A quadratic example
Consider (f(x)=x^2), whose derivative is (2x). With a constant step,
[ x_{k+1}=(1-2\eta)x_k, \qquad x_k=(1-2\eta)^k x_0. ]
For a nonzero initial point, convergence to zero occurs when (0<\eta<1). Steps below (1/2) approach zero without changing sign; steps between (1/2) and (1) alternate in sign while shrinking. At (\eta=1/2), the minimum is reached in one update. At (\eta=1), a nonzero iterate oscillates without shrinking, while larger steps diverge. This example illustrates how even a simple convex objective requires suitable step-size control. (d2l.smola.org)
Batch and stochastic methods
In supervised learning, the objective often averages losses over training data:
[ F(\theta)=\frac{1}{n}\sum_{i=1}^{n}\ell_i(\theta). ]
Full-batch gradient descent computes the gradient using all examples before each update. Stochastic gradient descent instead uses a sampled example, while mini-batch methods average gradients over a sampled subset. Uniform sampling produces an unbiased estimate of the full gradient; averaging independent samples reduces its variance. Mini-batches also support efficient vectorized computation and parallel computing, although larger batches require more work per update. Stochastic updates need not decrease the full objective at every iteration. (github.com)
Gradient computation and related methods
For linear regression, gradients can be derived directly from the squared-error objective. In artificial neural networks, backpropagation computes gradients by applying the chain rule through the model’s operations, commonly using automatic differentiation. Backpropagation calculates derivatives; gradient descent uses those derivatives to update parameters. They are distinct components of training. (classic.d2l.ai)
Momentum methods retain information from previous gradients to modify the update direction and can improve behavior on poorly conditioned problems. Newton’s method instead uses second-order curvature information. Basic gradient descent avoids constructing a full Hessian matrix, but this simplicity can come at the cost of slower convergence when curvature varies substantially across directions. (github.com)