Smoothed Score Queries and the Complexity of Sampling

arXiv:2605.27769v1 Announce Type: cross Abstract: We study the query complexity of sampling from high-dimensional Gaussian distributions using gradient information. In the standard oracle model, exact gradients expose only matrix-vector products with the precision matrix, leading to polynomial approximation barriers and a characteristic (sqrt{kappa}) dependence on the condition number. We show that this barrier disappears when the sampler is allowed to query smoothed scores, namely gradients of the logarithms of the Gaussian-convolved densities. For a Gaussian target with precision matrix (Lambda), a smoothed-score query at noise level (au) gives access to the resolvent ((Lambda+au^{-1}I)^{-1}). Combining geometrically spaced noise levels with sinc-quadrature rational approximation, we obtain a sampler with q=O!left(igl(logkappa+log(esqrt d/elta_{rm TV})igr)log(esqrt d/elta_{rm TV})right) smoothed-score queries for total variation error (elta_{rm TV}), improving the condition-number dependence from (sqrt{kappa}) to logarithmic. We also study finite-bit gradient oracles. Using coordinatewise quantization of the transformed smoothed-score answers and a final dithering step, we obtain a sampling scheme whose total communicated gradient information is polylogarithmic in (kappa); in particular, for fixed dimension and accuracy, the bit complexity is (O(log^2kappa)). To complement these upper bounds, we introduce a channel-synthesis, or reverse-Shannon, converse technique for sampling lower bounds. This converts total-variation simulation guarantees into communication requirements and yields an (Omega(logkappa)) lower bound on the required gradient information. Together, these results identify smoothed scores as a provably more informative oracle for sampling and give nearly matching upper and lower bounds for its finite-bit complexity.

Source: arXiv cs.LG | 2026-05-28