The Speed–Robustness Trade-Off for Iterative Optimization Algorithms

ABSTRACT: Most complicated optimization problems, in particular those involving a large number of variables, are solved in practice using iterative algorithms. A popular way to characterize the performance of such algorithms is the worst-case convergence rate. However, practical use cases often involve noisy data, so robustness can also be important. These two objectives are often competing. For example, with ordinary gradient descent, the choice of stepsize directly mediates the trade-off between speed and robustness. But for more complicated algorithms such as Polyak’s Heavy Ball method or Nesterov’s Accelerated method that have several tuning parameters, it is not clear how they should be tuned if more speed or more robustness is needed. In this talk, we will present a tractable way to compute convergence rate and sensitivity to additive gradient noise for a broad family of first-order methods, using tools from robust control. Specifically, we will solve small semidefinite programs in order to certify suitable dissipation inequalities. We will also present near-Pareto-optimal algorithm designs. Each design consists of a simple analytic update rule with two states of memory, similar to existing accelerated methods. Moreover, each design has a scalar tuning parameter that explicitly trades off convergence rate and robustness to noise. Finally, we validate the performance and near-optimality of our designs through numerous numerical simulations.

BIO: Laurent Lessard is an Associate Professor of Mechanical and Industrial Engineering at Northeastern University. Laurent was previously a Charles Ringrose Assistant Professor of Electrical and Computer Engineering at the University of Wisconsin-Madison and Faculty Member at the Wisconsin Institute for Discovery. He received the B.A.Sc. in Engineering Science from the University of Toronto, and received the M.S. and Ph.D. in Aeronautics and Astronautics at Stanford University. After completing his doctoral work, he was an LCCC Postdoc at Lund University in Sweden, and a postdoctoral researcher at the University of California, Berkeley. Dr. Lessard is a recipient of the Hugo Schuck best paper award and the NSF CAREER award. His research interests include: decentralized control, robust control, and optimization. For more information, see https://laurentlessard.com/

***Event will take place via Zoom. Zoom link and password will be distributed to the Controls Group e-mail list-serv. To join this list-serv, please send an (empty) email message to [email protected] with the word “subscribe” in the subject line. Zoom information is also available upon request to Katherine Godwin ([email protected]).