PaperlayerView exact revision on arXiv

Source-linked AI summary

Variational Structure at the Edge of Stability

Eric Regis

arXiv:2608.21660v1cs.LG

TL;DR

Edge-of-stability optimizers exhibit near-two-periodic oscillations reminiscent of conservative systems, but their connection to discrete mechanics is underexplored. The paper extends edge coupling to heavy-ball and Nesterov momentum, showing that critical points encode fixed points and two-point orbits, Hessians encode stability, and the coupling corresponds to the symmetric Verlet action.

  • Problem

    The precise connection between near-two-periodic optimizer dynamics at the edge of stability and discrete mechanics remains underexplored.

  • Method

    The paper extends Litman’s edge coupling to momentum methods and analyzes its critical points, Hessian, and relation to discrete actions.

  • Results

    The phase-space edge coupling characterizes fixed points and two-point orbits, encodes their stability through its Hessian, and is identified with the symmetric Verlet action.

  • Takeaways & Limitations

    The framework provides a variational account of momentum algorithms’ near-two-periodic behavior at the edge of stability.

  • Takeaways & Limitations

    The edge coupling and symmetric Verlet action share critical positions, but their critical momenta differ by a fixed rescaling; higher-period orbits remain future work.

Abstract

from arXiv · show

When discrete-time optimizers operate at the edge of stability, they exhibit near-two-periodic behavior. These oscillatory dynamics are reminiscent of conservative systems, such as the dynamics generated by symplectic integrators. However, a precise formulation of the connection between discrete-time optimizers at the edge of stability and discrete mechanics remains underexplored. Recently, Litman introduced the "edge coupling": a functional on consecutive gradient descent iterates whose critical points encode the fixed points and two-point orbits of the gradient descent dynamics. Here we extend the edge coupling to heavy-ball and Nesterov momentum. We show that its critical points characterize the fixed points and two-point orbits, with its Hessian characterizing their stability. We also show that the edge coupling can be identified with the symmetric Verlet action, formalizing the connection between the edge of stability and discrete mechanics.

1 Introduction

At the edge of stability, optimizers exhibit near-two-periodic oscillations that resemble conservative dynamics, but this connection remains underdeveloped. The paper extends edge coupling to momentum methods and connects it to discrete mechanics.

  • Motivation: Edge-of-stability iterates oscillate along sharp Hessian directions and nearly return after two updates.These bounces across the valley help explain slow loss decrease despite large update steps.
  • Motivation: The oscillatory behavior suggests a connection between optimizers and conservative systems, but its formalization remains underdeveloped.
  • Contributions: The phase-space edge coupling extends Litman’s functional from gradient descent to heavy-ball momentum.
  • Contributions: Its critical points encode fixed points and two-point orbits, while its Hessian encodes their stability.
  • Contributions: The paper demonstrates that phase-space edge couplings are symmetric Verlet actions for every momentum coefficient β.

2 Related Work

Related work explains edge-of-stability behavior through oscillatory optimization dynamics, consecutive-iterate analyses, and variational or symplectic interpretations. The paper builds on these lines by generalizing Litman’s edge coupling and linking it to discrete mechanics.

  • Edge of stability: Prior work characterizes edge-of-stability dynamics through sharpness thresholds, unstable oscillations, self-stabilization, and averaged central flows.
  • Consecutive iterates: Consecutive-iterate approaches analyze period-2 orbits, rod-flow models, edge flow, and Litman’s edge coupling for gradient descent.
  • Discrete mechanics: Discrete mechanics derives integrators by discretizing action, with Störmer–Verlet as a canonical example and stability analyzed for periodic orbits.
  • Momentum and variational principles: Other work interprets heavy-ball and Nesterov methods through conformal symplectic or symplectic discretizations of dissipative dynamics.

3 The Phase-Space Edge Coupling

The phase-space edge coupling is constructed for momentum dynamics so that its critical points correspond to fixed points and two-period orbits. For heavy-ball momentum, the coupling also reduces on the diagonal to a Lagrangian-like potential-minus-kinetic expression and recovers the gradient-descent coupling when β = 0.

  • Gradient descent: For gradient descent, vanishing derivatives of the edge coupling recover the two update equations, so critical pairs are fixed points or two-period orbits.
  • Gradient descent: The coupling depends on step size for two-period orbits, although gradient-descent fixed points do not.
  • Heavy-ball momentum: For heavy-ball momentum, β ∈ [0, 1], and the phase-space state combines position w with momentum m.
  • Construction: The phase-space edge coupling takes two phase-space points as arguments and is designed to characterize fixed points and two-point orbits.
  • Variational form: On the diagonal, the phase-space coupling becomes a potential-energy term minus a kinetic-energy term, forming a Lagrangian up to scale.
  • Heavy-ball momentum: The heavy-ball coupling’s critical conditions recover the position and momentum updates, yielding fixed points or nontrivial two-period orbits.
  • Position-space reduction: Eliminating momentum produces a position-space coupling whose critical points correspond to position pairs extendable to two-period momentum orbits, recovering Litman’s coupling at β = 0.
  • Nesterov momentum: Nesterov momentum also admits a phase-space coupling, while the paper presents the main development using heavy-ball momentum.

