Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions
Abstract
We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension d≥1. For μ-strongly convex, L-smooth potentials with unknown minimizers xf⋆ in the ball 𝔹(0,μ−1/2), and unbiased gradient oracles with variance at most σ2, the minimax worst-case expected query complexity is Θ(log(1+κ)+σ2/με), jointly optimal for the condition number κ:=L/μ, variance σ2≥ 0, and TV accuracy 0<ε≤ 1/10. In the noiseless setting σ=0, this tight complexity Θ(log(1+κ)) is independent of ε. Moreover, a gradient-only sampler generates an exact sample with O(log(1+κ)) worst-case expected queries. Without previous ball 𝔹(0,μ−1/2), exact sampling from any initial point x0 can be implemented with expected cost O(log(1+κ)+log(1+√μ|x0−xf⋆|)), without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.
Related
- Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
- Gradient-Free Sampling from Generative Models via Stochastic Bounded Extremum Seeking
- Spherical-Design Oracles for Zeroth-Order Optimisation: Deterministic, Variance-Free Gradient Estimation
- Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under (L0,L1)-Smoothness
- An Ω(κy8ε−6) Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
BibTeX
@misc{ou2026tight,
title = {{Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions}},
author = {Weiming Ou and Xiao Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12590},
eprint = {2609.12590},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12590},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions
AU - Weiming Ou
AU - Xiao Wang
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.12590
UR - https://arxiv.org/abs/2609.12590
AB - We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension d≥1. For μ-strongly convex, L-smooth potentials with unknown minimizers x_f^⋆ in the ball 𝔹(0,μ^−1/2), and unbiased gradient oracles with variance at most σ^2, the minimax worst-case expected query complexity is Θ(log(1+κ)+σ^2/με), jointly optimal for the condition number κ:=L/μ, variance σ^2≥ 0, and TV accuracy 0<ε≤ 1/10. In the noiseless setting σ=0, this tight complexity Θ(log(1+κ)) is independent of ε. Moreover, a gradient-only sampler generates an exact sample with O(log(1+κ)) worst-case expected queries. Without previous ball 𝔹(0,μ^−1/2), exact sampling from any initial point x_0 can be implemented with expected cost O(log(1+κ)+log(1+√μ|x_0−x_f^⋆|)), without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.
ER -