Gradient descent

Repeat θ ← θ − η∇f(θ). The step size must respect the curvature: past η = 2/L the steepest direction diverges, and below it the flattest direction sets the pace, so the condition number κ = L/μ decides how many steps you need.

11 min read946 wordscore0 viewsupdated 2026-10-11

Definition

Gradient descent is the iteration θt+1=θt−η ∇f(θt)\theta_{t+1}=\theta_t-\eta\,\nabla f(\theta_t): from the current point, take a step of size η\eta (the learning rate) in the direction in which ff decreases fastest. Repeat until the gradient is (nearly) zero.

Every optimizer used to train neural networks is a modification of this one rule. SGD and mini-batch training replace the exact gradient by a cheap estimate, momentum smooths it, Adam rescales it per parameter. Their behaviour makes sense only once you understand how plain gradient descent interacts with the curvature of the loss, and that is the subject of this article.

The method is old. Augustin-Louis Cauchy described it in 1847, in a short note on solving systems of simultaneous equations by repeatedly moving downhill on a sum of squared residuals. Its convergence theory for smooth convex functions was worked out in the 1960s, notably by Polyak, and Nesterov later proved that for this function class no first-order method can beat a rate of order κ\sqrt\kappa where gradient descent pays κ\kappa, which is why accelerated methods exist (see Momentum and Nesterov accelerated gradient).

The update rule and why it points downhill

θt+1=θt−η ∇f(θt)⟺θt+1=arg⁡min⁡θ[f(θt)+∇f(θt)⊤(θ−θt)+12η∥θ−θt∥2]\theta_{t+1}=\theta_t-\eta\,\nabla f(\theta_t)\qquad\Longleftrightarrow\qquad \theta_{t+1}=\arg\min_{\theta}\Big[f(\theta_t)+\nabla f(\theta_t)^\top(\theta-\theta_t)+\tfrac{1}{2\eta}\lVert\theta-\theta_t\rVert^2\Big]
θ\theta
all trainable parameters, as one vector
∇f(θt)\nabla f(\theta_t)
the gradient: the vector of partial derivatives ∂f/∂θj\partial f/\partial\theta_j, which points in the direction of steepest ascent
η\eta
learning rate (step size), η>0\eta>0
12η∥⋅∥2\tfrac{1}{2\eta}\lVert\cdot\rVert^2
a penalty for moving far from where the linear approximation was taken; small η\eta = little trust in it

The right-hand form shows what a step really is: minimize the first-order Taylor model of ff around θt\theta_t, but stay close because the model is only locally accurate. Setting its derivative to zero gives exactly the left-hand rule. Among all directions of unit length, −∇f/∥∇f∥-\nabla f/\lVert\nabla f\rVert makes the directional derivative most negative, so this is steepest descent in the Euclidean norm. Change the norm and you change the method: preconditioned and adaptive methods are steepest descent in a different geometry.

Curvature caps the step: L-smoothness

The linear model ignores curvature, and curvature is what makes a step overshoot. A function is LL-smooth if its gradient cannot change faster than LL times the distance moved; for a twice-differentiable ff this means every eigenvalue of the Hessian is at most LL in absolute value. Smoothness gives a quadratic upper bound on ff, and plugging the gradient step into it gives the descent lemma:

∥∇f(a)−∇f(b)∥≤L∥a−b∥    ⟹    f(θ−η∇f(θ))≤f(θ)−η(1−Lη2)∥∇f(θ)∥2\lVert\nabla f(a)-\nabla f(b)\rVert\le L\lVert a-b\rVert\;\;\Longrightarrow\;\; f\big(\theta-\eta\nabla f(\theta)\big)\le f(\theta)-\eta\Big(1-\frac{L\eta}{2}\Big)\lVert\nabla f(\theta)\rVert^2
LL
smoothness constant = largest curvature, λmax⁡\lambda_{\max} of the Hessian
1−Lη/21-L\eta/2
positive exactly when η<2/L\eta<2/L: then every step is guaranteed to decrease ff
η=1/L\eta=1/L
maximizes the guaranteed decrease, which is then ∥∇f∥2/(2L)\lVert\nabla f\rVert^2/(2L)

