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 has remained open. Known algorithms use $O(n+\sqrt{n}\,\Delta L_{\max}/\varepsilon^2)$ calls, while prior lower bounds miss a factor of $\sqrt{n}$. We prove the matching lower bound for randomized IFO algorithms whose component indices and query points may depend on the complete preceding transcript and private randomness. This determines the minimax IFO complexity up to universal constants under both individual and mean-squared smoothness. Under the global Polyak-Lojasiewicz (PL) condition, the standard PAGE guarantee is not tight when $\kappa_{\mathrm{ms}}<\sqrt{n}$. Restarted PAGE attains $O(n+n\log(\Delta/\varepsilon)/(1+\log(\sqrt{n}/\kappa_{\mathrm{ms}})))$ for $1\leq\kappa_{\mathrm{ms}}\leq\sqrt{n}$, and $O(n+\kappa_{\mathrm{ms}}\sqrt{n}\log(\Delta/\varepsilon))$ for $\kappa_{\mathrm{ms}}\geq\sqrt{n}$. We prove matching lower bounds under individual smoothness for every $\kappa_{\max}\geq 3$; the same hard instances also give the mean-squared lower bounds. In the small-$\kappa_{\max}$ range, their average objective is globally strongly convex. Our lower bounds use dense weak hiding. A fixed sign table spreads each hidden direction across the components. Each queried row carries little information, while the exact row average preserves the full signal after rescaling. A bounded radial map handles arbitrary query points, and a smooth gate makes unopened links invisible to both function values and gradients. Balancing the rows needed to reveal one stage with the number of stages allowed by individual smoothness yields the missing $\sqrt{n}$ factor.