Convex Optimization Is Free When Accuracy Is Expensive

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 $\epsilon$ at expected compute $\Theta ({\epsilon }^{-\gamma })$ in the convex case, against $\Theta ({\epsilon }^{-(\gamma +1)})$ for the same method run at a fixed accuracy: randomization buys a full power of $\epsilon$. Under $\mu$-strong convexity the exponent halves, to ${\epsilon }^{-\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.