Visual walkthrough — Gradient descent and variants — convergence analysis

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

Hum seedhe steps mein build karte hain. Har step mein likha hai KYA karte hain, KYUN karte hain, aur KAISA DIKHTA HAI (ek picture). Pictures padhna — woh argument carry karti hain.

---

Step 1 — Woh ek symbol jis par sab kuch tika hai: the gradient arrow

KYA. Humare paas ek function $f$ hai jo ek point leta hai aur ek height (ek number) return karta hai. Ek landscape socho: floor par har jagah $(x,y)$ ki ek height $f(x,y)$ hai. Hum sabse neeche waali jagah dhundna chahte hain.

Gradient, jise $\nabla f(x)$ likhte hain, ek arrow hai jo floor par point $x$ par draw hota hai. Yeh us direction mein point karta hai jahan height sabse tezi se badhti hai, aur iska length batata hai kitni tezi se.

KYUN yahi arrow aur koi direction nahi? Kyunki "downhill-steepest" woh exact direction hai jo chalne ki per unit distance mein humari height sabse zyada kam karta hai. Tamam directions $u$ mein se jinka length 1 hai, height mein change ka amount $\nabla f(x{)}^{\top }u$ hai — dono arrows ka dot product.

PICTURE.

Red arrow (uphill) aur uska blue flip (downhill) dekho. Green dashed rings level sets hain — equal height wale spots, jaise map par contour lines. Notice karo ki arrow hamesha us ring par perpendicular hai jis par woh baitha hai: yeh "steepest" ka visual signature hai.

---

Step 2 — $f$ ki wildness ko bound karna: do curvature walls

KYA. Progress ka koi vaada karne ke liye, hum $f$ ko arbitrarily wild hone se rokna chahte hain. Hum uski curvature (slope khud kitni tezi se change hoti hai) ko do numbers ke beech pin karte hain: ek ceiling $L$ aur ek floor $\mu$.

KYUN do walls? Ceiling $L$ hume overshoot karne se rokta hai (agar hume nahi pata floor kitna sharply upar jhuk sakta hai, toh hum safe step nahi chun sakte). Floor $\mu$ valley ko bottom par infinitely flat hone se rokta hai (flat bottom matlab gradient khatam ho jaata hai aur hum forever crawl karte hain). Ek wall safety control karti hai, doosri speed.

PICTURE.

Dark blue curve hai $f$. Yellow parabola (curvature $L$) ise upar se hug karta hai; green parabola (curvature $\mu$) ise neeche se hug karta hai. $f$ sandwich mein phansa hai. Unka ratio

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

condition number hai — $\kappa =1$ matlab do walls ek saath hain (ek perfect bowl); bada $\kappa$ matlab ek lamba patla trough.

---

Step 3 — The Descent Lemma: hill ko ek parabola se replace karna jise hum minimize kar sakein

KYA. Hum ceiling wall ko ek usable inequality mein badal dete hain. Ek point $x$ se shuru karke aur kisi bhi doosre point $y$ ko dekhte hue:

KYUN yeh build karein? Kyunki hum true foggy hill $f$ ko minimize nahi kar sakte — lekin hum ek parabola ko exactly, ek hi shot mein minimize kar sakte hain. Agar hum is over-estimating parabola ko lower karte hain, toh humne $f$ ko bhi provably lower kiya. Yahi har proof ka engine hai.

Yeh kahan se aata hai — concrete do-line sketch. Maano $\Delta =y-x$. Fundamental theorem of calculus kehta hai ki total height change, $x$ se $y$ tak ke segment par slope ka running sum hai:

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

Dono sides se flat "linear guess" $\nabla f(x{)}^{\top }\Delta$ subtract karo aur ceiling wall use karo (gradient at most $Lt\Vert \Delta \Vert$ drift kar sakta hai distance $t\Vert \Delta \Vert$ par):

$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.$

Last integral ${\int }_0^{1}tdt=\frac{1}{2}$ exactly wahi hai jahan factor $\frac{L}{2}$ paida hota hai.

