Lyapunov analysis is an essential tool in the study of (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 algorithms. 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 Chambolle-Pock algorithm.
This talk is based on joint works with great colleagues, that include:
- joint work with Laurent Lessard, Bryan Van Scoy: "Lyapunov functions for first-order methods: Tight automated convergence guarantees" (ICML 2018)
- joint work with Manu Upadhyaya, Sebastian Banert, and Pontus Giselsson: "Automated tight Lyapunov analysis for first-order methods", (Math Prog 2024)
- joint work with Baptiste Goujaud and Aymeric Dieuleveut: "Counter-examples in first-order optimization: a constructive approach" (CDC 2023) and "Provable non-accelerations of the heavy-ball method" (arXiv 2023).