Exercises — Gradient descent and variants — convergence analysis

HUM KYA USE KARTE HAIN: parent note ne dikhaya tha ki $x_{k+1}=x_k-\eta \nabla f(x_k)$ ko descent lemma mein plug karne par ek drop milta hai $\eta \left(1-\frac{L\eta }{2}\right)\Vert \nabla f(x_k){\Vert }^2$ ka. Yeh $\eta$ mein ek downward parabola hai, jo $\eta =1/L$ par maximise hoti hai. KYU $1/L$ aur bada kyun nahi: $\eta =2/L$ ke baad factor negative ho jaata hai — "guarantee" khatam ho jaati hai. Parabola ka peak bilkul $1/L$ par baithta hai. Toh $\eta =1/L=1/8=0.125$. Substitution explicitly dikhate hain: $\eta =1/L$ ko drop coefficient $\eta \left(1-\frac{L\eta }{2}\right)$ mein plug karo: $\frac{1}{L}\left(1-\frac{L}{2L}\right)=\frac{1}{L}\left(1-\frac{1}{2}\right)=\frac{1}{L}\cdot \frac{1}{2}=\frac{1}{2L}.$ Isliye guaranteed decrease hai $\frac{1}{2L}\Vert \nabla f(x_k){\Vert }^2=\frac{1}{2\cdot 8}\cdot 3^2=\frac{9}{16}=\mathrm{0.5625.}$

Eigenvalues ka matlab: ek quadratic ke liye, Hessian ke eigenvalues har principal axis ke saath curvatures hi hote hain. Sabse chhota $\mu$ hai, sabse bada $L$ hai. $\mu =2,L=50,\kappa =L/\mu =25.$ Optimal step size (parent note): ${\eta }^{\star }=\frac{2}{\mu +L}=\frac{2}{52}=\frac{1}{26}\approx \mathrm{0.03846.}$ Optimal rate: ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}=\frac{24}{26}=\frac{12}{13}\approx \mathrm{0.9231.}$

Function kya hai: ek bowl jo $x_2$ mein zyada steeply stretch hai. Iska gradient $\nabla f=(4x_1,36x_2)$ hai, toh Hessian diagonal hai jahan ${\lambda }_1=4,{\lambda }_2=36$ hai. KYU coordinates decouple hoti hain: kyunki Hessian diagonal hai, har axis independently evolve karti hai $x_{k+1}^{(i)}=(1-\eta {\lambda }_i)x_k^{(i)}$ ke roop mein. $x_1^{(1)}=(1-0.1\cdot 4)\cdot 1=0.6,x_1^{(2)}=(1-0.1\cdot 36)\cdot 1=1-3.6=-\mathrm{2.6.}$ Toh $x_1=(0.6,-2.6)$ hai. Dhyan do: coordinate 1 shrank (factor $0.6$), lekin coordinate 2 zero se aage nikal gaya (factor $|1-3.6|=2.6>1$) — yeh sign hai ki $\eta$ steep axis ke saath zyada bada hai. Neeche figure dekho.

KYA $\eta$ ko bound karta hai: hum chahte hain $|1-\eta {\lambda }_i|<1$ sab $i$ ke liye, yaani $0<\eta <2/{\lambda }_i$. Sabse tightest largest eigenvalue $L=36$ se hai. $\eta <\frac{2}{L}=\frac{2}{36}=\frac{1}{18}\approx \mathrm{0.0556.}$ Isliye 2.1 mein $\eta =0.1$ $x_2$ ke saath blow up kar gaya: $0.1>1/18$. Optimal step: ${\eta }^{\star }=\frac{2}{\mu +L}=\frac{2}{4+36}=\frac{2}{40}=\mathrm{0.05.}$ Optimal rate: $\kappa =36/4=9$, toh ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}=\frac{8}{10}=\mathrm{0.8.}$

