Gradient descent on a strongly convex quadratic

Take $A=I_d$ in [F1]. Then $\mathrm{\nabla }f(x)=x-b$ and $H_f(x)=I_d$. This Hessian is positive semidefinite, so [F2] proves convexity.

Direct expansion gives, for all $x,y$, $f(y)=f(x)+⟨x-b,y-x⟩+\frac{1}{2}\mathrm{\parallel }y-x{\mathrm{\parallel }}^2\mathrm{.}$ Thus the strong-convexity inequality holds with $\mu =1$. The gradient satisfies $\mathrm{\parallel }\mathrm{\nabla }f(x)-\mathrm{\nabla }f(y)\mathrm{\parallel }=\mathrm{\parallel }x-y\mathrm{\parallel }\le 2\mathrm{\parallel }x-y\mathrm{\parallel }$, so $L=2$ is valid. The minimum is $f^{\ast }=0$ at $x=b$.

Whenever the algorithm makes a fixed-step update with step $1\mathrm{/}2$, $x_{k+1}=x_k-\frac{1}{2}(x_k-b)=b+\frac{1}{2}(x_k-b)$. Induction along the generated iterates gives $\mathrm{\parallel }{x}_k-b{\mathrm{\parallel }}^2=4^{-k}\mathrm{\parallel }{x}_0-b{\mathrm{\parallel }}^2$, so $f(x_k)-f^{\ast }=4^{-k}(f(x_0)-f^{\ast })\le 2^{-k}(f(x_0)-f^{\ast })$ for each generated $k\ge 1$; for $k=0$ the gap is unchanged. A caller stop ends this finite prefix and does not assert later iterates. This is the bound from [F3] with $\mu \mathrm{/}L=1\mathrm{/}2$.