Let $N_{i}(x)$ be defined as Definition G.1.

  * •

Let $\|x-\mu_{i}(t)\|_{2}\leq R$, where $R\geq 1$, for each $i\in[k]$.

  * •

Let $\|x-\mu_{i}(t)\|_{2}\geq\beta$, where $\beta\in(0,0.1)$, for each
$i\in[k]$.

  * •

Let $\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x)\geq\gamma$, where $\gamma\in(0,0.1)$.

  * •

Let
$\sigma_{\min}:=\min\\{\sigma_{\min}(\Sigma_{1}(t)),\sigma_{\min}(\Sigma_{2}(t)),\dots,\sigma_{\min}(\Sigma_{k}(t))\\}$.

  * •

Let
$\sigma_{\max}:=\max\\{\sigma_{\max}(\Sigma_{1}(t)),\sigma_{\max}(\Sigma_{2}(t)),\dots,\sigma_{\max}(\Sigma_{k}(t))\\}$.

  * •

Let
$\det_{\min}:=\min\\{\det(\Sigma_{1}(t)),\det(\Sigma_{2}(t)),\dots,\det(\Sigma_{k}(t))\\}$.

Then, we have

$\displaystyle|(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x))^{-1}-(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}|\leq\gamma^{-2}\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}}\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$

###### Proof.

We can show

$\displaystyle\mathrm{LHS}=$
$\displaystyle~{}(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x))^{-1}\cdot(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}\cdot|\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x)-\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x})|$
$\displaystyle\leq$
$\displaystyle~{}\gamma^{-2}\cdot|\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x)-\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x})|$
$\displaystyle\leq$
$\displaystyle~{}\gamma^{-2}\cdot\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}}\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$

where the first step follows from simple algebra, the second step follows from
$\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x)\geq\gamma$, and the last step follows
from Lemma G.7. ∎

This lemma calculates Lipschitz constant of function
$|f_{i}(x)-f_{i}(\widetilde{x})|$.

######  Lemma G.9.

If the following conditions hold

  * •

Let $x,\widetilde{x}\in\mathbb{R}^{d}$.

  * •

Let $i\in[k]$.

  * •

Let $t\in\mathbb{R}$, and $t\geq 0$.

  * •

Let $\alpha_{i}(t)\in\mathbb{R}$, $\sum_{i=1}^{k}\alpha_{i}(t)=1$, and
$\alpha_{i}(t)\in(0,1)$.

  * •

Let $N_{i}(x)$ be defined as Definition G.1.

  * •

Let $f_{i}(x)$ be defined as Definition G.4.

  * •

Let $\|x-\mu_{i}(t)\|_{2}\leq R$, where $R\geq 1$, for each $i\in[k]$.

  * •

Let $\|x-\mu_{i}(t)\|_{2}\geq\beta$, where $\beta\in(0,0.1)$, for each
$i\in[k]$.

  * •

Let $\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x)\geq\gamma$, where $\gamma\in(0,0.1)$.

  * •

Let
$\sigma_{\min}:=\min\\{\sigma_{\min}(\Sigma_{1}(t)),\sigma_{\min}(\Sigma_{2}(t)),\dots,\sigma_{\min}(\Sigma_{k}(t))\\}$.

  * •

Let
$\sigma_{\max}:=\max\\{\sigma_{\max}(\Sigma_{1}(t)),\sigma_{\max}(\Sigma_{2}(t)),\dots,\sigma_{\max}(\Sigma_{k}(t))\\}$.

  * •

Let
$\det_{\min}:=\min\\{\det(\Sigma_{1}(t)),\det(\Sigma_{2}(t)),\dots,\det(\Sigma_{k}(t))\\}$.

Then, for each $i\in[k]$, we have

$\displaystyle|f_{i}(x)-f_{i}(\widetilde{x})|\leq
2\alpha_{i}(t)\cdot\gamma^{-2}\cdot\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}}\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$

###### Proof.

We can show

$\displaystyle|f_{i}(x)-f_{i}(\widetilde{x})|=$
$\displaystyle~{}|\alpha_{i}(t)N_{i}(x)\cdot(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x))^{-1}-\alpha_{i}(t)N_{i}(\widetilde{x})\cdot(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}|$
$\displaystyle\leq$
$\displaystyle~{}|\alpha_{i}(t)N_{i}(x)\cdot(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x))^{-1}-\alpha_{i}(t)N_{i}(x)\cdot(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}|$
$\displaystyle~{}+|\alpha_{i}(t)N_{i}(x)\cdot(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}-\alpha_{i}(t)N_{i}(\widetilde{x})\cdot(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}|$
$\displaystyle\leq$
$\displaystyle~{}\alpha_{i}(t)N_{i}(x)\cdot|(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x))^{-1}-(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}|$
$\displaystyle~{}+\alpha_{i}(t)(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}|N_{i}(x)-N_{i}(\widetilde{x})|$

where the first step follows from Definition G.4, the second step follows from
Fact C.2, and the last step follows from simple algebra.

For the first term in the above, we have

$\displaystyle~{}\alpha_{i}(t)N_{i}(x)\cdot|(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x))^{-1}-(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}|$
$\displaystyle\leq$
$\displaystyle~{}\alpha_{i}(t)\cdot\frac{1}{(2\pi)^{d/2}\det(\Sigma_{i}(t))^{1/2}}\cdot|(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x))^{-1}-(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}|$
$\displaystyle\leq$
$\displaystyle~{}\alpha_{i}(t)\cdot\frac{1}{(2\pi)^{d/2}\det(\Sigma_{i}(t))^{1/2}}\cdot\gamma^{-2}\cdot\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}}\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\alpha_{i}(t)\cdot\gamma^{-2}\cdot\frac{1}{(2\pi)^{d}\det_{\min}}\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$
(19)

where the first step follows from
$N_{i}(x)\leq\frac{1}{(2\pi)^{d/2}\det(\Sigma_{i}(t))^{1/2}}$, the second step
follows from Lemma G.8, and the last step follows from definition of
$\det_{\min}$.

For the second term in the above, we have

$\displaystyle~{}\alpha_{i}(t)(\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(\widetilde{x}))^{-1}|N_{i}(x)-N_{i}(\widetilde{x})|$
$\displaystyle\leq$
$\displaystyle~{}\alpha_{i}(t)\cdot\gamma^{-1}\cdot|N_{i}(x)-N_{i}(\widetilde{x})|$
$\displaystyle\leq$
$\displaystyle~{}\alpha_{i}(t)\cdot\gamma^{-1}\cdot\frac{1}{(2\pi)^{d/2}\det(\Sigma_{i}(t))^{1/2}}\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}(\Sigma_{i}(t))})\cdot\frac{R}{\sigma_{\min}(\Sigma_{i}(t))}\cdot\|x-\widetilde{x}\|_{2}$
(20)

where the first step follows from
$\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x)\geq\gamma$, the second step follows from
Lemma G.7.

Combining Eq. (G.4) and Eq. (G.4) together, we have

