A Proof of the Exact Convergence Rate of Gradient Descent

2024/12/05 by Jungbin Kim, Kim, Jungbin · 3 citations
Computer Science · Engineering · #Digital Image Processing Techniques #Advanced Numerical Analysis Techniques

paper · pdf · doi:10.48550/arxiv.2412.04427

Abstract

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(x_N)-f_*≤τ‖x₀-x_*‖² 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.

Cited by

• Data-Driven Analysis of First-Order Methods via Distributionally Robust Optimization
• A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms
• Optimized methods for composite optimization: a reduction perspective

Related

• A Proof of Exact Convergence Rate of Gradient Descent. Part I. Performance Criterion \Vert ∇ f(x_N)\Vert²/(f(x₀)-f_*)
• 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 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
• Revisit Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds