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 δ-γ 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.