$\displaystyle|f_{i}(x)-f_{i}(\widetilde{x})|\leq$
$\displaystyle~{}\alpha_{i}(t)\cdot\gamma^{-2}\cdot\frac{1}{(2\pi)^{d}\det_{\min}}\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$
$\displaystyle~{}+\alpha_{i}(t)\cdot\gamma^{-1}\cdot\frac{1}{(2\pi)^{d/2}\det(\Sigma_{i}(t))^{1/2}}\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}(\Sigma_{i}(t))})\cdot\frac{R}{\sigma_{\min}(\Sigma_{i}(t))}\cdot\|x-\widetilde{x}\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\alpha_{i}(t)\cdot\gamma^{-2}\cdot\frac{1}{(2\pi)^{d}\det_{\min}}\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$
$\displaystyle~{}+\alpha_{i}(t)\cdot\gamma^{-1}\cdot\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}}\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}2\alpha_{i}(t)\cdot\gamma^{-2}\cdot(\frac{1}{(2\pi)^{d}\det_{\min}}+\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$

where the first step follows from the bound of the first term and the second
term, the second step follows from the definition of
$\det_{\min},\sigma_{\max},\sigma_{\min}$, and the last step follows from
$\gamma<0.1$. ∎

This lemma calculates Lipschitz constant of function
$\|f_{i}(x)(-\Sigma_{i}(t)^{-1}(x-\mu_{i}(t)))-f_{i}(\widetilde{x})(-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t)))\|_{2}$.

######  Lemma G.10.

If the following conditions hold

  * •

Let $x,\widetilde{x}\in\mathbb{R}^{d}$.

  * •

Let $i\in[k]$.

  * •

Let $t\in\mathbb{R}$, and $t\geq 0$.

  * •

Let $\alpha_{i}(t)\in\mathbb{R}$, $\sum_{i=1}^{k}\alpha_{i}(t)=1$, and
$\alpha_{i}(t)\in(0,1)$.

  * •

Let $N_{i}(x)$ be defined as Definition G.1.

  * •

Let $f_{i}(x)$ be defined as Definition G.4.

  * •

Let $\|x-\mu_{i}(t)\|_{2}\leq R$, where $R\geq 1$, for each $i\in[k]$.

  * •

Let $\|x-\mu_{i}(t)\|_{2}\geq\beta$, where $\beta\in(0,0.1)$, for each
$i\in[k]$.

  * •

Let $\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x)\geq\gamma$, where $\gamma\in(0,0.1)$.

  * •

Let
$\sigma_{\min}:=\min\\{\sigma_{\min}(\Sigma_{1}(t)),\sigma_{\min}(\Sigma_{2}(t)),\dots,\sigma_{\min}(\Sigma_{k}(t))\\}$.

  * •

Let
$\sigma_{\max}:=\max\\{\sigma_{\max}(\Sigma_{1}(t)),\sigma_{\max}(\Sigma_{2}(t)),\dots,\sigma_{\max}(\Sigma_{k}(t))\\}$.

  * •

Let
$\det_{\min}:=\min\\{\det(\Sigma_{1}(t)),\det(\Sigma_{2}(t)),\dots,\det(\Sigma_{k}(t))\\}$.

Then, for each $i\in[k]$, we have

$\displaystyle~{}\|f_{i}(x)(-\Sigma_{i}(t)^{-1}(x-\mu_{i}(t)))-f_{i}(\widetilde{x})(-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t)))\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}(\frac{|f_{i}(x)|}{\sigma_{\min}}+2\alpha_{i}(t)\cdot\gamma^{-2}\cdot(\frac{1}{(2\pi)^{d}\det_{\min}}+\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot(\frac{R}{\sigma_{\min}})^{2})\cdot\|x-\widetilde{x}\|_{2}$

###### Proof.

We can show

$\displaystyle\mathrm{LHS}\leq$
$\displaystyle~{}\|f_{i}(x)(-\Sigma_{i}(t)^{-1}(x-\mu_{i}(t)))-f_{i}(x)(-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t)))\|_{2}$
$\displaystyle~{}+\|f_{i}(x)(-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t)))-f_{i}(\widetilde{x})(-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t)))\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}|f_{i}(x)|\cdot\|(-\Sigma_{i}(t)^{-1}(x-\mu_{i}(t)))-(-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t)))\|_{2}$
$\displaystyle~{}+|f_{i}(x)-f_{i}(\widetilde{x})|\cdot\|-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t))\|_{2}$

where the first step follows from Fact C.2, the second step follows from Fact
C.2.

For the first term in the above, we have

$\displaystyle~{}|f_{i}(x)|\cdot\|(-\Sigma_{i}(t)^{-1}(x-\mu_{i}(t)))-(-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t)))\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\frac{|f_{i}(x)|}{\sigma_{\min}(\Sigma_{i}(t))}\cdot\|x-\widetilde{x}\|_{2}$
(21)

where the first step follows from Lemma F.12.

For the second term in the above, we have

