# Faster Provable Sampling for Score-Based Diffusion

David S. Hippocampus
Department of Computer Science
Cranberry-Lemon University
Pittsburgh, PA 15213
<EMAIL_ADDRESS>
Use footnote for providing further information about author (webpage,
alternative address)— _not_ for acknowledging funding agencies.

###### Abstract

Score-based diffusion models have become the most popular approach to deep
generative modeling of images, largely due to their empirical performance and
reliability. But they also have nice theoretical properties: both the sample
complexity of training a sufficiently good score model with the ERM, and the
time complexity of sampling from the distribution given the trained model, are
polynomial in the parameters (dimension $d$, accuracy $\varepsilon$ as a
fraction of data radius, failure probability $\delta$, and bit complexity of
the model). We show for both the sample complexity of training and the time
complexity of sampling that the dependence on the accuracy $\varepsilon$ can
be improved from polynomial to logarithmic.

Our main observation is that as the diffusion process smooths the
distribution, it becomes more Lipschitz. This suggests a different step size
schedule for sampling, which (both synthetically and when applied to Stable
Diffusion) empirically leads to good samples from many fewer iterations.

##  1 Introduction

Score-based diffusion models are currently the most successful methods for
image generation, with popular models such as stable diffusion
Rombach_2022_CVPR, Midjourney, and DALL·E 2 dalle2 as well as state-of-the-art
performance on audio and image generation tasks
first_diffusion_probabilistic_models; first_ddpm; cs_mri; songmri;
diffusion_beats_gan.

A generative model involves two components: _training_ an estimate of the
distribution, and _sampling_ given the trained estimate. Compared to GANs
goodfellow2020generative, sampling from a score-based model is somewhat more
complex but training is much simpler.

For any distribution $q$ over $\mathbb{R}^{d}$, consider the smoothed
distribution $q_{\sigma}:=q*N(0,\sigma^{2}I_{d})$ and corresponding smoothed
score $s_{\sigma}(y):=\nabla\log q_{\sigma}(y)$. Score-based generative models
involve approximating $s_{\sigma}$ for various values of $\sigma>0$, then
using these to approximately sample from $q$. One can show that $s_{\sigma}$
is the minimizer of

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
q}\operatorname*{\mathbb{E}}_{z\sim
N(0,\sigma^{2}I)}\left\|s(x+z)-\frac{-z}{\sigma^{2}}\right\|^{2}_{2}.$ (1)

This gives a practical method for estimating $s_{\sigma}$: minimize the
_empirical_ value of (1) over samples $x_{i}$ from the distribution and
independent noise samples $z_{i}$. Such a minimizer can be approximated in
practice using deep neural networks, with the objective optimized by
stochastic gradient descent.

Given estimates $\widehat{s}_{\sigma}$ of the true $s_{\sigma}$ at various
noise levels $\sigma$, one can approximately sample from the distribution $q$
by various methods. One method, known as Denoising Diffusion Probabilistic
Modeling (DDPM) first_ddpm, is to reverse an SDE: for $X_{0}\sim q$ we can
consider the forward SDE

$\displaystyle\operatorname{d}\\!{X}_{t}=-X_{t}\operatorname{d}\\!{t}+\sqrt{2}\operatorname{d}\\!{B}_{t}$
(2)

for Brownian motion $dB_{t}$. This converges to a standard normal distribution
according to $X_{t}\sim e^{-t}X_{0}+\sqrt{1-e^{-2t}}N(0,I_{d})$ for $X_{0}\sim
q$. The SDE (2) has a corresponding reverse process anderson1982reverse

$\displaystyle\operatorname{d}\\!{X}_{t}=-(X_{t}+2s_{t}(X_{t}))\operatorname{d}\\!{t}+\sqrt{2}\operatorname{d}\\!{B}_{t}$
(3)

where $s_{t}$ is the score of the distribution of $X_{t}$, which is a rescaled
version of a smoothed score of $q$. That is to say, if we start at $q$ and run
the (2) process forward, we end at $X_{T}$ that is distributed exponentially
close to a standard normal; but if we start at a sample of $X_{T}$ and run (3)
_backward_ in time, we end at a sample $X_{0}\sim q$. Therefore, if we start
at $X_{T}\sim N(0,I_{d})$ and run (3) backward we end at $X_{0}$ that is
$\delta$-close in TV to being drawn from $q$, as long as $T$ is large enough;
which is $T=O(\log\frac{m_{2}}{\delta})$, where $m_{2}$ is the square root of
the second moment of $q$.

From a theoretical perspective, there are a number of questions about how
score-based generative models behave. In this paper we consider the following:
(A) how should the continuous process (3) be discretized, and how many steps
are needed? (B) how accurate must the score estimates $\widehat{s}_{t}$ be for
the samples to be close? (C) how many samples are needed for the empirical
optimization of (1) to produce sufficiently accurate scores, and under what
assumptions?

These questions have been the focus of a flurry of works in recent years. On
the _sampling_ side, several results are known under different assumptions on
the data distribution and score accuracy BMR20; liu2022let;
lee2022convergence; chen; lee2023convergence. If the score is $L$-Lipschitz
and sufficently bounded in $L_{2}$, and the distribution has bounded second
moment $M_{2}$, then chen; lee2023convergence show that the reverse process
can be discretized to achieve $\gamma$ error using
$\widetilde{O}(\frac{L^{2}d}{\gamma^{2}})$ steps.

On the _learning_ side, suppose we take the empirical minimizer over a class
$H$ of score functions. In the realizable setting (so the true score lies in
$h$), BMR20 shows that the sample complexity for $L_{2}$ error $\gamma$ is
polynomial in $\gamma$, the Rademacher complexity $\mathcal{R}$ of $H$, the
radius $R$ of the data, dimension $d$, and the Lipschitzness $L$ of the score
function.

It’s not clear that one should expect the score functions to be Lipschitz, but
$\sigma$-smoothed scores are: if the distribution has range bounded by $R$,
the $\sigma$-smoothed score is $\operatorname{poly}(d(R/\sigma))$-Lipschitz.
This gives the current state of the art for a bound from very minimal
assumptions on the data: for distributions bounded by $R$, sampling to within
accuracy $\gamma R$ takes $\operatorname{poly}(d/\gamma)$ time given
sufficiently good scores in $L_{2}$ chen; lee2023convergence; and for a class
$H$ of score functions realizing the true scores, the empirical minimizer of
(1) is a sufficiently good score function given
$\operatorname{poly}(d/\gamma)\cdot\mathcal{C}(H)$ samples, where
$\mathcal{C}(H)\leq\log\left|H\right|$ is a Rademacher complexity-based
measure of the complexity of $H$ (roughly equal to the number of parameters,
for a neural network bartlett2017spectrally).

In this paper we get exponential better dependence on the accuracy $\gamma$,
based on one simple observation: _smoother models are better behaved_. Early
on the reverse process, the distribution has been smoothed by a large
$\sigma$; this induces a smooth score, so the step size can be relatively
large. Later on, when $\sigma$ is small, the step size must also be small. Our
calculations recommend a step size proportional to
$\sigma^{2}=1-e^{-2t}=\Theta(\min(t,1))$; with these steps, we can integrate
from $T$ down to $\gamma$ in $O(T+\log\frac{1}{\gamma})$ steps. This is in
contrast to the constant step sizes used in chen: to perform well at the end
the step size must be $O(\gamma)$, leading them to need $O(T/\gamma)$
iterations.

######  Theorem 1.1 (Simplified version of Theorem A.7).

Let $q$ be a distribution over vectors with norm having second moment
$m_{2}^{2}$.

$N>\widetilde{O}(\frac{d^{3}}{\delta^{2}}\log^{2}\frac{m_{2}}{\gamma}).$

Then the reverse process (3) with true scores, discretized to $N$ steps with
step size proportional to $1-e^{-2t}$, returns a distribution $\widehat{q}$
such that there exists $q^{\prime}$ with
$TV(\widehat{q},q^{\prime})\leq\delta$ and $W_{2}(q^{\prime},q)\leq\gamma$.

The same holds for approximate scores, as long as each $\widehat{s}_{\sigma}$
for the variances $\sigma^{2}$ considered by the algorithm has

$\operatorname{\mathbb{P}}_{x\sim
q_{\sigma}}[\left\|\widehat{s}_{\sigma}(x)-s_{\sigma}(x)\right\|_{2}>\frac{\delta}{\sigma\sqrt{N}}]\leq\delta/N.$

Theorem 1.1 shows that, with carefully chosen step sizes, the approximation
error $\gamma m_{2}$ depends logarithmically on $\gamma$; alternatively, the
error depends logarithmically on the scale of the distribution $q$. Prior work
required a polynomial dependence for similar bounds. The “mixed” error bound,
with both a $\delta$ failure probability and $\gamma$ additional $W_{2}$
error, is comparable to chen.

A similar idea applies to the sample complexity of training. Theorem 1.1
requires $\widehat{s}_{\sigma}$ to have error proportional to
$\frac{1}{\sigma}$: the more-smoothed models are used for more time, so they
need to be estimated more precisely. Fortunately, being smoother means they
are correspondingly easier to estimate:

######  Theorem 1.2 (Simplified version of Theorem LABEL:thm:scoreestimation).

For any $\sigma>0$, consider any family $H$ of candidate score functions such
that there exists $h\in H$ with

$\operatorname*{\mathbb{E}}_{x\sim
p_{\sigma}}[\left\|h(x)-s_{\sigma}(x)\right\|_{2}^{2}]\leq\frac{\delta^{2}\varepsilon^{2}}{40\sigma^{2}}.$

Then with $1-\delta$ probability, the empirical minimizer $\widehat{s}_{r}$ of
(1) from
$M>\widetilde{O}(\frac{1}{\varepsilon^{4}\delta^{2}}d^{2}\log\left|H\right|)$
samples satisfies

$\left\|\widehat{s}_{\sigma}(x)-s_{\sigma}(x)\right\|\leq\varepsilon/\sigma$

with probability $1-\delta$ over $x\sim p_{\sigma}$.

Thus getting accuracy $\frac{1}{\sigma}$ requires a number of samples
independent of $\sigma$. Combining with Theorem 1.1, we find that

$M=\operatorname{poly}(\frac{1}{\delta}d\log\frac{1}{\gamma})\log\left|H\right|$

samples to get sufficiently accurate scores for $(\gamma
m_{2},\delta)$-approximate sampling.

#### Experiments.

While our analysis is primarily focused on theoretical guarantees, it gives
one practical suggestion: a different step size schedule for sampling. Our
analysis suggests that, since smoother models are better behaved, the step
size should be proportional to the smoothing variance, which is
$1-e^{-2t}=\Theta(\min(1,t))$.

The first practical demonstration of diffusion models for high quality
sampling, DDPM first_ddpm, used the process (3) with step sizes proportional
to $\Theta(t)$ at time $t$. Theory results like chen use constant step sizes,
proportional to $\Theta(1)$. Our recommendation is proportional to
$\Theta(\min(1,t))$, so it is an interpolation between the two.

We find that our suggested step size schedule leads to improved performance
for discretizing the backwards process (3), both in synthetic experiments
(Figure 1) and in comparison to DDPM in Stable Diffusion Rombach_2022_CVPR
(Figure LABEL:fig:our_stable_diffusion and Figure
LABEL:fig:ddpm_stable_diffusion). Of course, simply changing the step size
schedule is not as good in practice as some more recent sampling methods
(e.g., karras2022elucidating), but it is remarkable that one theoretically-
inspired tweak to the original DDPM algorithm leads to such improvements.

###  1.1 Related work

Score-based diffusion models were first introduced in
first_diffusion_probabilistic_models as a way to tractably sample from complex
distributions using deep learning. Since then, many empirically validated
techniques have been developed to improve the sample quality and performance
of diffusion models first_ddpm; improved_denoising;
yang_ermon_improved_techniques; song2021scorebased; song2021maximum. More
recently, diffusion models have found several exciting applications, including
medical imaging and compressed sensing cs_mri; songmri, and text-to-image
models like DALL$\cdot$E 2 dalle2 and Stable Diffusion Rombach_2022_CVPR.

Despite the large body of work studying diffusion models empirically, a solid
theoretical understanding of why diffusion models are so successful at
generating high-quality samples remains elusive, particularly since we seem to
lack a convincing understanding of why neural networks succeed at score
estimation. Nevertheless, a recent set of works chen; bortoli2021diffusion;
lee2023convergence have attempted to develop a theoretical understanding of
diffusion models by whether or not accurate score estimation implies fast
convergence of the diffusion model to the true distribution.

The strongest result is chen: given sufficiently good $L_{2}$-approximate
scores, the algorithm gets within $\varepsilon$ in TV distance in
$\operatorname{poly}(m_{2}Ld/\varepsilon)$ time, where $L$ is the
Lipschitzness of the score. But it’s not clear why the score, particularly the
_unsmoothed_ score, would be globally Lipschitz; that’s a requirement that the
distribution has no sharp edges. So chen also gives a corollary for
$R$-bounded distributions, with
$\operatorname{poly}(\frac{Rd}{\varepsilon\gamma})$ time to be
$\varepsilon$-close in TV to a distribution that is $\gamma$-close in $W_{2}$.

Our main contribution is that the number of samples and time can scale
_logarithmically_ in $(R/\gamma)$. The $\sigma$-smoothed distribution really
does have only $\operatorname{poly}(R/\sigma)$ Lipschitzness, but it has much
better _local_ Lipschitzness: with high probability, it is about
$\operatorname{poly}(1/\sigma)$-Lipschitz in a small neighborhood of the
random sample $x$ reached during the diffusion process. And this better
Lipschitzness, as well as other niceness of the smoothed distribution whp over
$x$, leads to a $\log(m_{2}/\gamma)<\log(R/\gamma)$ dependence.

##  2 Proof Overview

#### Smoothed scores.

The key innovation supporting both our theorems is to make use of the
smoothness caused by the diffusion process. The nice behavior of the smoothed
score has been studied in the context of location estimation GLPV22; GLP23,
and we make use of similar observations.

Consider the $1$-dimensional $\sigma$-smoothed distribution $y=x-z$ for $x\sim
q$ and $z\sim N(0,\sigma^{2})$. One can calculate (see, e.g., Lemma A.2 of
GLPV22) that the smoothed score satisfies:

$\displaystyle
s_{\sigma}(y+\varepsilon)=\frac{1}{\sigma^{2}}\frac{\operatorname*{\mathbb{E}}_{z\mid
y}[e^{\varepsilon
z/\sigma^{2}}(z-\varepsilon)]}{\operatorname*{\mathbb{E}}_{z\mid
y}[e^{\varepsilon z/\sigma^{2}}]}.$ (4)

Because $z$ is a standard gaussian on average over $y$, one can use (4) to
show that $s_{\sigma}(y+\varepsilon)$ is well-behaved with high probability
over $y$. For example: by setting $\varepsilon=0$, for any $k$ we have

$\operatorname*{\mathbb{E}}_{y}[s_{\sigma}(y)^{k}]=\operatorname*{\mathbb{E}}_{y}[\operatorname*{\mathbb{E}}_{z\mid
y}[\frac{z}{\sigma^{2}}]^{k}]\leq\operatorname*{\mathbb{E}}_{z}[(\frac{z}{\sigma^{2}})^{k}]\leq
k^{k/2}/\sigma^{k},$

and therefore the score $s_{\sigma}(y)$ is subgaussian: it is
$O(\frac{1}{\sigma}\sqrt{\log\frac{1}{\delta}})$ with probability $1-\delta$.

By taking the derivative of (4) with respect to $\varepsilon$, we get an
expression for $s_{\sigma}^{\prime}(y+\varepsilon)$. Then a similar argument
to the above shows that, with probability $1-\delta$ over $y$, for all
$\left|\varepsilon\right|\leq\frac{\sigma}{\sqrt{\log\frac{1}{\delta}}}$ we
have

$\displaystyle\frac{-1}{\sigma^{2}}\leq
s_{\sigma}^{\prime}(y+\varepsilon)\lesssim\frac{\log\frac{1}{\delta}}{\sigma^{2}}.$
(5)

That is to say, with high probability $s_{\sigma}$ is about
$\frac{1}{\sigma^{2}}$-Lipschitz in a neighborhood about a random sample $y$.
This proof generalizes to high-dimensional distributions with a polynomial
loss in $d$; see Lemma E.1. Our analysis will use this, among other nice
properties of the smoothed score.

###  2.1 Sampling

#### Background.

The forward process (2) converges to within $\delta$ total variation of
$N(0,1)$ after $T=O(\log\frac{m_{2}}{\delta})$ time. Therefore if we run the
backward process (3) from $X_{T}^{\prime}\sim N(0,1)$, we would end at
$X^{\prime}_{0}$ that is $\delta$-close in TV to being distributed according
to $q$. However, $X_{0}$ is not smoothed, and we will need smoothing to have a
fast algorithm. Therefore we only run the reverse process down to $X_{\gamma}$
for some small $\gamma$; this effectively adds $N(0,\gamma)$ noise to the
result, leading to the desired mixed $(\delta,\gamma)$ guarantee if we could
run the continuous process (3) perfectly with perfect score estimates.

The question is, (A) what is the effect of _discretizing_ the process, and (B)
how robust is this to noisy scores?

We begin with some basic understanding of SDEs. Consider two _discrete_
processes,

$X_{i+1}=f_{i}(X_{i})+N(0,I)$

and

$Y_{i+1}=f^{\prime}_{i}(Y_{i})+N(0,I)$

that run from $0$ to $n$, starting from $X_{0}=Y_{0}=0$. The KL divergence
starts out

$\textup{{KL}}(X_{1}\|Y_{1})=\textup{{KL}}(N(f_{0}(0),I)\|f_{0}^{\prime}(0),I)=\frac{1}{2}\left\|f_{0}(0)-f_{0}^{\prime}(0)\right\|_{2}^{2}.$

Then by the chain rule of divergences,

$\displaystyle\textup{{KL}}((X_{1},X_{2})\|(Y_{1},Y_{2}))$
$\displaystyle=\textup{{KL}}(X_{1}\|Y_{1})+\operatorname*{\mathbb{E}}_{x\sim
X_{1}}\left[\textup{{KL}}((X_{2}\mid X_{1}=x)\|(Y_{2}\mid Y_{1}=x))\right]$
$\displaystyle=\frac{1}{2}\left(\left\|f_{0}(0)-f_{0}^{\prime}(0)\right\|_{2}^{2}+\operatorname*{\mathbb{E}}[\left\|f_{1}(X_{1})-f_{1}^{\prime}(X_{1})\right\|_{2}^{2}]\right)$

which extends naturally to

