# Automated tight Lyapunov analysis for first-order methods

arXiv: https://arxiv.org/abs/2302.06713 · HTML: https://mlsanity.com/paper/2302.06713/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2023.

## Built on by (most cited first, 6 of 6)

- [Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysis](https://mlsanity.com/paper/2505.17965/) (2025)
- [Online Convex Optimization and Integral Quadratic Constraints: An automated approach to regret analysis](https://mlsanity.com/paper/2503.23600/) (2025)
- [Tight analyses of first-order methods with error feedback](https://mlsanity.com/paper/2506.05271/) (2025)
- [Gradient Methods with Online Scaling Part II. Practical Aspects](https://mlsanity.com/paper/2509.11007/) (2025)
- [Negative Momentum for Convex-Concave Optimization](https://mlsanity.com/paper/2604.17145/) (2026)
- [A Tight Theory of Error Feedback Algorithms in Distributed Optimization](https://mlsanity.com/paper/2605.31594/) (2026)

## Abstract (arXiv)

We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In particular, we consider i) classes of optimization problems of finite-sum form with (possibly strongly) convex and possibly smooth functional components, ii) first-order methods that can be written as a linear system in state-space form in feedback interconnection with the subdifferentials of the functional components of the objective function, and iii) quadratic Lyapunov inequalities that can be used to draw convergence conclusions. We present a necessary and sufficient condition for the existence of a quadratic Lyapunov inequality within a predefined class of Lyapunov inequalities, which amounts to solving a small-sized semidefinite program. We showcase our methodology on several first-order methods that fit the framework. Most notably, our methodology allows us to significantly extend the region of parameter choices that allow for duality-gap convergence in the Chambolle-Pock method when the linear operator is the identity mapping.