PaperlayerView exact revision on arXiv

Source-linked AI summary

A Dynamical Systems Perspective on Nesterov Acceleration

Michael Muehlebach, Michael I. Jordan

arXiv:1905.07436v1math.OCcs.LGcs.SYeess.SYstat.ML

TL;DR

The paper asks how to understand Nesterov acceleration without deriving an ODE through a vanishing-step limit. It starts from a second-order ODE and discretizes it with semi-implicit Euler; the analysis identifies curvature-dependent damping as seemingly instrumental to acceleration.

  • Problem

    The paper seeks an interpretation of accelerated gradient that does not begin by deriving an ODE through a vanishing-step-size argument.

    Source: §1 · p. 1

  • Method

    The authors start with a second-order ODE and derive Nesterov acceleration by discretizing it with semi-implicit Euler.

    Source: §1 · p. 1

  • Results

    The analysis identifies a curvature-dependent damping term that locally averages curvature and seems instrumental to acceleration.

    Source: §1 · p. 1

  • Takeaways & Limitations

    Under regularity conditions, the discretization preserves phase-space area contraction and time-reversibility, linking properties of the continuous dynamics to the discrete algorithm.

    Source: §1 · p. 1

    Phase-space area contraction alone does not seem sufficient to derive a convergence rate for f(q).

    Source: §6 · p. 6

Abstract

from arXiv · show

We present a dynamical system framework for understanding Nesterov's accelerated gradient method. In contrast to earlier work, our derivation does not rely on a vanishing step size argument. We show that Nesterov acceleration arises from discretizing an ordinary differential equation with a semi-implicit Euler integration scheme. We analyze both the underlying differential equation as well as the discretization to obtain insights into the phenomenon of acceleration. The analysis suggests that a curvature-dependent damping term lies at the heart of the phenomenon. We further establish connections between the discretized and the continuous-time dynamics.

1. Introduction

The paper frames accelerated gradient as a dynamical-systems problem and derives Nesterov acceleration by discretizing an ODE, rather than by taking a vanishing-step limit. It focuses mainly on smooth, strongly convex objectives while also treating the non-strongly-convex setting.

1. Introduction

  • The motivating problem class is real-valued, convex optimization with a Lipschitz-continuous gradient, assumptions often met locally in practice.The presentation focuses on finite-dimensional, strongly convex functions for simplicity, but also treats the non-strongly-convex setting.Source: §1 · pp. 1–2
  • Gradient methods are simple and scale to large problems, while accelerated gradient methods use two successive gradients to obtain faster convergence rates.The paper also notes acceleration's role in understanding limits on convergence rates.Source: §1 · p. 1
  • Earlier work derived an ODE limit for accelerated-gradient trajectories when the step size vanishes; this paper instead starts from an ODE and discretizes it.The paper also situates its approach among geometric, control-theoretic, and variational interpretations of acceleration.Source: §1 · p. 1
  • Nesterov acceleration is derived by discretizing a second-order ODE with semi-implicit Euler, without relying on a vanishing-step-size argument.The model includes damping that locally averages curvature, which the authors say seems instrumental to acceleration.Source: §1 · p. 1
  • The analysis connects continuous and discrete dynamics: under regularity conditions, discretization preserves phase-space area contraction and time-reversibility.The authors propose that properties of the continuous-time system can help explain the resulting algorithm.Source: §1 · p. 1

2. Dynamical systems model

The paper obtains Nesterov’s constant-step accelerated-gradient scheme by applying semi-implicit Euler discretization to a second-order ODE. It also describes a non-strongly-convex variant and relates the ODE to a general energy-based dynamical-system form.

2. Dynamical systems model

  • Semi-implicit Euler discretization of the stated ODE yields the constant-step accelerated-gradient scheme presented in Nesterov (2004, p. 81).The derivation uses a step size Ts = 1.Source: §2 · p. 2
  • The ODE has the form ẍ(t) + 2d ẋ(t) + (1/L)∇f(x(t) + βẋ(t)) = 0, with γ set to one by a time rescaling.The authors set γ = 1 for notational simplicity; changing γ rescales solution time.Source: §2 · p. 2
  • The ODE is expressed in a general energy-based dynamical-system form by identifying position q with x and momentum p with ẋ.The scheme defines kinetic energy T(p), non-potential forces f_NP(q, p), and step size Ts > 0.Source: §2 · p. 2
  • For smooth non-strongly-convex functions, time-varying coefficients d̄(t) and β̄(t) give an algorithm related to the starting point used in Su et al. (2016).The coefficients satisfy 2d + β = 1 and 2d̄(t) + β̄(t) = 1 for all t ≥ 0.Source: §2 · pp. 2–3