$\textup{{KL}}(X\|Y)=\frac{1}{2}\sum_{i=0}^{n-1}\operatorname*{\mathbb{E}}[\left\|f_{i}(X_{i})-f_{i}^{\prime}(X_{i})\right\|_{2}^{2}].$

An SDE is just the limiting continuous version of this, with Brownian motion
$\operatorname{d}\\!{B}_{t}$ being an infinitessimal Gaussian, leading to the
same bound except replacing the sum by an integral. So if we ran the backwards
SDE (3) with incorrect score functions $s^{\prime}_{t}$, up to measurability
issues we would have a process $X^{\prime}$ satisfying

$\displaystyle\textup{{KL}}(X\|X^{\prime})=\int_{0}^{T}\frac{1}{4}\operatorname*{\mathbb{E}}_{X_{t}}[\left\|s_{t}(X_{t})-s^{\prime}_{t}(X_{t})\right\|_{2}^{2}].$
(6)

To discretize (3), we start at $t_{0}=T$ and work our way down a series of
time stamps $T=t_{0}>t_{1}>\dotsb>t_{N}=\Theta(\gamma)$, having step size
$h_{k}=t_{k}-t_{k+1}$. Then given $X_{t_{k}}$, we compute $X_{t_{k+1}}$ by
following the SDE

$\displaystyle
X_{t}=-(X_{t}+2s_{t_{k}}(X_{t_{k}}))\operatorname{d}\\!{t}+\sqrt{2}\operatorname{d}\\!{B}_{t}$
(7)

from $t_{k}$ down to $t_{k+1}$. This is easy to solve in closed form. Let $Q$
be the distribution of $X$ under the true reverse process (3), and $P$ be the
one under the discrete approximation (7). Then, analogous to (6), we have

$\displaystyle\textup{{KL}}(Q\|P)=\operatorname*{\mathbb{E}}_{X\sim
Q}\left[\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\left\|s_{t}(X_{t})-s_{t_{k}}(X_{t_{k}})\right\|^{2}\right]\operatorname{d}\\!{t}.$
(8)

Error in the estimates $\widehat{s}_{t_{k}}$ of $s_{t_{k}}$ are then easy to
handle with the triangle inequality. This bound (8) is the basis for chen,
which shows it formally using Girsanov’s theorem.

#### Bounding the discretization error.

Per the above argument, we just need to bound

$\left\|s_{t}(X_{t})-s_{t_{k}}(X_{t_{k}})\right\|^{2}$

in expectation (or, if preferred, with high probability) over $X_{t}$ and
$X_{t_{k}}$ drawn from the _true_ process $Q$. In chen, this is done with the
decomposition

$\|s_{t}(X_{t})-{s}_{t_{k}}(X_{t_{k}})\|_{2}^{2}\lesssim\|s_{t}(X_{t})-{s}_{t}(X_{t_{k}})\|_{2}^{2}+\|s_{t}(X_{t_{k}})-{s}_{t_{k}}(X_{t_{k}})\|_{2}^{2}.$
(9)

The problem is that this decomposition is actually quite bad when $X$ is
large: for a small step size $h$, considering the forward process (2),
$X_{t+h}-X_{t}\approx hX_{t}+N(0,2h)$. So even if $s_{t}$ is Lipschitz, the
RHS of (9) involves an $O(hX_{t})$ term. If $q$ has second moment $m_{2}\gg
1$, this will force step sizes $h<1/m_{2}$ and hence $\Omega(m_{2})$
iterations. We want a logarithmic dependence on $m_{2}$.

Our observation is that the drift term $-X_{t}\operatorname{d}\\!{t}$ should
not have so much impact on the discretization error, since $X_{t}$ and $s_{t}$
drift at the same pace during the process. Let us look at the following
example. Instead of considering the original diffusion process, we consider
the process of

$\operatorname{d}\\!{X}_{t}=-X_{t}\operatorname{d}\\!{t},\quad X_{0}\sim q.$

In this scenario, we have $X_{t}=e^{-t}X_{0}$. Assuming $X_{t}\sim q_{t}$, we
have $q_{t}(x)=e^{t}q(e^{t}x)$, and consequently,

$s_{t}(X)=\nabla\log(e^{t}q(e^{t}X))=e^{t}s(e^{t}X).$

For a specific $t\in[t_{k}-h,t_{k}]$, if we define $\alpha$ to be
$e^{t_{k}-t}$, we have $X_{t}=\alpha X_{t_{k}}$ and

$s_{t_{k}}(X_{t_{k}})=e^{t_{k}}s_{t}(e^{t_{k}}X_{t_{k}})=\alpha s_{t}(\alpha
X_{t_{k}})=\alpha s_{t}(X_{t}),$

or

$\left\|s_{t}(X_{t})-s_{t_{k}}(X_{t_{k}})\right\|\leq
h\left\|s_{t}(X_{t})\right\|.$

That is, in this example the error is proportional to
$\left\|s_{t}(X_{t})\right\|$ rather than $\left\|X_{t}\right\|$. And because
$X_{t}$ is drawn from a smoothed distribution, $\left\|s_{t}(X_{t})\right\|$
is bounded with high probability (per the argument using (4)).

This shows that drifting itself does not necessarily introduce large error,
and motivates a different decomposition:

$\displaystyle\|s_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\|^{2}$
$\displaystyle\lesssim\|\alpha s_{t}(\alpha
X_{t_{k}})-s_{t}(X_{t})\|^{2}+\|s_{t_{k}}(X_{t_{k}})-\alpha s_{t}(\alpha
X_{t_{k}})\|^{2}$ (10)

for $\alpha=e^{t_{k}-t}$ as before.

As illustrated by the previous example, when the
$-X_{t}\operatorname{d}\\!{t}$ drift term is much larger than the other terms,
we will have $X_{t}\approx\alpha X_{t_{k}}$ and $s_{t_{k}}(x)\approx\alpha
s_{t}(\alpha x)$. Therefore this decomposition, unlike (9), can still be small
for large $X_{t}$.

We bound the first term by showing that $s_{t}$ is with high probability
Lipschitz in a small neighborhood about $X_{t}$ (essentially (5), but in high
dimensions and uniformly over $t\in[t_{k+1},t_{k}]$; this is Lemma E.1). That
this only holds for a small neighborhood is another reason to prefer (10) over
(9), since $\alpha X_{t_{k}}\sim X_{t}+\sqrt{\alpha^{2}-1}N(0,I_{d})$ lies in
a small neighborhood around $X_{t}$, but $X_{t_{k}}$ does not.

We bound the second term with another, similar argument. The change from
$X_{t_{k}}$ to $\alpha X_{t_{k}}$ is the expected drift term, so we just need
to show that an $r$-smoothed score and $(r-\varepsilon)$-smoothed score are
very similar at the _same_ position $x$, with high probability over $x$, and
uniformly over $0\leq\varepsilon\leq h$; this is Corollary F.2.

#### Quantitative intuition.

For a quantitative bound, consider the one-dimensional setting. Then (5) gives
that $s_{t}$ is about $\widetilde{O}(\frac{1}{\sigma^{2}})$-Lipschitz, where
$\sigma^{2}=(1-e^{-2t})$ is the smoothing variance of $X_{t}$. On the other
hand, $\alpha X_{t_{k}}-X_{t}\sim N(0,\alpha^{2}-1)\approx N(0,2h)$ usually
has $\left|\alpha X_{t_{k}}-X_{t}\right|\lesssim\sqrt{h}$. Thus we expect

$\displaystyle\left\|\alpha s_{t}(\alpha X_{t_{k}})-s_{t}(X_{t})\right\|$
$\displaystyle\lesssim h\left\|s_{t}(\alpha
x_{t_{k}})\right\|+\left\|s_{t}(\alpha X_{t_{k}})-s_{t}(X_{t})\right\|$
$\displaystyle\lesssim\frac{h}{\sigma}+\frac{\sqrt{h}}{\sigma^{2}}.$

If we ignore the other term in (10), this would give by (8) that

$\displaystyle\textup{{KL}}(Q\|P)$
$\displaystyle\approx\sum_{i=0}^{N-1}h\left(\frac{h}{\sigma}+\frac{\sqrt{h}}{\sigma^{2}}\right)^{2}$
$\displaystyle\eqsim\sum_{i=0}^{N-1}\frac{h^{3}}{\sigma^{2}}+\frac{h^{2}}{\sigma^{4}}.$

Setting $h=\varepsilon\sigma^{2}$, which is less than $1$, will make all these
terms equal at $\Theta(\varepsilon^{2})$, so

$\textup{{KL}}(Q\|P)\approx N\varepsilon^{2}.$

#### Step sizing.

To make step sizes $h_{k}=\varepsilon\sigma^{2}=\varepsilon(1-e^{-2t_{k}})$,
we have $h_{k}=\varepsilon\Theta(\min(1,t_{k}))$. Thus it will take
$\Theta(\frac{T}{\varepsilon})$ steps to go from $T$ down to $1$, then another
$\varepsilon\log\frac{1}{\gamma}$ steps to reach $\gamma$. That is, we will
set

$h_{k}=(1-e^{-2t_{k}})\frac{T+\log\frac{1}{\gamma}}{N}$

to go from $T$ down to $\Theta(\gamma)$ in $N$ steps. The accuracy is then

$\textup{{KL}}(Q\|P)\approx\frac{T+\log\frac{1}{\gamma}}{N}$

or a TV error that is the square root of this. The above argument is for
$d=1$; higher $d$ loses a polynomial factor in $d$.

###  2.2 Score Estimation

We would like to show that the empirical minimizer of (1) is with high
probability close to the optimal score. For the purposes of this overview, we
consider the $1$ dimensional setting. A natural approach would be to show that
(1) concentrates with high probability. This is the approach taken by BMR20,
with a dependence on the radius $R$ to get an $L_{2}$ error bound on the
result.

Using smoothness properties, we can try to replace $R$ by the smoothing radius
$r$. For the _true_ score $s^{*}$, we have (per the discussion after (4)) that
$s^{*}_{r}(x+z)$ is subgaussian as a distribution over $x+z$; this ensures
that (1) is subgamma and concentrates well. However, this does not work for
candidate scores $s^{\prime}\neq s^{*}$. Each $s^{\prime}(x)$ would be
subgaussian for samples $x$ drawn from the corresponding distribution, but it
is not necessarily well-behaved for $x\sim q$.

In fact, this is a real issue: one can construct examples where the empirical
optimizer of (1) does _not_ perform well in $L_{2}$. Consider two
distributions, $q^{\prime}=\delta_{0}$ and
$q=(1-\frac{1}{n^{2}})\delta_{0}+\frac{1}{n^{2}}\delta_{n^{9}}$. These two
distributions are close in TV and indistinguishable from $n$ samples, but

$\operatorname*{\mathbb{E}}_{x\sim q}[(s^{\prime}(x)-s(x))^{2}]\approx
n^{7}\gg 1.$

Thus on input distribution $q$, the empirical minimizer might well output
$s^{\prime}$ rather than $s$ and have very bad $L_{2}$ error. (Such an issue
does not occur in BMR20, due to the boundedness.)

To fix this, we need to relax our guarantee from a bound in $L_{2}$: we will
instead return a distribution that is $\varepsilon/r$-close with probability
$\delta$, given $\operatorname{poly}(\frac{1}{\varepsilon\delta})$ samples.
(For this reason, our sampling procedure is analyzed to tolerate this kind of
error in the score.)

With this goal in mind, rather than directly concentrate (1) for each score
$s$, we instead concentrate the _difference_ , which (for $\sigma=1$ and
$y:=x+z$) is

difference
$\displaystyle=\left\|s(y)+z\right\|^{2}-\left\|s^{*}(y)+z\right\|^{2}$
$\displaystyle=\left\|s(y)-s^{*}(y)\right\|^{2}+2(z+s^{*}(y))(s(y)-s^{*}(y))$
$\displaystyle=\left\|s(y)-s^{*}(y)\right\|^{2}+2(z-\operatorname*{\mathbb{E}}[z\mid
y])(s(y)-s^{*}(y)).$

The second term is zero in expectation over $(z\mid y)$, showing that indeed
$s^{*}$ minimizes the expectation of (1). Just using the fact that $(y,z)$ are
jointly distributed with $z$ having Gaussian marginal, and no other properties
of the score, we show that this difference is large with high probability
(Lemma B.2) whenever $s-s^{*}$ has a decent probability of being large. The
idea is: because $z$ is gaussian, $z-\operatorname*{\mathbb{E}}[z\mid y]$ is
essentially bounded. Therefore if $\left\|s(y)-s^{*}(y)\right\|^{2}$ is large,
then the difference will be large; and if it is not large, then the difference
is bounded and hence has subgaussian concentration.

##  3 Experiments

To evaluate our proposed step sizes, we run two sets of experiments. The first
is a synthetic experiment, on a mixture of two 1-dimensional Gaussians,
$q=\frac{1}{2}N(-R,\rho^{2})+\frac{1}{2}N(R,\rho^{2})$, for
$R=0.5,\sigma=0.01$. Here, we show a comparison of the algorithm using our
recommended step sizes as well as a constant and linear step size schedule. At
smoothing $\sigma$, the score of this distribution can be written as

$s_{\sigma}(q)=\frac{-(x+R)e^{-(x+R)^{2}/2(\rho^{2}+\sigma^{2})}-(x-R)e^{-(x-R)^{2}/2(\rho^{2}+\sigma^{2})}}{e^{-(x+R)^{2}/2(\rho^{2}+\sigma^{2})}+e^{-(x-R)^{2}/2(\rho^{2}+\sigma^{2})}}.$

At $\sigma=0$, this can be shown to have Lipschitz constant proportional to
$R^{2}/\rho^{2}$. So, if we were to follow a constant step size, as in chen,
we would need to make sure our step size is small enough to be proportional to
$\rho^{2}/R^{2}$ in order to satisfy the theoretical assumptions. However,
this large Lipschitzness only appears in very low-density areas of the
distribution (around $x=0$), where we will almost never be sampling from.

However, as noted before, we can use the fact that at smoothing $\sigma$, our
distribution is at most $1/\sigma^{2}$ Lipschitz with high probability. This
effectively means we ignore any samples that occur in the low probability and
high Lipschitz regions of our distribution.

From a practical perspective, we don’t need to set the constant and linear
step size schedules to match the $\rho^{2}/R^{2}$ bound that results from
weaker analysis. However, there is still a trade-off between accuracy and
iteration count. A smaller step size will always increase iteration counts,
but if the steps we take are too large, the reverse algorithm doesn’t spend
enough time in the region where $t$ is small, and therefore is unable to
accurately converge to the correct distribution. Our step sizes somewhat avoid
this tradeoff by taking bigger steps when $t$ is large and the distribution
allows bigger steps, and taking increasingly smaller steps as time approaches
$0$ to fine-tune the final, more delicate distribution. This tradeoff, as well
as the relative performances of the choices of step sizes, are shown in Figure
1.

Figure 1: Simulation of the reverse process with the original distribution
being an even mixture of Gaussians, shown on the left. On the right, we see
the convergence of the reverse processes with various step size schedules. The
red line shows our proposed step sizes, the green represents linearly
increasing step sizes, and the orange shows a constant step size. The
transparent lines represent different larger scalings of the step sizes, which
don’t converge as well, but terminate faster.

For the second experiment, we use our step sizes to create a sampler for
Stable Diffusion Rombach_2022_CVPR. We match the value of $T$ used by the
existing implementation of DDPM, and set our step sizes proportional to
$\varepsilon(1-e^{-2t})$, for some parameter $\varepsilon$ which controls the
total iteration count. Then, using the pre-trained model from Stable
Diffusion, we iterate our sampler to generate images given a prompt. Figure
LABEL:fig:our_stable_diffusion shows the performance of our recommended step
sizes, and Figure LABEL:fig:ddpm_stable_diffusion shows the performance of the
existing DDPM sampler with the same number of samples. These experiments were
run on a single NVIDIA A40.

It’s clear that our sampling converges much faster than DDPM. Even with only
$N=10$ iterations, we are able to see a clear picture that represents the
prompt. DDPM, however, needs a few hundred steps to converge to an acceptable
image. There are other sampling methods (lu2022dpmsolver,
karras2022elucidating) that achieve even better iteration complexity, but our
method has the advantage of having theoretical guarantees, and is also just a
simple modification to the original DDPM algorithm.

##  4 Future Work

Diffusion models are a very exciting area, and there are many potential
directions for future research. Obtaining tight upper and lower bounds for the
problem of sampling from a distribution assuming access to accurate estimates
of scores is one direction that we hope to pursue in the future.

In addition, we hope to perform more extensive experiments using our step
size, and to see if our techniques when combined with empirically studied
ideas result in faster sampling in practice. We are also interested in
studying whether some of these empirical techniques song2021denoising;
improved_denoising; karras2022elucidating can be understood better via
theoretical analysis. More generally, we are interested in exploring whether
theoretical analyses of this problem can lead to improvements in practice.

##  Appendix A Proofs for Sampling

###  A.1 Notations

We consider the stochastic process

$\operatorname{d}\\!{X}_{t}=-X_{t}\operatorname{d}\\!{t}+\sqrt{2}\operatorname{d}\\!{B}_{t}.$

Let $X_{0}\sim q_{0}$, where $q_{0}$ is an arbitrary $d$-dimensional
distribution. Then

$X_{t}\sim e^{-t}X_{0}+\sqrt{1-e^{-2t}}N(0,I_{d}).$

In the algorithm of the reverse process, we have the time $t$ run from $T$
towards 0. The process is discretized into $N$ phases, and we denote the
ending time of the $k$-th phase by $t_{k}$. Specifically, we have $0\leq
t_{N}<t_{N-1}<\dots<t_{0}=T$. The algorithm stops at $t_{N}$ and outputs
$X_{t_{N}}$. Let $q_{t}$ be the pdf of $X_{t}$. For $k\in\\{0,\dots,N-1\\}$,
we define $h_{k}:=t_{k}-t_{k+1}$.

We consider three measures over the path space
$\mathcal{C}((0,T];\mathbb{R}^{d})$.

  * •

$Q$, under which $(X_{t})_{t\in(0,T]}$ has the law of the perfect reverse
process initialized at $q_{T}$ and uses the true score.

  * •

$P^{q_{T}}$, under which $(X_{t})_{t\in(0,T]}$ has the law of the discretized
algorithm initialized at $q_{T}$ and uses the empirical score.

  * •

$P$, under which $(X_{t})_{t\in(0,T]}$ has the law of the discretized
algorithm initialized at $N(0,I_{d})$ and uses the empirical score.

In short, $Q$ represents the perfect reverse process, and $P$ represents the
actual reverse process we can implement. The key part of our proof for
sampling is to bound the distance between $Q$ and $P$.

###  A.2 Process discretization bound

######  Lemma A.1.

