{"id":"arxiv/2609.35418","url":"https://arxiv.org/abs/2609.35418","tags":["math.OC","cs.LG","stat.ML"],"score":0,"title":"Convex Optimization Is Free When Accuracy Is Expensive","domain":"math.OC","source":"arxiv","authors":["Arthur Paing","Arthur Jacot"],"reviews":0,"subject":"math.OC","summary":"This paper studies convex optimization when the gradient cannot be evaluated exactly, but only approximated by a hierarchy of algorithms whose compute grows like $δ^{-γ}$ in the accuracy $δ$. When $γ>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 $γ$, than a single evaluation of its gradient at the accuracy the problem demands. A randomized multilevel oracle replaces the deterministic approximation of accuracy…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}