Gradient descent

• 1. Introduction

  ›

  Gradient descent is one of the oldest ideas in modern optimization, first suggested by Augustin-Louis Cauchy in 1847. For a method with such modest origins, it now shapes virtually every deep learning system running today. How does an algorithm conceived in the nineteenth century end up at the core of artificial intelligence? The answer lies in a strikingly simple physical intuition: if you want to find the lowest point of a landscape, just keep walking downhill.

  Imagine people stranded in fog-covered mountains, trying to reach the valley below. They cannot see far enough to chart a route. What they can do is check the slope beneath their feet, then step in the direction the ground falls most steeply. Each step brings them a little lower. They repeat this, measurement by measurement, until they reach the bottom. That is gradient descent in its entirety. The elegance of the idea masked a deeper challenge that researchers would spend decades untangling: choosing the right size of each step turns out to matter enormously.

• 2. A Century of Development

  ›

  Cauchy's 1847 proposal sat relatively quietly in the mathematical literature for decades. Jacques Hadamard independently arrived at a similar method in 1907, suggesting the idea was ripe enough to be discovered more than once. The formal study of whether gradient descent actually converges on difficult, non-linear problems did not begin until Haskell Curry took it up in 1944. From that point, the method attracted growing attention and use across the following decades.

  Yurii Nesterov proposed a key refinement that changed what practitioners could expect from the algorithm. For a convex function that is also Lipschitz continuous, the standard gradient descent method accumulates error that shrinks at a rate bounded by a certain expression per step. Nesterov's acceleration technique drove that error down at a fundamentally faster rate. His approach came to be called the fast gradient method or the accelerated gradient method. A later refinement, the optimized gradient method, cut the remaining constant factor in half and established itself as an optimal first-order method for large-scale problems.

• 3. The Step Size Problem

  ›

  Philip Wolfe advocated for what he called "clever choices of the descent direction" in practice, and his observation points to a genuine tension at the heart of the algorithm. A step size that is too small causes the algorithm to creep toward a solution, wasting computation. A step size that is too large causes it to overshoot and diverge entirely, never settling. Finding a good setting is not a theoretical nicety; it is a practical requirement every time the method is applied.

  Several strategies have emerged for handling this. The Wolfe conditions provide a principled set of criteria that a step size should satisfy, and line search methods can locate such a step on each iteration. Backtracking line search offers both theoretical guarantees and reliable experimental performance. The Barzilai-Borwein method selects step sizes from a specific sequence derived from the function's recent behavior. Each strategy trades off computational cost against the quality of the step it produces.

  The descent direction itself need not be the exact negative gradient. Any direction that forms a positive inner product with the gradient will reduce the function's value, provided the step is small enough. This flexibility is what opens the door to the whole family of modified optimizers built on gradient descent's foundation.

• 4. Zig-Zags and Saddle Points

  ›

  Even for the simplest case, unconstrained quadratic minimization, gradient descent develops a characteristic zig-zag path as it iterates. The cause is geometric: in steepest descent applied to a symmetric positive-definite system, successive residual vectors are orthogonal to each other. Each step is taken in the steepest direction available, so when the level sets of the function are elongated rather than circular, the algorithm alternates between directions aligned with the extreme axes of those level sets. The result is slow, oscillating progress.

  The condition number of the system matrix drives this behavior. The number of iterations required is commonly proportional to this ratio of maximum to minimum eigenvalues, while the conjugate gradient method converges in a number of iterations determined by the square root of the same ratio. That difference compounds quickly on large problems. Preconditioning, which reshapes the geometry of the function so that its level sets resemble concentric circles rather than elongated ellipses, addresses the slow convergence directly, though constructing and applying a good preconditioner carries its own computational cost.

  Saddle points present a different hazard. Gradient descent can slow dramatically in their neighborhood, and the zig-zag problem persists independently of whether a saddle is nearby. The momentum or heavy ball method addresses both issues by carrying a memory of the previous update into the next one. The next step is computed as a linear combination of the current gradient and the prior update, analogous to a heavy ball that builds momentum as it rolls across the surface of the function being minimized.

• 5. Machine Learning's Workhorse

  ›

  Stochastic gradient descent is described as the most basic algorithm used for training most deep networks today. It extends the standard method by introducing randomness into the update direction, drawing on a subset of the training data rather than the full dataset at each step. This makes each iteration cheaper and, somewhat counterintuitively, the noise in the updates can help the algorithm escape shallow local minima.

  The backpropagation algorithm that trains artificial neural networks relies on the momentum technique as an extension. The weights of a network encode learnable parameters, and the derivatives needed to update them are computed through the network's layers. The momentum term then shapes how those updates accumulate. Practical optimizers used in deep learning, including Adam, DiffGrad, Yogi, and AdaBelief, are all built on modifications introduced through momentum terms, exponential moving averages, and positive-negative momentum variants traced back to ideas from Nesterov, Polyak, and Frank-Wolfe.

  For extremely large problems where memory becomes the binding constraint, methods like L-BFGS are preferred over full second-order approaches. L-BFGS belongs to the family of methods based on Newton's method and Hessian inversion, which generally converge in fewer iterations than gradient descent but at a higher cost per step. The trade-off between per-iteration cost and total iterations is the central engineering question when selecting an optimizer for a real system.

• 6. Beyond Simple Minimization

  ›

  Gradient descent applies to spaces of any number of dimensions, including infinite-dimensional function spaces where the search object is a function rather than a vector of numbers. In that setting, the relevant derivative is the Frechet derivative of the functional being minimized. The theoretical basis for why the method works in any finite number of dimensions follows from the Cauchy-Schwarz inequality: the inner product of two vectors is maximized when they are collinear, which means moving in the direction of the gradient extracts the maximum possible decrease per unit of movement.

  Linear systems can be recast as quadratic minimization problems, making gradient descent applicable there as well. When the system matrix is real, symmetric, and positive-definite, the algorithm has an analytic closed form for the optimal step size at each iteration. The method is rarely the first choice for linear systems, since conjugate gradient converges far faster, but both methods benefit from preconditioning, and gradient descent may require weaker assumptions on the preconditioner than conjugate gradient does.

  The algorithm also connects to continuous mathematics in a precise way: gradient descent can be understood as applying Euler's method for ordinary differential equations to a gradient flow equation. That equation can itself be derived as an optimal controller for a particular control system. This link to differential equations and control theory is part of why gradient descent appears across fields as distant from machine learning as fluid dynamics, variational calculus, and the Yang-Mills and Seiberg-Witten flows studied in mathematical physics.