Gradient descent and variants — convergence analysis: Worked examples

Before anything: three words we will keep using, pinned to a picture.

The scenario matrix

Every cell below is a distinct behaviour GD can exhibit. Each is claimed by exactly one example.

Cell	Input class	What makes it special	Example
A	$κ = 1$ , round bowl	converges in ONE step	Ex 1
B	$κ$ large, thin canyon	crawls, zig-zags	Ex 2
C	step $η > 2/ L$	diverges (oscillates outward)	Ex 3
D	step exactly $η = 2/ L$	boundary: neither grows nor shrinks	Ex 4
E	$μ = 0$ , flat bottom ( $x^{4}$ )	convex but only $O (1/ k)$ , sublinear	Ex 5
F	momentum on cell B	turns $κ$ into $κ$	Ex 6
G	noisy gradients (SGD)	constant $η$ leaves a residual ball	Ex 7
H	real-world word problem	pick $η$ from data (logistic-style)	Ex 8
I	exam twist: negative eigenvalue	$f$ not convex — GD escapes/diverges	Ex 9

Sign coverage note. The one-step contraction factor is $1 - η λ$ . We will meet it positive ( $η λ < 1$ , cell B), zero ( $η λ = 1$ , cell A), negative but $> - 1$ (overshoot yet converge, Ex 4 discussion), equal to $- 1$ (boundary, cell D), below $- 1$ (divergence, cell C), and with $λ < 0$ (non-convex, cell I). Every sign is shown.

Ex 1 — Cell A: the perfectly round bowl ( $κ = 1$ )

Worked example One-step convergence

Minimize $f (x) = \frac{1}{2} a x^{2}$ with $a = 4$ , starting at $x_{0} = 3$ . Use the optimal step $η^{⋆} = \frac{2}{μ + L}$ .

Forecast: guess how many iterations to reach $x^{⋆} = 0$ within machine precision. (Most people say "a few dozen".)

Step 1. Identify $μ$ and $L$ . Why this step? The whole rate depends on curvature, and for $f = \frac{1}{2} a x^{2}$ the second derivative is the constant $a$ , so $μ = L = a = 4$ , hence $κ = 1$ .

Step 2. Optimal step $η^{⋆} = \frac{2}{μ + L} = \frac{2}{4 + 4} = \frac{1}{4}$ . Why this step? The parent note proved $η^{⋆} = 2/ (μ + L)$ minimizes the worst contraction; here it collapses to $1/ a$ .

Step 3. Contraction factor $1 - η^{⋆} a = 1 - \frac{1}{4} \cdot 4 = 0$ . Why this step? The update is $x_{k + 1} = (1 - η a) x_{k}$ ; a factor of zero annihilates the error in a single hit.

Step 4. $x_{1} = (1 - 0) \cdot ?$ — no: $x_{1} = 0 \cdot x_{0} = 0$ . Done in one step.

Verify: $x_{1} = (1 - η^{⋆} a) x_{0} = 0 \cdot 3 = 0 = x^{⋆}$ . Sanity: a round bowl means the negative gradient points exactly at the minimum, and $η = 1/ a$ scales it to land there. Correct.

The contraction factor here is exactly zero — the boundary between the positive-factor world (Ex 2) and the overshoot world (Ex 4).

Ex 2 — Cell B: the thin canyon (large $κ$ )

Figure — Gradient descent and variants — convergence analysis

Worked example GD crawling in an anisotropic bowl

Minimize $f (x, y) = \frac{1}{2} (x^{2} + 100 y^{2})$ from $(x_{0}, y_{0}) = (1, 1)$ , with $η^{⋆} = \frac{2}{μ + L}$ .

Forecast: which coordinate converges fast and which slow? By how much does the error shrink each step?

Step 1. Read off eigenvalues. Why this step? The Hessian is diagonal $diag (1, 100)$ , so the two curvatures are $μ = 1$ (the $x$ direction, gentle) and $L = 100$ (the $y$ direction, steep). Thus $κ = 100$ .

Step 2. $η^{⋆} = \frac{2}{1 + 100} = \frac{2}{101}$ . Why this step? This is the value that balances the two directions' contraction so neither blows up.

Step 3. Worst rate $ρ^{⋆} = \frac{κ - 1}{κ + 1} = \frac{99}{101} \approx 0.9802$ . Why this step? The slowest eigendirection (here $x$ , the gentle one) governs; its factor is $∣1 - η^{⋆} μ ∣ = ∣1 - \frac{2}{101} ∣ = \frac{99}{101}$ .

Step 4. Per-step error shrinks by only $1 - 0.9802 \approx 2%$ . To cut error by $10 \times$ needs $k$ with $0.980 2^{k} = 0.1$ , i.e. $k = ln 0.1/ ln 0.9802 \approx 115$ . Why this step? Solving $ρ^{k} = 0.1$ tells us the crawl length.

Verify: $ρ^{⋆} = 99/101 = 0.980198 \dots$ and $ln (0.1) / ln (99/101) = 115.0 \dots$ Look at s01: the red path zig-zags across the steep $y$ direction while inching along the gentle $x$ direction — the visual signature of large $κ$ .

