Another Approach to Build Lyapunov Functions for the First Order Methods in the Quadratic Case

Daniil Merkulov, Ivan Oseledets

TL;DR

Researchers have discovered a surprisingly simple and universal Lyapunov function—a mathematical "energy function"—that proves the convergence of various accelerated optimization methods on quadratic problems. By applying Schur decomposition to the iteration matrices of these algorithms, they derived a single expression that decreases monotonically even when standard metrics like function value or distance to the optimum oscillate wildly.

What Problem Does This Paper Address?

In the world of optimization, "accelerated" first-order methods like Nesterov’s Accelerated Gradient (NAG) or the Heavy Ball (HB) method are the workhorses of modern machine learning. However, they have a frustrating quirk: they don't always move toward the solution in a straight line. If you plot the function value or the distance to the optimum over time, you’ll often see "ripples" or oscillations.

To prove these methods actually converge, mathematicians use Lyapunov functions. Think of a Lyapunov function as a measure of the system's total energy; if you can prove the energy always goes down, you've proved the system is stable and will eventually reach its lowest point. The problem is that finding these functions is usually an "art"—they are often complex, highly specific to a single algorithm, and require deep knowledge of constants like smoothness ($L$) or strong convexity ($\mu$).

Methods

The authors propose a systematic, linear-algebra-based approach to building these functions for quadratic problems.

  1. Linear Dynamical System: They represent first-order methods as a linear system: $z_{k+1} = Mz_k$, where $z$ is a state vector containing the current and previous iterations, and $M$ is the "iteration matrix."
  2. Schur Decomposition: Instead of looking at the whole system at once, they use Schur decomposition to bring the matrix $M$ into an upper triangular form.
  3. The "Magic" Coordinate: In this triangular form, the last coordinate of the transformed state vector is simply multiplied by an eigenvalue at each step. If the method is convergent, the absolute value of this eigenvalue is less than one, meaning this specific coordinate must shrink at every single iteration.
  4. The Universal Expression: By translating this shrinking coordinate back into the original variables, they arrived at a remarkably simple Lyapunov function: $$V(x_k, x_{k-1}, x_{k-2}) = \|x_{k-1} - x^*\|^2 - \langle x_k - x^*, x_{k-2} - x^* \rangle$$ where $x^*$ is the optimal solution.

Datasets

The paper relies on synthetic experimental setups to validate the theory:

  • Quadratic Problems: Randomly generated symmetric positive definite (SPD) matrices of various dimensions ($d=5$ to $d=500$) with controlled condition numbers.
  • Convex Non-Quadratic: An exponential function $f(x) = e^{\|x\|^2}$ to test the limits of the approach.
  • Non-Convex: The famous Rosenbrock function (a common benchmark for optimization) to see if the Lyapunov function holds up in "wilder" terrain.

Key Insights and Ideas

  • Independence from Constants: Unlike most Lyapunov functions, this one doesn't explicitly require the smoothness constant ($L$) or the strong convexity constant ($\mu$). It is derived purely from the structure of the iteration.
  • The Power of Conjugate Pairs: The authors found that for the function to decrease monotonically, the eigenvalues of the iteration matrix must be conjugate pairs (complex numbers). This is almost always true for methods like Heavy Ball and Nesterov when using optimal hyperparameters.
  • A Shared "Energy": Remarkably, the same mathematical expression works for several different algorithms (Heavy Ball, NAG, and NAG-GS). This suggests a deep underlying similarity in how these accelerated methods "spend" their momentum.

Key Results

  • Monotonicity Confirmed: In experiments with quadratic functions, the proposed Lyapunov function showed a perfectly smooth, monotonic decrease (a straight line on a log scale), while standard metrics like $\|\nabla f(x_k)\|$ and $f(x_k) - f(x^*)$ exhibited significant oscillations.
  • Asymptotic Optimality: The rate at which this Lyapunov function decreases is determined by the spectral radius of the iteration matrix, making it an asymptotically optimal measure of convergence.
  • Robustness to Hyperparameters: The function remains a valid Lyapunov function even when hyperparameters (like step size) are non-optimal, provided the "conjugate pair" condition on the eigenvalues is met.

Limitations and Future Work

  • Quadratic Constraint: The primary limitation is that the proof relies on the objective function being quadratic. While the function still "looks" okay in some convex cases, it is not a general-purpose Lyapunov function for all strongly convex functions.
  • Knowledge of the Optimum: The formula requires knowing $x^*$, which is usually what we are trying to find. This makes it a powerful tool for theoretical analysis and algorithm design, but less useful as a real-time stopping criterion in a production environment.
  • Future Directions: The authors suggest exploring whether this Schur-based approach can be extended to non-quadratic functions or used to automatically discover new, even faster optimization algorithms.

Summary updated

Abstract

Lyapunov functions play a fundamental role in analyzing the stability and convergence properties of optimization methods. In this paper, we propose a novel and straightforward approach for constructing Lyapunov functions for first-order methods applied to quadratic functions. Our approach involves bringing the iteration matrix to an upper triangular form using Schur decomposition, then examining the value of the last coordinate of the state vector. This value is multiplied by a magnitude smaller than one at each iteration. Consequently, this value should decrease at each iteration, provided that the method converges. We rigorously prove the suitability of this Lyapunov function for all first-order methods and derive the necessary conditions for the proposed function to decrease monotonically. Experiments conducted with general convex functions are also presented, alongside a study on the limitations of the proposed approach. Remarkably, the newly discovered L-yapunov function is straightforward and does not explicitly depend on the exact method formulation or function characteristics like strong convexity or smoothness constants. In essence, a single expression serves as a Lyapunov function for several methods, including Heavy Ball, Nesterov Accelerated Gradient, and Triple Momentum, among others. To the best of our knowledge, this approach has not been previously reported in the literature.
BibTeX
@inproceedings{merkulov2024another,
  author = {Daniil Merkulov and Ivan Oseledets},
  title = {{Another Approach to Build Lyapunov Functions for the First Order Methods in the Quadratic Case}},
  booktitle = {Computational},
  year = {2024},
  doi = {10.1134/s0965542524700131},
}

Loading related content...

Figure