arXiv preprint ·
Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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)$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Statistics Theory
Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
On the Equivalence of Stochastic Control and Path Space Formulations for Schrödinger Bridges over Compact Connected Lie Groups
Yet another asymptotic formula for implied volatility
Exact calibration of structural models via time-change
Gaussian Normalized Coordinates and Risk-Neutral CDF Deformations
Get the few papers worth your time in Statistics Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.