A Lyapunov Analysis of Momentum Methods in Optimization

By Ashia C. Wilson, B. Recht, Michael I. Jordan. 2016

236 citations recorded by the source corpus.

Momentum methods play a significant role in optimization. Examples include Nesterov's accelerated gradient method and the conditional gradient algorithm. Several momentum methods are provably optimal under standard oracle models, and all use a technique called estimate sequences to analyze their convergence properties. The technique of estimate sequences has long been considered difficult to understand, leading many researchers to generate alternative, "more intuitive" methods and analyses. We show there is an equivalence between the technique of estimate sequences and a family of Lyapunov functions in both continuous and discrete time. This connection allows us to develop a simple and unified analysis of many existing momentum algorithms, introduce several new algorithms, and strengthen the connection between algorithms and continuous-time dynamical systems.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Beyond Finite Layer Neural Networks: Bridging Deep Architectures and Numerical Differential Equations (2017, background): “The term ¨ u represents acceleration which leads to acceleration of the convergence of u n when f = −∇ g Su & Boyd (2015); Wilson et al. (2016).”
Accelerating Stochastic Gradient Descent (2017, background): “…θ. (ii) The key novelty in lemma 4 is that while standard analyses of accelerated gradient descent (in the exact first order oracle) use the potential function ‖x− x∗‖2H + µ ‖v − x∗‖ 2 2 (e.g. Wilson et al. (2016)), we consider it crucial for employing the potential function ‖x− x∗‖22 + µ ‖v −…”
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (2017, methodology): “Known Lyapunov functions for AGD [Wilson et al., 2016] are restricted to the convex setting and furthermore are not computable by the algorithm (as they depend on x ⋆ ).”
Understanding the acceleration phenomenon via high-resolution differential equations (2018, methodology): “In particular, these two methods have the same limiting ODE (see, for example, [44]): Ẍ(t) + 2√μẊ(t) + ∇ f (X(t)) = 0, (1.”
Aggregated Momentum: Stability Through Passive Damping (2018, methodology): “While most momentum methods can be viewed as the discretization of second order ODEs (Wilson et al., 2016) it seems that AggMo does not fall into this class of algorithms.”
Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems (2016, unknown): “A different approach is to use momentum methods [13] or random projections [14]– [17] to accelerate convergence.”
Effective Federated Adaptive Gradient Methods with Non-IID Decentralized Data (2020, background): “The SGD, its momentum variants (Ghadimi and Lan (2013); Wright and Nocedal (1999); Wilson et al. (2016); Yang et al. (2016)), and its adaptive versions (AGMs) (Duchi et al. (2011); Kingma and Ba (2014); Zeiler (2012)) can readily distribute their computation to multiple processors due to their…”
The Physical Systems Behind Optimization Algorithms (2016, background): “Recently, An independent paper of Wilson et al. (2016) studies a similar framework for analyzing first order algorithms, but their focus on bridging the gap between discrete algorithmic analysis and continuous approximation.”