$\displaystyle~{}|f_{i}(x)-f_{i}(\widetilde{x})|\cdot\|-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t))\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\frac{R}{\sigma_{\min}(\Sigma_{i}(t))}\cdot|f_{i}(x)-f_{i}(\widetilde{x})|$
$\displaystyle\leq$
$\displaystyle~{}\frac{R}{\sigma_{\min}(\Sigma_{i}(t))}\cdot
2\alpha_{i}(t)\cdot\gamma^{-2}\cdot(\frac{1}{(2\pi)^{d}\det_{\min}}+\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$
(22)

where the first step follows from Lemma F.9, the second step follows from
Lemma G.9.

Combining Eq. (G.4) and Eq. (G.4) together, we have

$\displaystyle~{}\|f_{i}(x)(-\Sigma_{i}(t)^{-1}(x-\mu_{i}(t)))-f_{i}(\widetilde{x})(-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t)))\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\frac{|f_{i}(x)|}{\sigma_{\min}(\Sigma_{i}(t))}\cdot\|x-\widetilde{x}\|_{2}$
$\displaystyle~{}+\frac{R}{\sigma_{\min}(\Sigma_{i}(t))}\cdot
2\alpha_{i}(t)\cdot\gamma^{-2}\cdot(\frac{1}{(2\pi)^{d}\det_{\min}}+\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\frac{|f_{i}(x)|}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$
$\displaystyle~{}+\frac{R}{\sigma_{\min}}\cdot
2\alpha_{i}(t)\cdot\gamma^{-2}\cdot(\frac{1}{(2\pi)^{d}\det_{\min}}+\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot\frac{R}{\sigma_{\min}}\cdot\|x-\widetilde{x}\|_{2}$
$\displaystyle=$
$\displaystyle~{}(\frac{|f_{i}(x)|}{\sigma_{\min}}+2\alpha_{i}(t)\cdot\gamma^{-2}\cdot(\frac{1}{(2\pi)^{d}\det_{\min}}+\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot(\frac{R}{\sigma_{\min}})^{2})\cdot\|x-\widetilde{x}\|_{2}$

where the first step follows from the bound of the first term and the second
term, the second step follows from the definition of
$\det_{\min},\sigma_{\max},\sigma_{\min}$, and the last step follows from
simple algebra. ∎

###  G.5 Lipschitz constant of the score function

This lemma calculates Lipschitz constant of the score function for $k$ mixture
of Gaussians.

######  Lemma G.11.

If the following conditions hold

  * •

Let $x,\widetilde{x}\in\mathbb{R}^{d}$.

  * •

Let $i\in[k]$.

  * •

Let $t\in\mathbb{R}$, and $t\geq 0$.

  * •

Let $\alpha_{i}(t)\in\mathbb{R}$, $\sum_{i=1}^{k}\alpha_{i}(t)=1$, and
$\alpha_{i}(t)\in(0,1)$.

  * •

Let $N_{i}(x)$ be defined as Definition G.1.

  * •

Let $p_{t}(x)$ be defined as Definition G.2.

  * •

Let $f_{i}(x)$ be defined as Definition G.4.

  * •

Let $\|x-\mu_{i}(t)\|_{2}\leq R$, where $R\geq 1$, for each $i\in[k]$.

  * •

Let $\|x-\mu_{i}(t)\|_{2}\geq\beta$, where $\beta\in(0,0.1)$, for each
$i\in[k]$.

  * •

Let $\sum_{i=1}^{k}\alpha_{i}(t)N_{i}(x)\geq\gamma$, where $\gamma\in(0,0.1)$.

  * •

Let
$\sigma_{\min}:=\min\\{\sigma_{\min}(\Sigma_{1}(t)),\sigma_{\min}(\Sigma_{2}(t)),\dots,\sigma_{\min}(\Sigma_{k}(t))\\}$.

  * •

Let
$\sigma_{\max}:=\max\\{\sigma_{\max}(\Sigma_{1}(t)),\sigma_{\max}(\Sigma_{2}(t)),\dots,\sigma_{\max}(\Sigma_{k}(t))\\}$.

  * •

Let
$\det_{\min}:=\min\\{\det(\Sigma_{1}(t)),\det(\Sigma_{2}(t)),\dots,\det(\Sigma_{k}(t))\\}$.

Then, we have

$\displaystyle~{}\|\frac{\mathrm{d}\log
p_{t}(x)}{\mathrm{d}x}-\frac{\mathrm{d}\log
p_{t}(\widetilde{x})}{\mathrm{d}\widetilde{x}}\|_{2}$ $\displaystyle\leq$
$\displaystyle~{}(\frac{1}{\sigma_{\min}}+\frac{2R^{2}}{\gamma^{2}\sigma_{\min}^{2}}\cdot(\frac{1}{(2\pi)^{d}\det_{\min}}+\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}}))\cdot\|x-\widetilde{x}\|_{2}$

###### Proof.

We can show

$\displaystyle~{}\mathrm{LHS}$ $\displaystyle=$
$\displaystyle~{}\|\sum_{i=1}^{k}f_{i}(x)(-\Sigma_{i}(t)^{-1}(x-\mu_{i}(t)))-\sum_{i=1}^{k}f_{i}(\widetilde{x})(-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t)))\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\sum_{i=1}^{k}\|f_{i}(x)(-\Sigma_{i}(t)^{-1}(x-\mu_{i}(t)))-f_{i}(\widetilde{x})(-\Sigma_{i}(t)^{-1}(\widetilde{x}-\mu_{i}(t)))\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\sum_{i=1}^{k}(\frac{|f_{i}(x)|}{\sigma_{\min}}+2\alpha_{i}(t)\cdot\gamma^{-2}\cdot(\frac{1}{(2\pi)^{d}\det_{\min}}+\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})\cdot(\frac{R}{\sigma_{\min}})^{2})\cdot\|x-\widetilde{x}\|_{2}$
$\displaystyle=$
$\displaystyle~{}(\frac{1}{\sigma_{\min}}+\frac{2R^{2}}{\gamma^{2}\sigma_{\min}^{2}}\cdot(\frac{1}{(2\pi)^{d}\det_{\min}}+\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}}))\cdot\|x-\widetilde{x}\|_{2}$

where the first step follows from Lemma G.5, the second step follows from
triangle inequality, the third step follows from Lemma G.10, and the last step
follows from $\sum_{i=1}^{k}|f_{i}(x)|=\sum_{i=1}^{k}f_{i}(x)=1$ and
$\sum_{i=1}^{k}\alpha_{i}(t)=1$. ∎

##  Appendix H Putting It All Together

Our overall goal is that we want to provide a more concrete calculation for
theorems in Section D by assuming the data distribution is a $k$ mixture of
Gaussian. Now we provide lemmas that are used in further calculation.

Now we provide the lemma for $k$-mixtue of Gaussians which states that if
$p_{0}$ is mixture Gaussians, then all the $\mathsf{pdf}$s in the diffusion
process are also mixtures of Gaussians.

######  Lemma H.1 (Formal version of Lemma 3.2).

Let $a,b\in\mathbb{R}$. Let ${\cal D}$ be a $k$-mixture of Gaussian
distribution, and let $p$ be its $\mathsf{pdf}$, i.e.,

$\displaystyle
p(x):=\sum_{i=1}^{k}\frac{\alpha_{i}}{(2\pi)^{d/2}\det(\Sigma_{i})^{1/2}}\exp(-\frac{1}{2}(x-\mu_{i})^{\top}\Sigma_{i}^{-1}(x-\mu_{i}))$

Let $x\in\mathbb{R}^{d}$ sample from ${\cal D}$. Let $z\in\mathbb{R}^{d}$ and
$z\sim{\cal N}(0,I)$, which is independent from $x$. Then we have a new random
variable $y=ax+bz$ which is also a $k$-mixture of Gaussian distribution
$\widetilde{\cal D}$, whose $\mathsf{pdf}$ is

$\displaystyle\widetilde{p}(x):=\sum_{i=1}^{k}\frac{\alpha_{i}}{(2\pi)^{d/2}\det(\widetilde{\Sigma}_{i})^{1/2}}\exp(-\frac{1}{2}(x-\widetilde{\mu}_{i})^{\top}\widetilde{\Sigma}_{i}^{-1}(x-\widetilde{\mu}_{i})),$

where
$\widetilde{\mu}_{i}=a\mu_{i},\widetilde{\Sigma}_{i}=a^{2}\Sigma_{i}+b^{2}I$.

###### Proof.

First, we know that the $\mathsf{pdf}$ of the sum of two independent random
variables is the convolution of their $\mathsf{pdf}$.

From [Vin04] we know that the convolution of 2 Gaussians is another Gaussian,
i.e.
$\mathcal{N}(\mu_{1},\Sigma_{1})*\mathcal{N}(\mu_{2},\Sigma_{2})=\mathcal{N}(\mu_{1}+\mu_{2},\Sigma_{1}+\Sigma_{2})$,
where $*$ is the convolution operator.

And we know the $\mathsf{pdf}$ of a linear transformation of a random variable
$x\in\mathbb{R}^{d}$, let’s say $Ax+b$ where $A\in\mathbb{R}^{d\times
d},b\in\mathbb{R}^{d}$, is $\frac{1}{|\det(A)|}p(A^{-1}(x-b))$.

If we consider the transformation $ax$ where
$a\in\mathbb{R},x\in\mathbb{R}^{d}$, this transformation can be written as
$aIx$. Therefore the $\mathsf{pdf}$ of $ax$ is
$\frac{1}{|\det(aI)|}p((aI)^{-1}x)=\frac{1}{|a^{d}|}p(x/a)$.

Now we prove the lemma. To find the $\mathsf{pdf}$ of $ax$, where $x\sim
p(x)$, we can show

