Gradient descent and variants — convergence analysis: Worked examples

4.10.20 · D3 · Maths › Advanced Topics (Elite Level) › Gradient descent and variants — convergence analysis

Shuru karne se pehle: teen words jo hum baar baar use karenge, ek picture ke saath.

The scenario matrix

Neeche har cell GD ka ek alag behaviour hai. Har cell exactly ek example se claim ki gayi hai.

Cell	Input class	Kya special hai	Example
A	$κ = 1$ , round bowl	EK step mein converge	Ex 1
B	$κ$ large, thin canyon	crawl karta hai, zig-zag	Ex 2
C	step $η > 2/ L$	diverge karta hai (bahar oscillate)	Ex 3
D	step exactly $η = 2/ L$	boundary: na barhta na ghatta	Ex 4
E	$μ = 0$ , flat bottom ( $x^{4}$ )	convex but sirf $O (1/ k)$ , sublinear	Ex 5
F	momentum on cell B	$κ$ ko $κ$ bana deta hai	Ex 6
G	noisy gradients (SGD)	constant $η$ ek residual ball chhod deta hai	Ex 7
H	real-world word problem	data se $η$ choose karo (logistic-style)	Ex 8
I	exam twist: negative eigenvalue	$f$ convex nahi — GD escape/diverge karta hai	Ex 9

Sign coverage note. One-step contraction factor hai $1 - η λ$ . Hum ise positive dekhenge ( $η λ < 1$ , cell B), zero ( $η λ = 1$ , cell A), negative par $> - 1$ (overshoot par converge, Ex 4 discussion), equal to $- 1$ (boundary, cell D), below $- 1$ (divergence, cell C), aur $λ < 0$ ke saath (non-convex, cell I). Har sign dikhaya gaya hai.

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

Worked example One-step convergence

Minimize karo $f (x) = \frac{1}{2} a x^{2}$ jahan $a = 4$ , $x_{0} = 3$ se shuru karo. Optimal step $η^{⋆} = \frac{2}{μ + L}$ use karo.

Forecast: andaza lagao kitne iterations mein $x^{⋆} = 0$ tak machine precision mein pahunchoge. (Zyaadatar log "kuch dozen" kehte hain.)

Step 1. $μ$ aur $L$ identify karo. Ye step kyun? Poora rate curvature pe depend karta hai, aur $f = \frac{1}{2} a x^{2}$ ke liye second derivative constant $a$ hai, isliye $μ = L = a = 4$ , hence $κ = 1$ .

Step 2. Optimal step $η^{⋆} = \frac{2}{μ + L} = \frac{2}{4 + 4} = \frac{1}{4}$ . Ye step kyun? Parent note ne prove kiya tha ki $η^{⋆} = 2/ (μ + L)$ worst contraction ko minimize karta hai; yahan ye $1/ a$ tak collapse ho jaata hai.

Step 3. Contraction factor $1 - η^{⋆} a = 1 - \frac{1}{4} \cdot 4 = 0$ . Ye step kyun? Update hai $x_{k + 1} = (1 - η a) x_{k}$ ; zero ka factor error ko ek hi baar mein khatam kar deta hai.

Step 4. $x_{1} = (1 - 0) \cdot ?$ — nahi: $x_{1} = 0 \cdot x_{0} = 0$ . Ek step mein done.

Verify: $x_{1} = (1 - η^{⋆} a) x_{0} = 0 \cdot 3 = 0 = x^{⋆}$ . Sanity check: ek round bowl mein negative gradient exactly minimum ki taraf point karta hai, aur $η = 1/ a$ ise scale karta hai wahan land karne ke liye. Sahi hai.

Yahan contraction factor exactly zero hai — positive-factor world (Ex 2) aur overshoot world (Ex 4) ke beech ki boundary.

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

Figure — Gradient descent and variants — convergence analysis

Worked example Anisotropic bowl mein GD ka crawl karna

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

Forecast: kaunsa coordinate fast converge karta hai aur kaunsa slow? Har step mein error kitna shrink hota hai?

Step 1. Eigenvalues padho. Ye step kyun? Hessian diagonal hai $diag (1, 100)$ , isliye do curvatures hain $μ = 1$ ( $x$ direction, gentle) aur $L = 100$ ( $y$ direction, steep). Thus $κ = 100$ .

Step 2. $η^{⋆} = \frac{2}{1 + 100} = \frac{2}{101}$ . Ye step kyun? Ye value dono directions ke contraction ko balance karti hai taki koi blow up na ho.

Step 3. Worst rate $ρ^{⋆} = \frac{κ - 1}{κ + 1} = \frac{99}{101} \approx 0.9802$ . Ye step kyun? Sabse slow eigendirection (yahan $x$ , gentle wala) govern karta hai; uska factor hai $∣1 - η^{⋆} μ ∣ = ∣1 - \frac{2}{101} ∣ = \frac{99}{101}$ .

