论文简报
cs.DS 2605.27769v1 必读

Smoothed Score Queries and the Complexity of Sampling

Jingbo Liu

发布日期：2026-05-26 23:38 相关性：1.0000 价值：0.8600 分类：cs.DS cs.IT cs.LG stat.ML
arXiv 摘要 PDF 原文 网页正文

摘要

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.

相关性判断

high
相关方向
information_theory communication_complexity sampling oracle_complexity
判断依据

The paper is directly about query and communication complexity, with a reverse-Shannon/channel-synthesis lower bound and finite-bit oracle complexity; it is clearly adjacent to information theory and cs.IT.

价值判断

Directly relevant to cs.IT via query complexity, communication complexity, and reverse-Shannon/channel-synthesis lower bounds. Clear technical contribution: smoothed-score oracle changes condition-number dependence from sqrt-kappa to logarithmic for Gaussian sampling. Structure analysis indicates substantial depth with matching upper/lower finite-bit complexity tools and explicit TV guarantees.

核心问题与主要方法

核心问题

Sampling high-dimensional Gaussians from gradient or smoothed-score oracles under query and communication constraints

场景：Centered Gaussian target N(0, Λ^{-1}) with condition number κ, exact or finite-bit smoothed-score oracle, total-variation sampling

主要方法

Smoothed-score access converts Gaussian score queries into shifted-inverse/resolvent evaluations of the precision matrix. Geometrically spaced smoothing levels provide a rational basis for approximating x^{-1/2} over [1, kappa]. Sinc-quadrature rational approximation supplies the coefficients and grid used by the exact samplers. Finite-bit sampling uses coordinatewise quantization of weighted transformed query responses, followed by Gaussian dithering to control total variation despite discretization. The converse treats a sampler with Q transmitted bits as a Q-bit simulator for a Gaussian covariance channel and imports channel-coding lower bounds through channel synthesis.

关键贡献与后续阅读

关键贡献

Identifies smoothed scores as a strictly more informative oracle than ordinary gradients for condition-number-dependent Gaussian sampling complexity. Gives exact smoothed-score samplers whose query complexity depends logarithmically on kappa through rational approximation rather than polynomial/Krylov approximation. Provides a finite-bit smoothed-score algorithm with polylogarithmic kappa communication and O(log^2 kappa) bit complexity for fixed dimension and accuracy. Introduces a channel-synthesis / reverse-Shannon converse for sampling lower bounds that directly reasons about simulation in total variation instead of reducing sampling to parameter estimation. Establishes nearly matching finite-bit upper and lower complexity in kappa for the Gaussian smoothed-score setting.

研究启发

How robust is the resolvent-access advantage when scores are approximate or learned rather than exact Gaussian-smoothed scores? Can the channel-synthesis lower-bound method be extended to exact real-valued smoothed-score queries by imposing a numerical stability or finite-information constraint? Which parts of the sinc-quadrature construction depend essentially on Gaussian algebra, and which might survive for broader log-concave or diffusion-model target classes?

限制与不确定性

Results appear specialized to Gaussian targets and resolvent algebra, so broader impact beyond this setting is uncertain. Exact real-valued smoothed-score lower bounds and non-Gaussian extensions remain open.

参考文献

