Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

Yuxing Peng, Zhiqing Tang, Weijia Jia

Under individual smoothness, known algorithms for nonconvex finite-sum optimization use $O(n+\sqrt{n}\Delta L_{\max }/{\epsilon }^2)$ incremental first-order oracle (IFO) calls, while exis…