$\displaystyle|\frac{1}{|a^{d}|}p(x/a)|=$
$\displaystyle~{}\frac{1}{|a^{d}|}\sum_{i=1}^{k}\frac{\alpha_{i}}{(2\pi)^{d/2}\det(\Sigma_{i})^{1/2}}\exp(-\frac{1}{2}(\frac{x}{a}-\mu_{i})^{\top}\Sigma_{i}^{-1}(\frac{x}{a}-\mu_{i}))$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{k}\frac{\alpha_{i}}{(2\pi)^{d/2}\det(a^{2}\Sigma_{i})^{1/2}}\exp(-\frac{1}{2}(x-a\mu_{i})^{\top}a^{-2}\Sigma_{i}^{-1}(a-a\mu_{i}))$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{k}\alpha_{i}\mathcal{N}(a\mu_{i},a^{2}\Sigma_{i})$

where the first step follows from the definition of $p(x)$, the second step
follows from $a^{2d}\det(\Sigma_{i})=\det(a^{2}\Sigma_{i})$, and the last step
follows from definition of Gaussian distribution.

For a single standard Gaussian random variable $z$, the $\mathsf{pdf}$ of $bz$
will simply be $\mathcal{N}(0,b^{2}I)$.

To find the $\mathsf{pdf}$ of $y=ax+bz$, we can show

$\displaystyle\widetilde{p}(x)=$
$\displaystyle~{}\frac{1}{|a^{d}|}p(x/a)*\mathcal{N}(0,b^{2}I)$
$\displaystyle=$
$\displaystyle~{}(\sum_{i=1}^{k}\alpha_{i}\mathcal{N}(a\mu_{i},a^{2}\Sigma_{i}))*\mathcal{N}(0,b^{2}I)$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{k}(\alpha_{i}\mathcal{N}(a\mu_{i},a^{2}\Sigma_{i})*\mathcal{N}(0,b^{2}I))$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{k}\alpha_{i}\mathcal{N}(a\mu_{i},a^{2}\Sigma_{i}+b^{2}I)$

where the first step follows from the $\mathsf{pdf}$ of the sum of 2
independent random variables is the convolution of their $\mathsf{pdf}$, the
second step follows from the $\mathsf{pdf}$ of $\frac{1}{|a^{d}|}p(x/a)$, the
third step follows from the distributive property of convolution, and the last
step follows from
$\mathcal{N}(a\mu_{i},a^{2}\Sigma_{i})*\mathcal{N}(0,b^{2}I)=\mathcal{N}(a\mu_{i},a^{2}\Sigma_{i}+b^{2}I)$.

Thus, the $\mathsf{pdf}$ of $y$ can be written as a mixture of $k$ Gaussians:

$\displaystyle\widetilde{p}(x):=\sum_{i=1}^{k}\frac{\alpha_{i}}{(2\pi)^{d/2}\det(\widetilde{\Sigma}_{i})^{1/2}}\exp(-\frac{1}{2}(x-\widetilde{\mu}_{i})^{\top}\widetilde{\Sigma}_{i}^{-1}(x-\widetilde{\mu}_{i})),$

where
$\widetilde{\mu}_{i}=a\mu_{i},\widetilde{\Sigma}_{i}=a^{2}\Sigma_{i}+b^{2}I$.
∎

Now we provide the lemma for the second momentum of $k$-mixtue of Gaussians.

######  Lemma H.2 (Formal version of Lemma 3.5).

If the following conditions hold:

  * •

$x_{0}\sim p_{0}$, where $p_{0}$ is defined by Eq. (9).

Then, we have

$\displaystyle m_{2}^{2}:=\operatorname*{{\mathbb{E}}}_{x_{0}\sim
p_{0}}[\|x_{0}\|_{2}^{2}]=\sum_{i=1}^{k}\alpha_{i}(\|\mu_{i}\|_{2}+\operatorname{tr}[\Sigma_{i}])$

###### Proof.

From [PKK22], we know the second momentum of data distribution $p_{0}(x)$ is
given by:

$\displaystyle\operatorname*{{\mathbb{E}}}[x_{0}x_{0}^{\top}]=\sum_{i=1}^{k}\alpha_{i}\cdot(\|\mu_{i}\|_{2}^{2}+\Sigma_{i})$
(23)

Then, we can show

$\displaystyle\operatorname*{{\mathbb{E}}}[\|x_{0}\|_{2}^{2}]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[x_{0}^{\top}x_{0}]$
$\displaystyle=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[\operatorname{tr}[x_{0}x_{0}^{\top}]]$
$\displaystyle=$
$\displaystyle~{}\operatorname{tr}[\operatorname*{{\mathbb{E}}}[x_{0}x_{0}^{\top}]]$
$\displaystyle=$
$\displaystyle~{}\operatorname{tr}[\sum_{i=1}^{k}\alpha_{i}(\mu_{i}\mu_{i}^{\top}+\Sigma_{i})]$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{k}\alpha_{i}(\|\mu_{i}\|_{2}^{2}+\operatorname{tr}[\Sigma_{i}])$

where the first step follows from definition of $\ell_{2}$-norm, the second
step follows from $\operatorname{tr}[aa^{\top}]=a^{\top}a$ where $a$ is a
vector, the third step follows from the linearity of the trace operator, the
fourth step follows from Eq. (23), and the last step follows from
$\operatorname{tr}[aa^{\top}]=\|a\|_{2}^{2}$. ∎

Now we give the Lipschitz constant explicitly.

######  Lemma H.3 (Formal version of Lemma 3.3).

If the following conditions hold

  * •

Let $\|x-a_{t}\mu_{i}\|_{2}\leq R$, where $R\geq 1$, for each $i\in[k]$.

  * •

Let $\|x-a_{t}\mu_{i}\|_{2}\geq\beta$, where $\beta\in(0,0.1)$, for each
$i\in[k]$.

  * •

Let $p_{t}(x)$ be defined as Eq. (10) and $p_{t}(x)\geq\gamma$, where
$\gamma\in(0,0.1)$.

  * •

Let
$\sigma_{\min}:=\min_{i\in[k]}\\{\sigma_{\min}(a_{t}^{2}\Sigma_{i}+b_{t}^{2}I)\\}$.

  * •

Let
$\sigma_{\max}:=\max_{i\in[k]}\\{\sigma_{\max}(a_{t}^{2}\Sigma_{i}+b_{t}^{2}I)\\}$.

  * •

Let $\det_{\min}:=\min_{i\in[k]}\\{\det(a_{t}^{2}\Sigma_{i}+b_{t}^{2}I)\\}$.

The Lipschitz constant for the score function
$\frac{\mathrm{d}\log(p_{t}(x))}{\mathrm{d}x}$ is given by:

$\displaystyle
L=\frac{1}{\sigma_{\min}}+\frac{2R^{2}}{\gamma^{2}\sigma_{\min}^{2}}\cdot(\frac{1}{(2\pi)^{d}\det_{\min}}+\frac{1}{(2\pi)^{d/2}\det_{\min}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max}})$

###### Proof.

Using Lemma G.11 and H.1, we can get the result. ∎

##  Appendix I More Calculation for Application

