The next presentation of the Rényi Institute's Deep Learning seminar will be held by Julien Hendrickx (UCLouvain) at the 5th of May, 14:30 here.


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.