So 1/L1/L is the "safe" step and 2/L2/L the edge. The decrease is proportional to ∥∇f∥2\lVert\nabla f\rVert^2: gradient descent moves fast on steep slopes and slows to a crawl where the gradient is small, which is exactly where it spends most of its time on ill-conditioned problems.

Exact behaviour on a quadratic

Near a minimum, any smooth loss looks like a quadratic f(θ)=12(θ−θ∗)⊤H(θ−θ∗)f(\theta)=\tfrac12(\theta-\theta^*)^\top H(\theta-\theta^*), so the quadratic tells the whole local story. Its gradient is H(θ−θ∗)H(\theta-\theta^*), and writing the error δt=θt−θ∗\delta_t=\theta_t-\theta^* in the eigenbasis of HH decouples the iteration into one scalar recursion per eigen-direction:

δt+1=(I−ηH) δt⇒δt(i)=(1−ηλi)t δ0(i),converges  ⟺  ∣1−ηλi∣<1  ∀i  ⟺  η<2λmax⁡\delta_{t+1}=(I-\eta H)\,\delta_t\quad\Rightarrow\quad \delta^{(i)}_{t}=(1-\eta\lambda_i)^t\,\delta^{(i)}_0,\qquad \text{converges}\iff |1-\eta\lambda_i|<1\ \ \forall i\iff \eta<\frac{2}{\lambda_{\max}}
λi\lambda_i
eigenvalues of the Hessian HH: the curvature along each principal direction; μ=λmin⁡\mu=\lambda_{\min}, L=λmax⁡L=\lambda_{\max}
1−ηλi1-\eta\lambda_i
per-step multiplier of that direction: in (0,1)(0,1) monotone, in (−1,0)(-1,0) zigzag, below −1-1 divergent

Every direction shrinks at its own rate, and the slowest one sets the pace: ρ(η)=max⁡i∣1−ηλi∣=max⁡(∣1−ημ∣,∣1−ηL∣)\rho(\eta)=\max_i|1-\eta\lambda_i|=\max(|1-\eta\mu|,|1-\eta L|). Raising η\eta helps the flat direction but hurts the steep one. The two balance at η∗=2/(L+μ)\eta^*=2/(L+\mu), which gives the best possible constant-step rate:

ρ∗=L−μL+μ=κ−1κ+1,κ=Lμ,tε≈κ2ln⁡1ε  (error ∥δ∥ reduced by ε)\rho^*=\frac{L-\mu}{L+\mu}=\frac{\kappa-1}{\kappa+1},\qquad \kappa=\frac{L}{\mu},\qquad t_\varepsilon\approx\frac{\kappa}{2}\ln\frac{1}{\varepsilon}\ \ (\text{error }\lVert\delta\rVert\text{ reduced by }\varepsilon)
κ\kappa
condition number: how much steeper the steepest direction is than the flattest
tεt_\varepsilon
steps needed: linear in κ\kappa, logarithmic in the accuracy

Gradient descent at a glance

