Visual walkthrough — Gradient descent and variants — convergence analysis

We build up in steps. Each step says WHAT we do, WHY we do it, and WHAT IT LOOKS LIKE (a picture). Read the pictures — they carry the argument.

---

Step 1 — The one symbol everything rests on: the gradient arrow

WHAT. We have a function $f$ that eats a point and returns a height (a number). Think of a landscape: each spot $(x,y)$ on the floor has a height $f(x,y)$. We want the lowest spot.

The gradient, written $\nabla f(x)$, is an arrow drawn on the floor at the point $x$. It points in the direction where the height climbs fastest, and its length says how steeply.

WHY this arrow and not some other direction? Because "downhill-steepest" is exactly the direction that lowers our height the most per unit of walking. Among all directions $u$ of length 1, the amount the height changes as you step is the number $\nabla f(x{)}^{\top }u$ — the dot product of the two arrows.

PICTURE.

Look at the red arrow (uphill) and its blue flip (downhill). The green dashed rings are level sets — spots of equal height, like contour lines on a map. Notice the arrow is always perpendicular to the ring it sits on: that is the visual signature of "steepest".

---

Step 2 — Bounding the wildness of $f$: the two curvature walls

WHAT. To promise anything about progress, we must forbid $f$ from being arbitrarily wild. We pin its curvature (how fast the slope itself changes) between two numbers: a ceiling $L$ and a floor $\mu$.

WHY two walls? The ceiling $L$ stops us from overshooting (if we don't know how sharply the floor can bend up, we can't pick a safe step). The floor $\mu$ stops the valley from being infinitely flat at the bottom (a flat bottom means the gradient dies and we crawl forever). One wall controls safety, the other controls speed.

PICTURE.

The dark blue curve is $f$. The yellow parabola (curvature $L$) hugs it from above; the green parabola (curvature $\mu$) hugs it from below. $f$ is trapped in the sandwich. Their ratio

$\kappa =\frac{L}{\mu }\ge 1$

is the condition number — $\kappa =1$ means the two walls coincide (a perfect bowl); large $\kappa$ means a long thin trough.

---

Step 3 — The Descent Lemma: replacing the hill with a parabola we can minimize

WHAT. We turn the ceiling wall into a usable inequality. Starting from a point $x$ and looking at any other point $y$:

WHY build this? Because we can't minimize the true foggy hill $f$ — but we can minimize a parabola exactly, in one shot. If we lower this over-estimating parabola, we've provably lowered $f$ too. That's the engine of every proof.

Where it comes from — the concrete two-line sketch. Let $\Delta =y-x$. The fundamental theorem of calculus says the total height change is the running sum of the slope along the segment from $x$ to $y$:

$f(y)-f(x)={\int }_0^1\nabla f(x+t\Delta {)}^{\top }\Delta dt.$

Subtract the flat "linear guess" $\nabla f(x{)}^{\top }\Delta$ from both sides and use the ceiling wall (the gradient can drift at most $Lt\Vert \Delta \Vert$ over distance $t\Vert \Delta \Vert$):

$f(y)-f(x)-\nabla f(x{)}^{\top }\Delta ={\int }_0^1[\nabla f(x+t\Delta )-\nabla f(x){]}^{\top }\Delta dt\le {\int }_0^{1}Lt\Vert \Delta {\Vert }^{2}dt=\frac{L}{2}\Vert \Delta {\Vert }^2.$

The last integral ${\int }_0^{1}tdt=\frac{1}{2}$ is exactly where the factor $\frac{L}{2}$ is born.

PICTURE.

The blue curve is $f$; the yellow parabola is the Descent-Lemma bound anchored at the black dot $x$. They touch at $x$ (the bound is exact there) and the parabola stays above everywhere else. Its lowest point (yellow star) is where the next step lands.

---

Step 4 — One step of GD: how far the parabola lets us drop

WHAT. Plug the actual GD move $y=x_k-\eta \nabla f(x_k)$ into the Descent Lemma. Write $g=\nabla f(x_k)$ for the gradient arrow at this step.

WHY this reveals the magic step. The net drop is $\eta (1-\frac{L\eta }{2})\Vert g{\Vert }^2$. As a function of $\eta$ this is an upside-down parabola: too small $\eta$ → tiny step; too big $\eta$ → the penalty eats the gain. Its peak is at $\eta =1/L$, giving the clean guarantee

$f(x_{k+1})\le f(x_k)-\frac{1}{2L}\Vert g{\Vert }^2.$

PICTURE.