Step 4. Per-step error sirf $1 - 0.9802 \approx 2%$ shrink hota hai. Error $10 \times$ cut karne ke liye chahiye $k$ jahan $0.980 2^{k} = 0.1$ , yaani $k = ln 0.1/ ln 0.9802 \approx 115$ . Ye step kyun? $ρ^{k} = 0.1$ solve karne se crawl length pata chalti hai.

Verify: $ρ^{⋆} = 99/101 = 0.980198 \dots$ aur $ln (0.1) / ln (99/101) = 115.0 \dots$ s01 dekho: red path steep $y$ direction ke across zig-zag karta hai jabki gentle $x$ direction mein inch karta hai — large $κ$ ka visual signature.

Ex 3 — Cell C: bahut bada step ⟹ divergence

Worked example

$2/ L$ se past overshoot karna $f (x) = \frac{1}{2} a x^{2}$ jahan $a = 2$ ( $L = 2$ ), $x_{0} = 1$ . $η = 1.5$ lo.

Forecast: $x_{k}$ shrink hoga, steady rahega, ya barhega?

Step 1. Threshold. Ye step kyun? Stability ke liye chahiye $∣1 - η L ∣ < 1$ , yaani $0 < η < 2/ L = 2/2 = 1$ . Hamara $η = 1.5$ is window ke bahar hai.

Step 2. Contraction factor $1 - η a = 1 - 1.5 \cdot 2 = - 2$ . Ye step kyun? Sign negative hai (overshoot) aur magnitude $∣ - 2∣ = 2 > 1$ hai, isliye har step sign flip aur grow karta hai.

Step 3. Iterate karo: $x_{1} = - 2$ , $x_{2} = 4$ , $x_{3} = - 8$ . Ye step kyun? $- 2$ se multiply karne par: magnitude double hoti hai, valley ke alternating sides pe.

Verify: $x_{3} = (- 2)^{3} x_{0} = - 8$ . s02 mein red iterates parabola ke alternating sides pe upar climb karte hain — divergence ki picture. Agla cell D se compare karo, razor's edge.

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

Worked example Perpetual oscillation, koi progress nahi

Same $f (x) = \frac{1}{2} a x^{2}$ , $a = 2$ , $x_{0} = 1$ , par ab $η = 2/ L = 1$ exactly.

Forecast: $x_{k}$ kis value pe settle hoga?

Step 1. Factor $1 - η a = 1 - 1 \cdot 2 = - 1$ . Ye step kyun? $η = 2/ L$ pe contraction magnitude exactly $1$ hai, shrink aur grow ke beech ki boundary.

Step 2. Iterate karo: $x_{1} = - 1$ , $x_{2} = 1$ , $x_{3} = - 1, \dots$ Ye step kyun? $- 1$ se multiply karne par sirf sign hamesha flip hota hai; magnitude $1$ pe frozen hai.

Step 3. Na convergence, na divergence — ek infinite oscillation. Ye step kyun? $∣ - 1∣ = 1$ na $< 1$ (converge) hai na $> 1$ (diverge); ye exactly woh edge case hai jo parent note ka " $0 < η < 2/ L$ " exclude karta hai.

Verify: $x_{100} = (- 1)^{100} \cdot 1 = 1$ , $x_{101} = - 1$ . Ye kabhi $0$ ki taraf move nahi karta. Isliye safe window open hai: $η$ strictly $2/ L$ se kam.

Sign ledger ab tak: Ex 1 factor $= 0$ , Ex 2 factor $\in (0, 1)$ , Ex 4 factor $= - 1$ , Ex 3 factor $< - 1$ . Bacha hua sign — factor $\in (- 1, 0)$ , overshoot par converge — kisi bhi $η \in (1/ L, 2/ L)$ ke liye hota hai; e.g. $η = 0.75$ yahan factor deta hai $1 - 0.75 \cdot 2 = - 0.5$ , sides alternate karte hue converge karta hai.

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

Worked example Convex par strongly convex NAHI

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

Forecast: error $ρ^{k}$ ki tarah geometrically girega, ya slower?

Step 1. Minimum pe curvature. Ye step kyun? $f^{''} (x) = 3 x^{2}$ , jo $x^{⋆} = 0$ pe $0$ hai. To $μ = 0$ : chahe kitni bhi chhoti parabola lo, bottom ke paas $f$ aur flat hai. Strong convexity fail ho jaati hai.

Step 2. Update $x_{k + 1} = x_{k} - η x_{k}^{3} = x_{k} - 0.1 x_{k}^{3}$ . Ye step kyun? $0$ ke paas, $x_{k}^{3}$ tiny hai, isliye step minuscule ho jaata hai — progress ruk jaata hai.

