You have a function ff of many variables, and you want to find the input that makes it as small as possible. If you could write the gradient down, set it to zero, and solve the resulting equations, you would be done. But you cannot — the function is too complicated, the dimensions are too many, the equations are too tangled.

What you can do is evaluate ff at any point, and compute the gradient there. The gradient ∇f\nabla f at a point tells you the direction of steepest increase; the negative gradient −∇f-\nabla f therefore tells you the direction of steepest decrease. The plan is irresistibly simple: starting from some initial guess, take a small step in the direction −∇f-\nabla f. Then evaluate the gradient at the new point and take another small step. Repeat until you stop changing much.

This is gradient descent. It is one of the oldest numerical techniques in continuous optimisation — Cauchy described it in 1847 — and one of the most important algorithms in modern computational mathematics. Every time a neural network is trained, a logistic regression is fit, a recommender system is optimised, or a physics simulation finds an equilibrium configuration, some variant of gradient descent is at work in the background. This article is about why the rule works, when it fails, and how its modern variants enable the most spectacular applications.

The basic update

The mathematical statement is one line. Given a learning rate η>0\eta > 0 and a starting point x0\mathbf{x}_0, iterate

xk+1  =  xk−η ∇f(xk).\mathbf{x}_{k+1} \;=\; \mathbf{x}_k - \eta\,\nabla f(\mathbf{x}_k).

That is the entire algorithm. Three operations per iteration: evaluate the gradient, multiply by the learning rate, subtract from the current point. For a convex function with Lipschitz-continuous gradient of constant LL — meaning ∥∇f(x)−∇f(y)∥≤L∥x−y∥\|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\| \leq L\|\mathbf{x} - \mathbf{y}\| — choosing η≤1/L\eta \leq 1/L guarantees the iterates converge to the minimum, with the suboptimality gap f(xk)−f∗f(\mathbf{x}_k) - f^* shrinking like O(1/k)O(1/k). For strongly convex functions the convergence is even faster, exponential in kk. These guarantees are not artistic suggestions; they are theorems with one-line proofs from the right definitions.

A picture of descent

The clearest way to see what gradient descent does is to watch a single trajectory on a simple landscape. Take

f(x,y)=14x2+2y2,f(x, y) = \tfrac{1}{4}x^2 + 2y^2,

whose contour lines are ellipses concentric at the origin. Starting from (5,2.5)(5, 2.5) with learning rate η=0.15\eta = 0.15, the algorithm produces the sequence of dots shown below.

Gradient descent on f(x, y) = ¼ x² + 2 y² from (5, 2.5) x y minimum start trajectory descends quickly to the y = 0 axis, then drifts left toward the minimum

The picture reveals a phenomenon that is characteristic of gradient descent on ill-conditioned problems: the trajectory drops to the long axis of the ellipses quickly, then drifts slowly along it toward the minimum. The reason is the conditioning of ff. The coefficient on y2y^2 is eight times the coefficient on x2x^2, so the gradient is eight times larger in the yy direction at any given off-axis point. A fixed step size therefore moves a lot in yy and only a little in xx. The first few iterates correct the larger error fast and the smaller error slow — a slow trickle along the long axis afterwards.

This is not a defect specific to ellipses. In any realistic optimisation, the function’s Hessian (matrix of second derivatives) is not the identity; its eigenvalues vary, and the algorithm’s progress is governed by their ratio. This ratio is called the condition number κ\kappa, and the convergence rate of gradient descent on strongly convex functions is roughly O((1−1/κ)k)O((1 - 1/\kappa)^k). Highly conditioned problems — with small κ\kappa — converge in a few steps; ill-conditioned ones with large κ\kappa converge glacially. Almost all of the interesting research in modern optimisation amounts to clever ways of fighting the condition number.

The learning rate

