Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization

Jingzhao Zhang, Suvrit Sra, Ali Jadbabaie

Abstract

We study gradient-based optimization methods obtained by direct Runge-Kutta discretization of the ordinary differential equation (ODE) describing the movement of a heavy-ball under constant friction coefficient. When the function is high order smooth and strongly convex, we show that directly simulating the ODE with known numerical integrators achieve acceleration in a nontrivial neighborhood of the optimal solution. In particular, the neighborhood can grow larger as the condition number of the function increases. Furthermore, our results also hold for nonconvex but quasi-strongly convex objectives. We provide numerical experiments that verify the theoretical rates predicted by our results.

Introduction

In first-order optimization, Gradient Descent (GD) is the standard workhorse, but it is often slow for "ill-conditioned" problems where the function is much steeper in some directions than others. Nesterov’s Accelerated Gradient (NAG) is famously faster, but its derivation is often considered "mysterious" and unintuitive. This research demonstrates that "acceleration" in optimization isn't just an algebraic trick—it can be systematically derived by discretizing the physical "heavy-ball" differential equation using high-order numerical integrators. By using Runge-Kutta methods, the authors achieve accelerated convergence rates for quasi-strongly convex functions, showing that the better we simulate the underlying physics, the faster we can optimize.

Methods: From Physics to Algorithms

The core idea is to start with the Heavy-Ball ODE: $$\ddot{x}(t) + 2\dot{x}(t) + \frac{\nabla f(x)}{\mu} = 0$$ This equation describes a ball with mass moving through a landscape $f(x)$ with a friction coefficient. To transform this continuous physical model into a discrete optimization algorithm, the authors employ three key steps:

  1. Variable Rescaling: A change of variables balances the "speed" of position and velocity coordinates, which is crucial for numerical stability when handling high condition numbers ($L/\mu$).
  2. High-Order Runge-Kutta (RK) Discretization: Instead of a simple Euler step (which leads to standard GD), the authors use explicit RK integrators of order $s$. These methods use multiple gradient evaluations per step to match the Taylor expansion of the ODE more accurately. The complexity of these integrators can be represented using Butcher trees.
  3. Lyapunov Analysis: Convergence is proven using a Lyapunov function (an energy-like function) that decreases over time, ensuring discretization errors do not destroy the physical acceleration of the system.
Butcher trees representing the structure of high-order Runge-Kutta integrators used for discretization.

Key Insights

  • Physics as a Blueprint: Acceleration is a natural property of the heavy-ball physical system. The "mystery" of acceleration in discrete algorithms is often just the result of a low-order discretization of that physical system.
  • The Smoothness Payoff: If a function is "high-order smooth" (bounded high-order derivatives), higher-order RK methods allow for much larger stable steps, leading to faster convergence.
  • Expanding Neighborhoods: Unlike many "local" convergence results, the region where this acceleration occurs actually grows larger as the problem becomes more ill-conditioned.
  • Beyond Convexity: The results hold for quasi-strongly convex functions, which behave like strongly convex functions relative to the optimal point but may not be convex everywhere.

Empirical Results

The authors evaluated their "Direct Discretization" (DD) algorithms on synthetic quadratic problems and regularized logistic regression. The experiments confirmed that the algorithm achieves a convergence rate approaching the theoretical lower bound $O(\sqrt{L/\mu} \log(1/\epsilon))$ as the order of the integrator $s$ increases.

Empirical convergence comparison showing that higher-order Direct Discretization (DD s=4) matches or exceeds the performance of Nesterov’s Accelerated Gradient (NAG).

As shown in the figure above, the DD method with order $s=4$ significantly outperformed lower-order versions ($s=1$ or $s=2$) and standard Gradient Descent. While $s=4$ requires four gradient evaluations per step, this is offset by the ability to take significantly larger and more effective steps toward the optimum.

Limitations and Future Work

While the results are promising, some challenges remain. The proof is technically local, though the neighborhood of acceleration is large. It remains an open question whether this approach can provide global acceleration for all convex functions without prior knowledge of NAG. Additionally, higher-order RK methods introduce computational overhead per iteration, and the theory relies on bounded high-order derivatives, which may not hold for objectives using non-smooth activations like ReLU.

Summary updated

Abstract

We study gradient-based optimization methods obtained by direct Runge-Kutta discretization of the ordinary differential equation (ODE) describing the movement of a heavy-ball under constant friction coefficient. When the function is high order smooth and strongly convex, we show that directly simulating the ODE with known numerical integrators achieve acceleration in a nontrivial neighborhood of the optimal solution. In particular, the neighborhood can grow larger as the condition number of the function increases. Furthermore, our results also hold for nonconvex but quasi-strongly convex objectives. We provide numerical experiments that verify the theoretical rates predicted by our results.
BibTeX
@inproceedings{zhang2019acceleration,
  author = {Jingzhao Zhang and Suvrit Sra and Ali Jadbabaie},
  title = {{Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization}},
  booktitle = {CDC},
  year = {2019},
  url = {https://openreview.net/forum?id=4SJt7VLuYoP},
}
Figure