Gradient descent and variants — convergence analysis

WHAT is gradient descent?

WHY this direction? Among all unit directions $u$ , the directional derivative is $\nabla f(x)^\top u$ , which by Cauchy–Schwarz is minimized when $u = -\nabla f(x)/\|\nabla f(x)\|$ . So $-\nabla f$ is the direction of steepest descent.

The two key assumptions (WHY we need them)

To prove anything, we need to control how "wild" $f$ can be.

The ratio $\kappa = L/\mu \ge 1$ is the condition number — it controls everything.

The Descent Lemma (the engine of ALL proofs)

Formula Descent Lemma — derived from scratch

Claim: If $f$ is $L$ -smooth then $f(y) \le f(x) + \nabla f(x)^\top(y-x) + \tfrac{L}{2}\|y-x\|^2.$

Derivation. By the fundamental theorem of calculus along the segment $x\to y$ : $f(y) - f(x) = \int_0^1 \nabla f(x + t(y-x))^\top (y-x)\,dt.$ Subtract the "first-order" term $\nabla f(x)^\top(y-x)=\int_0^1 \nabla f(x)^\top(y-x)\,dt$ : $f(y)-f(x)-\nabla f(x)^\top(y-x)=\int_0^1\big[\nabla f(x+t(y-x))-\nabla f(x)\big]^\top(y-x)\,dt.$ Bound by Cauchy–Schwarz then Lipschitz ( $\|\nabla f(x+t\Delta)-\nabla f(x)\|\le L\, t\|\Delta\|$ ): $\le \int_0^1 L\,t\,\|y-x\|^2\,dt = \tfrac{L}{2}\|y-x\|^2. \qquad\blacksquare$

WHAT it means: $f$ is sandwiched above by a parabola. We minimize that parabola each step.

Convergence for smooth (convex) functions

Formula One-step decrease ⟹

$O(1/k)$ rate Plug $y=x_{k+1}=x_k-\eta\nabla f(x_k)$ into the descent lemma: $f(x_{k+1}) \le f(x_k) - \eta\|\nabla f(x_k)\|^2 + \tfrac{L\eta^2}{2}\|\nabla f(x_k)\|^2 = f(x_k) - \eta\Big(1-\tfrac{L\eta}{2}\Big)\|\nabla f(x_k)\|^2.$ Why choose $\eta = 1/L$ ? It maximizes the guaranteed drop, giving $f(x_{k+1}) \le f(x_k) - \tfrac{1}{2L}\|\nabla f(x_k)\|^2.$ Summing and using convexity gives the classic $f(x_k) - f^\star \le \frac{L\|x_0-x^\star\|^2}{2k} = O\!\left(\tfrac1k\right).$

So with $\eta=1/L$ the loss always decreases (never diverges) — that's why $1/L$ is the magic step size.

Convergence for strongly convex + smooth: linear rate

Formula Geometric (linear) convergence — derivation

For a quadratic $f(x)=\tfrac12 x^\top A x$ with eigenvalues in $[\mu,L]$ , GD is $x_{k+1}=(I-\eta A)x_k$ . Along eigendirection $i$ : $x_{k+1}^{(i)} = (1-\eta\lambda_i)\,x_k^{(i)}.$ Contraction factor $|1-\eta\lambda_i|<1$ requires $0<\eta<2/L$ . The worst eigendirection sets the rate: $\rho(\eta)=\max\big(|1-\eta\mu|,\ |1-\eta L|\big).$ Minimize over $\eta$ : the two terms equal when $\eta^\star = \dfrac{2}{\mu+L}$ , giving $\rho^\star = \frac{L-\mu}{L+\mu} = \frac{\kappa-1}{\kappa+1}.$ Hence $\|x_k-x^\star\| \le \rho^{\star k}\|x_0-x^\star\|$ — linear convergence, and slow when $\kappa$ is large.

Figure — Gradient descent and variants — convergence analysis

Variants and their rates (the 80/20 table)

Method	Step / idea	Rate (strongly convex)
GD	full gradient, $\eta=2/(\mu+L)$	$\left(\frac{\kappa-1}{\kappa+1}\right)^k$
Heavy-ball / Momentum	add $\beta(x_k-x_{k-1})$	$\left(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\right)^k$
Nesterov accelerated GD	lookahead gradient	$O\!\left(\big(1-\tfrac1{\sqrt\kappa}\big)^k\right)$ ; $O(1/k^2)$ convex
SGD	stochastic gradient (one sample)	$O(1/k)$ , needs $\eta_k\to0$

SGD — why noise forces a shrinking step

Worked examples

Common mistakes

Recall Feynman: explain to a 12-year-old

