PaperlayerView exact revision on arXiv

Source-linked AI summary

A Variational Perspective on Accelerated Methods in Optimization

Andre Wibisono, Ashia C. Wilson, Michael I. Jordan

arXiv:1603.04245v1math.OCcs.LGstat.ML

TL;DR

Acceleration lacks a single underlying principle despite broad success and many extensions. The paper introduces the Bregman Lagrangian as a continuous-time variational framework generating accelerated methods, and shows that these methods correspond to one spacetime curve traversed at different speeds. Its discretizations include higher-order accelerated algorithms with matching rates, while naive Euler discretization can be unstable and the connection to restart schemes remains open.

  • Problem

    Despite acceleration’s broad use, its natural scope and status as a unified phenomenon remain unclear because existing explanations are often case-specific or restricted.

  • Method

    The paper defines a Bregman Lagrangian on continuous-time curves, derives its Euler-Lagrange equations, and discretizes them to construct accelerated algorithms.

  • Results

    The framework generates accelerated gradient, non-Euclidean, and higher-order methods whose continuous-time limits correspond to the same spacetime curve at different speeds.

  • Takeaways & Limitations

    Acceleration can be viewed as systematically discretizing and time-rescaling continuous-time Bregman-Lagrangian curves rather than as a collection of unrelated techniques.

  • Takeaways & Limitations

    Naive Euler discretization can be unstable, and the connection between discrete restart algorithms and exponential continuous-time flows remains open.

Abstract

from arXiv · show