If we start at $t_{0}=T$ and iteratively assign step sizes as
$h_{k}=(1-e^{-2t_{k}})(T+\log\frac{1}{\gamma})/N$ for each step, then we have

$\gamma\lesssim t_{N}\leq\gamma.$

###### Proof.

Note that

$N=\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\frac{\operatorname{d}\\!{t}}{h_{k}}=\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\frac{N}{(T+\log\frac{1}{\gamma})(1-e^{-2t_{k}})}\operatorname{d}\\!{t}.$

Given that

$\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\frac{N}{(T+\log\frac{1}{\gamma})(1-e^{-2t_{k}})}\operatorname{d}\\!{t}\leq\int_{t_{N}}^{T}\frac{N}{(T+\log\frac{1}{\gamma})(1-e^{-2t})}\operatorname{d}\\!{t}\leq\frac{N(T+\log\frac{1}{t_{N}})}{T+\log\frac{1}{\gamma}},$

it follows that $t_{N}\leq\gamma$. Moreover, since

$\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\frac{N}{(T+\log\frac{1}{\gamma})(1-e^{-2t_{k}})}\operatorname{d}\\!{t}\gtrsim\int_{t_{N}}^{T}\frac{N}{(T+\log\frac{1}{\gamma})(1-e^{-2t})}\operatorname{d}\\!{t}\gtrsim\frac{N(T+\log\frac{1}{t_{N}})}{T+\log\frac{1}{\gamma}},$

we have $t_{N}\gtrsim\gamma$. ∎

######  Theorem A.2.

Let $0<\gamma<1$. For any integer $N$ satisfying

$N\geq
C\left(T+\log\frac{1}{\gamma}\right)\left(d+\log\frac{N}{\delta}\right)^{3},$

where $C$ is a large enough constant. If we iteratively assign step sizes as
$h_{k}=(1-e^{-2t_{k}})(T+\log\frac{1}{\gamma})/N$ for each step, then with
probability $1-\delta$ over the forward process,

$\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\left\|s_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|_{2}^{2}\operatorname{d}\\!{t}\lesssim\frac{(T+\log\frac{1}{\gamma})^{2}(d+\log\frac{N}{\delta})^{3}}{N}.$

###### Proof.

By applying theorem C.1 with setting $\varepsilon$ to be
$\frac{C(T+\log\frac{1}{\gamma})(d+\log\frac{N}{\delta})^{3}}{N}<1$ and
$\delta$ to be $\frac{\delta}{N}$, for each $k\in\\{0,\dots,N-1\\}$, with
probability $1-\frac{\delta}{N}$ we have for all $t\in[t_{k+1},t_{k}]$,

$\left\|s_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|_{2}^{2}\lesssim\frac{(T+\log\frac{1}{\gamma})(d+\log\frac{N}{\delta})^{3}}{N(1-e^{-2t_{k}})}.$

By taking a union bound over all steps, we get that with probability
$1-\delta$ over the forward process,

$\displaystyle\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}{\left\|s_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|^{2}}\operatorname{d}\\!{t}$
$\displaystyle\lesssim\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\frac{(T+\log\frac{1}{\gamma})(d+\log\frac{N}{\delta})^{3}}{N(1-e^{-2t_{k}})}\operatorname{d}\\!{t}$
$\displaystyle\lesssim\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\frac{(T+\log\frac{1}{\gamma})(d+\log\frac{N}{\delta})^{3}}{N(1-e^{-2t})}\operatorname{d}\\!{t}$
$\displaystyle=\int_{t_{N}}^{T}\frac{(T+\log\frac{1}{\gamma})(d+\log\frac{N}{\delta})^{3}}{N(1-e^{-2t})}\operatorname{d}\\!{t}.$

According to lemma A.1, we have $\gamma\lesssim t_{N}$. Hence,

$\int_{t_{N}}^{T}\frac{(T+\log\frac{1}{\gamma})(d+\log\frac{N}{\delta})^{3}}{N(1-e^{-2t})}\operatorname{d}\\!{t}\lesssim\frac{(T+\log\frac{1}{\gamma})^{2}(d+\log\frac{N}{\delta})^{3}}{N}$

and finishes the proof. ∎

######  Theorem A.3 (Girsanov).

For $t\in[0,T]$, let
$\mathcal{L}_{t}=\int_{0}^{t}b_{s}\operatorname{d}\\!{B}_{s}$ where $B$ is a
$Q$-Brownian motion. If the Novikov’s condition

$\operatorname*{\mathbb{E}}_{Q}\left[\exp\left(\frac{1}{2}\int_{0}^{T}\|b_{s}\|_{2}^{2}\operatorname{d}\\!{s}\right)\right]<\infty$

is satisfied, then

$\mathcal{E(L)}_{t}:=\exp\left(\int_{0}^{t}b_{s}\operatorname{d}\\!{B}_{s}-\frac{1}{2}\int_{0}^{t}\|b_{s}\|_{2}^{2}\operatorname{d}\\!{s}\right)$

is a $Q$-martingale and

$\widetilde{B}_{t}:=B_{t}-\int_{0}^{t}b_{s}\operatorname{d}\\!{s}$

is a Brownian motion under $P$ where $P:=\mathcal{E(L)}_{T}Q$, the probability
distribution with density $\mathcal{E(L)}_{T}$ w.r.t. Q.

######  Lemma A.4.

If we have

$\operatorname{\mathbb{P}}_{Q}\left[\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\left\|s_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|_{2}^{2}\operatorname{d}\\!{t}\leq\varepsilon^{2}\right]\geq
1-\delta_{1},$

and there exists an event $E$ with probability at least $1-\delta_{2}$ such
that

$\operatorname*{\mathbb{E}}_{Q}\left[\sum_{k=0}^{N-1}\left(\left\|s_{t_{k}}(X_{t_{k}})-\widehat{s}_{t_{k}}(X_{t_{k}})\right\|_{2}^{2}(t_{k}-t_{k+1})\right)\
\middle|\ E\right]\leq\varepsilon_{score}^{2},$

then

$\textup{{{TV}}}(Q,P^{q_{T}})\leq\delta_{1}+\delta_{2}+O(\varepsilon)+O(\varepsilon_{score}).$

###### Proof.

For any $\eta>0$, consider event

$E_{\eta}:=\left(\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\left\|\widehat{s}_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|_{2}^{2}\operatorname{d}\\!{t}\leq\eta\right).$

Let $\eta^{\prime}\in[0,+\infty]$ be the minimum number such that

$\operatorname{\mathbb{P}}_{Q}\left[E_{\eta}\right]\geq
1-2\delta_{1}-2\delta_{2}.$

Note that $\eta^{\prime}$ always exists since
$\operatorname{\mathbb{P}}_{Q}\left[E_{\eta}\right]$ is right-continuous with
respect to $\eta$. We claim that under the assumptions given in the lemma,

$\eta^{\prime}\lesssim\frac{\varepsilon^{2}+\varepsilon_{score}^{2}}{\delta_{1}+\delta_{2}}\quad\text{and}\quad\operatorname*{\mathbb{E}}_{Q}\left[\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\left\|\widehat{s}_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|_{2}^{2}\operatorname{d}\\!{t}\
\middle|\
E_{\eta^{\prime}}\right]\lesssim\varepsilon^{2}+\varepsilon_{score}^{2}.$ (11)

We defer its proof to the end. Now for every $t\in(t_{N},T]$, consider event

$E(t):=\left(\sum_{i=0}^{k-1}\int_{t_{i+1}}^{t_{i}}\|s_{r}(X_{r})-\widehat{s}_{t_{i}}(X_{t_{i}})\|_{2}^{2}\operatorname{d}\\!{r}+\int_{t}^{t_{k}}\|s_{r}(X_{r})-\widehat{s}_{t_{k}}(X_{t_{k}})\|_{2}^{2}\operatorname{d}\\!{r}\leq\eta^{\prime}\right),$

where $k$ is the index such that $t\in(t_{k+1},t_{k}]$. $E(t)$ represents the
property that if we walk along the path using the empirical discretized score
from $T$ to $t$, the accumulated error of the drifting term is less than
$\varepsilon+\varepsilon_{score}$.

Using $E(t)$, we could define measure $Q^{\prime}$ over
$\mathcal{C}((0,T],\mathbb{R}^{d})$ as the law of a modified reverse process
initialized at $X_{T}\sim q_{T}$, and

$\operatorname{d}\\!{X}_{t}=-\left(X_{t}+2\widetilde{s}_{t}(X_{t})\right)dt+\sqrt{2}dB_{t},$
(12)

where for each $t\in(t_{k+1},t_{k}]$,

$\widetilde{s}_{t}(X_{t}):=\widehat{s}_{t_{k}}(X_{t_{k}})+\mathbf{1}_{E(t)}\cdot(s_{t}(X_{t})-\widehat{s}_{t_{k}}(X_{t_{k}})).$

We could think of $Q^{\prime}$ as a version of $Q$ with bounded accumulated
score difference from the discretized empirical score. The definition of
$Q^{\prime}$ guarantees that once the accumulated error exceeds
$\eta^{\prime}$, we switch from the true score to discretized empirical score.
Hence, the accumulated error is always maintained within $\eta^{\prime}$. This
implies that $Q^{\prime}(E_{\eta^{\prime}})=1$. Moreover, since we have
“manipulated” each discretized empirical path that doesn’t meet
$E_{\eta^{\prime}}$ into satisfying $E_{\eta}$, it follows that for any event
$E_{sub}\subseteq E_{\eta^{\prime}}$ , $Q^{\prime}(E_{sub})\geq Q(E_{sub})$.
Combining these two facts and we get

$\textup{{TV}}(Q,Q^{\prime})\leq 1-Q(E_{\eta^{\prime}})\leq
2\delta_{1}+2\delta_{2}.$

In addition, using (11) we have

Define

$b_{r}:=\sqrt{2}(\widetilde{s}_{r}(X_{r})-\widehat{s}_{t_{k}}(X_{t_{k}})),$

where $k$ is index such that $r\in[t_{k+1},t_{k}]$. We apply the Girsanov’s
theorem to $(Q^{\prime},(b_{r}))$. By the definition of $\widetilde{s}_{t}$,
we have

$\int_{t_{N}}^{T}\|\sqrt{2}(\widetilde{s}_{t}(X_{t})-\widehat{s}_{t_{k}}(X_{t_{k}}))\|_{2}^{2}\operatorname{d}\\!{t}\leq\eta^{\prime}<\infty.$

This satisfies Novikov’s condition and tells us that for

$\mathcal{E(L)}_{t}=\exp\left(\int_{T}^{t}{\sqrt{2}(\widetilde{s}_{r}(X_{r})-\widehat{s}_{t_{k}}(X_{t_{k}}))}\operatorname{d}\\!{B}_{r}-\frac{1}{2}\int_{T}^{t}\left\|\sqrt{2}(\widetilde{s}_{r}(X_{r})-\widehat{s}_{t_{k}}(X_{t_{k}}))\right\|_{2}^{2}\operatorname{d}\\!{r}\right),$

under measure $P^{\prime}:=\mathcal{E(L)}_{T}Q^{\prime}$, there exists a
Brownian motion $(\widetilde{B}_{t})_{t\in[t_{N},T]}$ such that

$\widetilde{B}_{t}=B_{t}-\int_{T}^{t}\sqrt{2}(\widetilde{s}_{r}(X_{r})-\widehat{s}_{t_{k}}(X_{t_{k}}))\operatorname{d}\\!{r},$

and thus

$\mathrm{d}\widetilde{B}_{t}=\operatorname{d}\\!{B}_{t}+\sqrt{2}(\widetilde{s}_{t}(X_{t})-\widehat{s}_{t_{k}}(X_{t_{k}}))\operatorname{d}\\!{t}.$