The curve plots drop per step against step size $\eta$. It's zero at $\eta =0$, peaks at $\eta =1/L$ (yellow star), and crosses back to zero at $\eta =2/L$ (red dot) — past which the "drop" goes negative, meaning the bound no longer promises any decrease. This single picture is why the parent's mnemonic says "below two-over-L you're well; at one-over-L, monotone descent."

---

Step 5 — Every quadrant of step size: safe, best, and exploding

WHAT. We now cover all regimes of $\eta$ so no reader hits an unshown case. Use the cleanest test problem, the 1-D bowl $f(x)=\frac{1}{2}L{x}^2$, where the update is $x_{k+1}=(1-\eta L)x_k$. The number $r=1-\eta L$ is the multiplier applied each step.

WHY the multiplier is everything. After $k$ steps the error is $r^k{x}_0$. So:

• $0<r<1$ (i.e. $0<\eta <1/L$): shrinks, all same sign — a gentle glide to zero.
• $r=0$ (i.e. $\eta =1/L$): lands exactly at the bottom in one step.
• $-1<r<0$ (i.e. $1/L<\eta <2/L$): shrinks but flips sign each step — converges while zig-zagging.
• $r=-1$ (i.e. $\eta =2/L$): bounces forever at the same height, never converging.
• $r<-1$ (i.e. $\eta >2/L$): grows and flips — explodes outward.

PICTURE.

Four trajectories on the same bowl. Green ($\eta <1/L$) slides in from one side. Yellow ($\eta =1/L$) drops straight to the minimum. Blue ($1/L<\eta <2/L$) overshoots and lands on alternating sides, still homing in. Red ($\eta >2/L$) leaps out and climbs the walls — divergence. Speed lives only in the interval $(0,2/L)$.

---

Step 6 — The strong-convexity floor gives the linear rate for general $f$

WHAT. For a general $\mu$-strongly convex, $L$-smooth $f$ we now show the error shrinks by a fixed factor each step — using the floor wall from Step 2, not just a quadratic. Strong convexity gives a lower-bound twin of the Descent Lemma:

WHY this closes the loop. Combine it with the Descent Lemma drop from Step 4 (using $\eta =1/L$). Let $D_k=f(x_k)-f^{\star }$ be the value-gap. Step 4 gave $f(x_{k+1})\le f(x_k)-\frac{1}{2L}\Vert g{\Vert }^2$; subtract $f^{\star }$ and feed in the floor inequality $\Vert g{\Vert }^2\ge 2\mu D_k$:

$D_{k+1}\le D_k-\frac{1}{2L}\underset{\ge 2\mu D_k}{\underbrace{\Vert g{\Vert }^2}}\le D_k-\frac{\mu }{L}{D}_k=(1-\frac{\mu }{L})D_k=(1-\frac{1}{\kappa })D_k.$

So the gap contracts by the fixed factor $(1-\frac{1}{\kappa })<1$ every step — that is linear (geometric) convergence, and the floor $\mu$ is exactly what makes it possible.

PICTURE.

The blue curve is the true value-gap $D_k$; the yellow dashed line is the guaranteed envelope $(1-1/\kappa {)}^k{D}_0$. The gap is pinned under a shrinking geometric curve — the visual meaning of "linear rate". Below, the log-scale inset turns that curve into a straight line whose slope is the rate.

---

Step 7 — Balancing two directions: where ${\eta }^{\star }=\frac{2}{\mu +L}$ comes from

WHAT. Real problems have different curvatures in different directions. Take $f(x,y)=\frac{1}{2}(\mu x^2+L{y}^2)$ with $\mu \ll L$. The eigenvalues of the curvature are exactly $\mu$ (gentle) and $L$ (steep). One step size $\eta$ must serve both multipliers:

WHY the optimum is ${\eta }^{\star }=\frac{2}{\mu +L}$ — the balancing argument. As $\eta$ grows from $0$: the gentle factor $|1-\eta \mu |$ decreases (still positive), while the steep factor $|1-\eta L|$ first decreases to $0$ at $\eta =1/L$ then increases (turns negative inside the absolute value). One is falling, the other eventually rising — so the max is smallest exactly where the two curves cross. Set them equal:

$1-\eta \mu =\eta L-1⟹2=\eta (\mu +L)⟹\boxed{{\eta }^{\star }=\frac{2}{\mu +L}}.$

Plug back into either factor:

${\rho }^{\star }=1-{\eta }^{\star }\mu =1-\frac{2\mu }{\mu +L}=\frac{L-\mu }{L+\mu }=\frac{\kappa -1}{\kappa +1}.$

PICTURE.