Ex 3 — Cell C: too big a step ⟹ divergence

Ex 4 — Cell D: the exact boundary $η = 2/ L$

Sign ledger so far: Ex 1 factor $= 0$ , Ex 2 factor $\in (0, 1)$ , Ex 4 factor $= - 1$ , Ex 3 factor $< - 1$ . The remaining sign — factor $\in (- 1, 0)$ , overshoot yet converge — happens for any $η \in (1/ L, 2/ L)$ ; e.g. $η = 0.75$ here gives factor $1 - 0.75 \cdot 2 = - 0.5$ , converging while alternating sides.

Ex 5 — Cell E: the flat bottom ( $μ = 0$ , sublinear)

Worked example Convex but NOT strongly convex

Minimize $f (x) = \frac{1}{4} x^{4}$ (so $f^{'} = x^{3}$ ), from $x_{0} = 1$ , constant $η = 0.1$ .

Forecast: does the error fall geometrically like $ρ^{k}$ , or slower?

Step 1. Curvature at the min. Why this step? $f^{''} (x) = 3 x^{2}$ , which is $0$ at $x^{⋆} = 0$ . So $μ = 0$ : no matter how small a parabola you try, near the bottom $f$ is flatter. Strong convexity fails.

Step 2. Update $x_{k + 1} = x_{k} - η x_{k}^{3} = x_{k} - 0.1 x_{k}^{3}$ . Why this step? Near $0$ , $x_{k}^{3}$ is tiny, so the step becomes minuscule — progress stalls.

Step 3. From $x_{0} = 1$ : $x_{1} = 1 - 0.1 (1)^{3} = 0.9$ ; $x_{2} = 0.9 - 0.1 (0.9)^{3} = 0.8271$ . Why this step? Compute the first steps to feel the slowing.

Step 4. Asymptotic rate. Why this step? For $f = x^{4}$ the error obeys $x_{k} \sim c k^{- 1/2}$ — polynomial, not geometric. That is the $O (1/ k)$ -flavoured (in fact sublinear) behaviour the parent note warned about for $μ = 0$ .

Verify: $x_{1} = 0.9$ and $x_{2} = 0.9 - 0.1 \cdot 0. 9^{3} = 0.82710$ . In s03 the red trajectory glues itself to the flat bottom, dawdling — contrast the crisp geometric drop of a strongly convex bowl.

Ex 6 — Cell F: momentum turns $κ \to κ$

Worked example Heavy-ball on the thin canyon

Same $f (x, y) = \frac{1}{2} (x^{2} + 100 y^{2})$ as Ex 2 ( $κ = 100$ ). Use momentum with the tuned rate.

Forecast: momentum's rate is $\frac{κ - 1}{κ + 1}$ — how many fewer iterations than plain GD?

Step 1. GD rate (from Ex 2): $ρ_{GD} = \frac{99}{101} \approx 0.9802$ . Why this step? We need a baseline to compare against.

Step 2. Momentum rate $ρ_{mom} = \frac{κ - 1}{κ + 1} = \frac{10 - 1}{10 + 1} = \frac{9}{11} \approx 0.8182$ . Why this step? $100 = 10$ ; the parent note's mnemonic "GD has $κ$ , momentum has $κ$ " is literally this substitution.

Step 3. Iterations to cut error $10 \times$ : GD needs $ln 0.1/ ln 0.9802 \approx 115$ ; momentum needs $ln 0.1/ ln 0.8182 \approx 11.5$ . Why this step? Solve $ρ^{k} = 0.1$ for each and compare.

Step 4. Speed-up $\approx 115/11.5 \approx 10 \times$ . Why this step? Ratio of the two iteration counts.

Verify: $ρ_{mom} = 9/11 = 0.81818 \dots$ , and $ln (0.1) / ln (9/11) = 11.49 \dots$ vs $115.0$ for GD. Speed-up factor $\approx 10$ . Same landscape, an order of magnitude fewer steps — the single biggest practical win.

Ex 7 — Cell G: noisy gradients (SGD residual ball)

Worked example Why a constant step can't reach the exact minimum

Minimize $f (x) = \frac{1}{2} a x^{2}$ , $a = 2$ , but each observed gradient is $g_{k} = a x_{k} + ε_{k}$ with noise variance $E [ε_{k}^{2}] = σ^{2} = 1$ . Use constant $η = 0.1$ . See Stochastic Approximation (Robbins–Monro).

Forecast: does $x_{k} \to 0$ exactly, or bounce forever in a small ball?

Step 1. Noiseless part contracts. Why this step? $x_{k + 1} = (1 - η a) x_{k} - η ε_{k} = (1 - 0.2) x_{k} - 0.1 ε_{k}$ ; the signal shrinks by factor $0.8$ .

Step 2. Steady-state variance. Why this step? At equilibrium $Var (x_{\infty}) = (0.8)^{2} Var (x_{\infty}) + (0.1)^{2} σ^{2}$ , so $Var (x_{\infty}) = \frac{( 0.1 ) ^{2} \cdot 1}{1 - 0.64} = \frac{0.01}{0.36}$ .

Step 3. Residual radius $Var = 0.01/0.36 = \frac{0.1}{0.6} \approx 0.1667$ . Why this step? $x_{k}$ never settles below this spread — the "ball of radius $\sim η σ$ " the parent note described.

Verify: $Var (x_{\infty}) = 0.01/0.36 = 0.027 \overline{7}$ , radius $= 1/6 \approx 0.16667$ . Fix: decay $η_{k}$ (e.g. $η_{k} = 1/ k$ ) so the injected term $η_{k}^{2} σ^{2} \to 0$ ; then the ball shrinks to a point.

Ex 8 — Cell H: real-world word problem (choose $η$ from data)

Worked example Setting the learning rate for a logistic-style loss

A model has smoothness constant $L = \frac{1}{4} λ_{m a x} (X^{⊤} X)$ . Suppose the largest eigenvalue of $X^{⊤} X$ is $λ_{m a x} = 40$ , and the smallest relevant curvature gives $μ = 0.5$ . Pick a safe monotone step and predict the rate.

Forecast: what $η$ guarantees the loss never increases, and how ill-conditioned is this problem?

Step 1. Compute $L$ . Why this step? The Hessian of logistic loss is $\frac{1}{4} X^{⊤} D X$ with $D ⪯ I$ , so its top curvature is at most $\frac{1}{4} λ_{m a x} (X^{⊤} X) = \frac{1}{4} \cdot 40 = 10$ .

Step 2. Safe monotone step $η = 1/ L = 1/10 = 0.1$ . Why this step? The parent note proved $η = 1/ L$ gives the guaranteed drop $f (x_{k + 1}) \leq f (x_{k}) - \frac{1}{2 L} ∥\nabla f ∥^{2}$ — no line search needed.

Step 3. Condition number $κ = L / μ = 10/0.5 = 20$ . Why this step? This sets the linear rate.

Step 4. Optimal-step rate $ρ^{⋆} = \frac{κ - 1}{κ + 1} = \frac{19}{21} \approx 0.9048$ . Why this step? With the tuned step $2/ (μ + L)$ you get this; the safe $η = 1/ L$ is slightly slower but always safe.

Verify: $L = 10$ , $κ = 20$ , $ρ^{⋆} = 19/21 = 0.90476 \dots$ . Units check: $η$ has units of (input)²/(loss), matching $1/ L$ since $L$ is a curvature (loss per input²). Consistent.

Ex 9 — Cell I: the exam twist (negative curvature, non-convex)

Worked example A saddle-flavoured direction where GD runs away

Consider $f (x) = - \frac{1}{2} b x^{2}$ with $b = 3$ (a downward parabola, curvature $- 3$ ). Start $x_{0} = 0.01$ , any positive $η = 0.1$ .

Forecast: does GD find a minimum? (Trick — there is none.)

Step 1. Curvature sign. Why this step? $f^{''} = - 3 < 0$ , so $λ = - 3$ : this direction is concave. No $μ > 0$ exists; the assumptions of every convergence theorem are violated.

Step 2. Update factor $1 - η λ = 1 - 0.1 \cdot (- 3) = 1.3$ . Why this step? With a negative eigenvalue the factor exceeds $1$ for every positive $η$ — there is no safe step.

Step 3. Iterate: $x_{1} = 1.3 \cdot 0.01 = 0.013$ , and $x_{k} = 1. 3^{k} \cdot 0.01 \to \infty$ . Why this step? GD climbs toward $+ \infty$ because $- \nabla f$ points away from the (nonexistent) minimum.

Verify: $x_{5} = 1. 3^{5} \cdot 0.01 = 0.0371293$ , growing. Lesson: GD's guarantees are only as good as convexity; a single negative eigenvalue (saddle/max) breaks them. This is the boundary of the whole theory — and why Newton's Method (second-order methods) (which uses curvature) is invoked near saddles.

The completed matrix

Every cell A–I now has a worked, verified example. The contraction factor $1 - η λ$ has appeared with value $0$ (Ex 1), in $(0, 1)$ (Ex 2), $= - 1$ (Ex 4), $< - 1$ (Ex 3), $> 1$ with $λ > 0$ (Ex 3), and $> 1$ with $λ < 0$ (Ex 9); the degenerate $μ = 0$ case (Ex 5), the noisy case (Ex 7), and a data-driven step (Ex 8) round out every scenario.

Recall Quick self-test

Which cell converges in one step, and why? ::: Cell A ( $κ = 1$ ): factor $1 - η a = 0$ when $η = 1/ a$ . For $κ = 100$ , how many iterations does GD need to cut error 10×? ::: About 115; momentum needs about 11.5. What is the exact step size at which GD oscillates forever without progress? ::: $η = 2/ L$ (factor $= - 1$ ). Why does constant- $η$ SGD not reach the exact minimum? ::: Noise injects variance $\propto η σ^{2}$ each step, leaving a residual ball. What breaks all convergence guarantees in Ex 9? ::: A negative eigenvalue ( $μ \leq 0$ ): no safe $η$ , GD diverges.