Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is $o(\epsilon^-2)$ rather than $\mathcalO(\epsilon^-2)$
<|reference_start|>Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is $o(\epsilon^-2)$ rather than $\mathcalO(\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.<|reference_end|>
@article{gratton2024refining,
    title={Refining asymptotic complexity bounds for nonconvex optimization
  methods, including why steepest descent is $o(\epsilon^{-2})$ rather than
  $\mathcal{O}(\epsilon^{-2})$},
    author={Serge Gratton, Chee-Khian Sim, Philippe L. Toint},
    journal={arXiv preprint arXiv:2408.09124},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.09124},
    primaryClass={math.OC cs.CC}
}