Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions

Kaihong Zhang, Heqi Yin, Feng Liang, Jingbo Liu
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:60134-60178, 2024.

Abstract

We study the asymptotic error of score-based diffusion model sampling in large-sample scenarios from a non-parametric statistics perspective. We show that a kernel-based score estimator achieves an optimal mean square error of ˜O(n−1t−d+22(td2∨1)) for the score function of p_0*\mathcal{N}(0,t\boldsymbol{I}_d), where n and d represent the sample size and the dimension, t is bounded above and below by polynomials of n, and p_0 is an arbitrary sub-Gaussian distribution. As a consequence, this yields an \widetilde{O}\left(n^{-1/2} t^{-\frac{d}{4}}\right) upper bound for the total variation error of the distribution of the sample generated by the diffusion model under a mere sub-Gaussian assumption. If in addition, p_0 belongs to the nonparametric family of the \beta-Sobolev space with \beta\le 2, by adopting an early stopping strategy, we obtain that the diffusion model is nearly (up to log factors) minimax optimal. This removes the crucial lower bound assumption on p_0 in previous proofs of the minimax optimality of the diffusion model for nonparametric families.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-zhang24bv, title = {Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions}, author = {Zhang, Kaihong and Yin, Heqi and Liang, Feng and Liu, Jingbo}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {60134--60178}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/zhang24bv/zhang24bv.pdf}, url = {https://proceedings.mlr.press/v235/zhang24bv.html}, abstract = {We study the asymptotic error of score-based diffusion model sampling in large-sample scenarios from a non-parametric statistics perspective. We show that a kernel-based score estimator achieves an optimal mean square error of $\widetilde{O}\left(n^{-1} t^{-\frac{d+2}{2}}(t^{\frac{d}{2}} \vee 1)\right)$ for the score function of $p_0*\mathcal{N}(0,t\boldsymbol{I}_d)$, where $n$ and $d$ represent the sample size and the dimension, $t$ is bounded above and below by polynomials of $n$, and $p_0$ is an arbitrary sub-Gaussian distribution. As a consequence, this yields an $\widetilde{O}\left(n^{-1/2} t^{-\frac{d}{4}}\right)$ upper bound for the total variation error of the distribution of the sample generated by the diffusion model under a mere sub-Gaussian assumption. If in addition, $p_0$ belongs to the nonparametric family of the $\beta$-Sobolev space with $\beta\le 2$, by adopting an early stopping strategy, we obtain that the diffusion model is nearly (up to log factors) minimax optimal. This removes the crucial lower bound assumption on $p_0$ in previous proofs of the minimax optimality of the diffusion model for nonparametric families.} }
Endnote
%0 Conference Paper %T Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions %A Kaihong Zhang %A Heqi Yin %A Feng Liang %A Jingbo Liu %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-zhang24bv %I PMLR %P 60134--60178 %U https://proceedings.mlr.press/v235/zhang24bv.html %V 235 %X We study the asymptotic error of score-based diffusion model sampling in large-sample scenarios from a non-parametric statistics perspective. We show that a kernel-based score estimator achieves an optimal mean square error of $\widetilde{O}\left(n^{-1} t^{-\frac{d+2}{2}}(t^{\frac{d}{2}} \vee 1)\right)$ for the score function of $p_0*\mathcal{N}(0,t\boldsymbol{I}_d)$, where $n$ and $d$ represent the sample size and the dimension, $t$ is bounded above and below by polynomials of $n$, and $p_0$ is an arbitrary sub-Gaussian distribution. As a consequence, this yields an $\widetilde{O}\left(n^{-1/2} t^{-\frac{d}{4}}\right)$ upper bound for the total variation error of the distribution of the sample generated by the diffusion model under a mere sub-Gaussian assumption. If in addition, $p_0$ belongs to the nonparametric family of the $\beta$-Sobolev space with $\beta\le 2$, by adopting an early stopping strategy, we obtain that the diffusion model is nearly (up to log factors) minimax optimal. This removes the crucial lower bound assumption on $p_0$ in previous proofs of the minimax optimality of the diffusion model for nonparametric families.
APA
Zhang, K., Yin, H., Liang, F. & Liu, J.. (2024). Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:60134-60178 Available from https://proceedings.mlr.press/v235/zhang24bv.html.

Related Material