Update
θ←θ−η∇f(θ)\theta\leftarrow\theta-\eta\nabla f(\theta), one gradient per step
Stability
η<2/L\eta<2/L (on a quadratic: η<2/λmax⁡\eta<2/\lambda_{\max})
Safe default
η=1/L\eta=1/L: monotone decrease, guaranteed drop ∥∇f∥2/2L\lVert\nabla f\rVert^2/2L per step
Convex, L-smooth
f(θt)−f∗≤L∥θ0−θ∗∥22tf(\theta_t)-f^*\le\dfrac{L\lVert\theta_0-\theta^*\rVert^2}{2t} with η=1/L\eta=1/L: rate O(1/t)O(1/t)
μ-strongly convex
f(θt)−f∗≤(1−μ/L)t (f(θ0)−f∗)f(\theta_t)-f^*\le(1-\mu/L)^t\,(f(\theta_0)-f^*) with η=1/L\eta=1/L: linear (geometric) rate
Best constant step
η∗=2/(L+μ)\eta^*=2/(L+\mu), error contracts by (κ−1)/(κ+1)(\kappa-1)/(\kappa+1) per step
Non-convex
with η=1/L\eta=1/L, min⁡s<t∥∇f(θs)∥2≤2L (f(θ0)−f∗)/t\min_{s<t}\lVert\nabla f(\theta_s)\rVert^2\le 2L\,(f(\theta_0)-f^*)/t: finds a stationary point, not necessarily a minimum
f = ½(μx² + Ly²), L = 10, μ = 1.00, κ = 10startminf(θₜ) (log) vs step1e-81e-41step 0 … 80|1 − ηλ| vs curvature λ1: unstable aboveμL
|
t = 80 · f = 4.1e-11 · ‖∇f‖ = 9.0e-6 · ηL = 1.50 (limit 2)
per step: x ×0.85, y ×−0.50 → converges, zigzagging across the valley · loss ÷10⁶ after 40 steps
fig.Gradient descent on f = ½(μx² + Ly²) with L = 10, started at (−4, 1.5). The lower-right panel plots each direction's multiplier |1 − ηλ|; anything above the dashed line at 1 diverges. At the default η = 0.15 and κ = 10 the steep coordinate flips sign each step (×−0.50) while the flat one creeps (×0.85): the path zigzags and the loss falls by 10⁶ in 40 steps. η = 1/L kills the steep direction in one step but needs 62 steps; η = 2/(L+μ) = 0.182 balances the two at ×0.82 and needs only 35. At η = 0.199 the steep direction barely contracts (×−0.99) and it takes 661 steps; at η = 0.21 > 2/L it grows ×−1.1 per step and diverges. Raise κ to 50 at η = 0.15 and the same task takes 193 steps.

Worked example: the figure's first steps

Take the figure's defaults: μ=1\mu=1, L=10L=10 (κ=10\kappa=10), η=0.15\eta=0.15, start θ0=(−4, 1.5)\theta_0=(-4,\,1.5), so f(θ0)=12(16+22.5)=19.25f(\theta_0)=\tfrac12(16+22.5)=19.25. The gradient is (μx, Ly)(\mu x,\,Ly).

