Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness
Abstract
Under individual smoothness, known algorithms for nonconvex finite-sum optimization use O(n+√nΔLmax/ε2) incremental first-order oracle (IFO) calls, while existing lower bounds miss the factor √n in the second term. We prove the matching lower bound Ω(n+√nΔLmax/ε2) 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 κ remained open for randomized IFO algorithms. We prove an Ω(n+κmax√nlog(Δ/ε)) lower bound for κmax≥√n, and an Ω(n+nlog(Δ/ε)/(1+log(√n/κmax))) lower bound for 3≤κmax≤√n. Restarted PAGE attains matching upper bounds under mean-squared smoothness in terms of κms=Lms/μ. 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.
Related
- Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
- The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
- Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under (L0,L1)-Smoothness
- On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{peng2026dense,
title = {{Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness}},
author = {Yuxing Peng and Zhiqing Tang and Weijia Jia},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.00045},
eprint = {2609.00045},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00045},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness
AU - Yuxing Peng
AU - Zhiqing Tang
AU - Weijia Jia
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2609.00045
UR - https://arxiv.org/abs/2609.00045
AB - Under individual smoothness, known algorithms for nonconvex finite-sum optimization use O(n+√nΔL_max/ε^2) incremental first-order oracle (IFO) calls, while existing lower bounds miss the factor √n in the second term. We prove the matching lower bound Ω(n+√nΔL_max/ε^2) 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 κ remained open for randomized IFO algorithms. We prove an Ω(n+κ_max√nlog(Δ/ε)) lower bound for κ_max≥√n, and an Ω(n+nlog(Δ/ε)/(1+log(√n/κ_max))) lower bound for 3≤κ_max≤√n. Restarted PAGE attains matching upper bounds under mean-squared smoothness in terms of κ_ms=L_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.
ER -