Improved Convergence Rate for Diffusion Probabilistic Models
Authors: Gen Li
Yuchen Jiao
Venue: ICLR 2025 Spotlight (2025)
Keywords: score-based generative model
diffusion model
probability flow ODE
randomized learning rate
Primary area: learning theory

Abstract: Score-based diffusion models have achieved remarkable empirical performance in the field of machine learning and artificial intelligence for their ability to generate high-quality new data instances from complex distributions. Improving our understanding of diffusion models, including mainly convergence analysis for such models, has attracted a lot of interests. Despite a lot of theoretical attempts, there still exists significant gap between theory and practice. Towards to close this gap, we establish an iteration complexity at the order of $d^{1/3}\varepsilon^{-2/3}$, which is better than $d^{5/12}\varepsilon^{-1}$, the best known complexity achieved before our work. This convergence analysis is based on a randomized midpoint method, which is first proposed for log-concave sampling (Shen & Lee, 2019), and then extended to diffusion models by Gupta et al. (2024). Our theory accommodates $\varepsilon$-accurate score estimates, and does not require log-concavity on the target distribution. Moreover, the algorithm can also be parallelized to run in only $O(\log^2(d/\varepsilon))$ parallel rounds in a similar way to prior works.

Published as a conference paper at ICLR 2025
IMPROVED CONVERGENCE RATE FOR DIFFUSION PROBABILISTIC MODELS
Gen Li
Yuchen Jiao"
Department of Statistics
Department of Statistics
The Chinese University of Hong Kong
The Chinese University of Hong Kong Hong Kong
Hong Kong
genli@cuhk wwuuhh.edu.ha edu.hk
yuchenjiaoBcuhke edu hk
ABSTRACT
Score-based diffusion models have achieved remarkable empirical performance the field of machine learning and artificial intelligence for their ability to generate high-quality new data instances from complex distributions. Improving our un- derstanding of diffusion models, including mainly convergence analysis for such models, has attracted a lot of interests. Despite a lot of theoretical attempts, there still exists significant gap between theory and practice. Towards to close this gap, we establish an iteration complexity at the order of d g-/3 which is better than d5/12g-1, the best known complexity achieved before our work. This convergence analysis based on a randomized midpoint method, which is first proposed for log-concave sampling (Shen & Lee, 2019), and then extended to diffusion models by Gupta et al. (2024). Our theory accommodates E-accurate score estimates, and does not require log-concavity can also be parallelized to run in only Ollog" (d/=)) parallel rounds in a similar way to prior works.
the target distribution. Moreover, the algorithm
INTRODUCTION
Score-based diffusion models are class of generative models that have gained prominence in the field of machine learning and artificial intelligence for their ability to generate high-quality new data instances from complex distributions (Dhariwal & Nichol, 2021; Ho et al., 2020; Sohl-Dickstein et al., 2015; Song & Ermon, 2019; Song et al., 2021). These models operate by gradually transform- ing noise into samples from the target distribution through denoising process guided by pretrained neural networks that approximate the score functions. In practice, score-based diffusion models have demonstrated remarkable performance in generating realistic and diverse content across vari- ous domains (Croitoru et al., 2023; Ramesh et al., 2022; Rombach et al., 2022; Saharia et al., 2022; Li & Jiao, 2025), achieving state-of-the-an performance in generative AI.
The development of score-based diffusion models is closely related to the theory of stochastic pro- cesses. At a high level, we consider forward process:
Xo add noise X1 add noise add noise XT,
which draws sample from the target data distribution (i.e.. Xo Pdata). and then progressively diffuses it to Gaussian noise over time. The key step of the diffusion model is to construct a reverse process:
Yy denoise
denoise
dengise
Yr-1
Yo:
d satisfying Y, RJ X, for all t, which starts with pure Gaussian noise (i.c., Yr ~ (O Ia)) and gradually converts back a new sample Yo sharing a similar distribution the most crucial step of the diffusion model lies in effective design of the reverse process. To accomplish this goal, Y--1 in each step typically obtained from Y, with the aid of score functions
Xp. Evidently,
"The authors contributed equally.

---

