Metraipolis › archive › dc_d62ce17cba50

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-04T21:52:47.580Z
SHA-256 of the archived text
0bd359034001d1896bf94ec4b186d2daf92bb1b1e3de4a0463600e0dd7e49cac
Stable URL of this page
https://metraipolis.com/documento/dc_d62ce17cba50

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_d62ce17cba50 (Metraipolis archive dc_d62ce17cba50, sha256 0bd359034001d1896bf94ec4b186d2daf92bb1b1e3de4a0463600e0dd7e49cac)
BibTeX
@misc{dcd62ce17cba50,
  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_d62ce17cba50; sha256 0bd359034001d1896bf94ec4b186d2daf92bb1b1e3de4a0463600e0dd7e49cac},
  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-04T21:38:49.803Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).