# 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.

Source: https://www.mlfoundry.in/learn/gradient-descent  
Section: Deep Learning › Optimization Algorithms  
Level: core · 11 min read · updated 2026-10-11

**Gradient descent:** is the iteration $\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 $f$ 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

$$
\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
- $\nabla f(\theta_t)$: the gradient: the vector of partial derivatives $\partial f/\partial\theta_j$, which points in the direction of steepest **ascent**
- $\eta$: learning rate (step size), $\eta>0$
- $\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 $f$ around $\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, $-\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 **$L$-smooth** if its gradient cannot change faster than $L$ times the distance moved; for a twice-differentiable $f$ this means every eigenvalue of the Hessian is at most $L$ in absolute value. Smoothness gives a quadratic upper bound on $f$, and plugging the gradient step into it gives the **descent lemma**:

$$
\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
$$

- $L$: smoothness constant = largest curvature, $\lambda_{\max}$ of the Hessian
- $1-L\eta/2$: positive exactly when $\eta<2/L$: then every step is guaranteed to decrease $f$
- $\eta=1/L$: maximizes the guaranteed decrease, which is then $\lVert\nabla f\rVert^2/(2L)$

So $1/L$ is the "safe" step and $2/L$ the edge. The decrease is proportional to $\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(\theta)=\tfrac12(\theta-\theta^*)^\top H(\theta-\theta^*)$, so the quadratic tells the whole local story. Its gradient is $H(\theta-\theta^*)$, and writing the error $\delta_t=\theta_t-\theta^*$ in the eigenbasis of $H$ decouples the iteration into one scalar recursion per eigen-direction:

$$
\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}}
$$

- $\lambda_i$: eigenvalues of the Hessian $H$: the curvature along each principal direction; $\mu=\lambda_{\min}$, $L=\lambda_{\max}$
- $1-\eta\lambda_i$: per-step multiplier of that direction: in $(0,1)$ monotone, in $(-1,0)$ zigzag, below $-1$ divergent

Every direction shrinks at its own rate, and the slowest one sets the pace: $\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 $\eta^*=2/(L+\mu)$, which gives the best possible constant-step rate:

$$
\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_\varepsilon$: steps needed: linear in $\kappa$, logarithmic in the accuracy

**Gradient descent at a glance**

- **Update:** $\theta\leftarrow\theta-\eta\nabla f(\theta)$, one gradient per step
- **Stability:** $\eta<2/L$ (on a quadratic: $\eta<2/\lambda_{\max}$)
- **Safe default:** $\eta=1/L$: monotone decrease, guaranteed drop $\lVert\nabla f\rVert^2/2L$ per step
- **Convex, L-smooth:** $f(\theta_t)-f^*\le\dfrac{L\lVert\theta_0-\theta^*\rVert^2}{2t}$ with $\eta=1/L$: rate $O(1/t)$
- **μ-strongly convex:** $f(\theta_t)-f^*\le(1-\mu/L)^t\,(f(\theta_0)-f^*)$ with $\eta=1/L$: linear (geometric) rate
- **Best constant step:** $\eta^*=2/(L+\mu)$, error contracts by $(\kappa-1)/(\kappa+1)$ per step
- **Non-convex:** with $\eta=1/L$, $\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

> Figure: 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: $\mu=1$, $L=10$ ($\kappa=10$), $\eta=0.15$, start $\theta_0=(-4,\,1.5)$, so $f(\theta_0)=\tfrac12(16+22.5)=19.25$. The gradient is $(\mu x,\,Ly)$.

