Lower Bounds for Smooth Nonconvex FiniteSum Optimization
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:75747583, 2019.
Abstract
Smooth finitesum optimization has been widely studied in both convex and nonconvex settings. However, existing lower bounds for finitesum optimization are mostly limited to the setting where each component function is (strongly) convex, while the lower bounds for nonconvex finitesum optimization remain largely unsolved. In this paper, we study the lower bounds for smooth nonconvex finitesum optimization, where the objective function is the average of $n$ nonconvex component functions. We prove tight lower bounds for the complexity of finding $\epsilon$suboptimal point and $\epsilon$approximate stationary point in different settings, for a wide regime of the smallest eigenvalue of the Hessian of the objective function (or each component function). Given our lower bounds, we can show that existing algorithms including {KatyushaX} \citep{allen2018katyushax}, {Natasha} \citep{allen2017natasha} and {StagewiseKatyusha} \citep{yang2018does} have achieved optimal {Incremental Firstorder Oracle} (IFO) complexity (i.e., number of IFO calls) up to logarithm factors for nonconvex finitesum optimization. We also point out potential ways to further improve these complexity results, in terms of making stronger assumptions or by a different convergence analysis.
Related Material


