Optimization & Flows

Gradient Descent

Find a minimum by repeatedly stepping downhill — the workhorse that trains almost everything.

Shading is the loss (dark = low). The blue path steps downhill toward the green minimum; the orange dot is the current position. Too large a step and the path overshoots and flies off.

What you're seeing

The shaded surface is a loss function over two parameters; we want the darkest point, its minimum. The gradient ∇f points in the direction of steepest increase, so to go downhill we step the opposite way: x ← x − η∇f(x), where η (the learning rate) sets the stride. Watch the path slide into the basin. On the elongated valley it zig-zags — the gradient points mostly across the narrow valley rather than along it; on the Rosenbrock surface it crawls along a curved trough, the classic case that defeats plain gradient descent. And push the step size up and the whole thing overshoots and diverges.

The rule

x = starting point
repeat:
    g = ∇f(x)            # gradient: steepest-ascent direction
    x = x − η · g        # step downhill; η = learning rate
until ‖g‖ ≈ 0            # a flat spot — a (local) minimum

The invariant

The guarantee needs two conditions. If f is convex (no false valleys — any local min is the global min) and L-smooth (its gradient changes no faster than rate L), then with a step size η ≤ 1/L, every iteration decreases the loss, and the iterates converge to the minimum — the loss gap shrinks like O(1/t) after t steps (and exponentially fast if f is also strongly convex). The smoothness bound is what makes a fixed step safe: it caps how much the downhill direction can swing within one stride, so a step of 1/L can't overshoot the valley. Cross that threshold — η > 2/L — and each step lands further out than it started: the loss grows, the path oscillates outward, and it diverges. Slide the step size up on the elongated surface and watch exactly that happen. (Drop convexity, as in Rosenbrock, and you keep the per-step decrease but lose the guarantee of reaching the global minimum.)

The cost

per stepsteps to ε Convex, smooth1 gradientO(1/ε) Strongly convex1 gradientO(log 1/ε)

Each step costs one gradient evaluation and O(1) memory — which is why it scales to billions of parameters where second-order methods (needing the Hessian) can't. The catch is conditioning: convergence speed depends on the ratio of largest to smallest curvature (the elongated valley is slow precisely because that ratio is 12). Momentum, Nesterov acceleration, and preconditioners (Adam, etc.) exist to fight exactly that — and stochastic gradient descent replaces the full gradient with a cheap noisy estimate from a minibatch, the backbone of modern machine learning.

In the wild

Gradient descent (and its stochastic, mini-batch form, SGD) trains essentially every neural network and most of modern machine learning; it fits logistic/linear regression, powers logistic and softmax classifiers, solves large-scale optimization in operations research, and underlies inverse problems in imaging and physics. The variants are a field unto themselves — momentum (Polyak), Nesterov acceleration, AdaGrad/RMSProp/Adam — but they are all refinements of the one idea on screen: estimate the downhill direction and take a step.

Try this

On the Elongated valley, raise the Step size slowly: the path tightens, then starts zig-zagging harder, then overshoots and explodes — you're walking right up to the η = 2/L stability cliff. Switch to Rosenbrock and watch even a careful descent crawl along the curved floor of the valley — the textbook reason people reach for momentum and second-order methods.

References

  1. Cauchy, A. "Méthode générale pour la résolution des systèmes d'équations simultanées." 1847. The original gradient method.
  2. Boyd, S. & Vandenberghe, L. Convex Optimization, §9 (Unconstrained minimization). Cambridge, 2004. stanford.edu/~boyd/cvxbook.
  3. Nesterov, Y. Lectures on Convex Optimization, 2nd ed. Springer, 2018 — convergence rates, acceleration.
  4. Vishnoi, N. Algorithms for Convex Optimization, Cambridge, 2021. And Andoni, Advanced Algorithms (Columbia, 2021), gradient-descent lectures. course materials.