Published as a conference paper at ICLR 2025
(st = Px.....). which pre-trained by means of score matching techniques (e.g.. Hyvärinen & Dayan (2005); Ho et al. (2020); Hyvärinen (2007); Vincent (2011); Song & Ermon (2019); Pang et al. (2020)).
Due to the impressive empirical success, in the past few years, there have been a lot of works exploring the convergence of diffusion models (De Bortoli, 2022; Gao et al., 2023; Lee al., 2022; Benton et al., 2023; Chen et al., 2023; Li et al., 2023; 2024c; Gupta et al.,
2023; Chen et al., 2022;
2024; Chen al., 2024b; Li al., 2024a; Li & Yan, 2024a; Huang et al.. 2024a: Li & Cai, 2024; Li & Yan, 2024b; Huang et al., 2024b; Liang et al.. 2025; Li et al., 2024b). They typically treat the score matching stage as blackbox and study how the sampling steps T and the score estimation eлror will affect the sampling accuracy. Given the observation that there still exists huge gap between prior theories and practice, this paper is devoted to improving the convergence theory for diffusion models.
1.1 MOTIVATION
Following the most existing works, let's focus on the total variation distance between distributions of the target data and generated samples. Let d be the dimension, and denote the accuracy which means the total variation is smaller than E. For the general target distribution, Benton et al. (2023) provides first linear d-dependency rate with iteration complexity d/ Later on, Li al. (2024c) achieves an improved complexity scaling as d/e, while with burn-in cost d².
However, such kind of result is still far away from practical observations. For example, for two typical image datasets, CIFAR- 10 with d = 32 x 32 x 3 3072 and ImageNet 256 x 256 with = 256 256 x 3 196608, it is sufficient to use about 50 steps generate good samples (Song et al., 2021; Nichol & Dhariwal, 2021), which is much smaller than the theoretical requirement. To close this gap. people try to derive faster convergence rate through exploiting extra data distribution properties, such as low-dimensional structure (Li & Yan, 2024a) and smoothness of score functions (Gupta et al., 2024; Chen et al., 2024b). Following this line of work, the scope of this paper lies in establishing some convergence theory for diffusion models towards aligning more closely with practical requirements.
1.2 OUR CONTRIBUTIONS
Focusing on the diffusion models with L-smooth score functions, this paper develops an improved iteration complexity following (up to some logarithmic factors):
/3 -233
which is inspired by the randomized mid-poin point design (Shen & Lee, 2019; Gupta et al., 2024). In what follows, let us make a brief comparison between our results and the state-of-the-art results about the convergence rate of score-based generative models.
Comparison under smoothness condition. Similarly, Chen al. (2024b) also studied the convergence theory by assuming smooth score functions. Recently, the iteration complexity is improved by Gupta et al. (2024); Chen et al. (2024b) in this setting, which, to ensure s- This means that convergence rate improves prior
accuracy, scales (L //12 -1). works by factor of 2/12
Comparison under general condition. Without the smoothness condition on score func- tions, Benton et al. (2023) proved an iteration complexity at the order of de de- which first exhibits linear dependency in the data dimension d. This bound is improved to Öd/e) by Li et al. (2024c) when the number of steps is larger than (dd²). In comparison, to achieve e-aceuracy, our theory improves these works provided that the Lipschitz condi- tions of score functions satisfy
L L< 2/33 4/3 for > 1/2 or L 2/ 1/3 for 1/2
Hopefully, such relations be satisfied in most real cases. for example, considering Im- ageNet 256 x 256, this requirement becomes L < 3381 for ss and L < 72845 for a 0.1.
2

---

Published as a conference paper at ICLR 2025
2 PRELIMINARY
In this section, we introduce some basics and notations score-based generative models. The diffusion generative model typically encompasses two processes: forward process and reverse process, as described below.
Forward process. Starting from Xo drawn from some target distribution Pdata: the forward pro- cess evolves as follows:
X, = vaiii +
IstsT,
(I)
where 0 < < 1, and s is a sequence of independent noise vectors drawn from W, i.idd (0 Ia). In addition, let's define
~
II ake 1
which will be helpful in our following analysis. Using this definition, X, can be expressed in closed form as X, Xo + v1 a₂ W. with W, ~ (N Ia). The diffusion models draw lot of motivations from the stochastic differential equations. Hence, let's also introduce the continuous- time limit of the forward diffusion process, which can be modeled as
dr 1 VI-7
dx,- =
dB,, for 0 <T<
(3)
where B, denotes some Brownian motion.
Reverse process. The core of diffusion models lies in constructing a reverse-time process with d nearly identical marginals as the forward process, namely, Y, R X,. Fortunately, it is shown that there exists some probability flow ODE
dY, 2(1 r) (Y, + Vloggx, (Y))
which can achieve our goal, such that if we start from Yo px for any S To it can
be ensured that Y, & X, for all 0 < 1. Then the design of reverse process is equivalent to discretize the above ODE process (4), as well as estimate V px,,,x, function.
px,, which is also called score
Score functions. The score functions are crucial for score-based generative modeling, and the definition of score function is follows.
Definition 1. The score function, denoted by sf Rd - od-RRd (1 < T), is defined as
st (x) = V Vlo 1 ae J Pxo x, (ro x) Vārzo)dro
1sts (5)
Following the same way as prior analysis, we assume access to faithful estimates of the score func- tions of across all intermediate steps i as following.
Assumption 1. We assume access to an estimate st(-) for each st(+) with the averaged e score estimation error
Exwgge (x) (x)
2
(6)
T
T
In addition, we mainly focus on the case with smooth score functions in this paper, which is stated below.
Assumption 2. Assume that st (x) and s (x) are Lipschitz all such that
(x1) (x2))112 & L|
x02 l|
(7a)
||<((1)) se(x2)l12 T.l 22 2|2-
(7b)
3

---