4 Coordinate Transformations

The edge coupling preserves its critical points under smooth invertible coordinate changes. Centered coordinates expose conditions characterizing two-point orbits, including zero mean-momentum for β > 0.

  • Invariance of Critical Points: Smooth invertible coordinate changes preserve the edge coupling’s critical points bijectively.The gradient transforms by the chain rule, and invertibility of the coordinate Jacobian preserves criticality.
  • Centered Coordinates: Centered coordinates represent the doubled phase space using a midpoint and half-displacement between the two points.The phase-space variables are recast through midpoint and displacement coordinates before deriving criticality conditions.
  • Criticality Conditions: For β > 0, criticality forces the mean momentum of every two-point orbit to equal zero.The momentum criticality condition is equivalent to ηm′ = w′ − w.
  • Position-Space Reduction: Reducing the phase-space coupling to position space recovers Litman’s edge coupling in centered coordinates.The position-space formulation retains the correspondence between critical points and two-point-orbit structure.
  • Criticality Conditions: The midpoint condition requires the gradients at the two orbit points to sum to zero.This means the average gradient along a two-point orbit vanishes.

5 Stability and the Hessian

The phase-space edge coupling encodes heavy-ball fixed points and two-point orbits through critical points, while its Hessian captures their stability. Determinant and inertia identities connect this Hessian to the two-step dynamics and are invariant under coordinate changes.

  • Two-Step Dynamics: Critical points of the phase-space edge coupling correspond to fixed points and two-point orbits of heavy-ball dynamics.These orbits are exactly the fixed points of the two-step update map T2.
  • Linear Stability: The two-period orbit is linearly stable when every eigenvalue of the two-step Jacobian lies inside the unit circle.The Jacobians evaluated at the two orbit points are conjugate and therefore have the same spectrum.
  • Linear Stability: The phase-space and position-space stability problems are equivalent through linear and quadratic matrix pencils.Their determinants agree for every λ, allowing momentum variables to be eliminated without changing the eigenvalue problem.
  • Hessian Structure: The Hessian admits a block LDL factorization whose congruence preserves its determinant and inertia.The Schur complement isolates the orbit-dependent block, while the fixed momentum block contributes inertia (d, d, 0) when ηβ ≠ 0.
  • Determinant: A determinant sign flip detects the period-doubling transition but not later transitions to higher-period orbits.Higher-period transitions can occur when an eigenvalue exits the unit circle at complex or negative real values.
  • Coordinate Invariance: The Hessian’s inertia and determinant sign are intrinsic to the orbit and independent of the coordinate choice.Coordinate changes preserve inertia and modify determinants only by the positive factor (det DU−1)^2.
  • Inertia: Every linearly stable two-point orbit yields a perfectly balanced Hessian saddle with inertia (2d, 2d, 0).For stable orbits, the Schur complement has inertia (d, d, 0), which determines the full Hessian inertia.

6 The Störmer–Verlet Action

Discretizing the action with the trapezoidal potential rule produces the Störmer–Verlet integrator. The edge coupling coincides with the corresponding two-period action up to scaling, while the phase-space version retains residual terms and rescaled critical momenta.

  • Recap of Discrete Mechanics: Discrete mechanics derives integrators by discretizing the action rather than the equations of motion.The discrete action is formed from a finite-difference velocity and trapezoidal potential approximation.
  • The Störmer–Verlet Integrator: Stationarity of the discrete action with respect to interior points yields the Störmer–Verlet, or leapfrog, scheme.The discrete Hamilton principle produces the update equations for the canonical variational integrator.
  • The Störmer–Verlet Integrator: Setting Δt = √η recovers heavy-ball dynamics with β = 1.This identifies a specific heavy-ball parameterization with the leapfrog time discretization.
  • Two-Period Action: For a period-two leapfrog orbit, the full discrete action decomposes into repeated two-step action blocks.Stationarity of the whole trajectory is equivalent to stationarity of the two-period action with respect to both orbit points.
  • Position-Space Edge Coupling: The position-space edge coupling and two-period action have identical critical points up to an overall factor.Thus heavy-ball two-period orbits coincide with leapfrog two-period orbits at the corresponding step size.
  • The Phase-Space Action: The phase-space action is constructed by summing two consecutive discrete phase-space Lagrangians.Its variational formulation treats position and momentum through a Hamilton–Pontryagin discretization.
  • The Phase-Space Action: The phase-space edge coupling shares critical positions with the action, but its critical momenta differ by a fixed rescaling.Residual terms remain in the functional identity because the momenta are not identical variables in the two formulations.

