Analysis and Design of Optimization Algorithms using Robust ControlAlgebra & Discrete Mathematics
|Ben Recht, University of California, Berkeley
|Thu, May 14 2015, 4:00PM
Convex optimization provides a powerful toolkit for robust and efficient solutions of difficult engineering problems. However, as practitioners build increasingly complicated models and deploy optimization systems in highly complex environments, it becomes laborious to extend and generalize the mathematical guarantees of simple, standard convex primitives. In this talk, I will show that much of the analysis and design of these optimization algorithms can be automated, and will demonstrate that multiple objectives—such as robustness, accuracy, and speed—can be balanced inside one unified proof system built on tools from robust control theory. In particular, I will derive upper bounds on convergence rates for the gradient method, the heavy-ball method, Nesterov's accelerated method, and related variants by solving small, simple semidefinite programming problems. I will close with a discussion of how these techniques can be used to search for optimization algorithms with desired performance characteristics, establishing a new methodology for algorithm design. Joint work with Laurent Lessard and Andrew Packard Bio: Benjamin Recht is an Assistant Professor in the Department of Electrical Engineering and Computer Sciences and the Department of Statistics at the University of California, Berkeley. Ben was previously an Assistant Professor in the Department of Computer Sciences at the University of Wisconsin-Madison. Ben received his B.S. in Mathematics from the University of Chicago, and received a M.S. and PhD from the MIT Media Laboratory. After completing his doctoral work, he was a postdoctoral fellow in the Center for the Mathematics of Information at Caltech. He is the recipient of a Presidential Early Career Award for Scientists and Engineers, an Alfred P. Sloan Research Fellowship, the 2012 SIAM/MOS Lagrange Prize in Continuous Optimization, the 2013 Jamon Lecture Award, and the 2015 William O. Baker Award for Initiatives in Research.