Published as a conference paper at ICLR 2025
Target data distribution. Following prior works, also need the following assumption the target data distribution Pdata to establish our theory.
Assumption 3. We assume that the target distribution Pdata has bounded second-order moment in the sense that
: = 2 < TER
for arbitrarily large constant CR >
Here, this assumption requires the second-order moment of Pdata be exceedingly large (given that the exponent CR can be arbitrarily large), which is a mild assumption. However, there exist exceptions including extremely heavy-tailed or non-smooth distributions. For example, densities decaying slower than 1/x" or purely discrete data may not align with our theoretical framework.
3
MAIN RESULTS
In this section, we first introduce a new score-based sampler with randomized midpoints, which is modified from Gupta al. (2024) for ease of analysis. Then, we prove faster convergence rate for this sampler based on new analysis framework, which might be useful for improving convergence guarantees for other variations of samplers. Finally, we also provide a parallel sampling strategy for our sampler following the similar idea from prior works (Gupta et al., 2024; Chen et al., 2024a).
3.1 ALGORITIIM
This part is devoted to explaining the details of our score- score-based sampler with randomized midpoints. Before proceeding, let's first specify the choice of learning rates to be used in our sampler.
Randomized schedule. schedule
Similar to prior works, we adopt the following randomized learning rate
N 04 (nif kt-1), for 2
+1, 1.....77
(9a)
where Unif denotes the uniform distribution, and
1
ū ag clār(1 - ār) log
and
(9b)
Teo
T
for sufficiently large constants co: c1 0 obeying c1/co sufficiently large.
Moreover, for ease presentation, we let K = c2Llog log for some constant 02 > such that sa sufficiently large, and N 27' Then define for O,..., , N, and 0. K 1,
2m = ar kN and Th == Ty 4x -n+1
(9c)
which satisfy the following lemma. The detailed proof of this result can be found in Li & Jiao (Appenii B.1).
Lemma 1. Our choice of learning schedules (9) satisfies
Fk
Pk.n
C log
- To,0 5 ât < Tou
TK.0 5 --i āi S T
and
Tk.n
Tk.n
T
(10)
Sampling procedure. With the learning schedule hand, we are now ready to introduce sam- pling procedure. The algorithm is actually a discretization of the probability ODE flow incorporated
with some stochastic noise, which proceeds as follows. We start from Yo ~ (O Ia). and then for k O...., K 1, we keep updating Yy through the formula:
Tk+1.0
T Tk.N Zk.
Ye+1
YE.N
(11a)
V
1
Tk
Tk.N
4

---

