CAM Colloquium: Laurent Lessard (University of Wisconsin–Madison) - Automating the analysis and design of large-scale optimization algorithms

Description

Abstract: Most large-scale optimization problems are solved in practice using iterative algorithms. The problem of selecting a suitable algorithm is currently more of an art than a science; a great deal of expertise is required to know which algorithms to try and how to properly tune them. Moreover, there are seldom performance guarantees. In this talk, I will show how the problem of algorithm selection can be approached using tools from robust control theory. By solving simple semidefinite programs (that do not scale with problem size), we can derive robust bounds on convergence rates for popular algorithms such as the gradient method, proximal methods, fast/accelerated methods, and operator-splitting methods such as ADMM. The bounds derived in this manner either match or improve upon the best known bounds from the literature. The bounds also lead to a natural energy dissipation interpretation and an associated Lyapunov function. Finally, our framework can be used to search for algorithms that meet desired performance specifications, thus establishing a principled methodology for designing new algorithms.

Bio: Laurent Lessard is an Assistant Professor of Electrical and Computer Engineering at the University of Wisconsin–Madison and faculty member of the Wisconsin Institute for Discovery. Laurent received the B.A.Sc. in Engineering Science from the University of Toronto and the M.S. and Ph.D. in Aeronautics and Astronautics from Stanford University. After completing his doctoral work, Laurent was an LCCC Postdoc at Lund University in Sweden and a postdoctoral researcher at the University of California, Berkeley. Laurent is a recipient of the Hugo Schuck best paper award and the NSF CAREER award. His research interests include: decentralized control, robust control, optimization, and machine learning.