The single most influential decision a user makes in applying gradient descent is the choice of learning rate η\eta. Too small and convergence takes thousands of iterations to make progress that could be made in dozens. Too large and the iterates overshoot the minimum at each step, bouncing back and forth across it or even spiralling outwards. The textbook analysis pinpoints a sharp threshold: for a convex function with Lipschitz-smooth gradient of constant LL, any η≤1/L\eta \leq 1/L is safe and produces convergence; above that, monotone descent is no longer guaranteed.

In practice, LL is rarely known in advance. Line search strategies — choose η\eta to minimise ff along the descent direction — are theoretically clean but expensive. Adaptive learning rates, in which η\eta is shrunk over time or adjusted per coordinate, are the modern default. The most popular of these, Adam (Kingma and Ba, 2014), maintains running estimates of the first and second moments of past gradients and uses them to set per-coordinate step sizes automatically. Most production neural-network training in the world is done with Adam or one of its descendants.

Stochastic gradient descent

For machine learning applications, evaluating the full gradient is the bottleneck. A modern training set might have ten million examples, and computing the gradient on all of them per iteration is far too slow. Stochastic gradient descent (SGD) replaces the exact gradient with an unbiased estimate computed from a small random batch — often as small as a single example. The estimate is noisy, but its expected value is the true gradient, and the iterates still converge to the minimum in the long run.

The mathematical guarantee is weaker: the convergence rate degrades to O(1/k)O(1/\sqrt{k}) for general convex problems, and to a noise-floor for strongly-convex ones. But the per-iteration cost drops by a factor of the dataset size, and the total wall-clock time to reach a good answer is dramatically lower. For modern deep learning, SGD and its variants — momentum, AdaGrad, RMSProp, Adam — are the only feasible optimisation algorithms.

There is a subtler benefit. The noise in the SGD estimate sometimes helps the algorithm escape bad saddle points and shallow local minima that would trap deterministic gradient descent. This is one reason why deep neural networks, which have non-convex loss landscapes with many saddles, are trainable at all using stochastic gradients. The dynamics of SGD on non-convex problems are an active research area; the empirical fact is that it works astoundingly well in practice, far better than the theoretical guarantees would have predicted.

Momentum and friends

A modification due originally to Polyak in 1964, but rediscovered by every generation since, dramatically accelerates gradient descent: keep a running velocity vector and update the position from the velocity, not from the gradient. Explicitly,

vk+1=β vk+∇f(xk),xk+1=xk−η vk+1.\mathbf{v}_{k+1} = \beta\,\mathbf{v}_k + \nabla f(\mathbf{x}_k), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k - \eta\,\mathbf{v}_{k+1}.

The momentum parameter β\beta is typically around 0.90.9. The effect is that the iterates accumulate past gradient directions; if successive gradients point the same way (a sustained descent), the algorithm picks up speed. If they oscillate (zigzagging across a valley), they cancel. For ill-conditioned problems, momentum can improve the convergence rate from O((1−1/κ)k)O((1 - 1/\kappa)^k) to O((1−1/κ)k)O((1 - 1/\sqrt{\kappa})^k) — a square-root improvement in the condition number. Nesterov’s accelerated gradient (1983) achieves the same rate provably and is the gold standard for first-order methods on smooth convex problems.

What it built

Gradient descent and its variants are the engine of almost every modern data-driven application. Deep neural networks, with their hundreds of millions of parameters, are trained essentially exclusively by SGD-with-momentum or Adam-like algorithms. Linear and logistic regression at large scale use gradient methods; the support vector machine is fitted with a gradient procedure on its dual; principal component analysis can be computed via gradient descent on a Lagrangian.

In physics and engineering, gradient descent is how variational quantum eigensolvers find ground states, how shape-optimal designs find their geometry, how robot trajectories are planned, and how protein folding is modelled. In scientific computing, it powers the implicit time-stepping of many partial differential equations. In operations research, gradient methods power large-scale optimisation in transportation, scheduling, and electricity grid management.