Step 3. $x_{0} = 1$ se: $x_{1} = 1 - 0.1 (1)^{3} = 0.9$ ; $x_{2} = 0.9 - 0.1 (0.9)^{3} = 0.8271$ . Ye step kyun? Slowing feel karne ke liye pehle steps compute karo.

Step 4. Asymptotic rate. Ye step kyun? $f = x^{4}$ ke liye error obey karta hai $x_{k} \sim c k^{- 1/2}$ — polynomial, not geometric. Ye wohi $O (1/ k)$ -flavoured (actually sublinear) behaviour hai jiske baare mein parent note ne $μ = 0$ ke liye warn kiya tha.

Verify: $x_{1} = 0.9$ aur $x_{2} = 0.9 - 0.1 \cdot 0. 9^{3} = 0.82710$ . s03 mein red trajectory flat bottom se chipak jaati hai, dawdling — strongly convex bowl ke crisp geometric drop se contrast karo.

Ex 6 — Cell F: momentum $κ$ ko $κ$ banaata hai

Worked example Thin canyon pe heavy-ball

Same $f (x, y) = \frac{1}{2} (x^{2} + 100 y^{2})$ jaise Ex 2 ( $κ = 100$ ). Momentum use karo tuned rate ke saath.

Forecast: momentum ka rate $\frac{κ - 1}{κ + 1}$ hai — plain GD se kitne kam iterations chahiye?

Step 1. GD rate (Ex 2 se): $ρ_{GD} = \frac{99}{101} \approx 0.9802$ . Ye step kyun? Compare karne ke liye baseline chahiye.

Step 2. Momentum rate $ρ_{mom} = \frac{κ - 1}{κ + 1} = \frac{10 - 1}{10 + 1} = \frac{9}{11} \approx 0.8182$ . Ye step kyun? $100 = 10$ ; parent note ka mnemonic "GD has $κ$ , momentum has $κ$ " literally ye substitution hai.

Step 3. Error $10 \times$ cut karne ke liye iterations: GD ko chahiye $ln 0.1/ ln 0.9802 \approx 115$ ; momentum ko chahiye $ln 0.1/ ln 0.8182 \approx 11.5$ . Ye step kyun? Dono ke liye $ρ^{k} = 0.1$ solve karo aur compare karo.

Step 4. Speed-up $\approx 115/11.5 \approx 10 \times$ . Ye step kyun? Dono iteration counts ka ratio.

Verify: $ρ_{mom} = 9/11 = 0.81818 \dots$ , aur $ln (0.1) / ln (9/11) = 11.49 \dots$ vs GD ke liye $115.0$ . Speed-up factor $\approx 10$ . Same landscape, order of magnitude kam steps — practically sabse bada fayda.

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

Worked example Constant step exact minimum tak kyun nahi pahunchta

Minimize karo $f (x) = \frac{1}{2} a x^{2}$ , $a = 2$ , par har observed gradient hai $g_{k} = a x_{k} + ε_{k}$ noise variance $E [ε_{k}^{2}] = σ^{2} = 1$ ke saath. Constant $η = 0.1$ use karo. Dekho Stochastic Approximation (Robbins–Monro).

Forecast: kya $x_{k} \to 0$ exactly jaayega, ya ek chhoti ball mein hamesha bounce karta rahega?

Step 1. Noiseless part contracts. Ye step kyun? $x_{k + 1} = (1 - η a) x_{k} - η ε_{k} = (1 - 0.2) x_{k} - 0.1 ε_{k}$ ; signal $0.8$ factor se shrink hota hai.

Step 2. Steady-state variance. Ye step kyun? Equilibrium pe $Var (x_{\infty}) = (0.8)^{2} Var (x_{\infty}) + (0.1)^{2} σ^{2}$ , isliye $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$ . Ye step kyun? $x_{k}$ kabhi is spread se neeche settle nahi karta — wohi "ball of radius $\sim η σ$ " jo parent note ne describe ki thi.

Verify: $Var (x_{\infty}) = 0.01/0.36 = 0.027 \overline{7}$ , radius $= 1/6 \approx 0.16667$ . Fix: $η_{k}$ decay karo (e.g. $η_{k} = 1/ k$ ) taaki injected term $η_{k}^{2} σ^{2} \to 0$ ; tab ball ek point tak shrink ho jaati hai.

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

Worked example Logistic-style loss ke liye learning rate set karna

Ek model ka smoothness constant hai $L = \frac{1}{4} λ_{m a x} (X^{⊤} X)$ . Maano $X^{⊤} X$ ka largest eigenvalue $λ_{m a x} = 40$ hai, aur smallest relevant curvature $μ = 0.5$ deti hai. Ek safe monotone step choose karo aur rate predict karo.

