Adaptive Normalized Gradient Method for $(L_0,L_1)$-smooth Problems: Estimating Problem Parameters as a Region

Abstract

We propose a parameter-free and efficient gradient descent algorithm for $(L_0,L_1)$-smooth optimization. This notion of smoothness, introduced by Zhang et al. (2020), allows the smoothness bound to grow with the gradient norm. Similar to cutting-plane localization, our method uses a sequence of observations to maintain a region of plausible values for $(L_0,L_1)$ and uses this region to select step sizes. In the convex setting, our method attains the standard iteration complexity bound $\tilde{\mathcal{O}}\left(\left(L_0/\epsilon +L_1^2\right)\Vert x^0-x^{\ast }{\Vert }^2\right)$ for finding an $\epsilon$-optimal solution, while in the nonconvex setting it finds an $\epsilon$-stationary point within $\tilde{\mathcal{O}}\left(\left(L_0/{\epsilon }^2+L_1/\epsilon \right)(f(x^0)-f^{\ast })\right)$ iterations. To the best of our knowledge, this is the first work to establish, for a single parameter-free algorithm, the best-known iteration-complexity guarantee in the nonconvex setting while also providing the above iteration-complexity guarantee in the convex setting. Experiments on logistic regression and real phase retrieval demonstrate that our method can exploit $(L_0,L_1)$-smoothness and perform efficiently on nonconvex problems.

arXiv comment27 pages, 6 figures