Derive: Going Downhill on Purpose

Because $A$ is symmetric, write $A=Q\Lambda Q^{\top }$ with $Q$ orthogonal and $\Lambda$ diagonal, and set $z=Q^{\top }\theta$. The quadratic becomes $$f=\frac{1}{2}{z}^{\top }\Lambda z=\frac{1}{2}\sum _i{\lambda }_i{z}_i^2,$$ and the gradient is $\Lambda z$. One step is therefore $$z_i\mapsto z_i-\eta {\lambda }_i{z}_i=(1-\eta {\lambda }_i)z_i,$$ coordinate by coordinate. After $t$ steps, $$f({\theta }_t)-f({\theta }^{\ast })=\frac{1}{2}\sum _i{\lambda }_i(1-\eta {\lambda }_i{)}^{2t}{z}_i(0{)}^2\le {\rho }^{2t}[f({\theta }_0)-f({\theta }^{\ast })],$$ where $\rho ={\max }_i|1-\eta {\lambda }_i|$. Each factor $|1-\eta \lambda |$ is largest at an endpoint of the interval $[m,L]$, so $\rho =\max (|1-\eta m|,|1-\eta L|)$.

For $0<\eta \le 1/L$ the term $1-\eta m$ is the larger one and falls as $\eta$ grows, so the best step in that range is $\eta =1/L$. Beyond $1/L$ the second term is $\eta L-1$, which grows with $\eta$, while the first term $1-\eta m$ still falls. The two are equal when $$1-\eta m=\eta L-1⟺{\eta }^{\ast }=\frac{2}{L+m}.$$ At that step, $$\rho =\frac{L-m}{L+m}.$$ For $L=10$ and $m=1$ the best step is ${\eta }^{\ast }=2/11\approx 0.1818$ and the factor is $$\rho =\frac{9}{11}=0.81818\dots ,$$ which rounds to $0.8182$. Compare the step $1/L=0.1$ used in section 17.4: there the factor is $1-m/L=0.9$, so balancing the two curvatures is faster. The derivation also shows why the text's factor $1-1/\kappa$ was not the end of the story: it is the best step among those at or below $1/L$, and the balanced step sits above $1/L$. To reach a gap smaller by a factor of $10^6$ the two factors need about $132$ steps and about $69$ steps respectively, so at this condition number the balanced step nearly halves the run.

The gradient at $(2,1)$ is $(2x,8y)=(4,8)$, so $$g\cdot d=4(1)+8(-1)=-4<0.$$ The arrow is a descent direction by the test of section 17.1. The Hessian is $H=\mathrm{diag}(2,8)$, so $d^{\top }Hd=2(1{)}^2+8(-1{)}^2=10$. Along the line, $$f((2,1)+\eta d)=f(2,1)+\eta (-4)+\frac{{\eta }^2}{2}(10)=8-4\eta +5{\eta }^2.$$ The step lowers the loss exactly when $$-4\eta +5{\eta }^2<0⟺\eta (5\eta -4)<0⟺0<\eta <\frac{4}{5}.$$ The largest step that still lowers the loss is therefore $\eta =4/5=0.8$. At that step the change is $-3.2+5(0.64)=0$, so the loss is still 8: the point is $(2.8,0.2)$, and $f=7.84+4(0.04)=8$. A larger step, $\eta =1$, lands at $(3,0)$ with loss 9, above the starting 8.

This is the counterexample the chapter's warning asks for. The first-order test said the arrow points downhill, and it does, but only for a short enough step: the second-order term is positive along every direction here, and it overtakes the first-order fall at $\eta =0.8$. The general condition for a quadratic is $\eta <-2g\cdot d/(d^{\top }Hd)$, which depends on the direction. It is not the constant-step window $2/L=0.25$: this arrow is shallower than the steepest one, so it tolerates a longer step before the curvature penalty wins.

Write $e_t={\theta }_t-{\theta }^{\ast }$. Because $\nabla f({\theta }_t)=m{e}_t$, the update becomes $$e_{t+1}=e_t-\eta (m{e}_t+{\xi }_t)=(1-\eta m)e_t-\eta {\xi }_t.$$ Take squared lengths: $$\Vert e_{t+1}{\Vert }^2=(1-\eta m{)}^2\Vert e_t{\Vert }^2-2\eta (1-\eta m)e_t\cdot {\xi }_t+{\eta }^2\Vert {\xi }_t{\Vert }^2.$$ The cross term has expectation zero: ${\xi }_t$ is independent of $e_t$ and has mean zero. Taking expectations, $$r_{t+1}=(1-\eta m{)}^2{r}_t+{\eta }^2{\sigma }^2.$$ This is a linear recursion. Its fixed point $r_{\infty }$ solves $r_{\infty }=(1-\eta m{)}^2{r}_{\infty }+{\eta }^2{\sigma }^2$, so $$r_{\infty }=\frac{{\eta }^2{\sigma }^2}{1-(1-\eta m{)}^2}=\frac{\eta {\sigma }^2}{m(2-\eta m)},$$ using $1-(1-\eta m{)}^2=\eta m(2-\eta m)$. The distance starts at $r_0$ and approaches $r_{\infty }$ geometrically; it does not reach zero unless ${\sigma }^2=0$.

For $m=2$, $\eta =0.1$ and ${\sigma }^2=8$, $$r_{\infty }=\frac{(0.1{)}^2(8)}{1-(0.8{)}^2}=\frac{0.08}{0.36}=\frac{2}{9}=0.2222\dots ,$$ which rounds to $0.222$. For a small step the denominator is close to $2\eta m$, so $r_{\infty }\approx \eta {\sigma }^2/(2m)=0.8/4=0.2$. Halving $\eta$ nearly halves the floor, because the noise injected per step falls with ${\eta }^2$ while the contraction per step falls only with $\eta$. That is why a schedule that shrinks ${\eta }_t$ can go lower than a constant step, and why section 17.6 requires $\sum {\eta }_t=\infty$: the floor vanishes as ${\eta }_t\to 0$, but the run must still be able to travel.