Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1, 2) , (3) , (4, 3)
1
2
3
4

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

Dates and versions

hal-01902068 , version 1 (25-10-2018)

Identifiers

Cite

Adrien Taylor, Bryan van Scoy, Laurent Lessard. Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees. Proceedings of the 35th International Conference on Machine Learning. PMLR 80:4897-4906, Jul 2018, Stockholm, Sweden. ⟨hal-01902068⟩
138 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More