Description
Automatic computation of exact worst-case performance for first-order methods
Joint work with Adrien Taylor (INRIA) and Francois Glineur (UCLouvain)
We show that the exact worst-case performances of a wide class of first-order convex optimization algorithms can be obtained as solutions to semi-definite programs, which provide both the performance bounds and functions on which these are reached.
Our formulation is based on a necessary and sufficient condition for smooth (strongly) convex interpolation, allowing for a finite representation for smooth (strongly) convex functions in this context.
These results allow improving the performance bounds of many classical algorithms, and better understanding their dependence on the algorithms parameters, leading to new optimized parameters, and thus stronger performances.
Our approach can be applied via the PESTO Toolbox, which let the user describe algorithms in a natural way.