University of Cambridge > Talks.cam > CCIMI Seminars > Computer-aided worst-case analyses and design of first-order methods for convex optimization

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

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Hamza Fawzi.

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, mirror, 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 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 https://github.com/AdrienTaylor/Performance-Estimation-Toolbox), which allows using the framework without any tedious semidefinite programming modelling step.

This talk are based on joint works with great collaborators (who will be mentioned during the presentation).

This talk is part of the CCIMI Seminars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity