Exponentially faster gradient methods in the presence of ravines

Abstract

Gradient methods are known to converge exponentially fast (i.e., linearly) when the objective function exhibits quadratic growth away from its minimizers. However, when the function is significantly flatter in certain directions, traditional gradient methods suffer an exponential slowdown. In this work, we introduce a gradient method with an adaptive stepsize that maintains rapid local convergence even in the presence of such flatness. We achieve this by geometrically formalizing the partial flatness through a structure we call a “Ravine.” This ravine structure allows us to interlace many short gradient steps with occasional long Polyak steps, collectively ensuring rapid convergence to the minimizer. We prove that ravines always exist for functions with at least fourth-order growth away from minimizers. Additionally, we illustrate the theory and algorithm on the problems of matrix sensing and factorization and learning a single neuron in the overparameterized regime. Time permitting, we will discuss the role of ravines in nonsmooth optimization problems and provide a local exponential acceleration of subgradient methods that applies to “generic” semialgebraic functions.

Bio

Damek Davis is a visiting Associate Professor at the Wharton Department of Statistics and Data Science at the University of Pennsylvania. He is also an Associate Professor of Operations Research at Cornell University (on leave). His research focuses on the interplay of optimization, signal processing, statistics, and machine learning. He has received several awards for his work, including a Sloan Research Fellowship in Mathematics (2020), the INFORMS Optimization Society Young Researchers Prize (2019), an NSF CAREER Award (2021), and the SIAM Activity Group on Optimization Best Paper Prize (2023).