31 条
  1. Aune et al., (2013) Aune, E., Eidsvik, J., and Pokern, Y. (2013). Iterative numerical methods for sampling from high dimensional Gaussian distributions. Statistics and Computing , 23(4):501–521.
  2. Bennett et al., (2014) Bennett, C. H., Devetak, I., Harrow, A. W., Shor, P. W., and Winter, A. (2014). The quantum reverse Shannon theorem and resource tradeoffs for simulating quantum channels. IEEE Transactions on Information Theory , 60(5):2926–2959.
  3. Bennett et al., (2002) Bennett, C. H., Shor, P. W., Smolin, J. A., and Thapliyal, A. V. (2002). Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem. IEEE Transactions on Information Theory , 48(10):2637–2655.
  4. Berta et al., (2011) Berta, M., Christandl, M., and Renner, R. (2011). The quantum reverse Shannon theorem based on one-shot information theory. Communications in Mathematical Physics , 306(3):579–615.
  5. Chen et al., (2026) Chen, F., Chewi, S., Daskalakis, C., and Rakhlin, A. (2026). High-accuracy sampling for diffusion models and log-concave distributions. arXiv preprint arXiv:2602.01338 .
  6. (6) Chen, S., Chewi, S., Lee, H., Li, Y., Lu, J., and Salim, A. (2023a). The probability flow ode is provably fast. Advances in Neural Information Processing Systems , 36:68552–68575.
  7. (7) Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. R. (2023b). Sampling is as easy as learning the score: Theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations . arXiv:2209.11215.
  8. Chen et al., (2022) Chen, T., Greenbaum, A., Musco, C., and Musco, C. (2022). Error bounds for Lanczos-based matrix function approximation. SIAM Journal on Matrix Analysis and Applications , 43(2):787–811.
  9. Chewi et al., (2024) Chewi, S., de Dios Pont, J., Li, J., Lu, C., and Narayanan, S. (2024). Query lower bounds for log-concave sampling. Journal of the ACM , 71(4):29:1–29:42. Preliminary version in FOCS 2023; arXiv:2304.02599.
  10. Chewi et al., (2023) Chewi, S., Gerber, P., Lee, H., and Lu, C. (2023). Fisher information lower bounds for sampling. In Proceedings of the 34th International Conference on Algorithmic Learning Theory , volume 201 of Proceedings of Machine Learning Research , pages 375–410. PMLR. arXiv:2210.02482.
  11. Chewi et al., (2022) Chewi, S., Gerber, P. R., Lu, C., Le Gouic, T., and Rigollet, P. (2022). The query complexity of sampling from strongly log-concave distributions in one dimension. In Proceedings of the Thirty Fifth Conference on Learning Theory , volume 178 of Proceedings of Machine Learning Research , pages 2041–2059. PMLR.
  12. Chow and Saad, (2014) Chow, E. and Saad, Y. (2014). Preconditioned Krylov subspace methods for sampling multivariate Gaussian distributions. SIAM Journal on Scientific Computing , 36(2):A588–A608.
  13. Cuff, (2013) Cuff, P. (2013). Distributed channel synthesis. IEEE Transactions on Information Theory , 59(11):7071–7096.
  14. Gallager, (1968) Gallager, R. G. (1968). Information Theory and Reliable Communication . John Wiley & Sons, New York.
  15. Gao and Zhu, (2025) Gao, X. and Zhu, L. (2025). Convergence analysis for general probability-flow ODEs of diffusion models in wasserstein distances. In International Conference on Artificial Intelligence and Statistics , volume 258 of Proceedings of Machine Learning Research , pages 1009–1017. arXiv:2401.17958.
  16. Ho et al., (2020) Ho, J., Jain, A., and Abbeel, P. (2020). Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems , volume 33, pages 6840–6851.
  17. Jiao and Li, (2024) Jiao, Y. and Li, G. (2024). Instance-dependent convergence theory for diffusion models. arXiv preprint arXiv:2410.13738 .
  18. Jiao et al., (2025) Jiao, Y., Zhou, Y., and Li, G. (2025). Optimal convergence analysis of DDPM for general distributions. arXiv preprint arXiv:2510.27562 .
  19. Liu et al., (2017) Liu, J., Cuff, P., and Verdú, S. (2017). E γ E_{\gamma} -resolvability. IEEE Transactions on Information Theory , 63(5):2629–2658.
  20. Liu and Verdú, (2018) Liu, J. and Verdú, S. (2018). Rejection sampling and noncausal sampling under moment constraints. In 2018 IEEE International Symposium on Information Theory (ISIT) , pages 1565–1569.
  21. Lu, (2023) Lu, C. (2023). Upper and Lower Bounds for Sampling . PhD thesis, Massachusetts Institute of Technology.
  22. Mahajan et al., (2025) Mahajan, J., Zhang, K., Liang, F., and Liu, J. (2025). The Picard-Lagrange framework for higher-order Langevin Monte Carlo. arXiv preprint arXiv:2510.18242 .
  23. Musco et al., (2018) Musco, C., Musco, C., and Sidford, A. (2018). Stability of the Lanczos method for matrix function approximation. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1605–1624.
  24. Neal, (2001) Neal, R. M. (2001). Annealed importance sampling. Statistics and Computing , 11(2):125–139.
  25. Okayama et al., (2013) Okayama, T., Matsuo, T., and Sugihara, M. (2013). Error estimates with explicit constants for sinc approximation, sinc quadrature and sinc indefinite integration. Numerische Mathematik , 124(2):361–394.
  26. Song et al., (2021) Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. (2021). Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations .
  27. Stenger, (1993) Stenger, F. (1993). Numerical Methods Based on Sinc and Analytic Functions , volume 20 of Springer Series in Computational Mathematics . Springer.
  28. Trefethen and Weideman, (2014) Trefethen, L. N. and Weideman, J. A. C. (2014). The exponentially convergent trapezoidal rule. SIAM Review , 56(3):385–458.
  29. Vershynin, (2018) Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science , volume 47 of Cambridge Series in Statistical and Probabilistic Mathematics . Cambridge University Press.
  30. Xun and Price, (2026) Xun, Z. and Price, E. (2026). Query lower bounds for diffusion sampling. arXiv preprint arXiv:2604.10857 .

底部评论

0 条根评论，可继续回复叠楼

0/2000