Plug this into $(\ref{eq:Q'})$ and we have that

$\operatorname{d}\\!{X}_{t}=-\left(X_{t}+2\widehat{s}_{t_{k}}(X_{t_{k}})\right)dt+\sqrt{2}\operatorname{d}\\!{\widetilde{B}_{t}},\quad
X_{T}\sim q_{T}.$

This equation depicts the distribution of $X$, and this exactly matches the
definition of $P^{q_{T}}$. Therefore,
$P^{q_{T}}=P^{\prime}=\mathcal{E(L)}_{T}Q^{\prime}$, and we have

$\textup{{KL}}\left(Q^{\prime}\middle\|P^{q_{T}}\right)=\operatorname*{\mathbb{E}}_{Q^{\prime}}\left[\ln\frac{\operatorname{d}\\!{Q}^{\prime}}{\operatorname{d}\\!{P}^{q_{T}}}\right]=\operatorname*{\mathbb{E}}_{Q^{\prime}}\left[\ln\mathcal{E(L)}_{t_{N}}\right]\lesssim\varepsilon^{2}+\varepsilon_{score}^{2}.$

Applying Pinsker’s inequality, we have

$\textup{{TV}}(Q^{\prime},P^{q_{T}})\leq\sqrt{\textup{{KL}}\left(Q^{\prime}\middle\|P^{q_{T}}\right)}\lesssim\varepsilon+\varepsilon_{score}.$

Combining with the fact that $\textup{{TV}}(Q,Q^{\prime})=\delta$, we conclude

$\textup{{TV}}(Q,P^{q_{T}})\leq\textup{{TV}}(Q,Q^{\prime})+\textup{{TV}}(Q^{\prime},P^{q_{T}})\leq\delta_{1}+\delta_{2}+O(\varepsilon)+O(\varepsilon_{score}).$

#### Proving (11).

Let $E^{\prime}$ be the event defined on $\mathcal{C}((0,T],\mathbb{R}^{d})$
such that

$E^{\prime}:=E\cap\left(\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\left\|s_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|_{2}^{2}\operatorname{d}\\!{t}\leq\varepsilon^{2}\right).$

Then we have

Applying a union bound on the assumptions, we have
$\operatorname{\mathbb{P}}_{Q}\left[E^{\prime}\right]\geq
1-\delta_{1}-\delta_{2}$.

Recall that $\eta^{\prime}$ is the minimum number that satisfies
$\operatorname{\mathbb{P}}_{Q}\left[E_{\eta}\right]\geq
1-2\delta_{1}-2\delta_{2}$, so we have for any $\varepsilon^{\prime}>0$,
$\operatorname{\mathbb{P}}_{Q}\left[E_{\eta^{\prime}-\varepsilon^{\prime}}\right]<1-2\delta_{1}-2\delta_{2}$.
Therefore,

$\operatorname{\mathbb{P}}_{Q}\left[\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\left\|\widehat{s}_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|_{2}^{2}\operatorname{d}\\!{t}\geq\eta^{\prime}\right]>2\delta_{1}+2\delta_{2}.$

Since $E^{\prime}$ has probability at least $1-\delta_{1}-\delta_{2}$, we know
that

$\operatorname{\mathbb{P}}_{Q}\left[\left(\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\left\|\widehat{s}_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|_{2}^{2}\operatorname{d}\\!{t}\geq\eta^{\prime}\right)\cap
E^{\prime}\right]\geq\delta_{1}+\delta_{2}.$

Multiplying $\eta^{\prime}$ on both sides and we have

$\eta^{\prime}(\delta_{1}+\delta_{2})\leq\operatorname*{\mathbb{E}}_{Q}\left[\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\left\|\widehat{s}_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|_{2}^{2}\operatorname{d}\\!{t}\
\middle|\ E^{\prime}\right]\lesssim\varepsilon^{2}+\varepsilon_{score}^{2}.$

This proves
$\eta^{\prime}\lesssim(\varepsilon^{2}+\varepsilon_{score}^{2})/(\delta_{1}+\delta_{2})$.
Then, by lemma G.6, we have

$\operatorname*{\mathbb{E}}_{Q}\left[\sum_{k=0}^{N-1}\int_{t_{k+1}}^{t_{k}}\left\|\widehat{s}_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\right\|_{2}^{2}\operatorname{d}\\!{t}\
\middle|\
E_{\eta^{\prime}}\right]\lesssim\varepsilon^{2}+\varepsilon_{score}^{2}.$

∎

######  Lemma A.5.

$W_{2}(q,q_{\gamma})\leq\gamma m_{2}+\sqrt{2\gamma}$, where $W_{2}$ denotes
the Wasserstein 2-distance.

###### Proof.

Since $q_{\gamma}=e^{-\gamma}q+\sqrt{1-e^{-2\gamma}}N(0,I_{d})$, we have

$W_{2}(q,q_{\gamma})\leq
W_{2}(q,e^{-\gamma}q)+W_{2}(e^{-\gamma}q,q_{\gamma})\leq(1-e^{-\gamma})m_{2}+\sqrt{1-e^{-2\gamma}}\leq\gamma
m_{2}+\sqrt{2\gamma},$

where $m_{2}$ represents the square root of the second moment of $q$. ∎

######  Lemma A.6.

Suppose $q$ has a second moment of $m_{2}^{2}$. Then, for $T\geq 1$ we have

$\textup{{TV}}(q_{T},N(0,I_{d}))\lesssim e^{-T}m_{2}$

###### Proof.

We define $p=N(0,I_{d})$, $p_{T}=N(0,(1-e^{-2T})I_{d})$, and $r=e^{-T}q$.
Since $q_{T}$ is the convolution of $p_{T}$ and $r$, we have

$q_{T}(x)=\int r(z)\cdot p_{T}({x-z})\operatorname{d}\\!{z}.$

Therefore,

$\displaystyle\textup{{TV}}(q_{T},p)$
$\displaystyle=\frac{1}{2}\int\left|q_{T}(x)-p(x)\right|\operatorname{d}\\!{x}$
$\displaystyle=\frac{1}{2}\int\left|\int r(z)\cdot
p_{T}({x-z})\operatorname{d}\\!{z}-p(x)\right|\operatorname{d}\\!{x}$
$\displaystyle=\frac{1}{2}\int\left|\int
r(z)\cdot\left(p_{T}({x-z})-p(x)\right)\operatorname{d}\\!{z}\right|\operatorname{d}\\!{x}$
$\displaystyle\leq\frac{1}{2}\int\int
r(z)\cdot\left|p_{T}({x-z})-p(x)\right|\operatorname{d}\\!{z}\operatorname{d}\\!{x}$
$\displaystyle\leq\frac{1}{2}\int\left(\int\left|p_{T}({x-z})-p(x)\right|\operatorname{d}\\!{x}\right)\cdot
r(z)\operatorname{d}\\!{z}.$

To bound $\int\left|p({x-z})-p(x)\right|\operatorname{d}\\!{x}$ for a fixed
$z$, we use the Pinsker’s inequality:

$\displaystyle\int\left|p_{T}({x-z})-p(x)\right|\operatorname{d}\\!{x}$
$\displaystyle=2\textup{{TV}}\left(N(z,(1-e^{-2T})I_{d}),N(0,I_{d})\right)$
$\displaystyle\leq 2\sqrt{\frac{1}{2}\textup{{KL}}\left(N(z,(1-e^{-2T})I_{d})\
\middle\|\ N(0,I_{d})\right)}$
$\displaystyle\leq\sqrt{\log\frac{1}{1-e^{-2T}}-d+d({1-e^{-2T}})+\left\|z\right\|^{2}}$
$\displaystyle\lesssim\left\|z\right\|$

By plugging this in, we have

$\textup{{TV}}(q_{T},p)\lesssim\operatorname*{\mathbb{E}}_{z\sim
r}\left[\left\|z\right\|\right]\leq\sqrt{\operatorname*{\mathbb{E}}_{z\sim
e^{-T}q}\left[\left\|z\right\|^{2}\right]}\leq
e^{-T}\sqrt{\operatorname*{\mathbb{E}}_{z\sim
q}\left[\left\|z\right\|^{2}\right]}=e^{-T}m_{2}.$

∎

######  Theorem A.7.

Let $0<\gamma<1$. Let $q$ be the original distribution with a second moment of
$m_{2}^{2}$. For any integer $N$ satisfying

$N\geq
C\left(T+\log\frac{1}{\gamma}\right)\left(d+\log\frac{N}{\delta}\right)^{3},$

where $C$ is a large constant. If we have

$\operatorname{\mathbb{P}}_{Q}\left[\sum_{k=0}^{N-1}\left(\left\|s_{t_{k}}(X_{t_{k}})-\widehat{s}_{t_{k}}(X_{t_{k}})\right\|_{2}^{2}(t_{k}-t_{k+1})\right)\leq\varepsilon_{score}^{2}\right]\geq
1-\delta_{score},$

then we can iteratively assign step sizes
$h_{k}=(1-e^{-2t_{k}})(T+\log\frac{1}{\gamma})/N$ to each step, and after $N$
steps DDPM converges to distribution $\widehat{q}$ such that

$\textup{{TV}}(\widehat{q},q_{t_{N}})\lesssim
m_{2}\exp(-T)+\frac{1}{\sqrt{N}}\left(T+\log\frac{1}{\gamma}\right)\left(d+\log\frac{N}{\delta}\right)^{\frac{3}{2}}+\delta+\delta_{score}+\varepsilon_{score},$

where $q_{t_{N}}$ is a distribution satisfying $W_{2}(q_{t_{N}},q)\leq\gamma
m_{2}+\sqrt{2\gamma}$.

###### Proof.

We have

$\textup{{TV}}(p,q_{\gamma})\leq\textup{{TV}}(P,Q)\leq\textup{{TV}}(P,P^{q_{T}})+\textup{{TV}}(P^{q_{T}},Q).$

Using the data processing inequality and lemma A.6, we obtain

$\textup{{TV}}(P,P^{q_{T}})\leq\textup{{TV}}(q_{T},N(0,I_{d}))\lesssim
m_{2}\exp(-T).$

By theorem A.2 and lemma A.4, we find that

$\textup{{TV}}(P^{q_{T}},Q)\lesssim\frac{1}{\sqrt{N}}\left(T+\log\frac{1}{\gamma}\right)\left(d+\log\frac{N}{\delta}\right)^{\frac{3}{2}}+\delta+\delta_{score}+{\varepsilon_{score}}.$

Thus,

$\textup{{TV}}(p,q_{t_{N}})\lesssim
m_{2}\exp(-T)+\frac{1}{\sqrt{N}}\left(T+\log\frac{1}{\gamma}\right)\left(d+\log\frac{N}{\delta}\right)^{\frac{3}{2}}+\delta+\delta_{score}+{\varepsilon_{score}}.$

Taking the bound of $t_{N}$ from lemma A.1 into lemma A.5, we get that

$W_{2}(q_{t_{N}},q)\leq\gamma m_{2}+\sqrt{2\gamma}.$

∎

###### Proof of Theorem 1.1.

By setting $\gamma=\min(\gamma_{0}/{m_{2}},\gamma_{0})$,
$T=\log(m_{2}/\delta)$ in theorem A.7 , when
$N>\widetilde{\Theta}(\frac{d^{3}}{\delta^{2}}\log^{2}\frac{m_{2}}{\gamma_{0}})$,
we have

$\textup{{TV}}(\widehat{q},q_{t_{N}})\lesssim\delta+\delta_{score}+\varepsilon_{score},$

and

$W_{2}(q_{t_{N}},q)\lesssim\gamma_{0}.$

Therefore, when we have the true score access
($\delta_{score}=\varepsilon_{score}=0$), theorem 1.1 holds.

If we have approximate score $\widehat{s}$, and for each $\sigma$, we have

$\operatorname{\mathbb{P}}_{x\sim
q_{\sigma}}[\left\|\widehat{s}_{\sigma}(x)-s_{\sigma}(x)\right\|_{2}>\frac{\delta}{\sigma\sqrt{N}}]\leq\delta/N,$

then we have for each $t_{k}$,

$\operatorname{\mathbb{P}}_{x\sim
q_{\sigma}}[\left\|\widehat{s}_{t_{k}}(x)-s_{t_{k}}(x)\right\|_{2}>\frac{\delta}{\sqrt{1-e^{-2t_{k}}}\sqrt{N}}]\leq\delta/N.$

Applying a union bound over every $t_{k}$, we have with probability at least
$1-\delta$, for every $k\in\\{0,\dots,N-1\\}$,

$\operatorname{\mathbb{P}}_{x\sim
q_{\sigma}}[\left\|\widehat{s}_{t_{k}}(x)-s_{t_{k}}(x)\right\|_{2}>\frac{\delta}{\sqrt{1-e^{-2t_{k}}}\sqrt{N}}]\leq\delta$

Therefore, with probability at least $1-\delta$,

$\sum_{k=0}^{N-1}\left(\left\|\widehat{s}_{t_{k}}(x)-s_{t_{k}}(x)\right\|_{2}^{2}(t_{k}-t_{k-1})\right)\leq\sum_{k=0}^{N-1}\left(\frac{T+\log\frac{1}{\gamma}}{N^{2}}\right)\leq\frac{T+\log\frac{1}{\gamma}}{N}.$

We get that in this scenario, $\delta_{score}=\delta$ and
$\varepsilon_{score}=\sqrt{\frac{T+\log\frac{1}{\gamma}}{N}}\lesssim\delta$.
Hence, $\textup{{TV}}(\widehat{q},q_{t_{N}})\lesssim\delta$ and
$W_{2}(q_{t_{N}},q)\lesssim\gamma_{0}$. Theorem 1.1 still holds. ∎

######  Remark A.8.

We note that the score estimation condition in theorem A.7 could be further
relaxed. It is sufficient to require there exists an event $E$ with
probability at least $1-\delta_{score}$ such that

$\operatorname*{\mathbb{E}}_{Q}\left[\sum_{k=0}^{N-1}\left(\left\|s_{t_{k}}(X_{t_{k}})-\widehat{s}_{t_{k}}(X_{t_{k}})\right\|_{2}^{2}(t_{k}-t_{k+1})\right)\
\middle|\ E\right]\leq\varepsilon_{score}^{2}.$

If this condition is met, it fulfills the requirements of lemma A.4. We could
then use the same proof to get the conclusion of theorem A.7. In other words,
rather than requiring the score error to be uniformly less than
$\varepsilon_{score}^{2}$ with probability $1-\delta_{score}$, we only need
the expected score error to be less than $\varepsilon_{score}^{2}$ after
throwing away $\delta_{score}$ probability.

######  Remark A.9.

We can further optimize the $W_{2}$ error in theorem A.7 by introducing an
additional step to our algorithm: At time $t_{N}$, output $e^{t_{N}}X_{t_{N}}$
instead of $X_{t_{N}}$ itself. We denote $\hat{q}^{\prime}$ as the
distribution for the output. Let $q_{t_{N}}^{\prime}$ to be the distribution
for $e^{t_{N}}X_{t_{N}}$, where $X_{t_{N}}\sim q_{t_{N}}$. Then under the same
condition given in theorem A.7, we could get that the output distribution
$\hat{q}^{\prime}$ satisfies

$\textup{{TV}}(\hat{q}^{\prime},q_{t_{N}}^{\prime})\lesssim
m_{2}\exp(-T)+\frac{1}{\sqrt{N}}\left(T+\log\frac{1}{\gamma}\right)\left(d+\log\frac{N}{\delta}\right)^{\frac{3}{2}}+\delta+\delta_{score}+\varepsilon_{score},$

and $W_{2}(q_{t_{N}}^{\prime},q)\leq
e^{\gamma}\sqrt{2\gamma}\approx\sqrt{2\gamma}$. We can see that after
multiplying $e^{\gamma}$, the TV distance remains the same, while the $W_{2}$
distance gets smaller and no longer depends on the $m_{2}$ of the original
distribution.

##  Appendix B Score estimation

This section analyzes the score-matching objective for arbitrary distributions
and bounded size function classes. Our main result (Theorem
LABEL:thm:scoreestimation) shows that if there is a function in the function
class $\mathcal{H}$ that approximates the score well in our $D_{p}^{\delta}$
sense (see (LABEL:eq:D_p^delta_def)), then the score-matching objective can
learn this function using a number of samples that is independent of the
domain size or the maximum value of the score.

We also show how to obtain a similar bound for the case when the function
class $\mathcal{H}$ is the class of neural networks with bounded weight
(Theorem LABEL:thm:neural_net).

###  B.1 Score Estimation for Fixed Time

#### Notation.

Fix a time $t$. For the purposes of this section, let $q:=q_{t}$ be the
distribution at time $t$, let $\sigma:=\sigma_{t}$ be the smoothing level for
time $t$, and let $s:=s_{t}$ be the score function for time $t$. For $m$
samples $y_{i}\sim q_{0}$ and $z_{i}\sim\mathcal{N}(0,\sigma^{2})$, let
$x_{i}=e^{-t}y_{i}+z_{i}\sim q_{t}$.

We use $\widehat{\operatorname*{\mathbb{E}}}[f(x,y,z)]$ to denote the
empirical expectation $\frac{1}{m}\sum_{i=1}^{m}f(x_{i},y_{i},z_{i})$.

We now state the score matching algorithm.

Algorithm 1 Empirical score estimation for $s$

#### Input:

Distribution $q_{0}$, $y_{1},\dots,y_{m}\sim q_{0}$, set of hypothesis score
function $\mathcal{H}=\\{\tilde{s}_{i}\\}$, smoothing level $\sigma$.

  1. 1.

Take $m$ independent samples $z_{i}\sim N(0,\sigma^{2}I_{d})$, and let
$x_{i}=e^{-t}y_{i}+z_{i}$.

  2. 2.

For each $\tilde{s}\in\mathcal{H}$, let

$l(\tilde{s})=\frac{1}{m}\sum_{i=1}^{m}\left\|\tilde{s}(x_{i})-\frac{-z_{i}}{\sigma^{2}}\right\|_{2}^{2}$

  3. 3.

Let $\hat{s}=\operatorname*{arg\,min}_{\tilde{s}\in\mathcal{H}}l(\tilde{s})$

  4. 4.

Return $\hat{s}$

*

###### Proof.

Per the notation discussion above, we set $s=s_{t}$ and $\sigma=\sigma_{t}$.

Denote

$\displaystyle l(s,x,z):=\left\|s(x)-\frac{-z}{\sigma^{2}}\right\|_{2}^{2}$

We will show that for all $\tilde{s}$ such that
$D^{\delta_{\text{score}}}_{q}(\tilde{s},s)>\varepsilon/\sigma$, with
probability $1-\delta_{\train}$,

$\displaystyle\hat{\operatorname*{\mathbb{E}}}\left[l(\tilde{s},x,z)-l(s^{*},x,z)\right]>0,$

so that the empirical minimizer $\hat{s}$ is guaranteed to have

$D^{\delta_{\text{score}}}_{q}(\hat{s},s)\leq\varepsilon/\sigma.$

We have

$\displaystyle\begin{split}l(\tilde{s},x,z)-l(s^{*},x,z)&=\left\|\tilde{s}(x)-\frac{-z}{\sigma^{2}}\right\|^{2}-\left\|s^{*}(x)-\frac{-z}{\sigma^{2}}\right\|^{2}\\\
&=\left(\left\|\tilde{s}(x)-\frac{-z}{\sigma^{2}}\right\|^{2}-\left\|s(x)-\frac{-z}{\sigma^{2}}\right\|^{2}\right)-\left\|s^{*}(x)-s(x)\right\|^{2}-2\langle
s^{*}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle.\end{split}$ (13)

Note that by Markov’s inequality, with probability $1-\delta_{\train}/3$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}_{x}\left[\|s^{*}(x)-s(x)\|^{2}\right]\leq\frac{\delta_{\text{score}}\cdot\varepsilon^{2}}{30\cdot\sigma^{2}}.$

By Lemma B.1, with probability $1-\delta_{\train}/3$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\langle
s^{*}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle\right]\leq\frac{\delta_{\text{score}}\cdot\varepsilon^{2}}{100\sigma^{2}}$

Also, by Corollary B.3, with probability $1-\delta_{\train}/3$, for all
$\tilde{s}\in\mathcal{H}$ that satisfy
$D^{\delta_{\text{score}}}_{q}(\tilde{s},s)>\varepsilon/\sigma$
simultaneously,

$\displaystyle\hat{\operatorname*{\mathbb{E}}}\left[\left\|\tilde{s}(x)-\frac{-z}{\sigma^{2}}\right\|^{2}-\left\|s(x)-\frac{-z}{\sigma^{2}}\right\|^{2}\right]\geq\frac{\delta_{\text{score}}\varepsilon^{2}}{16\sigma^{2}}.$

Plugging in everything into equation (13), we have, with probability
$1-\delta_{\train}$, for all $\tilde{s}\in\mathcal{H}$ with
$D^{\delta_{\text{score}}}_{q}(\tilde{s},s)>\varepsilon/\sigma$
simultaneously,

$\displaystyle\hat{\operatorname*{\mathbb{E}}}\left[l(\tilde{s},x,z)-l(s^{*},x,z)\right]\geq\frac{\delta_{\text{score}}\varepsilon^{2}}{16\sigma^{2}}-\frac{\delta_{\text{score}}\varepsilon^{2}}{30\sigma^{2}}-\frac{\delta_{\text{score}}\varepsilon^{2}}{50\sigma^{2}}>0$

as required. ∎

######  Lemma B.1.

For any distribution $q_{0}$ and time $t>0$, consider the
$\sigma_{t}$-smoothed version $q_{t}$ with associated score $s_{t}$. Suppose
$s^{*}$ is such that

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
q_{t}}\left[\|s^{*}(x)-s(x)\|^{2}\right]\leq\frac{\delta_{\text{score}}\cdot\delta_{\train}\cdot\varepsilon^{2}}{C\sigma_{t}^{2}}$

for a sufficiently large constant $C$. Then, using $m>\wt
O\left(\frac{1}{\varepsilon^{2}\delta_{\text{score}}}\left(d+\log\frac{1}{\delta_{\train}}\right)\right)$
samples $(x_{i},y_{i},z_{i})$ where $y_{i}\sim q_{0}$,
$z_{i}\sim\mathcal{N}(0,\sigma^{2}I_{d})$ and $x_{i}=e^{-t}y_{i}+z_{i}\sim
q_{t}$, we have with probability $1-\delta_{\train}$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\langle
s^{*}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle\right]\leq\frac{\delta_{\text{score}}\varepsilon^{2}}{1000\sigma^{2}}$

###### Proof.

Note that
$s(x)=\operatorname*{\mathbb{E}}_{z|x}\left[\frac{-z}{\sigma^{2}}\right]$ so
that

$\displaystyle\operatorname*{\mathbb{E}}\left[\langle
s^{*}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle\right]=0$

Also, with probability $1-\delta$, by Lemmas H.2 and G.2,

$\displaystyle\|s(x)-\frac{-z}{\sigma^{2}}\|^{2}\lesssim\frac{d+\log\frac{1}{\delta}}{\sigma^{2}}.$

Let $E$ be the event that the above holds for
$\delta=\frac{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}{100(d+\log\frac{d}{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}})}$.
Then, since the above holds for every $\delta$,

$\displaystyle\operatorname*{\mathbb{E}}\left[\|s(x)-\frac{-z}{\sigma^{2}}\|^{2}|\bar{E}\right]\lesssim\frac{d+\log\frac{d}{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}}{\sigma^{2}}$

Then, since $\operatorname{\mathbb{P}}[E]\geq
1-\frac{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}{100(d+\log\frac{d}{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}})}\geq\frac{1}{2}$
and
$\operatorname*{\mathbb{E}}\left[\|s^{*}(x)-s(x)\|^{2}|\bar{E}\right]\leq\operatorname*{\mathbb{E}}\left[\|s^{*}(x)-s(x)\|^{2}\right]/\operatorname{\mathbb{P}}[\bar{E}]$,
we have

$\displaystyle\operatorname*{\mathbb{E}}\left[\langle
s^{*}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle|E\right]$
$\displaystyle=-\frac{\operatorname*{\mathbb{E}}\left[\langle
s^{*}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle|\bar{E}\right]\operatorname{\mathbb{P}}[\bar{E}]}{\operatorname{\mathbb{P}}[E]}$
$\displaystyle\leq\frac{\sqrt{\operatorname*{\mathbb{E}}\left[\|s^{*}(x)-s(x)\|^{2}|\bar{E}\right]\operatorname*{\mathbb{E}}\left[\|s(x)-\frac{-z}{\sigma^{2}}\|^{2}|\bar{E}\right]}\operatorname{\mathbb{P}}[\bar{E}]}{\operatorname{\mathbb{P}}[E]}$
$\displaystyle\leq
2\sqrt{\operatorname*{\mathbb{E}}[\left\|s^{*}(x)-s(x)\right\|^{2}]\operatorname*{\mathbb{E}}\left[\|s(x)-\frac{-z}{\sigma^{2}}\|^{2}|\bar{E}\right]\operatorname{\mathbb{P}}[\bar{E}]}$
$\displaystyle\lesssim\frac{1}{\sigma^{2}}\sqrt{\frac{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}{C}}\cdot\sqrt{d+\log\frac{d}{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}}\cdot\sqrt{\frac{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}{100(d+\log\frac{d}{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}})}}$
$\displaystyle\leq\frac{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}{\sqrt{C}\sigma^{2}}.$

Moreover,

