More Like this

1. On the fast convergence of minibatch heavy ball momentum

   https://doi.org/10.1093/imanum/drae033  

   Bollapragada, Raghu; Chen, Tyler; Ward, Rachel (August 2024, IMA Journal of Numerical Analysis)

   Abstract Simple stochastic momentum methods are widely used in machine learning optimization, but their good practical performance is at odds with an absence of theoretical guarantees of acceleration in the literature. In this work, we aim to close the gap between theory and practice by showing that stochastic heavy ball momentum retains the fast linear rate of (deterministic) heavy ball momentum on quadratic optimization problems, at least when minibatching with a sufficiently large batch size. The algorithm we study can be interpreted as an accelerated randomized Kaczmarz algorithm with minibatching and heavy ball momentum. The analysis relies on carefully decomposing the momentum transition matrix, and using new spectral norm concentration bounds for products of independent random matrices. We provide numerical illustrations demonstrating that our bounds are reasonably sharp. 

   more » « less
2. Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization

   Wei, Jingrong; Chen, Long (January 2025, International Conference on Learning Representations (ICLR))

   The heavy-ball momentum method accelerates gradient descent with a momentum term but lacks accelerated convergence for general smooth strongly convex problems. This work introduces the Accelerated Over-Relaxation Heavy-Ball (AOR-HB) method, the first variant with provable global and accelerated convergence for such problems. AOR-HB closes a long-standing theoretical gap, extends to composite convex optimization and min-max problems, and achieves optimal complexity bounds. It offers three key advantages: (1) broad generalization ability, (2) potential to reshape acceleration techniques, and (3) conceptual clarity and elegance compared to existing methods. 

   more » « less
3. From differential equation solvers to accelerated first-order methods for convex optimization

   https://doi.org/10.1007/s10107-021-01713-3  

   Luo, Hao; Chen, Long (October 2021, Mathematical Programming)

   Convergence analysis of accelerated first-order methods for convex optimization problems are developed from the point of view of ordinary differential equation solvers. A new dynamical system, called Nesterov accelerated gradient (NAG) flow, is derived from the connection between acceleration mechanism and A-stability of ODE solvers, and the exponential decay of a tailored Lyapunov function along with the solution trajectory is proved. Numerical discretizations of NAG flow are then considered and convergence rates are established via a discrete Lyapunov function. The proposed differential equation solver approach can not only cover existing accelerated methods, such as FISTA, Güler’s proximal algorithm and Nesterov’s accelerated gradient method, but also produce new algorithms for composite convex optimization that possess accelerated convergence rates. Both the convex and the strongly convex cases are handled in a unified way in our approach. 

   more » « less
4. From differential equation solvers to accelerated first-order methods for convex optimization

   https://doi.org/10.1007/s10107-021-01713-3  

   Luo, Hao; Chen, Long (October 2021, Mathematical programming)

   Convergence analysis of accelerated first-order methods for convex optimization prob- lems are developed from the point of view of ordinary differential equation solvers. A new dynamical system, called Nesterov accelerated gradient (NAG) flow, is derived from the connection between acceleration mechanism and A-stability of ODE solvers, and the exponential decay of a tailored Lyapunov function along with the solution tra- jectory is proved. Numerical discretizations of NAG flow are then considered and convergence rates are established via a discrete Lyapunov function. The proposed differential equation solver approach can not only cover existing accelerated meth- ods, such as FISTA, Güler’s proximal algorithm and Nesterov’s accelerated gradient method, but also produce new algorithms for composite convex optimization that pos- sess accelerated convergence rates. Both the convex and the strongly convex cases are handled in a unified way in our approach. 

   more » « less
5. Acceleration and Implicit Regularization in Gaussian Phase Retrieval

   Maunu, Tyler; Molina-Fructuoso, Martin (May 2024, Proceedings of Machine Learning Research)

   Dasgupta, Sanjoy; Mandt, Stephan; Li, Yingzhen (Ed.)

   We study accelerated optimization methods in the Gaussian phase retrieval problem. In this setting, we prove that gradient methods with Polyak or Nesterov momentum have similar implicit regularization to gradient descent. This implicit regularization ensures that the algorithms remain in a nice region, where the cost function is strongly convex and smooth despite being nonconvex in general. This ensures that these accelerated methods achieve faster rates of convergence than gradient descent. Experimental evidence demonstrates that the accelerated methods converge faster than gradient descent in practice. 

   more » « less