Automatic Computation of Exact Worst-Case Performance for First-Order Methods

Tuesday, March 12, 2019 - 4:00pm to Wednesday, March 13, 2019 - 4:55pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Julien Hendrickx

Affiliation

UCLouvain

Building and Room Number

32-155

Abstract

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 algorithm's 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.

Biography

Julien M. Hendrickx is professor of mathematical engineering at Université catholique de Louvain, in the Ecole Polytechnique de Louvain since 2010. He is on sabbatical at Boston University in 2018-19, holding a WBI-World excellence fellowship.

He obtained an engineering degree in applied mathematics (2004) and a PhD in mathematical engineering (2008) from the same university. He has been a visiting researcher at the University of Illinois at Urbana Champaign in 2003-2004, at the National ICT Australia in 2005 and 2006, and at the Massachusetts Institute of Technology in 2006 and 2008. He was a postdoctoral fellow at the Laboratory for Information and Decision Systems of the Massachusetts Institute of Technology 2009 and 2010, holding postdoctoral fellowships of the F.R.S.-FNRS (Fund for Scientific Research) and of Belgian American Education Foundation.

Doctor Hendrickx is the recipient of the 2008 EECI award for the best PhD thesis in Europe in the field of Embedded and Networked Control, and of the Alcatel-Lucent-Bell 2009 award for a PhD thesis on original new concepts or application in the domain of information or communication technologies.