Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The authors investigate convex optimization in the "Harder-Than-Monte-Carlo" regime ($\gamma > 2$), where gradient evaluation compute scales super-quadratically as $\delta^{-\gamma}$ with respect to target accuracy $\delta$. By replacing deterministic gradient approximations with a randomized multilevel oracle that decouples accuracy and variance, they prove that reaching loss $\varepsilon$ requires only $\Theta(\varepsilon^{-\gamma})$ compute for general convex objectives and $\Theta(\varepsilon^{-\gamma/2})$ under strong convexity. This establishes that fully minimizing a convex function costs asymptotically no more than computing a single gradient at the target accuracy, saving an entire factor of $1/\varepsilon$ in compute while maintaining bounds independent of smoothness constants.
In regimes where high-accuracy gradients are brutally expensive to compute, minimizing a convex objective costs asymptotically no more than evaluating its gradient just once.
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 $Θ(\varepsilon^{-γ})$ in the convex case, against $Θ(\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.