Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule

Abstract

Can we accelerate convergence of gradient descent without changing the algorithm -- just by carefully choosing stepsizes? Surprisingly, we show that the answer is yes. Our proposed Silver Stepsize Schedule optimizes strongly convex functions in $k^{{\log }_{\rho }2}\approx k^{0.7864}$ iterations, where $\rho =1+\sqrt{2}$ is the silver ratio and $k$ is the condition number. This is intermediate between the textbook unaccelerated rate $k$ and the accelerated rate $\sqrt{k}$ due to Nesterov in 1983. The non-strongly convex setting is conceptually identical, and standard black-box reductions imply an analogous accelerated rate ${\epsilon }^{-{\log }_{\rho }2}\approx {\epsilon }^{-0.7864}$. We conjecture and provide partial evidence that these rates are optimal among all possible stepsize schedules. The Silver Stepsize Schedule is constructed recursively in a fully explicit way. It is non-monotonic, fractal-like, and approximately periodic of period $k^{{\log }_{\rho }2}$. This leads to a phase transition in the convergence rate: initially super-exponential (acceleration regime), then exponential (saturation regime).

arXiv comment7 figures

References in corpus (16)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Optimized first-order methods for smooth convex minimization
• A Lyapunov Analysis of Momentum Methods in Optimization
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Acceleration Methods
• On the convergence analysis of the optimized gradient method
• Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions
• Provable Super-Convergence with a Large Cyclical Learning Rate
• Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization
• Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
• Time-Reversed Dissipation Induces Duality Between Minimizing Gradient Norm and Function Value
• Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods
• Nonlinear conjugate gradient methods: worst-case convergence rates via computer-assisted analyses
• Provably Faster Gradient Descent via Long Steps

Cited by in corpus (1)

• Tannenbaum's gain-margin optimization meets Polyak's heavy-ball algorithm