$\displaystyle\operatorname*{\mathbb{E}}\left[\langle
s^{*}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle^{2}|E\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}\left[\|s^{*}(x)-s(x)\|^{2}\|s(x)-\frac{-z}{\sigma^{2}}\|^{2}|E\right]$
$\displaystyle\lesssim\operatorname*{\mathbb{E}}\left[\|s^{*}(x)-s(x)\|^{2}(\frac{d+\log\frac{d}{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}}{\sigma^{2}})|E\right]$
$\displaystyle\lesssim\frac{\delta_{\text{score}}\cdot\delta_{\train}\cdot\varepsilon^{2}}{C\sigma^{2}}\cdot\frac{d+\log\frac{d}{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}}{\sigma^{2}}.$

So, by Chebyshev’s inequality, with probability $1-\delta_{\train}/2$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\langle
s^{*}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle|E\right]\lesssim\frac{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}{\sqrt{C}\sigma^{2}}+\frac{1}{\sigma^{2}}\sqrt{\frac{\delta_{\text{score}}\cdot\varepsilon^{2}\cdot(d+\log\frac{d}{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}})}{Cm}}\lesssim\frac{\delta_{\text{score}}\cdot\varepsilon^{2}}{\sqrt{C}\sigma^{2}}$

for our choice of $m$. Since $E$ holds except with probability
$\frac{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}{100(d+\log\frac{d}{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}})}\ll\delta_{\train}$,
we have with probability $1-\delta_{\train}$ in total,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\langle
s^{*}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle\right]\leq\frac{\delta_{\text{score}}\cdot\varepsilon^{2}}{1000\sigma^{2}}$

for sufficiently large constant $C$. ∎

######  Lemma B.2.

Consider any set $\mathcal{F}$ of functions
$f:\mathbb{R}^{d}\to\mathbb{R}^{d}$ such that for all $f\in\mathcal{F}$,

$\operatorname{\mathbb{P}}_{x\sim
p}\left[\|f(x)\|>\varepsilon/\sigma\right]>\delta_{\text{score}}.$

Then, with $m>\wt
O\left(\frac{1}{\varepsilon^{2}\delta_{\text{score}}}{(d+\log\frac{1}{\delta_{\train}})\log\frac{|\mathcal{F}|}{\delta_{\train}}}\right)$
samples drawn in Algorithm 1, we have with probability $1-\delta_{\train}$,

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}-2\left(\frac{-z_{i}}{\sigma^{2}}-\operatorname*{\mathbb{E}}\left[\frac{-z}{\sigma^{2}}|x_{i}\right]\right)^{T}f(x_{i})+\frac{1}{2}\|f(x_{i})\|^{2}\geq\frac{\delta_{\text{score}}\cdot\varepsilon^{2}}{16\sigma^{2}}$

holds for all $f\in\mathcal{F}$.

###### Proof.

Define

$\displaystyle
h_{f}(x,z):=-2\left(\frac{-z}{\sigma^{2}}-\operatorname*{\mathbb{E}}\left[\frac{-z}{\sigma^{2}}|x\right]\right)^{T}f(x)+\frac{1}{2}\|f(x)\|^{2}$

We want to show that $h_{f}$ has

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[h_{f}(x,z)\right]:=\frac{1}{m}\sum_{i=1}^{m}h_{f}(x_{i},z_{i})\geq\frac{\delta_{\text{score}}\varepsilon^{2}}{16\sigma^{2}}$
(14)

for all $f\in\mathcal{F}$ with probability $1-\delta_{\train}$.

Let
$B=O\left(\frac{\sqrt{d+\log\frac{m}{\varepsilon\delta_{\text{score}}\delta_{\train}}}}{\sigma}\right)$.
For $f\in\mathcal{F}$, let

$\displaystyle g_{f}(x,z)=\begin{cases}B^{2}&\text{if }\left\|f(x)\right\|\geq
10B\\\ h_{f}(x,z)&\text{otherwise}\end{cases}$

be a clipped version of $h_{f}(x,z)$. We will show that for our chosen number
of samples $m$, the following hold with probability $1-\delta_{\train}$
simultaneously:

  1. 1.

For all $i$, $\left\|\frac{-z_{i}}{\sigma^{2}}\right\|\leq B$.

  2. 2.

For all $i$,
$\left\|\operatorname*{\mathbb{E}}[\frac{-z}{\sigma^{2}}|x_{i}]\right\|\leq B$

  3. 3.

$\hat{\operatorname*{\mathbb{E}}}[g_{f}(x,z)]\geq\frac{\delta_{\text{score}}\varepsilon^{2}}{16}$
for all $f\in\mathcal{F}$

To show that these together imply (14), note that whenever
$g_{f}(x_{i},z_{i})\neq h_{f}(x_{i},z_{i})$, $\|f(x_{i})\|\geq 10B$. So, since
$\|\frac{-z_{i}}{\sigma^{2}}\|\leq B$ and
$\|\operatorname*{\mathbb{E}}[\frac{-z}{\sigma^{2}}|x_{i}]\|\leq B$,

$\displaystyle
h_{f}(x_{i},z_{i})=-2\left(\frac{-z_{i}}{\sigma^{2}}-\operatorname*{\mathbb{E}}\left[\frac{-z}{\sigma^{2}}|x_{i}\right]\right)^{T}f(x_{i})+\frac{1}{2}\|f(x_{i})\|^{2}\geq-4B\|f(x_{i})\|+\frac{1}{2}\|f(x_{i})\|^{2}\geq
B^{2}\geq g_{f}(x_{i},z_{i}).$

So under conditions $1,2,3$, for all $f\in\mathcal{F}$,

$\displaystyle\hat{\operatorname*{\mathbb{E}}}[h_{f}(x,z)]\geq\hat{\operatorname*{\mathbb{E}}}[g_{f}(x,z)]\geq\frac{\delta_{\text{score}}\varepsilon^{2}}{16\sigma^{2}}$

So it just remains to show that conditions $1,2,3$ hold with probability
$1-\delta_{\train}$ simultaneously.

  1. 1.

For all i, $\left\|\frac{-z_{i}}{\sigma^{2}}\right\|\leq B$. Holds with
probability $1-\delta_{\train}/3$ by Lemma G.2 and the union bound.

  2. 2.

For all i, $\left\|\operatorname*{\mathbb{E}}\left[\frac{-z}{\sigma^{2}}\mid
x_{i}\right]\right\|\leq B$. Holds with probability $1-\delta_{\train}/3$ by
Lemma G.3 and the union bound.

  3. 3.

$\hat{\operatorname*{\mathbb{E}}}[g_{f}(x,z)]\geq\frac{\delta_{\text{score}}\varepsilon^{2}}{16\sigma^{2}}$
for all $f\in\mathcal{F}$.

Let $E$ be the event that $1.$ and $2.$ hold. Let
$a_{i}=\min(\|f(x_{i})\|,10B)$. We proceed in multiple steps.

     * •

Conditioned on $E$, $|g_{f}(x_{i},z_{i})|\lesssim B^{2}$.

If $\|f(x_{i})\|\geq 10B$, $|g_{f}(x_{i},z_{i})|=B^{2}$ by definition. On the
other hand, when $\|f(x_{i})\|<10B$, since we condition on $E$,

$\displaystyle|g_{f}(x_{i},z_{i})|=|h_{f}(x_{i},z_{i})|$
$\displaystyle=\left|-2\left(\frac{-z_{i}}{\sigma^{2}}-\operatorname*{\mathbb{E}}\left[\frac{-z}{\sigma^{2}}|x_{i}\right]\right)^{T}f(x_{i})+\frac{1}{2}\|f(x_{i})\|^{2}\right|\lesssim
B^{2}$

     * •

$\operatorname*{\mathbb{E}}\left[g_{f}(x_{i},z_{i})|E,a_{i}\right]\gtrsim
a_{i}^{2}-O(\delta_{\train}B^{2})$.

First, note that by definition of $g_{f}(x,z)$, for $a_{i}=10B$,

$\displaystyle\operatorname*{\mathbb{E}}\left[g_{f}(x_{i},z_{i})|a_{i}=10B\right]=B^{2}$

Now, for $a_{i}<10B$,

$\displaystyle\operatorname*{\mathbb{E}}\left[g_{f}(x_{i},z_{i})|a_{i}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}\left[h_{f}(x_{i},z_{i})|a_{i}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x_{i}|\|f(x_{i})\|=a_{i}}\left[\operatorname*{\mathbb{E}}_{-z|x_{i}}\left[h_{f}(x_{i},z)\right]\right]$

Now, note that

$\displaystyle\operatorname*{\mathbb{E}}_{z|x}\left[h_{f}(x,z)\right]=\frac{1}{2}\|f(x)\|^{2}$

So, for $a<10B$

$\displaystyle\operatorname*{\mathbb{E}}\left[g_{f}(x_{i},z_{i})|a_{i}\right]=\frac{1}{2}a_{i}^{2}$

Now let $g_{f}^{\text{clip}}(x_{i},z_{i})$ be a clipped version of
$g_{f}(x_{i},z_{i})$, clipped to $\pm CB^{2}$ for sufficiently large constant
$C$. We have, by above,

$\displaystyle\operatorname*{\mathbb{E}}[g_{f}(x_{i},z_{i})|a_{i},E]=\operatorname*{\mathbb{E}}[g_{f}^{\text{clip}}(x_{i},z_{i})|a_{i},E]$

But,

$\displaystyle\operatorname*{\mathbb{E}}[g_{f}^{\text{clip}}(x_{i},z_{i})|a_{i},E]$
$\displaystyle\geq\operatorname*{\mathbb{E}}[g_{f}^{\text{clip}}(x_{i},z_{i})|a_{i}]-O(\delta_{\train}B^{2})$
$\displaystyle\gtrsim a_{i}^{2}-O(\delta_{\train}B^{2})$

     * •

$\operatorname*{\text{Var}}(g_{f}(x_{i},z_{i})|a_{i},E)\lesssim
a_{i}^{2}B^{2}$.

For $a_{i}=10B$, we have, by definition of $g_{f}(x,z)$,

$\displaystyle\operatorname*{\text{Var}}(g_{f}(x_{i},z_{i})|a_{i},E)\lesssim
B^{4}\lesssim a_{i}^{2}B^{2}$

On the other hand, for $a_{i}<10B$,

$\displaystyle\operatorname*{\text{Var}}(g_{f}(x_{i},z_{i})|a_{i},E)$
$\displaystyle\leq\operatorname*{\mathbb{E}}\left[g_{f}(x_{i},z_{i})^{2}|a_{i},E\right]$
$\displaystyle=\operatorname*{\mathbb{E}}\left[\left(-2\left(\frac{-z_{i}}{\sigma^{2}}-\operatorname*{\mathbb{E}}\left[\frac{-z}{\sigma^{2}}|x_{i}\right]\right)^{T}f(x_{i})+\frac{1}{2}\|f(x_{i})\|^{2}\right)^{2}\right]$
$\displaystyle\lesssim a_{i}^{2}B^{2}$

by Cauchy-Schwarz.

     * •

With probability $1-\delta_{\train}/3$, for all $f\in\mathcal{F}$,
$\widehat{\operatorname*{\mathbb{E}}}[g_{f}(x_{i},z_{i})]\gtrsim\Omega\left(\frac{\varepsilon^{2}\delta_{\text{score}}}{\sigma^{2}}\right)$

Using the above, by Bernstein’s inequality, with probability
$1-\delta_{\train}/6$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[g_{f}(x_{i},z_{i})|a_{i},E\right]\gtrsim\frac{1}{n}\sum_{i=1}^{n}a_{i}^{2}-O(\delta_{\train}B^{2})-\frac{1}{n}B\sqrt{\sum_{i=1}^{n}a_{i}^{2}\log\frac{1}{\delta_{\train}}}-\frac{1}{n}B^{2}\log\frac{1}{\delta_{\train}}$

Now, note that since $\operatorname{\mathbb{P}}_{x\sim
p_{\sigma}}\left[\|f(x)\|>\varepsilon/\sigma\right]\geq\delta_{\text{score}}$,
we have with probability $1-\delta_{\train}/6$, for
$n>O\left(\frac{\log\frac{1}{\delta_{\train}}}{\delta_{\text{score}}}\right)$

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}a_{i}^{2}\geq\Omega\left(\frac{\varepsilon^{2}\delta_{\text{score}}}{\sigma^{2}}\right)$

So, for
$n>O\left(\frac{B^{2}\cdot\sigma^{2}\log\frac{1}{\delta_{\train}}}{\varepsilon^{2}\delta_{\text{score}}}\right)$,
we have, with probability $1-\delta_{\train}/3$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[g_{f}(x_{i},z_{i})|E\right]\gtrsim\Omega\left(\frac{\varepsilon^{2}\delta_{\text{score}}}{\sigma^{2}}\right)-O(\delta_{\train}B^{2})$

Rescaling so that $\delta_{\train}\leq
O\left(\frac{\varepsilon^{2}\delta_{\text{score}}}{\sigma^{2}\cdot
B^{2}}\right)$, for
$n>O\left(\frac{B^{2}\cdot\sigma^{2}\log\frac{B^{2}\cdot\sigma^{2}}{\varepsilon^{2}\delta_{\text{score}}\delta_{\train}}}{\varepsilon^{2}\cdot\delta\text{score}}\right)$,
we have, with probability $1-\delta_{\train}/3$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[g_{f}(x_{i},z_{i})|E\right]\gtrsim\Omega\left(\frac{\varepsilon^{2}\delta_{\text{score}}}{\sigma^{2}}\right)$

Combining with 1. and 2. gives the claim for a single $f\in\mathcal{F}$. Union
bounding over the size of $\mathcal{F}$ gives the claim.

∎

######  Corollary B.3.

Let $\mathcal{H}_{\text{bad}}$ be a set of score functions such that for all
$\tilde{s}\in\mathcal{H}_{\text{bad}}$,

$D^{\delta_{\text{score}}}_{q}(\tilde{s},s)>{\varepsilon}/{\sigma}.$

Then, for $m>\wt
O\left(\frac{1}{\varepsilon^{2}\delta_{\text{score}}}{(d+\log\frac{1}{\delta_{\train}})\log\frac{|\mathcal{H}_{\text{bad}}|}{\delta_{\train}}}\right)$
samples drawn by Algorithm 1, we have with probability $1-\delta_{\train}$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\|\tilde{s}(x)-\frac{-z}{\sigma^{2}}\|^{2}-\|s(x)-\frac{-z}{\sigma^{2}}\|^{2}\right]\geq\frac{\delta_{\text{score}}\varepsilon^{2}}{16\sigma^{2}}$

for all $\tilde{s}\in\mathcal{H}_{\text{bad}}$.

###### Proof.

We have, for $f(x):=\tilde{s}(x)-s(x)$,

$\displaystyle\|\tilde{s}(x)-\frac{-z}{\sigma^{2}}\|^{2}-\|s(x)-\frac{-z}{\sigma^{2}}\|^{2}$
$\displaystyle=\|f(x)+(s(x)-\frac{-z}{\sigma^{2}})\|^{2}-\|s(x)-\frac{-z}{\sigma^{2}}\|^{2}$
$\displaystyle=\|f(x)\|^{2}+2(s(x)-\frac{-z}{\sigma^{2}})^{T}f(x)$
$\displaystyle=\|f(x)\|^{2}-2(\frac{-z}{\sigma^{2}}-\operatorname*{\mathbb{E}}[\frac{-z}{\sigma^{2}}|x])^{T}f(x)$

since $s(x)=\operatorname*{\mathbb{E}}\left[\frac{-z}{\sigma^{2}}|x\right]$ by
Lemma I.1. Then, by definition, for $s\in\mathcal{H}_{\text{bad}}$, for the
associated $f$,
$\operatorname{\mathbb{P}}[\|f(x)\|>\varepsilon/\sigma]>\delta_{\text{score}}$.
So, by Lemma B.2, the claim follows. ∎

###  B.2 Score Estimation for Diffusion Process

######  Theorem B.4.

Let $q_{0}$ be a distribution over $\mathbb{R}^{d}$. For discretization times
$0=t_{0}<t_{1}<\dots<t_{N}$, let $s_{T-t_{k}}$ be the true score function of
$q_{T-t_{k}}$. If for each $t_{k}$, the function class $\mathcal{H}$ contains
some $\tilde{s}_{T-t_{k}}\in\mathcal{H}$ with

$\operatorname*{\mathbb{E}}_{x\sim
q_{T-t_{k}}}\left[\left\|\tilde{s}_{T-t_{k}}(x)-s_{T-t_{k}}(x)\right\|_{2}^{2}\right]\leq\frac{\delta_{\text{score}}\cdot\delta_{\train}\cdot\varepsilon^{2}}{40\sigma_{T-t_{k}}^{2}\cdot
N^{2}}$ (15)

Then, if we take $m>\wt
O\left(\frac{N}{\varepsilon^{2}\delta_{\text{score}}}{(d+\log\frac{1}{\delta_{\train}})\log\frac{|\mathcal{H}|}{\delta_{\train}}}\right)$
samples, then with probability $1-\delta_{\train}$, each score
$\hat{s}_{T-t_{k}}$ learned by score matching satisfies

$D^{\delta_{\text{score}}/N}_{q_{T-t_{k}}}(\hat{s}_{T-t_{k}},s_{T-t_{k}})\leq\varepsilon/\sigma_{T-t_{k}}.$

###### Proof.

Note that for each $t_{k}$, $q_{T-t_{k}}$ is a $\sigma_{T-t_{k}}$-smoothed
distribution. Therefore, we can use LABEL:thm:scoreestimation by taking
$\delta_{\train}/N$ into $\delta_{\train}$ and taking
$\delta_{\text{score}}/N$ into $\delta_{\text{score}}$. We have that for each
$t_{k}$, with probability $1-\delta_{\train}/N$ the following holds:

$\operatorname{\mathbb{P}}_{x\sim
q_{T-t_{k}}}\left[\|\hat{s}_{T-t_{k}}(x)-s_{T-t_{k}}^{*}(x)\|\leq\varepsilon/\sigma_{T-t_{k}}\right]\geq
1-\delta_{\text{score}}/N.$

By a union bound over all the steps, we conclude the proposed statement. ∎

###  B.3 Score Training for Neural Networks

*

###### Proof.

Per the notation discussion above, we set $s=s_{t}$ and $\sigma=\sigma_{t}$.
Note that $\sigma<1$ since $\sigma_{t}^{2}=1-e^{-2t}$.

For any function $f$ denote

$l(f,x,z):=\left\|f(x)-\frac{-z}{\sigma^{2}}\right\|^{2}$

We will show that for every $\wt\theta$ with $\|\wt\theta\|_{F}\leq\Theta$
such that
$D_{q}^{\delta_{\text{score}}}(\phi_{\wt\theta},s)>\varepsilon/\sigma$, with
probability $1-\delta_{\train}$,

$\widehat{\operatorname*{\mathbb{E}}}\left[l(\phi_{\wt\theta},x,z)-l(\phi_{\theta^{*}},x,z)\right]>0$