Anywhere a quantity needs to be minimised over a continuous space and the gradient is computable, gradient descent will plausibly do the job. The whole modern industry of automatic differentiation — frameworks like PyTorch and JAX — exists primarily to make gradient computation easy, so that gradient descent can be applied to ever more elaborate models.

Why it remains a single beautiful idea

Despite all the variants and refinements, the core of gradient descent has not changed since Cauchy: at each step, head downhill. The mathematical depth has accumulated around the questions of how to step — how big, in what direction, with what scaling, with what memory — but the underlying instinct is still that of a hiker on a foggy mountain. You cannot see the valley below, but you can feel the ground tilting beneath your feet, and you keep walking in that direction.

That such an intuitive rule, with so simple a mathematical statement, would turn out to be the workhorse of the largest computational projects in human history is one of the deeper surprises of contemporary mathematics. The training of a state-of-the-art neural network, with its billions of parameters and weeks of compute time, is in essence the same operation Cauchy described in 1847 — done by a computer instead of a human, on a model of a complexity Cauchy could not have imagined, and yet faithful in spirit to the original. A great algorithm is one that scales. Gradient descent has scaled by a factor of more than a billion. That is the mark of a truly great algorithm.

Frequently asked

Who invented gradient descent?

Augustin-Louis Cauchy described the basic idea in 1847, in the context of solving systems of equations: at each iteration, move in the direction of steepest descent. He proposed it as a numerical technique for problems where analytical solutions were unavailable. The modern formulation for differentiable convex optimisation and the convergence analyses are due to a long series of contributions through the 20th century, with major refinements by Nemirovski and Yudin in the 1970s and others. The stochastic variant — using random sub-samples — is much newer in popular use, although Robbins and Monro proved its first convergence theorem in 1951.

Why does the learning rate matter so much?

Because it controls how big each step is, and the same algorithm with a poorly-chosen step size can do anything from converging to the minimum, oscillating around it forever, or diverging entirely. Too small a step and convergence is glacial. Too large and the iterates bounce back and forth across the minimum, possibly amplifying with each step. For convex problems with smoothness L, the safe step size is at most 1/L; for the ill-conditioned ellipses that arise in real problems, hand-tuning or adaptive schemes like Adam are usually needed. Choosing the learning rate is the single most important practical decision in applied gradient descent.

What is stochastic gradient descent?

Instead of computing the gradient on the entire dataset at each iteration — which is wasteful when the dataset has millions of points — stochastic gradient descent (SGD) computes the gradient on a small random batch. The estimate is noisy, but it is unbiased: on average it points in the right direction. The noise actually helps escape shallow local minima and saddle points in non-convex problems, which is one reason SGD works well for training deep neural networks. The convergence guarantees are weaker (a worse rate), but the per-iteration cost is dramatically lower, and the overall efficiency is usually much better.

Does gradient descent always find the global minimum?

Only for convex functions. A convex function has no local minima other than the global one, so any descent procedure will eventually reach it. For non-convex functions — which include most loss functions of neural networks — gradient descent may get stuck in local minima or near saddle points. The remarkable empirical observation of the deep learning era is that for sufficiently large neural networks, most local minima have nearly the same loss value, and SGD reliably finds good ones. The theoretical reason this works is still actively debated; a complete explanation would be a Fields-Medal-level result.

Continue reading

Blog

The Universal Approximation Theorem: Why Neural Networks Can Learn Anything

A neural network with one hidden layer, given enough neurons, can approximate any continuous function to any accuracy. The 1989 theorem proving this is the mathematical license behind modern AI.

Read →Blog

Dynamic Programming: Solving Hard Problems by Remembering Easy Ones

Many problems repeat the same subproblems over and over. Storing each answer the first time you compute it can turn an exponential algorithm into a polynomial one — sometimes a stunning speedup.

Read →Blog

Principal Component Analysis: Finding the Best Few Dimensions in a Cloud of Data

High-dimensional data has hidden low-dimensional structure. PCA finds it: the few orthogonal directions along which the data varies most. From genomics to image compression, it is everywhere.

Read →