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

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 }/{\epsilon }^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 }/{\epsilon }^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 /\epsilon ))$ lower bound for large ${\kappa }_{\max }$. Existing PL lower bounds have focused only on relatively large $\kappa$. For the previously unexplored regime ${\kappa }_{\max }<\sqrt{n}$, we discover a new rate, $\Omega (n+n\log (\Delta /\epsilon )/(1+\log (\sqrt{n}/{\kappa }_{\max })))$. This lower bound motivates our Restarted PAGE algorithm, whose upper bound matches the new rate for small ${\kappa }_{\max }$ and recovers the standard PAGE rate for large ${\kappa }_{\max }$, showing that both bounds are nearly tight. Our lower bounds use the proposed dense weak hiding construction. It spreads each hidden direction across all components, so an individual IFO query reveals only weak information while the full average preserves the direction. Unrevealed stages remain inactive even for arbitrary query points, forcing many calls to expose a stage before substantial progress is possible. Balancing this revelation cost against the number of stages allowed by individual smoothness yields the missing $\sqrt{n}$ factor.

55 pages, 7 figures