In this section, we will provide a more concrete calculation for Theorem D.5,
Theorem D.6, Theorem D.7, Theorem D.8 and Theorem D.9.

###  I.1 Concrete calculation of Theorem D.5

######  Theorem I.1 ($\mathsf{DDPM}$, total variation, formal version of
Theorem 5.6).

If the following conditions hold:

  * •

Condition 5.3 and 5.4.

  * •

The step size $h_{k}:=T/N$ satisfies $h_{k}=O(1/L)$ and $L\geq 1$ for
$k\in[N]$.

  * •

Let $\widehat{q}$ denote the density of the output of the
$\mathsf{EulerMaruyama}$ defined by Definition 4.3.

We have

$\displaystyle\mathrm{TV}(\widehat{q},p_{0})\lesssim\underbrace{\sqrt{\mathrm{KL}(p_{0}\|\mathcal{N}(0,I))}\exp(-T)}_{\mathrm{convergence~{}of~{}forward~{}process}}+\underbrace{(L\sqrt{dh}+Lm_{2}h)\sqrt{T}}_{\mathrm{discretization~{}error}}+\underbrace{\epsilon_{0}\sqrt{T}}_{\mathrm{score~{}estimation~{}error}}.$

where

  * •

$L=\frac{1}{\sigma_{\min(p_{t})}}+\frac{2R^{2}}{\gamma^{2}\sigma_{\min(p_{t})}^{2}}\cdot(\frac{1}{(2\pi)^{d}\det_{\min(p_{t})}}+\frac{1}{(2\pi)^{d/2}\det_{\min(p_{t})}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max(p_{t})}})$,

  * •

$m_{2}=(\sum_{i=1}^{k}\alpha_{i}(\|\mu_{i}\|_{2}^{2}+\operatorname{tr}[\Sigma_{i}]))^{1/2}$,

  * •

$\mathrm{KL}(p_{0}(x)\|\mathcal{N}(0,I))\leq\frac{1}{2}(-\log(\mathrm{det}_{\min(p_{0})})+d\sigma_{\max(p_{0})}+\mu_{\max(p_{0})}-d)$.

###### Proof.

Now we want to find a more concrete $L$ in Assumption D.1. Notice that from
Lemma H.1, we know that at any time between $0\leq t\leq T$, $p_{t}$ is also a
$k$-mixture of gaussian, except that the mean and covariance change with time.

Using Lemma H.3, we can get $L$.

Now we want to find the second momentum in Assumption D.2. Using Lemma H.2, we
know that
$m_{2}=(\sum_{i=1}^{k}\alpha_{i}(\|\mu_{i}\|_{2}^{2}+\operatorname{tr}[\Sigma_{i}]))^{1/2}$.

In Assumption 5.1, we also assume the same thing.

Now we want to have a more concrete setting for Theorem D.5 by calculating
each term directly. Notice that now we have all the quantities except for the
KL divergence term. Thus, we calculate $\mathrm{KL}(p_{0}\|\mathcal{N}(0,I))$,
which means the KL divergence of data distribution and standard Gaussian.

In our notation, we have

$\displaystyle\mathrm{KL}(p_{0}(x)\|\mathcal{N}(0,I))=$
$\displaystyle~{}\mathrm{KL}(\sum_{i=1}^{k}\alpha_{i}\mathcal{N}(\mu_{i},\Sigma_{i})\|\mathcal{N}(0,I))$
$\displaystyle=$
$\displaystyle~{}\int\sum_{i=1}^{k}\alpha_{i}\mathcal{N}(\mu_{i},\Sigma_{i})\log(\frac{\sum_{i=1}^{k}\alpha_{i}\mathcal{N}(\mu_{i},\Sigma_{i})}{\mathcal{N}(0,I)})\mathrm{d}x.$

However, this integral has no close form, but we can find an upper bound for
this KL divergence instead.

We know the KL divergence of 2 normal distribution is given by:

$\displaystyle~{}\mathrm{KL}(\mathcal{N}(\mu_{1},\Sigma_{1})\|\mathcal{N}(\mu_{2},\Sigma_{2}))$
$\displaystyle=$
$\displaystyle~{}-\frac{1}{2}\log(\frac{\det(\Sigma_{1})}{\det(\Sigma_{2})})+\frac{1}{2}\operatorname{tr}[(\Sigma_{2})^{-1}\Sigma_{1}]+\frac{1}{2}(\mu_{1}-\mu_{2})^{\top}(\Sigma_{2})^{-1}(\mu_{1}-\mu_{2})-\frac{d}{2}$

We define
$\sigma_{\max(p_{0})}=\max_{i\in[k]}\\{\sigma_{\max}(\Sigma_{i})\\}$,
$\det_{\min(p_{0})}=\min_{i\in[k]}\\{\det(\Sigma_{i})\\}$,
$\mu_{\max(p_{0})}=\max_{i\in[k]}\\{\|\mu_{i}\|_{2}^{2}\\}$. From [HO07], we
can show

$\displaystyle\mathrm{KL}(\sum_{i=1}^{k}\alpha_{i}\mathcal{N}(\mu_{i},\Sigma_{i})\|\mathcal{N}(0,I))\leq$
$\displaystyle~{}\sum_{i=1}^{k}\alpha_{i}\mathrm{KL}(\mathcal{N}(\mu_{i},\Sigma_{i})\|\mathcal{N}(0,I))$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{k}\frac{\alpha_{i}}{2}(-\log(\det(\Sigma_{i}))+\operatorname{tr}[\Sigma_{i}]+\|\mu_{i}\|_{2}^{2}-d)$
$\displaystyle\leq$
$\displaystyle~{}\max_{i\in[k]}\frac{1}{2}(-\log(\det(\Sigma_{i}))+\operatorname{tr}[\Sigma_{i}]+\|\mu_{i}\|_{2}^{2}-d)$
$\displaystyle\leq$
$\displaystyle~{}\frac{1}{2}(-\log(\mathrm{det}_{\min(p_{0})})+d\sigma_{\max(p_{0})}+\mu_{\max(p_{0})}-d)$

where the first step follows from the convexity of KL divergence, the second
step follows from KL divergence of 2 normal distribution, the third step
follows from $\sum_{i=1}^{k}\alpha_{i}=1$ and $0\leq\alpha_{i}\leq 1$, and the
last step follows from the definition of $\det_{\min(p_{0})}$,
$\sigma_{\max(p_{0})}$, $\mu_{\max(p_{0})}$.

Then we have all the quantities in Theorem D.5. After directly applying the
theorem, we finish the proof. ∎

###  I.2 Concrete calculation for Theorem D.6

######  Theorem I.2 ($\mathsf{DDPM}$, KL divergence, formal version of Theorem
5.7).

If the following conditions hold:

  * •

Condition 5.4.

  * •

We use uniform discretization points.

We have

  * •

Let $\widehat{q}$ denote the density of the output of the
$\mathsf{ExponentialIntegrator}$ defined by Definition 4.4, we have

$\displaystyle\mathrm{KL}(p_{0}\|\widehat{q})\lesssim(M_{2}+d)e^{-T}+T\epsilon_{0}^{2}+\frac{dT^{2}L^{2}}{N}.$