Accelerated gradient methods play a central role in optimization, achieving optimal rates in many settings. While 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 \emph{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 correspond 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.

1 Introduction

The paper frames acceleration as broadly successful but conceptually fragmented, then proposes a continuous-time variational framework to unify accelerated methods and their discrete counterparts.

  • Acceleration has extended from Nesterov’s gradient descent to composite, stochastic, nonconvex, conic, non-Euclidean, and higher-order optimization.
  • Existing explanations rely on case-specific algebra or momentum intuition that does not readily generalize beyond restrictive settings.
  • The paper studies acceleration through a continuous-time variational formulation centered on a Bregman Lagrangian, then discretizes its Euler-Lagrange equation.
  • Accelerated gradient descent has discrete and continuous rates O(1/(ǫk2)) and O(1/t2), matching under t = √ǫk.
  • The Bregman Lagrangian is closed under time dilation, so accelerated methods correspond to one spacetime curve traversed at different speeds.
  • The framework is organized around general Bregman Lagrangians, their discretization into accelerated algorithms, and further properties including gauge invariance and classical-gradient connections.

2 The Bregman Lagrangian

The Bregman Lagrangian defines variational dynamics whose Euler-Lagrange solutions converge rapidly, while time dilation preserves the framework and links differently paced accelerated trajectories.

  • The Bregman Lagrangian: The Bregman Lagrangian depends on position, velocity, time, and smooth functions α, β, γ that weight velocity, potential, and damping.
  • Convergence rates: Under ideal scaling, Euler-Lagrange solutions minimize the objective at an exponential rate through a nonincreasing energy functional.
  • Convergence rates: The convergence proof uses an energy functional whose derivative is nonpositive, with convexity ensuring the relevant Bregman divergences are nonnegative.
  • Convergence rates: For fixed α_t, choosing β̇_t = e^α_t yields the optimal rate O(e^-βt) = O(exp(-∫_t0^t e^αs ds)).
  • Time dilation: Reparameterizing an Euler-Lagrange curve produces another Bregman-Lagrangian curve with modified parameters, while preserving the ideal scaling conditions.
  • Time dilation: The time-dilation property makes the family of continuous-time accelerated-method curves interpretable as one curve traveled at different speeds.

3 Polynomial convergence rates and accelerated methods

The paper constructs accelerated higher-order methods by discretizing polynomial Bregman-Lagrangian flows, showing how rate-matching schemes extend Nesterov’s approach beyond gradient descent. It contrasts unstable naive discretization with a three-sequence algorithm whose discrete rate matches the continuous-time rate.

  • Continuous-time dynamics: The polynomial Bregman-Lagrangian subfamily yields Euler-Lagrange dynamics with an O(1/t^p) convergence rate.The parameter p indexes the family, and time dilation maps every curve to the p = 2 curve via τ(t) = t^(p/2).
  • Continuous-time dynamics: For p = 2 and p = 3, the continuous-time dynamics recover accelerated mirror descent and accelerated cubic-regularized Newton’s method, respectively.In the Euclidean p = 2 case, the equation also recovers Su et al.’s accelerated-gradient differential equation.
  • Naive discretization: Naive forward- and backward-Euler discretization is empirically unstable and can send iterates to infinity even for a two-dimensional quadratic objective.The resulting updates do not yield an established convergence rate; oscillations eventually increase around the minimizer.
  • Rate-matching discretization: Nesterov’s three-sequence construction provides a rate-matching discretization, replacing the naive scheme with a sequence y_k and a generalized estimate-sequence proof.The sufficient condition on y_k enables the accelerated convergence guarantee without assumptions on f beyond those needed to construct that sequence.
  • Rate-matching discretization: Under uniform convexity of h and the stated construction conditions, the discrete algorithm achieves O(1/(εk^p)), matching the continuous-time O(1/t^p) rate when ε = δ^p.The theorem assumes p ≥ 2, z_0 = x_0, and an upper bound on the constant C.
  • Accelerated higher-order gradient method: The accelerated higher-order method improves on the higher-order gradient method’s O(1/(εk^(p−1))) rate under the same (p − 1)-st order smoothness assumption.The paper interprets the improved rate as acceleration, while noting that this discrete implementation is only one possible discretization of the polynomial flow.

4 Further explorations of the Bregman Lagrangian

The Bregman Lagrangian offers a unified framework for studying acceleration, including exponential-rate families, discrete-time algorithms, and relationships between gradient and Lagrangian flows.

  • Framework: The Bregman Lagrangian unifies accelerated gradient-based algorithms and has mathematical structure that can be studied directly.Its framework connects continuous-time dynamics with discrete-time methods.
  • Hessian vs. Bregman Lagrangian: Bregman divergence enables convergence guarantees where a Hessian-based non-Euclidean kinetic energy is unsatisfying.The resulting discrete-time method uses only the gradient of h through weighted mirror descent.
  • Gradient vs. Lagrangian flows: Second-order Bregman Lagrangian flows include natural and rescaled first-order gradient flows as strong-friction limits.Gradient-flow dynamics correspond to the high-friction regime, while reducing friction permits second-order motion.
  • Bregman Hamiltonian: The Bregman Hamiltonian measures kinetic energy using the Bregman divergence of the convex dual h∗ and combines it with potential energy.The Hamiltonian is the Legendre conjugate of the Lagrangian.
  • Gauge invariance: Gauge invariance permits replacing the Bregman divergence term with its first term under the ideal scaling condition.This offers an alternative perspective on the role of h in the Lagrangian.
  • Exponential convergence: Uniformly convex objectives yield exponential convergence for the higher-order gradient algorithm, while restarting the accelerated method improves condition-number dependence.The restart result generalizes Nesterov’s restart scheme for p = 3.
  • Open question: The connection between discrete-time restart algorithms and continuous-time exponential Lagrangian flows remains open.It is also unresolved whether restarting is necessary for exponential discrete-time convergence in general.

5 Discussion

The discussion presents acceleration as arising primarily from mirror-descent coupling within the Bregman-Lagrangian framework, while identifying several unresolved theoretical and extension questions.

  • Core interpretation: Bregman-Lagrangian dynamics are related by time dilation and produce accelerated algorithms by coupling a base method with weighted mirror descent.The framework includes higher-order gradient methods as possible base algorithms.
  • Core interpretation: The mirror-descent coupling, rather than the base algorithm, is identified as more important for the acceleration phenomenon.Higher-order gradient updates operate on a smaller timescale and vanish in the continuous-time limit.
  • Open questions: For p = 2, discrete- and continuous-time convergence assumptions match, unlike the differing assumptions described for general p.This suggests a stronger link between the two dynamics in the special case p = 2.
  • Open questions: The framework’s extensions to stochastic settings, preservation of desirable properties during discretization, and convergence of iterates remain open questions.The paper focuses on convergence rates of function values rather than iterates.
  • Future directions: The origins of the Bregman Lagrangian and other families with similarly favorable properties require further study.The paper also points to Hamiltonian properties such as phase-space volume preservation as possible discretization aids.

A.1 Proof of Theorem 2.2

The proof establishes time-dilation invariance by reparameterizing Euler-Lagrange curves and proves global well-posedness for the associated first-order system under regularity assumptions.

  • Time reparameterization: Reparameterizing an Euler-Lagrange curve changes its velocity and acceleration according to the time map.These relations are then inverted for the proof.
  • Time reparameterization: Substituting the reparameterized derivatives into the original Euler-Lagrange equation produces modified Bregman-Lagrangian parameters.Multiplication by the squared time-map derivative and collecting terms yields the transformed equation.
  • Time reparameterization: The transformed equation is recognized as the Euler-Lagrange equation for another Bregman Lagrangian satisfying the ideal scaling condition.The converse follows by applying the inverse time reparameterization.
  • Existence and uniqueness: Writing the second-order dynamics as first-order equations and setting W_t = ∇h(Z_t) yields a system involving the Legendre conjugate h∗.Under essential smoothness, ∇h and ∇h∗ are inverses.
  • Existence and uniqueness: Lipschitz continuity of ∇f and ∇h∗ gives a unique maximal solution, while a non-increasing energy prevents finite-time blow-up.The maximal interval can therefore be extended to all positive time.
  • Initial time: For p = 2, a regularized p/t coefficient supports unique solutions from t = 0 with zero initial velocity.The construction uses p/max{t, δ} and then lets δ approach zero.

A.3 Proof of Theorem 3.1

The proof of Theorem 3.1 uses an estimate sequence whose minimizer satisfies an inductive lower bound, then converts that bound into the stated convergence rate.

  • Estimate sequence: The estimate function ψ_k is the objective optimized by the sequence z_k in the algorithm’s update.Unrolling the recursion shows that z_k minimizes ψ_k.
  • Inductive argument: The convergence proof proceeds by induction on k, beginning with a zero-valued base case.The inductive step establishes the estimate-sequence inequality at k + 1.
  • Uniform convexity: Uniform convexity of h makes the rescaled Bregman divergence and estimate function uniformly convex of order p.This property supports the minimizer-based lower bound used in the proof.
  • Inductive step: Convexity of f and the definition of x_{k+1} as a convex combination produce the inductive inequality’s main terms.The proof then handles the remaining terms separately.
  • Inductive step: Applying the algorithmic inequality and Fenchel-Young inequality shows the remaining terms are nonnegative under the stated bound on C.This completes the inductive estimate ψ_{k+1}(x) ≥ C(k + 1)^p f(y_{k+1}).
  • Conclusion: Combining the estimate-sequence bound with convexity and rearranging yields the convergence rate in (3.9).The argument evaluates the bound at the minimizer x∗ of f.

A.4 Proof of Lemma 3.2

The proof derives the key inequality for higher-order gradient updates by combining Taylor smoothness, optimality, norm inequalities, and a convex minimization argument.

  • Taylor smoothness bounds the error in the (p −2)-nd order expansion of ∇f under the Lipschitz assumption on ∇p−1f.
  • The proof combines the resulting expansion with squared norm inequalities and rearranges terms into a bound involving A/r^(p−2) + Br^p.
  • Cauchy–Schwarz and the triangle inequality convert the intermediate bound into the two inequalities stated in (3.13).
  • Taking the (p −1)-st root of the rearranged inequality yields the desired result (3.13).

A.5 Proof of Theorem 3.3

The proof establishes descent and bounds the residual decrease for the higher-order gradient algorithm, then telescopes these inequalities to obtain Theorem 3.3's convergence rate.

  • The higher-order smoothness assumption and Taylor remainder theorem provide the function-value bound used to analyze the update.
  • The update is a descent method, so f(xk+1) ≤ f(xk) and all iterates remain within the initial level set's radius R around x∗.
  • Applying convexity to an interpolated point xλ and optimizing a convex expression in λ yields the residual inequality needed for the convergence proof.
  • The residual decrease is lower-bounded using Lemma A.2; summing and telescoping the resulting relation gives the stated conclusion (3.15).

A.6 Proof of Theorem 3.4

The proof identifies the continuous-time limit of the higher-order gradient algorithm as rescaled gradient flow and proves matching convergence through an energy functional.

  • A.6 Proof of Theorem 3.4: Scaling the discrete time step as δ^(p−1) = ǫ makes the discrete update converge to a continuous-time optimality condition.
  • A.6 Proof of Theorem 3.4: The limiting optimality condition implies ∥∇f(Xt)∥∗ = ∥Ẋt∥^(p−1), yielding the rescaled gradient flow equation (3.16).
  • A.6 Proof of Theorem 3.4: An energy functional shared with the discrete-time proof has a derivative that can be bounded using convexity, Cauchy–Schwarz, and the level-set radius R.
  • A.6 Proof of Theorem 3.4: The energy increases at least linearly, which yields the continuous-time convergence rate; an alternative energy functional gives the same bound.
  • A.6 Proof of Theorem 3.4: For f(x) = (1/p)∥x∥^p, the rescaled flow becomes independent of p and has explicit solution Xt = e^(−t)X0.
  • B.1 Exponential convergence: The exponential Lagrangian flow has rate O(e^(−ct)) but is harder to discretize, requiring constant progress per iteration to match the continuous rate.

B.1.1 Exponential convergence rate of higher-order gradient algorithm

Under uniform convexity, the higher-order gradient algorithm achieves exponential convergence, while the corresponding continuous-time rate depends on fewer smoothness parameters.

  • The section extends exponential convergence results to the p-th order gradient algorithm for uniformly convex objectives of order p ≥2.
  • Theorem B.1 assumes (p−1)!/ǫ-smoothness of order p−1 and σ-uniform convexity of order p for the discrete algorithm.
  • The theorem's convergence rate is obtained by combining the higher-order descent inequality with convexity, uniform convexity, and the inverse condition number κ = ǫσ.
  • The continuous-time rescaled gradient flow also converges exponentially under uniform convexity.
  • The continuous-time rate depends only on the uniform convexity constant, whereas the discrete-time rate additionally depends on higher-order smoothness.

B.1.2 Exponential convergence rate of accelerated method with restart scheme

The restart variant of the accelerated gradient method attains exponential convergence, with better dependence on the inverse condition number than the higher-order gradient method. The section also contrasts Bregman and Hessian formulations in non-Euclidean optimization.

  • The restart variant of the accelerated gradient method attains an exponential convergence rate.Running blocks of the accelerated method reduces the distance to the optimum by at least a factor of 1/e, which yields the exponential bound.
  • The restart scheme repeatedly runs the accelerated method for a fixed number of iterations before restarting from its output.The scheme uses blocks of m iterations, with m = 8p/κ.
  • The resulting convergence rate has better dependence on the inverse condition number κ than the higher-order gradient algorithm.
  • B.2 Hessian vs. Bregman Lagrangian: A Hessian-metric generalization is difficult to analyze and implement because its Euler-Lagrange equation contains the third-order derivative ∇3h.The Bregman formulation instead uses Bregman divergence and yields a discretization requiring only ∇h, not ∇2h.

B.3 Gradient vs. Lagrangian flows

The paper interprets gradient and accelerated dynamics as limits and reparameterizations of Lagrangian systems. This connects first-order flows, natural gradient flow, and accelerated motion through mass, momentum, and time-scaling perspectives.

  • Gradient flow emerges as the massless limit of a damped Lagrangian system, while the same limiting framework extends to natural and rescaled gradient flows.The mass parameter is m = 1/λ, and taking m → 0 recovers gradient flow from the damped dynamics.
  • As m → 0, the momentum variable diverges, so gradient flow corresponds to an infinitely massive, strongly damped particle that stops without oscillation.
  • The Bregman Lagrangian yields natural gradient flow for parameters αt = −log m, βt = log m, and γt = t/m.
  • B.4 Bregman Hamiltonian: The Bregman Hamiltonian expresses dynamics using momentum and combines kinetic and potential energy, with a kinetic term differing from the Lagrangian's form.
  • B.7 The Euclidean case: For the Euclidean family, choosing larger βt when r > 3 improves the rate from O(1/t^2) to O(1/t^(r−1)).
Loading 1603.04245v1…