Robustness of Accelerated First-Order Optimization Algorithms

Robustness of Accelerated First-Order Optimization Algorithms

By Mihailo Jovanovic (University of Southern California)

Talk Abstract: Gradient descent and its accelerated variants are increasingly used for learning and data-driven decision making for uncertain dynamical systems in which an approximation of the gradient is sought through noisy measurements. In this talk, we utilize techniques from control theory to quantify robustness of accelerated first-order algorithms to stochastic uncertainties in gradient evaluation. For unconstrained, smooth, strongly convex problems, we demonstrate how tight upper and lower bounds on the mean-square error in the optimization variable can be established when the iterates are perturbed by additive white noise. Our analysis reveals fundamental tradeoffs between noise amplification and convergence rates for any acceleration scheme similar to Nesterov’s or heavy-ball methods. In particular, we show that any choice of parameters for Nesterov’s accelerated and heavy-ball algorithms that yields an accelerated convergence rate increases noise amplification relative to gradient descent. To gain additional analytical insight, for strongly convex quadratic problems we provide a novel geometric characterization of conditions for linear convergence and clarify the relation between convergence rate, noise amplification, and algorithmic parameters. We specialize this result to the problem of distributed averaging over undirected networks and examine roles of network size and topology on robustness of noisy accelerated algorithms. Joint work with Hesameddin Mohammadi and Meisam Razaviyayn.

Speaker Bio: Mihailo R. Jovanovic is a professor in the Ming Hsieh Department of Electrical and Computer Engineering and the founding director of the Center for Systems and Control at the University of Southern California. He received the Dipl. Ing. and M.S. degrees from the University of Belgrade, Serbia, in 1995 and 1998, respectively, and the Ph.D. degree from the University of California, Santa Barbara, in 2004, under the direction of Bassam Bamieh. He was a visiting researcher with the Department of Mechanics, the Royal Institute of Technology, Stockholm, Sweden, from September to December 2004, and a faculty member in the Department of Electrical and Computer Engineering at the University of Minnesota, Minneapolis, from December 2004 until January 2017. He has held visiting positions with Stanford University and the Institute for Mathematics and its Applications.

Professor Jovanovic’s expertise is in modeling, dynamics, and control of large-scale and distributed systems and his current research focuses on large-scale and distributed optimization, design of controller architectures, sparsity-promoting optimal control, fundamental limitations in the design of large dynamic networks, and dynamics/control of fluid flows. He currently serves as an Associate Editor of the IEEE Transactions on Control of Network Systems and had served as a Guest Editor (of the Special Issue on Analysis, Control and Optimization of Energy System Networks in the IEEE Transactions on Control of Network Systems), the Chair of the American Physical Society External Affairs Committee, a Program Vice-Chair of the 55th IEEE Conference on Decision and Control, an Associate Editor of the SIAM Journal on Control and Optimization, and an Associate Editor of the IEEE Control Systems Society Conference Editorial Board.

Professor Jovanovic is a fellow of the American Physical Society (APS) and the Institute of Electrical and Electronics Engineers (IEEE). He received a CAREER Award from the National Science Foundation in 2007, an Early Career Award from the University of Minnesota Initiative for Renewable Energy and the Environment in 2010, a Resident Fellowship within the Institute on the Environment at the University of Minnesota in 2012, the George S. Axelby Outstanding Paper Award from the IEEE Control Systems Society in 2013, the University of Minnesota Informatics Institute Transdisciplinary Research Fellowship in 2014, and the Distinguished Alumnus Award from the Department of Mechanical Engineering at UC Santa Barbara in 2014. Papers of his students were finalists for the Best Student Paper Award at the American Control Conference in 2007 and 2014.