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:
- 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$).
- 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.
- 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.
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.
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