PICTURE.

Blue curve hai $f$; yellow parabola Descent-Lemma bound hai jo black dot $x$ par anchored hai. Woh $x$ par touch karte hain (bound wahan exact hai) aur parabola baaki jagah upar rehta hai. Iska sabse neecha point (yellow star) woh jagah hai jahan agla step land karta hai.

---

Step 4 — GD ka ek step: parabola hume kitna drop karne deta hai

KYA. Actual GD move $y=x_k-\eta \nabla f(x_k)$ ko Descent Lemma mein plug karo. Is step par gradient arrow ke liye $g=\nabla f(x_k)$ likho.

KYUN yeh magic step reveal karta hai. Net drop hai $\eta (1-\frac{L\eta }{2})\Vert g{\Vert }^2$. $\eta$ ki function mein yeh ek upside-down parabola hai: bahut chhota $\eta$ → tiny step; bahut bada $\eta$ → penalty gain kha jaati hai. Iska peak $\eta =1/L$ par hai, jo yeh clean guarantee deta hai

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

PICTURE.

Curve drop per step ko step size $\eta$ ke against plot karta hai. Yeh $\eta =0$ par zero hai, $\eta =1/L$ par peak karta hai (yellow star), aur $\eta =2/L$ par wapas zero cross karta hai (red dot) — jiske baad "drop" negative ho jaata hai, matlab bound kisi decrease ka vaada nahi karta. Yeh akeli picture isliye hai ki parent ka mnemonic kehta hai "two-over-L se neeche theek ho; one-over-L par, monotone descent."

---

Step 5 — Step size ka har quadrant: safe, best, aur exploding

KYA. Ab hum $\eta$ ke tamam regimes cover karte hain taaki koi reader koi unseen case na dekhe. Sabse clean test problem use karo, 1-D bowl $f(x)=\frac{1}{2}L{x}^2$, jahan update hai $x_{k+1}=(1-\eta L)x_k$. Number $r=1-\eta L$ woh multiplier hai jo har step par apply hota hai.

KYUN multiplier hi sab kuch hai. $k$ steps ke baad error hai $r^k{x}_0$. Toh:

• $0<r<1$ (yani $0<\eta <1/L$): shrinks, sab same sign — zero ki taraf gentle glide.
• $r=0$ (yani $\eta =1/L$): ek hi step mein exactly bottom par land karta hai.
• $-1<r<0$ (yani $1/L<\eta <2/L$): shrinks lekin har step mein sign flip karta hai — zig-zagging karte hue converge karta hai.
• $r=-1$ (yani $\eta =2/L$): hamesha bounce karta hai same height par, kabhi converge nahi karta.
• $r<-1$ (yani $\eta >2/L$): badhta hai aur flip karta hai — bahar explode karta hai.

PICTURE.

Ek hi bowl par char trajectories. Green ($\eta <1/L$) ek taraf se slide karta hai. Yellow ($\eta =1/L$) seedha minimum par girta hai. Blue ($1/L<\eta <2/L$) overshoot karta hai aur alternating sides par land karta hai, phir bhi home kar raha hai. Red ($\eta >2/L$) bahar koodta hai aur walls par chadhta hai — divergence. Speed sirf interval $(0,2/L)$ mein hai.

---

Step 6 — Strong-convexity floor general $f$ ke liye linear rate deta hai

KYA. Ek general $\mu$-strongly convex, $L$-smooth $f$ ke liye ab hum dikhate hain ki error har step mein ek fixed factor se shrink hoti hai — Step 2 ki floor wall use karke, sirf quadratic nahi. Strong convexity Descent Lemma ka ek lower-bound twin deta hai:

KYUN yeh loop close karta hai. Ise Step 4 ke Descent Lemma drop ke saath combine karo ($\eta =1/L$ use karke). $D_k=f(x_k)-f^{\star }$ value-gap ho. Step 4 ne diya $f(x_{k+1})\le f(x_k)-\frac{1}{2L}\Vert g{\Vert }^2$; $f^{\star }$ subtract karo aur floor inequality $\Vert g{\Vert }^2\ge 2\mu D_k$ feed karo:

$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.$

Toh gap fixed factor $(1-\frac{1}{\kappa })<1$ se har step mein contract karta hai — yeh linear (geometric) convergence hai, aur floor $\mu$ exactly wohi hai jo ise possible karta hai.

PICTURE.

Blue curve true value-gap $D_k$ hai; yellow dashed line guaranteed envelope $(1-1/\kappa {)}^k{D}_0$ hai. Gap ek shrinking geometric curve ke neeche pinned hai — "linear rate" ka visual meaning. Neeche, log-scale inset us curve ko ek straight line mein badal deta hai jiska slope hi rate hai.

---

Step 7 — Do directions balance karna: ${\eta }^{\star }=\frac{2}{\mu +L}$ kahan se aata hai

KYA. Real problems mein alag-alag directions mein alag-alag curvatures hoti hain. Lo $f(x,y)=\frac{1}{2}(\mu x^2+L{y}^2)$ jahan $\mu \ll L$. Curvature ke eigenvalues exactly $\mu$ (gentle) aur $L$ (steep) hain. Ek step size $\eta$ ko dono multipliers serve karne hain:

KYUN optimum ${\eta }^{\star }=\frac{2}{\mu +L}$ hai — balancing argument. Jaise $\eta$ $0$ se badhta hai: gentle factor $|1-\eta \mu |$ decrease karta hai (abhi positive hai), jabki steep factor $|1-\eta L|$ pehle $\eta =1/L$ par $0$ tak decrease karta hai phir increase karta hai (absolute value ke andar negative ho jaata hai). Ek gir raha hai, doosra eventually utha raha hai — toh max exactly wahan sabse chhota hai jahan do curves cross karte hain. Dono ko equal set karo:

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

Kisi bhi factor mein wapas plug karo:

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

PICTURE.

Upar: do factors $|1-\eta \mu |$ (green, falling) aur $|1-\eta L|$ (red, V-shaped) $\eta$ ke against plot kiye hue; unka crossing point yellow star hai ${\eta }^{\star }=\frac{2}{\mu +L}$ par, jo sabse chhota achievable max hai. Neeche: stretched valley par resulting path zig-zag karta hai narrow $y$-direction mein jabki lambe $x$-floor par creep karta hai — bade $\kappa$ ka visual meaning.

---

Step 8 — Degenerate walls: $\kappa =1$ aur $\mu =0$

KYA. Do extreme condition numbers poora spectrum explain karte hain.

• $\kappa =1$ ($\mu =L$): round bowl. ${\eta }^{\star }=\frac{2}{\mu +L}=1/L$ ke saath multiplier har jagah $0$ hai — GD ek hi step mein khatam ho jaata hai. Best case.
• $\mu =0$ (sirf convex, flat bottom): floor wall gayab ho jaata hai. Rate $1-\frac{1}{\kappa }\to 1$ aur ${\rho }^{\star }=\frac{L-0}{L+0}=1$ — koi fixed shrink factor nahi; hum slow $O(1/k)$ rate par wapas aa jaate hain. Isliye parent warn karta hai "convexity alone linear convergence nahi deta." Socho $f(x)=x^4$: iska bottom spoon-flat hai, slope kisi bhi straight-line shrink se tezi se mar jaata hai.

KYUN dono dikhana zaroori hai. Yeh do endpoints hain: round bowls trivial hain, flat-bottomed valleys stubborn hain, baaki sab rate $\frac{\kappa -1}{\kappa +1}$ ke saath beech mein hain.

PICTURE.

Left: round bowl, ek yellow arrow seedha centre mein ($\kappa =1$). Right: flat-bottomed $x^4$ curve — steps (red) chhote se chhote hote jaate hain jaise slope flat hoti hai, kabhi fixed factor se contract nahi karti ($\mu =0$).