3. Interpretation of the model

The ODE is interpreted as a mass-spring-damper system whose damping depends on local curvature, and its trajectories have stated convergence rates in both strongly and non-strongly-convex cases. The analysis links damping to energy dissipation and explains how constant and curvature-dependent damping are balanced.

3. Interpretation of the model

  • Without damping, total energy is conserved and trajectories remain on its level sets; with damping, energy dissipates and trajectories converge asymptotically to the origin.The authors state that similar asymptotic conclusions can be drawn in the non-convex case.Source: §3 · p. 3
  • The damping can be interpreted as a local average of curvature, with more averaging at higher velocities and larger maximum curvature κ.For large κ, 2d decreases with 1/√κ while β increases with 1/√κ.Source: §3 · p. 3
  • Total damping combines constant damping 2d and curvature-dependent damping β, which balance so that 2d + β = 1 for any maximum curvature κ.The constants are shown as functions of κ in Figure 1.Source: §3 · p. 3, Figure 1 · p. 3
  • The strongly convex ODE trajectories decay exponentially at rate at least 1/(2√κ) − 1/(4κ).The authors state that the rate matches the well-known accelerated-gradient rate.Source: §3 · pp. 3–4
  • In the non-strongly-convex case, f(x(t)) decays at least with O(1/t^2) when d and β are replaced by d̄(t) and β̄(t).The conclusions are described as analogous to those for the strongly convex case.Source: §3 · pp. 3–4
  • The convergence-rate propositions use Lyapunov functions, with parameter choices that make a cross-term vanish; more general sufficient conditions are possible.The function f is assumed smooth and strongly convex for the cited energy-dissipation bounds.Source: §3 · pp. 3–4

4. The discretization

The section analyzes how the discretization preserves geometric properties and establishes accelerated convergence. For Ts in (0, 1], discrete trajectories converge linearly at an accelerated rate; related area-contraction results compare discrete and continuous-time dynamics.

4. The discretization

  • The section relates phase-space area contraction to the continuous-time dynamics and uses geometric properties to bound convergence, while noting that the rate proof relies on a Lyapunov function.The area-contraction proposition is stated for a one-dimensional objective function.Source: §4 · p. 4
  • The discretization separates into a contraction step using non-conservative forces and a symplectic Euler step using the conservative dynamics.The symplectic Euler scheme is described as energy consistent over exponentially long time intervals.Source: §4 · p. 4
  • The discretized phase-space area contracts for Ts in (0, 2); for Ts in (0, 1], its contour preserves orientation, and at Ts = 1 it may contract to a point.The section states that the area contraction rate essentially matches the continuous-time counterpart; over one time step, contraction of an energy-level-set area is larger for the discretized dynamics.Source: §4 · p. 5
  • For Ts in (0, 1), the discrete integration is a homeomorphism and therefore time reversible, paralleling the continuous-time dynamics.The section combines this property with phase-space area contraction to bound convergence in a worst-case sense.Source: §4 · pp. 4–5
  • For every Ts in (0, 1], all trajectories of the discrete dynamics converge linearly with rate at least 1 − TsO(1/√κ).For Ts in (0, 1), the analysis also establishes that at least one trajectory converges at this rate.Source: §4 · p. 5

5. Simulation example

The numerical example varies the time step in the discrete integration and examines the resulting phase-space trajectories. Larger steps produce increasingly folded trajectories; at and above Ts = 1, the dynamics show additional changes, including loss of orientation preservation above 1.

5. Simulation example

  • The example uses a function and gradient with condition number κ = 5, and varies initial q0 from −2 to 5 in steps of 0.2.The time step is increased successively from 0.1 to 1.2.Source: §5 · p. 5
  • As Ts increases, trajectories fold more; at Ts = 1, multiple initial conditions can map to one point, and starts with q0 < 1 converge in two steps.For Ts = 1.3, trajectories starting from q0 ≥ 4.4 diverge.Source: §5 · p. 6
  • For Ts above 1, the integration map is no longer orientation preserving, and the resulting motion is less structured.The plotted panels use Ts = 0.1, 0.5, 1, and 1.2.Source: §5 · p. 6, Figure 3 · p. 6

6. Conclusions

