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

תקציר מקורי באנגליתarXiv:2609.00045v2 Announce Type: replace-cross Abstract: 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\,\Delta L_{\max}/\varepsilon^2)$ calls, while existing lower bounds miss the factor $\sqrt n$ in the second term. We prove the matching lower bound $\Omega(n+\sqrt n\,\Delta L_{\max}/\varepsilon^2)$ for randomized IFO algorithms, including those that choose component indices and query points from the full preceding history. Thus PAGE and SPIDER are minimax optimal up to universal constants under individual and mean-squared smoothness. Under the global Polyak--Lojasiewicz (PL) condition, we use a similar idea to obtain an $\Omega(n+\kappa_{\max}\sqrt n\log(\Delta/\var