ICML 2018oral86 citations
Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees
Adrien Taylor, Bryan Van Scoy, Laurent Lessard
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 and 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)).
BibTeX
@InProceedings{pmlr-v80-taylor18a,
title = {{L}yapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees},
author = {Taylor, Adrien and Van Scoy, Bryan and Lessard, Laurent},
booktitle = {Proceedings of the 35th International Conference on Machine Learning},
pages = {4897--4906},
year = {2018},
editor = {Dy, Jennifer and Krause, Andreas},
volume = {80},
series = {Proceedings of Machine Learning Research},
month = {10--15 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v80/taylor18a/taylor18a.pdf},
url = {https://proceedings.mlr.press/v80/taylor18a.html},
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 and 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)).}
}