On the Last Iterate Convergence of Momentum Methods

Abstract

SGD with Momentum (SGDM) is a widely used family of algorithms for large-scale optimization of machine learning problems. Yet, when optimizing generic convex functions, no advantage is known for any SGDM algorithm over plain SGD. Moreover, even the most recent results require changes to the SGDM algorithms, like averaging of the iterates and a projection onto a bounded domain, which are rarely used in practice. In this paper, we focus on the convergence rate of the last iterate of SGDM. For the first time, we prove that for any constant momentum factor, there exists a Lipschitz and convex function for which the last iterate of SGDM suffers from a suboptimal convergence rate of $\Omega (\frac{\ln T}{\sqrt{T}})$ after $T$ iterations. Based on this fact, we study a class of (both adaptive and non-adaptive) Follow-The-Regularized-Leader-based SGDM algorithms with increasing momentum and shrinking updates. For these algorithms, we show that the last iterate has optimal convergence $O(\frac{1}{\sqrt{T}})$ for unconstrained convex stochastic optimization problems without projections onto bounded domains nor knowledge of $T$. Further, we show a variety of results for FTRL-based SGDM when used with adaptive stepsizes. Empirical results are shown as well.

arXiv commentDifferences with ALT'22 camera ready: Clarified the statement of the lower bound

References in corpus (12)

• On the Convergence of Adam and Beyond
• Adaptive Gradient Methods with Dynamic Bound of Learning Rate
• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• Adaptive Bound Optimization for Online Convex Optimization
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Online Learning: A Modern Introduction Using Convex Optimization
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• Optimistic Rates for Learning with a Smooth Loss
• The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods
• Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization
• Dual Averaging is Surprisingly Effective for Deep Learning Optimization