# Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Mar 2018.

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

- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)
- [PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python](https://mlsanity.com/paper/2201.04040/) (2022)
- [Distributed Learning With Sparsified Gradient Differences](https://mlsanity.com/paper/2202.02491/) (2022)
- [Data-Driven Performance Guarantees for Classical and Learned Optimizers](https://mlsanity.com/paper/2404.13831/) (2024)
- [Stability and Performance Analysis of Discrete-Time ReLU Recurrent Neural Networks](https://mlsanity.com/paper/2405.05236/) (2024)
- [SQL-ASTRA: Alleviating Sparse Feedback in Agentic SQL via Column-Set Matching and Trajectory Aggregation](https://mlsanity.com/paper/2603.16161/) (2026)
- [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)
- [Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT](https://mlsanity.com/paper/2107.00481/) (2021)
- [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 novel way of generating Lyapunov functions for proving linear convergence rates of first-order optimization methods. Our approach provably obtains the fastest linear convergence rate that can be verified by a quadratic Lyapunov function (with given states), and only relies on solving a small-sized semidefinite program. Our approach combines the advantages of performance estimation problems (PEP, due to Drori & Teboulle (2014)) and integral quadratic constraints (IQC, due to Lessard et al. (2016)), and relies on convex interpolation (due to Taylor et al. (2017c;b)).