A Proof of Exact Convergence Rate of Gradient Descent. Part I. Performance Criterion \Vert ∇ f(x_N)\Vert²/(f(x₀)-f_*)

2024/12/05 by Kim, Jungbin
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2412.04435

Abstract

We prove the exact worst-case convergence rate of gradient descent for smooth strongly convex optimization, with respect to the performance criterion \Vert ∇ f(x_N)\Vert²/(f(x₀)-f_*). The proof differs from the previous one by Rotaru et al. [RGP24], and is based on the performance estimation methodology [DT14].

Related

• A Proof of the Exact Convergence Rate of Gradient Descent
• A note on the optimal convergence rate of descent methods with fixed step sizes for smooth strongly convex functions
• On the worst-case complexity of the gradient method with exact line\n search for smooth strongly convex functions
• Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions
• Smooth Strongly Convex Interpolation and Exact Worst-case Performance of\n First-order Methods