Analytic-DPM: an Analytic Estimate of the Optimal Reverse Variance in Diffusion Probabilistic Models
Authors: Fan Bao
Chongxuan Li
Jun Zhu
Bo Zhang
Venue: ICLR 2022 Oral (2022)
Keywords: diffusion probabilistic models
generative models

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 \textit{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\times$ to $80\times$ speed up.

Published as a conference paper at ICLR 2022
ANALYTIC-DPM: AN ANALYTIC ESTIMATE OF THE OPTIMAL REVERSE VARIANCE IN DIFFUSION PROB- ABILISTIC MODELS
Fan Bao' Chongxuan Li 31, Jun Zhu 1, Bo Zhang'
Dept. of Comp. Sei. & Tech., Institute for AI, Tsinghua-Huawei Joint Center for Al BNRist Center, State Key Lab for Intell. Tech. & Sys., Tsinghua University, Beijing, China 2Gooling School of Artificial Intelligence, Renmin University of China, Beijing, China Beijing Key Laboratory of Big Data Management and Analysis Methods Beijing, China bf1 1a192maass.... tssinghua.... edu. en, chong i 199919999000 gmail. com, {doszj, dcszb) stinggua 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 gener- ally needs to iterate over thousands of timesteps. A key problem in the inference is 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 cor- responding optimal KL divergence 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, correct the potential bias caused by the score-basee 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, pro- duces high-quality samples, and meanwhile enjoys a x to 80x speed up.
DPM have analytic forms w.r.t. its score
INTRODUCTION
A diffusion process gradually adds noise to a data distribution over a series of timesteps. By learning reverse it. diffusion probabilistic models (DPMs) (Sohl-Dickstent et al. 2015 Ho et al. 2020 Song et al. 2020b) define data generative process. Recently, it is shown that DPMs are able to produce hugh-quality samples (Ho et al.) 2020: Nichol Dhariwal, 2021: Song et al. 20206)
Dhariwal & Nichol, 2021). which are comparable or even superior to the current state-of-the tte--at
GAN models (Goodfellow et al. 2014 Brock et al. 2018 Wu 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 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 long chain obtain reasonable sample and density value (Nichol & Dhariwal 2021). NNcchol & Dhariwal (2021) attempt to improve the efficiency of sampling by learning variance network in the reverse process. However, still needs a relatively long trajectory to get a reasonable log-likelihood (see Appendix E in Nichol & Dhariwal 2202))
In this work, we present surprising result that both the optimal reverse variance and the corre- sponding optimal KL divergence of a DPM have analytic forms w.r.t. its score function (i.c., the gradient of log density). Building upon it, we propose Analytic-DPM, framework to improve the efficiency of a pretrained DPM while achieving comparable or even su- perior performance. Analytic- DDM 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 correspond- ing trajectory calculated via a dynamic programming algorithm (Watson et al., 2021). Further, to
training-free inference
Work done during an internship Huawei Noah's Ark Lab. CCorespondence to: C. Li and J. Zhu.

---

