A Proof of Exact Convergence Rate of Gradient Descent. Part I. Performance Criterion $\Vert \nabla f(x_N){\Vert }^2/(f(x_0)-f_{\ast })$

Abstract

We prove the exact worst-case convergence rate of gradient descent for smooth strongly convex optimization, with respect to the performance criterion $\Vert \nabla f(x_N){\Vert }^2/(f(x_0)-f_{\ast })$. The proof differs from the previous one by Rotaru \emph{et al.} [RGP24], and is based on the performance estimation methodology [DT14].

Merged into arXiv:2412.04427