Computer-aided worst-case analyses and design of first-order methods for convex optimization

Adrien Taylor (INRIA)

01-Jun-2020, 13:00-14:00 (4 years ago)

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

Export talk to