HUM KYA USE KARTE HAIN: $\Vert x_k-x^{\star }\Vert \le ({\rho }^{\star }{)}^k\Vert x_0-x^{\star }\Vert$ jahan ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}=\frac{99}{101}\approx 0.980198$ hai. KYU logarithm aata hai: hum chahte hain $({\rho }^{\star }{)}^k\le 10^{-3}$. $\ln$ lete hain (jo exponents ko multipliers mein baadal deta hai) aur negative number $\ln {\rho }^{\star }$ se divide karte hain (inequality flip ho jaati hai): $k\ge \frac{\ln (10^{-3})}{\ln {\rho }^{\star }}=\frac{-6.9078}{-0.020000}\approx \mathrm{345.4.}$ Upar round karo (hum chahte hain inequality hold kare): $k=346$ iterations.

$\sqrt{\kappa }=10$, toh ${\rho }_m=\frac{9}{11}\approx 0.818182$. $k\ge \frac{\ln (10^{-3})}{\ln (9/11)}=\frac{-6.9078}{-0.200671}\approx 34.42\Rightarrow k=35.$ Speedup: $346/35\approx 9.89\times$. Yeh "$\sqrt{\kappa }$ gift" numeric roop mein hai: $\kappa =100$ par lagbhag $10\times$ kam iterations.

HUM KAHAN SE SHURU KARTE HAIN: descent lemma $f(y)\le f(x)+\nabla f(x{)}^{\top }(y-x)+\frac{L}{2}\Vert y-x{\Vert }^2$. HUM KYA SUBSTITUTE KARTE HAIN: $y=x_{k+1}=x_k-\eta \nabla f(x_k)$, toh $y-x=-\eta \nabla f(x_k)$ aur $\Vert y-x{\Vert }^2={\eta }^2\Vert \nabla f(x_k){\Vert }^2$: $f(x_{k+1})\le f(x_k)-\eta \Vert \nabla f(x_k){\Vert }^2+\frac{L{\eta }^2}{2}\Vert \nabla f(x_k){\Vert }^2=f(x_k)-\eta (1-\frac{L\eta }{2})\Vert \nabla f(x_k){\Vert }^2.$ KYU $\eta =1/L$ clean decrease deta hai: $\eta =1/L$ substitute karo: $1-\frac{L\eta }{2}=1-\frac{1}{2}=\frac{1}{2},\eta \cdot \frac{1}{2}=\frac{1}{2L},$ toh $f(x_{k+1})\le f(x_k)-\frac{1}{2L}\Vert \nabla f(x_k){\Vert }^2$. Kyunki subtracted term $\ge 0$ hai, loss kabhi nahi badhti. Guarantee kab vanish hoti hai? Coefficient $\eta (1-L\eta /2)=0$ jab $\eta =0$ (trivial) ya $1-L\eta /2=0\Rightarrow \eta =2/L$ ho. $\eta >2/L$ ke liye coefficient negative hai — lemma ab kisi decrease ka promise nahi karta (aur GD worst eigendirection par diverge karta hai).

KYU zig-zag karta hai: $\mu =1,L=100,\kappa =100$. $x_2$ mein narrow valley ki huge curvature hai; optimal step bhi har iteration $x_2$ ke saath overshoot karta hai, ek back-and-forth path produce karta hai (neeche figure dekho). GD: ${\rho }^{\star }=\frac{99}{101}\approx 0.980198$. $k\ge \frac{\ln (10^{-6})}{\ln {\rho }^{\star }}=\frac{-13.8155}{-0.020000}\approx 690.8\Rightarrow 691.$ Momentum: ${\rho }_m=\frac{9}{11}\approx 0.818182$. $k\ge \frac{\ln (10^{-6})}{\ln (9/11)}=\frac{-13.8155}{-0.200671}\approx 68.8\Rightarrow 69.$ Speedup $\approx 691/69\approx 10\times$.