In particular, choosing $T=\Theta(\log(M_{2}d/\epsilon_{0}))$ and
$N=\Theta(dT^{2}L^{2}/\epsilon_{0}^{2})$, then we can show that

$\displaystyle\mathrm{KL}(p_{0}\|\widehat{q})=\widetilde{O}(\epsilon_{0}^{2})$

  * •

Let $\widehat{q}$ denote the density of the output of the
$\mathsf{EulerMaruyama}$ defined by Definition 4.3, we have

$\displaystyle\mathrm{KL}(p_{0}\|\widehat{q})\lesssim(M_{2}+d)e^{-T}+T\epsilon_{0}^{2}+\frac{dT^{2}L^{2}}{N}+\frac{T^{3}M_{2}}{N^{2}}.$

where

  * •

$L=\frac{1}{\sigma_{\min(p_{t})}}+\frac{2R^{2}}{\gamma^{2}\sigma_{\min(p_{t})}^{2}}\cdot(\frac{1}{(2\pi)^{d}\det_{\min(p_{t})}}+\frac{1}{(2\pi)^{d/2}\det_{\min(p_{t})}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max(p_{t})}})$,

  * •

$M_{2}=\sum_{i=1}^{k}\alpha_{i}(\|\mu_{i}\|_{2}^{2}+\operatorname{tr}[\Sigma_{i}])$.

###### Proof.

Using Lemma H.3, we can get $L$. Using Lemma H.2, we can get $m_{2}$. Then we
directly apply Theorem D.6. ∎

###  I.3 Concrete calculation for Theorem D.7

######  Theorem I.3 ($\mathsf{DDPM}$, KL divergence for smooth data
distribution, formal version of Theorem 5.8).

If the following conditions hold:

  * •

Condition 5.3 and 5.4.

  * •

We use the exponentially decreasing (then constant) step size
$h_{k}=c\min\\{\max\\{t_{k},\frac{1}{L}\\},1\\},c=\frac{T+\log
L}{N}\leq\frac{1}{Kd}$.

  * •

Let $\widehat{q}$ denote the density of the output of the
$\mathsf{ExponentialIntegrator}$ defined by Definition 4.4.

We have

$\displaystyle\mathrm{KL}(p_{0}\|\widehat{q})\lesssim(M_{2}+d)\exp(-T)+T\epsilon_{0}^{2}+\frac{d^{2}(T+\log
L)^{2}}{N},$

where

  * •

$L=\frac{1}{\sigma_{\min(p_{0})}}+\frac{2R^{2}}{\gamma^{2}(\sigma_{\min(p_{0})})^{2}}\cdot(\frac{1}{(2\pi)^{d}\det_{\min(p_{0})}}+\frac{1}{(2\pi)^{d/2}(\det_{\min(p_{0})})^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max(p_{0})}})$,

  * •

$M_{2}=\sum_{i=1}^{k}\alpha_{i}(\|\mu_{i}\|_{2}^{2}+\operatorname{tr}[\Sigma_{i}])$.

Furthermore, if we choosing $T=\Theta(\log(M_{2}d/\epsilon_{0}))$ and
$N=\Theta(d^{2}(T+\log L)^{2}/\epsilon_{0}^{2})$, then we can show

$\displaystyle\mathrm{KL}(p_{0}\|\widehat{q})\leq\widetilde{O}(\epsilon_{0}^{2})$

In addition, for Euler-Maruyama scheme defined in Definition 4.3, the same
bounds hold with an additional $M_{2}\sum_{k=1}^{N}h_{k}^{3}$ term.

###### Proof.

Clearly, $p_{0}$ is second-order differentiable. Using Lemma H.3, we can get
$L$. Using Lemma H.2, we can get $m_{2}$. Then we directly apply Theorem D.7.
∎

###  I.4 Concrete calculation for Theorem D.8

######  Theorem I.4 ($\mathsf{DPOM}$, formal version of Theorem 5.9).

If the following conditions hold:

  * •

Condition 5.4.

  * •

We use the $\mathsf{DPOM}$ algorithm defined in Definition 4.5, and let
$\widehat{q}$ be the output density of it.

We have

$\displaystyle\mathrm{TV}(\widehat{q},p_{0})\lesssim(\sqrt{d}+m_{2})\exp(-T)+L^{2}Td^{1/2}h_{\mathrm{pred}}+L^{3/2}Td^{1/2}h_{\mathrm{corr}}^{1/2}+L^{1/2}T\epsilon_{0}+\epsilon.$

where

  * •

$L=\frac{1}{\sigma_{\min(p_{t})}}+\frac{2R^{2}}{\gamma^{2}\sigma_{\min(p_{t})}^{2}}\cdot(\frac{1}{(2\pi)^{d}\det_{\min(p_{t})}}+\frac{1}{(2\pi)^{d/2}\det_{\min(p_{t})}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max(p_{t})}})$,

  * •

$m_{2}=(\sum_{i=1}^{k}\alpha_{i}(\|\mu_{i}\|_{2}^{2}+\operatorname{tr}[\Sigma_{i}]))^{1/2}$.

In particular, if we set $T=\Theta(\log(dm_{2}/\epsilon))$,
$h_{\mathrm{pred}}=\widetilde{\Theta}(\frac{\epsilon}{L^{2}d^{1/2}})$,
$h_{\mathrm{corr}}=\widetilde{\Theta}(\frac{\epsilon}{L^{3}d})$, and if the
score estimation error satisfies
$\epsilon_{0}\leq\widetilde{O}(\frac{\epsilon}{\sqrt{L}})$, then we can obtain
TV error $\epsilon$ with a total iteration complexity of
$\widetilde{\Theta}(L^{3}d/\epsilon^{2})$ steps.

###### Proof.

Using Lemma H.3, we can get $L$. Using Lemma H.2, we can get $m_{2}$. Then we
directly apply Theorem D.8. ∎

###  I.5 Concrete calculation for Theorem D.9

######  Theorem I.5 ($\mathsf{DPUM}$, formal version of Theorem 5.10).

If the following conditions hold:

  * •

Condition 5.4.

  * •

We use the $\mathsf{DPUM}$ algorithm defined in Definition 4.6, and let
$\widehat{q}$ be the output density of it.

We have

$\displaystyle\mathrm{TV}(\widehat{q},p_{0})\lesssim(\sqrt{d}+m_{2})\exp(-T)+L^{2}Td^{1/2}h_{\mathrm{pred}}+L^{3/2}Td^{1/2}h_{\mathrm{corr}}^{1/2}+L^{1/2}T\epsilon_{0}+\epsilon.$

where

  * •

$L=\frac{1}{\sigma_{\min(p_{t})}}+\frac{2R^{2}}{\gamma^{2}\sigma_{\min(p_{t})}^{2}}\cdot(\frac{1}{(2\pi)^{d}\det_{\min(p_{t})}}+\frac{1}{(2\pi)^{d/2}\det_{\min(p_{t})}^{1/2}})\cdot\exp(-\frac{\beta^{2}}{2\sigma_{\max(p_{t})}})$,

  * •

$m_{2}=(\sum_{i=1}^{k}\alpha_{i}(\|\mu_{i}\|_{2}^{2}+\operatorname{tr}[\Sigma_{i}]))^{1/2}$.

