Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization

Peiyuan Zhang, Antonio Orvieto, Hadi Daneshmand, Thomas Hofmann, Roy S. Smith

Introduction

In the quest for faster optimization algorithms, researchers have increasingly turned to continuous-time models. By viewing discrete algorithms like Nesterov’s Accelerated Gradient (NAG) as discretizations of Ordinary Differential Equations (ODEs), we can leverage the rich tools of calculus and dynamical systems to understand and design better optimizers. However, a persistent narrative in this field has been that the choice of numerical integrator is paramount—specifically, that "symplectic" or semi-implicit methods are the only way to preserve the acceleration properties of the underlying continuous flow.

This paper challenges that assumption, demonstrating that the perceived superiority of semi-implicit methods may simply be a consequence of looking at the "wrong" ODEs.

The Problem: Is Symplectic Integration Necessary?

The dominant theory suggested that while a continuous-time ODE might exhibit acceleration, standard Explicit Euler discretization would destroy this property or lead to instability. In contrast, Semi-implicit (symplectic) Euler was thought to be the "secret sauce" that allowed discrete algorithms to inherit the $O((1-\sqrt{\mu/L})^k)$ convergence rates of Nesterov-like flows.

The traditional view: Explicit Euler is often seen as insufficient for acceleration compared to semi-implicit methods.

A Unified Framework: The GM-ODE

To investigate this, the authors introduce the Generalized Momentum ODE (GM-ODE): $$\begin{cases} \dot{X} = -m\nabla f(X) - nV \\ \dot{V} = \nabla f(X) - qV \end{cases}$$ This three-parameter model ($m, n, q$) is highly flexible, encompassing many existing accelerated flows as special cases. By analyzing this system, the authors uncover a fundamental Reparameterization Lemma. They prove that any semi-implicit discretization of a GM-ODE is mathematically equivalent to an explicit discretization of the same ODE structure, just with a different set of parameters.

Key Insights: Debunking the "Symplectic" Myth

The most striking result is that the "acceleration" property is not tied to the integrator alone, but to the combination of the ODE and the integrator. By choosing the right continuous-time flow, even the simple Explicit Euler method can achieve optimal accelerated convergence rates.

The paper's new perspective: Both integrators can achieve acceleration by choosing the appropriate continuous-time flow.

This equivalence unifies a variety of momentum-based methods, including Quasi-Hyperbolic Momentum (QHM). It suggests that the "discretization error" often blamed for the failure of explicit schemes can actually be absorbed into the parameters of the continuous model.

Theoretical and Empirical Results

The authors provide rigorous proofs for these claims:

  1. Lyapunov Analysis: They develop a novel energy function to prove global asymptotic stability in continuous time.
  2. Discrete-Time Convergence: They establish the first general accelerated convergence rates for both Euler schemes. For $\mu$-strongly convex and $L$-smooth functions, both schemes achieve the accelerated rate of $O((1 - \sqrt{\mu/L})^k)$.
  3. Stability Regions: Numerical experiments demonstrate that neither integrator is universally superior. There are regimes where Explicit Euler is stable while Semi-implicit Euler is not, and vice versa, depending on the specific dissipative properties of the system.

The theory was validated on synthetic quadratic problems and regularized logistic regression, confirming that the predicted acceleration occurs in practice even for non-quadratic convex objectives.

Limitations and Future Work

While this work provides a powerful unification, it currently focuses on $\mu$-strongly convex functions. Extending these proofs to general convex or non-convex settings remains an open challenge. Additionally, the analysis is restricted to deterministic gradients and first-order Euler schemes. Exploring stochastic gradients and higher-order integrators (like Runge-Kutta) are promising avenues for future research.

Summary updated

BibTeX
@inproceedings{zhang2021revisiting,
  author = {Peiyuan Zhang and Antonio Orvieto and Hadi Daneshmand and Thomas Hofmann and Roy S. Smith},
  title = {{Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=MFGg8vFLQu},
}
Figure