151. Performance estimation of optimization methods: a guided tour
Invited abstract in session FA-5: Plenary III, stream Plenaries.
Friday, 9:00 - 10:00Room: E III
Authors (first author is the speaker)
| 1. | François Glineur
|
| ICTEAM/INMA & CORE, Université catholique de Louvain (UCLouvain) |
Abstract
Identifying the worst-case behaviour of an optimization method is a question that can itself be cast as an optimization problem. This is the main idea behind performance estimation, initially proposed by Drori and Teboulle in 2014. In this framework, one seeks to compute the exact convergence rate of a given black-box optimization algorithm over a given class of problem instances. In many cases, this computation can be reformulated into a finite-dimensional, tractable semidefinite program. Solving this program provides an exact, unimprovable convergence rate, a mathematical proof guaranteeing this rate and a problem instance where this worst-case behaviour is achieved. This is useful to compare efficiency across methods, tune algorithmic parameters (such as step-size) and, ultimately, design new methods with improved behaviour.
In this talk we will survey a few of the main achievements in the area of performance estimation, including the exact convergence rates of the gradient method over the full range of constant step-sizes, both on smooth (strongly) convex and smooth nonconvex functions, how to deal with methods involving linear operators and the exact convergence rate of the last iterate in subgradient methods, as well as some open questions related to performance estimation.
This talk will present joint work with Nizar Bousselmi, Julien Hendrickx, Panagiotis Patrinos, Teodor Rotaru and Moslem Zamani.
Keywords
- Complexity and efficiency of optimization algorithms
Status: accepted
Back to the list of papers