Example: \(f(\mathbf x)=\tfrac12(x_1^2+2x_2^2)\), \(\mathbf x^\star=0\). Move the slider to see an overshoot.

One gradient step

\(D_t=\|\mathbf x_t-\mathbf x^\star\|_2^2\), \(e_t=f(\mathbf x_t)-f^\star\).

\[\begin{aligned}D_{t+1}&=\|\mathbf x_t-\mathbf x^\star-\eta\mathbf g_t\|_2^2\\&=D_t-2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]

Use \(\|\mathbf a-\mathbf b\|^2=\|\mathbf a\|^2-2\mathbf a^\top\mathbf b+\|\mathbf b\|^2\),
with \(\mathbf a=\mathbf x_t-\mathbf x^\star\) and \(\mathbf b=\eta\mathbf g_t\).

First-order condition for convexity:

\[f(\mathbf x^\star)\ge f(\mathbf x_t)+\mathbf g_t^\top(\mathbf x^\star-\mathbf x_t).\]\[\begin{aligned}2\eta e_t&\le2\eta\mathbf g_t^\top(\mathbf x_t-\mathbf x^\star)\\&=D_t-D_{t+1}+\eta^2\|\mathbf g_t\|_2^2.\end{aligned}\]