HUM KYA OPTIMISE KARTE HAIN: drop $D(\eta )=\eta (1-\frac{L\eta }{2})g^2=g^2\left(\eta -\frac{L}{2}{\eta }^2\right)$. KYU differentiate karte hain: $D$ $\eta$ mein ek downward parabola hai; iska maximum wahan hai jahan derivative zero hai (Fermat's condition). $D^{\prime }(\eta )=g^2\left(1-L\eta \right)=0\Rightarrow \eta =\frac{1}{L}.$ Second derivative $D^{\prime \prime }(\eta )=-L{g}^2<0$ ek maximum confirm karta hai. Toh best guaranteed single-step drop exactly $\eta =1/L$ use karta hai, jo $D(1/L)=g^2\cdot \frac{1}{2L}=\frac{g^2}{2L}$ deta hai, jo parent note se match karta hai.

Plug in karo: $a=4$, $\eta =0.05$, ${\sigma }^2=9$: $\mathbb{E}[x_{\infty }^2]=\frac{0.05\cdot 9}{2\cdot 4-0.05\cdot 16}=\frac{0.45}{8-0.8}=\frac{0.45}{7.2}=\mathrm{0.0625.}$ Toh RMS residual $\sqrt{0.0625}=0.25$ hai — SGD us radius ki ek ball mein bounce karta rehta hai, kabhi settle nahi hota. KYU nonzero hai: numerator $\eta {\sigma }^2$ $\eta$ ke proportional hai; yeh sirf tab vanish hota hai jab $\eta \to 0$ ho. Kisi bhi fixed $\eta >0$ ke saath noise har step energy inject karta rehta hai, contraction se balance hoke — ek nonzero equilibrium. Fix (Robbins–Monro): ek decaying schedule use karo jisme ${\sum }_k{\eta }_k=\infty$ (kahin bhi travel karne mein capable) aur ${\sum }_k{\eta }_k^2<\infty$ (total injected noise finite) ho, jaise ${\eta }_k=1/(ak)$. Dekho Stochastic Approximation (Robbins–Monro).

Pehle, minimum kahan hai? $f=\frac{1}{2}{x}^{\top }Ax$ ke liye gradient $\nabla f=Ax$ hai, jo sirf $x^{\star }=0$ par zero hai (kyunki $A$ positive definite hai, toh invertible hai, toh $Ax=0\Rightarrow x=0$). Toh $x^{\star }=0$ poori jagah hai. (a) GD: $\kappa =100$, ${\rho }^{\star }=\frac{99}{101}\approx 0.980198$. Chahiye $({\rho }^{\star }{)}^k\le \frac{1}{2}$: $k\ge \frac{\ln (0.5)}{\ln {\rho }^{\star }}=\frac{-0.693147}{-0.020000}\approx 34.66\Rightarrow 35\text{ steps to halve.}$ (b) Newton: update hai $x_{k+1}=x_k-A^{-1}\nabla f(x_k)=x_k-A^{-1}A{x}_k=x_k-x_k=0=x^{\star }$ — yeh minimum $x^{\star }=0$ tak exactly ek step mein pahunch jaata hai, $\kappa$ se regardless. Gap kyun hai (ek sentence): Newton gradient ko $A^{-1}$ se multiply karta hai, jo har eigendirection ko uski apni curvature se rescale karta hai taaki sab axes ek saath zero hit karein, jabki GD ek single scalar $\eta$ use karta hai aur apni worst-conditioned axis se throttle hota hai. Dekho Newton's Method (second-order methods) aur Eigenvalues and the Condition Number.

Recognition = $\eta =1/L$, ${\eta }^{\star }=2/(\mu +L)$, ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}$ mein plug karo. Application = $\eta <2/L$ har eigendirection ke liye check karo. Analysis = iteration counts $k\ge \ln (\text{tol})/\ln \rho$ se (upar round karo!). Synthesis = descent lemma → monotone drop. Mastery = optima derive karo, aur jaano ki SGD ko ek decaying schedule chahiye jabki Newton $\kappa$ ko seedha khatam kar deta hai.