A Proof of the Exact Convergence Rate of Gradient Descent

Abstract

We prove the exact worst-case convergence rate of gradient descent for smooth strongly convex optimization on ${\mathbb{R}}^d$. Concretely, assuming that the objective function $f$ is $\mu$-strongly convex and $L$-smooth, we identify the smallest possible value of $\tau$ for which the inequality $f(x_N)-f_{\ast }\le \tau \Vert x_0-x_{\ast }{\Vert }^2$ always holds. The result was previously conjectured by Drori and Teboulle for the case $\mu =0$, and by Taylor, Hendrickx, and Glineur for the case $\mu >0$.

Part I and Part II are merged