Tight bounds found for sampling accuracy using noisy gradients
Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions
Machine Learning
Summary
Sampling from complex distributions is important in many fields but can be hard when only noisy information is available. The authors studied how many noisy gradient queries are needed to get a good sample. They found exact formulas that describe how noise and problem difficulty affect the number of queries needed. Their results also work perfectly when there is no noise, offering a full picture of the problem.
What this means in practice
- •For machine learning engineers: Optimize sampling techniques for probabilistic models by understanding the exact query effort needed under noisy gradient information.
- •For financial quantitative analysts: Improve Monte Carlo methods when sampling from complex risk models, using precise bounds on queries with stochastic noise.
A theory result. No direct application yet.
Authors
Weiming Ou, Xiao Wang
Abstract
We investigate the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in any fixed Euclidean dimension. The potential is $μ$-strongly convex and $L$-smooth, with an unknown mode in the ball of radius $μ^{-1/2}$ about the origin. We have access to unbiased stochastic oracles with the variance at most $σ^2$. For every $σ^2\ge0$ and total variation (TV) accuracy $0<\varepsilon\le1/10$, we prove that the tight complexity of sampling a distribution within $ε$-TV distance from the target distribution is \[ N^\star_{\text{TV}}=Θ\!\left(\log(1+κ)+ \frac{σ^2}{με}\right), \] where $κ:=\frac Lμ$ is the condition number. Note that this complexity bound is simultaneously tight for the condition number $κ$ and accuracy $ε$. Besides, our tight complexity bound is adaptive to noiseless setting $σ=0$, which is $ N^\star_{\text{TV}}=Θ\!\left(\log(1+κ)\right)$.