PaperlayerView exact revision on arXiv

Source-linked AI summary

A Lyapunov Analysis of Momentum Methods in Optimization

Ashia C. Wilson, Benjamin Recht, Michael I. Jordan

arXiv:1611.02635v4math.OCcs.DS

TL;DR

Momentum methods have effective but difficult-to-understand analyses, especially estimate sequences. The paper develops a Lyapunov-based framework, shows equivalence with estimate sequences, and uses it to unify analyses of existing algorithms and derive new ones.

  • Problem

    Estimate sequences support accelerated optimization methods but are difficult to understand, motivating alternative analyses and a search for clearer principles connecting discrete algorithms with continuous dynamics.

  • Method

    The paper develops Lyapunov functions for continuous and discrete momentum dynamics and relates them algebraically to estimate sequences.

  • Results

    The paper establishes equivalence between Lyapunov functions and estimate sequences and provides a unified analysis of many momentum algorithms.

  • Takeaways & Limitations

    The dynamical-systems perspective makes the design and analysis of accelerated optimization algorithms more transparent within the paper’s framework.

  • Takeaways & Limitations

    Constructing estimate sequences remains non-constructive and non-trivial, while preserving Lyapunov structure in discrete time restricts the ODE solvers that can be used.

Abstract

from arXiv · show

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.

1 Introduction

Momentum methods accelerate optimization, but the physical intuition behind them is not globally rigorous for general convex objectives. Nesterov’s estimate sequences provide general guarantees, yet their structure has remained difficult to understand and apply.

  • Motivation: Momentum adds a weighted previous step to the current step, encouraging directions that were previously fruitful.It has been used in practical optimization solvers and neural-network backpropagation since the 1980s.
  • Limits of physical intuition: Polyak’s Heavy Ball Method admits an eigenvalue-based comparison with conjugate gradients for quadratic costs.For positive-definite quadratics, it is equivalent to Chebyshev’s Iterative Method.
  • Limits of physical intuition: That eigenvalue analysis does not apply globally to general convex costs, and the standard Heavy Ball Method can fail to converge on a one-dimensional example.The counterexample was derived by Lessard and collaborators.
  • Estimate sequences: Nesterov’s estimate sequences establish broadly applicable acceleration guarantees under convex-programming oracle models.This approach replaced Polyak’s physical intuition with an algebraic verification technique.
  • Open gap: Continuous-time Lyapunov analyses clarify accelerated dynamics, but prior approaches did not provide principles for deriving convergent accelerated discrete algorithms from ODEs.The paper therefore develops a fuller Lyapunov-theoretic approach to the discretization problem.

2 A Dynamical View of Momentum Methods

The paper views momentum through Bregman-based continuous dynamics and Lyapunov functions. Under convexity and scaling conditions, these functions certify convergence rates, including O(e^-βt) in continuous time.

  • Problem setting: The setting uses a closed convex domain X, a continuously differentiable convex objective f, and a distance-generating function h defining a Bregman divergence.The function h is convex and essentially smooth; the Euclidean case is recovered with h(x) = 1/2∥x∥^2.
  • Bregman dynamics: The Bregman Lagrangian defines dynamics through position, velocity, time, and time-dependent functions α, β, and γ controlling damping and weighting.Its action is obtained by integrating the Lagrangian over curves, and the Euler-Lagrange equation identifies stationary trajectories.
  • Second Bregman dynamics: The second Bregman Lagrangian changes the damping applied to kinetic energy and yields a distinct Euler-Lagrange equation under the same scaling condition.This introduces a second family of continuous-time dynamics for analysis.
  • From dynamics to algorithms: Discretizing the dynamics produces optimization algorithms, and discretizing their Lyapunov functions supplies tools for analyzing those algorithms.The paper next studies discretizations that include explicit and implicit methods.
  • Lyapunov analysis: Lyapunov analysis constructs positive quantities that decrease along trajectories, thereby certifying convergence under suitable assumptions on f and h.The paper derives Lyapunov functions for both Euler-Lagrange families, with additional uniform-convexity assumptions for the second family.
  • Convergence rates: Under the stated scaling and convexity conditions, the derived Lyapunov functions imply an O(e^-βt) convergence rate for the objective value.For the second dynamics, the Lyapunov inequality applies at x = x* and extends to all x when the ideal scaling holds with equality.

