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

2018/03/16 by Adrien Taylor, Taylor, Adrien, Bryan Van Scoy +3 · 7 citations
Computer Science · Engineering · Mathematics · #Advanced Control Systems Optimization #Advanced Optimization Algorithms Research #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1803.06073

to appear in ICML'18

openalex publication_date 2018/03/16 · arxiv created 2018/06/11 · arxiv updated 2018/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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)).

Citations

• The general problem of the stability of motion
• System analysis via integral quadratic constraints
• Dissipativity Theory for Nesterov's Accelerated Method

Cited by

• HNAG++: A Super-Fast Accelerated Gradient Method for Strongly Convex Optimization
• Gradient Methods with Online Scaling Part II. Practical Aspects
• Computer-aided analyses of stochastic first-order methods, via interpolation conditions for stochastic optimization
• AutoLyap: A Python package for computer-assisted Lyapunov analyses for first-order methods
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm
• Tight analyses of first-order methods with error feedback
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• A Tight Theory of Error Feedback Algorithms in Distributed Optimization

Related

• Automated tight Lyapunov analysis for first-order methods
• Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems
• Automated Lyapunov Analysis of Primal-Dual Optimization Algorithms: An Interpolation Approach
• Another approach to build Lyapunov functions for the first order methods in the quadratic case
• A Unified Convergence Analysis of First Order Convex Optimization Methods via Strong Lyapunov Functions