Computer-aided worst-case analyses and design of first-order methods for convex optimization
Adrien Taylor (INRIA)
Abstract: In this presentation, I want to 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 and some of its variants, 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 base optimization schemes. For convincing the audience, and if time allows, we will provide other examples that include analyses of the Douglas-Rachford splitting, and of a variant of the celebrated conjugate gradient method in its most naive form.
The methodology is implemented within the package "PESTO" (for "Performance EStimation TOolbox", available at github.com/AdrienTaylor/Performance-Estimation-Toolbox), which allows using the framework without the SDP modelling steps.
This talk is based on joint works with great collaborators (who will be mentioned during the presentation).
optimization and control
Audience: researchers in the topic
Comments: the address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk
One World Optimization seminar
Series comments: Description: Online seminar on optimization and related areas
The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk
Organizers: | Sorin-Mihai Grad*, Radu Ioan BoČ›, Shoham Sabach, Mathias Staudigl |
*contact for this listing |