Question bank — Gradient descent and variants — convergence analysis

True. Full-batch gradients exact hote hain isliye ek fixed $\eta \le 2/L$ har step ko contract karta hai; SGD gradient noise $x^{\star }$ ke paas kabhi vanish nahi hota, isliye ek constant $\eta$ ek residual bounce of radius $\sim \sqrt{\eta }\sigma$ chhodta hai.

False. Plain convexity ($\mu =0$) sirf $O(1/k)$ deta hai. Linear ${\rho }^k$ rate aur contraction factor $\rho <1$ paane ke liye strong convexity $\mu >0$ chahiye.

True. Descent lemma se drop $\eta (1-L\eta /2)\Vert \nabla f{\Vert }^2$ hai; $\eta =1/L$ par yeh $\frac{1}{2L}\Vert \nabla f{\Vert }^2\ge 0$ hai, isliye $f$ monotone non-increasing hai.

False. Speed sirf $(0,2/L)$ mein hoti hai; $\eta =2/L$ se aage factor $|1-\eta L|>1$ hota hai aur GD outward oscillate karke diverge karta hai. Guaranteed-drop term toh negative bhi ho jaata hai.

True. $\mu =L=a$ aur ${\eta }^{\star }=2/(\mu +L)=1/a$ ke saath, contraction factor $1-\eta a=0$ hai, isliye $x_1=x^{\star }$ exactly hai.

False. $\kappa$ $f$ ki property hai (uske Hessian ke eigenvalue spread ki), algorithm ki nahi. Momentum $\kappa$ ko untouched rakhta hai lekin rate ki dependence ko $\kappa$ se $\sqrt{\kappa }$ tak improve karta hai.

False. Isse sirf $L$-smoothness chahiye. Proof fundamental theorem of calculus plus Lipschitz bound use karta hai — convexity kabhi invoke nahi hoti. Convexity baad mein chahiye, per-step drop ko global rate mein convert karne ke liye.

True. $\sum {\eta }_k=\infty$ iterates ko arbitrarily far travel karne deta hai (kisi bhi minimizer tak pahunchne ke liye); $\sum {\eta }_k^2<\infty$ accumulated noise ko finite banata hai taaki jitter khatam ho jaaye. Koi ek chhoddo aur convergence fail ho jaati hai.

True. ${\nabla }^{2}f⪰\mu I$ with $\mu >0$ matlab hai ki $f$ har direction mein strictly upward curve karta hai, isliye bowl ka exactly ek bottom hai.

Galat: $3/L>2/L$ hai, isliye $|1-\eta L|=|1-3|=2>1$ aur worst eigendirection har step mein grow karta hai. GD diverge ho jaata hai, speed up nahi hota.

Galat: minimum $x=0$ par curvature $f^{\prime \prime }(0)=0$ hai, isliye $\mu =0$ (strongly convex nahi). GD sirf sublinearly converge karta hai, ${\rho }^k$ rate par nahi.

Galat: $1/L$ smooth convex $f$ ke liye optimal hai. Strongly convex ke liye, $\rho (\eta )=\max (|1-\eta \mu |,|1-\eta L|)$ minimize karne se ${\eta }^{\star }=2/(\mu +L)$ milta hai, jo do worst eigendirections ko balance karta hai.

Galat: steepest descent locally best unit direction hai, lekin globally shortest route generally $x^{\star }$ tak straight line hoti hai. Ek anisotropic valley mein GD zig-zag karta hai — locally optimal, globally wasteful.

Galat: $L$ ko sirf curvature ka ek valid upper bound hona chahiye (${\nabla }^{2}f⪯LI$). Koi bhi overestimate safe hai (sirf chhote steps deta hai); danger $L$ ko underestimate karne mein hai, jo $\eta >2/L$ allow karta hai aur divergence hoti hai.

Galat: stability largest eigenvalue $L=100$ se set hoti hai, jisse $\eta <2/100$ chahiye. $\eta =1$ par $y$-direction factor $|1-100|=99$ hai aur blow up karta hai.