Top: the two factors $|1-\eta \mu |$ (green, falling) and $|1-\eta L|$ (red, V-shaped) plotted against $\eta$; their crossing point is the yellow star at ${\eta }^{\star }=\frac{2}{\mu +L}$, the lowest achievable max. Bottom: the resulting path on the stretched valley zig-zags across the narrow $y$-direction while creeping along the long $x$-floor — the visual meaning of a large $\kappa$.

---

Step 8 — The degenerate walls: $\kappa =1$ and $\mu =0$

WHAT. The two extreme condition numbers explain the whole spectrum.

• $\kappa =1$ ($\mu =L$): round bowl. With ${\eta }^{\star }=\frac{2}{\mu +L}=1/L$ the multiplier is $0$ everywhere — GD finishes in one step. Best case.
• $\mu =0$ (only convex, flat bottom): the floor wall vanishes. The rate $1-\frac{1}{\kappa }\to 1$ and ${\rho }^{\star }=\frac{L-0}{L+0}=1$ — no fixed shrink factor; we fall back to the slow $O(1/k)$ rate. This is why the parent warns "convexity alone does not give linear convergence." Think $f(x)=x^4$: its bottom is spoon-flat, the slope dies faster than any straight-line shrink.

WHY show both. They are the two endpoints: round bowls are trivial, flat-bottomed valleys are stubborn, everything else lives between with rate $\frac{\kappa -1}{\kappa +1}$.

PICTURE.

Left: round bowl, one yellow arrow straight to the centre ($\kappa =1$). Right: the flat-bottomed $x^4$ curve — steps (red) get tinier and tinier as the slope flattens, never contracting by a fixed factor ($\mu =0$).

---

The one-picture summary

Everything on one canvas: the true hill trapped between the $L$-ceiling and $\mu$-floor (Steps 2–3), the drop-vs-$\eta$ curve peaking at $1/L$ and dying at $2/L$ (Steps 4–5), the strong-convexity contraction $D_{k+1}\le (1-1/\kappa )D_k$ (Step 6), and the anisotropic zig-zag whose speed is set by $\kappa$ (Step 7). Read left to right: bound the hill → pick the safe step → the floor gives the rate → the condition number caps the speed.

Recall Feynman retelling — the whole walk in plain words

You're on a foggy hill. At your feet you can feel one arrow: the way up. Flip it — that's the way down — and that's where you step (Step 1). But how big a step is safe? You don't know the hill, so you agree on two rules: it never bends up faster than a ceiling $L$, and (if you're lucky) it always bends up at least a little, $\mu$ (Step 2). The ceiling lets you draw a bowl-shaped lid that sits on top of the real hill and touches under your feet; sliding to the bottom of that lid is guaranteed to lower the real hill too (Step 3). How far to slide? Step size $1/L$ drops you the most; past $2/L$ you fly across the valley and climb higher — you explode (Steps 4–5). The floor $\mu$ is what promises real speed: it guarantees the slope is always steep enough that each step shaves off a fixed fraction $1/\kappa$ of the remaining gap (Step 6). In two dimensions one step size must please a steep direction and a gentle one at once; the best you can do is make their two shrink-factors equal, which lands you at $\eta =2/(\mu +L)$ and a zig-zag whose speed is $\frac{\kappa -1}{\kappa +1}$ (Step 7). The two extremes: a round bowl finishes in one step, a spoon-flat bottom ($\mu =0$) makes you crawl forever (Step 8). That's the whole theory — bound the hill, pick the safe step, let the floor set the rate, and blame the condition number for any slowness.

Recall Quick self-check

Best step size for a strongly convex quadratic? ::: ${\eta }^{\star }=\frac{2}{\mu +L}$ Best per-step shrink factor with that ${\eta }^{\star }$? ::: ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}$ Per-step value-gap contraction with $\eta =1/L$? ::: $D_{k+1}\le (1-\frac{1}{\kappa })D_k$ Step size that finishes a round bowl ($\kappa =1$) in one step? ::: $\eta =1/L$ (multiplier $1-\eta L=0$) Range of $\eta$ where GD is guaranteed to make progress? ::: $0<\eta <2/L$ Why does a flat-bottomed convex function ($\mu =0$) lose linear convergence? ::: ${\rho }^{\star }=\frac{L-0}{L+0}=1$; no fixed shrink factor, only $O(1/k)$.

---

See also: Nesterov Acceleration and momentum turn $\kappa$ into $\sqrt{\kappa }$ (fixing the zig-zag of Step 7); Newton's Method (second-order methods) rescales each direction so $\kappa$ effectively becomes $1$; Stochastic Approximation (Robbins–Monro) explains why noisy gradients force a shrinking step.