Convergence-Rate-Matching Discretization of Accelerated Optimization Flows Through Opportunistic State-Triggered Control

Miguel Vaquero, Jorge CortésNeurIPS 2019 · OpenReview

Introduction

A recent body of exciting work seeks to shed light on the behavior of accelerated methods in optimization via high-resolution differential equations. These differential equations act as continuous counterparts to discrete-time optimization algorithms, allowing their convergence properties to be characterized using powerful tools from classical Lyapunov stability analysis.

However, an outstanding question of pivotal importance remains: how do we discretize these continuous flows while maintaining their fast convergence rates? This paper introduces a principled approach using opportunistic state-triggered control. By treating the optimization algorithm as a control system, the authors develop a variable-stepsize algorithm that ensures the discrete steps always respect the "energy decay" (Lyapunov stability) of the original continuous-time flow.

The Discretization Challenge

In recent years, researchers have increasingly analyzed accelerated optimization algorithms—which converge faster than standard gradient descent—as continuous-time differential equations. While these "flows" are mathematically elegant and easier to analyze using physics and control theory, they must eventually be converted back into discrete computer algorithms to be practically useful.

The core problem is that standard discretization methods, such as the Forward Euler scheme, are often brittle. If the chosen stepsize is too large, the algorithm becomes unstable and diverges. Conversely, if the stepsize is too small, the algorithm loses the very speed advantage that acceleration was supposed to provide. This paper tackles the challenge of finding a variable stepsize that is as large as possible while mathematically guaranteeing that the algorithm retains the accelerated convergence rate of the continuous model.

Methodology: Bridging Optimization and Control

The authors bridge the gap between optimization and control theory using three main pillars:

  1. High-Resolution ODEs: The study focuses on the "heavy-ball" and Nesterov accelerated models, specifically utilizing high-resolution versions that more accurately capture the nuanced behavior of discrete algorithms.
  2. State-Triggered Control: Instead of taking steps at fixed time intervals, the algorithm uses "triggers" to determine when to update.
  3. Event-Triggered (ET): The algorithm continuously monitors a condition and takes a new step only when the "energy" of the system stops decreasing at the desired rate.
  4. Self-Triggered (ST): The algorithm predicts the next safe time to take a step based solely on the current state. This is more computationally efficient as it removes the need for constant monitoring.
  5. Lyapunov-Based Design: The core innovation is designing the trigger condition based on a Lyapunov function. Because the true Lyapunov function usually requires knowing the optimal solution (the very thing we are trying to find), the authors use mathematical bounds derived from the function's strong convexity and Lipschitz constants to create a practical, computable trigger.
Conceptual diagram of state-triggered control

As illustrated above, the sample-and-hold implementation tracks the continuous flow and triggers a new iteration precisely when the trajectory threatens to violate the guaranteed Lyapunov decay level sets.

Key Insights

  • Optimization as Control: The breakthrough insight is treating an optimization algorithm as a "sample-and-hold" control system. This reframing allows the authors to leverage decades of control theory research to solve optimization stability problems.
  • Variable Stepsize is Not Arbitrary: Unlike heuristic line-searches, the stepsizes generated by this method are derived directly from the strict requirement to match the continuous-time convergence rate.
  • Guaranteed Progress: The authors mathematically prove that their variable stepsize will never shrink to zero—a problematic phenomenon in control theory known as "Zeno behavior." This ensures the algorithm will always make a minimum amount of progress per step.

Experimental Results

The paper evaluates the proposed algorithms on standard optimization benchmarks, including regularized logistic regression (testing strongly convex problems) and ill-conditioned quadratic functions (testing "stretched" geometries where standard methods struggle).

Performance comparison of integrators

The results demonstrate several significant advantages:

  • Faster Convergence: In logistic regression tests, the ET and ST integrators maintained significantly larger stepsizes than standard fixed-step methods (like Forward Euler and Symplectic Euler) for the early iterations, reaching the optimizer much faster.
  • Chasing the Optimal Step: Numerical results show that the event-triggered stepsize naturally "chases" the theoretically optimal stepsize as the algorithm approaches the solution, dynamically adapting to the local landscape of the objective function.
  • Stability and Rate Matching: While standard Forward Euler can become unstable on ill-conditioned problems, the triggered approach remained stable. Crucially, the authors mathematically proved that their discrete algorithm successfully inherits the $O(e^{-\alpha t})$ convergence rate of the continuous heavy-ball ODE.

Limitations and Future Work

While promising, the approach has limitations that pave the way for future research. First, the current trigger designs require prior knowledge of the strong convexity parameter ($\mu$) and the Lipschitz constant ($L$), which can be difficult to estimate in real-world machine learning tasks. Second, the paper currently relies on a Forward Euler (first-order) discretization; combining this triggering logic with higher-order integrators like Runge-Kutta could yield even better performance. Finally, extending this "rate-matching" logic beyond strongly convex functions to general convex or non-convex landscapes (such as those found in deep learning) remains an open and exciting frontier.

Summary updated

Abstract

A recent body of exciting work seeks to shed light on the behavior of accelerated methods in optimization via high-resolution differential equations. These differential equations are continuous counterparts of the discrete-time optimization algorithms, and their convergence properties can be characterized using the powerful tools provided by classical Lyapunov stability analysis. An outstanding question of pivotal importance is how to discretize these continuous flows while maintaining their convergence rates. This paper provides a novel approach through the idea of opportunistic state-triggered control. We take advantage of the Lyapunov functions employed to characterize the rate of convergence of high-resolution differential equations to design variable-stepsize forward-Euler discretizations that preserve the Lyapunov decay of the original dynamics. The philosophy of our approach is not limited to forward-Euler discretizations and may be combined with other integration schemes.
BibTeX
@inproceedings{vaquero2019convergence,
  author = {Miguel Vaquero and Jorge Cortés},
  title = {{Convergence-Rate-Matching Discretization of Accelerated Optimization Flows Through Opportunistic State-Triggered Control}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=gXcktGepa1},
}
Figure