# Convex Optimization Is Free When Accuracy Is Expensive

arXiv: https://arxiv.org/abs/2609.35418 · HTML: https://mlsanity.com/paper/2609.35418/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Builds on (most cited first, 10 of 10)

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Scaling Laws for Autoregressive Generative Modeling](https://mlsanity.com/paper/2010.14701/) (2020)
- [On the Convergence of SGD with Biased Gradients](https://mlsanity.com/paper/2008.00051/) (2020)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets](https://mlsanity.com/paper/2511.20888/) (2025)
- [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024)
- [Optimal inexactness schedules for Tunable Oracle based Methods](https://mlsanity.com/paper/2309.07787/) (2023)
- [Polynomial Speedup in Diffusion Models with the Multilevel Euler-Maruyama Method](https://mlsanity.com/paper/2603.24594/) (2026)

## Abstract (arXiv)

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 δ by an unbiased estimator of it, whose variance σ2 becomes a second, independently priced dial: the cost of one call drops from δ-γ to δ2-γσ-2. Plain inexact gradient descent driven by that oracle reaches loss varepsilon at expected compute Theta(varepsilon-γ) in the convex case, against Theta(varepsilon-(γ+1)) for the same method run at a fixed accuracy: randomization buys a full power of varepsilon. Under μ-strong convexity the exponent halves, to varepsilon-γ/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.