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 with constant parameters 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
Mihailo 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 was a faculty member in the Department of Electrical and Computer Engineering at the University of Minnesota, Minneapolis, from 2004 until 2017, and has held visiting positions with Stanford University, the Simons Institute for the Theory of Computing, the Institute for Mathematics and its Applications, and the University of Belgrade. Professor Jovanovic received a CAREER Award from the National Science Foundation in 2007, the George S. Axelby Outstanding Paper Award from the IEEE Control Systems Society in 2013, and the Distinguished Alumnus Award from the University of California at Santa Barbara in 2014. He is a Fellow of the American Physical Society (APS) and the Institute of Electrical and Electronics Engineers (IEEE).
