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

Serge Gratton, Chee-Khian Sim, Philippe L. Toint

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…