Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is $o(\hat{I}{\mu }^{-2})$ rather than $\mathcal{O}(\hat{I}{\mu }^{-2})$

Abstract

We revisit the standard ``telescoping sum'' argument ubiquitous in the final steps of analyzing evaluation complexity of algorithms for smooth nonconvex optimization, and obtain a refined formulation of the resulting bound as a function of the requested accuracy $\hat{I}\mu$. While bounds obtained using the standard argument typically are of the form $\mathcal{O}(\hat{I}{\mu }^{-\hat{I}\pm })$ for some positive $\hat{I}\pm$, the refined results are of the form $o(\hat{I}{\mu }^{-\hat{I}\pm })$. We then explore to which known algorithms our refined bounds are applicable and finally describe an example showing how close the standard and refined bounds can be.

10 ages, 1 figure