Robustness of accelerated first-order optimization algorithms

Abstract:
Gradient descent and its accelerated variants are increasingly employed in learning and data-driven decision-making for uncertain dynamical systems, where gradients must be approximated through noisy measurements. In this talk, we draw on techniques from control theory to quantify the robustness of accelerated first-order algorithms to stochastic uncertainties in gradient evaluations. For unconstrained, smooth, and strongly convex problems, we derive tight upper and lower bounds on the mean-square error of the optimization variable under additive white noise perturbations. Our analysis reveals fundamental tradeoffs between noise amplification and convergence rates for any acceleration scheme with constant parameters, such as those in Nesterov's or heavy-ball methods. In particular, we show that parameter choices enabling accelerated convergence in these methods necessarily lead to increased noise amplification compared to standard gradient descent. To further elucidate these tradeoffs, we provide a novel geometric characterization of linear convergence conditions for strongly convex quadratic problems, highlighting the interplay between convergence rate, noise sensitivity, and algorithmic parameters. We then specialize our results to distributed averaging over undirected networks, examining how network size and topology influence the robustness of noisy accelerated algorithms.

Joint work with: Hesameddin Mohammadi and Meisam Razaviyayn

 

References:

 

Biosketch:

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).