---

Ek-picture summary

Sab kuch ek canvas par: true hill $L$-ceiling aur $\mu$-floor ke beech trapped (Steps 2–3), drop-vs-$\eta$ curve $1/L$ par peak karti aur $2/L$ par khatam hoti (Steps 4–5), strong-convexity contraction $D_{k+1}\le (1-1/\kappa )D_k$ (Step 6), aur anisotropic zig-zag jiska speed $\kappa$ set karta hai (Step 7). Left se right padho: hill ko bound karo → safe step chuno → floor rate deta hai → condition number speed cap karta hai.

Recall Feynman retelling — poori walk plain words mein

Tum ek foggy hill par ho. Apne paon ke paas tumhe ek arrow feel hota hai: upar ki taraf. Ise flip karo — woh neeche ki taraf hai — aur wahan step lo (Step 1). Lekin safe step kitna bada hai? Tum hill nahi jaante, toh do rules par agree karte ho: yeh kabhi bhi ceiling $L$ se tezi se upar nahi jhukta, aur (agar lucky ho) yeh hamesha thoda upar jhukta hai kam se kam $\mu$ se (Step 2). Ceiling tumhe ek bowl-shaped lid draw karne deta hai jo real hill ke upar baithti hai aur tumhare paon ke neeche touch karti hai; us lid ke bottom par slide karna real hill ko bhi provably lower karta hai (Step 3). Kitna slide karna hai? Step size $1/L$ tumhe sabse zyada drop karta hai; $2/L$ ke baad tum valley ke across fly karte ho aur upar chadhte ho — tum explode karte ho (Steps 4–5). Floor $\mu$ hi real speed ka vaada karta hai: yeh guarantee karta hai ki slope hamesha itna steep hai ki har step remaining gap ka ek fixed fraction $1/\kappa$ kaat deta hai (Step 6). Do dimensions mein ek step size ko ek steep direction aur ek gentle direction dono ko please karna hota hai; best jo tum kar sakte ho woh yeh hai ki unke do shrink-factors equal bana do, jo tumhe $\eta =2/(\mu +L)$ par aur ek zig-zag par le jaata hai jiska speed $\frac{\kappa -1}{\kappa +1}$ hai (Step 7). Do extremes: ek round bowl ek step mein khatam ho jaata hai, ek spoon-flat bottom ($\mu =0$) tumhe forever crawl karwata hai (Step 8). Yahi poori theory hai — hill ko bound karo, safe step chuno, floor ko rate set karne do, aur kisi bhi slowness ke liye condition number ko blame karo.

Recall Quick self-check

Strongly convex quadratic ke liye best step size? ::: ${\eta }^{\star }=\frac{2}{\mu +L}$ Us ${\eta }^{\star }$ ke saath best per-step shrink factor? ::: ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}$ $\eta =1/L$ ke saath per-step value-gap contraction? ::: $D_{k+1}\le (1-\frac{1}{\kappa })D_k$ Round bowl ($\kappa =1$) ko ek step mein finish karne wala step size? ::: $\eta =1/L$ (multiplier $1-\eta L=0$) $\eta$ ka woh range jahan GD progress karne ki guarantee hai? ::: $0<\eta <2/L$ Flat-bottomed convex function ($\mu =0$) linear convergence kyun kho deta hai? ::: ${\rho }^{\star }=\frac{L-0}{L+0}=1$; koi fixed shrink factor nahi, sirf $O(1/k)$.

---

Yeh bhi dekho: Nesterov Acceleration aur momentum $\kappa$ ko $\sqrt{\kappa }$ mein badal deta hai (Step 7 ka zig-zag fix karta hai); Newton's Method (second-order methods) har direction ko rescale karta hai taaki $\kappa$ effectively $1$ ban jaaye; Stochastic Approximation (Robbins–Monro) explain karta hai kyun noisy gradients ek shrinking step force karte hain.