In particular, if we set $T=\Theta(\log(dm_{2}/\epsilon))$,
$h_{\mathrm{pred}}=\widetilde{\Theta}(\frac{\epsilon}{L^{2}d^{1/2}})$,
$h_{\mathrm{corr}}=\widetilde{\Theta}(\frac{\epsilon}{L^{3/2}d^{1/2}})$, and
if the score estimation error satisfies
$\epsilon_{0}\leq\widetilde{O}(\frac{\epsilon}{\sqrt{L}})$, then we can obtain
TV error $\epsilon$ with a total iteration complexity of
$\widetilde{\Theta}(L^{2}d^{1/2}/\epsilon)$ steps.

###### Proof.

Using Lemma H.3, we can get $L$. Using Lemma H.2, we can get $m_{2}$. Then we
directly apply Theorem D.9. ∎

## References

  * [ABDH+18] Hassan Ashtiani, Shai Ben-David, Nicholas Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan.  Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes.  Advances in Neural Information Processing Systems, 31, 2018.
  * [ADLS17] Jayadev Acharya, Ilias Diakonikolas, Jerry Li, and Ludwig Schmidt.  Sample-optimal density estimation in nearly-linear time.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1278–1289. SIAM, 2017.
  * [And82] Brian DO Anderson.  Reverse-time diffusion equation models.  Stochastic Processes and their Applications, 12(3):313–326, 1982.
  * [BDD23] Joe Benton, George Deligiannidis, and Arnaud Doucet.  Error bounds for flow matching methods.  arXiv preprint arXiv:2305.16860, 2023.
  * [BDJ+22] Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M Kane, Pravesh K Kothari, and Santosh S Vempala.  Robustly learning mixtures of k arbitrary gaussians.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1234–1247, 2022.
  * [BK20] Ainesh Bakshi and Pravesh Kothari.  Outlier-robust clustering of non-spherical mixtures.  arXiv preprint arXiv:2005.02970, 2020.
  * [BS10] Mikhail Belkin and Kaushik Sinha.  Polynomial learning of distribution families.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 103–112. IEEE, 2010.
  * [BS23] Rares-Darius Buhai and David Steurer.  Beyond parallel pancakes: Quasi-polynomial time guarantees for non-spherical gaussian mixtures.  In The Thirty Sixth Annual Conference on Learning Theory, pages 548–611. PMLR, 2023.
  * [CCL+22] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang.  Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions.  arXiv preprint arXiv:2209.11215, 2022.
  * [CCL+23] Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim.  The probability flow ode is provably fast.  Advances in Neural Information Processing Systems, 36, 2023.
  * [CDD23] Sitan Chen, Giannis Daras, and Alex Dimakis.  Restoration-degradation beyond linear diffusions: A non-asymptotic analysis for ddim-type samplers.  In International Conference on Machine Learning, pages 4462–4484. PMLR, 2023.
  * [CDSS13] Siu-On Chan, Ilias Diakonikolas, Xiaorui Sun, and Rocco A Servedio.  Learning mixtures of structured distributions over discrete domains.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1380–1394. SIAM, 2013.
  * [CHZW23] Minshuo Chen, Kaixuan Huang, Tuo Zhao, and Mengdi Wang.  Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data.  In International Conference on Machine Learning, pages 4672–4712. PMLR, 2023.
  * [CK11] Imre Csiszár and János Körner.  Information theory: coding theorems for discrete memoryless systems.  Cambridge University Press, 2011.
  * [CKS24] Sitan Chen, Vasilis Kontonis, and Kulin Shah.  Learning general gaussian mixtures with efficient score matching.  arXiv preprint arXiv:2404.18893, 2024.
  * [CLL23] Hongrui Chen, Holden Lee, and Jianfeng Lu.  Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions.  In International Conference on Machine Learning, pages 4735–4763. PMLR, 2023.
  * [CZZ+20] Nanxin Chen, Yu Zhang, Heiga Zen, Ron J Weiss, Mohammad Norouzi, and William Chan.  Wavegrad: Estimating gradients for waveform generation.  arXiv preprint arXiv:2009.00713, 2020.
  * [Das99] Sanjoy Dasgupta.  Learning mixtures of gaussians.  In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 634–644. IEEE, 1999.
  * [DHKK20] Ilias Diakonikolas, Samuel B Hopkins, Daniel Kane, and Sushrut Karmalkar.  Robustly learning any clusterable mixture of gaussians.  arXiv preprint arXiv:2005.06417, 2020.
  * [DK14] Constantinos Daskalakis and Gautam Kamath.  Faster and sample near-optimal algorithms for proper learning mixtures of gaussians.  In Conference on Learning Theory, pages 1183–1213. PMLR, 2014.
  * [DK20] Ilias Diakonikolas and Daniel M Kane.  Small covers for near-zero sets of polynomials and learning latent variable models.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 184–195. IEEE, 2020.
  * [DKK+19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.  Robust estimators in high-dimensions without the computational intractability.  SIAM Journal on Computing, 48(2):742–864, 2019.
  * [FOS08] Jon Feldman, Ryan O’Donnell, and Rocco A Servedio.  Learning mixtures of product distributions over discrete domains.  SIAM Journal on Computing, 37(5):1536–1564, 2008.
  * [GKL24] Khashayar Gatmiry, Jonathan Kelner, and Holden Lee.  Learning mixtures of gaussians using diffusion models.  arXiv preprint arXiv:2404.18869, 2024.
  * [GLB+24] Hanzhong Guo, Cheng Lu, Fan Bao, Tianyu Pang, Shuicheng Yan, Chao Du, and Chongxuan Li.  Gaussian mixture solvers for diffusion models.  Advances in Neural Information Processing Systems, 36, 2024.
  * [GLL+24] Jiuxiang Gu, Chenyang Li, Yingyu Liang, Zhenmei Shi, and Zhao Song.  Exploring the frontiers of softmax: Provable optimization, applications in diffusion model, and beyond.  arXiv preprint arXiv:2405.03251, 2024.
  * [HJA20] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  Advances in neural information processing systems, 33:6840–6851, 2020.
  * [HO07] John R Hershey and Peder A Olsen.  Approximating the kullback leibler divergence between gaussian mixture models.  In 2007 IEEE International Conference on Acoustics, Speech and Signal Processing-ICASSP’07, volume 4, pages IV–317. IEEE, 2007.
  * [HRX24] Yinbin Han, Meisam Razaviyayn, and Renyuan Xu.  Neural network-based score estimation in diffusion models: Optimization and generalization.  In The Twelfth International Conference on Learning Representations, 2024.
  * [KFL22a] Dohyun Kwon, Ying Fan, and Kangwook Lee.  Score-based generative modeling secretly minimizes the wasserstein distance.  Advances in Neural Information Processing Systems, 35:20205–20217, 2022.
  * [KFL22b] Dohyun Kwon, Ying Fan, and Kangwook Lee.  Score-based generative modeling secretly minimizes the wasserstein distance.  Advances in Neural Information Processing Systems, 35:20205–20217, 2022.
  * [KLL+24] Dongjun Kim, Chieh-Hsin Lai, Wei-Hsiang Liao, Naoki Murata, Yuhta Takida, Toshimitsu Uesaka, Yutong He, Yuki Mitsufuji, and Stefano Ermon.  Consistency trajectory models: Learning probability flow ODE trajectory of diffusion.  In The Twelfth International Conference on Learning Representations, 2024.
  * [KPH+20] Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro.  Diffwave: A versatile diffusion model for audio synthesis.  arXiv preprint arXiv:2009.09761, 2020.
  * [LKB+23a] Jae Hyun Lim, Nikola B Kovachki, Ricardo Baptista, Christopher Beckham, Kamyar Azizzadenesheli, Jean Kossaifi, Vikram Voleti, Jiaming Song, Karsten Kreis, Jan Kautz, et al.  Score-based diffusion models in function space.  arXiv preprint arXiv:2302.07400, 2023.
  * [LKB+23b] Jae Hyun Lim, Nikola B Kovachki, Ricardo Baptista, Christopher Beckham, Kamyar Azizzadenesheli, Jean Kossaifi, Vikram Voleti, Jiaming Song, Karsten Kreis, Jan Kautz, et al.  Score-based diffusion models in function space, 2023.  URL https://arxiv. org/abs/2302.07400, 2023.
  * [LLT22] Holden Lee, Jianfeng Lu, and Yixin Tan.  Convergence for score-based generative modeling with polynomial complexity.  Advances in Neural Information Processing Systems, 35:22870–22882, 2022.
  * [LS17] Jerry Li and Ludwig Schmidt.  Robust and proper learning for mixtures of gaussians via systems of polynomial inequalities.  In Conference on Learning Theory, pages 1302–1382. PMLR, 2017.
  * [MV10] Ankur Moitra and Gregory Valiant.  Settling the polynomial learnability of mixtures of gaussians.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 93–102. IEEE, 2010.
  * [ND21] Alexander Quinn Nichol and Prafulla Dhariwal.  Improved denoising diffusion probabilistic models.  In International conference on machine learning, pages 8162–8171. PMLR, 2021.
  * [NRW21] Eliya Nachmani, Robin San Roman, and Lior Wolf.  Non gaussian denoising diffusion models.  arXiv preprint arXiv:2106.07582, 2021.
  * [Ope24] OpenAI.  Video generation models as world simulators, 2024.  https://openai.com/research/video-generation-models-as-world-simulators.
  * [PKK22] João M Pereira, Joe Kileel, and Tamara G Kolda.  Tensor moments of gaussian mixture models: Theory and applications.  arXiv preprint arXiv:2202.06930, 2022.
  * [PX23] William Peebles and Saining Xie.  Scalable diffusion models with transformers.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4195–4205, 2023.
  * [RBL+22] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10684–10695, 2022.
  * [RFB15] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In Medical image computing and computer-assisted intervention–MICCAI 2015: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pages 234–241. Springer, 2015.
  * [RGKZ21] Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová.  Classifying high-dimensional gaussian mixtures: Where kernel methods fail and neural networks succeed.  In International Conference on Machine Learning, pages 8936–8947. PMLR, 2021.
  * [SCK23] Kulin Shah, Sitan Chen, and Adam Klivans.  Learning mixtures of gaussians using the ddpm objective.  Advances in Neural Information Processing Systems, 36:19636–19649, 2023.
  * [SCL+22] Zhenmei Shi, Jiefeng Chen, Kunyang Li, Jayaram Raghuram, Xi Wu, Yingyu Liang, and Somesh Jha.  The trade-off between universality and label efficiency of representations from contrastive learning.  In The Eleventh International Conference on Learning Representations, 2022.
  * [Sco15] David W Scott.  Multivariate density estimation: theory, practice, and visualization.  John Wiley & Sons, 2015.
  * [SDCS23] Yang Song, Prafulla Dhariwal, Mark Chen, and Ilya Sutskever.  Consistency models.  In Proceedings of the 40th International Conference on Machine Learning, pages 32211–32252, 2023.
  * [SDME21] Yang Song, Conor Durkan, Iain Murray, and Stefano Ermon.  Maximum likelihood training of score-based diffusion models.  Advances in neural information processing systems, 34:1415–1428, 2021.
  * [SDWMG15] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.  Deep unsupervised learning using nonequilibrium thermodynamics.  In International conference on machine learning, pages 2256–2265. PMLR, 2015.
  * [SE19] Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  Advances in neural information processing systems, 32, 2019.
  * [SE20] Yang Song and Stefano Ermon.  Improved techniques for training score-based generative models.  Advances in neural information processing systems, 33:12438–12448, 2020.
  * [SGSE20] Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon.  Sliced score matching: A scalable approach to density and score estimation.  In Uncertainty in Artificial Intelligence, pages 574–584. PMLR, 2020.
  * [SHC+22] Chitwan Saharia, Jonathan Ho, William Chan, Tim Salimans, David J Fleet, and Mohammad Norouzi.  Image super-resolution via iterative refinement.  IEEE transactions on pattern analysis and machine intelligence, 45(4):4713–4726, 2022.
  * [SK21] Yang Song and Diederik P Kingma.  How to train your energy-based models.  arXiv preprint arXiv:2101.03288, 2021.
  * [SMF+24] Zhenmei Shi, Yifei Ming, Ying Fan, Frederic Sala, and Yingyu Liang.  Domain generalization via nuclear norm regularization.  In Conference on Parsimony and Learning, pages 179–201. PMLR, 2024.
  * [SOAJ14] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour.  Near-optimal-sample estimators for spherical gaussian mixtures.  Advances in Neural Information Processing Systems, 27, 2014.
  * [SSDK+20] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  arXiv preprint arXiv:2011.13456, 2020.
  * [SWL21] Zhenmei Shi, Junyi Wei, and Yingyu Liang.  A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features.  In International Conference on Learning Representations, 2021.
  * [SWL24] Zhenmei Shi, Junyi Wei, and Yingyu Liang.  Provable guarantees for neural networks via gradient feature learning.  Advances in Neural Information Processing Systems, 36, 2024.
  * [Vin04] Susana Vinga.  Convolution integrals of normal distribution functions.  Supplementary material to Vinga and Almeida (2004)“Rényi continuous entropy of DNA sequences, 2004.
  * [WCL+24] Yuchen Wu, Minshuo Chen, Zihao Li, Mengdi Wang, and Yuting Wei.  Theoretical insights for diffusion guidance: A case study for gaussian mixture models.  arXiv preprint arXiv:2403.01639, 2024.
  * [XSW+23] Zhuoyan Xu, Zhenmei Shi, Junyi Wei, Fangzhou Mu, Yin Li, and Yingyu Liang.  Towards few-shot adaptation of foundation models via multitask finetuning.  In The Twelfth International Conference on Learning Representations, 2023.
  * [YFZ+23] Zhantao Yang, Ruili Feng, Han Zhang, Yujun Shen, Kai Zhu, Lianghua Huang, Yifei Zhang, Yu Liu, Deli Zhao, Jingren Zhou, et al.  Lipschitz singularities in diffusion models.  In The Twelfth International Conference on Learning Representations, 2023.
  * [ZHF+24] Jianbin Zheng, Minghui Hu, Zhongyi Fan, Chaoyue Wang, Changxing Ding, Dacheng Tao, and Tat-Jen Cham.  Trajectory consistency distillation.  arXiv preprint arXiv:2402.19159, 2024.