Glocal Smoothness: Line search and adaptive step sizes can help in theory too!

Curtis Fox, Aaron Mishkin, Sharan Vaswani +1

Iteration complexities for optimizing smooth functions with first-order algorithms are typically stated in terms of a global Lipschitz constant of the gradient, and near-optimal re…