3 Discretization Analysis

The paper analyzes how explicit and implicit Euler discretizations of continuous-time dynamics yield discrete optimization algorithms with Lyapunov-based convergence guarantees. An additional sequence and map G unify accelerated gradient, higher-order, universal, proximal, and related methods under this analysis.

  • Discretization schemes: Explicit Euler is easier to implement, while implicit Euler offers greater stability and convergence properties but requires solving an expensive implicit equation.
  • Discretization schemes: The analysis combines explicit and implicit discretizations in four ways to obtain algorithmic families from first-order dynamical systems.
  • Accelerated gradient family: The additional sequence y_k+1 = G(x) can produce better Lyapunov error bounds than the straightforward choice y_k+1 = x_k+1.
  • Accelerated gradient family: Accelerated gradient descent, accelerated higher-order, universal, and proximal methods arise from particular choices of G and smoothness assumptions on f and h.
  • Accelerated gradient family: O(1/εσk^2) matches the lower bound for algorithms using only full gradients under the stated smoothness assumptions.
  • Higher-order methods: O(1/εσk^p) improves over O(1/εσk^(p−1)) for the corresponding higher-order method under the same smoothness assumptions.

4 Equivalence to Estimate Sequences

The paper formalizes estimate sequences and shows their equivalence to Lyapunov functions in continuous and discrete time. This connection explains both their construction and their role in analyzing accelerated methods.

  • 4.2 Equivalence to Lyapunov functions: The paper derives continuous-time estimate sequences from Lyapunov functions and demonstrates that the two techniques are equivalent.The continuous-time view attributes errors in both frameworks to discretization errors.
  • 4.1 Estimate sequences: Estimate sequences provide a general framework for verifying convergence of momentum-based optimization methods.Nesterov’s lemma explains why sequences satisfying the estimate-sequence conditions are useful.
  • 4.1 Estimate sequences: Constructing estimate sequences is non-trivial because their definition is not constructive and typically requires knowing ε_k, A_k, and φ_k(x) in advance.A formal construction based on functions that underestimate f is presented as guidance.
  • 4.1 Estimate sequences: Table 1 organizes the choices of φ_k(x) and ε̃_k used for the four methods discussed in the paper.The table distinguishes linear and quadratic function choices.
  • 4.2 Equivalence to Lyapunov functions: In discrete time, the accelerated-gradient estimate sequence and Lyapunov analysis can be transformed into each other through algebraic rearrangement.The correspondence includes deriving E_k+1 ≤ E_k from the estimate sequence and recovering an estimate sequence from the Lyapunov bound.

5 Further Observations

The paper extends its Lyapunov-based perspective beyond the main deterministic momentum methods to proximal and stochastic optimization algorithms.

  • Proximal methods: The dynamical perspective extends to proximal methods for minimizing composite convex objectives.The paper recovers their convergence theory using the presented Lyapunov functions.
  • Stochastic methods: For stochastic methods, the paper analyzes four momentum-based algorithm families using Lyapunov inequalities with expected error terms.The families include stochastic mirror descent, accelerated coordinate descent, accelerated SVRG, and accelerated stochastic composite methods.
  • Stochastic methods: The stochastic analyses yield convergence rates by summing bounds on expected Lyapunov changes, provided the error sequence satisfies the stated condition.The bounds are E[E_k+1]−E_k ≤ E[ε_k+1] and E[E_k+1]−E_k ≤ −τ_kE_k + E[ε_k+1].

6 Discussion

The paper presents a unified Lyapunov analysis of many algorithms and connects discrete optimization methods with continuous-time dissipative dynamics. It also identifies constraints and open directions for extending this framework.

  • 6 Discussion: The main contributions are a unified analysis using three Lyapunov functions and an equivalence with Baes’s formalization of estimate sequences.The framework covers a wide variety of algorithms.
  • 6 Discussion: The dynamical-systems perspective connects discrete-time algorithms with continuous-time dissipative second-order dynamics.It builds on Polyak’s early momentum intuition.
  • 6 Discussion: Requiring a continuous-time Lyapunov function to remain valid in discrete time significantly constrains the ODE solvers that can be used.The paper derives new algorithms using a restricted set of ODE techniques, including several nonstandard ones.
  • 6 Discussion: The paper leaves open whether more accurate methods such as midpoint and Runge–Kutta schemes can be analyzed as optimization methods.It expects these methods may not improve asymptotic rates but could provide additional favorable properties.
  • 6 Discussion: Semidefinite-programming approaches might be adapted to automate the search for Lyapunov functions beyond momentum methods.This could extend automated analysis to novel optimization families.

