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+\sqrt nΔL_{\max}/\varepsilon^2)$ incremental first-order oracle (IFO) calls, while existing lower bounds miss the factor $\sqrt n$ in the second term. We prove the matching lower bound $Ω(n+\sqrt nΔL_{\max}/\varepsilon^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)…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.00045
curl -X POST /api/v1/records/arxiv/2609.00045/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.00045/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'