Metraipolis › archive › dc_d7d9ccd64d61

Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions — arXiv:2611.04171

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04171
License (as archived)
CC0-1.0
Archived
2026-11-04T12:41:26.440Z
SHA-256 of the archived text
dc289370a7a7a11bfbefd3eaa00d4c7c3d7c084e74bd1bfd405c9bfa3e81c074
Stable URL of this page
https://metraipolis.com/documento/dc_d7d9ccd64d61

How to cite

Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions — arXiv:2611.04171 — arXiv (en), https://arxiv.org/abs/2611.04171 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d7d9ccd64d61 (Metraipolis archive dc_d7d9ccd64d61, sha256 dc289370a7a7a11bfbefd3eaa00d4c7c3d7c084e74bd1bfd405c9bfa3e81c074)
BibTeX
@misc{dcd7d9ccd64d61,
  title = {Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions — arXiv:2611.04171},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04171},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d7d9ccd64d61; sha256 dc289370a7a7a11bfbefd3eaa00d4c7c3d7c084e74bd1bfd405c9bfa3e81c074},
  year = {2026}
}

Archived text

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

We study the minimization of the average of $n$ convex $(L_0,L_1)$-smooth functions: the Hessian norm of each function is bounded by an affine function of its gradient norm. We assume known upper bounds $R$ on the distance from the starting point to a minimizer and $\delta$ on the difference between the minimum of the average and the average of the infima of the components. We derive upper and lower bounds on the oracle complexity of reaching accuracy $\varepsilon$ in function value in expectation. Up to logarithmic factors, both bounds are of order $n(1+(L_1R)^{2/3}) +\sqrt{\frac{n(L_0+L_1^2\delta)R^2}{\varepsilon}+n(L_1R)^2}$. The upper bound is attained by the proposed method YETI. The method combines ideas of accelerated proximal methods and variance reduction methods with a heuristic for choosing additional points. The number of oracle calls made by the heuristic is bounded, which preserves the upper bound on the total number of queries needed to reach the target accuracy. In the experiments, YETI is compared with first-order methods on synthetic problems and Poisson regression problems. We also examine the stopping criterion and the effect of the heuristic separately. The lower bound is obtained by an explicit construction of families of instances that are hard for any first-order method.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2611.04171 — 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-11-04T12:29:47.380Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).