Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems

Abstract

The optimization step in many machine learning problems rarely relies on vanilla gradient descent but it is common practice to use momentum-based accelerated methods. Despite these algorithms being widely applied to arbitrary loss functions, their behaviour in generically non-convex, high dimensional landscapes is poorly understood. In this work, we use dynamical mean field theory techniques to describe analytically the average dynamics of these methods in a prototypical non-convex model: the (spiked) matrix-tensor model. We derive a closed set of equations that describe the behaviour of heavy-ball momentum and Nesterov acceleration in the infinite dimensional limit. By numerical integration of these equations, we observe that these methods speed up the dynamics but do not improve the algorithmic threshold with respect to gradient descent in the spiked model.

arXiv commentTo appear in NeurIPS 2021

References in corpus (16)

• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Spin-Glass Theory for Pedestrians
• Temperature evolution and bifurcations of metastable states in mean-field spin glasses, with connections with structural glasses
• The spherical 2+p spin glass model: an analytically solvable model with a glass-to-glass transition
• Quasi-hyperbolic momentum and Adam for deep learning
• Intrinsically-generated fluctuating activity in excitatory-inhibitory networks
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• From Averaging to Acceleration, There is Only a Step-size
• Out-of-equilibrium dynamical mean-field equations for the perceptron model
• Understanding the Role of Momentum in Stochastic Gradient Methods
• Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem
• Gradient descent dynamics in the mixed $p$-spin spherical model: finite size simulation and comparison with mean-field integration
• Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval
• Non equilibrium dynamics of isolated disordered systems: the classical Hamiltonian p-spin model
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization