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, the optimal incremental first-order oracle (IFO) complexity of nonconvex finite-sum optimization is open. Known algorithms use $O(n+\sqrt n\,ΔL_{\max}/…