A Proof of the Exact Convergence Rate of Gradient Descent

We prove the exact worst-case convergence rate of gradient descent for smooth strongly convex optimization on ℝd. Concretely, assuming that the objective function f is μ-strongly convex and L-smooth, we identify the smallest possible value of τ for which the inequality f(xN)-f*≤τ|x0-x*|2 always holds. The result was previously conjectured by Drori and Teboulle for the case μ=0, and by Taylor, Hendrickx, and Glineur for the case μ>0.