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

Under individual smoothness, the optimal incremental first-order oracle (IFO) complexity of nonconvex finite-sum optimization is still open. Known algorithms use $O(n+\sqrt{n}\Delta L_{\max }/{\epsilon }^2)$ calls, but the best lower bounds miss a factor of $\sqrt{n}$ on the $\Delta L_{\max }/{\epsilon }^2$ term. We prove the matching lower bound $\Omega (n+\sqrt{n}\Delta L_{\max }/{\epsilon }^2)$. Thus PAGE and SPIDER are minimax optimal up to universal constants, under both individual and mean-squared smoothness. Unlike earlier bounds for linear-span algorithms, our result applies to the broader class of randomized IFO algorithms, allowing arbitrary choices of component indices and query points based on the complete preceding history. Under the global Polyak–Lojasiewicz (PL) condition, we use a similar idea to obtain an $\Omega (n+{\kappa }_{\max }\sqrt{n}\log (\Delta /\epsilon ))$ lower bound for large ${\kappa }_{\max }$. We also note that existing PL lower bounds have explored only relatively large values of $\kappa$. To fill this gap, we study the regime ${\kappa }_{\max }<\sqrt{n}$ and obtain a new lower-bound rate, $\Omega \left(n+n\log (\Delta /\epsilon )/(1+\log (\sqrt{n}/{\kappa }_{\max }))\right)$. The new lower bound motivates us to propose Restarted PAGE. Its upper bound matches the new rate for small ${\kappa }_{\max }$ and recovers the standard PAGE rate for large ${\kappa }_{\max }$, so both lower bounds are nearly tight. Our new lower bounds are based on our proposed dense weak hiding construction. By spreading each hidden direction across all components, the construction makes every single IFO query weakly informative while preserving the direction in the full row average. Because unrevealed stages remain inactive even for arbitrary query points, an algorithm must spend many calls to expose a stage before it can make substantial progress. We choose the bias to balance this revelation cost against the number of stages permitted by individual smoothness, and this balance produces the missing $\sqrt{n}$ factor.