so that the empirical minimizer $\phi_{\widehat{\theta}}$ is guaranteed to
have

$\displaystyle
D_{q}^{\delta_{\text{score}}}(\phi_{\widehat{\theta}},s)\leq\varepsilon/\sigma$

First, note that since the ReLU activation is contractive, the total
Lipschitzness of $\phi_{\theta}$ is at most the product of the spectral norm
of the weight matrices at each layer. For any $\theta$, consider $\wt\theta$
such that

$\displaystyle\|\wt\theta-\theta\|_{F}\leq\frac{\tau}{\sigma D\Theta^{D-1}}$

Let $M_{1},\dots,M_{D}$ be the weight matrices at each layer of the neural net
$\phi_{\theta}$, and let $\wt M_{1},\dots,\wt M_{D}$ be the corresponding
matrices of $\phi_{\wt\theta}$.

We now show that $\left\|\phi_{\wt\theta}(x)-\phi_{\theta}(x)\right\|$ is
small, using a hybrid argument. Define $y_{i}$ to be the output of a neural
network with weight matrices
$M_{1},\dotsc,M_{i},\wt{M}_{i+1},\dotsc,\wt{M}_{D}$ on input $x$, so
$y_{0}=\phi_{\wt\theta}(x)$ and $y_{D}=\phi_{\theta}(x)$. Then we have

$\displaystyle\left\|y_{i}-y_{i+1}\right\|$
$\displaystyle\leq\left\|x\right\|\cdot\left(\prod_{j\leq
i}\left\|M_{j}\right\|\right)\cdot\left\|M_{i+1}-\wt{M}_{i+1}\right\|\cdot\left(\prod_{j>i+1}\left\|\wt{M}_{j}\right\|\right)$
$\displaystyle\leq\left\|x\right\|\Theta^{D-1}\left\|\wt{\theta}-\theta\right\|_{F}$

and so

$\left\|\phi_{\wt\theta}(x)-\phi_{\theta}(x)\right\|_{2}=\left\|y_{0}-y_{D}\right\|\leq\sum_{i=0}^{D-1}\left\|y_{i}-y_{i+1}\right\|\leq\left\|x\right\|D\Theta^{D-1}\left\|\wt{\theta}-\theta\right\|_{F}\leq\left\|x\right\|\cdot\tau/\sigma.$

Note that the dimensionality of $\theta$ is $P$. So, we can construct a
$\frac{\tau}{\sigma D\Theta^{D-1}}$-net $N$ over the set
$\\{\theta:\|\theta\|_{F}\leq\Theta\\}$ of size $O\left(\frac{\sigma
D\Theta^{D-1}}{\tau}\right)^{P}$, so that for any $\theta$ with
$\|\theta\|_{F}\leq\Theta$, there exists $\wt\theta\in N$ with

$\displaystyle\|\phi_{\wt\theta}(x)-\phi_{\theta}(x)\|_{2}\leq(\tau/\sigma)\cdot\|x\|$

Let $\mathcal{H}=\\{\phi_{\wt\theta}:\wt\theta\in N\\}$. Then, we have that
for every $\theta$ with $\|\theta\|_{F}\leq\Theta$, there exists
$h\in\mathcal{H}$ such that

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\|h(x)-\phi_{\theta}(x)\|^{2}\right]\leq(\tau/\sigma)^{2}\cdot\frac{1}{m}\sum_{i=1}^{m}\|x_{i}\|^{2}$
(16)

Now, choose any $\wt\theta$ with $\|\wt\theta\|_{F}\leq\Theta$ and
$D_{q}^{\delta_{\text{score}}}(\phi_{\wt\theta},s)>\varepsilon/\sigma$, and
let $\wt h\in\mathcal{H}$ satisfy the above for $\wt\theta$.

We will set

$\displaystyle\tau=\frac{C^{\prime}\varepsilon^{2}\delta_{\text{score}}}{\Theta^{D}\left(m\cdot\max(m_{2}^{2},1)+(d+\log\frac{m}{\delta_{\train}})\right)}$
(17)

for small enough constant $C^{\prime}$. So, $|\mathcal{H}|=O\left(\frac{\sigma
D\Theta^{D-1}}{\tau}\right)^{P}<O\left(\frac{D\Theta^{2D-1}(m\cdot
m_{2}^{2}+(d+\log\frac{m}{\delta_{\train}})}{\varepsilon^{2}\delta_{\text{score}}}\right)^{P}$,
since $\sigma<1$.

So, our final choice of $m$ satisfies $m>\wt
O\left(\frac{1}{\varepsilon^{2}\delta_{\text{score}}}\left(d+\log\frac{1}{\delta_{\train}}\right)\log\frac{|\mathcal{H}|}{\delta_{\train}}\right)$.

We have

$\displaystyle\begin{split}&l(\phi_{\wt\theta},x,z)-l(\phi_{\theta^{*}},x,z)\\\
&=\|\phi_{\wt\theta}(x)-\frac{-z}{\sigma^{2}}\|^{2}-\|\phi_{\theta^{*}}(x)-\frac{-z}{\sigma^{2}}\|^{2}\\\
&=\|\phi_{\wt\theta}(x)-\wt h(x)\|^{2}+2\langle\phi_{\wt\theta}(x)-\wt
h(x),\wt h(x)-\frac{-z}{\sigma^{2}}\rangle+\|\wt
h(x)-\frac{-z}{\sigma^{2}}\|^{2}\\\
&-\|s(x)-\frac{-z}{\sigma^{2}}\|^{2}-\|\phi_{\theta^{*}}(x)-s(x)\|^{2}-2\langle\phi_{\theta^{*}}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle\end{split}$
(18)

Now, by Corollary B.3, for our choice of $m$, with probability
$1-\delta_{\train}/4$ for every $h\in\mathcal{H}$ with
$D_{q}^{\delta_{\text{score}}/2}(h,s)>\varepsilon/(2\sigma)$ simultaneously,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\|h(x)-\frac{-z}{\sigma^{2}}\|^{2}-\|s(x)-\frac{-z}{\sigma^{2}}\|^{2}\right]\geq\frac{\delta_{\text{score}}\varepsilon^{2}}{128\sigma^{2}}$

By Markov’s inequality, with probability $1-\delta_{\train}/4$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\|\phi_{\theta^{*}}(x)-s(x)]\|^{2}\right]\leq\frac{\delta_{\text{score}}\cdot\varepsilon^{2}}{250\sigma^{2}}$

By Lemma B.1, with probability $1-\delta_{\train}/4$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\langle\phi_{\theta^{*}}(x)-s(x),s(x)-\frac{-z}{\sigma^{2}}\rangle\right]\leq\frac{\delta_{\text{score}}\varepsilon^{2}}{1000\sigma^{2}}$

Plugging into (18) we have that with probability $1-3\delta_{\train}/4$, for
every $\wt h$ satisfying $D_{q}^{\delta_{\text{score}}/2}(\wt
h,s)>\varepsilon/(2\sigma)$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[l(\phi_{\wt\theta},x,z)-l(\phi_{\theta^{*}},x,z)\right]$
$\displaystyle\geq\frac{\delta_{\text{score}}\varepsilon^{2}}{128\sigma^{2}}-\frac{\delta_{\text{score}}\cdot\varepsilon^{2}}{250\sigma^{2}}-2\cdot\frac{\delta_{\text{score}}\varepsilon^{2}}{1000\sigma^{2}}+2\langle\phi_{\wt\theta}(x)-\wt
h(x),\wt h(x)-\frac{-z}{\sigma^{2}}\rangle$
$\displaystyle\geq\frac{\delta_{\text{score}}\cdot\varepsilon^{2}}{600\cdot\sigma^{2}}+2\langle\phi_{\wt\theta}(x)-\wt
h(x),\wt h(x)-\frac{-z}{\sigma^{2}}\rangle$ (19)

Now, we will show that $D_{q}^{\delta_{\text{score}}/2}(\wt
h,s)>\varepsilon/(2\sigma)$, as well as bound the last term above, for every
$\wt{\theta}$ satisfying
$D_{q}^{\delta_{\text{score}}}(\phi_{\wt\theta},s)>\varepsilon/\sigma$ and
$\wt{h}\in\mathcal{H}$ the rounding of $\phi_{\wt{\theta}}$.

By the fact that $q_{0}$ has second moment $m_{2}^{2}$, we have that with
probability $1-\delta$ over $x$,

$\displaystyle\|x\|\leq\frac{m_{2}}{\sqrt{\delta}}+\sigma\left(\sqrt{d}+\sqrt{2\log\frac{1}{\delta}}\right)$

Now since
$D_{q}^{\delta_{\text{score}}}(\phi_{\wt\theta},s)>\varepsilon/\sigma$, and
$\|\wt h(x)-\phi_{\wt\theta}(x)\|\leq(\tau/\sigma)\cdot\|x\|$, we have, with
probability at least $\delta_{\text{score}}/2$,

$\displaystyle\|\wt h(x)-s(x)\|$
$\displaystyle\geq\|\phi_{\wt\theta}(x)-s(x)\|-\|\wt
h(x)-\phi_{\wt\theta}(x)\|$
$\displaystyle\geq\varepsilon/\sigma-(\tau/\sigma)\cdot\left(\frac{m_{2}}{\sqrt{\delta_{\text{score}}/2}}+\sigma\left(\sqrt{d}+\sqrt{2\log\frac{2}{\delta_{\text{score}}}}\right)\right)$
$\displaystyle\geq\varepsilon/(2\sigma)$

for our choice of $\tau$ as in (17). So, we have shown that
$D_{q}^{\delta_{\text{score}}/2}(\wt h,s)>\varepsilon/(2\sigma)$.

Finally, we bound the last term in (19) above. We have by (16) and a union
bound, with probability $1-\delta_{\train}/8$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\|\wt
h(x)-\phi_{\wt\theta}(x)\|^{2}\right]$
$\displaystyle\lesssim(\tau/\sigma)^{2}\cdot\left(\frac{m\cdot
m_{2}^{2}}{\delta_{\train}}+\sigma^{2}\left(d+\log\frac{m}{\delta_{\train}}\right)\right)$
$\displaystyle\lesssim(\tau/\sigma)^{2}\cdot\left(\frac{m\cdot
m_{2}^{2}}{\delta_{\train}}+\left(d+\log\frac{m}{\delta_{\train}}\right)\right)\quad\text{since
$\sigma<1$}$ $\displaystyle\lesssim\frac{C^{\prime
2}\varepsilon^{4}\delta_{\text{score}}^{2}}{\sigma^{2}\Theta^{2D}}\cdot\frac{1}{\frac{m\cdot\max(m_{2}^{2},1)}{\delta_{\train}}+\left(d+\log\frac{m}{\delta_{\train}}\right)}\quad\text{by
\eqref{eq:tau_setting}}$

Similarly, with probability $1-\delta_{\train}/8$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\|\wt
h(x)-\frac{-z}{\sigma^{2}}\|^{2}\right]$
$\displaystyle\lesssim\Theta^{D}\cdot\left(\frac{m\cdot
m_{2}^{2}}{\delta_{\train}}+\sigma^{2}\left(d+\log\frac{m}{\delta_{\train}}\right)\right)+\frac{1}{\sigma^{2}}\left(d+\log\frac{m}{\delta_{\train}}\right)$

So, putting the above together, with probability $1-\delta_{\train}/4$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\|\wt
h(x)-\phi_{\wt\theta}(x)\|^{2}\right]\cdot\widehat{\operatorname*{\mathbb{E}}}\left[\|\wt
h(x)-\frac{-z}{\sigma^{2}}\|^{2}\right]$ $\displaystyle\lesssim\frac{C^{\prime
2}\varepsilon^{4}\delta_{\text{score}}^{2}}{\sigma^{2}}\left(1+\frac{1}{\sigma^{2}}\right)$
$\displaystyle\lesssim\frac{C^{\prime
2}\varepsilon^{4}\delta_{\text{score}}^{2}}{\sigma^{4}}\quad\text{since
$\sigma<1$}$

So, with probability $1-\delta_{\train}/4$, for some small enough constant
$C^{\prime}$,

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[\langle\phi_{\wt\theta}(x)-\wt
h(x),\wt h(x)-\frac{-z}{\sigma^{2}}\rangle\right]$
$\displaystyle\geq-\sqrt{\widehat{\operatorname*{\mathbb{E}}}\left[\|\wt
h(x)-\phi_{\wt\theta}(x)\|^{2}\right]\cdot\widehat{\operatorname*{\mathbb{E}}}\left[\|\wt
h(x)-\frac{-z}{\sigma^{2}}\|^{2}\right]}$
$\displaystyle\geq-\frac{\delta_{\text{score}}\varepsilon^{2}}{2000\cdot\sigma^{2}}$

So finally, combining with (19), we have with probability $1-\delta_{\train}$

$\displaystyle\widehat{\operatorname*{\mathbb{E}}}\left[l(\phi_{\wt\theta},x,z)-l(\phi_{\theta^{*}},x,z)\right]\geq\frac{\delta_{\text{score}}\cdot\varepsilon^{2}}{1000\cdot\sigma^{2}}>0$

So, we have shown that with probability $1-\delta_{\train}$, for every
$\wt\theta$ with $\|\wt\theta\|_{F}\leq\Theta$ and
$D_{q}^{\delta_{\text{score}}}(\phi_{\wt\theta},s)>\varepsilon/\sigma$,

$\displaystyle\widehat{E}\left[l(\phi_{\wt\theta},x,z)-l(\phi_{\theta^{*}},x,z)\right]>0$

so that the empirical minimizer $\phi_{\widehat{\theta}}$ is guaranteed to
have

$\displaystyle
D_{q}^{\delta_{\text{score}}}(\phi_{\widehat{\theta}},s)\leq\varepsilon/\sigma$

∎

##  Appendix C Discretization Error

######  Theorem C.1.

Let $C$ be a sufficiently large constant, and let
$h_{k}=\frac{\varepsilon(1-e^{-2t_{k}})}{C\left(d+\log\frac{1}{\delta}\right)^{3}}$
for $t_{k}$ with $t_{k}-h_{k}\geq 0$ and $\varepsilon<1$. With probability
$1-\delta$, we have for all $t\in[t_{k}-h_{k},t_{k}]$ simultaneously,

$\displaystyle\|s_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\|^{2}\lesssim\frac{\varepsilon}{1-e^{-2t_{k}}}$

###### Proof.

First,

$\displaystyle\|s_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\|^{2}$
$\displaystyle\lesssim\|s_{t_{k}}(X_{t_{k}})-\alpha s_{t}(\alpha
X_{t_{k}})\|^{2}+\|\alpha s_{t}(\alpha X_{t_{k}})-s_{t}(X_{t})\|^{2}$
$\displaystyle\lesssim\|s_{t_{k}}(X_{t_{k}})-\alpha s_{t}(\alpha
X_{t_{k}})\|^{2}+\|(\alpha-1)s_{t}(\alpha X_{t_{k}})\|^{2}+\|s_{t}(\alpha
X_{t_{k}})-s_{t}(X_{t})\|^{2}$

So by Lemmas C.2, C.3 and C.4, with probability $1-\delta$,

$\displaystyle\|s_{t_{k}}(X_{t_{k}})-s_{t}(X_{t})\|^{2}\lesssim\frac{h_{k}^{2}}{1-e^{-2t_{k}}}\left(d+\log\frac{1}{h_{k}\delta}\right)^{3}+h_{k}^{2}\frac{d+\log\frac{1}{\delta}}{1-e^{-2t_{k}}}+h_{k}\frac{(d+\log\frac{1}{\delta})^{3}}{(1-e^{-2t_{k}})^{2}}$

For our choice of $h_{k}$, the claim follows. ∎

######  Lemma C.2 (First term bound).

Let $C$ be a sufficiently large constant. Let
$h_{k}=t_{k}-t_{k+1}\leq\frac{1}{C\log\frac{1}{\delta}}$, and for
$t\in[t_{k+1},t_{k}]$, let $\alpha_{t}=e^{t_{k}-t}$. We have with probability
$1-\delta$, for all $t\in[t_{k+1},t_{k}]$ simultaneously,

$\displaystyle\|s_{t_{k}}(X_{t_{k}})-\alpha_{t}s_{t}(\alpha_{t}X_{t_{k}})\|^{2}$
$\displaystyle\lesssim\frac{h_{k}^{2}}{1-e^{-2t_{k}}}\left(d+\log\frac{1}{h_{k}\delta}\right)^{3}$

###### Proof.

We know

$\displaystyle
X_{t_{k}}\sim\frac{X_{t}}{\alpha_{t}}+\sqrt{1-\frac{1}{\alpha_{t}^{2}}}\mathcal{N}(0,I_{d})$

This means $q_{t_{k}}(x)\propto
q_{t}(\alpha_{t}x)*\mathcal{N}(0,1-\frac{1}{\alpha_{t}^{2}})$. That is,
$q_{t_{k}}(x)$ is the density of the smoothed version of
$\alpha_{t}^{d}q_{t}(\alpha_{t}x)$ when smoothed using
$\mathcal{N}\left(0,1-\frac{1}{\alpha_{t}^{2}}\right)$. Since the score
corresponding to the density $\alpha_{t}^{d}q_{t}(\alpha_{t}x)$ is $\nabla\log
q_{t}(\alpha_{t}x)=\alpha_{t}s_{t}(\alpha_{t}x)$, and for $\eta=2h_{k}$, we
have that $(1-e^{-2t_{k}})(1-\eta)\leq 1-e^{-2t_{k+1}}\leq 1-e^{-2t}$, we have
by Corollary F.2, with probability $1-\delta$, for all $t\in[t_{k+1},t_{k}]$
simultaneously,

$\displaystyle\|s_{t_{k}}(X_{t_{k}})-\alpha_{t}s_{t}(\alpha_{t}X_{t_{k}})\|^{2}$
$\displaystyle\lesssim\frac{h_{k}^{2}}{1-e^{-2t_{k}}}\left(d+\log\frac{1}{h_{k}\delta}\right)^{3}$

∎

######  Lemma C.3 (Second term bound).

Let $C$ be a sufficiently large constant. Let
$h_{k}=t_{k}-t_{k+1}\leq\frac{1}{C\log\frac{1}{\delta}}$, and for
$t\in[t_{k+1},t_{k}]$, let $\alpha_{t}=e^{t_{k}-t}$. We have with probability
$1-\delta$, for all $t\in[t_{k+1},t_{k}]$ simultaneously,

$\displaystyle\|(\alpha_{t}-1)s_{t}(\alpha_{t}X_{t_{k}})\|^{2}\lesssim
h_{k}^{2}\frac{d+\log\frac{1}{\delta}}{1-e^{-2t_{k}}}$

###### Proof.

