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

期刊论文
发表日期：

2025年7月24日

查看全文

S. Gratton,
C.-K. Sim,
Ph. 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 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.