Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness
It is proved 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, and PAGE and SPIDER are minimax optimal up to universal constants under individual and mean-squared smoothness.