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

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 $$\epsilon $$ . While bounds obtained using the standard argument typically are of the form $$\mathcal{O}(\epsilon ^{-\alpha })$$ for some positive $$\alpha $$ , the refined results are of the form $$o(\epsilon ^{-\alpha })$$ . 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.