A variational perspective on accelerated methods in optimization

By Andre Wibisono, Ashia C. Wilson, Michael I. Jordan. Proceedings of the National Academy of Sciences of the United States of America, 2016

659 citations recorded by the source corpus.

Significance Optimization problems arise naturally in statistical machine learning and other fields concerned with data analysis. The rapid growth in the scale and complexity of modern datasets has led to a focus on gradient-based methods and also on the class of accelerated methods, first proposed by Nesterov in 1983. Accelerated methods achieve faster convergence rates than gradient methods and indeed, under certain conditions, they achieve optimal rates. However, accelerated methods are not descent methods and remain a conceptual mystery. We propose a variational, continuous-time framework for understanding accelerated methods. We provide a systematic methodology for converting accelerated higher-order methods from continuous time to discrete time. Our work illuminates a class of dynamics that may be useful for designing better algorithms for optimization. Accelerated gradient methods play a central role in optimization, achieving optimal rates in many settings. Although many generalizations and extensions of Nesterov’s original acceleration method have been proposed, it is not yet clear what is the natural scope of the acceleration concept. In this paper, we study accelerated methods from a continuous-time perspective. We show that there is a Lagrangian functional that we call the Bregman Lagrangian, which generates a large class of accelerated methods in continuous time, including (but not limited to) accelerated gradient descent, its non-Euclidean extension, and accelerated higher-order gradient methods. We show that the continuous-time limit of all of these methods corresponds to traveling the same curve in spacetime at different speeds. From this perspective, Nesterov’s technique and many of its generalizations can be viewed as a systematic way to go from the continuous-time curves generated by the Bregman Lagrangian to a family of discrete-time accelerated algorithms.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/6d4f21e1ef8632de182846958a11d4b16e630180

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 Numerical Analysis

Citations in the corpus

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 ⋆ ).”
The Physical Systems Behind Optimization Algorithms (2016, background): “Recently, di ﬀ erential equation approaches attract enormous interests on the analysis of optimization algorithms, because they provide a clear interpretation for the continuous approximation of the algorithmic systems (Su et al., 2014; Wibisono et al., 2016).”
User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient (2017, background): “Some recent advances on the gradient flow (Wibisono et al., 2016) might be useful for achieving these goals.”
On Acceleration with Noise-Corrupted Gradients (2018, positive): “Recently, some of the mystery of acceleration has faded, as different works have provided natural interpretations and alternative proofs for accelerated methods (Allen-Zhu & Orecchia, 2017; Krichene et al., 2015; Wibisono et al., 2016; Bubeck et al., 2015; Lessard et al., 2016; Hu & Lessard, 2017; D”
Stochastic Gradient Descent Performs Variational Inference, Converges to Limit Cycles for Deep Networks (2017, background): “The continuous-time point-of-view used in this paper gives access to general principles that govern SGD, such analyses are increasingly becoming popular [57, 58].”
Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems (2016, neutral): “up convergence of ISTA (see [8], [9], [41]–[48] as a partial list of such works).”
Augmented Normalizing Flows: Bridging the Gap Between Generative Flows and Latent Variable Models (2020, methodology): “Our approximation theory builds on the result of Wang & Li (2019), which follows the optimal control framework of Wibisono et al. (2016).”
A Lyapunov Analysis of Momentum Methods in Optimization (2016, methodology): “An over-dot means derivative with respect to time, i.e., ˙ X t = X t .”
Stochastic Mirror Descent in Variationally Coherent Optimization Problems (2017, background): “For the role of variational monotonicity in the context of convex programming, see also [22].”
Underdamped Langevin MCMC: A non-asymptotic analysis (2017, background): “Also related is the recent work on understanding acceleration of first-order optimization methods as discretizations of second-order differential equations [23, 24, 25].”
Stochastic Modified Equations and Adaptive Stochastic Gradient Algorithms (2015, methodology): “Other deterministic continuous time approximation methods include Su et al. (2014); Krichene et al. (2015); Wibisono et al. (2016).”
Aggregated Momentum: Stability Through Passive Damping (2018, methodology): “The convergence of momentum methods has been studied extensively, both theoretically and empirically (Wibisono & Wilson, 2015; Wibisono et al., 2016; Wilson et al., 2016; Kidambi et al., 2018).”
Online Adaptive Methods, Universality and Acceleration (2018, background): “And the connection between acceleration and ODEs is investigated in, [30, 32, 13, 19, 5, 4].”
On Learning Rates and Schrödinger Operators (2020, methodology): “For example, [SBC16, WWJ16, SDJS18] derived ODEs for modeling Nesterov’s accelerated gradient methods and used the ODEs to understand the acceleration phenomenon (see the review [Jor18]).”
On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization (2018, methodology): “This approach has led to numerous interesting ﬁndings, including recent results in the context of acceleration methods ( e.g. Su et al. (2014); Wibisono et al. (2016)).”