Thu, 18-May-2023 / 4:00pm / Packard 202
Most complicated optimization problems, in particular those involving a large number of variables, 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. We give examples of novel algorithm designs to address distributed optimization and stochastic optimization problems.
Laurent Lessard is an Associate Professor of Mechanical and Industrial Engineering at Northeastern University, Boston, USA, and a core faculty member of the Experiential Institute for AI. He received a B.A.Sc. in Engineering Science from the University of Toronto, and the M.S. and Ph.D. in Aeronautics and Astronautics at Stanford University. His research interests include: decentralized control, robust control, optimization, and machine learning. Before joining Northeastern, he was a Charles Ringrose Assistant Professor of Electrical and Computer Engineering at the University of Wisconsin–Madison. Prior to that, he was an LCCC Postdoc in the Department of Automatic Control at Lund University, Sweden, and a postdoctoral researcher in the Berkeley Center for Control and Identification at the University of California, Berkeley. Laurent is a recipient of the Hugo Schuck best paper award and the NSF CAREER award. He is also a Senior Member of IEEE.