Imagine rolling a ball down a hill in thick fog. You can only feel the slope under your feet, so you step the steepest way down and repeat. If your steps are too big you'll fly across the valley and bounce up the other side (diverge). If they're "just right" you slide smoothly to the bottom. A long thin valley is annoying — you zig-zag — unless you keep a bit of momentum like a real rolling ball, which smooths the path. Bumpy fog (noisy slope readings = SGD) means you must take smaller and smaller steps near the bottom or you'll keep jittering around it.

Flashcards

What is the gradient descent update rule?

x_{k+1}=x_k-\eta\nabla f(x_k)

Why is

-\nabla f

the steepest descent direction?

By Cauchy–Schwarz,

\nabla f^\top u

is minimized over unit

u

u=-\nabla f/\|\nabla f\|

Define

L

-smoothness.

\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|

, i.e.

\nabla^2 f\preceq LI

Define

\mu

-strong convexity.

\nabla^2 f\succeq \mu I

with

\mu>0

State the descent lemma.

f(y)\le f(x)+\nabla f(x)^\top(y-x)+\tfrac{L}{2}\|y-x\|^2

With

\eta=1/L

, what guaranteed per-step decrease holds?

f(x_{k+1})\le f(x_k)-\tfrac1{2L}\|\nabla f(x_k)\|^2

GD convergence rate for smooth convex

f

f(x_k)-f^\star\le \tfrac{L\|x_0-x^\star\|^2}{2k}=O(1/k)

Optimal step size for strongly convex quadratics?

\eta^\star=2/(\mu+L)

Best contraction factor of GD (strongly convex)?

\rho^\star=\frac{\kappa-1}{\kappa+1}=\frac{L-\mu}{L+\mu}

Range of

\eta

for GD to converge on quadratics?

0<\eta<2/L

How does momentum improve the rate?

Replaces

\kappa

\sqrt\kappa

: factor

\frac{\sqrt\kappa-1}{\sqrt\kappa+1}

Nesterov's rate for smooth convex (non-strong)

f

O(1/k^2)

Why must SGD use a decaying step size?

Constant

\eta

leaves residual noise

\propto\eta\sigma^2

; need

\sum\eta_k=\infty,\ \sum\eta_k^2<\infty

What is the condition number

\kappa

\kappa=L/\mu\ge1

; large

\kappa

⇒ slow GD.

Connections

Convex Functions and Optimization
Lipschitz Continuity
Eigenvalues and the Condition Number
Taylor's Theorem and the Fundamental Theorem of Calculus
Stochastic Approximation (Robbins–Monro)
Nesterov Acceleration
Newton's Method (second-order methods)

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek foggy pahaadi par tum khade ho aur sabse neeche jaana hai. Door tak dikh nahi raha, par paer ke neeche slope feel kar sakte ho — wahi $-\nabla f$ direction hai, sabse steep downhill. Gradient descent bas yahi karta hai: har step me steepest downhill jao, dobara slope naapo, repeat. Pura convergence theory sirf ek sawaal ka jawaab hai — step kitna bada lein aur neeche pahunchne me kitna time lagega?

Do cheezein crucial hain. $L$ -smoothness matlab gradient zyada tezi se nahi badalta (curvature upar se bounded), isi se "descent lemma" milta hai jo function ko ek parabola ke neeche sandwich kar deta hai. Agar $\eta=1/L$ lo to har step me loss guaranteed kam hoga — kabhi diverge nahi karega. Doosra, $\mu$ -strong convexity matlab function neeche se bhi parabola jaisa curve karta hai; tabhi linear (geometric) speed milti hai, factor $\frac{\kappa-1}{\kappa+1}$ ke saath, jahaan $\kappa=L/\mu$ condition number hai.

Sabse bada practical point: agar $\kappa$ bada hai (lambi patli valley), GD zig-zag karta hai aur bahut slow chalta hai — diagram me red path dekho. Yahin momentum kaam aata hai: woh back-and-forth ko average kar deta hai aur $\kappa$ ko $\sqrt\kappa$ bana deta hai — yaani kaafi tez. Aur agar learning rate $2/L$ se bada le liya, to GD bahar ki taraf bounce karke diverge ho jaata hai — isliye "bigger = faster" galat hai.

SGD me gradient noisy hota hai (ek sample se estimate). Constant step lo to bottom ke paas jitter karta rahega kyunki noise kabhi khatam nahi hota. Isliye step size ko dheere-dheere ghatana padta hai ( $\eta_k\to0$ , jaise $1/k$ ), tabhi exact minimum tak pahunchta hai. Yeh sab ML training me directly use hota hai — isiliye yeh chapter elite-level zaroori hai.

Gradient descent and variants — convergence analysis

WHAT is gradient descent?

The two key assumptions (WHY we need them)

The Descent Lemma (the engine of ALL proofs)

Convergence for smooth (convex) functions

Convergence for strongly convex + smooth: linear rate

Variants and their rates (the 80/20 table)

SGD — why noise forces a shrinking step

Worked examples

Common mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced Topics (Elite Level)

Connections