Convex optimization cost drops when precise gradients are costly
Convex Optimization Is Free When Accuracy Is Expensive
Machine Learning
Summary
This paper looks at solving math problems where the usual way to check progress is expensive or only approximate. The authors show that if getting very exact answers is really costly, cleverly randomizing the process means you don’t pay much more than just one approximate measurement. This approach makes it cheaper to reach good solutions even when you can only estimate gradients noisily. Their results hold for common optimization methods and give precise ways to understand the cost depending on problem hardness.
What this means in practice
- •For machine learning engineers: Reduce computational cost in training models that rely on approximate gradient evaluations by using randomization to balance accuracy and compute.
- •For computational finance teams: Optimize pricing or risk models where exact gradient computations are expensive, benefiting from cost savings through randomized inexact gradients.
A theory result. No direct application yet.
Authors
Arthur Paing, Arthur Jacot
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 $δ^{-γ}$ 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.