Metraipolis › archive › dc_96d58ea97760

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.00045
License (as archived)
CC0-1.0
Archived
2026-10-17T06:52:27.953Z
SHA-256 of the archived text
0621c4d9996e66926319bc1759b2539dd0fd0cabcd3d9b4a43850ce75ec8bedd
Stable URL of this page
https://metraipolis.com/documento/dc_96d58ea97760

How to cite

Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness — arXiv:2609.00045 — arXiv (en), https://arxiv.org/abs/2609.00045 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_96d58ea97760 (Metraipolis archive dc_96d58ea97760, sha256 0621c4d9996e66926319bc1759b2539dd0fd0cabcd3d9b4a43850ce75ec8bedd)
BibTeX
@misc{dc96d58ea97760,
  title = {Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness — arXiv:2609.00045},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.00045},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_96d58ea97760; sha256 0621c4d9996e66926319bc1759b2539dd0fd0cabcd3d9b4a43850ce75ec8bedd},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.00045. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Under individual smoothness, known algorithms for nonconvex finite-sum optimization use $O(n+\sqrt n\Delta 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 $\Omega(n+\sqrt n\Delta 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) 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+\kappa_{\max}\sqrt n\log(\Delta/\varepsilon))$ lower bound for $\kappa_{\max}\ge\sqrt n$, and an $\Omega(n+n\log(\Delta/\varepsilon)/(1+\log(\sqrt n/\kappa_{\max})))$ lower bound for $3\le\kappa_{\max}\le\sqrt n$. Restarted PAGE attains matching upper bounds under mean-squared smoothness in terms of $\kappa_{\rm ms}=L_{\rm ms}/\mu$. 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 $\sqrt n$ factor.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-02 in cs.LG).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.00045 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T06:41:55.873Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).