Published as a conference paper at ICLR 2025
where Zk i... NN I) and for n = I,...,., .N we compute
Yk,
Yn
ST +1- (Yk))
ST FNN -i+1 (Yk,r)
0h.0 2(1 Tk.0) 3//2 (Tk.0 Fx.00) +
2(1 Th, 3//2 (Th
F22,)
Tkin
V1
1
+ 8T 4/4 n+ 1-)
2(1 Th,n 33/2 (Tk,n - Tk.n).
(11b)
Here, we let Y2,0 Ys. Notice that for each step to calculate Yk. only one additional score evaluation for ST 2/- -n+2 ( is needed. This implies that the total iteration complexity is
KN =2T.
3.2 CONVERGENCE ANALYSIS
We are now positioned to present the convergence guarantees - measured by the total variation distance between the forward and the reverse processes for the proposed sampler (11). The proof is postponed to Section 4.
Theorem 1. Suppose that Assumptions 1, 2. and 3 hold true. Then the sampling process (11) with the learning rate schedule (9) satisfies
11,
5/2
TV (pdata: PVx
+ C'score log 1/2 T
(12)
T3/2
for some constant C O large enough.
We now take moment to discuss the main implications of Theorem 1.
Iteration complexity. Let's focus on the first term in (12), which corresponds to discretization error, and ignore the score estimation error. To ensure TV (Pdata,Pyx) I E, it sufficient to choose
T L/ 5/3 T
2//3
As far as we know, the existing iteration complexity guarantees (with sub-linear dependency on d) are ((15/886/12--1) achieved in Gupta et al. (2024) and ((L2d derived in Chen et al. (2024b). Our theory improves the prior results with at least /112
Dependency of score estimation error. Turning attention to the second term, the sampling ac- curacy scales Escore log!/2r, I,, suggesting that sampler is stable to imperfect score estimation. In comparison, the existing results (with sub-linear dependency on d) scale as /2/22t/122scom log T and L 1 log I in Gupta et al. (2024) and Chen et al. (2024b). respectively. Our theory exhibits a better dependency on score estimation error, which similar to the results Chen al. (2022) and Benton et al. (2023).
Lipschitz condition of score functions. is noteworthy that our better iteration complexity holds under the condition of Lipschitz continuity for score functions. Without this condition, the best results are Óde -2) and Õdd + d)), which are achieved in Benton et al. (2023) and Li et al. (2024c), respectively. Our theory is better than such result when the Lipschitz constant for the score functions satisfies I /2/3 for > d/1/22 or T, < 11/3 for < d-1/2 and it is still unknown how to achieve sub-linear dependency d in the general case.
Finally, we remark that the extension to non-Lipschitz settings is significantly more challenging due to the critical role the smoothness assumption plays our analysis. Previous analysis on diffusion models focus primarily stepwise error propagation, analyzing how enrors at one step affect the next. In contrast, our randomized design requires tracking error propagation across multiple steps simultaneously. which necessitates uniform control over these errors. Without smoothness, only bighbbrobbbility bound that depends on the dimension can be established, which hard to use compared to the uniform bound and may result in worse bound since it scales with d.
5

---

Published as a conference paper at ICLR 2025
3.3 PARALLEL SAMPLING
In this section, we provide a way to do parallel sampling for our proposed sampler that needs the similar number of parallel rounds as prior works (Gupta al., 2024), while the number of parallel processors here is significantly reduced. In the following, we first introduce the parallel sampling procedure, and then present the theoretical guarantee. The analysis is postponed the Section 5.
Details of parallel sampling procedure. In the parallel sampling, all procedures are the same as the above sampler (11), except that we will update Yu, for n 1,.., NN at the same time. Specifically, we first initialize
Yo.k.
Yx
n 1, N.
(13a)
Tk
V1-
Tk.0
Then we update all YE. for M rounds simultaneously: at the m-th round, we update Ynkk,n for 1, I,...,A N in the following way:
Ymnka
Y2
8T 2/ (Vs)
8T AN i+1 (Y m 1,
2(1 33/2 (Tk,0 Fk.0) +
(fk Fx.s)
Tkn
VI
0g.0
2(1 Tk.i) 33/2
1=1
8T 3 n+2 Y 1k
+
(fr - Tk,n).
(13b)
2(1- pkin-1 33/2
Finally, we compute
Y++1 Tk+1.0 VoriLyyar.. YAN + 1 1-TK,N
Tk+ TK.N 7kz
(13c)
TK.N
and we complete the update from Ys to Yx-1 in the parallel way. In this parallel setting, the total number of parallel rounds to yield sample YK is MK, and N parallel processors are needed. We remark that the implementation of this parallel algorithm assumes that the GPU memory is capable of supporting score estimations for a large batch of data simultaneously. Parallelizing across multiple GPUs introduces additional communication overhead, which may impact efficiency.
Theoretical guarantee of parallel sampling. The convergence guarantees for the above parallel sampling is as follows, whose proof can be found in Section 5: Theorem 2. With the same setting Theorem 1, it is sufficient to choose
/13 2/3 T
MK 2 I. log2 T,
and
Eccore S e² log-
(14)
g2/3
to achieve TV (pdatai PYx) S e for the sampler (13).
Finally, let briefly compare our theory with the prior works. This theorem states that the parallel sampler achieves E-accuracy with respect total variation distance through using O(log"(Ld/e) (Ld/=)) parallel rounds, which is similar to Gupta et al. (2024); Chen et al. (2024a). In addition, we only need /3 ///-3/)-2/3) parallel processors, which improves their results significantly.
4 ANALYSIS
This section is devoted to establishing Theorem 1. Before proceeding, we find it helpful to introduce the following notations. Without abuse of notations, we use X, to denote the continuous process as follows:
X, 4 vi 7x,
7o + VTZ, with Z ~ NNO, I), for 0 0 11
(15)
and the corresponding score function is
* (a) = Voogxx, (x) -
Pxa Px, (2o (xo|=)(< (x- v1 7.00) Idzo-

---

Published as a conference paper at ICLR 2025
In addition, we rewrite the sampling process with the continuous index following:
Tk
YE
8Tr.0 (Yx)
8 (Yrr.)
(Tk.0 -k.0)) +
Σ
2(1 Tk,,) (Fk,i-1 Fk.x)
Tk,n
VI
0k.0
2(1 Tk) 3/22
i=1
(Y Tk 1)
8Ta.
(Tk Tkim),
2(1 Tk }3/2
and
Te+10 VFn.N +
Th+1100 - Tk,N Z
Y&+1 =
TK,N
1 TK,N
where Yo 1), and Z& 1). Here, Yr... corresponds to the Yk,n in the discrete case. In the following, it is enough to consider T > cog T' for some constant cg > 0 large enough; otherwise, the desired bound holds trivially.
Before diving into the details of the proof, we provide some core institution of our algorithm and the overview of the proof. Our algorithm is designed based on the following institution. First, by injecting noise into the probability flow ODE (ef. (16)), we transfer the sampling task to one of discretizing the ODE with small error (see Lemma 2). This step contributes the main improvement of our work over prior works, which provides a simple framework for transferring the sampling task discretizing the ODE (16) with small error. Once this reduction is established, we make use of the techniques proposed by Shen & Lee (2019) and Gupta et al. (2024), utilizing randomized midpoints to improve efficiency in estimating the ODE solution (see Lemma 3). The final algorithm is designed based on the discretization form of ODE (16), where estimates of X Tu, are iteratively computed using this form and are inserted into the subsequent estimates.
In our algorithm, the main sources of error include discretization error controlled in Lemma 3, estimation error arising from the approximation of X which bounded in Lemma 4, and the initialization and early stopping errors, which are controlled in Lemma 5 using techniques similar to prior works. The proof can be divided into three steps.
4.1 STEP INTRODUCE THE AUXILIARY SEQUENCE
Let T5 (7- (1) Frzz or, = defined through the following ODE
(x+) V1 2(1 2(1-7)377 dr.
JT
(16)
Then, we have the following result. The detailed proof can be found in Li & Jiao (2024)(Appendix B.2).
Lemma 2. It can be shown that
① +m (X,,) ) $ X
(17)
Moreover, assume that Xo X To.. Then we have for S K,
8 Tk+1. o T..0 NUN (8x)+ +
Tk+1.0 TK.N
Zi X 11.01
(18)
TK.N
1 1-TKNN TK.N
where Zy 1id. NOO.,). I).
Given the definition of Nx, we make the following decomposition:
TV S (pdasaa, Px,)) +
(19a)
and
1 TV² (Pxx)) < KL (pxx llpr)) - KL
K (p (Prommin))
7

---

Published as a conference paper at ICLR 2025
K-1
1 = 2 (px, (lxx))
1 + B Bomax k=0
KL (P
( (.12k) PY ( (.12%))
2
(19b)
where make of Pinsker's inequality and the data proceespoessngggggg inequality. In the next step, we will bound the divergence between P PX,-1 and 1 and the remaining terms can be controlled easily, which is left to the final step.
4.2
STEP 2: CONTROL THE DIVERGENCE BETWEEN PR AND PV++1 1
Based the update rule for Y Tu we let
y Mrk.m
Vrk.o
8 8T (Uru,o)
(Tk.0 (Tk.0- -k,,0)
Σ
n-1
Srk, (Urr.s) (Th,i-1 FR.s))
2(1 Tk) 3/22
2(1 Tk 3/2
Tknn
Th.0
i=1
87k.. (Wrr.n
(Trma- 1 Tk,)),
2(1 Tknn )3/2
for n ,,...,,.... N. Then notice that X and Ya+I/Yo are both normal distributions with the
same variance T TE.N and different means v
1-re+10 1
T P (Xx) and / T-Tu,N VYK.N
1-Te+10
1-7A,N
T-TU,N
respectively. This tells that
KL (.12x)) PY (-1 2(Tk+1.0 Tk.N)
Th++1.0
I1y7n.N - IT 11
(20)
when set FrA Vra.o Ik. and T is defined ITE,N T +Te,, (IK).
Towards controlling the difference between VTa, and ITK,ND let's consider the ODE trajectory be- ginning from ZTk. 2k, and define
(xk((Fk) = VI Thin
Irk.n
ITk.o
Sru.0 (ITe,O)
33/2 (Tk,0 Fk,00
-TTk0
2(1 - Tk.0)3/2
n-1
8Tu.
(ITH.t)
Tk 3//2 (Fk,5-1 Fk.i))
8Tu.n (Witee 1)
(Tr.n-1 - Then),
2(1
2(1 Tk 33/2
(21)
which denotes the discretization and estimation error of the ODE process (16).
Given an initialization point TT.,0 = Tk. the term ((T: := 2(1-r)372 depends only on т. Solving (16) is equivalent to calculating the integral of 0(T; Consequently, it is natural for the algorithm to approximate the integral by discretizing and estimating 0(T; at some discrete time points. The following lemma controls the estimation error, and the underlying intuition lies in controlling the error between the true value and its estimation obtained through this discretization as defined in (21). The detailed proof can be found in Li & Jiao (2024)Appendix A.1). Similar errors also analyzed in Gupta et al. (2024) (Appendix A.1) under an exponential integrator formulation. Our derivation adapts these ideas to the context of the probability flow ODE discretization in this work.
(x+)
Lemma 3. For any ls and n, it can be seen that with probability at least 1 1100
L'dlog T
ERsppx [II
(fr,511 -Fkk))
175
273
N log 2 T T
Fr
-x. B LN -11
(22)
1=
where e is defined in (6).
With the above relation, we can bound the divergence as following. The detailed proof can be found in Li & Jiao (2024) (pppendix A.2).
8

---

Published as a conference paper at ICLR 2025
Lemma 4. According to Lemma it can be shown that
[KL (PR ( (1x))) PY (- (-1xx)) ExxMpx
L
L'dlog T
log T
N-1
x
73
7- 2
-14
==
(23)
where eT-'N- -b+1 is defined in (6).
4.3 STEP 3: PUTTING EVERYTHING TOGETHER
The remaining terms (19) can be bounded through the following lemma. The detailed proof can be found in Li & Jiao (ApennAppendix B.3).
Lemma 5. Under our choice of learning schedule (9), we have
TV(datta: P S TIō and (L (IY)) S T10
(24)
Inserting (24) and (23) into (19) leads to
TV (pdata, PYg
1
V
1
Led
T
+ E eoo log x
2222 2
Ecorre log! 1/2 12
710
710
73
73/2
and we conclude the proof here.
5 ANALYSIS FOR PARALLELIZATION (THEOREM 2)
By comparing the update rules for Yn,n and M, it is natural to control the difference of the following two sequences:
Dre.
Vrk.o
ST.. (Ure.o)
8 (Nrx.)
2(1 Tk.0) 3/2 (TK.0 -k.00) +
2(1 3//2 (Tr.i-1 FR.s))
Tknn
V
Oh.0
(H
8
2(1 Tk,n 33/2 (TR Tk,a),
and
Mm Tk
Mra
8TA.0 (NTn.o)
87a. (ym 1.m0.)
(Tk,0 =kk.0)
3/2 (Fr Fk.s))
2(1 T2 33/2
2(1 Th. 33/2
Tkin
Tk.0
TT. (1/m 1.
(Tk,n-1
Tk.n)
2(1 1k, 3/2
The above update rules, together with the Lipschitz condition of score estimates, lead to
ym. Vrr ll/
Log T
| 1.72. Vru. 1l,
VI Tk,n
T
V1 - Th.s
1=1
Applying the above relation recursively gives
JyM.TKn
VTk.
NN T
|1 - Brumll2
1
max
max
V1
Tk,
T
V1 Tk.n
poly(T))
1//3 1/g which guarantees
provided that M 2 log T and T No T. Thus as long as N
2273
that T > Lal/3 5/3 we can get the desired result immediately through just inserting the above 2273
enror boound into Lemma 4. We omit the details here due the similarity.

---

Published as a conference paper at ICLR 2025
6 DISCUSSION
In this paper, we establish faster convergence rate for diffusion probabilistic models, which scales as L assuming smooth score functions. Our theory achieves at least (2/33///22--1 im- provement over prior works (Gupta al., 2024; Chen al., 2024b), and thereby aligns more closely with practical requirements. Recent researches (Benton et al., 2023; Li et al., 2024c) have shown an O(de dependence for diffusion models without the assumption of smoothness. However, remains unclear whether any algorithm can achieve sub-linear dependence on d in the absence of smoothness. We leave this as an open question for future research. Moreover, the benefit of the randomized design in work relies heavily the deterministic nature of ODE process. It is still unclear for us how to adapt this approach to deal with the inherent stochasticity in SDEs while main- taining similar improvements. This will also be left as future work. In addition, it may be feasible to apply your analysis framework to improve the bound for other variants of samplers such as the Langevin algorithm. Furthermore, estimating the Lipschitz constant in real-world cases would be highly beneficial, potentially broadening the applicability our results.
ACKNOWLEDGMENTS
Gen Li is supported in part by the Chinese University of Hong Kong Direct Grant for Research and the Hong Kong Research Grants Council ECS 2191363.
REFERENCES
Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly d-linear con- vergence bounds for diffusion models via stochastic localization. The Twelfth International Conference on Learning Representations, 2023.
Haoxuan Chen, Yinuo Ren, Lexing Ying, and Grant Rotskoff. Accelcrating diffusion models with parallel sampling: Inference sub-linear time complexity. arXiv preprint arXiv:2405.15986 2024a.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, pp. 4735-4763, PMLR, 2023.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint 22Xiv:2209.11225, 2022.
Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ode is provably fast, Advances in Neural Information Processing Systems, 36, 2024b.
Florinel-Alin Croitoru, Vlad Hondru, Radu Tudor Ionescu, and Mubarak Shah. Diffusion models in vision: A survey. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(9): 10850910869, 2023.
Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. Transactions on Machine Learning Research, 2022.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-8799 2021.
Xuefeng Gao, Hoang M Nguyen, and Lingjiong Zhu. Wasserstein convergence guarantees for a general class of score-based generative models. arXiv preprint arXiv:2311.11005 2023.
Shivam Gupta, Linda Cai, and Sitan Chen. Faster liffusion-bused sampling with randomized mid- points: Sequential and parallel. arXiv preprint arXiv:2406.00924 2024.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851 2020.
10

---

Published as a conference paper at ICLR 2025
Daniel Zhengyu Huang, Jiaoyang Huang, and Zhengjiang Lin. Convergence analysis of probability flow ode for score-based generative models. arXiv preprint arXiv:2404.09730, 2024a.
Zhihan Huang, Yuting Wei, and Yuxin Chen. Denoising diffusion probabilistic models are optimally adaptive unknown low dimensionality. arXiv preprint arXiv:2410.1877 2024b.
Aapo Hyvärinen. Some extensions score matching. Computational statistics data analysis, (5):2499-2512, 2007.
Aapo Hyvärinen and Peter Dayan. Estimation of non-normalizzd statistical models by score match- ing. Journal of Machine Learning Research, 6(4), 2005.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. Advances Neural Information Processing Systems, 35:22870-22889 2022.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, pp- 946-985, PMLR, 2023.
Gen Li and Changxiao Cai. Provable acceleration for diffusion models under minimal assumptions. arXiv preprint arXiv:2410.232855 2024.
Gen Li and Yuchen Jiao. Improved convergence rate for diffusion probabilistic models. arXiv preprint arXiv:2410.13738, 2024.
Gen Li and Yuchen Jiao. Provable efficiency of guidance in diffusion models for general data distribution. arXiv preprint arXiv:2505.01382, 2025.
Gen Li and Yuling Yan. Adapting to unknown low-dimensional structures score-based diffusion models. arXiv preprint arXiv:2405.1486/ 2024a.
Gen Li and Yuling Yan. o(d/t) convergence theory for diffusion probabilistic models under minimal assumptions. arXiv preprint 11XI::2409.18959 2024b.
Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Towards faster non-asymptotic convergence for diffusion-based generative models. arXiv preprint (rXiv:230660925/ 2023.
Gen Li, Yu Huang, Timofey Efimov, Yuting Wei, Yuejie Chi, and Yuxin Chen. Accelerating con- vergence of score-based diffusion models, provably. In Forty-first International Conference on Machine Learning, 2024a.
Gen Li, Zhihan Huang, and Yuting Wei. Towards mathematical theory for consistency training in diffusion models. arXiv preprint arXiv:2402. 07.002 2024b.
Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. A sharp convergence theory for the probability flow odes of diffusion models. arXiv preprint arXiv:2408.02322 2024c.
Jiadong Liang, Zhihan Huang, and Yuxin Chen. Low-dimensional adaptation diffusion models:
Convergence in total variation. arXiv preprint arXiv:2501. 2025.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International conference on machine learning, pp. 8162-8171. PMLR, 2021.
Tianyu Pang, Kun Xu, Chongxuan Li, Yang Song. Stefano Ermon, and Jun Zhu. Efficient learn- ing of generative models via finite-difierence score matching. Advances in Neural Information Processing Systems, 33:19175-11188 2020.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. arXiv preprint arXiv:2204.06/25,, 1(2):3, 2022.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF confer- on computer vision and pattern recognition, pp. 10684-10695 2022.

---

Published as a conference paper at ICLR 2025
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. Photorealistic text-to-image diffusion models with deep language understanding. Advances in neural informa- sion processing systems, 35:36479-36494, 2022.
Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log-concave sampling. Advances in Neural Information Processing Systems, 32, 2019.
Jascha Sohl-Dicksteiin Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learn- ing. pp. 2256-2265. PMLR, 2015.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In Interna- fional Conference on Learning Representations, 2021.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Pascal Vincent. A connection between score matching and denoising autoencoders. Neural compu- fation, 23(7):1661-1677 2011.
12


Reviews:
[{"review_id": "lifg8HKvQt", "reviewer": "Reviewer_EyNz", "summary": "The paper focuses on enhancing the theoretical convergence rate of diffusion models, which are widely used for high-quality data generation in various machine learning applications. Traditional analyses show a significant gap between theoretical complexity and the number of steps needed in practice for good performance. This work introduces a faster convergence rate of $O\\left(d^{1 / 3} \\epsilon^{-2 / 3}\\right)$, an improvement over previous bounds, achieved by adapting a randomized midpoint method. The authors' analysis allows for smooth, $\\epsilon$-accurate score estimates without assuming restrictive properties like log-concavity in the data distribution. Additionally, they propose a parallel sampling technique that minimizes the number of parallel rounds required, further increasing efficiency.", "questions": "See weaknesses part above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Theorem 1 introduces a new convergence rate for diffusion models, specifically $O\\left(d^{1 / 3} \\epsilon^{-2 / 3}\\right)$, which is faster than previous results (e.g., $O\\left(d^{5 / 12} \\epsilon^{-1}\\right)$ by Gupta et al., 2024). This improvement relies on an adaptation of the randomized midpoint method from log-concave sampling and brings theoretical guarantees closer to practical performance.\n2. Theorem 2 paper presents an efficient parallel sampling method that reduces the number of parallel rounds needed while maintaining the improved convergence rate.", "weaknesses": "1. Theorem 2 describes an efficient parallel sampling method with fewer parallel rounds, but the practical implementation details are limited. like How does memory consumption scale with $d$ in parallel sampling? Are there specific cases or datasets where the parallel method might fail to produce substantial speedups due to communication overhead between processors? If so, what alternative strategies or adjustments would the authors suggest?\n2. Are there specific types of data distributions (e.g., multimodal, heavy-tailed) that the authors believe may not meet the framework’s assumptions?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FT9VtTWQPR", "reviewer": "Reviewer_yjdB", "summary": "This paper studies the diffusion models and proposes sampling method based on randomized midpoint for probability flow ODE.  Their method has an improved sequential iteration complexity as $Ld^{1/3}/\\epsilon^{-2/3}$ and similar parallel iteration complexity $\\log^2(d/\\epsilon)$, with measurement as total variance.", "questions": "- I am curious about the results when your method is applied to the implementation of diffusion models using SDEs", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper studies the complexity of the inference process of diffusion models, which is a problem of significane interest and practical importance in the related fields.\n\n- the sequential itertaion complexity is improved from $L^{5/3}d^{5/12}\\epsilon^{-1}$ to $Ld^{1/3}\\epsilon^{-2/3}$.", "weaknesses": "- This main drawback is the additional smoothness assumption on the score function and its estimation.\n\n- The algorithm and the proof presented in Lemma 3 are difficult to follow. It may be helpful to provide more detailed explanations or include additional diagrams for clarity.\n\n- Your method looks like N=poly(T)-stage Runge-Kutta method with random Runger-Kutta matrix. Then $\\varepsilon^{-1/N}$ iteration complexity is expected although such method needs higher order smooth for ode case [1]. Calling it the midpoint method seems somewhat misleading. \n\n[1]Convergence analysis of probability flow ODE for score-based generative models, Huang, Daniel Zhengyu, Jiaoyang Huang, and Zhengjiang Lin, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wENArgBWw6", "reviewer": "Reviewer_Twhm", "summary": "This paper studies the problem of sampling from a diffusion model, and provides an algorithm with the best known dimension dependence of $d^{1/3}$, an improvement over $d^{5/12}$ of previous work. It also improves the dependence on the score estimation error $\\epsilon$, from $1/\\epsilon$ to $\\epsilon^{-2/3}$. The algorithm uses the randomized midpoint method along with corrector steps, a strategy first proposed for diffusion by Gupta et. al. (2024). The authors show that a new analysis of this algorithm (with some modifications) achieves the improved iteration complexity bounds.", "questions": "- Is it possible to translate these techniques to obtain improved bounds for log-concave sampling in TV? Please update the paper to discuss any challenges in doing so.\n\n- Can you condense the core intuition and explain it in a proof overview? Please add a proof overview to the paper that explains the key insight relative to prior work in a condensed form.\n\n- Does this work have any implications for the setting where the score is not assumed to be Lipschitz? Please add a discussion of the challenges in translating these techniques to the non-Lipschitz setting, or what bound you could hope to get.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "Studies an important and well-studied problem and develops new techniques that allow the authors to show the best known iteration complexity. Perhaps surprisingly, as of this work, we have faster algorithms for sampling from diffusion models than for log-concave sampling.", "weaknesses": "While I appreciate the brevity of the paper, I feel that the core intuition could be explained better for easier digestion.\n\nOverall though, I don't have many complaints.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ez02YhgZqj", "reviewer": "Reviewer_FYHg", "summary": "This paper considers the well-studied question of sampling from a smooth distribution $p$ given approximate access to its score functions $\\nabla \\ln p_t$, where $p_t$ is $p$ convolved with some level of noise.\n\nRecent work has shown that this can be done for essentially arbitrary smooth distributions, with iteration complexity $L^a d^b/\\epsilon^{c}$ for progressively smaller constants $a,b,c$. Here $L$ is the Lipschitz constant for the score functions and score estimates. Recent works of Chen et al. and Gupta et al. culminated in bounds of $(a,b,c) = (2/3, 5/12, 1)$. The present work gives a clever analysis that pushes this down to $(1, 1/3, 2/3)$.\n\nWhile not explicitly written as such, the sampler the algorithms propose can be thought of as a predictor-corrector scheme: it alternates between reverse diffusion steps (implemented via a slight variant of the randomized midpoint method) and steps in which additional noise is added to the trajectory. The corrector steps allow one to essentially convert Wasserstein closeness between the algorithm and the true (continuous) reverse diffusion into KL closeness, so that the KL between the algorithm and the true distribution is small by chain rule for KL.", "questions": "I'm not sure I followed why one needs to modify randomized midpoint for the \"predictor\" part of the sampler, i.e. in the computation of the $Y_{k,n}$'s. Why couldn't one just run the predictor analysis in Gupta et al. off the shelf to get an analogue of Lemma 3?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "This result was quite surprising to me. It is a big open question to achieve $d^{1/3}$ dependence for log-concave sampling in KL, and I had expected that the result in the present paper would not be achieved until that milestone had been reached. \n\nThe key insight, which is somewhat buried in the notation, is the following. The prior works of Chen et al. and Gupta et al. similarly adopted a predictor-correct approach, but their corrector was based on running underdamped Langevin dynamics to keep the sampler stationary at a fixed noise level. But this required a discretization analysis for underdamped Langevin in KL; while it is conjectured that one can achieve $d^{1/3}$ dependence for this (and indeed, this is the best known rate one can achieve for Wasserstein), the best known analyses are currently stuck at $d^{1/2}$. \n\nThe authors of the present work sidestep this with an ingenious idea: instead of running underdamped Langevin at a fixed noise level, they simply add Gaussian noise in the corrector step and rescale. It is much more straightforward to see that this converts Wasserstein closeness to KL closeness. Instead of preserving the noise level however, this has the effect of increasing the noise slightly. But if the rescaling is chosen appropriately, it still remains on the trajectory of the reverse diffusion! By balancing appropriately between the progress the predictor step makes in reducing the noise level and the progress the corrector step undoes by raising the noise level, the authors are able to circumvent the issues from prior work and achieve the desired $d^{1/3}$ scaling. This idea of using a corrector step which raises the noise level while staying on the trajectory of the true reverse diffusion is simple and very nice.", "weaknesses": "My main complaint is that the writing is very dense and it was very hard from a quick glance to extract the key idea outlined above. If this work is to be accepted, the authors should make sure to include a technical overview section where they explain the intuition for how they are able to go beyond the prior works of Chen et al. and Gupta et al.\n\nThere might be some complaints about the fact that they need to assume Lipschitzness of the score and the score estimate, but note that no sublinear-in-$d$ bounds are known for diffusions under less stringent assumptions, so I wouldn't count this as a real downside.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)