tθₜ = (x, y)∇f(θₜ)f(θₜ)
0(−4.000, 1.500)(−4.00, 15.00)19.250
1(−3.400, −0.750)(−3.40, −7.50)8.593
2(−2.890, 0.375)(−2.89, 3.75)4.879
3(−2.457, −0.188)(−2.46, −1.88)3.193
Plain gradient descent, η = 0.15 (values computed from the figure's code)
  1. 1The yy-component of the gradient is 15, almost 4 times the xx-component, so the first step is mostly across the valley: yy goes from 1.51.5 to 1.5−0.15⋅15=−0.751.5-0.15\cdot15=-0.75. It overshot the floor, because ηL=1.5>1\eta L=1.5>1.
  2. 2Each step multiplies yy by 1−0.15⋅10=−0.51-0.15\cdot10=-0.5 and xx by 1−0.15⋅1=0.851-0.15\cdot1=0.85. After 10 steps yy is 1.5⋅0.510≈0.00151.5\cdot0.5^{10}\approx0.0015, while xx is still −4⋅0.8510≈−0.79-4\cdot0.85^{10}\approx-0.79.
  3. 3From then on the flat direction is everything: the loss falls by 0.852≈0.720.85^2\approx0.72 per step, and reaching 10−610^{-6} of the start takes 40 steps in total.
  4. 4Change only η\eta to 0.210.21: the yy multiplier becomes −1.1-1.1, its magnitude grows 10% per step, and the loss passes 10610^6 at step 60 although the xx direction was converging the whole time.

What the condition number means in practice

For a linear model with squared loss the Hessian is the feature covariance 1NX⊤X\tfrac1N X^\top X, so κ\kappa is a property of the data. Features on very different scales, or strongly correlated features, give a large κ\kappa, and standardizing them (zero mean, unit variance) is the cheapest way to make gradient descent faster. Normalization layers, careful initialization and residual connections play a similar role in deep networks; adaptive optimizers and second-order methods attack κ\kappa directly.

Neural-network losses are not quadratic, and the Hessian changes along the path. Cohen et al. (2021) found that full-batch gradient descent on neural networks typically drives the largest Hessian eigenvalue (the sharpness) up until it hovers around 2/η2/\eta, the edge of stability, and training keeps making progress there, non-monotonically. The 2/L2/L rule is still the right mental model; the network just adapts its own LL to the step size.

python
1import torch
2
3# f(θ) = ½(μ x² + L y²) with μ = 1, L = 10
4H = torch.tensor([1.0, 10.0])
5f = lambda th: 0.5 * (H * th**2).sum()
6
7theta = torch.tensor([-4.0, 1.5], requires_grad=True)
8eta = 0.15
9for t in range(3):
10 loss = f(theta)
11 (g,) = torch.autograd.grad(loss, theta)
12 with torch.no_grad():
13 theta -= eta * g # θ ← θ − η ∇f
14 print(t + 1, theta.tolist(), f(theta).item())
15# ≈ 1 [-3.4, -0.75] 8.5925 2 [-2.89, 0.375] 4.8792 3 [-2.4565, -0.1875] 3.193
16
17# The same update through the optimizer API (full gradient = gradient descent)
18theta = torch.tensor([-4.0, 1.5], requires_grad=True)
19opt = torch.optim.SGD([theta], lr=0.15) # no momentum: plain GD step
20for _ in range(3):
21 opt.zero_grad()
22 f(theta).backward()
23 opt.step()
24
25# Estimate L = λ_max(Hessian) without forming the Hessian: power iteration on H·v
26def top_eigenvalue(loss_fn, params, iters=20):
27 v = [torch.randn_like(p) for p in params]
28 for _ in range(iters):
29 norm = torch.sqrt(sum((u**2).sum() for u in v))
30 v = [u / norm for u in v]
31 grads = torch.autograd.grad(loss_fn(), params, create_graph=True)
32 Hv = torch.autograd.grad(grads, params, grad_outputs=v)
33 lam = sum((h * u).sum() for h, u in zip(Hv, v)).item() # Rayleigh quotient
34 v = [h.detach() for h in Hv]
35 return lam
36
37print(top_eigenvalue(lambda: f(theta), [theta])) # ≈ 10.0, so keep η below 2/10 = 0.2
Gradient descent by hand, the same with torch.optim.SGD, and an estimate of L by power iteration on Hessian-vector products

Use when

  • +One hyperparameter, one gradient per step, no extra state: the simplest possible optimizer
  • +Guaranteed monotone decrease for η<2/L\eta<2/L, with clean convergence rates on convex problems
  • +Works for any differentiable loss; the template every other optimizer modifies

Avoid when

  • −Steps needed grow linearly with the condition number κ\kappa; slow on ill-conditioned problems
  • −The best η\eta depends on curvature you usually do not know; too large diverges
  • −Exact gradients of a large dataset are expensive (see batch vs stochastic variants)
  • −On non-convex losses it finds a stationary point, which can be a saddle or a poor local minimum

Check yourself

The largest Hessian eigenvalue of your loss near the minimum is 50. Which learning rate is the largest one for which gradient descent still converges there?

Check yourself

On f = ½(x² + 100y²) you use the best constant step η = 2/(L+μ). Roughly how much does the error shrink per step?

Remember

  • ✓Update: θ←θ−η∇f(θ)\theta\leftarrow\theta-\eta\nabla f(\theta), the minimizer of the linear model plus a proximity penalty 12η∥Δθ∥2\tfrac1{2\eta}\lVert\Delta\theta\rVert^2.
  • ✓LL-smoothness bounds curvature; every step decreases ff when η<2/L\eta<2/L, and η=1/L\eta=1/L is the safe default.
  • ✓On a quadratic each eigen-direction is multiplied by 1−ηλi1-\eta\lambda_i: divergence past 2/λmax⁡2/\lambda_{\max}, slow progress along λmin⁡\lambda_{\min}.
  • ✓Best constant rate (κ−1)/(κ+1)(\kappa-1)/(\kappa+1); steps grow like κlog⁡(1/ε)\kappa\log(1/\varepsilon).
  • ✓Convex: O(1/t)O(1/t); strongly convex: linear (1−μ/L)t(1-\mu/L)^t; non-convex: gradient norm →0\to0.
← back to Deep Learning roadmap