Skip to content. Skip to navigation
CIM Menus
 

McGill ECE Seminar

Performance Estimation Problems: Automatic computation of first order optimization methods performances


Julien Hendrickx (joint work with Adrien Taylor and Francois Glineur)
UC Louvain
Belgium

July 27, 2017 at  11:00 AM
McConnell Engineering Room 603

Abstract:

We show that computing the worst-case performances of a broad class of first order optimization methods can be formulated as an optimization problem, which we can solve exactly. This allows simultaneously obtaining tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this worst-case, improving the bounds known for several classical algorithms.

Our method relies on a closed form necessary and sufficient condition for (smooth and/or strongly) convex interpolation. It can be applied to all fixed steps first order methods performing explicit, projected, proximal, conditional and/or inexact (sub)gradient steps, and combination of these. Moreover, we have developped a Matlab toolbox allowing users to write the algorithm to be evaluated in a natural way, as if they were implementing it.

Related references:
Taylor, A. B., Hendrickx, J. M., & Glineur, F. (2017). Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming, 161(1-2), 307-345.
Taylor, A. B., Hendrickx, J. M., & Glineur, F. (2017). Exact worst-case performance of first-order methods for composite convex optimization. SIAM Journal on Optimization, 27(3), 1283-1313.
Taylor, A. B., Hendrickx, J. M., & Glineur, F. (2017). Exact worst-case convergence rates of the proximal gradient method for composite convex minimization. arXiv preprint arXiv:1705.04398.
Toolbox: Performance Estimation Toolbox

Short bio:

Julien M. Hendrickx received an engineering degree in applied mathematics and a PhD in mathematical engineering from the Université catholique de Louvain, Belgium, in 2004 and 2008, respectively. 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. Since September 2010, he is a faculty member of the Université catholique de Louvain, in the Ecole Polytechnique de Louvain. Dr 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.