Note that $q_{t_{k}}(x)\propto
q_{t}(\alpha_{t}x)*\mathcal{N}(0,1-\frac{1}{\alpha_{t}^{2}})$, and that the
score function of $\alpha^{d}q_{t}(\alpha_{t}x)$ is $\alpha s_{t}(\alpha x)$.
So for $X_{t_{k}}\sim q_{t_{k}}$, by Lemma G.5, we have that with probability
$1-\delta$, for all $t\in[t_{k+1},t_{k}]$ simultaneously,

$\displaystyle\|(\alpha_{t}-1)s_{t}(\alpha_{t}X_{t_{k}})\|^{2}$
$\displaystyle=\left(\frac{\alpha_{t}-1}{\alpha_{t}}\right)^{2}\|\alpha_{t}s_{t}(\alpha_{t}X_{t_{k}})\|^{2}$
$\displaystyle\lesssim h_{k}^{2}\frac{d+\log\frac{1}{\delta}}{1-e^{-2t_{k}}}$

∎

######  Lemma C.4 (Third term bound).

Let $C$ be a sufficiently large constant. Let
$h_{k}=t_{k}-t_{k+1}\leq\frac{1-e^{-2t_{k}}}{C\left(d+\log\frac{1}{\delta}\right)^{3}}$,
and for $t\in[t_{k+1},t_{k}]$, let $\alpha_{t}=e^{t_{k}-t}$. We have that with
probability $1-\delta$, for all $t\in[t_{k+1},t_{k}]$ simultaneously,

$\displaystyle\|s_{t}(\alpha_{t}X_{t_{k}})-s_{t}(X_{t})\|^{2}\lesssim
h_{k}\frac{\left(d+\log\frac{1}{\delta}\right)^{3}}{(1-e^{-2t_{k}})^{2}}$

###### Proof.

By Lemma D.1, we have that with probability $1-\delta$ over $X_{t_{k}}$, for
all $t\in[t_{k+1},t_{k}]$ simultaneously,

$\displaystyle\|\alpha_{t}X_{t_{k}}-X_{t}\|^{2}\lesssim
h_{k}\left(d+\log\frac{1}{\delta}\right)$

On the other hand, for $\eta=2h_{k}$, we have that
$(1-e^{-2t_{k}})(1-\eta)\leq 1-e^{-2t_{k}+1}\leq 1-e^{-2t}$. So, by Lemma E.1,
with probability $1-\delta$ over $X_{t_{k}}$, for all $t\in[t_{k+1},t_{k}]$
and
$\varepsilon\leq\frac{\sqrt{1-e^{-2t_{k}}}}{\sqrt{C(d+\log\frac{1}{\delta}})}$
simultaneously,

$\displaystyle\|\mathbf{J}_{s_{t}}(X_{t_{k}}+\varepsilon)\|_{2}\lesssim\frac{d+\log\frac{1}{\delta}}{1-e^{-2t_{k}}}$

So, with probability $1-2\delta$ over $X_{t_{k}}$, for all
$t\in[t_{k+1},t_{k}]$ simultaneously, for our setting of $h_{k}$,

$\displaystyle\|s_{t}(\alpha_{t}X_{t_{k}})-s_{t}(X_{t})\|^{2}\lesssim
h_{k}\frac{\left(d+\log\frac{1}{\delta}\right)^{3}}{(1-e^{-2t_{k}})^{2}}$

∎

##  Appendix D Maximum Deviation in Diffusion Process

The following bounds (with high probability) the deviation of our diffusion
process over a small time interval.

######  Lemma D.1.

For any $h<1$, we have that with probability $1-\delta$ over the forward
process, for all $t\in[t_{k}-h,t_{k}]$, the following inequality holds:

$\left\|e^{t_{k}-t}X_{t_{k}}-X_{t}\right\|_{2}^{2}\lesssim
h\left(d+\log\frac{1}{\delta}\right)$

###### Proof.

We define $Y_{t}=X_{t_{k}}-e^{-t}X_{t_{k}-t}$ for $t\in[0,h]$. It follows that

$\left\|e^{t_{k}-t}X_{t_{k}}-X_{t}\right\|_{2}^{2}=e^{2(t_{k}-t)}\left\|X_{t_{k}}-e^{t-t_{k}}X_{t}\right\|_{2}^{2}\lesssim\left\|Y_{t_{k}-t}\right\|_{2}^{2},$

which implies that we only need to prove that with probability at least
$1-\delta$,

$\max_{t\in[0,h]}\|Y_{t}\|_{2}^{2}\lesssim
h\left(d+\log\frac{1}{\delta}\right)$

Notice that $Y_{0}=0$, and since
$\operatorname{d}\\!{X}_{t}=-X_{t}\operatorname{d}\\!{t}+\sqrt{2}\operatorname{d}\\!{B}_{t}$,
we have

$\displaystyle\operatorname{d}\\!{Y}_{t}=\operatorname{d}\\!{(}X_{t_{k}}-e^{-t}X_{t_{k}-t})$
$\displaystyle=e^{-t}X_{t_{k}-t}\operatorname{d}\\!{t}-e^{-t}\operatorname{d}\\!{X}_{t_{k}-t}$
$\displaystyle=e^{-t}X_{t_{k}-t}\operatorname{d}\\!{t}-e^{-t}(X_{t_{k}-t}\operatorname{d}\\!{t}-\sqrt{2}\operatorname{d}\\!{B}_{t})$
$\displaystyle=\sqrt{2}e^{-t}\operatorname{d}\\!{B}_{t}.$

Now let $v$ be a unit vector, and consider $v^{T}Y_{t}$. Then we have
$v^{T}Y_{t}=0$ and
$\operatorname{d}\\!{(}v^{T}Y_{t})=\sqrt{2}e^{-t}\operatorname{d}\\!{W}_{t}$,
where $W_{t}$ is the one-dimensional Wiener process. It is known that with
probability $1-\delta$,

$\max_{t\in[0,h]}\left|W_{t}\right|\lesssim\sqrt{h\log\frac{1}{\delta}}$

so that we have with probability $1-\delta$,

$\max_{t\in[0,h]}|v^{T}Y_{t}|\lesssim\sqrt{h\log\frac{1}{\delta}}$

But by a net argument, we have that there exists a set
$T\subset\mathbb{R}^{d}$ of $3^{d}$ unit vectors such that

$\displaystyle\|Y_{t}\|\leq 4\max_{v\in T}|v^{T}Y_{t}|$

So union bounding over $v\in T$, we have that with probability $1-\delta$,

$\max_{t\in[0,h]}\|Y_{t}\|_{2}^{2}\lesssim
h\left(d+\log\frac{1}{\delta}\right)$

∎

##  Appendix E High probability Lipschitzness

######  Lemma E.1.

Let $C$ be a sufficiently large constant. Let $Q=q^{2}I_{d}$. Let $f_{Q}$ be
the $Q$-smoothed version of $f$, and let $s_{Q}$ be the score function of
$f_{Q}$, and $\mathbf{J}_{s_{Q}}$ be the Jacobian of $s_{Q}$. Let $f_{R}$ be
the $R$-smoothed version of $f$ for $R=r^{2}I_{d}$ with $r\geq q$. We have
that for $x\sim f_{R}$, with probability $1-\delta$, for all $\frac{r}{2}\leq
q\leq r$ and $\varepsilon$ with
$\|\varepsilon\|\leq\frac{r}{C\sqrt{d+\log\frac{1}{\delta}}}$ simultaneously,

$\left\|\mathbf{J}_{s_{Q}}(x+\varepsilon)\right\|_{2}\lesssim\frac{d+\log\frac{1}{\delta}}{r^{2}}$

###### Proof.

For $f_{Q}$ the $Q$-smoothed of $f$, we can draw a joint distribution
$(x,x^{\prime},Z_{Q})$ such that $x=x^{\prime}-Z_{Q}\sim f_{Q}$ for $Z_{Q}\sim
N(0,Q)$ independent of $x^{\prime}\sim f$. Then, by Lemma I.1,

$s_{Q}(x)=\operatorname*{\mathbb{E}}_{Z_{Q}\mid
x}\left[\frac{Z_{Q}}{q^{2}}\right].$

and

$s_{Q}(x+\varepsilon)=\frac{\nabla
f_{Q}(x+\varepsilon)}{f_{Q}(x+\varepsilon)}=\frac{\operatorname*{\mathbb{E}}_{Z_{Q}\mid
x}\left[e^{\frac{2\varepsilon^{T}Z_{Q}-\varepsilon^{T}\varepsilon}{2q^{2}}}\frac{Z_{Q}-\varepsilon}{q^{2}}\right]}{\operatorname*{\mathbb{E}}_{Z_{Q}\mid
x}\left[e^{\frac{2\varepsilon^{T}Z_{Q}-\varepsilon^{T}\varepsilon}{2q^{2}}}\right]}=\frac{\operatorname*{\mathbb{E}}_{Z_{Q}\mid
x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\frac{Z_{Q}-\varepsilon}{q^{2}}\right]}{\operatorname*{\mathbb{E}}_{Z_{Q}\mid
x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\right]}$

So, we have

Since the second term is positive semidefinite, we have

$\displaystyle\mathbf{J}_{s_{Q}}(x+\varepsilon)\preccurlyeq\frac{\operatorname*{\mathbb{E}}_{Z_{Q}\mid
x}\left[\frac{e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}}{q^{2}}\left(\frac{Z_{Q}Z_{Q}^{T}}{q^{2}}-I_{d}\right)\right]}{\operatorname*{\mathbb{E}}_{Z_{Q}\mid
x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\right]}\preccurlyeq$

To bound the denominator, by Jensen’s inequality, and the fact that
$u^{T}v\geq-\|u\|\|v\|$,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\right]\geq
e^{\varepsilon^{T}\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{Z_{Q}}{q^{2}}\right]}\geq
e^{-\|\varepsilon\|\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{\|Z_{Q}\|}{q^{2}}\right]}$

By Lemma G.4, for all $\frac{r}{2}\leq q\leq r$ simultaneously, with
probability $1-\delta/2$,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{\|Z_{Q}\|}{q^{2}}\right]\lesssim\frac{\sqrt{d+\log\frac{1}{\delta}}}{r}$

So for $\|\varepsilon\|\leq\frac{r}{C\sqrt{d+\log\frac{1}{\delta}}}$

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\right]\gtrsim
1$ (20)

For the numerator, for any unit vector $v$, we have

$\displaystyle
v^{T}\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\frac{Z_{Q}Z_{Q}^{T}}{q^{4}}\right]v\leq\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\left(e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}+e^{-\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\right)\frac{(v^{T}Z_{Q})^{2}}{q^{4}}\right]$

Now, for even $k$, we have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{R}}\left[\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\left(e^{\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}+e^{-\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}\right)\frac{(v^{T}Z_{R})^{2}}{r^{4}}\right]^{k}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{Z_{R}}\left[\left(e^{\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}+e^{-\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}\right)^{k}\left(\frac{(v^{T}Z_{R})^{2}}{r^{4}}\right)^{k}\right]$
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{E}}_{Z_{R}}\left[\left(e^{\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}+e^{-\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}\right)^{2k}\right]\operatorname*{\mathbb{E}}_{Z_{R}}\left[\left(\frac{(v^{T}Z_{R})^{2}}{r^{4}}\right)^{2k}\right]}$
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{E}}_{Z_{R}}\left[2^{2k}\left(e^{\frac{8k\varepsilon^{T}Z_{R}}{r^{2}}}+e^{-\frac{8k\varepsilon^{T}Z_{R}}{r^{2}}}\right)\right]\operatorname*{\mathbb{E}}_{Z_{R}}\left[\left(\frac{(v^{T}Z_{R})^{2}}{r^{4}}\right)^{2k}\right]}$
$\displaystyle\leq\sqrt{2^{2k+1}e^{\frac{64k^{2}\|\varepsilon\|^{2}}{r^{2}}}\frac{(4k)^{2k}}{r^{4k}}}\quad\text{since
$\varepsilon^{T}Z_{R}\sim\mathcal{N}(0,r^{2}\|\varepsilon\|^{2})$}$
$\displaystyle=2^{4k+\frac{1}{2}}e^{\frac{64k^{2}\|\varepsilon\|^{2}}{r^{2}}}\left(\frac{k}{r^{2}}\right)^{k}$
$\displaystyle\leq\left(30e^{\frac{64k\|\varepsilon\|^{2}}{r^{2}}}\frac{k}{r^{2}}\right)^{k}$

For $k=\log\frac{5^{d}}{\delta}\leq 10d+\log\frac{1}{\delta}$, we have that
$k\|\varepsilon\|^{2}\leq 1$ for
$\|\varepsilon\|\leq\frac{r}{C\sqrt{d+\log\frac{1}{\delta}}}$ so that

$\displaystyle\operatorname{\mathbb{P}}_{x\sim
f_{R}}\left[\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\left(e^{\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}+e^{-\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}\right)\frac{(v^{T}Z_{R})^{2}}{r^{4}}\right]>\frac{100e\log\frac{5^{d}}{\delta}}{r^{2}}\right]$
$\displaystyle\leq\frac{r^{2k}\cdot\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\left(e^{\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}+e^{-\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}\right)\frac{(v^{T}Z_{R})^{2}}{r^{4}}\right]^{k}}{(100e\log\frac{5^{d}}{\delta})^{k}}$
$\displaystyle\leq e^{-k}$ $\displaystyle\leq\frac{\delta}{5^{d}}$

Then, since
$\left(e^{\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}+e^{-\frac{4\varepsilon^{T}Z_{R}}{r^{2}}}\right)\frac{(v^{T}Z_{R})^{2}}{r^{4}}$
is a monotonically non-decreasing function in $\|Z_{R}\|$, we have by Lemma
G.1 that with probability $1-\frac{\delta}{5^{d}}$, for all $Q=q^{2}I_{d}$ for
$r/2\leq q\leq r$ simultaneously,

$\displaystyle
v^{T}\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\frac{Z_{Q}Z_{Q}^{T}}{q^{4}}\right]v$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\left(e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}+e^{-\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\right)\frac{(v^{T}Z_{Q})^{2}}{q^{4}}\right]$
$\displaystyle\leq
16\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\left(e^{\frac{4\varepsilon^{T}Z_{Q}}{r^{2}}}+e^{-\frac{4\varepsilon^{T}Z_{Q}}{r^{2}}}\right)\frac{(v^{T}Z_{Q})^{2}}{r^{4}}\right]$
$\displaystyle\leq 16\left(\frac{100e\log\frac{5^{d}}{\delta}}{r^{2}}\right)$
$\displaystyle\lesssim\frac{d+\log\frac{1}{\delta}}{r^{2}}$

Now, we will proceed by a net argument. We know that exists a set
$T\subset\mathbb{R}^{d}$ of $3^{n}$ unit vectors such that

$\displaystyle\left\|\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\frac{Z_{Q}Z_{Q}^{T}}{q^{2}}\right]\right\|_{2}\leq
4\max_{v\in
T}v^{T}\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\frac{Z_{Q}Z_{Q}^{T}}{q^{2}}\right]v$

So, by a union bound using the above, with probability $1-\delta/2$,

$\displaystyle\left\|\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\frac{Z_{Q}Z_{Q}^{T}}{q^{2}}\right]\right\|_{2}\lesssim\frac{d+\log\frac{1}{\delta}}{r^{2}}$

Together with (20), this gives,

$\displaystyle\left\|\frac{\operatorname*{\mathbb{E}}_{Z_{Q}\mid
x}\left[\frac{e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}}{q^{2}}\frac{Z_{Q}Z_{Q}^{T}}{q^{2}}\right]}{\operatorname*{\mathbb{E}}_{Z_{Q}\mid
x}\left[e^{\frac{\varepsilon^{T}Z_{Q}}{q^{2}}}\right]}\right\|_{2}\lesssim$

Combining this with (E) and Lemma I.2, we have the claim. ∎

##  Appendix F Reducing smoothing approximately preserves score

######  Lemma F.1.

Let $C$ be a sufficiently large constant. Let $\varepsilon\leq 1/C$,
$R=r^{2}I_{d}$ for $r\geq 0$, and let $v$ be a unit vector. We have that for
$x\sim f_{R}$, with probability $1-\delta$, for all $Q=q^{2}I_{d}$ with
$(1-\eta)r\leq q\leq r$ and $\eta\log\frac{1}{\delta}\leq 1/C$ simultaneously,

$\displaystyle\left|v^{T}s_{Q}(x)-v^{T}s_{R}(x)\right|\lesssim\frac{\eta}{r}\left(\log\frac{1}{\eta\delta}\right)^{3/2}$

###### Proof.

For all $Q=q^{2}I_{d}$ with $q\leq r$, by Lemma I.1,

$\displaystyle
v^{T}s_{Q}(x)=\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{v^{T}Z_{Q}}{q^{2}}\right]=\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{v^{T}Z_{Q}}{q^{2}}\cdot
1_{\|Z_{Q}\|\leq
r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]+\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{v^{T}Z_{Q}}{q^{2}}\cdot
1_{\|Z_{Q}\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]$

Thus,

$\displaystyle\begin{split}\left|v^{T}s_{Q}(x)-v^{T}s_{R}(x)\right|&\leq\left|\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{v^{T}Z_{Q}}{q^{2}}\cdot
1_{\|Z_{Q}\|\leq
r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]-\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\frac{v^{T}Z_{R}}{r^{2}}\cdot
1_{\|Z_{R}\|\leq
r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]\right|\\\
&+\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\left|\frac{v^{T}Z_{Q}}{q^{2}}\right|\cdot
1_{\|Z_{Q}\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]+\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\left|\frac{v^{T}Z_{R}}{r^{2}}\right|\cdot
1_{\|Z_{R}\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]\end{split}$
(21)

Now, since $Z_{R}\sim\mathcal{N}(0,r^{2}I_{d})$,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{R}}\left[\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\left|\frac{v^{T}Z_{R}}{r^{2}}\right|\cdot
1_{\|Z_{R}\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]\right]\lesssim\frac{\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}{r}\cdot\frac{\varepsilon\delta}{\log\frac{1}{\varepsilon\delta}}\lesssim\frac{\varepsilon\delta}{r}\quad\text{since
$\varepsilon\lesssim 1$ so that $\varepsilon\delta\lesssim 1$ }$

So by Markov’s inequality, with probability $1-\delta$, for $x\sim f_{R}$,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\left|\frac{v^{T}Z_{R}}{r^{2}}\right|\cdot
1_{\|Z_{R}\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]\lesssim\frac{\varepsilon}{r}$

