Gradient descent rate under strong convexity and smoothness

Fix $x$ and write $g:=\mathrm{\nabla }f(x)$ and $d:=-g\mathrm{/}L$. Define $\varphi (s):=f(x+sd)$ on $[0,1]$. By [F2]–[F3], ${\varphi }^{\mathrm{\prime }}(s)=⟨\mathrm{\nabla }f(x+sd),d⟩$ on $(0,1)$. The gradient is continuous by [A1], so ${\varphi }^{\mathrm{\prime }}$ is continuous and integrable by [F4]. Applying [F5] gives $f(x-g\mathrm{/}L)-f(x)=-\frac{1}{L}{\int }_0^1⟨\mathrm{\nabla }f(x-sg\mathrm{/}L),g⟩ds\mathrm{.}$ By [A1] and [F6], $\mathrm{\parallel }\mathrm{\nabla }f(x-sg\mathrm{/}L)-g\mathrm{\parallel }\le s\mathrm{\parallel }g\mathrm{\parallel }$, whence $⟨\mathrm{\nabla }f(x-sg\mathrm{/}L),g⟩\ge (1-s)\mathrm{\parallel }g{\mathrm{\parallel }}^2$. Integrating this bound gives $f(x-g\mathrm{/}L)\le f(x)-\frac{\mathrm{\parallel }g{\mathrm{\parallel }}^2}{2L}\mathrm{.}$

By [A2], for every $y$, $f(y)\ge f(x)+⟨g,y-x⟩+\frac{\mu }{2}\mathrm{\parallel }y-x{\mathrm{\parallel }}^2=f(x)-\frac{\mathrm{\parallel }g{\mathrm{\parallel }}^2}{2\mu }+\frac{\mu }{2}{\parallel y-x+\frac{g}{\mu }\parallel }^2\mathrm{.}$ Taking $y=x^{\ast }$ and using nonnegativity of the square yields $\mathrm{\parallel }g{\mathrm{\parallel }}^2\ge 2\mu (f(x)-f^{\ast })$.

Apply steps 1.1 and 1.2 at $x=x_k$ and use [F1]. Then $f(x_{k+1})-f^{\ast }\le f(x_k)-f^{\ast }-\frac{\mathrm{\parallel }\mathrm{\nabla }f(x_k){\mathrm{\parallel }}^2}{2L}\le (1-\frac{\mu }{L})(f(x_k)-f^{\ast })\mathrm{.}$ The factor is nonnegative because $\mu \le L$.

The $k=0$ case is equality. For $k=1$, the result is step 2.1 whenever $x_1$ is generated. If $x_{k+1}$ is generated, then $x_k$ was generated and the algorithm made the $k$th update; multiplying the bound at $k$ by $1-\mu \mathrm{/}L\ge 0$ and applying step 2.1 proves it at $k+1$. Induction along generated iterates gives the claim for every generated $k\ge 1$. If the stopping rule fires earlier, no later iterate is asserted.