Practical perspectives on symplectic accelerated optimization

Valentin Duruisseaux, Melvin Leok

TL;DR

This paper bridges the gap between the elegant theory of symplectic geometry and the messy reality of machine learning optimization. By introducing momentum restarting and a "temporal looping" strategy, the authors transform highly oscillatory and numerically unstable symplectic integrators into robust, high-performance algorithms that rival industry standards like Adam.

What Problem Does This Paper Address?

The field of "symplectic optimization" recently emerged as a way to understand acceleration (like Nesterov’s method) through the lens of physics. By viewing optimization as the simulation of a physical system—specifically a Bregman Lagrangian or Hamiltonian system—researchers can use "symplectic integrators" to preserve the underlying geometry of the problem.

However, a major gap remained: these theoretical systems are notoriously difficult to use in practice. They suffer from extreme oscillations (overshooting the minimum), require tedious parameter tuning, and can become numerically unstable because the "time" variable in the simulation grows toward infinity, eventually hitting the limits of floating-point precision. This paper provides the "practical handbook" for making these methods work in the real world.

Methods

The authors evaluate a class of algorithms they call BrAVO (Bregman Accelerated Variational Optimizer). Their approach focuses on three key technical improvements:

  1. Momentum Restarting: To combat the "overshoot" problem common in accelerated methods, they test three restarting schemes: Function (restart if the loss increases), Gradient (restart if moving against the gradient), and Velocity (restart if speed decreases).
  2. Temporal Looping: Because the Hamiltonian formulation treats time as a coordinate that grows linearly, numerical precision eventually fails. The authors introduce a "looping" mechanism that resets the time variable without losing the accumulated momentum, ensuring long-term stability.
  3. Integrator Comparison: They benchmark four different geometric integrators: Hamiltonian Taylor Variational Integrator (HTVI), Lagrangian Taylor Variational Integrator (LTVI), Störmer-Verlet (SV), and Symmetric Leapfrog Composition (SLC).

Crucially, they discover that while previous research emphasized "time-adaptivity" (variable time-steps), the use of momentum restarting actually makes constant time-steps perfectly viable, significantly simplifying the algorithms.

Datasets

The authors didn't just stick to toy math problems; they tested their algorithms on a wide array of benchmarks:

  • Synthetic Convex Problems: Quartic polynomials, negative entropy, and ill-conditioned functions.
  • Standard ML Benchmarks: Fashion-MNIST and CIFAR-10 for image classification.
  • Natural Language Processing: Multi-label text classification of arXiv paper abstracts.
  • Timeseries & Dynamics: Weather prediction (LSTM) and learning pendulum dynamics (Hamiltonian Neural ODEs) using data from OpenAI Gym.

Key Insights and Ideas

  • Restarting is the Great Equalizer: The most striking finding is that momentum restarting (specifically the Gradient Scheme) makes the algorithms incredibly robust. It expands the "safe zone" for parameters like the time-step ($h$) and the scaling constant ($C$), making the algorithms much easier to tune.
  • Adaptivity is Overrated: In the presence of restarting, the complex math required for time-adaptive integrators becomes "futile." This is a win for practitioners, as it allows for simpler, faster code.
  • The "Time Explosion" Fix: The "Temporal Looping" idea is a clever fix for a purely numerical issue. By resetting the internal clock of the simulation, they prevent the exponential growth of terms that would otherwise lead to "NaN" errors or divergence after convergence is initially reached.
  • SLC is the Top Performer: Among the integrators tested, the Symmetric Leapfrog Composition (SLC) emerged as the most efficient and stable choice for integrating these specific accelerated flows.

Key Results

  • Massive Speedups: On certain ill-conditioned problems, restarting reduced the number of iterations required for convergence from over 15,000 down to just 51.
  • Competitive with Adam: In deep learning tasks like Fashion-MNIST and CIFAR-10, the BrAVO algorithms achieved accuracy and loss curves comparable to Adam and SGD, proving that geometric integrators are viable for high-dimensional neural network training.
  • Stability: While standard symplectic methods eventually "blow up" due to numerical precision issues, the version with Temporal Looping remained stable at the minimum for thousands of additional iterations.

Limitations and Future Work

The authors acknowledge a few hurdles remaining for widespread adoption:

  • Theoretical Gaps: While the continuous versions of these flows have proven convergence rates, proving the same for the discrete, restarted algorithms is mathematically very difficult because they are no longer monotonic.
  • Implementation Maturity: The current Python/PyTorch implementation is described as "rudimentary." To truly beat Adam in wall-clock time, the code needs to be more deeply optimized for GPU/TPU hardware.
  • Manifold Extension: While this paper focuses on Euclidean space, the authors suggest that extending these practical tricks to Riemannian manifolds is a promising next step for optimizing over more complex geometric spaces.

Summary updated

Abstract

Geometric numerical integration has recently been exploited to design symplectic accelerated optimization algorithms by simulating the Lagrangian and Hamiltonian systems from the variational framework introduced in Wibisono et al. In this paper, we discuss practical considerations which can significantly boost the computational performance of these optimization algorithms, and considerably simplify the tuning process. In particular, we investigate how momentum restarting schemes ameliorate computational efficiency and robustness by reducing the undesirable effect of oscillations, and ease the tuning process by making time-adaptivity superfluous. We also discuss how temporal looping helps avoiding instability issues caused by numerical precision, without harming the computational efficiency of the algorithms. Finally, we compare the efficiency and robustness of different geometric integration techniques, and study the effects of the different parameters in the algorithms to inform and simplify tuning in practice. From this paper emerge symplectic accelerated optimization algorithms whose computational efficiency, stability and robustness have been improved, and which are now much simpler to use and tune for practical applications.
BibTeX
@article{duruisseaux2023practical,
  author = {Valentin Duruisseaux and Melvin Leok},
  title = {{Practical perspectives on symplectic accelerated optimization}},
  journal = {Optim. Methods Softw},
  year = {2023},
  doi = {10.1080/10556788.2023.2214837},
}

Loading related content...

Figure