Lyapunov functions for optimization algorithms

Adrien Taylor, Bryan Van Scoy, and I have recently posted a manuscript on arxiv entitled “Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees”.

Lyapunov functions are a mathematical tool used in the analysis of dynamical systems for implicitly certifying stability. The rough idea is that we look for some sort of “energy function” that we can prove always decreases, and then we can relate the rate of decay of energy to the rate of decay of a more meaningful quantity, such as the state of our dynamical system.

In the context of optimization algorithms, the dynamical system is the algorithm itself (a discrete-time dynamical system), and the function we are optimizing is treated as uncertainty. The function is uncertain because we don’t assume we know it precisely, just that we know some of its properties (e.g. strong convexity and Lipschitz gradients). The goal is to look for a Lyapunov function that will always decrease regardless of what our function happens to be, so long as it satisfies the aforementioned properties. Finding the best Lyapunov function is a difficult problem in general, so one typically uses a “Lyapunov candidate”, which is a parameterized family of functions that can be efficiently searched by computational means. A popular choice is to use quadratic functions because in the case of a linear system, the existence of a quadratic Lyapunov function is necessary and sufficient for stability. In the case of robust optimization, where we are uncertain about the function, there is no such guarantee of quadratic necessity.

In this paper, we provide an efficient way of searching for quadratic Lyapunov functions that prove the robust stability of algorithms. Specifically, we show that for any fixed rate rho, the feasibility of a particular (small) semidefinite program is equivalent to the existence of a quadratic Lyapunov function that certifies a linear convergence rate of rho in the worst case. The key result here is the necessity. While previous results used semidefinite programs as sufficient conditions for convergence, our result is also necessary. So if our semidefinite program is infeasible, it means that there is no quadratic Lyapunov function that certifies stability with a rate of rho.