Everyone is welcome to attend the N&O lecture of Adrien Taylor (ENS Paris) with the title 'Computer-aided worst-case analyses and design of first-order methods'.
Abstract:
In this presentation, we will provide a high-level overview of recent approaches for analyzing and designing first-order methods using symbolic computations and/or semidefinite programming. A particular emphasis will be given to the "performance estimation" approach, which enjoys comfortable tightness guarantees: the approach fails only when the target results are impossible to prove. In particular, it allows obtaining (tight) worst-case guarantees for fixed-step first-order methods involving a variety of oracles - that includes explicit, projected, proximal, conditional, inexact, or stochastic (sub)gradient steps - and a variety of convergence measures.
The presentation will be example-based, as the main ingredients necessary for understanding the methodologies are already present in the analysis of the vanilla gradient method. For convincing the audience, we will provide other examples that include novel (100% computer-generated) analyses of the Douglas-Rachford splitting, and of a variant of the celebrated conjugate gradient method.
The methodology is implemented within the package "PESTO" (for "Performance EStimation TOolbox", available at <u>https://github.com/AdrienTaylor/Performance-Estimation-Toolbox</u>), which allows using the framework without any tedious semidefinite programming modelling step.
The talk is based on joint works with great collaborators: François Glineur (UCLouvain), Julien Hendrickx (UCLouvain), Etienne de Klerk (Tilburg/TU Delft), Yoel Drori (Google), Pontus Giselsson (Lund), Carolina Bergeling (Lund), Ernest Ryu (UCLA), Laurent Lessard (Wisconsin-Madison), Bryan Van Scoy (Wisconsin-Madison), and Francis Bach (Inria/ENS Paris).
