Fast Score-Based Sampling via Log-Concave Reductions

Martin J. Wainwright
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6592-6621, 2026.

Abstract

Sampling based on score diffusions has led to striking empirical results, and has attracted considerable attention from various research communities. It depends on the availability of (approximate) Stein score functions for various levels of additive noise. We show how, in some generality, the availability of scores allows the general problem to be “reduced” to sampling from an adaptively constructed sequence of $K$ strongly log-concave (SLC) sub-problems. The reduction is simple, constructive and algorithm-independent, so that any SLC sampler can be used as a subroutine. Various bounds on score-based sampling complexity follow directly: for instance, high-accuracy SLC samplers yield $\tilde{O}(\sqrt{d} \operatorname{polylog}(1/\varepsilon))$ guarantees for accuracy $\varepsilon$ in dimension $d$, whereas randomized midpoint SLC schemes yield $\tilde{O}( d^{1/3} \operatorname{poly}(1/\varepsilon))$ guarantees. When the original distribution itself is SLC, we prove that $K \leq 1 + \log_2(\kappa)$, thereby obtaining the first efficient procedure with logarithmic dependence on the condition number $\kappa$; for general distributions, the quantity $K$ depends on the geometry of the score Hessian across the trajectory. Our analysis is direct and simple, involving techniques and insights complementary to those in standard analyses of discretized diffusions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-wainwright26a, title = {Fast Score-Based Sampling via Log-Concave Reductions}, author = {Wainwright, Martin J.}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {6592--6621}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/wainwright26a/wainwright26a.pdf}, url = {https://proceedings.mlr.press/v336/wainwright26a.html}, abstract = {Sampling based on score diffusions has led to striking empirical results, and has attracted considerable attention from various research communities. It depends on the availability of (approximate) Stein score functions for various levels of additive noise. We show how, in some generality, the availability of scores allows the general problem to be “reduced” to sampling from an adaptively constructed sequence of $K$ strongly log-concave (SLC) sub-problems. The reduction is simple, constructive and algorithm-independent, so that any SLC sampler can be used as a subroutine. Various bounds on score-based sampling complexity follow directly: for instance, high-accuracy SLC samplers yield $\tilde{O}(\sqrt{d} \operatorname{polylog}(1/\varepsilon))$ guarantees for accuracy $\varepsilon$ in dimension $d$, whereas randomized midpoint SLC schemes yield $\tilde{O}( d^{1/3} \operatorname{poly}(1/\varepsilon))$ guarantees. When the original distribution itself is SLC, we prove that $K \leq 1 + \log_2(\kappa)$, thereby obtaining the first efficient procedure with logarithmic dependence on the condition number $\kappa$; for general distributions, the quantity $K$ depends on the geometry of the score Hessian across the trajectory. Our analysis is direct and simple, involving techniques and insights complementary to those in standard analyses of discretized diffusions.} }
Endnote
%0 Conference Paper %T Fast Score-Based Sampling via Log-Concave Reductions %A Martin J. Wainwright %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-wainwright26a %I PMLR %P 6592--6621 %U https://proceedings.mlr.press/v336/wainwright26a.html %V 336 %X Sampling based on score diffusions has led to striking empirical results, and has attracted considerable attention from various research communities. It depends on the availability of (approximate) Stein score functions for various levels of additive noise. We show how, in some generality, the availability of scores allows the general problem to be “reduced” to sampling from an adaptively constructed sequence of $K$ strongly log-concave (SLC) sub-problems. The reduction is simple, constructive and algorithm-independent, so that any SLC sampler can be used as a subroutine. Various bounds on score-based sampling complexity follow directly: for instance, high-accuracy SLC samplers yield $\tilde{O}(\sqrt{d} \operatorname{polylog}(1/\varepsilon))$ guarantees for accuracy $\varepsilon$ in dimension $d$, whereas randomized midpoint SLC schemes yield $\tilde{O}( d^{1/3} \operatorname{poly}(1/\varepsilon))$ guarantees. When the original distribution itself is SLC, we prove that $K \leq 1 + \log_2(\kappa)$, thereby obtaining the first efficient procedure with logarithmic dependence on the condition number $\kappa$; for general distributions, the quantity $K$ depends on the geometry of the score Hessian across the trajectory. Our analysis is direct and simple, involving techniques and insights complementary to those in standard analyses of discretized diffusions.
APA
Wainwright, M.J.. (2026). Fast Score-Based Sampling via Log-Concave Reductions. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:6592-6621 Available from https://proceedings.mlr.press/v336/wainwright26a.html.

Related Material