In classical optimization, proving that an algorithm works usually involves showing "sufficient descent": demonstrating that the objective function $f(x)$ decreases at every single step. However, for modern algorithms like Nesterov’s acceleration, Adam, or Heavy-ball momentum, this simple monotonic decrease often doesn't happen. The iterates might "overshoot" or oscillate, causing the objective value to temporarily rise even as the algorithm moves toward the solution.
To make sense of these "mysterious" behaviors, researchers have turned to Lyapunov stability theory, a cornerstone of control theory and physics. Instead of tracking the objective function alone, they construct a "Lyapunov function" (or energy functional)—a scalar metric that combines the objective value with other internal states of the optimizer, such as velocity or adaptive learning rates. By showing that this total "energy" consistently decreases, researchers can prove convergence for algorithms that appear chaotic under traditional analysis.
From Discrete Steps to Continuous Flows
The shift toward Lyapunov analysis was catalyzed by viewing optimization as a continuous-time dynamical system. In their seminal work, Weijie J. Su, Stephen P. Boyd, and Emmanuel J. Candès showed that Nesterov’s Accelerated Gradient Method can be modeled as a second-order ordinary differential equation (ODE).
This perspective transforms a sequence of algebraic updates into a physical trajectory. In this continuous world, proving convergence becomes a matter of finding the right energy function that "leaks" over time. This approach was further refined by Benjamin Recht and Michael I. Jordan, who demonstrated that the notoriously opaque "estimate sequence" technique used in discrete-time proofs is actually equivalent to a family of discrete-time Lyapunov functions.
The Physics of Momentum: Potential and Kinetic Energy
The most intuitive application of this theory is in momentum-based methods like the Heavy-ball method. In standard gradient descent, we only care about our current position (potential energy). In momentum methods, we also care about our velocity (kinetic energy).
Chi Jin and Michael I. Jordan utilized a Hamiltonian function—a sum of potential and kinetic energy—to analyze how accelerated methods escape saddle points. Even if the potential energy (the loss function) increases as the optimizer climbs out of a valley, the total Hamiltonian energy decreases because the kinetic energy is being traded for position.
Similarly, Tao Sun and Hao Jiang developed momentum-aware Lyapunov functions to prove "non-ergodic" convergence. This ensures that the actual current iterate converges to the optimum, rather than just the average of all past iterates, providing a much stronger guarantee for practitioners.
Taming Adaptive and Stochastic Complexity
Lyapunov functions are particularly powerful when dealing with the "noise" and "stale" information inherent in modern machine learning.
- Adaptive Stepsizes: When algorithms like those proposed by Yura Malitsky and Konstantin Mishchenko aggressively increase stepsizes based on local curvature, the objective function may fluctuate wildly. A specialized Lyapunov energy function can "absorb" these fluctuations, proving that the algorithm remains stable despite its aggression.
- Adaptive Optimizers (Adam): Anas Barakat and Pascal Bianchi modeled the Adam optimizer as a dynamical system. They constructed Lyapunov functions that incorporate the optimizer's internal "memory" (the first and second moments of gradients), showing that Adam’s complex state-tracking is actually a principled way of minimizing a global energy surface.
- Distributed Learning: In distributed settings where gradients are compressed or delayed, Zhize Li and Peter Richtárik used Lyapunov analysis to track how "compression noise" interacts with momentum. Their work on the CANITA algorithm shows that as long as the Lyapunov function accounts for the error introduced by compression, acceleration can still be achieved.
Stability in Unstable Landscapes
Perhaps the most challenging frontier is minimax optimization (used in GANs), where two players compete. These systems are prone to limit cycles—endless loops where the players chase each other without ever settling.
Ernest K. Ryu and Wotao Yin addressed this by introducing "anchoring" and analyzing it via ODEs. By constructing nonpositive Lyapunov functions, they could bound the magnitude of gradients over time. Benjamin Grimmer and Vahab S. Mirrokni further extended this by using smoothed primal-dual gaps as Lyapunov-type metrics, providing a way to quantify the stability of these "Wild West" landscapes.
By treating optimization as a physical system, Lyapunov stability theory replaces brittle algebraic proofs with a robust, geometric framework. It explains not just that an algorithm converges, but how it balances the trade-offs between speed, noise, and stability.