review_iclr_bench/iclr_parsed/0xiJLKH-ufZ.txt

# ANALYTIC-DPM: AN ANALYTIC ESTIMATE OF THE OPTIMAL REVERSE VARIANCE IN DIFFUSION PROB## ABILISTIC MODELS

**Fan Bao[1][ ∗], Chongxuan Li[2 3][ †], Jun Zhu[1][ †], Bo Zhang[1]**

1Dept. of Comp. Sci. & Tech., Institute for AI, Tsinghua-Huawei Joint Center for AI
BNRist Center, State Key Lab for Intell. Tech. & Sys., Tsinghua University, Beijing, China
2Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China
3Beijing Key Laboratory of Big Data Management and Analysis Methods, Beijing, China
bf19@mails.tsinghua.edu.cn,chongxuanli1991@gmail.com,
_{dcszj, dcszb}@tsinghua.edu.cn_

ABSTRACT

Diffusion probabilistic models (DPMs) represent a class of powerful generative
models. Despite their success, the inference of DPMs is expensive since it generally needs to iterate over thousands of timesteps. A key problem in the inference
is to estimate the variance in each timestep of the reverse process. In this work,
we present a surprising result that both the optimal reverse variance and the corresponding optimal KL divergence of a DPM have analytic forms w.r.t. its score
function. Building upon it, we propose Analytic-DPM, a training-free inference
framework that estimates the analytic forms of the variance and KL divergence
using the Monte Carlo method and a pretrained score-based model. Further, to
correct the potential bias caused by the score-based model, we derive both lower
and upper bounds of the optimal variance and clip the estimate for a better result.
Empirically, our analytic-DPM improves the log-likelihood of various DPMs, produces high-quality samples, and meanwhile enjoys a 20× to 80× speed up.

1 INTRODUCTION

A diffusion process gradually adds noise to a data distribution over a series of timesteps. By learning
to reverse it, diffusion probabilistic models (DPMs) (Sohl-Dickstein et al., 2015; Ho et al., 2020;
Song et al., 2020b) define a data generative process. Recently, it is shown that DPMs are able
to produce high-quality samples (Ho et al., 2020; Nichol & Dhariwal, 2021; Song et al., 2020b;
Dhariwal & Nichol, 2021), which are comparable or even superior to the current state-of-the-art
GAN models (Goodfellow et al., 2014; Brock et al., 2018; Wu et al., 2019; Karras et al., 2020b).

Despite their success, the inference of DPMs (e.g., sampling and density evaluation) often requires
to iterate over thousands of timesteps, which is two or three orders of magnitude slower (Song et al.,
2020a) than other generative models such as GANs. A key problem in the inference is to estimate
the variance in each timestep of the reverse process. Most of the prior works use a handcrafted
value for all timesteps, which usually run a long chain to obtain a reasonable sample and density
value (Nichol & Dhariwal, 2021). Nichol & Dhariwal (2021) attempt to improve the efficiency of
sampling by learning a variance network in the reverse process. However, it still needs a relatively
long trajectory to get a reasonable log-likelihood (see Appendix E in Nichol & Dhariwal (2021)).

In this work, we present a surprising result that both the optimal reverse variance and the corresponding optimal KL divergence of a DPM have analytic forms w.r.t. its score function (i.e., the
gradient of a log density). Building upon it, we propose Analytic-DPM, a training-free inference
framework to improve the efficiency of a pretrained DPM while achieving comparable or even superior performance. Analytic-DPM estimates the analytic forms of the variance and KL divergence
using the Monte Carlo method and the score-based model in the pretrained DPM. The corresponding trajectory is calculated via a dynamic programming algorithm (Watson et al., 2021). Further, to

_∗Work done during an internship at Huawei Noah’s Ark Lab._ _†Correspondence to: C. Li and J. Zhu._


-----

correct the potential bias caused by the score-based model, we derive both lower and upper bounds
of the optimal variance and clip its estimate for a better result. Finally, we reveal an interesting
relationship between the score function and the data covariance matrix.

Analytic-DPM is applicable to a variety of DPMs (Ho et al., 2020; Song et al., 2020a; Nichol &
Dhariwal, 2021) in a plug-and-play manner. Empirically, Analytic-DPM consistently improves the
log-likelihood of these DPMs and meanwhile enjoys a 20× to 40× speed up. Besides, AnalyticDPM also consistently improves the sample quality of DDIMs (Song et al., 2020a) and requires
up to 50 timesteps (which is a 20× to 80× speed up compared to the full timesteps) to achieve a
comparable FID to the corresponding baseline.

2 BACKGROUND

Diffusion probabilistic models (DPMs) firstly construct a forward process q(x1:N **_x0) that injects_**
_|_
noise to a data distribution q(x0), and then reverse the forward process to recover it. Given a forward
noise schedule βn (0, 1), n = 1, _, N_, denoising diffusion probabilistic models (DDPMs) (Ho
et al., 2020) consider a Markov forward process: ∈ _· · ·_


_N_

_qM(xn|xn−1),_ _qM(xn|xn−1) = N_ (xn|[√]αnxn−1, βnI), (1)
_n=1_

Y


_qM(x1:N_ **_x0) =_**
_|_


where I is the identity matrix, αn and βn are scalars and αn := 1−βn. Song et al. (2020a) introduce
a more general non-Markov process indexed by a non-negative vector λ = (λ1, _, λN_ ) R[N]0[:]
_· · ·_ _∈_ _≥_


_qλ(x1:N_ _|x0) = qλ(xN_ _|x0)_ _qλ(xn−1|xn, x0),_ (2)

_n=2_

Y

_qλ(xN_ **_x0) =_** (xN _αN_ **_x0, βN_** **_I),_**
_|_ _N_ _|[√]_

_qλ(xn_ 1 **_xn, x0) =_** (xn 1 **_µ˜_** _n(xn, x0), λ[2]n[I][)][,]_
_−_ _|_ _N_ _−_ _|_

**_µ˜_** _n(xn, x0) =_ _αn−1x0 +_ qβn−1 − _λ[2]n_ _[·][ x][n][ −√]β[α]n_ _[n][x][0]_ _._
p

q


Here αn := _i=1_ _[α][i][ and][ β]n_ [:= 1][ −] _[α][n][. Indeed, Eq. (2) includes the DDPM forward process as a]_

special case when λ[2]n [= ˜]βn, where _β[˜]n :=_ _ββn−n_ 1 _[β][n][. Another special case of Eq. (2) is the denoising]_

[Q][n]

diffusion implicit model (DDIM) forward process, where λ[2]n [= 0][. Besides, we can further derive]
_qλ(xn_ **_x0) =_** (xn _αnx0, βnI), which is independent of λ. In the rest of the paper, we will_
_|_ _N_ _|[√]_
focus on the forward process in Eq. (2) since it is more general, and we will omit the index λ and
denote it as q(x1:N **_x0) for simplicity._**
_|_

The reverse process for Eq. (2) is defined as a Markov process aimed to approximate q(x0) by
gradually denoising from the standard Gaussian distribution p(xN ) = (xN **0, I):**
_N_ _|_

_N_

_p(x0:N_ ) = p(xN ) _p(xn_ 1 **_xn),_** _p(xn_ 1 **_xn) =_** (xn 1 **_µn(xn), σn[2]_** **_[I][)][,]_**

_−_ _|_ _−_ _|_ _N_ _−_ _|_
_n=1_

Y

where µn(xn) is generally parameterized [1] by a time-dependent score-based model sn(xn) (Song
& Ermon, 2019; Song et al., 2020b):


1
**_xn,_** (xn + βnsn(xn)) _._ (3)
_√αn_



**_µn(xn) = ˜µn_**


The reverse process can be learned by optimizing a variational bound Lvb on negative log-likelihood:


_Lvb =_ Eq


"−log p(x0|x1)+n=2DKL(q(xn−1|x0, xn)||p(xn−1|xn))+DKL(q(xN _|x0)||p(xN_ ))

X


1Ho et al. (2020); Song et al. (2020a) parameterize1 **_µn(xn) with ˜µn(xn,_** _√α1_ _n (xn_ _−_ _βnϵn(xn))), which_

is equivalent to Eq. (3) by letting sn(xn) = **_ϵn(xn)._** q
_−_ _√βn_


-----

which is equivalent to optimizing the KL divergence between the forward and the reverse process:

min _Lvb_ min _DKL(q(x0:N_ ) _p(x0:N_ )). (4)
**_µn,σn[2]_** _[}][N]n=1_ _⇔_ **_µn,σn[2]_** _[}][N]n=1_ _||_
_{_ _{_

To improve the sample quality in practice, instead of directly optimizing Lvb, Ho et al. (2020)
consider a reweighted variant of Lvb to learn sn(xn):


min EnβnEqn(xn) **_sn(xn)_** **_xn log qn(xn)_** = En,x0,ϵ **_ϵ +_**
**_sn_** _n=1_ _||_ _−∇_ _||[2]_ _||_
_{_ _}[N]_


_βnsn(xn)_ + c, (5)
_||[2]_


where n is uniform between 1 and N, qn(xn) is the marginal distribution of the forward process
at timestep n, ϵ is a standard Gaussian noise, xn on the right-hand side is reparameterized by

**_xn =_** _αnx0+_ _βnϵ and c is a constant only related to q. Indeed, Eq. (5) is exactly a weighted sum_

_[√]_

of score matching objectives (Song & Ermon, 2019), which admits an optimal solutionq **_s[∗]n[(][x][n][) =]_**
_∇xn log qn(xn) for all n ∈{1, 2 · · ·, N_ _}._

Note that Eq. (5) provides no learning signal for the variance σn[2] [. Indeed,][ σ]n[2] [is generally handcrafted]
in most of prior works. In DDPMs (Ho et al., 2020), two commonly used settings are σn[2] [=][ β][n] [and]
_σn[2]_ [= ˜]βn. In DDIMs, Song et al. (2020a) consistently use σn[2] [=][ λ]n[2] [. We argue that these handcrafted]
values are not the true optimal solution of Eq. (4) in general, leading to a suboptimal performance.

3 ANALYTIC ESTIMATE OF THE OPTIMAL REVERSE VARIANCE

For a DPM, we first show that both the optimal mean µ[∗]n[(][x][n][)][ and the optimal variance][ σ]n[∗][2] [to Eq. (4)]
have analytic forms w.r.t. the score function, which is summarized in the following Theorem 1.
**Theorem 1. (Score representation of the optimal solution to Eq. (4), proof in Appendix A.2)**

_The optimal solution µ[∗]n[(][x][n][)][ and][ σ]n[∗][2]_ _[to Eq. (4) are]_


**_µ[∗]n[(][x][n][) = ˜]µn_**

_σn[∗][2]_ [=][ λ]n[2] [+]




1
**_xn,_** _√αn_ (xn + βn∇xn log qn(xn)) _,_ (6)


2

_βn_ **_xn log qn(xn)_**
_αn_ _−_ _βn−1 −_ _λ[2]n_ 1 − _βnEqn(xn)_ _||∇_ _d_ _||[2]_ _,_ (7)
q  




_where qn(xn) is the marginal distribution of the forward process at the timestep n and d is the_
_dimension of the data._

The proof of Theorem 1 consists of three key steps:

-  The first step (see Lemma 9) is known as the moment matching (Minka, 2013), which
states that approximating arbitrary density by a Gaussian density under the KL divergence
is equivalent to setting the first two moments of the two densities as the same. To our
knowledge, the connection of moment matching and DPMs has not been revealed before.

-  In the second step (see Lemma 13), we carefully use the law of total variance conditioned
on x0 and convert the second moment of q(xn 1 **_xn) to that of q(x0_** **_xn)._**
_−_ _|_ _|_

-  In the third step (see Lemma 11), we surprisingly find that the second moment of q(x0 **_xn)_**
_|_
can be represented by the score function, and we plug the score representation into the
second moment of q(xn−1|xn) to get the final results in Theorem 1.

The results in Theorem 1 (and other results to appear later) can be further simplified for the DDPM
forward process (i.e., λ[2]n [= ˜]βn, see Appendix D for details). Besides, we can also extend Theorem 1 to DPMs with continuous timesteps (Song et al., 2020b; Kingma et al., 2021), where their
corresponding optimal mean and variance are also determined by the score function in an analytic
form (see Appendix E.1 for the extension).

Note that our analytic form of the optimal mean µ[∗]n[(][x][n][)][ in Eq. (6) and the previous parameterization]
of µn(xn) (Ho et al., 2020) in Eq. (3) coincide. The only difference is that Eq. (3) replaces the


-----

2 7 2 12

2 9 2 13

variance2 11 2[3]

2 13

n n 2n

2[2] 2[5] 2[8]

timestep n


0.4 n n 2n

0.3

(bits/dim)

0.2

term 0.1
vb0.1
L 2[2]

2[2] 2[5] 2[8]

timestep n


(a) Variance


(b) Terms in Lvb


Figure 1: Comparing our analytic estimate ˆσn[2] [and prior works with handcrafted variances][ β][n] [and]
_β˜n. (a) compares the values of the variance for different timesteps. (b) compares the term in Lvb_
corresponding to each timestep. The value of Lvb is the area under the corresponding curve.

score function ∇xn log qn(xn) in Eq. (6) with the score-based model sn(xn). This result explicitly
shows that Eq. (5) essentially shares the same optimal mean solution to the Lvb objective, providing
a simple and alternative perspective to prior works.

In contrast to the handcrafted strategies used in (Ho et al., 2020; Song et al., 2020a), Theorem 1
shows that the optimal reverse variance σn[∗][2] [can also be estimated without any extra training process]
given a pretrained score-based model sn(xn). In fact, we first estimate the expected mean squared
norm of ∇xn log qn(xn) by Γ = (Γ1, ..., ΓN ), where


**_sn(xn,m)_**
_||_ _||[2]_


Γn = [1]


_iid_
**_xn,m_** _qn(xn)._ (8)
_∼_


_m=1_


_M is the number of Monte Carlo samples. We only need to calculate Γ once for a pretrained_
model and reuse it in downstream computations (see Appendix H.1 for a detailed discussion of the
computation cost of Γ). Then, according to Eq. (7), we estimate σn[∗][2] [as follows:]


_βn_
_αn_


_σˆn[2]_ [=][ λ]n[2] [+]


1 _βnΓn_ _._ (9)
_−_




_βn−1 −_ _λ[2]n_


We empirically validate Theorem 1. In Figure 1 (a), we plot our analytic estimate ˆσn[2] [of a DDPM]
trained on CIFAR10, as well as the baselines βn and _β[˜]n used by Ho et al. (2020). At small timesteps,_
these strategies behave differently. Figure 1 (b) shows that our ˆσn[2] [outperforms the baselines for each]
term of Lvb, especially at the small timesteps. We also obtain similar results on other datasets (see
Appendix G.1). Besides, we show that only a small number of Monte Carlo (MC) samples (e.g.,
_M_ =10, 100) is required to achieve a sufficiently small variance caused by MC and get a similar
performance to that with a large M (see Appendix G.2). We also discuss the stochasticity of Lvb
after plugging ˆσn[2] [in Appendix H.2.]

3.1 BOUNDING THE OPTIMAL REVERSE VARIANCE TO REDUCE BIAS


According to Eq. (7) and Eq. (9), the bias of the analytic estimate ˆσn[2] [is]


_βn_ **_xn log qn(xn)_**

_|σn[∗][2]_ _[−]_ _σ[ˆ]n[2]_ _[|][ =]_ s _αn_ _−_ _βn−1 −_ _λ[2]n_ _βn_ _|Γn −_ Eqn(xn) _||∇_ _d_ _||[2]_ _|_ _._ (10)

q

Approximation error

 Coefficient 

| {z }

Our estimate of the variance employs a score-based model| {z } **_sn(xn) to approximate the true score_**
function ∇xn log qn(xn). Thus, the approximation error in Eq. (10) is irreducible given a pretrained
model. Meanwhile, the coefficient in Eq. (10) can be large if we use a shorter trajectory to sample
(see details in Section 4), potentially resulting in a large bias.


_βn_
_αn_


_|σn[∗][2]_ _[−]_ _σ[ˆ]n[2]_ _[|][ =]_


-----

To reduce the bias, we derive bounds of the optimal reverse variance σn[∗][2] [and clip our estimate based]
on the bounds. Importantly, these bounds are unrelated to the data distribution q(x0) and hence
can be efficiently calculated. We firstly derive both upper and lower bounds of σn[∗][2] [without any]
assumption about the data. Then we show another upper bound of σn[∗][2] [if the data distribution is]
bounded. We formalize these bounds in Theorem 2.
**Theorem 2. (Bounds of the optimal reverse variance, proof in Appendix A.3)**

_σn[∗][2]_ _[has the following lower and upper bounds:]_


_βn_
_αn_


_λ[2]n_ _[≤]_ _[σ]n[∗][2]_ _[≤]_ _[λ]n[2]_ [+]


(11)


_βn−1 −_ _λ[2]n_


_If we further assume q(x0) is a bounded distribution in [a, b][d], where d is the dimension of data,_
_then σn[∗][2]_ _[can be further upper bounded by]_

2

2

_αn_ _b_ _a_

_σn[∗][2]_ _n_ [+] _αn_ 1 _βn_ 1 _λ[2]n_ _−_ _._ (12)

_[≤]_ _[λ][2]_ _−_ _−_ q _−_ _−_ _[·]_ s _βn_ !  2 

p

Theorem 2 states that the handcrafted reverse variance λ[2]n [in prior works (Ho et al., 2020; Song et al.,]
2020a) underestimates σn[∗][2][. For instance,][ λ]n[2] [= ˜]βn in DDPM. We compare it with our estimate in
Figure 1 (a) and the results agree with Theorem 2. Besides, the boundedness assumption of q(x0)
is satisfied in many scenarios including generative modelling of images, and which upper bound
among Eq. (11) and Eq. (12) is tighter depends on n. Therefore, we clip our estimate based on the
minimum one. Further, we show theses bounds are tight numerically in Appendix G.3.

4 ANALYTIC ESTIMATION OF THE OPTIMAL TRAJECTORY

The number of full timesteps N can be large, making the inference slow in practice. Thereby, we can
construct a shorter forward process q(xτ1 _, · · ·, xτK_ _|x0) constrained on a trajectory 1 = τ1 < · · · <_
_τK = N of K timesteps (Song et al., 2020a; Nichol & Dhariwal, 2021; Watson et al., 2021), and K_
can be much smaller than N to speed up the inference. Formally, the shorter process is defined as
_q(xτ1_ _, · · ·, xτK_ _|x0) = q(xτK_ _|x0)_ _k=2_ _[q][(][x][τ]k−1_ _[|][x][τ]k_ _[,][ x][0][)][, where]_

_q(xτk−1_ _|xτk_ _, x0) = N[Q](x[K]τk−1_ _|µ˜_ _τk−1|τk_ (xτk _, x0), λ[2]τk−1|τk_ **_[I][)][,]_** (13)

**_µ˜_** _τk−1|τk_ (xτk _, x0) =_ _ατk−1_ **_x0 +_** _βτk−1_ _λ[2]τk−1|τk_ _._
q _−_ _[·][ x][τ][k][ −√]βτ[α]k[τ][k]_ **_[x][0]_**

[p] q

The corresponding reverse process is p(x0, xτ1 _, · · ·, xτK_ ) = p(xτK ) _k=1_ _[p][(][x][τ]k−1_ _[|][x][τ]k_ [)][, where]

_p(xτk−1_ _|xτk_ ) = N (xτk−1 _|µτk−1|τk_ (xτk ), στ[2]k−1[Q]|τ[K]k **_[I][)][.]_**

According to Theorem 1, the mean and variance of the optimal p[∗](xτk−1 _|xτk_ ) in the sense of KL
minimization is


**_µ[∗]τk−1|τk_** [(][x][τ]k [) = ˜]µτk−1|τk

_στ[∗]k[2]−1|τk_ [=] _[λ]τ[2]k−1|τk_ [+]s




**_xτk_** _,_ _√ατk_ (xτk + βτk _∇xτk log q(xτk_ ))


(1−βτk Eq(xτk ) _||∇xτk logd q(xτk_ )||[2]


_βτk_

_ατk|τk−1_


_βτk−1_ _λ[2]τk−1|τk_
_−_


),


where ατk|τk−1 := ατk _/ατk−1_ . According to Theorem 2, we can derive similar bounds for στ[∗]k[2]−1|τk
(see details in Appendix C). Similarly to Eq. (9), the estimate of στ[∗]k[2]−1|τk [is]


_βτk_

_ατk|τk−1_


_σˆτ[2]k−1|τk_ [=] _[λ]τ[2]k−1|τk_ [+]


_βτk−1_ _λ[2]τk−1|τk_
_−_


(1 _βτk_ Γτk ),
_−_


-----

where Γ is defined in Eq. (8) and can be shared across different selections of trajectories. Based on
the optimal reverse process p[∗] above, we further optimize the trajectory:


min
_τ1,_ _,τK_ _[D][KL][(][q][(][x][0][,][ x][τ][1]_ _[,][ · · ·][,][ x][τ][K]_ [)][||][p][∗][(][x][0][,][ x][τ][1] _[,][ · · ·][,][ x][τ][K]_ [)) =][ d]2

_···_


_J(τk−1, τk) + c,_ (14)
_k=2_

X


where J(τk−1, τk) = log(στ[∗]k[2]−1|τk _[/λ]τ[2]k−1|τk_ [)][ and][ c][ is a constant unrelated to the trajectory][ τ][ (see]
proof in Appendix A.4). The KL in Eq. (14) can be decomposed into K − 1 terms and each term
has an analytic form w.r.t. the score function. We view each term as a cost function J evaluated
at (τk−1, τk), and it can be efficiently estimated by J(τk−1, τk) ≈ log(ˆστ[2]k−1|τk _[/λ]τ[2]k−1|τk_ [)][, which]
doesn’t require any neural network computation once Γ is given. While the logarithmic function
causes bias even when the correct score function is known, it can be reduced by increasing M .

As a result, Eq. (14) is reduced to a canonical least-cost-path problem (Watson et al., 2021) on a
directed graph, where the nodes are {1, 2, · · ·, N _} and the edge from s to t has cost J(s, t). We_
want to find a least-cost path of K nodes starting from 1 and terminating at N . This problem
can be solved by the dynamic programming (DP) algorithm introduced by Watson et al. (2021).
We present this algorithm in Appendix B. Besides, we can also extend Eq. (14) to DPMs with
continuous timesteps (Song et al., 2020b; Kingma et al., 2021), where their corresponding optimal
KL divergences are also decomposed to terms determined by score functions. Thereby, the DP
algorithm is also applicable. See Appendix E.2 for the extension.

5 RELATIONSHIP BETWEEN THE SCORE FUNCTION AND THE DATA
COVARIANCE MATRIX

In this part, we further reveal a relationship between the score function and the data covariance
matrix. Indeed, the data covariance matrix can be decomposed to the sum of Eq(xn)Covq(x0 **_xn)[x0]_**
_|_
and Covq(xn)Eq(x0 **_xn)[x0], where the first term can be represented by the score function. Further,_**
_|_
the second term is negligible when n is sufficiently large because x0 and xn are almost independent.
In such cases, the data covariance matrix is almost determined by the score function. Currently, the
relationship is purely theoretical and its practical implication is unclear. See details in Appendix A.5.

6 EXPERIMENTS

We consider the DDPM forward process (λ[2]n [= ˜]βn) and the DDIM forward process (λ[2]n [= 0][),]
which are the two most commonly used special cases of Eq. (2). We denote our method, which
uses the analytic estimate σn[2] [= ˆ]σn[2] [, as][ Analytic-DPM][, and explicitly call it][ Analytic-DDPM][ or]
_Analytic-DDIM according to which forward process is used. We compare our Analytic-DPM with_
the original DDPM (Ho et al., 2020), where the reverse variance is either σn[2] [= ˜]βn or σn[2] [=][ β][n][, as]
well as the original DDIM (Song et al., 2020a), where the reverse variance is σn[2] [=][ λ]n[2] [= 0][.]

We adopt two methods to get the trajectory for both the analytic-DPM and baselines. The first one is
even trajectory (ET) (Nichol & Dhariwal, 2021), where the timesteps are determined according to a
fixed stride (see details in Appendix F.4). The second one is optimal trajectory (OT) (Watson et al.,
2021), where the timesteps are calculated via dynamic programming (see Section 4). Note that the
baselines calculate the OT based on the Lvb with their handcrafted variances (Watson et al., 2021).

We apply our Analytic-DPM to three pretrained score-based models provided by prior works (Ho
et al., 2020; Song et al., 2020a; Nichol & Dhariwal, 2021), as well as two score-based models
trained by ourselves. The pretrained score-based models are trained on CelebA 64x64 (Liu et al.,
2015), ImageNet 64x64 (Deng et al., 2009) and LSUN Bedroom (Yu et al., 2015) respectively. Our
score-based models are trained on CIFAR10 (Krizhevsky et al., 2009) with two different forward
noise schedules: the linear schedule (LS) (Ho et al., 2020) and the cosine schedule (CS) (Nichol &
Dhariwal, 2021). We denote them as CIFAR10 (LS) and CIFAR10 (CS) respectively. The number
of the full timesteps N is 4000 for ImageNet 64x64 and 1000 for other datasets. During sampling,
we only display the mean of p(x0 **_x1) and discard the noise following Ho et al. (2020), and we_**
_|_
additionally clip the noise scale σ2 of p(x1|x2) for all methods compared in Table 2 (see details in
Appendix F.2 and its ablation study in Appendix G.4). See more experimental details in Appendix F.


-----

Table 1: Negative log-likelihood (bits/dim) ↓ under the DDPM forward process. We show results
under trajectories of different number of timesteps K. We select the minimum K such that analyticDPM can outperform the baselines with full timesteps and underline the corresponding results.

Model \ # timesteps K 10 25 50 100 200 400 1000

CIFAR10 (LS)

DDPM, σn[2] [= ˜]βn 74.95 24.98 12.01 7.08 5.03 4.29 3.73
ET DDPM, σn[2] [=][ β][n] 6.99 6.11 5.44 4.86 4.39 4.07 3.75
Analytic-DDPM **5.47** **4.79** **4.38** **4.07** **3.84** **3.71** **3.59**

OT DDPM, σn[2] [=][ β][n] 5.38 4.34 3.97 3.82 3.77 3.75 3.75
Analytic-DDPM **4.11** **3.68** **3.61** **3.59** **3.59** **3.59** **3.59**

CIFAR10 (CS)

DDPM, σn[2] [= ˜]βn 75.96 24.94 11.96 7.04 4.95 4.19 3.60
ET DDPM, σn[2] [=][ β][n] 6.51 5.55 4.92 4.41 4.03 3.78 3.54
Analytic-DDPM **5.08** **4.45** **4.09** **3.83** **3.64** **3.53** **3.42**

OT DDPM, σn[2] [=][ β][n] 5.51 4.30 3.86 3.65 3.57 3.54 3.54
Analytic-DDPM **3.99** **3.56** **3.47** **3.44** **3.43** **3.42** **3.42**

CelebA 64x64

DDPM, σn[2] [= ˜]βn 33.42 13.09 7.14 4.60 3.45 3.03 2.71
ET DDPM, σn[2] [=][ β][n] 6.67 5.72 4.98 4.31 3.74 3.34 2.93
Analytic-DDPM **4.54** **3.89** **3.48** **3.16** **2.92** **2.79** **2.66**

OT DDPM, σn[2] [=][ β][n] 4.76 3.58 3.16 2.99 2.94 2.93 2.93
Analytic-DDPM **2.97** **2.71** **2.67** **2.66** **2.66** **2.66** **2.66**


Model \ # timesteps K 25 50 100 200 400 1000 4000

ImageNet 64x64

DDPM, σn[2] [= ˜]βn 105.87 46.25 22.02 12.10 7.59 5.04 3.89
ET DDPM, σn[2] [=][ β][n] 5.81 5.20 4.70 4.31 4.04 3.81 3.65
Analytic-DDPM **4.78** **4.42** **4.15** **3.95** **3.81** **3.69** **3.61**

OT DDPM, σn[2] [=][ β][n] 4.56 4.09 3.84 3.73 3.68 3.65 3.65
Analytic-DDPM **3.83** **3.70** **3.64** **3.62** **3.62** **3.61** **3.61**

We conduct extensive experiments to demonstrate that analytic-DPM can consistently improve the
inference efficiency of a pretrained DPM while achieving a comparable or even superior performance. Specifically, Section 6.1 and Section 6.2 present the likelihood and sample quality results
respectively. Additional experiments such as ablation studies can be found in Appendix G.

6.1 LIKELIHOOD RESULTS

Since λ[2]n [= 0][ in the DDIM forward process, its variational bound][ L][vb] [is infinite. Thereby, we]
only consider the likelihood results under the DDPM forward process. As shown in Table 1, on all
three datasets, our Analytic-DPM consistently improves the likelihood results of the original DDPM
using both ET and OT. Remarkably, using a much shorter trajectory (i.e., a much less inference
time), Analytic-DPM with OT can still outperform the baselines. In Table 1, we select the minimum K such that analytic-DPM can outperform the baselines with full timesteps and underline the
corresponding results. Specifically, analytic-DPM enjoys a 40× speed up on CIFAR10 (LS) and
ImageNet 64x64, and a 20× speed up on CIFAR10 (CS) and CelebA 64x64.

Although we mainly focus on learning-free strategies of choosing the reverse variance, we also
compare to another strong baseline that predicts the variance by a neural network (Nichol & Dhariwal, 2021). With full timesteps, Analytic-DPM achieves a NLL of 3.61 on ImageNet 64x64, which
is very close to 3.57 reported in Nichol & Dhariwal (2021). Besides, while Nichol & Dhariwal
(2021) report that the ET drastically reduces the log-likelihood performance of their neural-networkparameterized variance, Analytic-DPM performs well with the ET. See details in Appendix G.6.


-----

Table 2: FID ↓ under the DDPM and DDIM forward processes. All are evaluated under the even
trajectory (ET). The result with _[†]_ is slightly better than 3.17 reported by Ho et al. (2020), because
we use an improved model architecture following Nichol & Dhariwal (2021).

Model \ # timesteps K 10 25 50 100 200 400 1000

CIFAR10 (LS)

DDPM, σn[2] [= ˜]βn 44.45 21.83 15.21 10.94 8.23 6.43 5.11
DDPM, σn[2] [=][ β][n] 233.41 125.05 66.28 31.36 12.96 4.86 _†3.04_
Analytic-DDPM **34.26** **11.60** **7.25** **5.40** **4.01** **3.62** 4.03

DDIM 21.31 10.70 7.74 6.08 5.07 4.61 4.13
Analytic-DDIM **14.00** **5.81** **4.04** **3.55** **3.39** **3.50** **3.74**

CIFAR10 (CS)

DDPM, σn[2] [= ˜]βn 34.76 16.18 11.11 8.38 6.66 5.65 4.92
DDPM, σn[2] [=][ β][n] 205.31 84.71 37.35 14.81 5.74 **3.40** **3.34**
Analytic-DDPM **22.94** **8.50** **5.50** **4.45** **4.04** 3.96 4.31

DDIM 34.34 16.68 10.48 7.94 6.69 5.78 4.89
Analytic-DDIM **26.43** **9.96** **6.02** **4.88** **4.92** **5.00** **4.66**

CelebA 64x64

DDPM, σn[2] [= ˜]βn 36.69 24.46 18.96 14.31 10.48 8.09 5.95
DDPM, σn[2] [=][ β][n] 294.79 115.69 53.39 25.65 9.72 **3.95** **3.16**
Analytic-DDPM **28.99** **16.01** **11.23** **8.08** **6.51** 5.87 5.21

DDIM 20.54 13.45 9.33 6.60 4.96 4.15 3.40
Analytic-DDIM **15.62** **9.22** **6.13** **4.29** **3.46** **3.38** **3.13**


Model \ # timesteps K 25 50 100 200 400 1000 4000

ImageNet 64x64

DDPM, σn[2] [= ˜]βn **29.21** **21.71** 19.12 17.81 17.48 16.84 16.55
DDPM, σn[2] [=][ β][n] 170.28 83.86 45.04 28.39 21.38 17.58 16.38
Analytic-DDPM 32.56 22.45 **18.80** **17.16** **16.40** **16.14** **16.34**

DDIM 26.06 20.10 18.09 17.84 17.74 17.73 19.00
Analytic-DDIM **25.98** **19.23** **17.73** **17.49** **17.44** **17.57** **18.98**

6.2 SAMPLE QUALITY

As for the sample quality, we consider the commonly used FID score (Heusel et al., 2017), where a
lower value indicates a better sample quality. As shown in Table 2, under trajectories of different K,
our Analytic-DDIM consistently improves the sample quality of the original DDIM. This allows us
to generate high-quality samples with less than 50 timesteps, which results in a 20× to 80× speed
up compared to the full timesteps. Indeed, in most cases, Analytic-DDIM only requires up to 50
timesteps to get a similar performance to the baselines. Besides, Analytic-DDPM also improves the
sample quality of the original DDPM in most cases. For fairness, we use the ET implementation in
Nichol & Dhariwal (2021) for all results in Table 2. We also report the results on CelebA 64x64
using a slightly different implementation of the ET following Song et al. (2020a) in Appendix G.7,
and our Analytic-DPM is still effective. We show generated samples in Appendix G.9.

We observe that Analytic-DDPM does not always outperform the baseline under the FID metric,
which is inconsistent with the likelihood results in Table 1. Such a behavior essentially roots in the
different natures of the two metrics and has been investigated in extensive prior works (Theis et al.,
2015; Ho et al., 2020; Nichol & Dhariwal, 2021; Song et al., 2021; Vahdat et al., 2021; Watson et al.,
2021; Kingma et al., 2021). Similarly, using more timesteps doesn’t necessarily yield a better FID.
For instance, see the Analytic-DDPM results on CIFAR10 (LS) and the DDIM results on ImageNet
64x64 in Table 2. A similar phenomenon is observed in Figure 8 in Nichol & Dhariwal (2021).
Moreover, a DPM (including Analytic-DPM) with OT does not necessarily lead to a better FID
score (Watson et al., 2021) (see Appendix G.5 for a comparison of ET and OT in Analytic-DPM).


-----

Table 3: Efficiency comparison, based on the least number of timesteps ↓ required to achieve a FID
around 6 (with the corresponding FID). To get the strongest baseline, the results with _[†]_ are achieved
by using the quadratic trajectory Song et al. (2020a) instead of the default even trajectory.

Method CIFAR10 CelebA 64x64 LSUN Bedroom

DDPM (Ho et al., 2020) _†90 (6.12)_ _> 200_ 130 (6.06)
DDIM (Song et al., 2020a) _†30 (5.85)_ _> 100_ Best FID > 6
Improved DDPM (Nichol & Dhariwal, 2021) 45 (5.96) Missing model **90 (6.02)**
Analytic-DPM (ours) **25 (5.81)** **55 (5.98)** 100 (6.05)

We summarize the efficiency of different methods in Table 3, where we consider the least number
of timesteps required to achieve a FID around 6 as the metric for a more direct comparison.

7 RELATED WORK

**DPMs and their applications. The diffusion probabilistic model (DPM) is initially introduced by**
Sohl-Dickstein et al. (2015), where the DPM is trained by optimizing the variational bound Lvb.
Ho et al. (2020) propose the new parameterization of DPMs in Eq. (3) and learn DPMs with the
reweighted variant of Lvb in Eq. (5). Song et al. (2020b) model the noise adding forward process
as a stochastic differential equation (SDE) and introduce DPMs with continuous timesteps. With
these important improvements, DPMs show great potential in various applications, including speech
synthesis (Chen et al., 2020; Kong et al., 2020; Popov et al., 2021; Lam et al., 2021), controllable
generation (Choi et al., 2021; Sinha et al., 2021), image super-resolution (Saharia et al., 2021; Li
et al., 2021), image-to-image translation (Sasaki et al., 2021), shape generation (Zhou et al., 2021)
and time series forecasting (Rasul et al., 2021).

**Faster DPMs. Several works attempt to find short trajectories while maintaining the DPM per-**
formance. Chen et al. (2020) find an effective trajectory of only six timesteps by the grid search.
However, the grid search is only applicable to very short trajectories due to its exponentially growing
time complexity. Watson et al. (2021) model the trajectory searching as a least-cost-path problem
and introduce a dynamic programming (DP) algorithm to solve this problem. Our work uses this
DP algorithm, where the cost is defined as a term of the optimal KL divergence. In addition to
these trajectory searching techniques, Luhman & Luhman (2021) compress the reverse denoising
process into a single step model; San-Roman et al. (2021) dynamically adjust the trajectory during inference. Both of them need extra training after getting a pretrained DPM. As for DPMs with
continuous timesteps (Song et al., 2020b), Song et al. (2020b) introduce an ordinary differential
equation (ODE), which improves sampling efficiency and enables exact likelihood computation.
However, the likelihood computation involves a stochastic trace estimator, which requires a multiple
number of runs for accurate computation. Jolicoeur-Martineau et al. (2021) introduce an advanced
SDE solver to simulate the reverse process in a more efficient way. However, the log-likelihood
computation based on this solver is not specified.

**Variance Learning in DPMs. In addition to the reverse variance, there are also works on learning**
the forward noise schedule (i.e., the forward variance). Kingma et al. (2021) propose variational
diffusion models (VDMs) on continuous timesteps, which use a signal-to-noise ratio function to
parameterize the forward variance and directly optimize the variational bound objective for a better
log-likelihood. While we primarily apply our method to DDPMs and DDIMs, estimating the optimal
reverse variance can also be applied to VDMs (see Appendix E).

8 CONCLUSION

We present that both the optimal reverse variance and the corresponding optimal KL divergence
of a DPM have analytic forms w.r.t. its score function. Building upon it, we propose Analytic_DPM, a training-free inference framework that estimates the analytic forms of the variance and KL_
divergence using the Monte Carlo method and a pretrained score-based model. We derive bounds
of the optimal variance to correct potential bias and reveal a relationship between the score function
and the data covariance matrix. Empirically, our analytic-DPM improves both the efficiency and
performance of likelihood results, and generates high-quality samples efficiently in various DPMs.


-----

ACKNOWLEDGMENTS

This work was supported by NSF of China Projects (Nos. 62061136001, 61620106010,
62076145), Beijing NSF Project (No. JQ19016), Beijing Outstanding Young Scientist Program
NO. BJJWZYJH012019100020098, Beijing Academy of Artificial Intelligence (BAAI), TsinghuaHuawei Joint Research Program, a grant from Tsinghua Institute for Guo Qiang, and the NVIDIA
NVAIL Program with GPU/DGX Acceleration, Major Innovation & Planning Interdisciplinary Platform for the “Double-First Class” Initiative, Renmin University of China.

ETHICS STATEMENT

This work proposes an analytic estimate of the optimal variance in the reverse process of diffusion
probabilistic models. As a fundamental research in machine learning, the negative consequences are
not obvious. Though in theory any technique can be misused, it is not likely to happen at the current
stage.

REPRODUCIBILITY STATEMENT

[We provide our codes and links to pretrained models in https://github.com/baofff/](https://github.com/baofff/Analytic-DPM)
[Analytic-DPM. We provide details of these pretrained models in Appendix F.1. We provide de-](https://github.com/baofff/Analytic-DPM)
tails of data processing, log-likelihood evaluation, sampling and FID computation in Appendix F.2.
We provide complete proofs of all theoretical results in Appendix A.

REFERENCES

Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural
image synthesis. arXiv preprint arXiv:1809.11096, 2018.

Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov. Importance weighted autoencoders. arXiv
_preprint arXiv:1509.00519, 2015._

Nanxin Chen, Yu Zhang, Heiga Zen, Ron J Weiss, Mohammad Norouzi, and William Chan. Wavegrad: Estimating gradients for waveform generation. arXiv preprint arXiv:2009.00713, 2020.

Jooyoung Choi, Sungwon Kim, Yonghyun Jeong, Youngjune Gwon, and Sungroh Yoon. Ilvr: Conditioning method for denoising diffusion probabilistic models. arXiv preprint arXiv:2108.02938,
2021.

Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition,
pp. 248–255. Ieee, 2009.

Prafulla Dhariwal and Alex Nichol. Diffusion models beat gans on image synthesis. arXiv preprint
_arXiv:2105.05233, 2021._

Yilun Du and Igor Mordatch. Implicit generation and generalization in energy-based models. arXiv
_preprint arXiv:1903.08689, 2019._

Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair,
Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information
_processing systems, 27, 2014._

Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.
Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in
_neural information processing systems, 30, 2017._

Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. arXiv preprint
_arXiv:2006.11239, 2020._


-----

Alexia Jolicoeur-Martineau, Ke Li, R´emi Pich´e-Taillefer, Tal Kachman, and Ioannis Mitliagkas.
Gotta go fast when generating data with score-based models. arXiv preprint arXiv:2105.14080,
2021.

Tero Karras, Miika Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Training
generative adversarial networks with limited data. arXiv preprint arXiv:2006.06676, 2020a.

Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. Analyzing and improving the image quality of stylegan. In Proceedings of the IEEE/CVF Conference on
_Computer Vision and Pattern Recognition, pp. 8110–8119, 2020b._

Hyun-Chul Kim and Zoubin Ghahramani. Bayesian gaussian process classification with the em-ep
algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(12):1948–1959,
2006.

Diederik P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolutions.
_arXiv preprint arXiv:1807.03039, 2018._

Diederik P Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models.
_arXiv preprint arXiv:2107.00630, 2021._

Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile
diffusion model for audio synthesis. arXiv preprint arXiv:2009.09761, 2020.

Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images.
2009.

Max WY Lam, Jun Wang, Rongjie Huang, Dan Su, and Dong Yu. Bilateral denoising diffusion
models. arXiv preprint arXiv:2108.11514, 2021.

Haoying Li, Yifan Yang, Meng Chang, Huajun Feng, Zhihai Xu, Qi Li, and Yueting Chen.
Srdiff: Single image super-resolution with diffusion probabilistic models. _arXiv preprint_
_arXiv:2104.14951, 2021._

Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In
_2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December_
_7-13, 2015, pp. 3730–3738. IEEE Computer Society, 2015._

Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. _arXiv preprint_
_arXiv:1711.05101, 2017._

Eric Luhman and Troy Luhman. Knowledge distillation in iterative generative models for improved
sampling speed. arXiv preprint arXiv:2101.02388, 2021.

Thomas P Minka. Expectation propagation for approximate bayesian inference. arXiv preprint
_arXiv:1301.2294, 2013._

Thomas Peter Minka. A family of algorithms for approximate Bayesian inference. PhD thesis,
Massachusetts Institute of Technology, 2001.

Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization
for generative adversarial networks. arXiv preprint arXiv:1802.05957, 2018.

Alex Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. _arXiv_
_preprint arXiv:2102.09672, 2021._

Vadim Popov, Ivan Vovk, Vladimir Gogoryan, Tasnima Sadekova, and Mikhail Kudinov. Grad-tts:
A diffusion probabilistic model for text-to-speech. arXiv preprint arXiv:2105.06337, 2021.

Kashif Rasul, Calvin Seward, Ingmar Schuster, and Roland Vollgraf. Autoregressive denoising diffusion models for multivariate probabilistic time series forecasting. _arXiv preprint_
_arXiv:2101.12072, 2021._


-----

Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International conference on machine learning,
pp. 1278–1286. PMLR, 2014.

Chitwan Saharia, Jonathan Ho, William Chan, Tim Salimans, David J Fleet, and Mohammad
Norouzi. Image super-resolution via iterative refinement. arXiv preprint arXiv:2104.07636, 2021.

Robin San-Roman, Eliya Nachmani, and Lior Wolf. Noise estimation for generative diffusion models. arXiv preprint arXiv:2104.02600, 2021.

Hiroshi Sasaki, Chris G Willcocks, and Toby P Breckon. Unit-ddpm: Unpaired image translation
with denoising diffusion probabilistic models. arXiv preprint arXiv:2104.05358, 2021.

Abhishek Sinha, Jiaming Song, Chenlin Meng, and Stefano Ermon. D2c: Diffusion-denoising
models for few-shot conditional generation. arXiv preprint arXiv:2106.06819, 2021.

Jascha Sohl-Dickstein, 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. arXiv
_preprint arXiv:2010.02502, 2020a._

Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution.
_arXiv preprint arXiv:1907.05600, 2019._

Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben
Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint
_arXiv:2011.13456, 2020b._

Yang Song, Conor Durkan, Iain Murray, and Stefano Ermon. Maximum likelihood training of scorebased diffusion models. arXiv e-prints, pp. arXiv–2101, 2021.

Lucas Theis, A¨aron van den Oord, and Matthias Bethge. A note on the evaluation of generative
models. arXiv preprint arXiv:1511.01844, 2015.

Arash Vahdat and Jan Kautz. Nvae: A deep hierarchical variational autoencoder. arXiv preprint
_arXiv:2007.03898, 2020._

Arash Vahdat, Karsten Kreis, and Jan Kautz. Score-based generative modeling in latent space. arXiv
_preprint arXiv:2106.05931, 2021._

Daniel Watson, Jonathan Ho, Mohammad Norouzi, and William Chan. Learning to efficiently sample from diffusion probabilistic models. arXiv preprint arXiv:2106.03802, 2021.

Yan Wu, Jeff Donahue, David Balduzzi, Karen Simonyan, and Timothy Lillicrap. Logan: Latent
optimisation for generative adversarial networks. arXiv preprint arXiv:1912.00953, 2019.

Zhisheng Xiao, Karsten Kreis, Jan Kautz, and Arash Vahdat. Vaebm: A symbiosis between variational autoencoders and energy-based models. In International Conference on Learning Repre_sentations, 2020._

Fisher Yu, Yinda Zhang, Shuran Song, Ari Seff, and Jianxiong Xiao. Lsun: Construction of
a large-scale image dataset using deep learning with humans in the loop. _arXiv preprint_
_arXiv:1506.03365, 2015._

Linqi Zhou, Yilun Du, and Jiajun Wu. 3d shape generation and completion through point-voxel
diffusion. arXiv preprint arXiv:2104.03670, 2021.


-----

A PROOFS AND DERIVATIONS

A.1 LEMMAS

**Lemma 1. (Cross-entropy to Gaussian) Suppose q(x) is a probability density function with mean**
**_µq and covariance matrix Σq and p(x) = N_** (x|µ, Σ) is a Gaussian distribution, then the cross_entropy between q and p is equal to the cross-entropy between_ (x **_µq, Σq) and p, i.e.,_**
_N_ _|_

_H(q, p) = H(_ (x **_µq, Σq), p)_**
_N_ _|_

= [1]

2 [log((2][π][)][d][|][Σ][|][) + 1]2 [tr(][Σ][q][Σ][−][1][) + 1]2 [(][µ][q][ −] **_[µ][)][⊤][Σ][−][1][(][µ][q][ −]_** **_[µ][)][.]_**


_Proof._


1

exp(
(2π)[d]|Σ| _−_ [(][x][ −] **_[µ][)][⊤][Σ]2[−][1][(][x][ −]_** **_[µ][)]_**


_H(q, p) = −Eq(x) log p(x) = −Eq(x) log_


= [1]

2 [log((2][π][)][d][|][Σ][|][) + 1]2 [E][q][(][x][)][(][x][ −] **_[µ][)][⊤][Σ][−][1][(][x][ −]_** **_[µ][)]_**


= [1]

2 [log((2][π][)][d][|][Σ][|][) + 1]2 [E][q][(][x][)][ tr((][x][ −] **_[µ][)(][x][ −]_** **_[µ][)][⊤][Σ][−][1][)]_**

= 2 [1] [log((2][π][)][d][|][Σ][|][) + 1]2 [tr(][E][q][(][x][)] (x − **_µ)(x −_** **_µ)[⊤][]_** **Σ[−][1])**



= [1] (x **_µq)(x_** **_µq)[⊤]_** + (µq **_µ)(µq_** **_µ)[⊤][]_** **Σ[−][1])**

2 [log((2][π][)][d][|][Σ][|][) + 1]2 [tr(][E][q][(][x][)] _−_ _−_ _−_ _−_



= [1]2 [log((2][π][)][d][|][Σ][|][) + 1]2 [tr(] **Σq + (µq −** **_µ)(µq −_** **_µ)[⊤][]_** **Σ[−][1])**



= [1]

2 [log((2][π][)][d][|][Σ][|][) + 1]2 [tr(][Σ][q][Σ][−][1][) + 1]2 [tr((][µ][q][ −] **_[µ][)(][µ][q][ −]_** **_[µ][)][⊤][Σ][−][1][)]_**

= [1]

2 [log((2][π][)][d][|][Σ][|][) + 1]2 [tr(][Σ][q][Σ][−][1][) + 1]2 [(][µ][q][ −] **_[µ][)][⊤][Σ][−][1][(][µ][q][ −]_** **_[µ][)]_**

=H( (x **_µq, Σq), p)._**
_N_ _|_

**Lemma 2. (KL to Gaussian) Suppose q(x) is a probability density function with mean µq and**
_covariance matrix Σq and p(x) = N_ (x|µ, Σ) is a Gaussian distribution, then

_DKL(q_ _p) = DKL(_ (x **_µq, Σq)_** _p) + H(_ (x **_µq, Σq))_** _H(q),_
_||_ _N_ _|_ _||_ _N_ _|_ _−_

_where H(·) denotes the entropy of a distribution._

_Proof. According to Lemma 1, we have H(q, p) = H(_ (x **_µq, Σq), p). Thereby,_**
_N_ _|_

_DKL(q_ _p) = H(q, p)_ _H(q) = H(_ (x **_µq, Σq), p)_** _H(q)_
_||_ _−_ _N_ _|_ _−_
=H( (x **_µq, Σq), p)_** _H(_ (x **_µq, Σq)) + H(_** (x **_µq, Σq))_** _H(q)_
_N_ _|_ _−_ _N_ _|_ _N_ _|_ _−_
=DKL( (x **_µq, Σq)_** _p) + H(_ (x **_µq, Σq))_** _H(q)._
_N_ _|_ _||_ _N_ _|_ _−_

**Lemma 3. (Equivalence between the forward and reverse Markov property) Suppose q(x0:N** ) =


_n=1_ _q(xn|xn−1) is a Markov chain, then q is also a Markov chain in the reverse direction,_

Q


_q(x0)_


_i.e., q(x0:N_ ) = q(xN )


_n=1_ _q(xn−1|xn)._

Q


-----

_Proof._


_q(xn−1|xn, · · ·, xN_ ) = _[q][(][x]q[n]([−]x[1]n[,][ x],_ _[n][,],[ · · ·] x[,]N[ x])_ _[N]_ [)]

_· · ·_

_N_
_q(xn−1, xn)_ _i=n+1_ _q(xi|xi−1)_

= q(xn 1 **_xn)._**

_N_ Q _−_ _|_
_q(xn)_ _i=n+1_ _q(xi|xi−1)_
Q


Thereby, q(x0:N ) = q(xN )


_n=1_ _q(xn−1|xn)._

Q


**Lemma 4. (Entropy of a Markov chain) Suppose q(x0:N** ) is a Markov chain, then


EqH(q(xn 1 **_xn)) = H(q(x0)) +_** EqH(q(xn **_xn_** 1)).
_−_ _|_ _|_ _−_
_n=1_ _n=1_

X X


_H(q(x0:N_ )) = H(q(xN )) +


_Proof. According to Lemma 3, we have_


_H(q(x0:N_ )) = − Eq log q(xN )


_q(xn_ 1 **_xn) =_** Eq log q(xN ) Eq log q(xn 1 **_xn)_**
_−_ _|_ _−_ _−_ _−_ _|_
_n=1_ _n=1_

Y X


=H(q(xN )) + EqH(q(xn 1 **_xn))._**

_−_ _|_
_n=1_

X


Similarly, we also have H(q(x0:N )) = H(q(x0)) +


EqH(q(xn **_xn_** 1)).
_n=1_ _|_ _−_

P


**Lemma 5. (Entropy of a DDPM forward process) Suppose q(x0:N** ) is a Markov chain and
_q(xn|xn−1) = N_ (xn|[√]αnxn−1, βnI), then


_H(q(x0:N_ )) = H(q(x0)) + _[d]_

2

_Proof. According to Lemma 4, we have_


log(2πeβn).
_n=1_

X


EqH(q(xn **_xn_** 1)) = H(q(x0)) +
_|_ _−_
_n=1_ _n=1_

X X


_H(q(x0:N_ )) = H(q(x0)) +


2 [log(2][πeβ][n][)][.]


**Lemma 6. (Entropy of a conditional Markov chain) Suppose q(x1:N** _|x0) is Markov, then_


_H(q(x0:N_ )) = H(q(x0)) + EqH(q(xN _|x0)) +_

_Proof. According to Lemma 4, we have_

_H(q(x0:N_ )) =H(q(x0)) + EqH(q(x1:N _|x0))_

=H(q(x0)) + EqH(q(xN _|x0)) +_


EqH(q(xn 1 **_xn, x0))._**
_−_ _|_
_n=2_

X

_N_

EqH(q(xn 1 **_xn, x0))._**
_−_ _|_
_n=2_

X


-----

**Lemma 7. (Entropy of a generalized DDPM forward process) Suppose q(x1:N** _|x0) is Markov,_
_q(xN_ **_x0) is Gaussian with covariance βN_** **_I and q(xn_** 1 **_xn, x0) is Gaussian with covariance λ[2]n[I][,]_**
_|_ _−_ _|_
_then_


_H(q(x0:N_ )) = H(q(x0)) + _[d]_

2 [log(2][πeβ][N] [) +][ d]2

_Proof. Directly derived from Lemma 6._


log(2πeλ[2]n[)][.]
_n=2_

X


**Lemma 8. (KL to a Markov chain) Suppose q(x0:N** ) is a probability distribution and p(x0:N ) =


_p(xN_ ) _n=1_ _p(xn−1|xn) is a Markov chain, then we have_
Q


EqDKL(q(x0:N 1 **_xN_** ) _p(x0:N_ 1 **_xN_** )) =
_−_ _|_ _||_ _−_ _|_


EqDKL(q(xn 1 **_xn)_** _p(xn_ 1 **_xn)) + c,_**
_−_ _|_ _||_ _−_ _|_
_n=1_

X


_where c =_ EqH(q(xn 1 **_xn))_** EqH(q(x0:N 1 **_xN_** )) is only related to q. Particularly, if

_n=1_ _−_ _|_ _−_ _−_ _|_

_q(x0:N_ ) is also a Markov chain, thenP _c = 0._


_Proof._

EqDKL(q(x0:N 1 **_xN_** ) _p(x0:N_ 1 **_xN_** )) = Eq log p(x0:N 1 **_xN_** ) EqH(q(x0:N 1 **_xN_** ))
_−_ _|_ _||_ _−_ _|_ _−_ _−_ _|_ _−_ _−_ _|_


= Eq log p(xn 1 **_xn)_** EqH(q(x0:N 1 **_xN_** ))
_−_ _−_ _|_ _−_ _−_ _|_

_n=1_

X


EqDKL(q(xn 1 **_xn)_** _p(xn_ 1 **_xn)) +_**
_−_ _|_ _||_ _−_ _|_
_n=1_

X


EqH(q(xn 1 **_xn))_** EqH(q(x0:N 1 **_xN_** )).
_−_ _|_ _−_ _−_ _|_
_n=1_

X


Let c =


EqH(q(xn 1 **_xn))_** EqH(q(x0:N 1 **_xN_** )), then
_n=1_ _−_ _|_ _−_ _−_ _|_

P


EqDKL(q(x0:N 1 **_xN_** ) _p(x0:N_ 1 **_xN_** )) =
_−_ _|_ _||_ _−_ _|_


EqDKL(q(xn 1 **_xn)_** _p(xn_ 1 **_xn)) + c._**
_−_ _|_ _||_ _−_ _|_
_n=1_

X


If q(x0:N ) is also a Markov chain, according to Lemma 4, we have c = 0.

**Lemma 9. (The optimal Markov reverse process with Gaussian transitions is equivalent to moment**


_matching) Suppose q(x0:N_ ) is probability density function and p(x0:N ) = _n=1_ _p(xn−1|xn)p(xN_ )

_is a Gaussian Markov chain with p(xn_ 1 **_xn) =_** (xn 1 **_µn(xn), σn[2]_** **_[I][)][, then the joint KL opti-]Q_**
_−_ _|_ _N_ _−_ _|_
_mization_


min _DKL(q(x0:N_ ) _p(x0:N_ ))
**_µn,σn[2]_** _[}][N]n=1_ _||_
_{_

_has an optimal solution_

**_µ[∗]n[(][x][n][) =][ E]q(xn−1|xn)[[][x][n][−][1][]][,]_** _σn[∗][2]_ [=][ E]qn(xn) tr(Covq(xn−d1|xn)[xn−1])

_which match the first two moments of q(xn−1|xn). The corresponding optimal KL is_


_DKL(q(x0:N_ ) _p[∗](x0:N_ )) = H(q(xN ), p(xN )) + _[d]_
_||_ 2


log(2πeσn[∗][2][)][ −] _[H][(][q][(][x][0:][N]_ [))][.]
_n=1_

X


**Remark. Lemma 9 doesn’t assume the form of q(x0:N** ), thereby it can be applied to more general
_Gaussian models, such as multi-layer VAEs with Gaussian decoders (Rezende et al., 2014; Burda_
_et al., 2015). In this case, q(x1:N_ **_x0) is the hierarchical encoders of multi-layer VAEs._**
_|_


-----

_Proof. According to Lemma 8, we have_

_DKL(q(x0:N_ ) _p(x0:N_ )) = DKL(q(xN ) _p(xN_ )) +
_||_ _||_


EqDKL(q(xn 1 **_xn)_** _p(xn_ 1 **_xn)) + c,_**
_−_ _|_ _||_ _−_ _|_
_n=1_

X


where c =


EqH(q(xn 1 **_xn))_** EqH(q(x0:N 1 **_xN_** )).
_n=1_ _−_ _|_ _−_ _−_ _|_

P


Since EqDKL(q(xn 1 **_xn)_** _p(xn_ 1 **_xn)) is only related to µn(_** ) and σn[2] [, the joint KL optimization]
_−_ _|_ _||_ _−_ _|_ _·_
is decomposed into n independent optimization sub-problems:

min EqDKL(q(xn 1 **_xn)_** _p(xn_ 1 **_xn)),_** 1 _n_ _N._
**_µn,σn[2]_** _−_ _|_ _||_ _−_ _|_ _≤_ _≤_

According to Lemma 2, we have

EqDKL(q(xn 1 **_xn)_** _p(xn_ 1 **_xn))_**
_−_ _|_ _||_ _−_ _|_
=EqDKL( (xn 1 Eq(xn 1 **_xn)[xn_** 1], Covq(xn 1 **_xn)[xn_** 1]) _p(xn_ 1 **_xn))_**
_N_ _−_ _|_ _−_ _|_ _−_ _−_ _|_ _−_ _||_ _−_ _|_

+ EqH( (xn 1 Eq(xn 1 **_xn)[xn_** 1], Covq(xn 1 **_xn)[xn_** 1])) EqH(q(xn 1 **_xn))_**
_N_ _−_ _|_ _−_ _|_ _−_ _−_ _|_ _−_ _−_ _−_ _|_

=F(σn[2] [) +][ G][(][σ]n[2] _[,][ µ][n][) +][ c][′]_

where


_F(σn[2]_ [) = 1]2 _σn[−][2][E][q]_ [tr(Cov]q(xn−1|xn)[[][x][n][−][1][]) +][ d][ log][ σ]n[2] _,_

 


_G(σn[2]_ _[,][ µ][n][) = 1]2_ _[σ]n[−][2][E][q][||][E]q(xn−1|xn)[[][x][n][−][1][]][ −]_ **_[µ][n][(][x][n][)][||][2][,]_**

and c[′] = _[d]2_ [log(2][π][)][ −] [E][q][H][(][q][(][x][n][−][1][|][x][n][))][. The optimal][ µ]n[∗] [(][x][n][)][ is achieved when]

Eq(xn 1 **_xn)[xn_** 1] **_µn(xn)_** = 0.
_||_ _−_ _|_ _−_ _−_ _||[2]_


Thereby, µ[∗]n[(][x][n][) =][ E]q(xn 1 **_xn)[[][x][n][−][1][]][. In this case,][ G][(][σ]n[2]_** _[,][ µ][∗]n[) = 0][ and we only need to consider]_
_−_ _|_
_F(σn[2]_ [)][ for the optimal][ σ]n[∗][2][. By calculating the gradient of][ F][, we know that][ F][ gets its minimum at]

_σn[∗][2]_ [=][ E][q] tr(Covq(xn−1|xn)[xn−1]) _._

_d_

In the optimal case, F(σn[∗][2][) =][ d]2 [(1 + log][ σ]n[∗][2][)][ and]


_EqDKL(q(xn_ 1 **_xn)_** _p[∗](xn_ 1 **_xn)) =_** _[d]_ _n_ [)][ −] [E][q][H][(][q][(][x][n][−][1][|][x][n][))][.]
_−_ _|_ _||_ _−_ _|_ 2 [log(2][πeσ][∗][2]

As a result,

_DKL(q(x0:N_ ) _p[∗](x0:N_ ))
_||_


_d_
2 [log(2][πeσ]n[∗][2][)][ −]


EqH(q(xn 1 **_xn))_**
_−_ _|_
_n=1_

X


=DKL(q(xN ) _p(xN_ )) +
_||_


_n=1_


EqH(q(xn 1 **_xn))_** (H(q(x0:N )) _H(q(xN_ )))
_−_ _|_ _−_ _−_
_n=1_

X


_d_
2 [log(2][πeσ]n[∗][2][)][ −] _[H][(][q][(][x][0:][N]_ [))][.]


=H(q(xN ), p(xN )) +


_n=1_


**Lemma 10. (Marginal score function) Suppose q(v, w) is a probability distribution, then**

**_w log q(w) =Eq(v_** **_w)_** **_w log q(w_** **_v)_**
_∇_ _|_ _∇_ _|_


-----

_Proof. According to Eq(v_ **_w)_** **_w log q(v_** **_w) =_** **_wq(v_** **_w)dv =_** **_w_** _q(v_ **_w)dv = 0, we have_**
_|_ _∇_ _|_ _∇_ _|_ _∇_ _|_

**_w log q(w) =_** **_w log q(w) +R Eq(v_** **_w)_** **_w log q(v_** **_w)R_**
_∇_ _∇_ _|_ _∇_ _|_

=Eq(v **_w)_** **_w log q(v, w) = Eq(v_** **_w)_** **_w log q(w_** **_v)._**
_|_ _∇_ _|_ _∇_ _|_

**Lemma 11. (Score representation of conditional expectation and covariance) Suppose q(v, w) =**
_q(v)q(w|v), where q(w|v) = N_ (w|[√]αv, βI), then

1
Eq(v **_w)[v] =_** (w + β **_w log q(w)),_**
_|_ _√α_ _∇_


Eq(w)Covq(v **_w)[v] =_** _[β]_ **_I_** _βEq(w)_ **_w log q(w)_** **_w log q(w)[⊤][
]_**
_|_ _α_ _−_ _∇_ _∇_

tr(Covq(v **_w)[v])_**   **_w log q(w)_**
Eq(w) _|_ = _[β]_ 1 _βEq(w)_ _||∇_ _||[2]_ _._

_d_ _α_ _−_ _d_

 


_Proof. According to Lemma 10, we have_

**_w_** _αv_
**_w log q(w) = Eq(v_** **_w)_** **_w log q(w_** **_v) =_** Eq(v **_w)_** _−_ _[√]_ _._
_∇_ _|_ _∇_ _|_ _−_ _|_ _β_

Thereby, Eq(v|w)[v] = _√1α_ (w + β∇w log q(w)). Furthermore, we have

Eq(w)Covq(v **_w)[v] =_** _[β][2]_ ]
_|_ _α_ [E][q][(][w][)][Cov][q][(][v][|][w][)][[] **_[w][ −√]β_** _[α][v]_

= _[β][2]_ Eq(v **_w)(_** **_[w][ −√][α][v]_** )( **_[w][ −√][α][v]_** )[⊤] Eq(v **_w)[_** **_[w][ −√][α][v]_** ]Eq(v **_w)[_** **_[w][ −√][α][v]_** ][⊤]

_α_ [E][q][(][w][)] _|_ _β_ _β_ _−_ _|_ _β_ _|_ _β_

 

1

= _[β][2]_

_α_ _β[2][ E][q][(][v][)][E][q][(][w][|][v][)][(][w][ −√][α][v][)(][w][ −√][α][v][)][⊤]_ _[−]_ [E][q][(][w][)][∇][w][ log][ q][(][w][)][∇][w][ log][ q][(][w][)][⊤]

 

1

= _[β][2]_

_α_ _β[2][ E][q][(][v][)][Cov][q][(][w][|][v][)][w][ −]_ [E][q][(][w][)][∇][w][ log][ q][(][w][)][∇][w][ log][ q][(][w][)][⊤]

 

1

= _[β][2]_

_α_ _β[2][ E][q][(][v][)][β][I][ −]_ [E][q][(][w][)][∇][w][ log][ q][(][w][)][∇][w][ log][ q][(][w][)][⊤]

 

1

= _[β][2]_ = _[β]_

_α_ _β_ **_[I][ −]_** [E][q][(][w][)][∇][w][ log][ q][(][w][)][∇][w][ log][ q][(][w][)][⊤] _α_ [(][I][ −] _[β][E][q][(][w][)][∇][w][ log][ q][(][w][)][∇][w][ log][ q][(][w][)][⊤][)][.]_

 


Taking the trace, we have

Eq(w) tr(Covq(v|w)[v])


**_w log q(w)_**

= _[β]_ _||∇_ _||[2]_

_α_ [(1][ −] _[β][E][q][(][w][)]_ _d_


).


**Lemma 12. (Bounded covariance of a bounded distribution) Suppose q(x) is a bounded distribution**
_in [a, b][d], then_ tr(Covdq(x)[x]) _≤_ ( _[b][−]2_ _[a]_ [)][2][.]

_Proof._


= [E][q][(][x][)][||][x][ −] _[a][+]2_ _[b]_ _[||][2][ −||][E][x][ −]_ _[a][+]2_ _[b]_ _[||][2]_

_d_


= [tr(Cov][q][(][x][)][[][x][ −] _[a][+]2_ _[b]_ [])]


tr(Covq(x)[x])


2

_[||][2]_

_≤_ [E][q][(][x][)][||][x]d[ −] _[a][+][b]_


( _[b][ −]_ _[a]_ )[2].
_≤_ 2


-----

**Lemma 13. (Convert the moments of q(xn** 1 **_xn) to moments of q(x0_** **_xn)) The optimal solution_**
_−_ _|_ _|_
**_µ[∗]n[(][x][n][)][ and][ σ]n[∗][2]_** _[to Eq. (4) can be represented by the first two moments of][ q][(][x][0][|][x][n][)]_

**_µ[∗]n[(][x][n][) = ˜]µn(xn, Eq(x0_** **_xn)x0)_**
_|_

2

_σn[∗][2]_ [=][ λ]n[2] [+] _αn_ 1 _βn_ 1 _λ[2]n_ _αn_ Eq(xn) tr(Covq(x0|xn)[x0])

_−_ _−_ _−_ _−_ _[·]_ s _βn_ ! _d_
q

p

_where qn(xn) is the marginal distribution of the forward process at timestep n and d is the dimension_
_of the data._

_Proof. According to Lemma 9, the optimal µ[∗]n_ [and][ σ]n[∗][2] [under KL minimization is]

**_µ[∗]n[(][x][n][) =][ E]q(xn−1|xn)[[][x][n][−][1][]][,]_** _σn[∗][2]_ [=][ E]qn(xn) tr(Covq(xn−d1|xn)[xn−1]) _._

We further derive µ[∗]n[. Since][ ˜]µn(xn, x0) is linear w.r.t. x0, we have

**_µ[∗]n[(][x][n][) =][ E]q(xn_** 1 **_xn)[[][x][n][−][1][] =][ E]q(x0_** **_xn)[E]q(xn_** 1 **_xn,x0)[[][x][n][−][1][]]_**
_−_ _|_ _|_ _−_ _|_

=Eq(x0 **_xn) ˜µn(xn, x0) = ˜µn(xn, Eq(x0_** **_xn)x0)._**
_|_ _|_

Then we consider σn[∗][2][. According to the law of total variance, we have]

Covq(xn 1 **_xn)[xn_** 1] = Eq(x0 **_xn)Covq(xn_** 1 **_xn,x0)[xn_** 1] + Covq(x0 **_xn)Eq(xn_** 1 **_xn,x0)[xn_** 1]
_−_ _|_ _−_ _|_ _−_ _|_ _−_ _|_ _−_ _|_ _−_


_αn_
_βn_ )[2]Covq(x0|xn)[x0].


=λ[2]n[I][ + Cov]q(x0 **_xn)µ[˜]_** _n(xn, x0) = λ[2]n[I][ + (]_
_|_

Thereby,


_βn−1 −_ _λ[2]n_ _[·]_


_αn−1 −_


_σn[∗][2]_ [=][ E]qn(xn) tr(Covq(xn−1|xn)[xn−1])


_αn_ )[2]Eq(xn) tr(Covq(x0|xn)[x0])
_βn_ _d_


=λ[2]n [+ (]


_αn−1 −_


_βn−1 −_ _λ[2]n_ _[·]_


A.2 PROOF OF THEOREM 1

**Theorem 1. (Score representation of the optimal solution to Eq. (4), proof in Appendix A.2)**

_The optimal solution µ[∗]n[(][x][n][)][ and][ σ]n[∗][2]_ _[to Eq. (4) are]_


**_µ[∗]n[(][x][n][) = ˜]µn_**

_σn[∗][2]_ [=][ λ]n[2] [+]




1
**_xn,_** _√αn_ (xn + βn∇xn log qn(xn)) _,_ (6)


2

_βn_ **_xn log qn(xn)_**
_αn_ _−_ _βn−1 −_ _λ[2]n_ 1 − _βnEqn(xn)_ _||∇_ _d_ _||[2]_ _,_ (7)
q  




_where qn(xn) is the marginal distribution of the forward process at the timestep n and d is the_
_dimension of the data._

_Proof. According to Lemma 11 and Lemma 13, we have_

1
**_µ[∗]n[(][x][n][) = ˜]µn(xn, Eq(x0_** **_xn)x0) = ˜µn(xn,_** (xn + βn **_xn log q(xn))),_**
_|_ _√αn_ _∇_


-----

and


_αn_ )[2]Eq(xn) tr(Covq(x0|xn)[x0])
_βn_ _d_


_σn[∗][2]_ [=][ λ]n[2] [+ (]


_αn−1 −_


_βn−1 −_ _λ[2]n_ _[·]_


_αn_ **_xn log q(xn)_**
)[2][ β][n] (1 _βnEq(xn)_ _||∇_ _||[2]_
_βn_ _αn_ _−_ _d_


=λ[2]n [+ (]

=λ[2]n [+ (]


_βn−1 −_ _λ[2]n_ _[·]_


_αn−1 −_

_βn_
_αn_ _−_
q


**_xn log q(xn)_**
_βn_ 1 _λ[2]n[)][2][(1][ −]_ _[β]n[E]q(xn)_ _||∇_ _||[2]_
_−_ _−_ _d_


).


A.3 PROOF OF THEOREM 2

**Theorem 2. (Bounds of the optimal reverse variance, proof in Appendix A.3)**

_σn[∗][2]_ _[has the following lower and upper bounds:]_


_βn_
_αn_


_λ[2]n_ _[≤]_ _[σ]n[∗][2]_ _[≤]_ _[λ]n[2]_ [+]


(11)


_βn−1 −_ _λ[2]n_


_If we further assume q(x0) is a bounded distribution in [a, b][d], where d is the dimension of data,_
_then σn[∗][2]_ _[can be further upper bounded by]_

2

2

_αn_ _b_ _a_

_σn[∗][2]_ _n_ [+] _αn_ 1 _βn_ 1 _λ[2]n_ _−_ _._ (12)

_[≤]_ _[λ][2]_ _−_ _−_ q _−_ _−_ _[·]_ s _βn_ !  2 

p

_Proof. According to Lemma 13 and Theorem 1, we have_


_βn_
_αn_


_λ[2]n_ _[≤]_ _[σ]n[∗][2]_ _[≤]_ _[λ]n[2]_ [+ (]


_βn_ 1 _λ[2]n[)][2][.]_
_−_ _−_


If we further q(x0) assume is a bounded distribution in [a, b][d], then q(x0 **_xn) is also a bounded_**
_|_
distribution in [a, b][d]. According to Lemma 12, we have


Eq(xn) tr(Covq(x0|xn)[x0])

_d_

Combining with Lemma 13, we have


( _[b][ −]_ _[a]_ )[2].
_≤_ 2


_αn_ )[2]Eq(xn) tr(Covq(x0|xn)[x0])
_βn_ _d_


_σn[∗][2]_ [=][λ]n[2] [+ (]

_≤λ[2]n_ [+ (]


_αn−1 −_

_αn−1 −_


_βn−1 −_ _λ[2]n_ _[·]_

_βn−1 −_ _λ[2]n_ _[·]_


_αn_
)[2]( _[b][ −]_ _[a]_ )[2].
_βn_ 2


A.4 PROOF OF THE DECOMPOSED OPTIMAL KL

**Theorem 3. (Decomposed optimal KL, proof in Appendix A.4)**

_The KL divergence between the shorter forward process and its optimal reverse process is_


_DKL(q(x0, xτ1_ _, · · ·, xτK_ )||p[∗](x0, xτ1 _, · · ·, xτK_ )) = _[d]2_


_J(τk−1, τk) + c,_
_k=2_

X


_σ[∗][2]_
_where J(τk−1, τk) = log_ _λτk[2]τk−−11||τkτk_ _and c is a constant unrelated to the trajectory τ_ _._


-----

_Proof. According to Lemma 7 and Lemma 9, we have_

_DKL(q(x0, xτ1_ _,_ _, xτK_ ) _p[∗](x0, xτ1_ _,_ _, xτK_ ))
_· · ·_ _||_ _· · ·_
=EqDKL(q(x0|xτ1 _, · · ·, xτK_ )||p[∗](x0|x1)) + DKL(q(xτ1 _, · · ·, xτK_ )||p[∗](xτ1 _, · · ·, xτK_ ))
=EqDKL(q(x0|xτ1 _, · · ·, xτK_ )||p[∗](x0|x1)) + H(q(xN ), p(xN ))


+ _[d]_


log(2πeστ[∗]k[2] 1 _τk_ [)][ −] _[H][(][q][(][x][τ]1_ _[,][ · · ·][,][ x][τ]N_ [))]
_−_ _|_
_k=2_

X


= Eq log p[∗](x0 **_x1) + H(q(xN_** ), p(xN )) + _[d]_
_−_ _|_ 2

= Eq log p[∗](x0 **_x1) + H(q(xN_** ), p(xN )) + _[d]_
_−_ _|_ 2


log(2πeστ[∗]k[2] 1 _τk_ [)][ −] _[H][(][q][(][x][0][,][ x][τ]1_ _[,][ · · ·][,][ x][τ]K_ [))]
_−_ _|_
_k=2_

X

_K_

log(2πeστ[∗]k[2] 1 _τk_ [)]
_−_ _|_
_k=2_

X


_H(q(x0))_
_−_ _−_ _[d]2 [log(2][πeβ][N]_ [)][ −] _[d]2_


log(2πeλ[2]τk 1 _τk_ [)]
_−_ _|_
_k=2_

X


_K_ log _στ[∗]k[2]−1|τk_ _H(q(x0))_

_k=2_ _λ[2]τk−1|τk_ _−_ _−_ _[d]2 [log(2][πeβ][N]_ [)][.]

X


= Eq log p[∗](x0 **_x1) + H(q(xN_** ), p(xN )) + _[d]_
_−_ _|_ 2


_σ[∗][2]_
Let J(τk−1, τk) = log _λτk[2]τk−−11||τkτk_ and c = −Eq log p[∗](x0|x1) + H(q(xN ), p(xN )) − _H(q(x0)) −_

_d_
2 [log(2][πeβ][N] [)][, then][ c][ is a constant unrelated to the trajectory][ τ][ and]


_DKL(q(x0, xτ1_ _, · · ·, xτK_ )||p[∗](x0, xτ1 _, · · ·, xτK_ )) = _[d]2_

A.5 THE FORMAL RESULT FOR SECTION 5 AND ITS PROOF


_J(τk−1, τk) + c._
_k=2_

X


Here we present the formal result of the relationship between the score function and the data covariance matrix mentioned in Section 5.
**Proposition 1. (Proof in Appendix A.5) The expected conditional covariance matrix of the data**
_distribution is determined by the score function ∇xn log qn(xn) as follows:_

Eq(xn)Covq(x0 **_xn)[x0] =_** _[β][n]_ **_I_** _βnEqn(xn)_ **_xn log qn(xn)_** **_xn log qn(xn)[⊤][
]_** _,_ (15)
_|_ _αn_ _−_ _∇_ _∇_

 

_which contributes to the data covariance matrix according to the law of total variance_

Covq(x0)[x0] = Eq(xn)Covq(x0 **_xn)[x0] + Covq(xn)Eq(x0_** **_xn)[x0]._** (16)
_|_ _|_

_Proof. Since q(xn_ **_x0) =_** (xn _αnx0, βnI), according to Lemma 11, we have_
_|_ _N_ _|[√]_

Eq(xn)Covq(x0 **_xn)[x0] =_** _[β][n]_ (I _βnEqn(xn)_ **_xn log qn(xn)_** **_xn log qn(xn)[⊤])._**
_|_ _αn_ _−_ _∇_ _∇_

The law of total variance is a classical result in statistics. Here we prove it for completeness:


Eq(xn)Covq(x0 **_xn)[x0] + Covq(xn)Eq(x0_** **_xn)[x0]_**
_|_ _|_

=Eq(xn) Eq(x0|xn)x0x[⊤]0 _q(x0|xn)[[][x][0][]][E]q(x0|xn)[[][x][0][]][⊤][
]_

_[−]_ [E]

+ Eq(xn) Eq(x0 **_xn)[x0]Eq(x0_** **_xn)[x0][⊤][
]_** Eq(xn)Eq(x0 **_xn)[x0]_** Eq(xn)Eq(x0 **_xn)[x0]_** _⊤_
_|_ _|_ _−_ _|_ _|_

=Eq(x0)x0x[⊤]0 _q(x0)[[][x][0][]][E]q(x0)[[][x][0][]][⊤]_ [= Cov] _q(x0)[[][x][0][]][.]_ 
  


_[−]_ [E]


-----

**Algorithm 1 The DP algorithm for the least-cost-path problem (Watson et al., 2021)**

1: Input: Cost function J(s, t) and integers K, N (1 ≤ _K ≤_ _N_ )
2: Output: The least-cost-trajectory 1 = τ1 < · · · < τK = N
3: C ←{∞}1≤k,n≤N, D ←{−1}1≤k,n≤N
4: C[1, 1] ← 0
5: for k = 2 to K do _▷_ Calculate C and D

6: _CJ ←{C[k −_ 1, s] + J(s, n)}1≤s≤N,k≤n≤N

7: _C[k, k :] ←_ (min(CJ[:, k]), min(CJ[:, k + 1]), · · ·, min(CJ[:, N ]))

8: _D[k, k :] ←_ (arg min(CJ[:, k]), arg min(CJ[:, k + 1]), · · ·, arg min(CJ[:, N ]))

9: end for

10: τK = N
11: for k = K to 2 do _▷_ Calculate τ

12:13: end forτk−1 ← _D[k, τk]_

14: return τ

B THE DP ALGORITHM FOR THE LEAST-COST-PATH PROBLEM


Given a cost function J(s, t) with 1 ≤ _s < t and k, n ≥_ 1, we want to find a trajectory 1 =
_τ1 < · · · < τk = n of k nodes starting from 1 and terminating at n, s.t., the total cost J(τ1, τ2) +_
_J(τ2, τ3) + · · · + J(τk−1, τk) is minimized. Such a problem can be solved by the DP algorithm_
proposed by Watson et al. (2021). Let C[k, n] be the minimized cost of the optimal trajectory, and
_D[k, n] be the τk_ 1 of the optimal trajectory. For simplicity, we also let J(s, t) = for s _t_ 1.
_−_ _∞_ _≥_ _≥_

0 _n = 1_
Then for k = 1, we have C[1, n] = and D[1, n] = 1 (here and 1
_N_ _n > 1_ _−_ _∞_ _−_
 _∞_ _≥_

represent undefined values for simplicity). For N ≥ _k ≥_ 2, we have


_∞_ 1 ≤ _n < k_
min min _N_ _n_ _k,_
( _k_ 1 _s_ _n_ 1 _[C][[][k][ −]_ [1][, s][] +][ J][(][s, n][) =] 1 _s_ _N_ _[C][[][k][ −]_ [1][, s][] +][ J][(][s, n][)] _≥_ _≥_
_−_ _≤_ _≤_ _−_ _≤_ _≤_

1 1 _n < k_
_−_ _≤_
( _k_ arg min1 _s_ _n_ 1 _C[k −_ 1, s] + J(s, n) = arg min1 _s_ _N_ _C[k −_ 1, s] + J(s, n) _N ≥_ _n ≥_ _k._
_−_ _≤_ _≤_ _−_ _≤_ _≤_


_C[k, n] =_

_D[k, n] =_


As long as D is calculated, we can get the optimal trajectory recursively by τK = N and τk 1 =
_−_
_D[k, τk]. We summarize the algorithm in Algorithm 1._

C THE BOUNDS OF THE OPTIMAL REVERSE VARIANCE CONSTRAINED ON A
TRAJECTORY

In Section 4, we derive the optimal reverse variance constrained on a trajectory. Indeed, the optimal
reverse variance can also be bounded similar to Theorem 2. We formalize it in Corollary 1.

**Corollary 1. (Bounds of the optimal reverse variance constrained on a trajectory)**

_στ[∗]k[2]−1|τk_ _[has the following lower and upper bounds:]_


_βτk_

_ατk|τk−1_


_λ[2]τk−1|τk_ _τk−1|τk_ _τk−1|τk_ [+]

_[≤]_ _[σ][∗][2]_ _[≤]_ _[λ][2]_


_βτk−1_ _λ[2]τk−1|τk_
_−_


_If we further assume q(x0) is a bounded distribution in [a, b][d], where d is the dimension of data,_
_then σn[∗][2]_ _[can be further upper bounded by]_

2

_στ[∗]k[2]−1|τk_ _[≤]_ _[λ]τ[2]k−1|τk_ [+] _ατk−1 −_ _βτk−1 −_ _λ[2]τk−1|τk_ _[·]_ s _αβττkk_ ! ( _[b][ −]2_ _[a]_ )[2].

q
p


-----

D SIMPLIFIED RESULTS FOR THE DDPM FORWARD PROCESS

The optimal solution µ[∗]n[(][x][n][)][ and][ σ]n[∗][2] [in Theorem 1 and the bounds of][ σ]n[∗][2] [in Theorem 2 can be]
directly simplified for the DDPM forward process by letting λ[2]n [= ˜]βn. We list the simplified results
in Corollary 2 and Corollary 3.
**Corollary 2. (Simplified score representation of the optimal solution)**

_When λ[2]n_ [= ˜]βn, the optimal solution µ[∗]n[(][x][n][)][ and][ σ]n[∗][2] _[to Eq. (4) are]_

1
**_µ[∗]n[(][x][n][) =]_** (xn + βn **_xn log qn(xn)),_**
_√αn_ _∇_


**_xn log qn(xn)_**

_σn[∗][2]_ [=][ β][n] (1 _βnEqn(xn)_ _||∇_ _||[2]_

_αn_ _−_ _d_

**Corollary 3. (Simplified bounds of the optimal reverse variance)**

_When λ[2]n_ [= ˜]βn, σn[∗][2] _[has the following lower and upper bounds:]_

_β˜n ≤_ _σn[∗][2]_ _[≤]_ _α[β][n]n_ _._


).


_If we further assume q(x0) is a bounded distribution in [a, b][d], where d is the dimension of data,_
_then σn[∗][2]_ _[can be further upper bounded by]_

2

_σn[∗][2]_ _[≤]_ _β[˜]n +_ _[α][n]β[−]2n[1][β]n[2]_  _b −2_ _a_  _._

As for the shorter forward process defined in Eq. (13), it also includes the DDPM as a special case

_β_

when λ[2]τk−1|τk [= ˜]βτk−1|τk, where _β[˜]τk−1|τk :=_ _βτkτk−1_ _βτk|τk−1_ . Similar to Corollary 2, the optimal

mean and variance of its reverse process can also be simplified for DDPMs by letting λ[2]τk−1|τk [=]
_β˜τk−1|τk_ . Formally, the simplified optimal mean and variance are


1
**_µ[∗]τk−1|τk_** [(][x][τ]k [) =] _√ατk_ _τk_ 1 (xτk + βτk|τk−1 _∇xτk log qτk_ (xτk )),

_|_ _−_

_στ[∗]k[2]−1|τk_ [=][ β]α[τ]τ[k]k[|]|[τ]τ[k]k[−]−[1]1 (1 − _βτk|τk−1_ Eqτk (xτk ) _||∇xτk log qd_ _τk_ (xτk )||[2]


).


Besides, Theorem 3 can also be simplified for DDPMs. We list the simplified result in Corollary 4.
**Corollary 4. (Simplified decomposed optimal KL)**

_When λ[2]n_ [= ˜]βn, the KL divergence between the subprocess and its optimal reverse process is


_DKL(q(x0, xτ1_ _, · · ·, xτK_ )||p[∗](x0, xτ1 _, · · ·, xτK_ )) = _[d]2_


_J(τk−1, τk) + c,_
_k=2_

X


_where J(τk−1, τk) = log(1 −_ _βτk|τk−1_ Eqτk (xτk ) _||∇xτk log qd_ _τk_ (xτk )||[2] ),

_and c is a constant unrelated to the trajectory τ_ _._


E EXTENSION TO DIFFUSION PROCESS WITH CONTINUOUS TIMESTEPS

Song et al. (2020b) generalizes the diffusion process to continuous timesteps by introducing a
stochastic differential equation (SDE) dz = f (t)zdt + g(t)dw. Without loss of generality, we
consider the parameterization of f (t) and g(t) introduced by Kingma et al. (2021)


_f_ (t) = [1]


d log αt

dt _,_ _g(t)[2]_ = [d]d[β]t[t] dt _βt,_

_[−]_ [d log][ α][t]


-----

where αt and βt are scalar-valued functions satisfying some regular conditions (Kingma et al., 2021)
with domain t ∈ [0, 1]. Such a parameterization induces a diffusion process on continuous timesteps
_q(x0, z[0,1]), s.t.,_

_q(zt_ **_x0) =_** (zt _αtx0, βtI),_ _t_ [0, 1],
_|_ _N_ _|[√]_ _∀_ _∈_
_q(zt|zs) = N_ (zt|[√]αt|szs, βt|sI), _∀0 ≤_ _s < t ≤_ 1,

where αt _s := αt/αs and βt_ _s := βt_ _αt_ _sβs._
_|_ _|_ _|_
_−_

E.1 ANALYTIC ESTIMATE OF THE OPTIMAL REVERSE VARIANCE

Kingma et al. (2021) introduce p(zs **_zt) =_** (zs **_µs_** _t(zt), σs[2]_ _t[)][ (][s < t][) to reverse from timestep]_
_|_ _N_ _|_ _|_ _|_

_t to timestep s, where σs[2]|t_ [is fixed to][ β]β[s]t _[β][s][|][t][. In contrast, we show that][ σ]s[2]|t_ [also has an optimal]

solution in an analytic form of the score function under the sense of KL minimization. According to
Lemma 9 and Lemma 11, we have


1
**_µ[∗]s_** _t[(][z][t][) =][ E][q][(][z]s[|][z]t[)][[][z][s][] =]_ (zt + βt _s_ **_zt log q(zt)),_**
_|_ _√αt_ _s_ _|_ _∇_

_|_

_σs[∗]|[2]t_ [=][ E][q] tr(Covq(zds|zt)[zs]) = _α[β][t]t[|]|[s]s_ (1 − _βt|sEq(zt)_ _||∇zt logd q(zt)||[2]_


).


Thereby, both the optimal mean and variance have a closed form expression w.r.t. the score function.
In this case, we first estimate the expected mean squared norm of the score function by Γt for
_t ∈_ [0, 1], where

**_st(zt)_**
Γt = Eq(zt) _||_ _||[2]_ _._

_d_

Notice that there are infinite timesteps in [0, 1]. In practice, we can only choose a finite number of
timesteps 0 = t1 < _< tN = 1 and calculate Γtn_ . For a timestep t between tn 1 and tn, we can
_· · ·_ _−_
use a linear interpolation between Γtn−1 and Γtn . Then, we can estimate σs[∗]|[2]t [by]

_σˆs[2]_ _t_ [=][ β][t][|][s] (1 _βt_ _sΓt)._
_|_ _αt|s_ _−_ _|_

E.2 ANALYTIC ESTIMATION OF THE OPTIMAL REVERSE TRAJECTORY


Now we consider optimize the trajectory 0 = τ1 < · · · < τK = 1 in the sense of KL minimization

min
_τ1,_ _,τK_ _[D][KL][(][q][(][x][0][,][ z][τ][1]_ _[,][ · · ·][,][ z][τ][K]_ [)][||][p][∗][(][x][0][,][ z][τ][1] _[,][ · · ·][,][ z][τ][K]_ [))][.]

_···_

Similar to Theorem 3, the optimal KL is


_DKL(q(x0, zτ1_ _, · · ·, zτK_ )||p[∗](x0, zτ1 _, · · ·, zτK_ )) = _[d]2_


_J(τk−1, τk) + c,_
_k=2_

X


where J(τk−1, τk) = log(1 − _βτk|τk−1_ Eq _||∇zτk logd q(zτk )||[2]_ ) and c is unrelated to τ . The difference

is that J(s, t) is defined on a continuous range 0 ≤ _s < t ≤_ 1 and the DP algorithm is not directly
applicable. However, we can restrict J(s, t) on a finite number of timesteps 0 = t1 < · · · < tN = 1.
Then we can apply the DP algorithm (see Algorithm 1) to the restricted J(s, t).


-----

F EXPERIMENTAL DETAILS

F.1 DETAILS OF SCORE-BASED MODELS

[The CelebA 64x64 pretrained score-based model is provided in the official code (https://](https://github.com/ermongroup/ddim)
[github.com/ermongroup/ddim) of Song et al. (2020a). The LSUN Bedroom pretrained](https://github.com/ermongroup/ddim)
[score-based model is provided in the official code (https://github.com/hojonathanho/](https://github.com/hojonathanho/diffusion)
[diffusion) of Ho et al. (2020). Both of them have a total of N = 1000 timesteps and use the](https://github.com/hojonathanho/diffusion)
linear schedule (Ho et al., 2020) as the forward noise schedule.

The ImageNet 64x64 pretrained score-based model is the unconditional Lhybrid model provided
[in the official code (https://github.com/openai/improved-diffusion) of Nichol](https://github.com/openai/improved-diffusion)
& Dhariwal (2021). The model includes both the mean and variance networks, where the mean
network is trained with Eq. (5) as the standard DDPM (Ho et al., 2020) and the variance network is
trained with the Lvb objective. We only use the mean network. The model has a total of N = 4000
timesteps and its forward noise schedule is the cosine schedule (Nichol & Dhariwal, 2021).

The CIFAR10 score-based models are trained by ourselves. They have a total of N = 1000
timesteps and are trained with the linear forward noise schedule and the cosine forward noise schedule respectively. We use the same U-Net model architecture to Nichol & Dhariwal (2021). Following Nichol & Dhariwal (2021), we train 500K iterations with a batch size of 128, use a learning rate
of 0.0001 with the AdamW optimizer (Loshchilov & Hutter, 2017) and use an exponential moving average (EMA) with a rate of 0.9999. We save a checkpoint every 10K iterations and select
the checkpoint according to the FID results on 1000 samples generated under the reverse variance
_σn[2]_ [=][ β][n] [and full timesteps.]

F.2 LOG-LIKELIHOOD AND SAMPLING

Following Ho et al. (2020), we linearly scale the image data consisting of integers in {0, 1, · · ·, 255}
to [ 1, 1], and discretize the last reverse Markov transition p(x0 **_x1) to obtain discrete log-_**
_−_ _|_
likelihoods for image data.

Following Ho et al. (2020), at the end of sampling, we only display the mean of p(x0 **_x1) and discard_**
_|_
the noise. This is equivalent to setting a clipping threshold of zero for the noise scale σ1. Inspired
by this, when sampling, we also clip the noise scale σ2 of p(x1|x2), such that E|σ2ϵ| ≤ 2552 _[y][,]_

where ϵ is the standard Gaussian noise and y is the maximum tolerated perturbation of a channel. It
improves the sample quality, especially for our analytic estimate (see Appendix G.4). We clip σ2 for
all methods compared in Table 2, and choose y ∈{1, 2} according to the FID score. We find y = 2
works better on CIFAR10 (LS) and CelebA 64x64 with Analytic-DDPM. For other cases, we find
_y = 1 works better._

[We use the official implementation of FID to pytorch (https://github.com/mseitzer/](https://github.com/mseitzer/pytorch-fid)
[pytorch-fid). We calculate the FID score on 50K generated samples on all datasets. Follow-](https://github.com/mseitzer/pytorch-fid)
ing Nichol & Dhariwal (2021), the reference distribution statistics are computed on the full training
set for CIFAR10 and ImageNet 64x64. For CelebA 64x64 and LSUN Bedroom, the reference distribution statistics is computed on 50K training samples.

F.3 CHOICE OF THE NUMBER OF MONTE CARLO SAMPLES AND CALCULATION OF Γ

We use a maximal M without introducing too much computation. Specifically, we set M = 50000
on CIFAR10, M = 10000 on CelebA 64x64 and ImageNet 64x64 and M = 1000 on LSUN
Bedroom by default without a sweep. All of the samples are from the training dataset. We use the
default settings of M for all results in Table 1, Table 2 and Table 3.

We only calculate Γ in Eq. (8) once for a pretrained model, and Γ is reused during inference under
different settings (e.g., trajectories of smaller K) in Table 1, Table 2 and Table 3.


-----

F.4 IMPLEMENTATION OF THE EVEN TRAJECTORY

We follow Nichol & Dhariwal (2021) for the implementation of the even trajectory. Given the
number of timesteps K of a trajectory, we firstly determine the stride a = _KN_ _−11_ [. Then the][ k][th]
_−_
timestep is determined as round(1 + a(k − 1)).

F.5 EXPERIMENTAL DETAILS OF TABLE 3

In Table 3, the results of DDPM, DDIM and Analytic-DPM are based on the same scorebased models (i.e., those listed in Section F.1). We get the results of Improved DDPM by run[ning its official code and unconditional Lhybrid models (https://github.com/openai/](https://github.com/openai/improved-diffusion)
[improved-diffusion). As shown in Table 4, on the same dataset, the sizes as well as the](https://github.com/openai/improved-diffusion)
averaged time of a single function evaluation of these models are almost the same.

Table 4: Model size and the averaged time to run a model function evaluation with a batch size of
10 on one GeForce RTX 2080 Ti.

CIFAR10 CelebA 64x64 LSUN Bedroom

DDPM, DDIM, Analytic-DPM 200.44 MB / 29 ms 300.22 MB / 50 ms 433.63 MB / 438 ms
Improved DDPM 200.45 MB / 30 ms Missing model 433.64 MB / 439 ms

The DDPM and DDIM results on CIFAR10 are based on the quadratic trajectory following Song
et al. (2020a), which gets better FID than the even trajectory. The Analytic-DPM result is based on
the DDPM forward process on LSUN Bedroom, and based on the DDIM forward process on other
datasets. These choices achieve better efficiency than their alternatives.


-----

G ADDITIONAL RESULTS

G.1 VISUALIZATION OF REVERSE VARIANCES AND VARIATIONAL BOUND TERMS


Figure 1 visualizes the reverse variances and Lvb terms on CIFAR10 with the linear forward noise
schedule (LS). In Figure 2, we show more DDPM results on CIFAR10 with the cosine forward noise
schedule (CS), CelebA 64x64 and ImageNet 64x64.


16

2 2 2 7 2 12 2 3 2

2 14 2 9 13 2 7

2 8 2

variance variance2 11 2[3] variance2 11

2[3]

2 14 n n 2n 2 13 n n 2n 2 15 2[3] n n 2n

2[2] 2[5] 2[8] 2[2] 2[5] 2[8] 2[3] 2[7] 2[11]

timestep n timestep n timestep n


(a) CIFAR10 (CS)

0.4 n n 2n 0.3 n n 2n 0.6 n n 2n

(bits/dim)0.3 (bits/dim)0.2 0.1 (bits/dim)0.4 0.4

0.2

term 0.1 0.1 term 0.1 term 0.2
Lvb Lvb Lvb 2[0] 2[1]

2[2] 2[2]

2[2] 2[5] 2[8] 2[2] 2[5] 2[8] 2[2] 2[5] 2[8] 2[11]

timestep n timestep n timestep n


(d) CIFAR10 (CS)


(b) CelebA 64x64

n

2[2]

2[2] 2[5]

timestep n

(e) CelebA 64x64


(c) ImageNet 64x64

n n

2[0]

2[2] 2[5] 2[8]

timestep n

(f) ImageNet 64x64


0.3


0.6


Figure 2: Comparing our analytic estimate ˆσn[2] [and prior works with handcrafted variances][ β][n] [and]
_β˜n. (a-c) compare the values of the variance of different timesteps. (d-e) compare the term in Lvb_
corresponding to each timestep. The value of Lvb is the area under the corresponding curve.

G.2 ABLATION STUDY ON THE NUMBER OF MONTE CARLO SAMPLES


We show that only a small number of Monte Carlo (MC) samples M in Eq. (8) is enough for a small
MC variance. As shown in Figure 3, the values of Γn with M = 100 and M = 50000 Monte Carlo
samples are almost the same in a single trial. To explicitly see the variance, in Figure 4 and Figure 5,
we plot the mean, the standard deviation and the relative standard deviation (RSD) (i.e., the ratio of
the standard deviation to the mean) of a single Monte Carlo sample _[||][s][n][(][x]d_ _[n][)][||][2]_, xn _qn(xn) and_

Γn with different M respectively on CIFAR10 (LS). In all cases, the RSD decays fast as ∼ _n increases._
When n is small (e.g., n = 1), using M = 10 Monte Carlo samples can ensure that the RSD of Γn is
below 0.1, and using M = 100 Monte Carlo samples can ensure that the RSD of Γn is about 0.025.
When n > 100, the RSD of a single Monte Carlo sample is below 0.05, and using only M = 1
Monte Carlo sample can ensure the RSD of Γn is below 0.05. Overall, a small M like 10 and 100 is
sufficient for a small Monte Carlo variance.

Furthermore, we show that Analytic-DPM with a small M like 10 and 100 has a similar performance
to that with a large M . As shown in Figure 6 (a), using M = 100 or M = 50000 almost does not
affect the likelihood results on CIFAR10 (LS). In Table 5 (a), we show results with even smaller M
(e.g., M = 1, 3, 10). Under both the NLL and FID metrics, M = 10 achieves a similar result to that
of M = 50000. The results are similar on ImageNet 64x64, as shown in Figure 6 (b) and Table 5
(b). Notably, the expected performance of FID is almost not influenced by the choice of M .

As a result, Analytic-DPM consistently improves the baselines using a much smaller M (e.g., M =
10), as shown in Table 6.


-----

M=50000

4000 M=100

3000

n

2000

1000

0

10[0] 10[1] 10[2] 10[3]

timestep n


15000 M=10000M=100

10000

n

5000

0

10[0] 10[1] 10[2] 10[3]

timestep n


(a) CIFAR10 (LS)


(b) ImageNet 64x64


Figure 3: The value of Γn in a single trial with different number of Monte Carlo samples M .


4000

3000

2000

1000

0

10[0] 10[1] 10[2] 10[3]

timestep n


1250

1000

750

500

250

0

10[0] 10[1] 10[2] 10[3]

timestep n


0.25

0.20

0.15

0.10

0.05

10[0] 10[1] 10[2] 10[3]

timestep n


(a) Mean


(b) Standard deviation


(c) Relative standard deviation


Figure 4: The mean, the standard deviation and the relative standard deviation (RSD) (i.e., the ratio
of the standard deviation to the mean) of a single Monte Carlo sample _[||][s][n][(][x]d_ _[n][)][||][2]_, xn _qn(xn) at_

different n on CIFAR10 (LS). These values are estimated by 50000 samples. _∼_


4000

3000

2000

1000

0

10[0] 10[1] 10[2] 10[3]

timestep n


1250

M=1

1000 M=10M=100

750

500

250

0

10[0] 10[1] 10[2] 10[3]

timestep n


0.25 M=1
M=10

0.20 M=100

0.15

0.10

0.05

0.00

10[0] 10[1] 10[2] 10[3]

timestep n


(a) Mean


(b) Standard deviation


(c) Relative standard deviation


Figure 5: The mean, the standard deviation and the relative standard deviation (RSD) (i.e., the ratio
of the standard deviation to the mean) of Γn with different number of Monte Carlo samples M
at different n on CIFAR10 (LS). These values are directly calculated from the mean, the standard
deviation and the RSD of _[||][s][n][(][x]d_ _[n][)][||][2]_, xn _qn(xn) presented in Figure 4._

_∼_


-----

5.5

5.0

(bits/dim)4.5
nll 4.0

M=50000
M=100

3.5

10[1] 10[2] 10[3]

# timesteps K


5.0

4.5

(bits/dim)
nll 4.0

M=10000
M=100

10[1] 10[2] 10[3]

# timesteps K


(a) CIFAR10 (LS)


(b) ImageNet 64x64


Figure 6: The curves of NLL v.s. the number of timesteps K in a trajectory with different number
of Monte Carlo samples M, evaluated under σn[2] [= ˆ]σn[2] [and the even trajectory.]

Table 5: The negative log-likelihood (NLL) and the FID results of Analytic-DPM with different
number of Monte Carlo samples M . The results with M = 1, 3, 10, 100 are averaged by 5 runs. All
results are evaluated under the DDPM forward process and the even trajectory. We use K = 10 for
CIFAR10 (LS) and K = 25 for ImageNet 64x64.


(a) CIFAR10 (LS)

NLL ↓ FID ↓

_M = 1_ 6.220±1.126 34.05±4.97
_M = 3_ 5.689±0.424 34.29±2.88
_M = 10_ 5.469±0.005 33.69±2.10
_M = 100_ 5.468±0.004 34.63±0.68
_M = 50000_ 5.471 34.26


(b) ImageNet 64x64

NLL ↓ FID ↓

_M = 1_ 4.943±0.162 31.59±5.11
_M = 3_ 4.821±0.055 31.98±1.19
_M = 10_ 4.791±0.017 31.93±1.02
_M = 100_ 4.785±0.003 31.93±0.69
_M = 10000_ 4.783 32.56


Table 6: The NLL and FID comparison between Analytic-DDPM with M = 10 Monte Carlo
samples and DDPM. Results are evaluated under the even trajectory on CIFAR10 (LS).

# timesteps K 10 25 50 100 200 400

NLL ↓

Analytic-DDPM (M = 10) 5.47 4.80 4.38 4.07 3.85 3.71
DDPM 6.99 6.11 5.44 4.86 4.39 4.07

FID ↓

Analytic-DDPM (M = 10) 33.69 11.99 7.24 5.39 4.19 3.58
DDPM 44.45 21.83 15.21 10.94 8.23 4.86


G.3 TIGHTNESS OF THE BOUNDS

In Section 3.1 and Appendix C, we derive upper and lower bounds of the optimal reverse variance.
In this section, we show these bounds are tight numerically in practice. In Figure 7, we plot the
combined upper bound (i.e., the minimum of the upper bounds in Eq. (11) and Eq. (12)) and the
lower bound on CIFAR10. As shown in Figure 7 (a,c), the two bounds almost overlap under the fulltimesteps (K=N ) trajectory. When the trajectory has a smaller number of timesteps (e.g., K=100),
the two bounds also overlap when the timestep τk is large. These results empirically validate that
our bounds are tight, especially when the timestep is large.


-----

2 2 2 2

combined UBLB combined UBLB 2 2 combined UBLB 2 2 combined UBLB

2 8 2 8 2 8 2 8

2 14 2 14 2 14 2 14

2[2] 2[5] 2[8] 2[2] 2[5] 2[8] 2[2] 2[5] 2[8] 2[2] 2[5] 2[8]

timestep n timestep k timestep n timestep k


(a) LS, K=N


(b) LS, K=100


(c) CS, K=N


(d) CS, K=100


Figure 7: The combined upper bound (UB) and the lower bound (LB) under full-timesteps (K=N )
and 100-timesteps (K=100) trajectories on CIFAR10 (LS) and CIFAR10 (CS).

In Figure 8, we also plot the two upper bounds in Eq. (11) and Eq. (12) individually. The upper
bound in Eq. (11) is tighter when the timestep is small and the other one is tighter when the timestep
is large. Thereby, both upper bounds contribute to the combined upper bound.


2 2 2 1 UB in Eq.(11) UB in Eq.(11)

2[5] UB in Eq.(12) 2[12] UB in Eq.(12)

2 6 2 4 2 2 2[4]

2 10 UB in Eq.(11) 2 7 UB in Eq.(11) 2 9 2 4

UB in Eq.(12) UB in Eq.(12)

200 500 800 200 500 800 200 500 800 200 500 800

timestep n timestep k timestep n timestep k


(a) LS, K=N


(b) LS, K=100


(c) CS, K=N


(d) CS, K=100


Figure 8: The upper bounds (UB) in Eq. (11) and Eq. (12) under full-timesteps (K=N ) and 100timesteps (K=100) trajectories on CIFAR10 (LS) and CIFAR10 (CS).

To see how these bounds work in practice, in Figure 9, we plot the probability that ˆσn[2] [is clipped]
by the bounds in Theorem 2 with different number of Monte Carlo samples M on CIFAR10 (LS).
For all M, the curves of ratio v.s. n are similar and the estimate is clipped more frequently when n
is large. This is as expected because when n is large, the gap between the upper bound in Eq. (12)
and the lower bound in Eq. (11) tends to zero. The results also agree with the plot of the bounds in
Figure 7. Besides, the similarity of results between different M implies that the clipping by bounds
occurs mainly due to the error of the score-based model sn(xn), instead of the randomness in Monte
Carlo methods.

1.0 M=1

M=10

0.8 M=50

M=100

0.6 M=500

M=1000

ratio M=50000

0.4

0.2

0.0

0 200 400 600 800 1000

timestep n


Figure 9: The probability that ˆσn[2] [is clipped by the bounds in Theorem 2 with different number of]
Monte Carlo samples M on CIFAR10 (LS). The probability is estimated by the ratio of ˆσn[2] [being]
clipped in 100 independent trials. The results are evaluated with full timesteps K = N .


-----

G.4 ABLATION STUDY ON THE CLIPPING OF σ2 DESIGNED FOR SAMPLING

This section validates the argument in Appendix F.2 that properly clipping the noise scale σ2 in
_p(x1_ **_x2) leads to a better sample quality. As shown in Figure 10 and Figure 11, it greatly improves_**
_|_
the sample quality of our analytic estimate. The curves of clipping and no clipping overlap as K
increases, since σ2 is below the threshold for a large K.

Indeed, as shown in Table 7, the clipping threshold designed for sampling in Appendix F.2 is 1 to 3
orders of magnitude smaller than the combined upper bound in Theorem 2 (i.e., the minimum of the
upper bounds in Eq. (11) and Eq. (12)) when K is small.

As shown in Figure 12, clipping σ2 also slightly improves the sample quality of the handcrafted
reverse variance σn[2] [=][ β][n] [used in the original DDPM (Ho et al., 2020). As for the other two]
variances, i.e., σn[2] [= ˜]βn in the original DDPM and σn[2] [=][ λ]n[2] [= 0][ in the original DDIM (Song et al.,]
2020a), their σ2 generally don’t exceed the threshold and thereby clipping doesn’t affect the result.


75 clipping clipping 75 clipping 40 clipping

no clipping 75 no clipping no clipping no clipping

FID 50 FID 50 FID 50 FID 30

25 25 25

20

0 0

10[1] 10[2] 10[3] 10[1] 10[2] 10[3] 10[1] 10[2] 10[3] 10[2] 10[3]

# timesteps K # timesteps K # timesteps K # timesteps K


(a) CIFAR10 (LS)


(b) CIFAR10 (CS)


(c) CelebA 64x64


(d) ImageNet 64x64


Figure 10: Ablation study on clipping σ2, evaluated under Analytic-DDPM.


75 clipping 60 clipping 60 clipping 30 clipping

no clipping no clipping no clipping no clipping

50 40 40 25

FID FID FID FID

25 20 20 20

0

10[1] 10[2] 10[3] 10[1] 10[2] 10[3] 10[1] 10[2] 10[3] 10[2] 10[3]

# timesteps K # timesteps K # timesteps K # timesteps K


(a) CIFAR10 (LS)


(b) CIFAR10 (CS)


(c) CelebA 64x64


(d) ImageNet 64x64


Figure 11: Ablation study on clipping σ2, evaluated under Analytic-DDIM.


300 300

clipping 200 clipping clipping 150 clipping
no clipping no clipping no clipping no clipping

200 200

100

FID FID 100 FID FID

100 100

50

0 0 0

10[1] 10[2] 10[3] 10[1] 10[2] 10[3] 10[1] 10[2] 10[3] 10[2] 10[3]

# timesteps K # timesteps K # timesteps K # timesteps K

(a) CIFAR10 (LS)


300

clipping
no clipping

200

100

0

10[1] 10[2]

# timesteps K

(c) CelebA 64x64


(b) CIFAR10 (CS)


(d) ImageNet 64x64


Figure 12: Ablation study on clipping σ2, evaluated under DDPM with σn[2] [=][ β][n][.]


-----

Table 7: Comparing the values of (i) the threshold in Appendix F.2 used to clip σ2[2] [designed for sam-]
pling, (ii) the combined upper bound in Theorem 2 when n = 2, (iii) the lower bound in Theorem 2
when n = 2 and (iv) our analytic estimate ˆσ2[2][. We show comparison results on different datasets and]
different forward processes when K is small.

Model \ # timesteps K 10 25 50 100

CIFAR10 (LS)

Threshold (y=2) 3.87 × 10[−][4] 3.87 × 10[−][4] 3.87 × 10[−][4] 3.87 × 10[−][4]

Upper bound 1.45 10[−][1] 2.24 10[−][2] 6.20 10[−][3] 2.10 10[−][3]

DDPM _×_ _×_ _×_ _×_

Lower bound 9.99 × 10[−][5] 9.96 × 10[−][5] 9.84 × 10[−][5] 9.55 × 10[−][5]

_σˆ2[2]_ 8.70 10[−][3] 2.99 10[−][3] 1.32 10[−][3] 6.54 10[−][4]
_×_ _×_ _×_ _×_

Threshold (y=1) 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5]

Upper bound 1.37 10[−][1] 1.96 10[−][2] 4.82 10[−][3] 1.36 10[−][3]

DDIM _×_ _×_ _×_ _×_

Lower bound 0 0 0 0
_σˆ2[2]_ 8.17 10[−][3] 2.54 10[−][3] 9.66 10[−][4] 3.73 10[−][4]
_×_ _×_ _×_ _×_

CIFAR10 (CS)

Threshold (y=1) 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5]

Upper bound 3.56 10[−][2] 6.15 10[−][3] 1.85 10[−][3] 6.80 10[−][4]

DDPM _×_ _×_ _×_ _×_

Lower bound 4.12 × 10[−][5] 4.10 × 10[−][5] 4.04 × 10[−][5] 3.89 × 10[−][5]

_σˆ2[2]_ 3.90 10[−][3] 1.28 10[−][3] 5.61 10[−][4] 2.75 10[−][4]
_×_ _×_ _×_ _×_

Threshold (y=1) 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5]

Upper bound 3.33 10[−][2] 5.22 10[−][3] 1.37 10[−][3] 4.18 10[−][4]

DDIM _×_ _×_ _×_ _×_

Lower bound 0 0 0 0
_σˆ2[2]_ 3.61 10[−][3] 1.06 10[−][3] 3.95 10[−][4] 1.53 10[−][4]
_×_ _×_ _×_ _×_

CelebA 64x64


Threshold (y=2) 3.87 × 10[−][4] 3.87 × 10[−][4] 3.87 × 10[−][4] 3.87 × 10[−][4]

Upper bound 1.45 × 10[−][1] 2.24 × 10[−][2] 6.20 × 10[−][3] 2.10 × 10[−][3]

Lower bound 9.99 × 10[−][5] 9.96 × 10[−][5] 9.84 × 10[−][5] 9.55 × 10[−][5]

_σˆ2[2]_ 4.04 10[−][3] 1.54 10[−][3] 7.54 10[−][4] 4.06 10[−][4]
_×_ _×_ _×_ _×_

Threshold (y=1) 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5]

Upper bound 1.37 × 10[−][1] 1.96 × 10[−][2] 4.82 × 10[−][3] 1.36 × 10[−][3]
Lower bound 0 0 0 0
_σˆ2[2]_ 3.74 10[−][3] 1.26 10[−][3] 5.17 10[−][4] 2.11 10[−][4]
_×_ _×_ _×_ _×_


DDPM

DDIM


Model \ # timesteps K 25 50 100 200

ImageNet 64x64


Threshold (y=1) 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5]

Upper bound 5.93 × 10[−][3] 1.84 × 10[−][3] 6.44 × 10[−][4] 2.61 × 10[−][4]

Lower bound 9.85 × 10[−][6] 9.81 × 10[−][6] 9.72 × 10[−][6] 9.51 × 10[−][6]

_σˆ2[2]_ 1.40 10[−][3] 6.05 10[−][4] 2.77 10[−][4] 1.39 10[−][4]
_×_ _×_ _×_ _×_

Threshold (y=1) 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5] 9.66 × 10[−][5]

Upper bound 5.46 × 10[−][3] 1.59 × 10[−][3] 5.03 × 10[−][4] 1.77 × 10[−][4]
Lower bound 0 0 0 0
_σˆ2[2]_ 1.28 10[−][3] 5.17 10[−][4] 2.12 10[−][4] 9.11 10[−][5]
_×_ _×_ _×_ _×_


DDPM

DDIM


-----

G.5 SAMPLE QUALITY COMPARISON BETWEEN DIFFERENT TRAJECTORIES

While the optimal trajectory (OT) significantly improves the likelihood results, it doesn’t lead to
better FID results. As shown in Figure 13, the even trajectory (ET) has better FID results. Such
a behavior essentially roots in the different natures of the two metrics and has been investigated in
extensive prior works (Ho et al., 2020; Nichol & Dhariwal, 2021; Song et al., 2021; Vahdat et al.,
2021; Watson et al., 2021; Kingma et al., 2021).


75 ET ET 40 ET 80 ET

OT 40 OT OT OT

50 60

FID FID FID FID

20 20 40

25

20

0

10[1] 10[2] 10[3] 10[1] 10[2] 10[3] 10[1] 10[2] 10[3] 10[2] 10[3]

# timesteps K # timesteps K # timesteps K # timesteps K


(a) CIFAR10 (LS)


(b) CIFAR10 (CS)


(c) CelebA 64x64


(d) ImageNet 64x64


Figure 13: FID results with ET and OT, evaluated under Analytic-DDPM.

G.6 ADDITIONAL LIKELIHOOD COMPARISON


We compare our Analytic-DPM to Improved DDPM (Nichol & Dhariwal, 2021) that predicts the
reverse variance by a neural network. The comparison is based on the ImageNet 64x64 model
described in Appendix F.1. As shown in Table 8, with full timesteps, Analytic-DPM achieves a
NLL of 3.61, which is very close to 3.57 achieved by predicting the reverse variance in Improved
DDPM. Besides, we also notice that the ET reduces the log-likelihood performance of Improved
DDPM when K is small, and this is consistent with what Nichol & Dhariwal (2021) report. In
contrast, our Analytic-DPM performs well with the ET.

Table 8: Negative log-likelihood (bits/dim) ↓ under the DDPM forward process on ImageNet 64x64.
All are evaluated under the even trajectory (ET).


Model \ # timesteps K 25 50 100 200 400 1000 4000

Improved DDPM 18.91 8.46 5.27 4.24 3.86 **3.68** **3.57**
Analytic-DDPM **4.78** **4.42** **4.15** **3.95** **3.81** 3.69 3.61

G.7 CELEBA 64X64 RESULTS WITH A SLIGHTLY DIFFERENT IMPLEMENTATION OF THE
EVEN TRAJECTORY


Song et al. (2020a) use a slightly different implementation of the even trajectory on CelebA 64x64.
They choose a different stride a = int( _K[N]_ [)][, and the][ k][th timestep is determined as][ 1 +][ a][(][k][ −] [1)][. As]

shown in Table 9, under the setting of Song et al. (2020a) on CelebA 64x64, our Analytic-DPM still
improves the original DDIM consistently and improves the original DDPM in most cases.

G.8 COMPARISON TO OTHER CLASSES OF GENERATIVE MODELS


While DPMs and their variants serve as the most direct baselines to validate the effectiveness of
our method, we also compare with other classes of generative models in Table 10. Analytic-DPM
achieves competitive sample quality results among various generative models, and meanwhile significantly reduces the efficiency gap between DPMs and other models.


-----

Table 9: FID ↓ on CelebA 64x64, following the even trajectory implementation of Song et al.
(2020a). _[†]Original results in Song et al. (2020a)._ _[‡]Our reproduced results._

Model \ # timesteps K 10 20 50 100 1000

CelebA 64x64

DDPM, σn[2] [= ˜]βn[†] 33.12 26.03 18.48 13.93 5.98
DDPM, σn[2] [= ˜]βn[‡] 33.13 25.95 18.61 13.92 5.95
DDPM, σn[2] [=][ β][n][†] 299.71 183.83 71.71 45.20 **3.26**
DDPM, σn[2] [=][ β][n][‡] 299.88 185.21 71.86 45.15 **3.21**
Analytic-DDPM **25.88** **17.40** **10.98** **7.95** 5.21

DDIM, σn[2] [=][ λ]n[2] [= 0][†] 17.33 13.73 9.17 6.53 3.51
DDIM, σn[2] [=][ λ]n[2] [= 0][‡] 17.38 13.72 9.17 6.51 3.40
Analytic-DDIM **12.74** **9.50** **5.96** **4.14** **3.13**

Table 10: Comparison to other classes of generative models on CIFAR10. We show the FID results,
the number of model function evaluations (NFE) to generate a single sample and the time to generate
10 samples with a batch size of 10 on one GeForce RTX 2080 Ti.

Method FID↓ NFE ↓ Time (s) ↓

Analytic-DPM, K = 25 (ours) 5.81 25 0.73
DDPM, K = 90 (Ho et al., 2020) 6.12 90 2.64
DDIM, K = 30 (Song et al., 2020a) 5.85 30 0.88
Improved DDPM, K = 45 (Nichol & Dhariwal, 2021) 5.96 45 1.37

SNGAN (Miyato et al., 2018) 21.7 1 - 
BigGAN (cond.) (Brock et al., 2018) 14.73 1 - 
StyleGAN2 (Karras et al., 2020a) 8.32 1 - 
StyleGAN2 + ADA (Karras et al., 2020a) 2.92 1 - 

NVAE (Vahdat & Kautz, 2020) 23.5 1 - 
Glow (Kingma & Dhariwal, 2018) 48.9 1 - 
EBM (Du & Mordatch, 2019) 38.2 60 - 
VAEBM (Xiao et al., 2020) 12.2 16 - 


-----

G.9 SAMPLES

In Figure 14-17, we show Analytic-DDIM constrained on a short trajectory of K = 50 timesteps
can generate samples comparable to these under the best FID setting.

In Figure 18-21, we also show samples of both Analytic-DDPM and Analytic-DDIM constrained
on trajectories of different number of timesteps K.

(a) Best FID samples (b) Analytic-DDIM, K = 50

Figure 14: Generated samples on CIFAR10 (LS).

(a) Best FID samples (b) Analytic-DDIM, K = 50

Figure 15: Generated samples on CIFAR10 (CS).


-----

(a) Best FID samples (b) Analytic-DDIM, K = 50

Figure 16: Generated samples on CelebA 64x64.

(a) Best FID samples (b) Analytic-DDIM, K = 50

Figure 17: Generated samples on ImageNet 64x64.


-----

(a) Analytic-DDPM, K = 10 (b) Analytic-DDPM, K = 100 (c) Analytic-DDPM, K = 1000

(d) Analytic-DDIM, K = 10 (e) Analytic-DDIM, K = 100 (f) Analytic-DDIM, K = 1000

Figure 18: Generated samples on CIFAR10 (LS).

(a) Analytic-DDPM, K = 10 (b) Analytic-DDPM, K = 100 (c) Analytic-DDPM, K = 1000

(d) Analytic-DDIM, K = 10 (e) Analytic-DDIM, K = 100 (f) Analytic-DDIM, K = 1000

Figure 19: Generated samples on CIFAR10 (CS).


-----

(a) Analytic-DDPM, K = 10 (b) Analytic-DDPM, K = 100 (c) Analytic-DDPM, K = 1000

(d) Analytic-DDIM, K = 10 (e) Analytic-DDIM, K = 100 (f) Analytic-DDIM, K = 1000

Figure 20: Generated samples on CelebA 64x64.

(a) Analytic-DDPM, K = 25 (b) Analytic-DDPM, K = 200 (c) Analytic-DDPM, K = 4000

(d) Analytic-DDIM, K = 25 (e) Analytic-DDIM, K = 200 (f) Analytic-DDIM, K = 4000

Figure 21: Generated samples on ImageNet 64x64.


-----

H ADDITIONAL DISCUSSION

H.1 THE EXTRA COST OF THE MONTE CARLO ESTIMATE

The extra cost of the Monte Carlo estimate Γ is small compared to the whole inference cost. In fact,
the Monte Carlo estimate requires MN additional model function evaluations. During inference,
suppose we generate M1 samples or calculate the log-likelihood of M1 samples with K timesteps.
Both DPMs and Analytic-DPMs need M1K model function evaluations. Employing the same scorebased models, the relative additional cost of Analytic-DPM is _MMN1K_ [. As shown in Appendix G.2,]

a very small M (e.g., M = 10, 100) is sufficient for Analytic-DPM, making the relative additional
cost small if not negligible. For instance, on CIFAR10, let M = 10, N = 1000, M1 = 50000 and
_K_ 10, we obtain _MMN1K_

presented in Table 6. ≥ _[≤]_ [0][.][02][ and Analytic-DPM still consistently improves the baselines as]

Further, the additional calculation of the Monte Carlo estimate occurs only once given a pretrained
model and training dataset, since we can save the results of Γ = (Γ1, _, ΓN_ ) in Eq.(8) and reuse
_· · ·_
it among different inference settings (e.g., trajectories of various K). The reuse is valid, because the
marginal distribution of a shorter forward process q(x0, xτ1 _, · · ·, xτK_ ) at timestep τk is the same as
that of the full-timesteps forward process q(x0:N ) at timestep n = τk. Indeed, in our experiments
(e.g., Table 1,2), Γ is shared across different selections of K, trajectories and forward processes.
Moreover, in practice, Γ can be calculated offline and deployed together with the pretrained model
and the online inference cost of Analytic-DPM is exactly the same as DPM.

H.2 THE STOCHASTICITY OF THE VARIATIONAL BOUND AFTER PLUGGING THE ANALYTIC
ESTIMATE

In this part, we write Lvb as Lvb(σn[2] [)][ to emphasize its dependence on the reverse variance][ σ]n[2] [.]

When calculating the variational bound Lvb(σn[2] [)][ (i.e., the negative ELBO) of Analytic-DPM, we]
will plug ˆσn[2] [into the variational bound and get][ L][vb][(ˆ]σn[2] [)][. Since][ ˆ]σn[2] [is calculated by the Monte Carlo]
method, Lvb(ˆσn[2] [)][ is a stochastic variable. A natural question is that whether][ L][vb][(ˆ]σn[2] [)][ is a stochastic]
bound of Lvb(E[ˆσn[2] [])][, which can be judged by the Jensen’s inequality if][ L][vb] [is convex or concave.]
However, this is generally not guaranteed, as stated in Proposition 2.
**Proposition 2. Lvb(σn[2]** [)][ is neither convex nor concave w.r.t.][ σ]n[2] _[.]_

_Proof. Since σn[2]_ [only influences the][ n][-th term][ L][n] [in the variational bound][ L][vb][, where]


EqDKL(q(xn 1 **_xn, x0)_** _p(xn_ 1 **_xn))_** 2 _n_ _N_
_Ln =_ _−_ _|_ _||_ _−_ _|_ _≤_ _≤_
 _−Eq log p(x0|x1)_ _n = 1_

we only need to study the convexity of Ln w.r.t. σn[2] [.]


When 2 ≤ _n ≤_ _N_,

_Ln =_ _[d]_


_λ2n_ 1 + log _[σ]n[2]_ + [1] Eq _||µ˜(xn, x0) −_ **_µn(xn)||[2]_**

_σn[2]_ _−_ _λ[2]n_ _σn[2]_ _d_




Let A = λ[2]n [+][ E][q] _|| ˜µ(xn,x0)d−µn(xn)||[2]_, then Ln as a function of σn[2] [is convex when][ 0][ < σ]n[2] _[<][ 2][A]_

and concave when 2A < σn[2] [. Thereby,][ L][vb][(][σ]n[2] [)][ is neither convex nor concave w.r.t.][ σ]n[2] [.]

Nevertheless, in this paper, Lvb(ˆσn[2] [)][ is a stochastic upper bound of][ L][vb][(][σ]n[∗][2][)][ because][ L][vb][(][σ]n[∗][2][)][ is]
the optimal. The bias of Lvb(ˆσn[2] [)][ w.r.t.][ L][vb][(][σ]n[∗][2][)][ is due to the Monte Carlo method as well as]
the error of the score-based model. The former can be reduced by increasing the number of Monte
Carlo samples. The latter is irreducible if the pretrained model is fixed, which motivates us to clip
the estimate, as discussed in Section 3.1.

H.3 COMPARISON TO OTHER GAUSSIAN MODELS AND THEIR RESULTS

The reverse process of DPMs is a Markov process with Gaussian transitions. Thereby, it is interesting to compare it with other Gaussian models, e.g., the expectation propagation (EP) with the
Gaussian process (GP) (Kim & Ghahramani, 2006).


-----

Both EP and Analytic-DPM use moment matching as a key step to find analytic solutions of
_DKL(ptarget_ _popt) terms. However, to our knowledge, the relation between moment matching_
_||_
and DPMs has not been revealed in prior literature. Further, compared to EP, we emphasize that it
is highly nontrivial to calculate the second moment of ptarget in DPMs because ptarget involves an
unknown and potentially complicated data distribution.

In EP with GP (Kim & Ghahramani, 2006), ptarget is the product of a single likelihood factor and all
other approximate factors for tractability. In fact, the form of the likelihood factor is chosen such that
the first two moments of ptarget can be easily computed or approximated. For instance, the original
EP (Minka, 2001) considers Gaussian mixture likelihood (or Bernoulli likelihood for classification)
and the moments can be directed obtained by the properties of Gaussian (or integration by parts).
Besides, at the cost of the tractability, there is no converge guarantee of EP in general.

In contrast, ptarget in this paper is the conditional distribution q(xn 1 **_xn) of the corresponding_**
_−_ _|_
joint distribution q(x0:N ) defined by the forward process. Note that the moments of q(xn−1|xn) are
nontrivial to calculate because it involves an unknown and potentially complicated data distribution.
Technically, in Lemma 13, we carefully use the law of total variance conditioned on x0 and convert
the second moment of q(xn−1|xn) to that of q(x0|xn), which surprisingly can be expressed as the
score function as proven in Lemma 11.

H.4 FUTURE WORKS

In our work, we mainly focus on image data. It would be interesting to apply Analytic-DPM to other
data modalities, e.g. speech data (Chen et al., 2020). As presented in Appendix E, our method can be
applied to continuous DPMs, e.g., variational diffusion models (Kingma et al., 2021) that learn the
forward noise schedule. It is appealing to see how Analytic-DPM works on these continuous DPMs.
Finally, it is also interesting to incorporate the optimal reverse variance in the training process of
DPMs.


-----