351. Perspectives on the analysis and design of optimization algorithms: Lyapunov analyses and counter-examples
Invited abstract in session TB-10: First order methods: new perspectives for machine learning , stream Large scale optimization: methods and algorithms.
Tuesday, 10:30-12:30Room: B100/8011
Authors (first author is the speaker)
| 1. | Adrien Taylor
|
| Inria/ENS |
Abstract
Perspectives on the analysis and design of optimization algorithms: Lyapunov analyses and counter-examples
Lyapunov analysis is an essential tool in the study of simple first-order optimization methods, and for obtaining performance guarantees. This talk will cover a few recent constructive approaches to the discovery of such Lyapunov functions and of their structural properties in the context of first-order optimization. In addition, we cover a few constructive approaches to counter-examples for when no such Lyapunov exist.
The talk will be example-based, as many ingredients of those methodologies are already present when analyzing simple optimization algorithms such as gradient descent, the heavy-ball method, or the primal-dual hybrid gradient algorithm (Chambolle-Pock). We further illustrate how simple Lyapunov structure can be studied with existing software for computer-aided analyses (and in particular with PEPit) relying on different formulations of the analysis problem.
This talk is based on joint works with great colleagues, that include Francis Bach, Laurent Lessard, Bryan Van Scoy, Manu Upadhyaya, Sebastian Banert, Pontus Giselsson, Baptiste Goujaud, Daniel Berg Thomsen, Si Yi Meng, and Aymeric Dieuleveut.
Keywords
- First-order optimization
- Computer-aided algorithm analysis
- Large-scale optimization
Status: accepted
Back to the list of papers