The conclusions interpret Nesterov’s accelerated gradient method as a semi-implicit Euler discretization of an ODE with curvature-dependent damping. The analysis relates discretized geometric properties to continuous-time dynamics, while identifying limits to the justification and implications of area contraction.

6. Conclusions

  • Nesterov’s accelerated gradient method is interpreted as a semi-implicit Euler discretization of an ODE whose curvature-dependent damping seems essential for acceleration.The analysis suggests that time reversibility and phase-space area contraction are conserved by the discretization.Source: §6 · p. 6
  • Because the contraction and symplectic Euler steps do not commute, straightforward backward error analysis to rigorously justify the discretization intuition seems difficult.The symplectic Euler step is based on the conservative dynamics, and the contraction step on the non-conservative part.Source: §6 · p. 6
  • Phase-space area contraction alone does not seem sufficient to derive a convergence rate for f(q).Source: §6 · p. 6

A.1. Proof of Prop. 3.1

The proof of Proposition 3.1 uses a Lyapunov function for the differential equation. It bounds the derivative along trajectories to establish exponential decay.

A.1. Proof of Prop. 3.1

  • A Lyapunov function V is evaluated along trajectories of the differential equation to support the proof of Proposition 3.1.The proof uses y := q + βp and bounds based on smoothness and strong convexity.Source: §A.1 · p. 8
  • The constant a is chosen to cancel the cross-term q^T p, allowing the remaining term to be bounded.Source: §A.1 · p. 8
  • The coefficient inequalities imply V̇ ≤ −aV; Grönwall’s inequality then establishes the proposition.Source: §A.1 · p. 8

A.2. Proof of Prop. 3.2

The proof bounds the differential equation with a time-dependent Lyapunov function. Its derivative estimate uses a piecewise case analysis and yields the proposition’s bound for t≥1.

A.2. Proof of Prop. 3.2

  • The choice of ā(t) cancels the qᵀp cross term, while two coefficient expressions vanish.The proof states ā(t)=2/(t+2) and uses the resulting cancellations in its derivative calculation.Source: §A.2 · p. 8
  • Smoothness and convexity bound the final term in the Lyapunov derivative.The resulting derivative bound is piecewise, with an additional momentum term for t∈[0,1).Source: §A.2 · p. 8
  • Uniform Lipschitz continuity bounds trajectory growth, allowing the proof to control the Lyapunov function at t=1.The argument then applies Grönwall’s inequality.Source: §A.2 · p. 8
  • For t≥1, the Lyapunov estimate establishes the proposition, with C̄≤5/6.The proof’s stated bound applies for all t≥1.Source: §A.2 · p. 9

A.3. Generalization of Prop. 4.1 to dimensions n ≥1

The proof generalizes the proposition using smooth surfaces in phase space and the variational form of the integration scheme. Stokes’ theorem connects the boundary calculation to the stated surface-integral relations.

A.3. Generalization of Prop. 4.1 to dimensions n ≥1

  • A smooth two-dimensional surface with boundary is represented as the image of the unit simplex under a smooth map into R²ⁿ.The proof assumes f is sufficiently smooth.Source: §A.3 · p. 9
  • The integration scheme is rewritten as a variational equality and applied to parametrized points along the surface boundary.The boundary is mapped to the boundary of the next surface by continuity of the scheme.Source: §A.3 · p. 9
  • Stokes’ theorem yields formulas (46) and (47) from the respective boundary integrals.The integrated form uses the canonical symplectic form dq∧dp.Source: §A.3 · p. 9

A.4. Proof of Prop. 4.2

The proof block establishes area containment under the continuous dynamics, bijectivity properties of the discretization, and conditions used in a discrete-time Lyapunov argument.

A.4. Proof of Prop. 4.2

  • Energy dissipation keeps Γ(t) within Γ(0), supporting the area comparison in the proof.A(t) denotes the area enclosed by ∂Γ(t).Source: §A.4 · p. 9

A.5. Proof of Prop. 4.3

  • The contraction-step iteration converges to a unique limit, and the full map is Lipschitz and composed of bijective steps.The contraction property holds for Ts∈(0,1) because 2d+β=1.Source: §A.5 · pp. 9–10

A.6. Proof of Prop. 4.5

  • For Ts∈(0,1], M is negative semidefinite for sufficiently large κ; the proposed discrete-time Lyapunov function is positive definite in that range.For Ts∈(0,1), M is negative definite as κ→∞; at Ts=1 it is negative semidefinite for all κ≥1.Source: §A.6 · pp. 10–11
Loading 1905.07436v1…