Foundations — Gradient descent and variants — convergence analysis

This page is the toolbox. The parent note fires off a barrage of symbols at speed. Here we earn every single one from zero — plain words, then a picture, then why the topic can't live without it. Nothing is used before it is built. Read top to bottom; each item leans only on the ones above it.

---

0. The scene: a function and its landscape

Before any symbol, fix the mental picture.

The picture (figure s01): for $n=2$, imagine a hilly landscape. The floor is the $(x,y)$ plane; the height above each floor-point is $f$. Our goal is to find the floor-point sitting under the lowest part of the surface.

Why the topic needs it: every later symbol describes this landscape — its slope, its curvature, its lowest point. If you don't see the landscape, the algebra is noise.

Why needed: every convergence bound is measured as a distance from $x^{\star }$ or a height gap above $f^{\star }$. They are the finish line.

---

1. Vectors and their length $\Vert \cdot \Vert$

A location $x\in {\mathbb{R}}^n$ is a vector: an arrow from the origin to that floor-point.

The picture: in 2D, $\Vert (3,4)\Vert =\sqrt{9+16}=5$ — the hypotenuse of a 3-by-4 right triangle.

Why needed: convergence means "the gap shrinks". To say something shrinks we must measure it — and $\Vert x_k-x^{\star }\Vert$ (distance from current point to the goal) is exactly that measuring stick.

---

2. The dot product $u^{\top }v$

The picture (figure s02): $u^{\top }v=\Vert u\Vert \Vert v\Vert \cos \theta$, where $\theta$ is the angle between the arrows. So it measures how much two arrows point the same way: maximal when aligned, zero when perpendicular, negative when opposed.

Why the topic needs it: the slope-in-a-direction is a dot product ($\nabla f^{\top }u$, next section), and the whole "steepest descent" argument is "which direction $u$ makes this dot product most negative?"

Why needed: this is the one line that proves $-\nabla f$ is the steepest direction, and it also appears bounding the descent-lemma integral (Section 9). It caps how big a dot product can be.

---

3. The gradient $\nabla f$

Here is the star of the show.

The picture (figure s03): at any floor-point, $\nabla f$ is an arrow lying in the floor plane pointing in the direction of steepest uphill, and its length is how steep that climb is. So $-\nabla f$ points steepest downhill — the direction we step.

Why needed: the entire update rule $x_{k+1}=x_k-\eta \nabla f(x_k)$ is built from this arrow. No gradient, no descent.

---

4. The step size $\eta$ and the iteration index $k$

Why needed: "how big a step ($\eta$) and how fast ($k$)" is the topic's central question. Both symbols live in every bound.

---

5. Curvature: the Hessian ${\nabla }^{2}f$, positive semidefiniteness, and the ordering $⪯$

Slope tells you which way is down; curvature tells you how the slope itself changes — and curvature is what decides how hard the problem is.

The picture (figure s04): trap the true curved surface between two parabolas — a flatter one of curvature $\mu$ below and a steeper one of curvature $L$ above.

Why needed: these two sandwiching bounds ($\mu$ below, $L$ above) are the only facts the convergence proofs use. Everything — safe step size, speed — is squeezed out of this sandwich. See Convex Functions and Optimization for the convexity ($\mu \ge 0$) that guarantees a single valley.

---

6. The two named constants: $L$ and $\mu$

Why needed: $L$ sets the safe step size (derived in Section 7). Because curvature $\le L$, a step of $\eta \approx 1/L$ is guaranteed not to overshoot.

Why needed: $\mu$ gives the valley a definite pull toward the bottom, which is what upgrades convergence from slow $O(1/k)$ to fast geometric ${\rho }^k$ (Section 8).

---

7. Why steps bigger than $2/L$ blow up

We can now derive the danger line the parent note keeps citing, using only $L$ and the picture of a bowl.

Why needed: this is the precise reason $L$ (not $\mu$) controls the safe step size, and it is the seed of the full convergence rates in the parent note.

---

8. The condition number $\kappa$, eigenvalues, and rate $\rho$

The picture: round bowl → straight shot to the bottom. Long ravine → zig-zag across the narrow direction while barely moving down the long axis.

Why needed: $\kappa$ is the single number that says whether GD flies or crawls, and $\rho$ is the literal speed. The headline "momentum turns $\kappa$ into $\sqrt{\kappa }$" lives here — see Nesterov Acceleration.

---

9. The Descent Lemma, and two borrowed tools

---

How it all feeds the topic

---

Equipment checklist

Cover the right side and recall each before moving on.