A.2.1 Proof of Proposition 2

This appendix derives Lyapunov functions for momentum dynamics and bounds their discrete-time change using convexity, uniform convexity, and Bregman-divergence identities.

  • Lyapunov derivation: The Lyapunov function for momentum dynamics (4) is derived by combining the momentum dynamics with convexity of f.Under β̇_t = e^α_t, its derivative is nonpositive for all t; under β̇_t ≤ e^α_t, decrease is guaranteed only at x = x*.
  • Lyapunov derivation: The derivation for momentum dynamics (6) uses the Bregman three-point identity, uniform convexity, nonnegative Bregman divergence, and the ideal scaling condition.When β̇_t ≤ e^α_t, the argument requires x = x*.
  • Initial bounds: The initial error bounds use uniform convexity of h, the Fenchel–Young inequality, and the specified update identities.These bounds establish the starting conditions needed for the subsequent Lyapunov analysis.
  • Discrete-time bounds: The discrete-time Lyapunov change is expanded into Bregman-divergence and objective-difference terms before applying uniform convexity and Fenchel–Young inequalities.The resulting expression is then combined with the algorithmic update.
  • Discrete-time bounds: Convexity of f yields the bound E_k+1 − E_k ≤ ε_k for the analyzed update.The preceding rearrangement expresses the change in terms of convexity-controlled error terms.

B.2 Proof of Proposition 7

The proof establishes a progress bound for the higher-order method by combining Hölder continuity with convexity and analyzing a convex expression in the step distance.

  • Proof of Proposition 7: The proof uses Hölder continuity of the gradient to bound the higher-order Taylor expansion error.This bound is applied to the (p − 2)-nd-order expansion of ∇f.
  • Proof of Proposition 7: The resulting inequality proves the progress bound (32).The argument concludes after squaring, expanding, and rearranging the preceding inequality.
  • Proof of Proposition 7: When ˜p = 2, the first term alone implies the desired bound.The proof treats the ˜p = 2 case separately before assuming ˜p ≥ 3.
  • Proof of Proposition 7: For ˜p ≥ 3, the resulting expression has the form A/r^(˜p−2) + Br^˜p, which is convex for r > 0.The convexity enables the subsequent minimization argument.

B.3 Proof of Universal Gradient Method

The universal gradient method is analyzed through Lyapunov functions in continuous and discrete time, yielding polynomial convergence rates under Hölder-smoothness assumptions.

  • Continuous-time analysis: The continuous-time analysis uses a Lyapunov function and obtains an O(t^(p−1)) convergence rate by integration.The argument uses convexity, Fenchel–Young, and boundedness of the trajectory relative to an optimum.
  • Rate conclusion: Choosing A_k as a polynomial of degree ˜p gives an O(1/k^(˜p−1)) convergence rate.The proof first establishes descent and then sums the resulting bound.
  • Discrete-time analysis: The discrete-time proof applies a Lyapunov function to control successive energy differences.The proof begins by defining the Lyapunov function and bounding its one-step change.
  • Discrete-time analysis: The inequalities rely on strong convexity, the Bregman three-point identity, Fenchel–Young, and smoothness of f.These properties are used at different stages of the energy-difference bound.
  • Continuous-time connection: The same Lyapunov framework is shown to apply to the associated dynamics.The proof explicitly identifies (47) as a Lyapunov function for dynamics (44).

C.1 The quasi-monotone subgradient method