Galat: $\sum 1/k=\infty$ ✓ lekin $\sum 1/k=\infty$ bhi hai (kyunki ${\eta }_k^2=1/k$ hai), isliye $\sum {\eta }_k^2$ diverge karta hai. Noise kill nahi hoti; ${\eta }_k=1/k$ use karo jahan $\sum 1/k^2<\infty$ hai.

Kyunki descent lemma $f$ ko parabola $f(x)+\nabla f^{\top }(y-x)+\frac{L}{2}\Vert y-x{\Vert }^2$ ke neeche sandwich karta hai. Us easy upper bound ko minimize karna guarantee karta hai ki $f$ kam se kam utna hi drop karega — hum $f$ ko directly minimize nahi kar sakte bina globally jaane.

$\kappa =L/\mu$ measure karta hai ki bowl kitna stretched hai (steepest se flattest curvature ka ratio). Bada $\kappa$ matlab ek lamba thin valley jahan steep direction ke liye safe step flat direction ke liye tiny hai, zig-zag force karta hai aur ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}\to 1$ hota hai.

Rate dono eigendirection factors ka max hai. Ek ko lower karna doosre ko raise karta hai, isliye minimax exactly wahan reach hota hai jahan dono equal hain — $1-\eta \mu =\eta L-1$ solve karne se ${\eta }^{\star }=2/(\mu +L)$ milta hai.

Momentum narrow valley mein oscillation ko average out karta hai aur uske floor ke saath speed accumulate karta hai, isliye effective slowdown eigenvalue spread ke square root ke saath scale karta hai. Formally accelerated contraction $\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1}$ hai.

Ek unit direction $u$ ke liye, rate of change $\nabla f^{\top }u$ hai, jo Cauchy–Schwarz se most negative tab hota hai jab $u$ gradient ke exactly opposite point kare, $u=-\nabla f/\Vert \nabla f\Vert$.

GD ka gradient exact hai, isliye ek constant contraction error ko zero tak shrink karta hai. SGD ka stochastic gradient $x^{\star }$ ke paas ek variance floor ${\sigma }^2$ rakhta hai; sirf ek shrinking ${\eta }_k$ us noise ko zero tak scale karta hai.

$f(y)-f(x)$ ko exactly fundamental theorem of calculus ke through express karne ke liye, taaki sirf Lipschitz bound ka inequality use ho ki gradient kitna drift kar sakta hai — yahi clean $\frac{L}{2}\Vert y-x{\Vert }^2$ term produce karta hai.

Factor $|1-2|=1$ hai: na contraction aur na divergence — iterate hamesha ke liye $\pm$ same magnitude ke beech oscillate karta rehta hai. Yeh stability ka exact knife-edge hai.

Contraction factor ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}\to 1$ jaata hai jab $\kappa \to \infty$, isliye koi linear rate exist nahi karta; tum $O(1/k)$ sublinear guarantee par fall back karte ho.

Saari curvatures equal hain ($\mu =L$): level sets perfect circles/spheres hain. ${\rho }^{\star }=\frac{1-1}{1+1}=0$, isliye ek optimal step $x^{\star }$ par land karta hai.

Yeh rukk jaata hai — $x_{k+1}=x_k$ — kyunki update (zero) gradient ko multiply karta hai. GD ke convergence guarantees convexity assume karte hain exactly saddles ko rule out karne ke liye; nonconvex $f$ par yeh ek par stall ho sakta hai.

Yeh $0$ tend karta hai: infinitesimal steps infinitesimal progress karte hain. Convergence phir bhi hold karti hai lekin infinitely many steps leta hai — yahi reason hai ki $\eta$ near $1/L$ (near $0$ nahi) sweet spot hai.

Dono same phenomenon hai: $|1-\eta L|>1$ worst-direction error ko geometrically grow karta hai, isliye $\Vert x_k-x^{\star }\Vert$ aur hence $f(x_k)-f^{\star }$ dono blow up karte hain. Guaranteed-drop term already negative ho chuka hai.

Tab $\eta =1/\hat{L}>1/L$ hai, possibly $2/L$ se bhi zyada, isliye "safe" step ab safe nahi raha aur GD diverge ho sakta hai. $L$ ko overestimate karna conservative hai; underestimate karna dangerous hai.