Published as a conference paper at ICLR 2022
correct the potential bias caused by the score- score-based model, 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 DPMs (Ho et al. 2020 Song et al. 2020a Nichol & Dhariwal 2021) in plug-and-play manner. Empirically, Analytic-PPM consistently improves the log-likelihood of these DPMs and meanwhile enjoys a 20 to 40x speed up. Besides, Analytic- (020a) and requires up to 50 timesteps (which 20x to 80x speed up compared to the full timesteps) to achieve a comparable FID the corresponding baseline.
DPM also consistently improves the sample quality of DDIMs (Song
BACKGROUND
Diffusion probabilistic models (DPMs) firstly construct forward process q (( (20)) that injects noise data distribution (20)). and then reverse the forward process to recover Given a forward noise schedule 3n E (0, 1), n 1.... N, denoising diffusion probabilistic models (DDPMs) (Ho
al. 2020) consider a Markov forward process:
N
9M (Z (p)
II (2nl Ihe (x
= N (,, B..1)
where / is the identity matrix, On and 3n are scalars and ax == 1- Bn. Song et al. (2020a) introduce a more general non-Markov process indexed by non-negative vector d (A1, ... .x) E R
(x(11 (20) (x (o0)
II ga ga 12 2o);
(2)
(x(xN NN(N Va II
yx ( [n, x0) = (2 jin (mas σo), X
Un v v
Pn (In, 20) = v an + +VBB
BB-1-
X3
B
Here OG,, = IT a₂ and B, 1 Cnn Indeed, Eq. 2 includes the DDPM forward process as special case when 2 = Ba. where B.. == 9--1 Bn. Another special case of Eq. 2 is the denoising diffusion implicit model (DDIM) forward process, where X₂ 0. Besides, we can further derive vx(x, = VV( 3,, 3,, which is independent of A. In the rest of the paper, we will focus on the forward process in Eq. (2) since it is more general, and will omit the index À and denote it as q( æb) for simplicity.
3,
The reverse process for Eq. (2) defined as a Markov process aimed approximate g(x)) by gradually denoising from the standard Gaussian distribution p(æN) = Nxxx 0)
N
p( = p(æN) ))
II
p(æ p(zn-1/ p(zn-112,, = - I
where M4n (xx)) is generally parameterized by time-dependent score-based model 8,, (xx) & Ermon 2019 Song et al. 2020b)):
Song
1 (In "onn+B,,0000 +Bn
1 (xx) jh,, Cn: Van
The reverse process can be learned by optimizing a variational bound Lvb on negative log-liielihood:
N
Lub = E,
log pl (20 x1
+
Σ
Dit. (hka.g(@n-111 1 &n lpppppppp.n (xx)) )) DKI. (a(æ ( (2))
n=2
Ho et al. 2020y: Song 2020a
parameterize pen (wn) with jin (wn, - (xn -- en which
equivalent to Eq.
by letting 8,, (x.)
v 3 (x..).
2

---

Published as a conference paper at ICLR 2022
which is equivalent to optimizing the KL divergence between the forward and the reverse process:
min (Mn.a 1.8
Tec + min (u H mmm
DKL (
(4)
To improve the sample quality in practice, instead of directly optimizing Lyb- Ho et al. (2020)
consider reweighted variant of Lvb to learn 8, (x,):
min E, (2,,, lll (x,,) - Van (n = En, + (z + ( 10mhm
(5)
where is uniform between and N, In (T.,) is the marginal distribution of the forward process timestep n, is standard Gaussian noise, In on the hight-hand side is reparameterized by
nn v Co + P,, and cs constant only related to q. Indeed, Eq. (5 is exactly a weighted sum of score matching objectives (Song & Ermon 2019) which admits optimal solution s, (æ,) Va. log 9n (z,) for all n E {1,2...
Note that Eq. (5) provides learning signal for the variance of Indeed, o is generally handcrafted in most of prior works. DDPMs (Ho et al. 2020), two commonly used settings are o = 3, and
o = 3n. In DDIMs, Song et al. (2200a) consistently use o = X We argue that these handcrafted values not the true optimal solution of Eq. (4) in general, leading suboptimal performance.
ANALYTIC ESTIMATE OF THE OPTIMAL REVERSE VARIANCE
For DPM, we first show that both the optimal mean μ (#r) and the optimal variance x Eq. have analytic forms w.r.t. the score function, which is summarized in the following Theorem
Theorem 1. (Score representation of the optimal solution to Eq. 4 proof in Appendix A.2
The optimal solution F2, (xr.) and a,2² Eq. are
1 _(xn (In + B Va,, log on (2xn))
Mr (20)) ) = iin
En Van
(6)
2
(Var - ---BBnn
| ar log (n
0²2 X2 +
X3
where Qn (Dn) is the marginal distribution of the forward process at the timestep and d is the dimension of the data.
The proof Theorem consists of three key steps:
The first step (see Lemma 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 the same. To 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 #o and convert the second moment of ((#n-1((.)) to that of xx
In the third step (see Lemmal 11 we surprisingly find that the second moment of ( (z,, can be represented by the score function, and we plug the score representation into the second moment of g( xx,) to get the final results in Theorem
The results in Theorem I (and other results to appear later) can be further simplified for the DDPM forward process (i.c., X = B,,, see Appendix D for details). Besides, we can also extend Theo- rem [ 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. for the extension).
Note that our analytic form of the optimal mean 14,, (x.) in Eq. (6 and the previous parameterization of f,((,,,) (Ho et al.) 2020) in Eq. coincide. The only difference is that Eq. 33 replaces the

---

Published as a conference paper at ICLR 2022
0.4
8.
4.
2-7
2-12
Lus term (bits/dimm)
0.3
variance
2-
23
0.2
2-11
2-11
8,
2
2
2
2
2
2
timestep
timestep n
(a) Variance
(b) Terms in Lyb
Figure 1: Comparing our analytic estimate a and prior works with handerafted variances 3n and 3n. (a) compares the values of the variance for different timesteps.
(b) compares the term in Lub corresponding to each timestep. The value of Lvb is the area under the corresponding curve.
score function V 20. 9n (Z.) in Eq. (6) with the score-based model s,, (Z,)) This result explicitly shows that Eq. (5) essentially shares the same optimal mean solution the Lvb objective, providing a simple and alternative perspective to prior works.
In contrast to the handcrafted strategies used in (Ho al. 2020 Song et al. 2020a), Theorem shows that the optimal reverse variance o% can also be estimated without any extra training process given a pretrained
based model s, (x,,)), fact, we first estimate the expected mean squared norm of V log (Ix,) by I (T,,..,, NN), where
| (Zn,mm)
F
nn.m
did
Qn (zx
M is the number of Monte Carlo samples. We only need calculate I once for pretrained model and reuse in downstream computations (see Appendix[H.]]foo detailed discussion of the computation cost of I'). Then, according Eq. ( we estimate o, as follows:
(1B=
Ba On
02 = X
+
(
V B B--1
X2
(1-B.rm).
We empirically validate Theorem In Figure (a). plot our analytic estimate 6% of DDPM trained on CIFAR10, as well as the baselines 8n, and 3n used by et al. (2020). small timesteps, these strategies behave differently. Figure (b) shows that our o;;- outperforms the baselines for each term of Tubb especially the small timesteps. We also obtain similar results on other datasets (see Appendix G.I. Besides, we show that only 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 similar performance to that with large M (see Appendix G.2 We also discuss the stochasticity of Lub after plugging &, in Appendix H.2
3.1 BOUNDING THE OPTIMAL REVERSE VARIANCE TO REDUCE BIAS
According to Eq. 77 and Eq.
9 the bias of the analytic estimate & is
2
BB -
(
B an
| 2n log (In))l
10 021
V
V
X2
B IT En (m..))
(10)
d
Approximation error
Cueflicient
Our estimate of the variance employs a score-based model s, [ ) to approximate the true score function Va. log qn (x,). Thus, the approximation error in Eq. (10) is irreducible given pretrained model. Meanwhile, the coefficient in Eq. (IO) can be large we use a shorter trajectory to sample (see details in Section potentially resulting in large bias.
4

---

Published as a conference paper at ICLR 2022
To reduce the bias, we derive bounds of the optimal reverse variance o₂² and clip our estimate based on the bounds. Importantly, these bounds are unrelated to the data distribution g and hence can be efficiently calculated. We firstly derive both upper and lower bounds of on without any assumption about the data. Then we show another upper bound of o% if the data distribution is bounded. We formalize these bounds in Theorem
Theorem 2. (Bounds of the optimal reverse variance, proof in Appendix A.3
x2 has the following lower and upper bounds:
(V B - X
2 S on S A
(1I)
we fürther assume ((20)) is a bounded distribution [a, bj², then o can be further upper bounded by
where d is the dimension of data,
002 S 2 + (Va--1
10n-1-BBa.. Bn-1
X2
T n.
b
(12)
2
Theorem states that the handcrafted reverse variance X2; in prior works (Ho et al. 2020 Song et al. 2020a) underestimates o; For instance, XØ 3, in DDPM. We compare it with our estimate in Figure (a) and results agree with Theorem 2 Besides, the boundedness assumption of g( satished in many scenarios including generative modelling of images, and which upper bound among Eq. (II) 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
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 qf x ... Fg [D)) constrained on trajectory 1 T < .... <
TK N of K timesteps (Song et al. 2020a Nichol & Dhariwal 2202 Watson et al. 202 b,, and K can be much smaller than N to speed up the inference. Formally, y, the shorter process is defined as ((Z '.. FTx (mo) = {(xTr (20) II ((ET,) [ 2n), where
( Rr,, xo) = NN 1 (Wrr 2o), 22-11
(13)
Tr Vorri 20
P (Dry, mo) varu- + Bru_, X2 1/
BBn
TTx) = p((Tx) I p(a (xTz): where The corresponding reverse process is p(0o, Trys" p( (r,,)) = N M va (Drr ), o²
-e- I).
According to Theorem minimization
I the mean and variance of the optimal p² (IT (Krr)) in the sense of KL
PT (I+z) -uru-117 1170 ITzi Vān
(In
Brg Vær, log (ogg(zTe))
2
B T
Votr xry
log (2x 12
72-111 = =x2 =122-1177 +
12-1 (1- 11-B., By((nng)
X2
aTulTe-1
where OrylTe = ar./ a According to Theorem we can derive similar bounds for x²
1/76
(see details in Appendix Ch. Similarly Eq. (9 the estimate of x² is
Tk 1/T4
2
(v
B v Brg. -22
02 Tk-1/7 -7-_1117
-2
(1 (1-3,1 TT.))
7k-1/74
5

---

Published as a conference paper at ICLR 2022
where I' is defined in Eq. (8) and can be shared across different selections of trajectories. Based on the optimal reverse process pa above, we further optimize the trajectory:
K
min (g " :. Frx Hllp (xo, Zr mTx)) = Σ 7x)+ +c, (14) k=
Tar TK
2
and c is constant unrelated to the trajectory T (see proof in Appendix A.4.. The KL in Eq. (4) 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 (Tk-1, Tk), and it can be efficiently estimated by J(T--1, Tk) z log(ö?, Tv / 1 nn)) which doesn't 't require any neural network computation once I' is given. While the logarithmic function causes bias even when the correct score function is known, it can be reduced by increasing M.
where (( = log(o"2 - /12
As a result, Eq. (14p reduced to canonical least-cost-path problem (Watson et al. 2021) on directed graph, where the nodes are (1,2,... ,N and the edge from & to F has cost J [s, t). We want to find least-cost path of К nodes starting from 1 and terminating at N. This problem can be solved by the dynamic programming (DP) algorithm introduced by Watson et al. [022I.
We present this algorithm Appendix B Besides, we can also extend Eq. (14) to DPMs with continuous timesteps (Song et al.) 2020b; Kingma et al. 202TD, 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 E.y,,.)) Cov (r.. [xo] and Cov, Bofaaal ) [zzo]. where the first term can be represented by the score function. Further, the second term is negligible when n is sufficiently large because Do and Sn 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
6 EXPERIMENTS
We consider the DDPM forward process (A = =B,) and the DDIM forward process (A2, = 0). which are the two most commonly used special cases of Eq. ( We denote method, which uses the analytic estimate o 6%, as Analytic-PPM, and explicitly call it Analytic- -DDM or Analyti-DDDM according which forward process is used. We compare
Analytie-DPM with
the original DDPM (Ho et al. 2020). where the reverse variance is either of = 3n or 0 Sn, as well as the original DDIM (Song et al. 2020a), where the reverse variance is o X 0.
We adopt two methods get the trajectory for both the analytic-DPM and baselines. The first one is even trajectory (ET) (Nichol & Dhariwal (002). where the timesteps are determined according to a fixed stride (see details in Appendix F.4). F.44). The second one is optimal trajectory (OT) (Watson 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 al. 2021
We apply our Analytic-DPM. to three pretrained score-based models provided by prior works (Ho al. 2020 Song et al. [020aa] Nichol & Dhariwal [22T]) as well as two boore-baed models trained by ourselves. The pretrained
based models Is are trained on CelebA 64x64 (Liu et al.) 2015), ImageNet 64x64 (Deng et al., 2009) and LSUN Bedroom YYu 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 CIFAR 10 (LS) and CIFARIO (CS) respectively. The number of the full timesteps N is 4000 for ImageNet 64x64 and 1000 for other datasets. During sampling, only display the mean of p( xx1) and discard the noise following Ho et al. (2020), and additionally clip the noise scale a2 of p(z) (x2) for all methods compared in Table (see details in Appendix and its ablation study in Appendix G.4 See more experimental details Appendix F.

---

Published as a conference paper at ICLR 2022
Negative log-lik ligeliicl (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 analytic- DPM can outperform the baselines with full timesteps and underline the corresponding results.
Table 1:
Model timesteps K
10
25
50
100
200
400
1000
CIFARIO (LS)
DDPM, o² An
74.95
24.98
12.01
7.08
5.03
4.29
3.73
-
ET
DDPM, in 3n
6.99
6.11
5.44
4.86
4.39
4.07
3.75
Analyti-DDDPA
5.47
4.79
4.38
4.07
3.84
3.71
3.59
DDPM, of 3n Analytic-DDPM
5,38
4.34
3.97
3.82
3.77
3.75
3.75
OT
4.11
3.68
3.61
3.59
3.59
3.59
3.59
CIFARIO (CS)
DDPM, a² 3n
75.96
24.94
11.96
7.04
4.95
4.19
3.60
ET
DDPM, oh 3
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
DDPM, a² = 3n Analytic-DDPM
5.51
4.30
3.86
3.65
3.57
3.54
3.54
OT
3,99
3.56
3.47
3.44
3.43
3.42
3.42
CelebA 64x64
DDPM, of Bn DDPM. o² 3n
33.42
13.09
7.14
4.60
3.45
3.03
2.71
ET
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
DDPM, a² 3n Analytic-DDPM
4.76
3.58
3.16
2.99
2.94
2.93
2.93
OT
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, o² Br
105.87
46.25
22.02
12.10
7.59
5.04
3.89
DDPM, - B,
ET
5.81
5.20
4.70
4.31
4.04
3.81
3.65
Analytic-DDie DDDM
4.78
4.42
4.15
3.95
3.81
3.69
3.61
DDPM, of Bn Analytic-DDPM 3.83
4.56
4.09
3.84
3.73
3.68
3,65
3.65
OT
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 pretrained DPM while achieving comparable mance. Specifically, Section 6.1 and Section 6.2 present the likelihood and sample quality results respectively, Additional experiments such ablation studies can be found in Appendix
superior perfor-
6.1 LIKELIHOOD RESULTS
Since X 0 in the DDIM forward process, its variational bound Lvb is infinite. Thereby, only consider the likelihood results under the DDPM forward process, As shown in Table on all three datasets, using both ET and OT. Remarkably, using much shorter trajectory (i.e.. much less inference time), Analytic-DPM with OT can still outperform the baselines. In Table [ we select the mini- mum K such that analytic-DPM can outperform the baselines with full timesteps and underline the corresponding results. Specifically, analytic- DDM enjoys 40x speed up on CIFAR1O (L.S) and ImageNet 64x64, and 20x speed up CIFARIO (CS) and CelebA 64x64.
Analytic-DPM consistently improves the likelihood results of the original DDPM
Although we mainly focus on learning strategies of choosing the reverse variance, we also compare another strong baseline that predicts the variance by neural network (Nichol & Dhari- wal 2021). With full timesteps, Analytic- Analytic-DPM achieves a NLL of 3.61 on ImageNet 64x64, which very close 3.57 reported in Nichol & Dhariwal (2021). Besides, while Nichol & Dhariwal (202 report that the ET drastically reduces the likeliood performance of their neural-network: parameterized variance, Analytic-DPM performs well with the ET. See details in Appendix G.6

---

Published as a conference paper at ICLR 2022
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. (202)), because we use an improved model architecture following Nichol & Dhariwal (221).
Model timesteps K
10
25
50
100
200
400
1000
CIFARIO (LS)
DDPM, 0 An
44.45
21.83
15.21
10.94
8.23
6.43
5.11
DDPM, o² 3n
233.41
125.05
66.28
31.36
12.96
4.86
13.04
Analytic-DDPH
34.26
11.60
7.25
5,40
4.01
3.62
4.03
DDIM Analytie-DDDI
21.31
10.70
7.74
6.08
5.07
4.61
4.13
14.00
5.81
4.04
3.55
3.39
3.50
3.74
CIFARIO (CS)
DDPM, of 8n
34.76
16.18
11.11
8.38
6.66
5.65
4.92
DDPM, 0f = 3n
205.31
84.71
37.35
14.81
5.74
3.40
3.34
Analytie-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 MMMI DDIM
26.43
9.96
6.02
4.88
4.92
5.00
4.66
CelebA 64x64
DDPM, of 8n
36.69
24.46
18.96
14.31
10.48
8.09
5.95
DDPM, o, = In
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-
ADMM 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, o² = An
29.21
21.71
19.12
17.81
17.48
16.84
16.55
DDPM, of = Bn
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 sample quality, we consider the commonly used score (Heusel et al. 2017), where lower value indicates a better sample quality. As shown in Table 2 under trajectories of different K, our Amalytic-DDIM consistently improves the sample quality of the original DDIM. This allows us generate high-quality samples with less than 50 timesteps, which results in 20x 80x speed up compared to the full timesteps. Indeed, in most cases, Analytic-DDIM only requires up to 50 timesteps get similar performance the baselines. Besides, Mmalytic-DDPP also improves the sample quality of the original DDPM in most cases, For fairness, we use the ET implementation in Nichol Dhariwal (20TT) for all results in Table 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 Appendix G.9
We observe that Analytic-DDDD DDPM does not always outperform the baseline under the FID metric, which is inconsistent with the likelihood results in Table T Such behavior essentially roots in the different natures of the two metrics and has been investigated in extensive prior works (Theis et al., Ho et al. 2020 Nichol Dhariwal 2021 Song et al.) 202 Vahdat al. 2021 Watson al, 2021). Similarly, using more timesteps doesn I necessarily yield better FID.
2015
202
Kingma et al.
For instance, see the Analytic-DDDD DDMM results on CIFARIO (LS) and the DDIM results on ImageNet
64x64 in Table 2 A similar phenomenon is observed in Figure 8 in Nichol & Dhariwal (22II)
Moreover, a DPM (including Analytic-DPM) with OT does not necessarily lead to a better FID
score (Wassnn al. 2021) (see Appendix G.5 for comparison of ET and OT in Analytic-DPM).
8

---

Published as a conference paper at ICLR 2022
Table 3: Efficiency comparison, based on the least number of timesteps & required achieve FID around 6 (with the corresponding FID). To get the strongest baseline, the results with i are achieved by using the quadratic trajectory [Song al. (2020a) instead of the default even trajectory.
Method
CIFAR1O
CelebA 64x64
LSUUN Bedroom
DDPM (Ho et al. 2020)
t90 (6.12)
> 200
130 (6.06)
DDIM (Song et al. 2020a)
130 (5.85)
> 100
Best FID > 6
Improved DDPM (Nichol& & Dhariwal 2021
45 (5.96)
Missing model 55 (5.98)
90 (6.02)
Analytic-DPM (ours)
25 (5.81)
100 (6.05)
We summarize the efficiency of different methods in Table 3 where we consider the least number of timesteps required 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 L-b- Ho al. (2020) propose the new parameterization of DPMs in Eq. (3) and learn DPMs with the reweighted variant of Lub in Eq. ( 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., 202T Lam al. (202T), controllable generation (Choi et al. [021] [Sinaa et al. (021). image super-resolution (Saharia et al.] 2021] Li
jet 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 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 term of the optimal KL. divergence. In addition to these trajectory searching techniques, Luhmann & Luhman (202T) compress the reverse denoising process into a single step model; [San-Roman al. (2021) dynamically adjust the trajectory dur- ing inference. Both of them need extra training after getting a pretrained DPM. As for DPMs with continuous timesteps (Song et al.) 2020b), Song 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 Baticoeur-Martineuu number of runs for accurate computation. [Jolicouur Martineau et al. (202T) introduce an advanced SDE solver to simulate the reverse process in a more efficient way. However, the log- likelihhood computation based on this solver is not specified.
Variance Learning in DPMs. addition to the reverse variance, there are also works on learning the forward noise schedule (i.e., the forward variance). Kingma al. (2021) propose variational diffusion models (VDMs) on continuous timesteps, which use a signal-to to-iose ratio function to parameterize the forward variance and directly optimize the variational bound objective for 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
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, 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 relationship between the score function and the data covariance matrix. Empirically, our analytic-DPP -DMM improves both the efficiency and performance of likelihood results, and generates high-quality samples efficiently in various DPMs.

---

Published as a conference paper at ICLR 2022
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. 10T7YJJH0101110002200
Beijing Academy of Artificial Intelligence (BAAI, Tsinghua- Huawei Joint Research Program, a grant from Tsinghua Institute for Guo Qiang, and the NVIDIA NVAIL Program with GPU/DGX Acceleration, Major Innovation & Planning Interdisciplinary Plat- form for the "Double-Fine Class" Initiative, Renmin University of China.
ETHICS STATEMENT
This work proposes analytic estimate of the optimal variance in the reverse process of diffusion probabilistic models. As fundamental research in machine learning, the negative consequences are not obvious. Though in theory any technique can be misused, it is not likely happen at the current stage.
REPRODUCIBILITY STATEMENT
We provide codes and links pretrained models in Analytic-DEE We provide details of these pretrained models in Appendix[F.] We provide de- tails of data processing, li-likiiihodd evaluation, sampling and FID computation in Appendix F2 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: 1096, 2018.
Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov. Importance weighted autoencoders. arXiv preprint 1eXXvv1509.00511 2015.
Nanxin Chen, Yu Zhang, Heiga Zen, Ron Weiss, Mohammad Norouzi, and William Chan. Wave- grad: Estimating gradients for waveform generation. arXiv preprint 2rXiv:2009.007133 2020.
Jooyoung Choi, Sungwon Kim, Yonghyun Jeong. Youngjune Gwon, and Sungroh Yoon. Ilvr: Con- ditioning method for denoising diffusion probabilistic models. arXiv preprint 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- crarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-24422 255. leee, 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 2XXv:/903.00669 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 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. / /239, 2020.
10

---

Published as a conference paper at ICLR 2022
Alexia Volicoeur-Martinear Ke Li, Rémi Piché-Taillefer. Tal Kachman, and Ioannis Mitliagkas. Gotta go fast when generating data with score-based models. arXiv preprint arXiv:2105. 2021.
Tero Karras, Miika Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Training generative adversarial networks with limited data, arXiv preprini arXiv:2006.0666 2020a.
Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. Analyz- ing and improving the image quality stylegan. In Proceedings of the IEEE/CVV Conference on Computer Vision and Pattern Recognition, pp. 8110-8119, 2020b.
Hyun-Char Chnn-CCllll Kim and Zoubin Ghahramani. Bayesian gaussian process classification with the em-ep algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(12); (222::998-99999 2006.
Diederik P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. arXiv preprint arXiv: 1807.0003. 2018.
Diederik P Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. arXiv preprint arXiv:2107.00633 2021.
Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. arXiv preprint (xXxx:2009.09661, 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. 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.1499 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, (CCV2015, Santiago, Chile, December 7-13, 2015, pp. 3730-3738. IEEE Computer Society, 2015.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 1rXiv:1711.01101, 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 denois- ing diffusion models for multivariate probabilistic time series forecasting. arXiv preprint arXiv:2 12072, 2021.
11

---

Published as a conference paper at ICLR 2022
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and ap- proximate 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.070. 2021.
Robin Ram-Roman, Eliya Nachmani, and Lior Wolf. Noise estimation for generative diffusion mod- els. 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- -ennosinn models for few-shot conditional generation. arXiv preprint arXiv:2106.068// 2021.
Jascha Sohl-Dickse Dill-Dicstten, 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: (907.05000000000 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, lain Murray, and Stefano Ermon. Maximum likelihood training of score- based diffusion models. arXiv e-prints, pp. arXiv-2101, 2021.
Lucas Theis, Aäron van den Oord, and Matthias Bethge. A note on the evaluation of generative models. arXiv preprint arXiv:1511.0180 2015.
Arash Vahdat and Jan Kautz. Nvae: A deep hierarchical variational autoencoder. arXiv preprint arXiv:2007.03899, 2020.
Arash Vahdat, Karsten Kreis, and Jan Kautz. Score-based generative modeling in latent space. arXiv preprint arXiv:2106.054) 2021.
Daniel Watson, Jonathan Ho, Mohammad Norouzi, and William Chan. Learning to efficiently sam- ple from diffusion probabilistic models. arXiv preprint arX1v: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.0095. 2019.
Zhisheng Xiao, Karsten Kreis, Jan Kautz, and Arash Vahdat. Vaebm: A symbiosis between varia- tional 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 large-scale image dataset using deep learning with humans in the loop. arXiv preprint 10Xiv:1566.083 03366. 2015.
Linqi Zhou, Yilun Du, and Jiajun Wu. 3d shape generation and completion through point-voxel diffusion. arXiv preprint urXiv:2104.088 2021.
12

---

Published as a conference paper at ICLR 2022
A PROOFS AND DERIVATIONS
A.1 LEMMAS
Lemma 1. (Cross-entropy Gaussian) Suppose q(ær) is probability density function with mean My and covariance matrix Eg and p(æ) = -N jr, Σ) is Gaussian distribution, then the cross- entropy between q and p is equal to the cross-entropy between N (2x 2g) and p. i.e.,
H(g. = H(N(aa Eq),p)
1
1og((22) + ir 1r(E,1 + (1g 11) =- (14 - p))
Proof.
(x 41) 1 (x p
Hg..)) = - Ra((e) log p(x) (B log ((2T)
exp(
2
12T((2T))
[ + E B(a -11 =- 14)
2
12x((2
E 1ー Σ) + E (2)) tr((x: 12) 12) "
2
(2x(
Σ) + tr(B
ar(By(a) y(x)
(xx 11)( - 11) )
2
2
1
l2g((2
Σ)) + (B)(a))
[xx (x p₂) T + (Hg - (1) - -+) E --1)
2
1
log((27)"
Σ|) + tr( [2g
(14g 11 1 -
2
(0g((22)4
Σ)) + tr Σ- - + 2 tr((Hg - (1 - -1) -1)² -ー
2
1og((2
Σ + 2
tr (E (#4 - 11) -11 11)
2
(W pe: p)
Lemma 2. (KL to Gaussian) Suppose q(x) is a probability density function with mean fu and covariance matrix Eg and p(æ:) NN(x:) Jr, Σ) is Gaussian distribution, then
(al(all) = DKL (xx) Ej)lpp) - H(V(x)p Eg)) - H()).
where H.)) denotes the entropy of a distribution.
Proof. According to Lemma
we have H(g. p) = H(N(2)) (x) My. Ey). Thereby,
DKl(allp) H(.p)) (()) H (NV Eg), H (g)) (c))
=H(N( Eg).p) H (N pug En)) + HN (x) Mg: Eg)) H(4) -DRL(N(ellm, Ex)(p) + H[N(x ug: Eg)) Hg)..
Lemma 3. (Equivalence between the forward and reverse Markov property) Suppose q( N ((z0) II q( (n))) is a Markov chain, then q is also Markov chain the reverse direction,
N
ie, ((FO.N)= = ((xN)) II q( (.n))
n=1
13

---

Published as a conference paper at ICLR 2022
Proof.
g( 2n. 2
(a 120. (NN)
glann ... (2N)
N
g( 1, 1,)))
II ((anglars-1)
imn+11
q(
g(xn))
11 ((x11)2)-1)
i=++1
N Thereby, g(<o.N) g(TN) II ((
mmm
Lemma 4. (Entropy of a Markov chain) Suppose q(zu:N) is a Markov chain, then
N
N
H({(zo.N)) = H(g(xN)) +
Σ
E, 1(( 100--H((aaa ((((z))) +
En H (g( (2
n=
n=
Proof. According to Lemma
we have
H ((g(Fo:))) = E8 log (xx)
II g(xn-112,,) -Bg log. ((xN)(
Bg log q q(mn-11x.,)
n=1
=H(g(#N)) H ( (g(2n-1(2n))
Similarly, we also have H (g(xo.N)) 11 (q((x)))
Σ (g (2n-1))
Lemma 5. (Entropy of a DDPM forward process) Suppose g(<o.N) a Markov chain and (een) = N (an B, then
d
N
H H(q(#o.)) = ((((x))) +
log(2Tre
2 n=1
Proof. According to Lemma 4 we have
N
d
H(g(za.N) (q())))
Σ
H(gg(( H(g(zo))
Σ
log (2xe3,.)
n=1
Lemma 6. (Entropy of a conditional Markov chain) Suppose q( (2o) is Markov, then
N
H(g(2o.N)) = (g(xx)) + (q xo)) - Σ
E. (g(2n æo)).
n=2
Proof. According to Lemma
we have
H(g(wo.)) H (q(#n)) + E, (1
=H(((())) (g(
E E H. (((a)((())-1)))) vo)).
n=
14

---

Published as a conference paper at ICLR 2022
Lemma 7. (Entropy of generalized DDPM forward process) Suppose ((ZIN|(2)) is Markov, q(æx (x)) is Gaussian with covariance x and ( vo) is Gaussian with covariance X,, then
N
H(g(Zo:N) = (((()))) log(2meBN) + 2
Σ log((22 (Tee)
Proof. Directly derived from Lemma
Lemma 8. (KL Markov chain) Suppose (( is probability distribution and p(
p(æN) II p( (x)) is Markov chain, then we have
By PepDeccl(taooownlaa//lloo/..m (ow
Σ Bag DKL (2t.g(aanna))) 1ea c.
where - (e -E, -o is only related q. Particularly, ((xDN:) is also Markov chain, then O.
Proof.
6.Palllleuxx-laa//llloxxx--ee -Eg log log -g
Eg log -.
N
Σ n=1
Eg
+
Σ n=1
Eg H (((Zn-11ZT)) - H Hg((((2uNN-1aa)
N Let
Σ (, Eg ((((///NNN1/NN) then n=l
Σ F.y DKL (1(E))(((nn11))00 1/o./////---- + cc
=
If g( is also Markov chain, according Lemma we have 0.
Lemma 9, (The optimal Markov reverse process with Gaussian transitions is equivalent to moment
N
matching) Suppose ((Fo:N) is probability density function and p(Zo:N) = II
p(=n=1/l pp(x))
n-1
is Gaussian Markov chain with p( -N( (xo.) T.T),, then the joint Kl. opti- mization
min D=L_((2O.:))l(((Ox.N)) ( hw-1
has an optimal solution
tr tr(Cov, 1/m., [In 1])
(xx) = Eggann (lm.) [nn 0,2 Egg. (ma.)
which match the first two moments of g(#n-1122 The corresponding optimal KL is
N
DKL. ERi.lg(aan ((((( (x)..))))))))))))))))))))))))))) ((((((()
log(2nee H H(q(#o,)))
n=1
Remark. Lemma 9 doesn't 't assume the form of q(vu.N), thereby it can be applied to general Gaussian models, such as multi-layer VAEs with Gaussian decoders (Rezende et al. 2014 Burda el al. 2015,. In this case, q( (m0) is the hierarchical encoders of multi-layer VAEs.
15

---

Published as a conference paper at ICLR 2022
Proof. According to Lemma
8
have
DKL DKL(g(2o.v)ll(xxx) Dka(((ew))l(xx))
Σ B 1a + e,
N where c= Σ - - H =((
Since DxL. ( is only related to pn (-) and o the joint KL optimization decomposed into n independent optimization sub-problems:
min E (g(#n | (xn)), ISnsN.
According to Lemma
we have
xn))
= (2 1g(xx- (a.) (n Co l /
+ HN (Z [B((en (w,) an 1I, la.) [en (()) E. (g((xn11()))
-F(og) + 0 1b +
where
1
F(o
(on tr(CoV ( 1l (0n)) + log o
2
1
G (m))
n
Bg E Ee(an 1 ) nn (r 11?
2
and c' 12g((2)) Eg H
The optimal pe, (I,,) ) is achieved when
g u|m,
) 11n nn (z,,, )|
Thereby, (2,,) = By(a,- - (a.)) x -1] In this case, G(o n. m4, = 0 and we only need to consider F(oz) for the optimal o By calculating the gradient of F, we know that F gets its minimum
tr(Cov g(#n-1 (a..) Rn x2)
o Eyg
In the optimal case, F(o;²)) = $1 (1 + log x²²) and
= d let log(2meo0)) - ([([
As result,
(((((()0.:)l((((0..))) = =Dralg@NN) p((()) + Σ
log 2Tee
E (q(#n-1\xw))
==1
n=1
E.g H (( (w))) (H (H((xo)))) H(((xx)))
(((((aw),
log (2g(2 - H H(g(za))).
Lemma 10. (Marginal score function) Suppose q w) is a probability distribution, then u log (w))(w) =Bg(v w) V. log q( v)
16

---

Published as a conference paper at ICLR 2022
Proof. According to (v/ww) V logg(u/w) Vug(U/w)dr V q()lw)dd 0, have W log ((w) = =V log g(w) + Bo( V logg(v)
Bggtl/)) v log q(v, w) Ey((|() V log logq(w))).
Lemma 11. (Score representation of conditional expectation and covariance) Suppose q(v, w) ())), where q(w vv) = =N(w) / (T),, then
1
E Roo [o]
(w + BV w log ((w)),
Va
B
E (v)) Cov
(I - -- V lologg(w))) log ((w) T]),
a
Lr(Cov (())))(()))))))))
3
| ((gg(()))
E (ww)
1 - (B
d
d
Proof. According to Lemma
10 we have
w Vov
V log ((w) = Eq(o//m) V log (ww)) - -By(v
B
Thereby, [o(
Ja (w + 3V log ((w)) Furthermore, we have
B² w voo w vau
2 Vav
Eg( Cov Covo(olwn)lo)
Bo(w) Cov ww)
B f2 Be vav)(w vav) Eg((w) Va log ((w) V log ((w)
W Vav w
Vou
E ((o)
T [x(r/a))
(
(T)
B
B
B
8²
82
882 By(() -aaa--Ette Eytwn Va log ((w) V logg(w)
g²
B1(n) Ey(w) Vw log (w)) ve log (og((w))
g2
1 Eg(oo) V.n logg(w) V., V. logg(w)))
3
(I-BE,, (I-BBBp(w)) (w) V
log V logg(w) )).
a
Taking the trace, we have
tr tr(Covg(o/w))oo) (b])
3 (1 BE
| log g [2)
By(wn)
d
d
Lemma 12. (Bounded covariance of bounded distribution) Suppose q(x)) is bounded distribution [a, b)d, then (=))o)(())) (2
Proof.
tr(Covg(a)(z))
tr(Cov q(
Be(w)) |x - 12
Ex
o+b ||2
d
d
ااي 12
b - 02
2
d
2
17

---

Published as a conference paper at ICLR 2022
Lemma 13. (Convert the moments of x to moments of q(zo) The optimal solution ( and o to Eq. (4) can be represented by the first two moments of q()o)
Mn (x,) = iinn [g(wolee.)
2
on = X2, (Vām-1- v 1
Tn 3,
(a tr tr xe (r))
2n
(x())
d
where qu (xx) is the marginal distribution of the forward process timestep and is the dimension of the data.
Proof. According to Lemma 9 the optimal je, and 0x under KI, minimization is
tr tr(Covale. 1/w,,) [En
M (2 E (xn-) 2.2 g. (m...)
We further derive pha Since (Dn; mo) is linear w.r.t. æo. we have
( Byg (a.) [n-11 = Eggano (m..) Bylan [2n1] -B Bg l Mrr (I 2u) (Z )
Then we consider " According to the law of total variance, we have
Cov g( [xn By(wo) (z..) CoVg(ae CoVg(ann.. (()n [In 1] + Cov CoVa(wel in,. Be(er 11 mo) [nn 1]
=>? I + Co inn (In, (In, xa) X²1 + (Van-1 / /a-1 2B V 3,
On @oo (C mo [20o) [zo]-
Thereby.
Ir(CoVgfas 1/x,,)
Bn
0,2 = =Bg. (mr.)
d
=>,- + (Von-1 -V X2
On ) BB
tr tr(Cov (xo))
V
3
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 μr, (2n) and o² Eq.
4
Hr, (zn)) = inn
Eni Van
In + B, Van log qn (zx,))
(6)
2
Br (v
1 (1- B
V xe, log gn (xx) )112
o02 X2 +
X2
Onn
where 9n (xn) is the marginal distribution of the forward process at the timestep n and d is the dimension of the data.
Proof. According Lemmal I and Lemma 13 have
P., (wx) ftn (In, Egg (o))
( Van (0n, + B, Va,, log ()x)))
18

---

Published as a conference paper at ICLR 2022
and
tr ir(Cov (orol(z (oo)
on = =1 + (van1 V 3n- - X
B (mn))
3
d
B
|V log g nxx
=1 + (V (Van-1 V 3 Pn-1 - 13 2/2
(1
3 E (mn.)
V/
3
a2
d
Br
|1V,, log q (1 (2x))l
=xa + (V
- -
- -22)
BB g
an
d
A.3 PROOF OF THEOREM 2
Theorem 2. (Bounds of the optimal reverse variance, proof in Appendix A.3
o22 has the following lower and upper bounds:
3 VB
S on S 2
X
(11)
If we further assume g( is a bounded distribution in (a, bja, then o can be further upper bounded by
where d is the dimension of data,
o S X2, + (Vom11 - Bn-1
Tn B,
2
b
2
27
(12)
2
Proof. According Lemma
13 and Theorem
have
Bn On
S on S
(V
:m-11~ 22
we further ((3r)) assume is a bounded distribution in {a, bjd, then c(x0)/en)) also bounded distribution in (a, bjd. According to Lemma 12 we have
Ir (
(20))
5 b bba
E
Combining with Lemma 13 we have
0,2 2
=22
(Va-1 V 1 X2
an 2 (x))
Ir tr(Cov qaza (o.) (mo))
V
3
<X² (Van-1 V 23
On 2
b
)
3
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
d Σ J(T-1,,TH) C.
DKL. (g(a,, " "r Brg Ilpp"llpxeaa (wo "r RTx
12
where J(T Tk) ==)== log ---ll and is constant unrelated to the trajectory
x²
19

---

Published as a conference paper at ICLR 2022
Proof. According to Lemma 7 and Lemma
we have
DKL (g(oo T , }lpp" (To, T
=E,DKL(9( Tr Txx )lp (xu (x1) + DKL (9( "xxxx, xxx))lp"(xx, (a xrk))
-B, DKL (g Fr
Trx , }1pp (2o (x1) + ((((ax)),p(a)))
d
K
+
log(2
(2TE0
Th-1lh 1178 H (q( ... , xxx))
2
2=
d
B log (200 (11) ((((2)))))((NN)))
log (2reo +2 -2
H H(((2n, "" ;FFxx)
k=2
k
= =- By (x0)==)))))))))))))))))))))))))) + ((((xx)))(ON)) +
log 2TTer 11
k
d - -H(((o)) - - (og((
d
log 2T
k=
x²2 log
Th T4-1/7 (((((())) d
-, log 1x))"<)) (1(((()))))
1og((TeBN))
Tu-1/TH
Let (TT Th) log x²2 Thte and c EE, log (20l21) ((((xN)) H1 (g((x))
12ge2 N)), then e a constant unrelated to the trajectory T and
d K
Ir, LI Mlpp (Io: Dr, ... ITk
))= ,
Σ 2 k=2
J(k-11, Tk) tc.
A.5 THE FORMAL RESULT FOR SECTION AND ITS PROOF
Here present the formal result of the relationship between the score function and the data covari- ance matrix mentioned in Section
Proposition 1. (Proof in Appendix A.5) The expected conditional covariance matrix of the data distribution is determined by the score function Va,, log 9n (Xn) as follows:
3_
Exx ) Cov q(wo) ax.)
[o]
(I-
By, [Vx,, log gm (xn) Va, log qn (In)
(15)
Ch.
which contributes the data covariance matrix according to the law of total variance
Covg(ao)) [xr] = Eyg(r..) Cov ((xo)l..)))))))) Cov [200] + Cov Covy(ar.) g(..) (eggsul [oo]-
(16)
Proof. Since q( (( (mo) (a.nlVVn Br I). according Lemma 11 we have
Br(1 By V V.,,, log qu (at,) V.,, log qn (Ix)) T))
Fyg(...) Cov Cov [zn]]
Cr
The law of total variance a classical result in statistics. Here we prove it for completeness:
By(m..) (Mmm)Come CoV [xo]] Cov Co)a(ma))) B [xo]]
=Bn(m..)) (E 2
EE Ey (m.)) [xo] (t.)) [x0]
+ E.(oa))) (o.) [x ( a. [xp]] ) (200)) (Eagen Be
-on( 1 - Em((,)) [wo] ( [xo]] T = Cov (2o).
20

---

Published as a conference paper at ICLR 2022
Algorithm The DP algorithm for the least-cost-path problem (Watson et al. 2021)
1: Input: Cost function (s. t) and integers K, N. (1 K < N)
2: Output: The least-cost-trajectory 1 1= < ... < TK = N
3: C (po)isk,nN, D (-1hisKnSN
4: C(1, 1] + 0-
5: for k = K do
Calculate C and D
6:
CJ + [C[k + (
7: Clk, k f (min, k)) min(CJ]:: k +1), ... min(CJ[;; M)))
8: Dík, f (arg min CJ] k)), arg min(I] k 1I) ." arg min ((I
9: end for
10: = N
11: for k == K to 2 do
b Calculate
12: Tk-1 f D(k TR.
13: end for
14: return
B THE DP ALGORITHM FOR THE LEAST-COST-PATH PROBLEM
to find trajectory .... < Th = n of nodes starting from and terminating at n, s.t., the total cost [(11, T2) + J 13) + ... J[Tk- Tk] is minimized. Such a problem can be solved by the DP algorithm proposed by Watson et al. (2021). Let Clk, n) be the minimized cost of the optimal trajectory. and Dik ni] be the Tk-1 of the optimal trajectory. For simplicity, we also let J(s, = oo for 2 t 2 1.
Given a function (s, with 1 < < and k,n 1,
Then for k 1, we have C[1,n]
n
N 2 n >> and [[1,n] -1 (here xo and -1
DO
represent undefined values for simplicity). For N 2 k 2 2, we have
1 < Clk: - 1,,] J(8 m) = min Clk - 1, J(,,n) k k-1sosn-1
Clk, m]
min
N 2 n n 2
I5.5N
D[k, n]
arg min Clk 1, [(s,n) arg min Clk 1, J(s,) k-1Sagn-1
N k
IS$5N
As long as D is calculated, we can get the optimal trajectory recursively by TK N and πー
Dik, Tk.. We summarize the algorithm in Algorithm
C THE BOUNDS OF THE OPTIMAL REVERSE VARIANCE CONSTRAINED ON A TRAJECTORY
In Section 4 derive the optimal reverse variance constrained trajectory. Indeed, reverse variance can also be bounded similar to Theorem) 2 We formalize it in Corollary [
the optimal
Corollary 1. (Bounds of the optimal reverse variance constrained on a trajectory)
x²2 Tu-1lT has the following lower and upper bounds:
(1 (Vantte
2 7u- S 0022 Ttull S &2 +
V
3 Tk-1
1/-1
we further assume q(x6)) is bounded distribution in [a, where d is the dimension of data, then o can be further upper bounded by
2
Th 11m I X2 1/ra + (Vāre. - Br - 22 1170 V
Qra B
a
21

---

Published as a conference paper at ICLR 2022
D SIMPLIFIED RESULTS FOR THE DDPM FORWARD PROCESS
The optimal solution M (w.) and on in Theorem and the bounds of 0, in Theorem 2 can be directly simplified for the DDPM forward process by letting X = B.. We list the simplified results in Corollary and Corollary
Corollary 2. (Simplified score representation of the optimal solution)
When X = Br the optimal solution (xr,) and 0, to Eq. (4) are
1
1 (2n))
(xxn
(En + Pn Ve, den log On (x())))
Van
Bn (,, On
V an log On (I.) 11?
Corollary 3. (Simplified bounds of the optimal reverse variance)
When X? = Bm. o% has the following lower and upper bounds:
8n
Bn S n On
we fürther assume g(200 is a bounded distribution in [a,b]* bjd, where d is the dimension of data, then o can be further upper bounded by
C1 1 - a
o
2
As for the shorter forward process defined in Eq. 13 it also includes the DDPM special case
when 2 2 = B where 372-1172 1- B Similar to Corollary 2 the optimal
3r
mean and variance of its reverse process also be simplified for DDPMs by letting X2 1-1 B 1/m Formally, the simplified optimal mean and variance are
MT 1Tx (xte)= Tr T2-1
(ETr + BTuITO-I Var, log gra. (xrx),;
2 B (1 BrulTe.s Ear, (20r))
V aang log Dr (Irr )11
7h 7-1l aTalTH
d
Besides, Theorem 3 can also be simplified for DDPMs. We list the simplified result in Corollary
Corollary 4. (Simplified decomposed optimal KL)
When X2 = Bm. the KL. divergence between the subprocess and its optimal reverse process is
d
DKi "r.""" (rxx) (lpx))lll(aa (wo Tras
xT ))
[(T=11, +
| Ver, 2r log 4Ta (x 1|
where [(K--1, TK) = log(1 Bo By-, (Kr,))
and c a constant unrelated the trajectory T.
E EXTENSION TO DIFFUSION PROCESS WITH CONTINUOUS TIMESTEPS
Song al. (2020)) generalizes the diffusion process continuous timesteps by introducing stochastic differential equation (SDE) dz = f(t) + g(t)dw. Without loss generality, we consider the parameterization of [(t) and g()) introduced by Kingma al. (021)
1 d log Ce
d3, dt
d log C 3,
m(()
g(1)²
2 dt
dt
22

---

Published as a conference paper at ICLR 2022
where and 33 are scalar-valueds functions satisfying some regular conditions Kingma al. 2021 with domain E [0, 1]. Such parameterization induces diffusion process on continuous timesteps q( 2(0.1) s.t.,
(z, 2D) = Naziloarao B, E E [0, I],
((z Zz)
31 v0 <1151,
where Otls = 0s/0s and Sejs == 3, asj.....
E.1 ANALYTIC ESTIMATE OF THE OPTIMAL REVERSE VARIANCE
2021 introduce p(z,(z,) (ZzelMoji (2)) (s < to reverse from timestep 1 to timestep where 0² is fixed Bap. In contrast, We show that o2e 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 [1. we have
Kingma et
8,
o (x)) = [ = 1(z,
(z: + Bele Vz, log ((2)));
/0tel
tr tr(Cov
Sels (((ss)
V1 log q (2,))1
a/t Eg
d
Thereby, both the optimal mean and variance have 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 r for t [0, 1], where
r, Eg(2.) (=((2))1
Notice that there are infinite timesteps in [0, 1]. In practice, we can only choose a finite number of timesteps <... it and calculate It.,. For timestep between f and f,s we can use linear interpolation between ri,-, and Tr,, Then, we can estimate o3f by
Ber (1 Be).
0/1
E.2 ANALYTIC ESTIMATION OF THE OPTIMAL REVERSE TRAJECTORY
Now we consider optimize the trajectory 0 = TI < ... < <KK = the sense of KL minimization
min DKL(g(xO, "1 1p (xo. Zry , The JK
Similar to Theorem the optimal KI. is
DKL(g(Wo. ". Zrx (1ppp Z.1.".. xTx )) ((T-11TT +
IV,,, (ogg(==,)) )! and is unrelated to т. The difference
where J(Tk-1,7H)) log(1 8Ta.Te- - E,
is that (s, is defined continuous range 0 < < 1 and the DP algorithm is not directly applicable. However, we can restrict (s, t) on finite number timesteps 0 = f < .... < Iy 1.
Then apply the DP algorithm (see Algorithm I the restricted J(s, t).
23

---

Published as a conference paper at ICLR 2022
F EXPERIMENTAL DETAILS
F.1 DETAILS OF SCORE- BRAEE MODELS
The CelebA 64x64 pretrained score-based model is provided in the official code (https: / github. com www.errooooooooooeeeeoooro /ddmm of [Song et al. (2020a). The LSUN Bedroom pretrained score-based model is provided in the official code (https:/ /ttpss///gttttte /tggtggttbb..... com/co/////ooo/oo jonathannnatahhol diffusion) of Ho et al. (2020). Both of them have a total of N 1000 timesteps and use the linear schedule (Ho al. (0200) as the forward noise schedule.
The ImageNet 64x64 pretrained score-based model is the unconditional Laybrid model provided in the official code (https://giti))))
of Nichol & Dhariwal (20T)) 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 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 the cosine schedule (Nichol & Dhariwal 2021).
com/ wtwpaaa//nnproeeddcfffiulle
The CIFARIO score-based models are trained by ourselves. They have total of N 1000 timesteps and are trained with the linear forward noise schedule and the cosine forward noise sched- ule respectively. We use the same U-Net model architecture to NNichol & Dhariwal (2021). Follow- ing Nichol & Dhariwal (202I). we train 500K iterations with a batch size of 128, use a learning rate of 0.0001 with the AdamW W optimizer (Loshchilov & Hutter 2017) and use an exponential mov- ing average (EMA) with a rate of 0.9999. We save checkpoint every 10K iterations and select the checkpoint according the FID results 1000 samples generated under the reverse variance o² = B,, and full timesteps.
F.2 LOG-LIKELIHOOD AND SAMPLING
Following Ho et al. 22020), linearly scale the image data consisting of integers in 1, .255)
to [-,, and discretize the last reverse Markov transition p(zg x to obtain discrete log- likelihoods for image data.
Following Ho et al. 2020), at the end of sampling, we only display the mean of (( and discard the noise. This is equivalent setting a clipping threshold of zero for the noise scale dT. Inspired by this, when sampling, we also clip the noise scale 02 of p(x1|x2)) such that E| S 253 where is the standard Gaussian noise and y is the maximum tolerated perturbation of a channel. improves the sample quality, especially for our analytic estimate (see Appendix G.4). We clip 02 for all methods compared in Table 2 and choose y E {1,2) according the FID score. We find y = works better on CIFARIO (LS) and CelebA 64x64 with Analytic-DDPM. For other cases, we find
y works better.
We use the official implementation of FID to pytorch (https: thuu:bbb//uuub......o thub. cwm/mmeeeeeeoc.. izer/ pytorch- f fid). We calculate the FID score on 50K generated samples on all datasets. Follow- ing Nichol & Dhariwal (22T), the reference distribution statistics are computed on the full training set for CIFARIO and ImageNet 64x64. For CelebA 64x64 and LSUN Bedroom, the reference dis- tribution statistics is computed on 50K training samples.
F.3 CHOICE OF THE NUMBER OF MONTE CARLO SAMPLES AND CALCULATION OF I'
We use a maximal M without introducing too much computation. Specifically, we set M = 50000
CIFAR10, M = 10000 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 Table and Table 3
We only calculate I in Eq. 8 once for a pretrained model, and is reused during inference under different settings (e.g., trajectories of smaller K) in Table T Table and Table
24

---

Published as a conference paper at ICLR 2022
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 trajectory, firstly determine the stride N-1 Then the kth timestep is determined 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 the score- based models (i.e., those listed in Section F.I. We get the results of Improved DDPM by run- ning its official code and unconditional hybeid models (https://gi wwggthuubb.... com/ openai/ improved- di fifsiinn).. As shown in Table 4 on the same dataset, the sizes as well as the averaged time of 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.
300.22 MB 50 10
CelebA 64x64
LSUN Bedroom
DDPM, DDIM, Analytic-PPM
200.44 MB / 29 ms
433.63 MB 438 ms
Improved DDPM
200.45 MB / 30 ms
Missing model
433.64 MB 433 ms
The DDPM and DDIM results on CIFARIO are based on the quadratic trajectory following Song al. (2020a), which gets better FID than the even trajectory. The Analytic-DPM result is based on the DDPM forward process LSUN Bedroom, and based on the DDIM forward process on other datasets. These choices achieve better efficiency than their alternatives.
25

---

Published as a conference paper at ICLR 2022
G ADDITIONAL RESULTS
G.1 VISUALIZATION REVERSE VARIANCES AND VARIATIONAL BOUND TERMS
Figure visualizes the reverse variances and Lyb terms on CIFARIO with the linear forward noise schedule (LS). In Figure 2 we show more DDPM results on CIFARIO with the cosine forward noise schedule (CS), CelebA 64x64 and ImageNet 64x64.
2-2
2-7
2-12
2
variance
variance
variance
2
2-
2-45
2-8
2
2111
2-11
2
2-15
2-14
A.
9.
8,
By
8n
22
2
2
2
2
2
2
27
2
timestep n
timestep
timestep
(a) CIFARIO (CS)
(b) CelebA 64x64
(c) ImageNet 64x64
Lyo term (bitsidim)
Lvo term (bits/dim)
0.3
Lup term 4 (bits/dim)
0.4
Br
Br
Bn
8n
0.3
0.2
0.2
0.1
0.1
0.2
0.1
2-
2
2
2
2
2
2
2
2
2
2
2
timestep
timestep n
timestep n
(d) CIFARIO (CS)
(e) CelebA 64x64
ImageNet 64x64
Figure 2: Comparing our analytic estimate 6ū and prior works with handcrafted variances 8n, and 3n. (a-c) compare the values of the variance of different timesteps. (d-e) compare the term in Tub corresponding to each timestep. The value of Tubb 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 I, with M 100 and M 50000 Monte Carlo samples are almost the same in a single trial. To explicitly see the variance, in Figure and Figure plot the mean, the standard deviation and the relative standard deviation (RSD) (i.e., the ratio of ~ (xx) and I, with different M respectively on CIFARIO (LS). In all cases, the RSD decays fast as n increases. When n is small (e.g., 71 = 1). using M = 10 Monte Carlo samples can ensure that the RSD of 1 is below 0.1, and using M 100 Monte Carlo samples can ensure that the RSD of T, about 0.025. When n > 100, the RSD of single Monte Carlo sample is below 0.05, and using only M = Monte Carlo sample can ensure the RSD of I,, below 0.05. Overall, a small M like 10 and 100 sufficient for small Monte Carlo variance.
the standard deviation to the mean) of single Monte Carlo sample [am.),
Furthermore, we show that Analytic- DPM with a small M like and 100 has a similar performance to that with a large M. As shown in Figure 6 (a), using M 100 M 50000 almost does not affect the likelihood results on CIFARIO (LS). In Table (a), we show results with even smaller (e.g., g., M 1. 10). Under both the NLL and FID metries. M 10 achieves similar result that of M = 50000. The results are similar on ImageNet 64x64, as shown in Figure 6 (b) and Table (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 (c.g., M 10), shown in T
26

---

Published as a conference paper at ICLR 2022
15000
4000
1--
....M00
3000
10000
2000
5000
1000
10
10a
10a
10
10
102
10a
timestep
timestep
(a) CIFARIO (LS)
(b) ImageNet 64x64
Figure 3: The value of Tn in a single trial with different number Monte Carlo samples M.
1250
0.25
1000
0.20
3000
750
2000
0.10
1000
250
0.05
0-
10a
10)
10a
10
16a
10
10
10
10a
10:
10a
10a
timestep
timestop
timestep
(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 [=,,(. an qn (x.) at different n CIFARIO (LS). These values are estimated by 50000 samples.
d
1250
M--1
4000
1000
M-10
0.20
3000
0.15
2000
500
0.10
250
0.05
0-
10a
10a
10a
10a
10a
10a
10a
10a
10a
timestep
timestep
timestep
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 In with different number of Monte Carlo samples M at different on CIFARIO (LS). These values are directly calculated from the mean, the standard deviation and the RSD of (..))( x.n ~ qu (wx) presented Figure
27

---

Published as a conference paper at ICLR 2022
5.5
(bits/dlm))
5.0
4 (bits/dim)
5.0
4.5
4.5
4.0
4.0
M-50000
M- M-10000
MM100
MM=00
3.5
10a
10
10a
10
102
10a
timesteps K
# timesteps K
(a) CIFARIO (LS)
(b) ImageNet 64x64
Figure 6: The curves of NLL v.s. the number of timesteps in a trajectory with different number of Monte Carlo samples M, evaluated under o² o and the even trajectory.
Table 5: The negative log- likeliiodd (NLL) and the FID results of Analytic-DPM with different
number of Monte Carlo samples M. The results with M 1, 3, 10, 100 averaged by 5 runs. All results are evaluated under the DDPM forward process and the even trajectory. We use K 10 for CIFARIO (LS) and K 25 for ImageNet 64x64.
(a) CIFARIO (LS)
(b) ImageNet 64x64
NLL +
FID L
NLL
FID
M = 1
6.220#1.126
34.05+4.97
M = 1
4.943+0.161
31.59+5.11
M 3
5.68940.424
34.2942.88
M
4.821=0.055
31.98*1.19
M = 10
5.469+0.005
33.6942.10
M 10
4.791#0.017
31.93=1.02
M 100
5.468+0.004
34.6340..6
100
4.785+0.003
31.9320.69
M 50000
5.471
34.26
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 CIFARIO (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 4
Analytic-DDi -DDM (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 we derive upper and lower bounds of the optimal reverse variance. this section, we show these bounds are tight numerically 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 (a.c), the two bounds almost overlap under the full- timesteps (K=N) trajectory. When the trajectory has smaller number of timesteps (c.g.. K=100), the two bounds also overlap when the timestep тı is large. These results empirically validate that bounds tight, especially when the timestep is large.
28

---

Published as a conference paper at ICLR 2022
2-2
2 w
combined LB
combbneee
2
combined UB
LB
2
2
2
2-14
2
2
2
2-1
2
2
2-14
22
2
2
2-14
2
2
2
timestep
timestep
timestep
timestep
(a) I.S. K=N
(b) L., K=100
(c) CS, K=N
(d) CS, K=100
Figure 7: The combined upper bound (UB) and the lower bound (LB) under full- full-timesteps (K=N) and 100-timesteps (K=100) trajectories on CIFARIO (LS) and CIFARIO (CS).
In Figure also plot the two upper bounds in Eq. 11 and Eq. 12 individually. The upper
bound Eq. (TT) is tighter when the timestep is small and the other one is tighter when the timestep is large. Thereby, both upper bounds contribute the combined upper bound.
2-2
212
UB
2-4
2-2
24
2-10
2-7
UB (1.(1
2-9.
2-4
0B
in Eq.(12)
UB (1.)
200
500
800
200
500
800
200 timestep
500
800
200
500
800
timestep
timestep To
timestap
(a) LS, K=N
LS, K=100
(c) CS, K=N
CS, K=100
Figure 8: The upper bounds (UB) in Eq. 11b and Eq. 12) under full-timesteps (K=N) and 100-
timesteps (K=100) trajectories on CIFARIO (LS) and CIFARIO (CS).
To see how these bounds work in practice, in Figure 9, we plot the probability that o% is clipped by the bounds in Theorem with different number of Monte Carlo samples M on CIFARIO (LS). For all M. the curves of ratio v.s. are similar and the estimate is clipped more frequently when n large. This as expected because when n large, the gap between the upper bound Eq. (1)) 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 implies that the clipping by bounds occurs mainly due to the error of the coorebbaedd model (H,). instead of the randomness in Monte Carlo methods.
1.0
M=1
M=10
0.8
M050
M=100
ratio
M=1000
50000
0.4
0.2
0.0
200
400
600
800
1000
timestep n
Figure 9: The probability that a² is clipped by the bounds in Theorem with different number of Monte Carlo samples M on CIFARIO (LS). The probability estimated by the ratio of &3 being clipped in 100 independent trials. The results evaluated with full timesteps K = N.
29

---

Published as a conference paper at ICLR 2022
G.4 ABLATION STUDY ON THE CLIPPING OF d2 DESIGNED FOR SAMPLING
This section validates the argument in Appendix F.2 that properly clipping the noise scale 02 in p(ar) (æ22) leads to better sample quality. As shown Figure and the sample quality of our analytic estimate. The curves of clipping and no clipping overlap as K increases, since 02 below the threshold for large K.
and Figure 11 it greaty improves
Indeed, as shown in Table 7 the clipping threshold designed for sampling in Appendix F2 is 1 to orders of magnitude smaller than the combined upper bound in Theorem 2 (i.e., the minmuu of the upper bounds in Eq. [11 and Eq. (12) when K is small.
As shown in Figure clipping 02 also slightly improves the sample quality of the handcrafted reverse variance oh Sn used in the original DDPM (Ho et al., 2020). As for the other two variances, i.e., o B, in the original DDPM and of X = 0 in the original DDIM (Song al, 2020a), their 02 generally don't exceed the threshold and thereby clipping doesn't 't affect the result.
75
clipping
clipping
clipping
40
clipping clipping
clipping
clipping
no clipping
50
50
50 e
30 g
25
25
20
102
10
10
10
10" timesteps K
timesteps K
# timesteps K
timesteps
(a) CIFARIO (LS)
(b) CIFARIO (CS)
(c) CelebA 64x64
(d) ImageNet 64x64
Figure 10: Ablation study on clipping Ø2 evaluated under Analytic-DDPM.
75
clipping
clipping
60
clipping no clipping
30
clipping clipping
clipping
clipping
50
25 g
25
20
20
0
10a
10"
10
10a
10a timesteps K
10-
10a
timesteps K
# timesteps K
timesteps
(a) CIFARIO (LS)
(b) CIFAR10 (CS)
(c) CelebA 64x64
(d) ImageNet 64x64
Figure 11: Ablation study on clipping 02 evaluated under Analytic-DDIM.
300
clipping no clipping
200
Elipping ...... no clipping
clipping .... no clipping
150
...... no cl clipping
clipping
200
c 100
100
100
100
50
0
0
10
10a
10
10a
10a
10a
10a
10a # timesteps
timesteps K
timesteps K
# timesteps K
(a) CIFARIO (LS)
(b) CIFARIO (CS)
(c) CclebA 64x64
(d) ImageNet 64x64
Figure 12: Ablation study on clipping d2, evaluated under DDPM with o = 3n
30

---

Published as a conference paper at ICLR 2022
Table 7: Comparing the values of (i) the threshold in Appendix F.2diixFF2uae used to clip ož designed for sam- pling, (ii) the combined upper bound in Theorem weee when 2. (iii) the lower bound Theorem when n = 2 and (iv) our analytic estimate 02. We show comparison results on different datasets and
different forward processes when K is small.
Model timesteps
10
25
50
100
CIFARIO (LS)
Threshold (y=2)
3.87 x 10
3.87 x 10-4
3.87 x 10
3.87 x 10
Upper bound
1.45 x 10-1
2.24 x 10
6.20 x 10-3
2.10 10-3
DDPM
Lower bound 0
9.99 10-5
9.96 x 10-5
9.84 x 10-5
9.55 10-5
8.70 x 10-3
2.99 x 10-3
1.32 x 10-3
6.54 x 10
Threshold (y=1)
9.66
10-5
9.66 x 10-6
9.66 x 10-5
9.66
10-3
Upper bound
1.37 x 10
1.96 x 10
4.82 x 10
1.36 x 10
DDIM
Lower bound
02
8.17 10-3
2.54 x 10
9.66 X 10
3.73 10
CIFARIO (CS)
Threshold (y=1)
9.66 x
9.66 x 10
9.66 x 10
9.66 x 10
Upper bound
3.56 10
6.15 x 10
1.85 x 10-3
6.80 10-4
DDPM
Lower bound
4.12 x 10-5
4.10 x 10
4.04 X 10
3.89 x 10
03
3.90 x 10-3
1.28 x 10-3 3
5.61 x 10
2.75 x 10
Threshold (y=1)
9.66 x 10
9.66 x 10
9.66 X 10
9.66 x 10
Upper bound
3.33 x 5.22 x 10-3
1.37 x 10
4.18 x 10 -4
DDIM
Lower bound
0
0
65
3.61 x 10-3
1.06 x 10-3
3.95 X 10
1.53 x 10
CelebA 64x64
Threshold (y=2) Upper bound
3.87 10-1
3.87 x 10
3.87 10
3.87 10-4
1.45 x 10
2.24 x 10
6.20 X 10
2.10 x 10
DDPM
Lower bound
9.99 x 10-5
9.96 x 10-5
9.84 10-5
9.55 x 10
62
4.04 10-3
x x 10-3
7.54
10
4.06 10
Threshold (y=1) Upper bound
9.66 x 10-5
9.66 x 1
9.66 x 10
9.66 x 10
1.37 10-1
1.96 x 10-2
4.82
10-3
1.36
10-3
DDIM
Lower bound
0
0
a3
3.74
10-3
1.26 x 10-3
5.17 x 10-4
2.11
10-1
Model timesteps
25
50
100
200
ImageNet 64x64
Threshold (y=1) Upper bound
9.66 x 10-5
9.66 x 10-5
9.66 x 10-5
9.66 x 10-3
5.93 x 10-3
1.84 x 10 33
6.44 x 10
2.61 x 10
DDPM
Lower bound
9.85 10-6
9.81 x 10-6
9.72 x 10-6
9.51 10
63
1.40 x 10-3
6.05 x 10-4
2.77 x 10
1.39 x 10-4
Threshold (y=1)
9.66 10-5
9.66 10-5
9.66 10-5
9.66 10-3
Upper bound
5.46 x 10-3
1.59 x 10-3
5.03 x 10-4
1.77 x 10-1
DDIM
Lower bound
0
1.28 10-3
5.17 x 10-4
2.12 x 10-4
9.11 10-5
31

---

Published as a conference paper at ICLR 2022
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 [3] the even trajectory (ET) has better FID results. Such 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 al. 2021
75
ET
ET
40
ET
80
ET
40
50
20
20
40
25
20
0
10
102
10
10a
10a
10a
10
10a
10a
10a
10"
# timesteps K
# timesteps K
# timesteps K
timesteps K
(a) CIFARIO (LS)
(b) CIFARIO (CS)
(c) CelebA 64x64
(d) ImageNet 64x64
Figure 13: FID results with ET and OT, evaluated under Analytic-DDPM.
G.6 ADDITIONAL LIKELIHOOD COMPARISON
Improved DDPM (Nichol & Dhariwal 202T) that predicts the reverse variance by a neural network. The comparison is based on the ImageNet 64x64 model described in Appendix F.T. As shown in Table 8 with full timesteps, Analytie-DPM achieves 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 Improved DDPM when K is small, and this is consistent with what Nichol & Dhariwal (2021) report. In contrast, our Analytic-DPP DDM performs well with the ET.
We compare our Analytic-DPM
Table 8: Negative likeeiiddoood (bits/dim) J 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. 2020al use slightly different implementation of the even trajectory CelebA 64x64. They choose a different stride a = int( ( ). and the kth 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 Analytie-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 method, we also compare with other classes of generative models in Table [0] Analytic-DPM achieves competitive sample quality results among various generative models, and meanwhile sig- nificantly reduces the efficiency gap between DPMs and other models.
32

---

Published as a conference paper at ICLR 2022
Table 9: 2020a).
FID on CelebA 64x64, following the even trajectory implementation of Song al.
Oriigiall results in Song et al. (2020a). *Our reproduced results.
Model # timesteps K
10
20
50
100
1000
CelebA 64x64
DDPM, o² Bn
33.12
26.03
18.48
13.93
5.98
DDPM, a² Bn
33.13
25.95
18.61
13.92
5.95
DDPM, 2 Bn
299.71
183.83
71.71
45.20
3.26
DDPM, af B
299.88
185.21
71.86
45.15
3.21
Analytic-DDPM
25.88
17.40
10.98
7.95
5.21
DDIM, o² X2 O
17.33
13.73
9.17
6.53
3.51
DDIM, of A OF
17.38
13.72
9.17
6.51
3,40
Analytic-DDII
12.74
9.50
5.96
4.14
3.13
Table 10: Comparison to other classes of generative models CIFARIO. We show the FID results,
the number of model function evaluations (NFE) to generate single sample and the time to generate 10 samples with a batch size 10 on one GeForce RTX 2080 Ti.
Method
FID
NFE |
Time (s) 1
Analytic-DPM, K (ours)
5.81
25
0.73
DDPM, K 90 (Ho et al. 2020
6.12
90
2.64
DDIM, = 30 (Song et al.)
2020a)
5,85
30
0.88
Improved DDPM, K 45
Nichol & Dhariwal 2021
5.96
45
1.37
SNGAN (Miyato
2018
21.7
BigGAN (cond.) (Brock el al.
2018)
14.73
StyleGAN2 Karras al. 2020a
8.32
StyleGAN2 + ADA (Karras et al.
2020a)
2.92
1
NVAE Vahdat & Kautz 2020)
23.5
Glow Kingma & Dhariwal 2018
48.9
1
EBM Du & Mordatch 2019
38.2
60
VAEBM (iiao et al. 2020)
12.2
16
33

---

Published as a conference paper at ICLR 2022
G.9
SAMPLES
In Figure 1417 17
we show Analytic-DDIM constrained on a short trajectory of K 50 timesteps generate samples comparable these under the best FID setting.
In Figure 18
we also show samples both Analytic-DDPM and Analytic-DDIM constrained on trajectories of different number of timesteps K.
21
(a) Best FID samples
(b) DAnnllyii-DDiil K 50
Figure 14: Generated samples on CIFARIO (LS).
(a) Best FID samples
(b) Analytic- K 50
Figure 15: Generated samples on CIFARIO (CS).
34

---

Published as a conference paper at ICLR 2022
(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.
35

---

Published as a conference paper at ICLR 2022
(a) Analytic DDPM, 10
(b) Analytic DDMMM K 100
(c) Analytic- DDPM, 1000
(d) Analytic-DDIM, K = 10
(e) Analytic-DDIM, K 100
(l) Analytic-DDIM, K
1000
Figure 18: Generated samples on CIFAR1O (LSS).
(a) Analytic-DDDin DDPM, 10
(b) Analytic-DDDiD DDPM,
100
(c) Analytic- Analytic-DDPM. DDPM,
1000
(d) Analytic-DDIM, K = 10
(e) Analytic-DDIM, K 100
(I) Analytic-DDIM, K = 1000
Figure 19: Generated samples on CIFARIO (CS).
36

---

Published as a conference paper at ICLR 2022
(a) Analytic- DDPM, K 10
(b) Analytic- Mnalytic-DDPM, K 100
(c) Analytic- DDPM, K 1000
(d) Analytic-DDIM, K = 10
(e) Analytic-DDIM, K 100 (1) Analytic-DDIM, K 1000
Figure 20: Generated samples on CelebA 64x64.
Dnayttic-DDPM, (a) Analytic- DDPM, K 25
(b) Analytic Analytic-DDPM, K 200
(c) Analytic- DDPM, K 4000
(d) Analytic-DDIM, K 25
(c) Analylic-DDIM, K = 200 (I) Analytic-DDIM, K = 4000
Figure 21: Generated samples on ImageNet 64x64.
37

---

Published as a conference paper at ICLR 2022
H ADDITIONAL DISCUSSION
H.1 THE EXTRA COST OF THE MONTE CARLO ESTIMATE
The extra cost of the Monte Carlo estimate I' is small compared to the whole inference cost. In fact, the Monte Carlo estimate requires MN additional model function evaluations. During inference, suppose generate M1 samples calculate the log-liked rggliiklihood of M1 samples with K timesteps.
Both DPMs and Analytic-PPMs need M1 K model function evaluations. Employing the same score- based models, the relative additional cost of Analytic-DPM is MN M,K' As shown in Appendix G.2
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 CIFARIO, let M = 10, N 1000, M1 = 50000 and
K 2 10, we obtain MN presented in Table
Mr S 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 r (T 1. (N) in (8) and reuse it among different inference settings (c.g., trajectories of various K). The reuse is valid, because the marginal distribution of shorter forward process g Pr, .... 3rg) ) timestep ты is the same as that of the full-timesteps forward process ((To:N) at timestep = тk- Indeed, in our experiments (e.g., Table p shared across different selections of K, trajectories and forward processes. Moreover, in practice, I' 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 Lyb as (o) to emphasize its dependence on the reverse variance of
When calculating the variational bound (a)) (i.e., the negative ELBO) of Analytic-DPM, we will plug 5% into the variational bound and get Lvb( Since O is calculated by the Monte Carlo method, (o)( ) is stochastic variable. A natural question is that whether (d.) ) is stochastic bound of Lvb (E [[]))), which can be judged by the Jensen's incquality if Lyb is convex or concave. However, this is generally not guaranteed, stated in Proposition 2
Proposition Lob( is neither convex nor concave w.r.l. o
Proof. Since o only influences the 7-th term L, in the variational bound Leb. where Egg (g |Kn, -E, log pl (1)
Ln = {
2 S. < N
n ==
we only need to study the convexity of L,, w.r.t. o2.
When 2 n < N.
Ln d 2 1 + log 0
1 +
[ 2o) - 14m (2n())))1
Eng
2
X2
d
Let A = X2 + E.
A ( mo) [a.))_,,_.0.,) (2. then Ln as function of o is convex when 0 < O. < 2A and concave when 2A- < o. Thereby, (o.)) is neither convex nor concave w.r.t. o²
Nevertheless, in this paper, Lv)( is stochastic upper bound of Lxx(ox)) because Lub (o +2) is the optimal. The bias of (ox) w.r.t. Lvb(o,;2) is due to the Monte Carlo method as well as the етrоr 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.I
n
H.3 COMPARISON TO OTHER GAUSSIAN MODELS AND THEIR RESULTS
The reverse process of DPMs is Markov process with Gaussian transitions. Thereby, it is inter- esting to compare it with other Gaussian models, e.g., the expectation propagation (EP) with the Gaussian process (GP) (Kim & Ghahramani 2006
38

---

Published as a conference paper at ICLR 2022
Both EP and Analytic-PPM use moment matching key step to find analytic solutions of DKL (Ptargee |Popt) terms. However, to our knowledge, the relation between moment matching and DPMs has not been revealed in prior literature. Further, compared to EP, emphasize that 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 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 Ptarger can be easily computed or approximated. For instance, the original EP Miinaa 2001) considers Gaussian mixture likelihood (or Bemoulli 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 (( of the corresponding joint distribution ((Fo:)) defined by the forward process. Note that the moments of q( x are nontrivial to calculate because it involves
unknown and potentially complicated data distribution. Technically, in Lemma 13 we carefully use the law of total variance conditioned on wo and convert the second moment of (( (.,)) to that of g( (.,,), which surprisingly can be expressed as the score function as proven in Lemma
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. (020). As presented in Appendix (E) our method can be applied to continuous DPMs, e.g., variational diffusion models (Kingma et al. (2221) that learn the forward noise schedule. It is appealing to see how Analytic-DPM DPM works on these continuous DPMs. Finally, it is also interesting incorporate the optimal reverse variance the training process of DPMs.
39


Reviews:
[{"review_id": "Pm0oyznxmaz", "reviewer": "Reviewer_ejLx", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- Paper has single well-executed idea (optimal variance can be computed as a function of score) \n- Improvements over generally fair base lines are achieved by only post-processing; no additional training needed\n- Paper is generally well-written and straightforward to read\n- I did not check all Lemmas (appendix) in detail, however, it seems that their proofs are generally very rigorous and detailed.\n- The bounds in Theorem 2 are quite nice. Given that DPMs are often used for images, the specific bound for the data distributions supported in the $d$-dimensional cube are quite applicable.\n\nWeaknesses:\n- For $K<100$, FID scores of the proposed method greatly rely on a trick of clipping the variance of the step $n=2$ (can be seen in appendix G.4). This seems to be a crucial element and should be discussed more in the main paper. In particular, I would like to see how this clipping compares to the bounds (and the clipping) of the optimal score wrt Theorem 2.\n- The post-processing method can be quite expensive. For example, on ImageNet the best values are achieved using $MK= 400000$ additional ($M=100, K=N=4000$) function evaluations. For even trajectories (ET), the obvious solution would be to simply use $K \\ll N$ (results for this are shown in paper), however, if I am not mistaken, for the optimal trajectory (OT), computed using the DP algorithm from [4], $MN$ functions have to be evaluated for any $K$ (see appendix B and eq (14)). Therefore, in my opinion, the comparison of DDPM and Analytic=DDPM in the OT setting of Table 1 is unfair.\n\nSuggestions:\n- It would be helpful to understand how often the estimator is actually clipped. I suggest to compute $R$ (maybe $R=100$) estimators for, say $M=[1,10, 50, 100, 500, 1000]$, and plot he number of the ratio of estimators that was clipped over $M$. This could be done for a few different instantiations of $n$ (I guess there will be more clipping for $n$ being small).\n- the estimator $J$ in (14) is biased even when the correct score is known ($J$ is the log of an unbiased (Monte Carlo) estimator); it might be nice to mention this fact.\n- It would be nice to see even lower $M$ in the ablations in G.2. Instead of only indicating variance by plotting the estimator in Figure 3, it would be nice to see the estimated variance of the sampler directly.\n- Please state the number of Monte Carlo samples used for results in Tables 1,2,3.\n- To me it seems that the optimal variance could also be used for training, using for example only $M=1$. I would be curious to see how this performs compared to using the optimal variance only as a guide for post-processing. I greatly encourage the authors to try this (in case there are no major problems I am missing)", "summary_of_the_paper": "In Sec. 2, the authors review the general framework of Diffusion Probabilistic Models~(DPMs) with non-Markovian forward processes from [1] which has DDPMs [2] and DDIMs [1] as special cases. They emphasize that the variance of the reverse process, such as in DDPM and DDIM, are generally hand-crafted.\n\nIn Sec. 3, the authors present their main theorem: the optimal variance of the reverse process at step $n$ is a linear function of the expected squared norm of the score at step $n$. As a post-processing scheme of learned models, they then propose to replace the commonly used hand-crafted variances by an estimator of their optimal variance: in particular, the score is replaced by the learned score model and the expectation is replaced by a Monte Carlo estimate (with $M$ samples) thereof. In the remainder of this section, the authors derive bounds for the optimal variance and state that in practice their estimator is clipped according to these bounds.\n\nIn Sec. 4, the authors repeat the derivation of an optimal variance and bounds thereof when only a subset (of size $K$) of the $N$ timesteps are used for inference as is very common in the literature [1, 3, 4]. Furthermore, they show how their estimator in this setting can be used to still compute the optimal subset according to the commonly used DP algorithm introduced in [4].\n\nIn Sec. 6, they apply their post-processing scheme to models trained on CIFAR-10, CelebA 64 and ImageNet 64 and show that it generally leads to improved likelihood and FID scores. They show that their post-procecssing scheme consistently outperforms suboptimal hand-crafted choices (such as in DDPM and DDIM).\n\nReferences:\n\n[1] Song et al. Denoising Diffusion Implicit Models. ICLR 2021.\n\n[2] Ho et al. Denoising Diffusion Probabilistic Models. NeurIPS 2020.\n\n[3] Dhariwal & Nichol. Diffusion Models Beat GANs on Image Synthesis. arXiv:2105.05233.\n\n[4] Watson et al. Learning to Efficiently Sample from Diffusion Probabilistic Models. arXiv:2106.03802.", "summary_of_the_review": "Overall, I vote for accepting. The paper provides an important insight in DPMs and shows improved results for pretrained models by a simple post-processing technique. My major concern about the paper is that OT [4] does not work well in combination with their method, which in my opinion makes the work slightly less significant. I hope the authors can address this concern in the rebuttal period.\n\n**Post discussion period update:**\nI strongly vote for accepting (and also changed the correctness score from 3 to 4). All of my concerns, questions, and suggestions have been addressed by the authors in the discussion period. I thank the authors for this productive reviewing process.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HVoY12Mc5YC", "reviewer": "Reviewer_FHw9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**novelty, significance**\n\nThe result on optimal variance is new, to the best of my knowledge. The authors also do a reasonable job in convincing me that a Monte Carlo estimate of it is useful for inference. Given the recent progress and interest on DPMs, I think this work will also have reasonable significance and influence. \n\n**presentation**\n\nAuthors do a reasonable job on the writing and presenting experimental results. Past works are adequately and appropriately cited, to the best of my knowledge. \n\n**Technical quality and correctness**\n\nOne thing I'll add here is that once the Monte Carlo estimate of $\\sigma_t^2$ is plugged into the bound computation, it seems we end up with a stochastic lower bound of the ELBO (assuming the loss is concave in $\\sigma_t^2$). The important thing here to note perhaps is that bias is introduced. To put it more concretely, say the quantity being estimated is $\\mathbb{E}[ f(\\sigma_t^2) ]$, where I've written the bound as the expectation of the loss $f$ as a function of $\\sigma_t^2$. The estimator $f(\\hat{\\sigma}_t^2)$ is now a stochastic lower bound on the original quantity by Jensen's, since \n$$\\mathbb{E} [f(\\hat{\\sigma}_t^2)] \\le \\mathbb{E} [f( \\mathbb{E} [ \\hat{\\sigma}_t^2 ] ) ]  = \\mathbb{E} [f( \\sigma_t^2)].$$\n\nI think there should be some discussion about this. I'm assuming $f$ is concave in $\\sigma_t^2$, mostly reasoning from past bounds, but authors should perhaps make parts of the discussion more precise. \n\n**Experimental results**\n\nAuthors do a reasonable job in evaluating their method. One particular point I didn't get is how $M$ (number of samples for estimating the expected score) is chosen. The are a couple of potential issues here.\n- Selecting $M$ requires additional hyperparameter tuning, potentially; the tuning procedure should be reported. \n- How results depend on $M$ isn't entirely clear just from reading the main text (maybe there's some discussion in the appendix, but I didn't have time to read all content in the appendix). Ideally, some discussions should appear in the main text.\n- Large $M$ incurs more compute cost during inference -- while this seems less an issue when inference is run on GPUs (since most scenarios, I'd guess, there's enough cores to parallelize the Monte Carlo samples), this could be an issue for CPU inference. How does the run-time in practice compare in this case? Note while practical systems don't tend to run training on CPUs, inference on CPUs is still quite common. ", "summary_of_the_paper": "The paper studies diffusion probabilistic models, and derives the optimal mean and variance (as functions of the expected data score) for the reverse process. Authors then propose to plug in a Monte Carlo estimate of the the variance for the reverse process and experimentally show how this leads to improved results with trained and/or pretrained models in terms of FID and NLL. In addition, authors combine their approach with recent work that optimizes for \"knot\" locations given a fixed number of knots for faster sampling. ", "summary_of_the_review": "Authors study choosing the optimal variance for the reverse process in DPMs and propose to Monte Carlo estimate it for improved inference.  Technical quality, writing, and experiments are mostly good with the two minor caveats I described above. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BN1_YyCfcR-", "reviewer": "Reviewer_a5eg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The paper is clearly written and well organized. Contents are easy to follow. There are many technical details for readers to understand the results, such as the derivation of Theorem 1.\n\n2. The analytic results are interesting and novel. According to the introduction and the related work sections, the optimal forms of the reverse process of DPM didn't appear in the previous DPM work and I believe it will help people in the field of DPM better understand this type of models. The bias analysis and the bound of the variance are helpful to understand the estimate and improve the estimate performance. The authors also make detailed discussions on these results, which are very helpful.\n\n3. The experiment results are strong. The authors not only validate their analytic forms but also present the outperformance of their methods. The experiment results show significant improvements in their methods.\n\nWeaknesses:\n\n1. The DPM is a Gaussian-distribution-based simple model and similar analytic results can exist in similar models. The Gaussian model considered in this paper has a simple Markov property, which as a result has decomposable probability. The optimization is via forward KL divergence. Therefore, for example, the classical result on the expectation propagation algorithm with the Gaussian process can simplify the derivation: the decomposable form of the probability guarantees the forward KL decomposable, and minimizing the forward KL is equivalent to moment matching. So, I am concerned that the contribution is not as much as what was introduced in the paper. I also believe that such kind of connection will be helpful to figure out the possible further directions along this line and also save energy to get new results. I suggest authors add some discussions on the connection to other Gaussian models and their results.", "summary_of_the_paper": "The paper studies an estimate of the reverse process of a diffusion probabilistic model (DPM). The reverse process is usually estimated by minimizing the KL divergence between the forward and the reverse process. Authors present that the optimal mean and variance of the reverse process have analytic forms w.r.t. the score function. The form of the optimal mean coincides with the parameterization in the previous work and justifies a reweighted variant of the variational bound proposed in the recent work. Different from the handcrafted strategies employed in other work, the authors propose a novel estimation for the variance and analyze its bias. To reduce the bias, bounds of the optimal reverse variance are analyzed and the estimate is clipped based on the bound. Furthermore, the KL divergence between the forward and the optimal reserve process also has an analytical form and as a result, the authors propose the optimal trajectory which has minimal KL value. Finally, the authors present the relationship between the score function and the data covariance matrix and assess the proposed approach in the experiments. The experiment results show that the analytic results improve the efficiency, likelihood, and sample quality.", "summary_of_the_review": "The paper contributes interesting analytic results to the DPM models and the methods perform well in practice. However, the DPM is a simple Gaussian model and similar results can appear in other similar models.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4Qh32Izg8a5", "reviewer": "Reviewer_Xtgn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n* Strong theoretical motivation and strong empirical results to support it.\n* Nicely written, does a great job putting prior work in the context of the new insights on optimal reverse mean and variance.\n* Despite the abundance of theory / derivations, the paper still remains accessible.\n\n**Weaknesses**\n\nI am convinced by the paper in its current form. But if I had to list something:\n* It would be great to see applications of this method to other data modalities, such as for example speech / sound generation.\n* The performance of Analytical-DPMs on methods that learn forward process variance schedules (e.g. VDMs) would also be great to see.", "summary_of_the_paper": "The paper proposes a theoretically grounded method for estimating *optimal* reverse process variances for DDPMs and DDIMs. This method can be applied to a trained DDPM / DDIM after the fact and lead to improved likelihoods and faster sampling (when used together with optimal trajectory search). The proposed method and theoretical insights also perform strongly in practice across a range of models and datasets.", "summary_of_the_review": "The paper provides valuable insights into optimal reverse process variance of DDPMs and DDIMs, and makes connections between the proposed optimal variance and previous handcrafted choices, etc. The improved understanding of these model classes could have been sufficient to recommend acceptance. However, the empirical results, especially those around faster sampling are also strong and convincing. DDPMs / DDIMs achieve high sample quality and it's primarily their sampling speed that prevents practical application off this model class in real-world systems. This works makes a significant step towards enabling faster sampling for this model class.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "19df0k-PGMz", "reviewer": "Reviewer_Qdy8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. the paper derives the optimal reverse variance for diffusion probabilistic models as well as its lower and upper bound. This leads to more efficient DPMs with better performance compared to existing DPM variants. It also leads to new insights into DPMs such as why the way the reversed variance is chosen by existing work is not ideal.\n\n2. The paper is clearly presented. The technical results reported in the paper are non-trivially obtained. The relationship between the paper and existing works is well discussed and well-motivated.\n\n3. Experimental results compared to other variants of DPM are well discussed. It also demonstrates the advantage of the proposed method compared to existing DPM variants.\n\nWeakness:\n1. Although proposition 1 establishes the relationship between data covariance and score function, it is unclear to me what is the practical implication of proposition 1.\n\n2. In the experiment, it is unclear to me whether timestep is a good metric to measure efficiency in Table 3. Does each method spend roughly the same time at each timestep?\n\n3. While the authors compare the proposed method with other existing variants of DPMs. Is there any reason why the comparison between the proposed method and other classes of generative models such as GAN should be conducted or not?\n\n", "summary_of_the_paper": "The paper proposed a modification of the diffusion probabilistic models (DPMs) called analytic-DPM that is based on an analytic estimate of the optimal reverse variance. Using this analytic estimate, the proposed method can achieve fast and performant inference through the Monte Carlo method and pre-trained score-based model. The derivation of the optimal reverse analytic mean and variance is proven to be associated with the score function. Upper bounds and lower bounds are provided for the optimal reverse variance, the relationship between the data covariance and the score function is shown. Experimental results are provided by comparing the proposed method with existing variants of DPMs, through both negative log-likelihood and FID as metrics. The experimental results suggest that the proposed method can potentially provide better performance more efficiently compared to alternatives.", "summary_of_the_review": "Correctness: I think the paper is mostly correct. I am not sure if using timestep is a good metric to demonstrate the efficiency of the proposed method. Since efficiency is a major aspect of the proposed method, it would be desirable to make a clarification on this issue.\n\nNovelty and significance: I think the derivation of the optimal reverse variance is novel and insightful. The lower bound and upper bound of the optimal reverse variance is also useful in practice. While the proposed method is performant compared to existing DPM variants, these existing variants achieve better or comparable FID or negative log-likelihood with enough timesteps. These strong baselines suggest the (potentially limited) headroom left for improvement for the proposed method.\n\nOverall, I think the paper solves an interesting problem in DPM. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an analytic approach for estimating the optimal reverse variance schedule given a pre-trained score-based model. The experimental results demonstrated the efficacy of the proposed method on several datasets across different sampling budgets. Given the recent interest in score-based generative models, I believe that the paper will find applications in various domains. I am pleased to recommend it for acceptance.
Decision: Accept (Oral)