This section demonstrates the equivalence between discrete-time estimate sequences and Lyapunov arguments, including continuous-time estimate sequences for Frank–Wolfe and accelerated gradient descent.

  • Quasi-monotone subgradient method: The Lyapunov argument yields an energy inequality with an additive error term for the quasi-monotone subgradient method.The resulting relation is E_k+1 ≤ E_k + ε_k+1.
  • Estimate-sequence equivalence: Conversely, the Lyapunov analysis produces an estimate-sequence bound with an additional error term.This establishes the reverse direction of the correspondence.
  • Conditional gradient method: For the conditional gradient method, the Lyapunov inequality leads to a bound involving E_k, A_k, f(x_k), and the estimate sequence φ_k.The displayed inequality connects the energy bound to the estimate-sequence construction.
  • Frank–Wolfe: In continuous time, the Lyapunov property extracts {f(X_t), e^βt} as the estimate sequence for Frank–Wolfe.This identifies the continuous-time estimate sequence directly from the Lyapunov function.
  • Accelerated gradient descent: For strongly convex accelerated gradient descent, the continuous-time estimate sequence includes f(X_t) + µ/2∥x − Z_t∥² and e^βt.The construction is obtained from the Lyapunov function property.
  • Existence and uniqueness: Under Lipschitz continuity of ∇f, the Euclidean dynamics have a unique maximal solution for arbitrary future time.The proof applies the Cauchy–Lipschitz theorem and uses energy decrease to extend the solution.

D.1.1 Convex functions [32, 4, 21]

The paper extends Lyapunov analyses to composite convex and strongly convex objectives, including nonsmooth terms, continuous-time rates, and discretized proximal algorithms.

  • Convex composite functions: For composite objectives f = ϕ + ψ with smooth ϕ and simple nonsmooth ψ, directional subgradients support a continuous-time Lyapunov analysis.The paper defines directional subgradients and applies them to second-order dynamics.
  • Convex composite functions: Solutions of the composite second-order ODE satisfy f(X_t) − f(x) ≤ O(1/t^p).The result follows by showing that the associated Lyapunov function is non-increasing.
  • Discretization: Discretizing the composite dynamics with implicit and explicit Euler schemes produces a proximal update and an associated algorithm.The discretization uses distinct schemes for the smooth and nonsmooth vector-field components.
  • Convex composite functions: The convex composite algorithm is analyzed under strong convexity of h, smoothness of ϕ, and simplicity of ψ.Proposition 20 states an initial bound whose error has a specified scaling.
  • Strongly convex functions: The continuous-time strongly convex analysis gives f(X_t) − f(x) ≤ O(e^(−βt)).The result applies when ϕ is strongly convex relative to h and ψ is convex.
  • Strongly convex functions: For the strongly convex setting, the condition ensuring non-positive error matches accelerated gradient descent, yielding a rate that matches the lower bound.The analysis also permits subgradients of ψ.

D.2 Stochastic methods

The section extends the Lyapunov analysis to stochastic-gradient and stochastic-dynamics settings, deriving error bounds for two algorithms and comparing them with established stochastic optimization rates.

  • Stochastic-gradient algorithms: Stochastic-gradient versions of algorithms (19) and (42) admit Lyapunov-based error bounds under the stated convexity assumptions.The bounds follow from the proofs of Propositions 5 and 12 after replacing full gradients with stochastic gradients.
  • Stochastic-gradient algorithms: O(1/k) is obtained for the second algorithm, matching the rate of SGD while applying to the entire sequence of iterates.The section contrasts this sequence-wide guarantee with SGD’s rate statement.
  • Stochastic dynamics: The stochastic dynamics framework introduces an additional sequence y_k, with choices of G recovering discretizations of the continuous-time systems.The framework encompasses several accelerated method families through particular choices of G.
  • Stochastic dynamics: For the Euclidean strongly convex stochastic dynamics, the diffusion coefficient is assumed to have bounded expected squared operator norm.The dynamics use Brownian motion and assume E∥σ(X_t,t)^⊤σ(X_t,t)∥^2 ≤ M.
  • Stochastic dynamics: Taking expectations removes the Itô-integral term through the martingale property, enabling the Lyapunov estimate.The stochastic integral vanishes after expectation is taken.
  • Stochastic dynamics: Choosing β_t = 2 log t + log(1/2) yields an O(1/t^2) + O(1/t) convergence rate.The resulting upper bound is compared with the discrete bound using β̇_t = τ_k and e^β_t = A_k.
Loading 1611.02635v4…