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

Under individual smoothness, known algorithms for nonconvex finite-sum optimization use O(n+√ nDelta Lmax/varepsilon2) incremental first-order oracle (IFO) calls, while existing lower bounds miss the factor √ n in the second term. We prove the matching lower bound Omega(n+√ nDelta Lmax/varepsilon2) for randomized IFO algorithms, allowing component indices and query points to depend on the complete 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, prior lower bounds did not capture the correct dependence on n under individual smoothness, and the regime of small kappa remained open for randomized IFO algorithms. We prove an Omega(n+kappamax√ nlog(Delta/varepsilon)) lower bound for kappamax≥√ n, and an Omega(n+nlog(Delta/varepsilon)/(1+log(√ n/kappamax))) lower bound for 3≤kappamax≤√ n. Restarted PAGE attains matching upper bounds under mean-squared smoothness in terms of kapparm ms=Lrm ms/μ. Our lower bounds use dense weak hiding. Each hidden direction is spread across all components, making individual queries weakly informative while preserving the direction in the average. A sufficiently large dimension makes premature activation of future stages unlikely within the query budget. Balancing the cost of revealing a stage against the number of stages permitted by individual smoothness yields the missing √ n factor.