So, since $\left|\frac{v^{T}z}{r^{2}}\right|\cdot
1_{\|z\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}$
is monotonically increasing in $\|z\|$, by Lemma G.1, we have

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\left|\frac{v^{T}Z_{Q}}{r^{2}}\right|\cdot
1_{\|Z_{Q}\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]\leq\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\left|\frac{v^{T}Z_{R}}{r^{2}}\right|\cdot
1_{\|Z_{R}\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]$

so that for $x\sim f_{R}$, with probability $1-\delta$, for all $Q=q^{2}I_{d}$
with $q\leq r$ simultaneously,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\left|\frac{v^{T}Z_{Q}}{q^{2}}\right|\cdot
1_{\|Z_{Q}\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]\lesssim\frac{\varepsilon
r}{q^{2}}$ (22)

By a similar argument, for $x\sim f_{R}$, with probability $1-\delta$

$\displaystyle\operatorname{\mathbb{P}}_{Z_{R}|x}\left[\|Z_{R}\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon{\delta}}}\right]\lesssim\frac{\varepsilon}{\log\frac{1}{\varepsilon\delta}}$

so that by Lemma G.1, for all $Q=q^{2}I_{d}$ with $q\leq r$ simultaenously,

$\displaystyle\operatorname{\mathbb{P}}_{Z_{Q}|x}\left[\|Z_{Q}\|>r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon{\delta}}}\right]\lesssim\frac{\varepsilon}{\log\frac{1}{\varepsilon\delta}}$

Now for $z$ with $\|z\|\leq
r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon{\delta}}}$, we
have that

$\left(\frac{r}{q}\right)^{d}\cdot\left(\frac{\varepsilon\delta}{\log\frac{1}{\varepsilon\delta}}\right)^{\frac{r^{2}}{q^{2}}-1}\leq\frac{w_{Q}(z)}{w_{R}(z)}\leq\left(\frac{r}{q}\right)^{d}$

So, this along with the above gives that for $x\sim f_{R}$, with probability
$1-\delta$, for all $Q=q^{2}I_{d}$ with $q\leq r$ and
$\left(\frac{r^{2}}{q^{2}}-1\right)\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}\leq
1/C$ simultaneously,

$\displaystyle\left(\frac{r}{q}\right)^{d}\cdot\left(\frac{\varepsilon\delta}{\log\frac{1}{\varepsilon\delta}}\right)^{\frac{r^{2}}{q^{2}}-1}f_{R}(x)\leq
f_{Q}(x)\leq\left(\frac{r}{q}\right)^{d}f_{R}(x)+f_{Q}(x)O\left(\frac{\varepsilon}{\log\frac{1}{\varepsilon\delta}}\right)\leq
f_{R}(x)(r/q)^{d}\left(1+O\left(\frac{\varepsilon}{\log\frac{1}{\varepsilon\delta}}\right)\right)$

So, for $\|z\|\leq
r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}$,

$\displaystyle
f_{Z_{R}|x}(z)\left(\frac{\varepsilon\delta}{\log\frac{1}{\varepsilon\delta}}\right)^{\frac{r^{2}}{q^{2}}-1}\left(1-O\left(\frac{\varepsilon}{\log\frac{1}{\varepsilon\delta}}\right)\right)\leq
f_{Z_{Q}|x}(z)\leq\frac{f_{Z_{R}|x}(z)}{\left(\varepsilon\delta/\log\frac{1}{\varepsilon\delta}\right)^{\frac{r^{2}}{q^{2}}-1}}$

In other words, for $\|z\|\leq
r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}$,

$\displaystyle\left|f_{Z_{Q}|x}(z)-f_{Z_{R}|x}(z)\right|\lesssim
f_{Z_{R}|x}(z)\left(\left(\frac{r^{2}}{q^{2}}-1\right)\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}+\frac{\varepsilon}{\log\frac{1}{\varepsilon\delta}}\right)$

This means

$\displaystyle\left|\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{v^{T}Z_{Q}}{r^{2}}\cdot
1_{\|Z_{Q}\|\leq
r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]-\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\frac{v^{T}Z_{R}}{r^{2}}\cdot
1_{\|Z_{R}\|\leq
r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]\right|$
$\displaystyle\lesssim\frac{\varepsilon}{r}+\frac{1}{r}\left(\frac{r^{2}}{q^{2}}-1\right)\left(\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}\right)^{3/2}$

so that

$\displaystyle\left|\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{v^{T}Z_{Q}}{q^{2}}\cdot
1_{\|Z_{Q}\|\leq
r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]-\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\frac{v^{T}Z_{R}}{r^{2}}\cdot
1_{\|Z_{R}\|\leq
r\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}}\right]\right|$
$\displaystyle\lesssim\frac{\varepsilon}{r}+\frac{1}{r}\left(\frac{r^{2}}{q^{2}}-1\right)\left(\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}\right)^{3/2}+\frac{1}{r}\left(\frac{r^{2}}{q^{2}}-1\right)\sqrt{\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}}$
$\displaystyle\lesssim\frac{\varepsilon}{r}+\frac{1}{r}\left(\frac{r^{2}}{q^{2}}-1\right)\left(\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}\right)^{3/2}$

So, putting this together with (21) and (F), for $x\sim f_{R}$ with
probability $1-2\delta$, for all $Q=q^{2}I_{d}$ with $q\leq r$ and
$\left(\frac{r^{2}}{q^{2}}-1\right)\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}\leq
1/C$ simultaneously,

$\displaystyle\left|v^{T}s_{Q}(x)-v^{T}s_{R}(x)\right|\lesssim\frac{\varepsilon
r}{q^{2}}+\frac{1}{r}\left(\frac{r^{2}}{q^{2}}-1\right)\left(\log\frac{\log\frac{1}{\varepsilon\delta}}{\varepsilon\delta}\right)^{3/2}+\frac{\varepsilon}{r}$

For $(1-\eta)r\leq q$, setting
$\varepsilon=\eta\log\left(\frac{1}{\varepsilon\delta}\right)^{3/2}$, the
claim follows. ∎

######  Corollary F.2.

Let $C$ be a sufficiently large constant. Let $\varepsilon\leq 1/C$,
$R=r^{2}I_{d}$ for $r\geq 0$, and let $v$ be a unit vector. We have that for
$x\sim f_{R}$, with probability $1-\delta$, for all $Q=q^{2}I_{d}$ with
$(1-\eta)r\leq q\leq r$ and $\eta\log\frac{1}{\delta}\leq 1/C$ simultaneously,

$\displaystyle\|s_{Q}(x)-s_{R}(x)\|^{2}\lesssim\frac{\eta^{2}}{r^{2}}\left(d+\log\frac{1}{\eta\delta}\right)^{3}$

###### Proof.

We show the claim via a net argument. We know that there exists a set
$T\subset\mathbb{R}^{d}$ of $3^{d}$ vectors such that

$\displaystyle\|s_{Q}(x)-s_{R}(x)\|\leq 4\max_{v\in
T}|v^{T}(s_{Q}(x)-s_{R}(x))|$

So, the claim follows from the lemma by a union bound. ∎

##  Appendix G Utility Lemmas

######  Lemma G.1.

Suppose $h:\mathbb{R}^{d}\to\mathbb{R}$ is such that $h(z)$ is monotonically
non-decreasing in $\|z\|$. Let $R=r^{2}I_{d}$. Then, for all $Q=q^{2}I_{d}$
with $q\leq r$,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[h(z)\right]\leq\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[h(z)\right]$

###### Proof.

Let $f_{Z_{R}|x}$ be the pdf of $Z_{R}|x$. We have that $f_{Z_{R}|x}(z)\propto
w_{R}(z)f(x-z)$. So, $f_{Z_{Q}|x}(z)\propto f_{Z_{R}|x}(z)\cdot g(z)$ where
$g(z)=\frac{w_{Q}(z)}{w_{R}(z)}$. Note that since $q\leq r$, $g(z)$ is
decreasing in $\|z\|$. So, since $h(z)$ is monotonically non-decreasing in
$\|z\|$, we have the claim ∎

######  Lemma G.2.

For $z\sim\mathcal{N}(0,r^{2}I_{d})$, with probability $1-\delta$,

$\displaystyle\left\|\frac{z}{r^{2}}\right\|\lesssim\frac{\sqrt{d+\log\frac{1}{\delta}}}{r}$

###### Proof.

Note that $\|z\|^{2}$ is chi-square, so that we have for any
$0\leq\lambda<r^{2}/2$,

$\displaystyle\operatorname*{\mathbb{E}}_{z}\left[e^{\lambda\left\|\frac{\|z\|}{r^{2}}\right\|^{2}}\right]\leq\frac{1}{(1-2(\lambda/r^{2}))^{d/2}}$

The claim then follows by the Chernoff bound. ∎

######  Lemma G.3.

For $x\sim f_{R}$, with probability $1-\delta$,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\frac{\|Z_{R}\|}{r^{2}}\right]\lesssim\frac{\sqrt{d+\log\frac{1}{\delta}}}{r}$

###### Proof.

Since $Z_{R}\sim\mathcal{N}(0,r^{2}I_{d})$ so that $\|Z_{R}\|^{2}$ is chi-
square, we have that for any $0\leq\lambda<r^{2}/2$, by Jensen’s inequality,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{R}}\left[e^{\lambda\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\frac{\|Z_{R}\|}{r^{2}}\right]^{2}}\right]\leq\operatorname*{\mathbb{E}}_{Z_{R}}\left[e^{\lambda\frac{\|Z_{R}\|^{2}}{r^{4}}}\right]\leq\frac{1}{(1-2(\lambda/r^{2}))^{d/2}}$

The claim then follows by the Chernoff bound. That is, setting
$\lambda=r^{2}/4$, for any $t>0$,

$\displaystyle\operatorname{\mathbb{P}}_{x\sim
f_{R}}\left[\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\frac{\|Z_{R}\|}{r^{2}}\right]^{2}\geq
t\right]\leq\frac{\operatorname*{\mathbb{E}}_{x\sim
f_{R}}\left[e^{\lambda\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\frac{\|Z_{R}\|}{r^{2}}\right]^{2}}\right]}{e^{\lambda
t}}\leq 2^{d/2}e^{-tr^{2}/4}=2^{\frac{d\ln 2}{2}-\frac{tr^{2}}{4}}$

For $t=O\left(\frac{d+\log\frac{1}{\delta}}{r^{2}}\right)$, this is less than
$\delta$. ∎

######  Lemma G.4.

Let $f$ be an arbitrary distribution, and let $f_{Q}$ be the $Q$-smoothed
version of $f$ for $Q=q^{2}I_{d}$. Let $f_{R}$ be the $R$-smoothed version of
$f$ for $R=r^{2}I_{d}$. We have that for $x\sim f_{R}$, with probability
$1-\delta$, for all $\frac{r}{2}\leq q\leq r$ simultaneously,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{\|Z_{Q}\|}{q^{2}}\right]\lesssim\frac{\sqrt{d+\log\frac{1}{\delta}}}{r}$

###### Proof.

By Lemma G.3, we have that with probability $1-\delta$,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[\frac{\|Z_{R}\|}{r^{2}}\right]\lesssim\frac{\sqrt{d+\log\frac{1}{\delta}}}{r}$

So, by Lemma G.1, with probability $1-\delta$, for all $Q=q^{2}I_{d}$ with
$q\leq r$ simultaneously,

$\displaystyle\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{\|Z_{Q}\|}{q^{2}}\right]\lesssim\frac{r\sqrt{d+\log\frac{1}{\delta}}}{q^{2}}\lesssim\frac{\sqrt{d+\log\frac{1}{\delta}}}{r}$

for $r/2\leq q\leq r$. ∎

######  Corollary G.5.

Let $f$ be an arbitrary distribution, and let $f_{Q}$ be the $Q$-smoothed
version of $f$ for $Q=q^{2}I_{d}$. Let $f_{R}$ be the $R$-smoothed version of
$f$ for $R=r^{2}I_{d}$. We have that for $x\sim f_{R}$, with probability
$1-\delta$, for all $\frac{r}{2}\leq q\leq r$ simultaneously,

$\displaystyle\|s_{Q}(x)\|\lesssim\frac{\sqrt{d+\log\frac{1}{\delta}}}{n}$

###### Proof.

Follows from the fact that

$\displaystyle\|s_{Q}(x)\|=\left\|\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{Z_{Q}}{q^{2}}\right]\right\|\leq\operatorname*{\mathbb{E}}_{Z_{Q}|x}\left[\frac{\|Z_{Q}\|}{q^{2}}\right]$

∎

######  Lemma G.6.

Let $Z\in\mathbb{R}$ be a random variable with
$\operatorname{\mathbb{P}}\left[Z>\varepsilon/\delta\right]<2\delta$. If there
exists an event $E$ with probability $1-\delta$ such that

$\operatorname*{\mathbb{E}}\left[Z\mid E\right]\leq\varepsilon,$

then we have

$\operatorname*{\mathbb{E}}\left[Z\mid
Z\leq\frac{\varepsilon}{\delta}\right]\lesssim\varepsilon.$

###### Proof.

We have

$\displaystyle\operatorname*{\mathbb{E}}\left[Z\ \middle|\
Z\leq\frac{\varepsilon}{\delta}\right]=\operatorname{\mathbb{P}}\left[E\
\middle|\
Z\leq\frac{\varepsilon}{\delta}\right]\cdot\operatorname*{\mathbb{E}}\left[Z\
\middle|\ Z\leq\frac{\varepsilon}{\delta}\cap
E\right]+\left(1-\operatorname{\mathbb{P}}\left[E\ \middle|\
Z\leq\frac{\varepsilon}{\delta}\right]\right)\cdot\operatorname*{\mathbb{E}}\left[Z\
\middle|\ Z\leq\frac{\varepsilon}{\delta}\cap\overline{E}\right]$

Since

$1-\operatorname{\mathbb{P}}\left[E\ \middle|\
Z\leq\frac{\varepsilon}{\delta}\right]\leq
1-\frac{1-3\delta}{1-2\delta}\lesssim\delta,$

we have

$\left(1-\operatorname{\mathbb{P}}\left[E\ \middle|\
Z\leq\frac{\varepsilon}{\delta}\right]\right)\cdot\operatorname*{\mathbb{E}}\left[Z\
\middle|\
Z\leq\frac{\varepsilon}{\delta}\cap\overline{E}\right]\lesssim\frac{\varepsilon}{\delta}\cdot\delta\leq\varepsilon.$

Furthermore, we have

$\displaystyle\operatorname*{\mathbb{E}}\left[Z\ \middle|\
E\right]\geq\operatorname{\mathbb{P}}\left[Z\leq\frac{\varepsilon}{\delta}\
\middle|\ E\right]\operatorname*{\mathbb{E}}\left[Z\ \middle|\
Z\leq\frac{\varepsilon}{\delta}\cap
E\right]\geq\frac{1-3\delta}{1-\delta}\operatorname*{\mathbb{E}}\left[Z\
\middle|\ Z\leq\frac{\varepsilon}{\delta}\cap E\right]$

Thus,

$\displaystyle\operatorname*{\mathbb{E}}\left[Z\ \middle|\
Z\leq\frac{\varepsilon}{\delta}\cap
E\right]\lesssim\operatorname*{\mathbb{E}}\left[Z\ \middle|\
E\right]\leq\varepsilon$

This implies that

$\operatorname*{\mathbb{E}}\left[Z\ \middle|\
Z\leq\frac{\varepsilon}{\delta}\right]\lesssim\varepsilon.$

∎

##  Appendix H Subgaussianity of score

######  Lemma H.1.

For $s_{R}$ the score function of an $R$-smoothed distribution where
$R=r^{2}I$, we have that $v^{T}s_{R}(x)$ is $O(1/r^{2})$-subgaussian, when
$x\sim f_{R}$ and $\|v\|=1$.

###### Proof.

We have by Lemma I.1 that

$\displaystyle
s_{R}(x)=\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[R^{-1}Z_{R}\right]$

So,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim
f_{R}}\left[(v^{T}s_{R}(x))^{k}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim
f_{R}}\left[\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[v^{T}R^{-1}Z_{R}\right]^{k}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{Z_{R}}\left[(v^{T}R^{-1}Z_{R})^{k}\right]$
$\displaystyle\leq\frac{k^{k/2}}{r^{k}}\quad\text{since
$v^{T}Z_{R}\sim\mathcal{N}(0,r^{2})$}$

The claim follows. ∎

######  Lemma H.2.

Let $R=r^{2}I$, and let $x\sim f_{R}$. We have that with probability
$1-\delta$,

$\|s_{R}(x)\|^{2}\lesssim\frac{d+\log\frac{1}{\delta}}{r^{2}}$

###### Proof.

Follows from Lemmas H.1 and I.3. ∎

##  Appendix I Useful Results

######  Lemma I.1 (From [GLP23]).

Let $f$ be an arbitrary distribution on $\mathbb{R}^{d}$, and let $f_{R}$ be
the $R$-smoothed version of $f$. That is,
$f_{R}(x)=\operatorname*{\mathbb{E}}_{y\sim
f}\left[(2\pi)^{-d/2}\det(R)^{-1/2}\exp\left(-\frac{1}{2}(x-Y)^{T}R^{-1}(x-Y)\right)\right]$.
Let $s_{R}$ be the score function of $f_{R}$. Let $(X,Y,Z_{R})$ be the joint
distribution such that $Y\sim f$, $Z_{R}\sim\mathcal{N}(0,R)$ are independent,
and $X=Y+Z_{R}\sim f_{R}$. We have for $\varepsilon\in\mathbb{R}^{d}$,

$\frac{f_{R}(x+\varepsilon)}{f_{R}(x)}=\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[e^{-\varepsilon^{T}R^{-1}Z_{R}-\frac{1}{2}\varepsilon^{T}R^{-1}\varepsilon}\right]$

so that

$s_{R}(x)=\operatorname*{\mathbb{E}}_{Z_{R}|x}\left[-R^{-1}Z_{R}\right]$

######  Lemma I.2 (From [GLP23]).

Let $s_{R}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ be the score function of $f_{R}$,
the $R$-smoothed version of distribution $f$. Let $\mathbf{J}_{s_{R}}(x)$ be
the Jacobian of $s_{R}$. We have that

$\mathbf{J}_{s_{R}}(x)\succcurlyeq-R^{-1}$

for all $x$.

######  Lemma I.3 (From [Hsu:2012], restated).

Let $x$ be a mean-zero random vector in $\mathbb{R}^{d}$ that is
$\Sigma$-subgaussian. That is, for every vector $v$,

$\displaystyle\operatorname*{\mathbb{E}}\left[e^{\lambda\langle
x,v\rangle}\right]\leq e^{\lambda^{2}v^{T}\Sigma v/2}$

Then, with probability $1-\delta$,

$\displaystyle\|x\|\lesssim\sqrt{\operatorname{Tr}(\Sigma)}+\sqrt{2\|\Sigma\|\log\frac{1}{\delta}}$