Convex Optimization Is Free When Accuracy Is Expensive

arXiv:2609.35418v1 Announce Type: cross Abstract: This paper studies convex optimization when the gradient cannot be evaluated exactly, but only approximated by a hierarchy of algorithms whose compute grows like elta^{-gamma} in the accuracy elta. 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 elta by an unbiased estimator of it, whose variance sigma^2 becomes a second, independently priced dial: the cost of one call drops from elta^{-gamma} to elta^{2-gamma}sigma^{-2}. Plain inexact gradient descent driven by that oracle reaches loss arepsilon at expected compute Theta(arepsilon^{-gamma}) in the convex case, against Theta(arepsilon^{-(gamma+1)}) for the same method run at a fixed accuracy: randomization buys a full power of arepsilon. Under mu-strong convexity the exponent halves, to arepsilon^{-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.

Source: arXiv cs.LG | 2026-09-29