Timezone: »
Poster
Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees
Adrien Taylor · Bryan Van Scoy · Laurent Lessard
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)).
Author Information
Adrien Taylor (INRIA/ENS)
Bryan Van Scoy (University of Wisconsin--Madison)
Laurent Lessard (University of Wisconsin-Madison)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Oral: Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees »
Wed. Jul 11th 02:20 -- 02:30 PM Room A9
More from the Same Authors
-
2018 Poster: Dissipativity Theory for Accelerating Stochastic Variance Reduction: A Unified Analysis of SVRG and Katyusha Using Semidefinite Programs »
Bin Hu · Stephen Wright · Laurent Lessard -
2018 Oral: Dissipativity Theory for Accelerating Stochastic Variance Reduction: A Unified Analysis of SVRG and Katyusha Using Semidefinite Programs »
Bin Hu · Stephen Wright · Laurent Lessard -
2017 Poster: Dissipativity Theory for Nesterov's Accelerated Method »
Bin Hu · Laurent Lessard -
2017 Talk: Dissipativity Theory for Nesterov's Accelerated Method »
Bin Hu · Laurent Lessard