Exercises — Gradient descent and variants — convergence analysis

WHAT we use: the parent note showed that plugging $x_{k+1}=x_k-\eta \nabla f(x_k)$ into the descent lemma gives a drop of $\eta \left(1-\frac{L\eta }{2}\right)\Vert \nabla f(x_k){\Vert }^2$. This is a downward parabola in $\eta$, maximised at $\eta =1/L$. WHY $1/L$ and not bigger: past $\eta =2/L$ the factor turns negative — the "guarantee" evaporates. The peak of the parabola sits exactly at $1/L$. So $\eta =1/L=1/8=0.125$. Showing the substitution explicitly: plug $\eta =1/L$ into the drop coefficient $\eta \left(1-\frac{L\eta }{2}\right)$: $\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}.$ The guaranteed decrease is therefore $\frac{1}{2L}\Vert \nabla f(x_k){\Vert }^2=\frac{1}{2\cdot 8}\cdot 3^2=\frac{9}{16}=\mathrm{0.5625.}$

WHAT the eigenvalues mean: for a quadratic, the Hessian's eigenvalues are the curvatures along each principal axis. The smallest is $\mu$, the largest is $L$. $\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.}$

WHAT the function is: a bowl stretched more steeply in $x_2$. Its gradient is $\nabla f=(4x_1,36x_2)$, so the Hessian is diagonal with ${\lambda }_1=4,{\lambda }_2=36$. WHY coordinates decouple: because the Hessian is diagonal, each axis evolves independently as $x_{k+1}^{(i)}=(1-\eta {\lambda }_i)x_k^{(i)}$. $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.}$ So $x_1=(0.6,-2.6)$. Notice: coordinate 1 shrank (factor $0.6$), but coordinate 2 overshot past zero (factor $|1-3.6|=2.6>1$) — a sign $\eta$ is too big along the steep axis. See figure below.

WHAT bounds $\eta$: we need $|1-\eta {\lambda }_i|<1$ for all $i$, i.e. $0<\eta <2/{\lambda }_i$. The tightest is the largest eigenvalue $L=36$. $\eta <\frac{2}{L}=\frac{2}{36}=\frac{1}{18}\approx \mathrm{0.0556.}$ That is why $\eta =0.1$ in 2.1 blew up along $x_2$: $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$, so ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}=\frac{8}{10}=\mathrm{0.8.}$

WHAT we use: $\Vert x_k-x^{\star }\Vert \le ({\rho }^{\star }{)}^k\Vert x_0-x^{\star }\Vert$ with ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}=\frac{99}{101}\approx 0.980198$. WHY a logarithm enters: we want $({\rho }^{\star }{)}^k\le 10^{-3}$. Taking $\ln$ (which turns exponents into multipliers) and dividing by the negative number $\ln {\rho }^{\star }$ (flipping the inequality): $k\ge \frac{\ln (10^{-3})}{\ln {\rho }^{\star }}=\frac{-6.9078}{-0.020000}\approx \mathrm{345.4.}$ Round up (we need the inequality to hold): $k=346$ iterations.

$\sqrt{\kappa }=10$, so ${\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$. This is the "$\sqrt{\kappa }$ gift" made numeric: near a $10\times$ fewer iterations at $\kappa =100$.

WHAT we start from: the descent lemma $f(y)\le f(x)+\nabla f(x{)}^{\top }(y-x)+\frac{L}{2}\Vert y-x{\Vert }^2$. WHAT we substitute: $y=x_{k+1}=x_k-\eta \nabla f(x_k)$, so $y-x=-\eta \nabla f(x_k)$ and $\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.$ WHY $\eta =1/L$ gives clean decrease: substitute $\eta =1/L$: $1-\frac{L\eta }{2}=1-\frac{1}{2}=\frac{1}{2},\eta \cdot \frac{1}{2}=\frac{1}{2L},$ so $f(x_{k+1})\le f(x_k)-\frac{1}{2L}\Vert \nabla f(x_k){\Vert }^2$. Since the subtracted term is $\ge 0$, the loss never increases. When does the guarantee vanish? The coefficient $\eta (1-L\eta /2)=0$ when $\eta =0$ (trivial) or $1-L\eta /2=0\Rightarrow \eta =2/L$. For $\eta >2/L$ the coefficient is negative — the lemma no longer promises any decrease (and GD diverges on the worst eigendirection).

WHY it zig-zags: $\mu =1,L=100,\kappa =100$. The narrow valley in $x_2$ has huge curvature; even the optimal step overshoots along $x_2$ each iteration, producing a back-and-forth path (see figure below). 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$.

WHAT we optimise: the drop $D(\eta )=\eta (1-\frac{L\eta }{2})g^2=g^2\left(\eta -\frac{L}{2}{\eta }^2\right)$. WHY differentiate: $D$ is a downward parabola in $\eta$; its maximum is where the derivative is zero (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$ confirms a maximum. So the best guaranteed single-step drop uses exactly $\eta =1/L$, giving $D(1/L)=g^2\cdot \frac{1}{2L}=\frac{g^2}{2L}$, matching the parent note.

Plug in: $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.}$ So the RMS residual is $\sqrt{0.0625}=0.25$ — SGD bounces in a ball of that radius, never settling. WHY nonzero: the numerator $\eta {\sigma }^2$ is proportional to $\eta$; it vanishes only as $\eta \to 0$. With any fixed $\eta >0$ the noise keeps injecting energy each step, balanced by the contraction — a nonzero equilibrium. The fix (Robbins–Monro): use a decaying schedule with ${\sum }_k{\eta }_k=\infty$ (still able to travel anywhere) and ${\sum }_k{\eta }_k^2<\infty$ (total injected noise finite), e.g. ${\eta }_k=1/(ak)$. See Stochastic Approximation (Robbins–Monro).

First, where is the minimum? For $f=\frac{1}{2}{x}^{\top }Ax$ the gradient is $\nabla f=Ax$, which is zero only at $x^{\star }=0$ (since $A$ is positive definite, it is invertible, so $Ax=0\Rightarrow x=0$). So $x^{\star }=0$ throughout. (a) GD: $\kappa =100$, ${\rho }^{\star }=\frac{99}{101}\approx 0.980198$. Need $({\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: the update is $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 }$ — it reaches the minimum $x^{\star }=0$ in exactly one step, regardless of $\kappa$. Why the gap (one sentence): Newton multiplies the gradient by $A^{-1}$, which rescales every eigendirection by its own curvature so all axes hit zero simultaneously, whereas GD uses a single scalar $\eta$ and is throttled by its worst-conditioned axis. See Newton's Method (second-order methods) and Eigenvalues and the Condition Number.

Recognition = plug into $\eta =1/L$, ${\eta }^{\star }=2/(\mu +L)$, ${\rho }^{\star }=\frac{\kappa -1}{\kappa +1}$. Application = check $\eta <2/L$ per eigendirection. Analysis = iteration counts via $k\ge \ln (\text{tol})/\ln \rho$ (round up!). Synthesis = the descent lemma → monotone drop. Mastery = derive the optima, and know SGD needs a decaying schedule while Newton kills $\kappa$ outright.