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.

Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Optimization and Control (math.OC)

arXiv:2609.00045 [cs.DS]

(or arXiv:2609.00045v1 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2609.00045 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.