Smoothed Score Queries and the Complexity of Sampling

New research shows that switching to a different type of gradient query can dramatically reduce the computational cost of sampling from high-dimensional Gaussian distributions, improving the dependence on the condition number from a square-root to a logarithmic relationship [1]. The standard approach to sampling uses an oracle that provides exact gradients, which effectively only gives access to matrix-vector products with the precision matrix. This method hits a fundamental polynomial approximation barrier, resulting in a complexity that scales with the square root of the condition number, \(\sqrt{\kappa}\) [1]. The study, submitted for review on 26 May 2026, demonstrates this barrier is not inherent to the problem but is a limitation of the standard query model [2]. By instead querying "smoothed scores"—the gradients of the logarithms of Gaussian-convolved densities—a sampler gains access to a different mathematical object. For a Gaussian target with precision matrix \(\Lambda\), a smoothed-score query at noise level \(\tau\) provides the resolvent \((\Lambda+\tau^{-1}I)^{-1}\) [2]. This technique, which combines geometrically spaced noise levels with a sinc-quadrature rational approximation, yields a sampler requiring \(q=O\!\left(\bigl(\log\kappa+\log(e\sqrt d/\delta_{\rm TV})\bigr)\log(e\sqrt d/\delta_{\rm TV})\right)\) queries to achieve a total variation error of \(\delta_{\rm TV}\) [2]. The condition-number dependence is thereby improved from \(\sqrt{\kappa}\) to logarithmic [1]. The work also examines a more realistic setting where gradient information is communicated with finite precision. By applying coordinatewise quantization to transformed smoothed-score answers and a final dithering step, the researchers developed a sampling scheme whose total communicated gradient information is polylogarithmic in \(\kappa\) [2]. For a fixed dimension and accuracy, the bit complexity is \(O(\log^2\kappa)\) [1]. To establish the tightness of these results, the authors introduce a novel lower-bound technique based on channel synthesis, or a reverse-Shannon converse. This method converts total-variation simulation guarantees into communication requirements, producing an \(\Omega(\log\kappa)\) lower bound on the required gradient information [2]. Together, the nearly matching upper and lower bounds identify smoothed scores as a provably more informative oracle for sampling and precisely characterize its finite-bit complexity [1].