Forecast: kaunsa $η$ guarantee karta hai ki loss kabhi increase na ho, aur ye problem kitni ill-conditioned hai?

Step 1. $L$ compute karo. Ye step kyun? Logistic loss ka Hessian hai $\frac{1}{4} X^{⊤} D X$ jahan $D ⪯ I$ , isliye uski top curvature at most $\frac{1}{4} λ_{m a x} (X^{⊤} X) = \frac{1}{4} \cdot 40 = 10$ hai.

Step 2. Safe monotone step $η = 1/ L = 1/10 = 0.1$ . Ye step kyun? Parent note ne prove kiya tha ki $η = 1/ L$ guaranteed drop deta hai $f (x_{k + 1}) \leq f (x_{k}) - \frac{1}{2 L} ∥\nabla f ∥^{2}$ — koi line search nahi chahiye.

Step 3. Condition number $κ = L / μ = 10/0.5 = 20$ . Ye step kyun? Ye linear rate set karta hai.

Step 4. Optimal-step rate $ρ^{⋆} = \frac{κ - 1}{κ + 1} = \frac{19}{21} \approx 0.9048$ . Ye step kyun? Tuned step $2/ (μ + L)$ ke saath ye milta hai; safe $η = 1/ L$ thoda slower hai par hamesha safe hai.

Verify: $L = 10$ , $κ = 20$ , $ρ^{⋆} = 19/21 = 0.90476 \dots$ . Units check: $η$ ki units hain (input)²/(loss), $1/ L$ se match karta hai kyunki $L$ ek curvature hai (loss per input²). Consistent.

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

Worked example Saddle-flavoured direction jahan GD bhaag jaata hai

Maano $f (x) = - \frac{1}{2} b x^{2}$ jahan $b = 3$ (ek downward parabola, curvature $- 3$ ). $x_{0} = 0.01$ se shuru karo, koi bhi positive $η = 0.1$ .

Forecast: kya GD ek minimum dhundh paayega? (Trick — koi minimum hai hi nahi.)

Step 1. Curvature ka sign. Ye step kyun? $f^{''} = - 3 < 0$ , isliye $λ = - 3$ : ye direction concave hai. Koi $μ > 0$ exist nahi karta; har convergence theorem ki assumptions violate hain.

Step 2. Update factor $1 - η λ = 1 - 0.1 \cdot (- 3) = 1.3$ . Ye step kyun? Ek negative eigenvalue ke saath factor har positive $η$ ke liye $1$ se bada hota hai — koi safe step nahi hai.

Step 3. Iterate karo: $x_{1} = 1.3 \cdot 0.01 = 0.013$ , aur $x_{k} = 1. 3^{k} \cdot 0.01 \to \infty$ . Ye step kyun? GD $+ \infty$ ki taraf climb karta hai kyunki $- \nabla f$ (nonexistent) minimum se door point karta hai.

Verify: $x_{5} = 1. 3^{5} \cdot 0.01 = 0.0371293$ , grow ho raha hai. Lesson: GD ki guarantees utni hi achi hain jitni convexity; ek bhi negative eigenvalue (saddle/max) unhe tod deta hai. Ye poori theory ki boundary hai — aur isliye Newton's Method (second-order methods) (jo curvature use karta hai) saddles ke paas invoke kiya jaata hai.

The completed matrix

Har cell A–I ka ab ek worked, verified example hai. Contraction factor $1 - η λ$ value $0$ (Ex 1) ke saath, $(0, 1)$ mein (Ex 2), $= - 1$ (Ex 4), $< - 1$ (Ex 3), $> 1$ $λ > 0$ ke saath (Ex 3), aur $> 1$ $λ < 0$ ke saath (Ex 9) appear hua hai; degenerate $μ = 0$ case (Ex 5), noisy case (Ex 7), aur data-driven step (Ex 8) har scenario ko round out karte hain.

Recall Quick self-test

Kaun sa cell ek step mein converge karta hai, aur kyun? ::: Cell A ( $κ = 1$ ): factor $1 - η a = 0$ jab $η = 1/ a$ . $κ = 100$ ke liye, GD ko error $10 \times$ cut karne mein kitne iterations lagte hain? ::: Lagbhag 115; momentum ko lagbhag 11.5 chahiye. Exact step size kya hai jis par GD hamesha ke liye oscillate karta hai bina progress ke? ::: $η = 2/ L$ (factor $= - 1$ ). Constant- $η$ SGD exact minimum tak kyun nahi pahunchta? ::: Noise har step mein variance $\propto η σ^{2}$ inject karta hai, ek residual ball chhod deta hai. Ex 9 mein saari convergence guarantees kya tod deta hai? ::: Ek negative eigenvalue ( $μ \leq 0$ ): koi safe $η$ nahi, GD diverge karta hai.