SILO: Escaping Saddle Points: Geometry and Dynamics of Gradient-Based Optimization

Abstract

Nonconvex optimization is central to modern computational algorithms, with first-order methods playing a leading role because of their low cost per iteration. Although saddle points can obstruct progress toward local minima, gradient descent and certain momentum methods almost surely avoid converging to strict saddles under suitable assumptions. Prior work establishes efficient escape for perturbed first-order methods, and O’Neill and Wright show that momentum can speed escape on nonconvex quadratics. For general nonconvex objectives, we ask what governs the speed of saddle escape: how do local curvature, a trajectory’s angle of entry into a saddle neighborhood, and momentum determine the number of iterations needed to escape that neighborhood?

This talk studies these questions by analyzing how optimization trajectories approach and leave saddle neighborhoods. We consider a class of locally analytic functions with nondegenerate critical points and Lipschitz gradients and Hessians. For gradient descent, we identify entry conditions that ensure fast escape from sufficiently small saddle neighborhoods, with an iteration bound that grows at most logarithmically with the inverse neighborhood radius. These conditions lead to a gradient method that uses a negative-curvature step when needed and converges to a local minimum under an additional coercivity assumption.

We then consider a general family of methods with time-varying momentum and establish conditions for fast escape from saddle neighborhoods. Within a family extending Nesterov’s accelerated method, stronger momentum improves the escape guarantees but weakens the guaranteed convergence rate near a local minimum. This tradeoff provides quantitative guidance for choosing momentum to balance fast saddle escape with convergence near a minimum.

This talk is based on joint work with Rishabh Dixit and Mert Gurbuzbalaban.

Bio

Waheed U. Bajwa is a professor in the Department of Electrical and Computer Engineering at Rutgers University-New Brunswick and a member of the graduate faculty of the Department of Statistics. He received his Ph.D. in electrical engineering from the University of Wisconsin-Madison in 2009. Before joining Rutgers in 2011, he was a postdoctoral research associate at Princeton University and a research scientist at Duke University. He later returned to Princeton as a visiting fellow in the Center for Statistics and Machine Learning from 2021 to 2022. His research interests include statistical signal processing, high-dimensional statistics, machine learning, inverse problems, and networked systems. He is an IEEE Fellow.

Dr. Bajwa’s honors include the Army Research Office Young Investigator Award, the National Science Foundation CAREER Award, the Rutgers Presidential Outstanding Faculty

Scholar Award, and the Rutgers Warren I. Susman Award for Excellence in Teaching. He has served as Chair of the IEEE Signal Processing Society’s Signal Processing for Communications and Networking Technical Committee and as a member of the Society’s Technical Directions Board. He currently serves on the Senior Editorial Board of IEEE Signal Processing Magazine and as an Associate Editor of IEEE Transactions on Information Theory.