Plain gradient descent, η = 0.15 (values computed from the figure's code)

| 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 |

1. The $y$-component of the gradient is 15, almost 4 times the $x$-component, so the first step is mostly across the valley: $y$ goes from $1.5$ to $1.5-0.15\cdot15=-0.75$. It overshot the floor, because $\eta L=1.5>1$.
2. Each step multiplies $y$ by $1-0.15\cdot10=-0.5$ and $x$ by $1-0.15\cdot1=0.85$. After 10 steps $y$ is $1.5\cdot0.5^{10}\approx0.0015$, while $x$ is still $-4\cdot0.85^{10}\approx-0.79$.
3. From then on the flat direction is everything: the loss falls by $0.85^2\approx0.72$ per step, and reaching $10^{-6}$ of the start takes 40 steps in total.
4. Change only $\eta$ to $0.21$: the $y$ multiplier becomes $-1.1$, its magnitude grows 10% per step, and the loss passes $10^6$ at step 60 although the $x$ 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 $\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/\eta$, the edge of stability, and training keeps making progress there, non-monotonically. The $2/L$ rule is still the right mental model; the network just adapts its own $L$ to the step size.

```python
import torch

# f(θ) = ½(μ x² + L y²) with μ = 1, L = 10
H = torch.tensor([1.0, 10.0])
f = lambda th: 0.5 * (H * th**2).sum()

theta = torch.tensor([-4.0, 1.5], requires_grad=True)
eta = 0.15
for t in range(3):
    loss = f(theta)
    (g,) = torch.autograd.grad(loss, theta)
    with torch.no_grad():
        theta -= eta * g                      # θ ← θ − η ∇f
    print(t + 1, theta.tolist(), f(theta).item())
# ≈ 1 [-3.4, -0.75] 8.5925   2 [-2.89, 0.375] 4.8792   3 [-2.4565, -0.1875] 3.193

# The same update through the optimizer API (full gradient = gradient descent)
theta = torch.tensor([-4.0, 1.5], requires_grad=True)
opt = torch.optim.SGD([theta], lr=0.15)       # no momentum: plain GD step
for _ in range(3):
    opt.zero_grad()
    f(theta).backward()
    opt.step()

# Estimate L = λ_max(Hessian) without forming the Hessian: power iteration on H·v
def top_eigenvalue(loss_fn, params, iters=20):
    v = [torch.randn_like(p) for p in params]
    for _ in range(iters):
        norm = torch.sqrt(sum((u**2).sum() for u in v))
        v = [u / norm for u in v]
        grads = torch.autograd.grad(loss_fn(), params, create_graph=True)
        Hv = torch.autograd.grad(grads, params, grad_outputs=v)
        lam = sum((h * u).sum() for h, u in zip(Hv, v)).item()   # Rayleigh quotient
        v = [h.detach() for h in Hv]
    return lam

print(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

> **Divergence looks like a bad model:** When $\eta>2/L$ the loss does not just plateau: it oscillates with growing amplitude and then becomes `inf` or `nan`. The direction that blows up is the steepest one, which may be only a handful of parameters, so the early symptom is a loss that bounces rather than falls. Halve the learning rate before suspecting the architecture or the data.

> **The flat directions pay for the steep one:** Gradient descent has one step size for every direction. The steepest direction caps it at $2/L$; the flattest direction then moves at $\eta\mu<2/\kappa$ of its distance per step. Nearly every improvement in this module (momentum, adaptive scaling, preconditioning, normalization) is a way of not paying that $\kappa$.

> **Gradient descent vs SGD vs mini-batch:** This article assumes the exact gradient. When $f$ is an average over a dataset, computing it exactly is **batch gradient descent**; using one random example is **stochastic gradient descent**; using a random subset is **mini-batch gradient descent**. All three share the curvature limits described here, and add noise on top.

**Strengths**

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

**Limitations**

- 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

**Question:** 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?

- A. Any η below 0.04
- B. Any η below 0.02
- C. Any η below 0.1
- D. Any η below 2

**Answer:** A. Any η below 0.04 — Along the top eigenvector the error is multiplied by $1-50\eta$ per step, which has magnitude below 1 only for $0<\eta<2/50=0.04$. At $\eta=0.02=1/L$ that direction is removed in a single step; between 0.02 and 0.04 it zigzags but still shrinks.

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

- A. ×0.50
- B. ×0.98
- C. ×0.90
- D. ×0.01

**Answer:** B. ×0.98 — $\kappa=100$, so $\rho^*=(\kappa-1)/(\kappa+1)=99/101\approx0.98$. Each step removes only about 2% of the remaining error, so cutting it by $10^6$ needs about $\ln(10^6)/0.0198\approx700$ steps. Better conditioning, not a better step size, is the fix.

**Key points**

- Update: $\theta\leftarrow\theta-\eta\nabla f(\theta)$, the minimizer of the linear model plus a proximity penalty $\tfrac1{2\eta}\lVert\Delta\theta\rVert^2$.
- $L$-smoothness bounds curvature; every step decreases $f$ when $\eta<2/L$, and $\eta=1/L$ is the safe default.
- On a quadratic each eigen-direction is multiplied by $1-\eta\lambda_i$: divergence past $2/\lambda_{\max}$, slow progress along $\lambda_{\min}$.
- Best constant rate $(\kappa-1)/(\kappa+1)$; steps grow like $\kappa\log(1/\varepsilon)$.
- Convex: $O(1/t)$; strongly convex: linear $(1-\mu/L)^t$; non-convex: gradient norm $\to0$.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