7 Conclusion

The paper presents a variational framework for understanding momentum algorithms at the edge of stability and relates it to near-two-periodic behavior. It identifies higher-period orbit analysis as a natural next step.

  • The paper presents a variational framework for understanding momentum algorithms at the edge of stability.
  • The framework is intended to shed light on the near-two-periodic behavior observed at the edge of stability.
  • Future work: A natural next step is developing a variational account of higher-period orbits.

A.1 The Quadratic Loss

For the quadratic loss, the edge-coupling criticality conditions reduce to linear algebra involving the Hessian and a matrix A. Two-period orbits arise at the heavy-ball sharpness threshold but are only marginally stable.

  • When A is non-singular, the only valid critical point is the origin, representing a fixed point rather than a two-point orbit.
  • Non-trivial two-period orbits require A to be singular, with det A = 0 reducing to Hessian conditions.
  • A zero Hessian eigenvalue yields a line of fixed points because the gradient vanishes along its eigenvector.
  • The condition det(H − 2κId) = 0 corresponds to the heavy-ball sharpness threshold.
  • The quadratic loss has no stable two-period orbits; at best, they are marginally stable, with perturbations persisting without growth or decay.
  • Centered coordinates: In centered coordinates, the condition w̄ = 0 and (H − 2κId)δ = 0 characterizes a fixed point or two-period orbit.

A.2 The Quartic Loss

For the quartic loss, nonlinear terms allow isolated nondegenerate critical points and generate antipodal two-period orbits after a Hessian eigenvalue crosses the threshold 2κ. Stable two-period orbits have a min–max structure.

  • Unlike the quadratic case, quartic nonlinearities can balance the linear part, producing isolated and nondegenerate nonzero critical points.
  • The centered quartic edge coupling contains a cross term that couples the midpoint w̄ and half-difference δ.
  • When λmax(H) < 2κ, the quartic analysis yields no nonzero two-point orbits under the stated positivity assumption on Q.
  • As a simple Hessian eigenvalue crosses 2κ, a supercritical branch of antipodal orbits emerges from the origin.
  • Stability: Stable two-period orbits are minima in the midpoint w̄ and maxima in the half-difference δ of the centered edge coupling.
  • Nesterov momentum: The appendix collects Nesterov analogues, including look-ahead coordinates and a phase-space edge coupling whose determinant analysis uses the two-step Jacobian.

C Deferred Proofs

This section states that it will prove key assertions made throughout the paper.

  • The section provides proofs of key assertions made throughout the paper.

C.1 Equivalence of the Phase-Space and Position-Space Pencils

The phase-space eigenvalue problem for the two-step Jacobian can be reduced to a position-space equation governed by W. The corresponding pencil determinants agree for every λ, and the phase-space and position-space critical conditions coincide in position variables while momentum coordinates differ by a fixed scaling.

  • Eigenvalue reduction: The resulting position-space equation is precisely the eigenvalue equation governed by the quadratic pencil W.This identifies the reduced phase-space eigenproblem with the position-space formulation.
  • Eigenvalue reduction: Eliminating the momentum variables from the eigenvalue equations yields the position-only system (λ + β)y = λA_wx and (λ + β)x = A_w′y.The reduction starts from the two half-period Jacobian maps and expresses both momenta in terms of the positions.
  • Determinant identity: The determinants of the phase-space pencil P and position-space pencil S agree for every λ, not only at their zeros.The proof uses determinant-preserving row operations, commuting block determinants, cancellation of cross terms, and transpose-related products.
  • Determinant identity: The two-period Jacobian is formed as M = J(H_w′)J(H_w), whose eigenvector relations provide the starting point for the position-space reduction.Writing ξ = (x,p), ζ = (y,q), and J(H_w′)ζ = λξ gives the two half-period component equations used in the elimination.
  • Critical points: The phase-space edge coupling and symmetric Verlet action impose identical critical-position equations, so their critical positions coincide.Both functionals yield the same conditions on (w,w′), including the relations in Equation (119).
  • Critical points: Their critical momenta differ only by a constant scaling: the action uses (w − w′)/∆t, whereas the edge coupling uses (w − w′)/η.The action momenta are obtained from the edge-coupling momenta by the fixed factor η/∆t.
Loading 2608.21660v1…