Metraipolis › archive › dc_d476720fe06f
Convex Optimization Is Free When Accuracy Is Expensive — arXiv:2609.35418
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35418
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T22:41:11.900Z
- SHA-256 of the archived text
ec9961cc14e954019ab7c4081b049ae5a512c68879056feb556c576b3f5c14ea- Stable URL of this page
https://metraipolis.com/documento/dc_d476720fe06f
How to cite
Convex Optimization Is Free When Accuracy Is Expensive — arXiv:2609.35418 — arXiv (en), https://arxiv.org/abs/2609.35418 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d476720fe06f (Metraipolis archive dc_d476720fe06f, sha256 ec9961cc14e954019ab7c4081b049ae5a512c68879056feb556c576b3f5c14ea)
BibTeX
@misc{dcd476720fe06f,
title = {Convex Optimization Is Free When Accuracy Is Expensive — arXiv:2609.35418},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35418},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d476720fe06f; sha256 ec9961cc14e954019ab7c4081b049ae5a512c68879056feb556c576b3f5c14ea},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35418. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
This paper studies convex optimization when the gradient cannot be evaluated exactly, but only approximated by a hierarchy of algorithms whose compute grows like $\delta^{-\gamma}$ in the accuracy $\delta$. When $\gamma>2$, falling into the Harder-Than-Monte-Carlo (HTMC) regime, the price of accuracy outruns the variance reduction that Monte Carlo would buy and we show that minimizing a loss function costs no more, up to a factor depending only on $\gamma$, than a single evaluation of its gradient at the accuracy the problem demands. A randomized multilevel oracle replaces the deterministic approximation of accuracy $\delta$ by an unbiased estimator of it, whose variance $\sigma^2$ becomes a second, independently priced dial: the cost of one call drops from $\delta^{-\gamma}$ to $\delta^{2-\gamma}\sigma^{-2}$. Plain inexact gradient descent driven by that oracle reaches loss $\varepsilon$ at expected compute $\Theta(\varepsilon^{-\gamma})$ in the convex case, against $\Theta(\varepsilon^{-(\gamma+1)})$ for the same method run at a fixed accuracy: randomization buys a full power of $\varepsilon$. Under $\mu$-strong convexity the exponent halves, to $\varepsilon^{-\gamma/2}$, because the iterates settle at a noise floor and the bias budget relaxes accordingly. Both bounds are independent of the step size, and hence of the smoothness constant, and we show that the cost is a functional of the underlying gradient flow rather than of any discretization of it.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LG).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2609.35418 — 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-07T22:14:28.923Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).