The Physical Systems Behind Optimization Algorithms

Lin Yang, Raman Arora, Vladimir Braverman, Tuo ZhaoNeurIPS 2018 · OpenReview

Introduction

This paper bridges the gap between optimization theory and classical mechanics by demonstrating that popular machine learning algorithms—like Gradient Descent and Nesterov’s Acceleration—are fundamentally discrete simulations of damped physical oscillators. By viewing optimization through the intuitive lens of particle mass, friction, and restoring forces, the authors provide a unified physical framework that explains why certain algorithms converge faster than others.

The Problem: Mysterious Algebraic Tricks

In machine learning, optimization algorithms such as Vanilla Gradient Descent (VGD) or Nesterov’s Accelerated Gradient (NAG) are standard tools for minimizing loss functions. While rigorous mathematical proofs exist for their convergence rates, these proofs often rely on opaque "algebraic tricks" that offer little intuitive understanding.

For instance, it has long been unclear why adding a momentum term (as in Nesterov’s method) naturally leads to faster convergence. Furthermore, previous continuous-time analyses using differential equations have been fragmented. They often treated different algorithms as unrelated phenomena and struggled to account for randomized methods (like Coordinate Descent) or second-order methods (like Newton’s method) under a single umbrella.

Methods: The Continuous-Time Approximation

To solve this, the authors employ a continuous-time approximation strategy. They treat the discrete steps of an optimization algorithm as snapshots of a continuous physical trajectory. By taking the limit as the step size approaches zero, they derive an Ordinary Differential Equation (ODE) that governs the algorithm's "motion":

$$m\ddot{X}(t) + c\dot{X}(t) + \nabla f(X(t)) = 0$$

A physical system of a mass on a spring submerged in a fluid, illustrating the restoring force (Hooke's law) and damping coefficient.

In this physical framework:

  • $f(x)$ represents the potential energy (the loss function to be minimized).
  • $m$ represents the particle mass (inertia).
  • $c$ represents the damping coefficient (friction or viscosity, as seen in the fluid of the figure above).
  • $\nabla f(X)$ is the restoration force pulling the particle toward the minimum equilibrium.

Using this single physical model, the authors analyze VGD, NAG, Randomized Coordinate Gradient Descent (RCGD), and Newton’s method.

Key Insights and Ideas

By mapping algorithms to physical properties, several intuitive insights emerge:

  • VGD is Massless: Vanilla Gradient Descent corresponds to a "massless" particle system ($m=0$). Because it lacks inertia, it stops immediately when the force (gradient) stops and cannot accelerate. It behaves like an extremely over-damped system.
  • NAG is Massive: Nesterov’s Acceleration corresponds to a "massive" particle. The momentum term acts as literal physical inertia, allowing the particle to maintain speed even when the gradient is weak.
  • Acceleration = Critical Damping: In physics, a "critically damped" system returns to equilibrium as fast as possible without oscillating wildly. The authors prove that Nesterov’s acceleration is mathematically equivalent to tuning a physical system to this optimal critical damping point.
  • The PŁ Condition is Hooke’s Law: The Polyak-Łojasiewicz (PŁ) condition—a mathematical relaxation of convexity—is shown to be the algorithmic equivalent of Hooke’s Law for springs ($F = kx$). It guarantees that the restoration force is always strong enough to pull the particle back to the center, explaining why linear convergence is possible even for certain non-convex functions.
  • Newton’s Method as Anisotropic Fluid: Newton’s method is interpreted as a particle moving through a "viscosity tensor field," where friction varies depending on the direction the particle is moving, effectively normalizing the curvature of the space.

Key Results

Comparison of the proposed unified physical framework against prior works across various algorithms and conditions.

The authors successfully recover state-of-the-art convergence rates for all studied algorithms using Lyapunov functions derived directly from physical energy equations.

Crucially, their analysis extends well beyond simple convex functions. As shown in the comparison table above, their unified framework applies to strongly convex functions, proximal variants, and functions satisfying the PŁ condition, matching the best-known theoretical bounds. Additionally, they prove that Randomized Coordinate Gradient Descent (RCGD) weakly converges to the same ODE as VGD, providing a theoretical justification for why their convergence rates are so similar despite vastly different update rules.

Limitations and Future Work

While powerful, this physical lens has a few limitations:

  • The "Small Step" Assumption: The ODE approach assumes infinitesimal step sizes. In practice, ML practitioners use the largest step size possible to speed up training, which continuous models can struggle to perfectly capture.
  • Newton’s Method Local Analysis: The physical framework only justifies the local linear convergence of Newton’s method. It fails to capture the extremely rapid "quadratic convergence" that occurs very close to the minimum, as that behavior relies on the discrete nature of large steps smoothed out by the ODE.
  • Stochastic Noise: The paper touches on randomized coordinate descent but does not deeply explore the "thermal noise" or stochasticity inherent in Stochastic Gradient Descent (SGD). Future work could model this using a Langevin equation to capture the chaotic dynamics of modern deep learning.

Summary updated

Abstract

We use differential equations based approaches to provide some {\it \textbf{physics}} insights into analyzing the dynamics of popular optimization algorithms in machine learning. In particular, we study gradient descent, proximal gradient descent, coordinate gradient descent, proximal coordinate gradient, and Newton's methods as well as their Nesterov's accelerated variants in a unified framework motivated by a natural connection of optimization algorithms to physical systems. Our analysis is applicable to more general algorithms and optimization problems {\it \textbf{beyond}} convexity and strong convexity, e.g. Polyak-\L ojasiewicz and error bound conditions (possibly nonconvex).
BibTeX
@inproceedings{yang2018physical,
  author = {Lin Yang and Raman Arora and Vladimir Braverman and Tuo Zhao},
  title = {{The Physical Systems Behind Optimization Algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=SJbhpPWObB},
}
Figure