用平滑得分查询突破高维高斯采样中的条件数瓶颈,实现对数级复杂度。
Smoothed Score Queries and the Complexity of Sampling
- 引入平滑得分查询,将梯度信息转化为对精度矩阵的有理逼近。
- 总变差误差下,查询次数仅对条件数呈对数依赖,优于传统方法的√κ。
- 适合关注高效采样与低通信开销的机器学习研究者,尤其在高维场景中。
我们研究利用梯度信息从高维高斯分布中采样的查询复杂度。在标准预言机模型中,精确梯度仅暴露精度矩阵与向量的乘积,导致多项式近似障碍和对条件数√κ的依赖。当允许查询平滑得分(即高斯卷积密度对数的梯度)时,该障碍消失。对于精度矩阵为Λ的高斯目标,噪声水平τ下的平滑得分查询可访问算子(Λ+τ⁻¹I)⁻¹。通过几何间隔设置噪声水平并结合sinc-求积有理逼近,我们得到一个总变差误差δ_TV的采样器,其平滑得分查询次数q=O((logκ+log(e√d/δ_TV))log(e√d/δ_TV)),将条件数依赖从√κ降至对数级。同时研究有限比特梯度预言机:通过对变换后的平滑得分答案进行坐标量化并引入最终抖动步骤,获得通信梯度信息为κ的多对数级的采样方案;在固定维度与精度下,比特复杂度为O(log²κ)。为补全上界,提出通道合成(反香农)下界技术,将总变差模拟保证转化为通信需求,得到所需梯度信息Ω(logκ)的下界。这些结果共同表明平滑得分是采样中更优的预言机,并给出了其有限比特复杂度的几乎匹配上下界。
原文摘要 · Abstract (English)
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κ\) dependence on the condition number. We show that this barrier disappears when the sampler is allowed to query \emph{smoothed scores}, namely gradients of the logarithms of the Gaussian-convolved densities. For a Gaussian target with precision matrix \(Λ\), a smoothed-score query at noise level \(τ\) gives access to the resolvent \((Λ+τ^{-1}I)^{-1}\). Combining geometrically spaced noise levels with sinc-quadrature rational approximation, we obtain a sampler with $q=O\!\left(\bigl(\logκ+\log(e\sqrt d/δ_{\rm TV})\bigr)\log(e\sqrt d/δ_{\rm TV})\right)$ smoothed-score queries for total variation error \(δ_{\rm TV}\), improving the condition-number dependence from \(\sqrtκ\) 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 \(κ\); in particular, for fixed dimension and accuracy, the bit complexity is \(O(\log^2κ)\). 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 \(Ω(\logκ)\) 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。