How Much is a  Noisy Image Worth? Data Scaling Laws for Ambient Diffusion.
Authors: Giannis Daras
Yeshwanth Cherapanamjeri
Constantinos Costis Daskalakis
Venue: ICLR 2025 Poster (2025)
Keywords: ambient diffusion
noisy data
dataset design
gaussian mixtures
Primary area: generative models
TL;DR: We study the scaling behaviors of models trained with corrupted data and we find that for training on a combination of a small set of clean images and a large set of noisy images suffices for near state-of-the-art performance.

Abstract: The quality of generative models depends on the quality of the data they are trained on. Creating large-scale, high-quality datasets is often expensive and sometimes impossible, e.g.~in certain scientific applications where there is no access to clean data due to physical or instrumentation constraints. Ambient Diffusion and related frameworks train diffusion models with solely corrupted data (which are usually cheaper to acquire) but ambient models significantly underperform models trained on clean data. We study this phenomenon at scale by training more than $80$ models on data with different corruption levels across three datasets ranging from $30,000$ to $\approx 1.3$M samples. We show that it is impossible, at these sample sizes, to match the performance of models trained on clean data when only training on noisy data. Yet, a combination of a small set of clean data (e.g.~$10\%$ of the total dataset) and a large set of highly noisy data suffices to reach the performance of models trained solely on similar-size datasets of clean data, and in particular to achieve near state-of-the-art performance. We provide theoretical evidence for our findings by developing novel sample complexity bounds for learning from Gaussian Mixtures with heterogeneous variances. Our theoretical model suggests that, for large enough datasets, the effective marginal utility of a noisy sample is exponentially worse that of a clean sample. Providing a small set of clean samples can significantly reduce the sample size requirements for noisy data, as we also observe in our experiments.

Published as a conference paper at ICLR 2025
How MUCH IS A NOISY IMAGE WORTH?
DATA SCALING LAWS FOR AMBIENT DIFFUSION.
Giannis Daras*
Yeshwanth Cherapanamjeri
Costantinos Daskalakis
CSAIL
CSAIL
CSAIL
MIT, IFML
MIT
MIT
gdaras@mit. edu
yesh@mi edu
costis@csal il 1.mmmtt.... edu
ABSTRACT
The quality of generative models depends on the quality of the data they are trained on. Creat- ing large-scale, high-quality datasets is often expensive and sometimes impossible, e.g. in certain scientific applications where there is no access to clean data due to physical or instrumentation con- straints. Ambient Diffusion and related frameworks train diffusion models with solely corrupted data (which are usually cheaper to acquire) but ambient models significantly underperform models trained on clean data. We study this phenomenon scale by training more than 80 models data with different corruption levels across three datasets ranging from 30, 000 to z 1.3M samples. We show that it is impossible, at these sample sizes, to match the performance of models trained on clean data when only training on noisy data. Yet, a combination of a small set of clean data (e.g. 10% of the total dataset) and large set of highly noisy data suffices to reach the performance of models trained solely on similar-size datasets of clean data, and in particular achieve near state-of-the-art performance. We provide theoretical evidence for our findings by developing novel sample com- plexity bounds for learning from Gaussian Mixtures with heterogeneous variances. Our theoretical model suggests that, for large enough datasets, the effective marginal utility of a noisy sample is exponentially worse that of a clean sample. Providing a small set of clean samples can significantly reduce the sample size requirements for noisy data, as we also observe in our experiments.
1 INTRODUCTION
A key factor behind the remarkable success of modern generative models, from image Diffusion Models (DMs) to Large Language Models (LLMss,, is the curation of large scale datasets (Gadre et al. [023 Li al. 2024). However, in certain applications, access to high-quality data is scarce, expensive, or impossible. For example, in Magnetic Resonance Imaging (MRI) the quality of the data is proportional to the time spent in the scanner (Jalal al. 2021
and, in black-hole imaging, it is never possible to get full measurements from the object of interest (L.in et al. 2024
Constructing a (copyright-free) large-scale dataset of high-quality general domain images is also an expensive and complex process. Enterprise text-to fext-to-ing text-to-image image DMs rely on proprietary datasets, often acquired from third-party vendors at significant cost (Betker et al., 2023
2024). State-of-the-an open-source DMs are typically trained by crawling a large pool of images from the Web and filtering them for quality with a pipeline that deems each sample suitable or non-suitable for training (Gadre et al. samples is problematic because often low-quality images still contain useful information. For example, a blurry image might get dismissed from the filtering pipeline to avoid blurry generations at inference time, yet the image might still contain important information about the world, such as the type of objects present at the scene.
et al.
2023). However, this binary treatment of
Recently, there has been a growing interest in developing frameworks for training generative models using corrupted data, c.g. from blurry noisy images (Bora et al. 2018 Daras al. 2023b: Kawar et al. 2023 Aali al. 2023
Daras et al., 2024 Bai et al. 2024, Rozet et al. 2024 Wang et al. 2024 Kelkar et al.) 2023). Most frameworks that are applicable to diffusion models introduce training or sampling approximations, which significantly hurt performance. A recent work, Consistent Diffusion Meets Tweedie (Daras et al.) 2024). proposes a method that guarantees exact sampling, at least asymptotically as the number of noisy samples tends to infinity. For realistic sample sizes, however,
"Equal contribution.

---

Published as a conference paper at ICLR 2025
Imagenet FID
12
p% clean
pR and 12 11.p/% noiy (Sigma:
Figure 1: ImageNet FID performance (lower is better) for models trained with different amounts of clean and noisy data. Perfor- mance of models trained with only clean data (red curve) reduces as we decrease the amount of data used. Training with purely noisy data (right- most points) also gives poor performance - even if 100% of the dataset is available. Training with a mix of noisy and clean data strikes an inter- esting balance: model trained with 90% noisy and 10% clean data is almost as good as a model trained with 100% clean data.
p7% clean and (1/p)% noisy (Sigma: 0.1)
10
p7% clean and f1-p7%% noisy iSigmm: 0.05)
90%% moloy dati
F10
10% clean data
Performance almost constant despite having less clean data as long noisy data
100%
60%
40%
0%
models Number of clean stated fraccion of total ImagaNet size, on noisy using
(of any proposed method) are significantly inferior to models
trained on clean data. How do we overcome this challenge?
A fundamental limitation facing existing approaches for leveraging corrupted data is that, so far, they have been studied under the assumption that no access to clean samples is available. As we show in this work, it is theoretically and experimentally impossible to compensate for the lack of clean data without a significant hit (that is exponential in the number of classes in our theoretical analysis) in the number of noisy datapoints. On the other hand, we show that a combination of a small set of clean images (e.g. 10% of the total dataset) and a large set of noisy images (e.g. 90% of the total dataset) suffices maintain state-of-the-art performance. Models trained on this data mixture significantly outperform two natural baselines: i) training only on the small set of clean images; and ii) training only on the large set of noisy images (see also Figure 1 and Table D. We validate our finding by training more than 80 models across various noise scales and corruption ratios on ImageNet, CelebA-HQ, and CIFAR-10.
Theoretically. we consider novel variant of the classical problem of learning Gaus- sian Mixture Models (GMMs) with hetero-
Available Data
CIFAR-10
CelebA
ImageNet
100% clean
1.99
2.40=0.07
1.41=0.03
geneous noise levels. In contrast to the clas-
100% noisy
11 11.9310..09
12.97
5.02
sical setting, each sample is generated with a (potentially) different noise level reflec- tive of how clean or noisy the data point is. We derive minimax optimal estimation rates, which showcase the differing utility of clean and noisy data. Concretely, having lots of noisy data enables identification of the right low-dimensional structure for learning the mixture components, while more moderate number of clean data allows fine-grained differentiation of the com- ponents in low dimensions. In particular, effective learning is possible even when the number of clean samples is substantially smaller than the dimension. At the same time, relying solely on noisy data requires exponentially (in the number of components) noisy samples than clean ones. This theoretical result could justify why training on a mixture of clean and noisy data significantly outperforms training solely on either one of the clean or the noisy sets. In summary, our contributions are as follows:
10% clean (smaller dataset)
17.30+0.14 14
11.92=0.05
10.57+0.06 06
90% noisy + 10% clean
2.802
2.75=0.02
1.68=0.02
Table 1: FID scores for models trained on datasets with different per- centages of noisy and clean data. Training with a mix of 90% noisy and 10% clean data achieves much better performance than training the same num- ber of purely noisy samples, or just the clean samples.
We train more than 80 models at different datasets, noise levels and corruption ratios.
We show that as long as few clean images are available, models trained with corrupted data perform par with models trained on clean data. We further show that training on a combination of a small set of clean images and a large set of noisy images significantly outperforms training solely on either one of these sets. We provide a thcoretical explanation for this phenomenon by developing novel sample complexity bounds for the case of GMMs with heterogeneous variances. Our minimax rates show that the availability of noisy data removes the polynomial dependence dimension in the number of clean samples while simultaneously showing exponentially more noisy samples are required to compensate for the lack of clean data.
2

---

Published as a conference paper at ICLR 2025
Through our theoretical analysis and our experimental validation, we pinpoint the price of noisy images for different datasets and noise levels. These insights can potentially guide budget allocation for dataset curation.
2 BACKGROUND AND RELATED WORK
2.1 DIFFUSION MODELING
The dominant paradigm for learning distributions is diffusion models. A diffusion model is trained to denoise images
at different levels of additive Gaussian noise (Ho et al. 2020; Song Ermon 2019 Song et al. 2020b). To establish some notation, we will & E [0, T] for the diffusion time and or for the associated standard deviation of the added noise. Let Xo Po be sample from the distribution of interest and let X, Pt sample of the noisy distribution at
time t, where it holds that X, Xo + 2, Z ~ (0,, I). At training time, the goal is to learn x = xt for all levels t. Diffusion models are trained to approximate this quantity using the following objective
(Viceet 2011 I
JDSM (0) Baor-p R2 Be (a Xo=zo)
(0 t) zooll
(1)
Once trained, the model is used for sampling following discretized version of the update rule (Song et al. 2020b
dx, = do, (31, t) xt.
that is guaranteed to sample from Po given that it is initialized from pr and ha( f) there are errors due to initialization, discretization, and improper learning of the score (Chen et al. 2022 2023).
x X, xz). In practice,
2.2 LEARNING DIFFUSION MODELS FROM NOISY DATA
The training objective of Equation| I requires access to data from the distribution Po- We will refer to this data as clean for the rest of this paper. As explained in the Introduction, in many applications access clean data is scarce and hence methods for training diffusion models from corrupted data have been developed.
Ambient Diffusion (Daras et al. 2023b) proposes a framework to train diffusion models from linear measurements.
An alternative framework to Ambient Diffusion leverages Stein's s Unbiased Risk Estimate (SURE) (Kawar et al. 2023]
Aali al. 2023). These works extend classical results for training restoration models from corrupted data (Moran
et al. 2020 Stein 1981 Xu et al. 2020 Pang et al. 2021 Krull al. 2019 Batson & Royer 2019) to the setting of learning generative models under corruption. Unfortunately, these methods induce sampling approximations that significantly hurt the performance. A different thread of papers on this topic relies on the Expectation-Maxxiizatioo
(EM) algorithm (Bai et al. 2024] Rozet et al., [024 Wang et al. (0024). The convergence of these models to the true distribution depends on the convergence of the EM algorithm, which might get stuck in local minimum.
Consistent Diffusion Meets Tweedie (Daras al. 2023a 2024) generalized Ambient Diffusion handle additive Gaussian noise and became the first framework with provably exact sampling given infinite (noisy) data. In what follows, we give brief description of the method, since we are going to use this in the rest of this paper.
Problem Setting. Assume that we are given samples at a specific noise level In (nature noise level). The question becomes how we can leverage these samples to learn the optimal denoiser [ X, xx] for all noise levels t.
Learning the optimal denoiser for high noise levels. The first task is to learn the optimal denoiser for t > t,, To perform this goal, one can leverage the following Lemma:
Lemma 2.1 Daras et al. 2. Let Xt,. = Xo + oi, Z1 and X, = Xo or for any a, > ot,,, we have that:
Zi. Zz (O,, i.idd Then,
of
0² Tt.
E| X, 11 of
E[X,, X, x..
(3)
of o
removes all
removes additiional
'In practice, non-uniform distribution for t and loss weighting w(t) often used Karras al.
2022
3

---

Published as a conference paper at ICLR 2025
This Lemma states that to remove all the noise there is, it suffices to remove the noise that we added on top of the dataset noisy samples from the R. V. Xt, One can train the denoiser E X X, = mr] with supervised learning, as in The following loss will train the network to estimate X X = Øt] directly:
Equation] I
o oi of
o xt Bin (2,, t)
Jmmiien: DSM Em,, Min, Et Bu m
(4)
of
This idea is closely related to Noisier2Noise (Morn et al. 2020). We underline that there are also alternative ways to learn the optimal denoiser in this regime, such as SURE (Seein 1981). However, SURE-based methods usually bring computational overhead, as one needs to compute (or approximate) a Jacobian Vector Product.
Learning the optimal denoiser for low noise levels. Learning the optimal denoiser for < f, is significantly harder problem since there is no available data in this regime. Most of the prior works did not even attempt to solve this problem. At training time, a denoiser (x,,,, 1) is trained for all L > l.- At sampling time, one can: i) also use he for times & < ty. even though the model was not trained in this regime, hoping that the neural network will extrapolate in a meaningful way, or ii) truncate the sampling at time en. by predicting čy- = ho t.). In Algorithm of the Appendix, we provide a reference implementation of the truncated sampling idea. A more principled attempt was introduced by Daras et al. (2024) where the authors attempt to learn the optimal denoiser for low noise levels by enforcing a consistency loss. Specifically, for t < tn. the network is trained with the following objective:
F.m, Ee la, ho (rze, 1') - -E. (2) [ho (aver, l' ('I1I"]
00) = E
(5)
where po is the distribution induced by the SDE version of Equation 2 (we refer the interested reader to the works of Song et al. (2200)). Daras et al. (202a)). Assuming that the network has been perfectly trained to predict E[Xa] o X, =
Øt] for all times > tn. the minimizer of this loss will be E[X, X = xz| also for times < fn. There are a few important drawbacks though. First, the consistency loss adds a significant training overhead since at each training step: i) expectations need to be computed and ii) sampling steps need to be performed. Second, the theoretical guarantees only hold given perfect learning of the conditional expectation for > in and it is unclear how errors propagate. Finally, even for slight corruption, the method leads to significant performance deterioration (Daras et al. 2024).
3 METHOD
Problem Setting. The need for consistency or sampling approximations arises from the fact that we do not have samples train the network in the regime L (4n, Oj. We relax this assumption by considering the setting where small set of clean and a large set of noisy images are available. To establish the notation, let's use Sclean to denote the clean set and Suotey to denote the noisy set. The clean samples are realizations of the R. Xo ~ Po and the noisy samples realizations of the V.V. X,, = -x + ot Z for some fixed noise level tn-
Training algorithm. Our training algorithm leverages samples from both sets. For times E [L,, Oj. we will rely solely on clean samples. On the other hand, fort E tn), we will leverage both the clean and the noisy samples. The clean samples will be used as usual, following the Denoising Score Matching objective, defined in Equation [ The noisy samples in this regime will utilize Equation 4 to learn denoiser by relating it to the quantity E[,,,,, t.. Xx =x]] through the use of Lemma 2.
(see Algorithm
Method Discussion. In prior work (Daras et al. 2024), the optimal denoiser for times t < tx was learned through the (expensive) consistency loss. In our setting, we assume access to a small set of clean images that we are using to learn the optimal denoiser for these times. The question then becomes: "does small set of clean images suffice to learn the optimal denoiser for low-noise levels?" As show in this paper, the answer to this question is affirmative, i.e. we only need handful of uncorrupted images to learn the optimal denoiser for low corruption.
The intuition is as follows. To learn the distribution, we need to be able to generate accurately both structural infor- mation (low-frequencies) and texture content. The addition of noise corrupts the fighhfrey content faster (for discussion, see Dieleman (2024)). Hence, noisy images are mostly useful to learn the low-frequency content of the distribution, i.e. they are useful to learn to generate structure. Humans, and metrics that are trying to model human preferences (such FID), are more
Clean samples have both low-frequency and figh-freeuency
4

---

Published as a conference paper at ICLR 2025
Algorithm Algorithm for training using both clean and noisy samples.
Input: untrained network hg, set of clean samples Sclean set of noisy samples Snoisy, std of the noise ot,, batch size B, diffusion time T, noisy diffusion start time in
while not converged do Form batch B of size uniformly sampled from Sclean Snoiey
loss f- 0
Initialize loss.
4: for each sample E B do
5:
<~ (0,
> Sample noise.
if Sposay then
It, t
We are dealing with a noisy sample, Sample diffusion time for noisy sample.
~ U(tn; T)
Dt Tt, +
03 - of
Add additional noise.
10:
loss + loss
ot ai-
ho(
ogg at It..
Ambient Denoising Score Matching loss.
of
11:
else
12:
Ey f- x ~ ((, T)
D We are dealing with a clean sample. b Sample diffusion time for clean sample, Add additional noise. Regular Denoising Score Matching loss.
13:
14:
2y 3o + osF
15:
loss + loss (2,,( t) xol?
16:
end if
17:
end for
18:
loss f- loss
A Compute mean loss. D Update network parameters via backpropagation.
B
19:
B V Vooos
20:
end while
perceptible to errors in structural information than errors in the high-entropy image texture. So even though it might be impossible to perfectly generate going to penalize these errors less, given that the model can accurately generate the low-frequency content.
content using only a few clean images, metrics, such as FID, are
The method we developed in Algorithm can be trivially extended to more than two of points. In fact, each point in the training set can have its own noise level 4. In that case, algorithm would use each point æ; to learn the optimal denoiser for t > t.. For the case of presentation, we stick to two noise levels for the rest of this paper. Further, if the noise level ot,, is not known, it can be estimated by computing the difference of the variances between the sets Sclenn and Snoiay-
4 THEORETICAL RESULTS
Before presenting our experiments, we establish theoretical results that will support our experimental findings. We note that most theoretical works on distribution learning operate under the assumption of i.i.d samples from a fixed distribution. In contrast, the goal our paper is to understand the effects that heterogeneity in sample quality has on estimation error. This setting is quite niche and creates space for interesting theory to be developed.
We develop our results for the Gaussian Mixture Model that is commonly used in diffusion theory (Shah et al. 2023
Gatmiry et al.) 2024 Gu et al., 2024; Chidambaram et al.) 2024 Li & Chen, 2024] Cui et al. 2023 Chen et al.
2024
We examine the following adaptation of the classical estimation problem to the heterogeneous setting:
Definition 4.1. We are given X,....,
Ei,...,,,,, X,, independently drawn from the following distribution:
X, D +0 where D wromp
where o, denotes the Dirac distribution μ and the convolution operator. The goal is output D minimizing:
W W1 D) min E Exxxx)=olIX- X'II C(D.))
where C(D, D) is coupling of D, with marginals equal to D and D.
5

---

Published as a conference paper at ICLR 2025
Note now that variance in sample quality can now be naturally expressed in terms of the noise level, S,, of the individual observations with the larger d; denoting lower-quality samples and vice-versa.
4.1 MAIN THEORETICAL. RESULTS AND DISCUSSION
Overview of Theoretical Results. Theorems 4.2 and 4.4 and Corollary 4.3 establish tight bounds the sample complexity of learning heterogeneous mixture-of -fGaasssinnn model which precisely characterize the utilities of high and low-quality samples. These theoretical results match the intuition from [Section 3 where noisy data is useful for learning low-frequency information while clean data helps in resolving high-frequency details. Concretely, the low-dimensional subspace spanned by the means of the GMM model corresponds to the low-frequency information estimated from the noisy samples while the resolution of the mixture components in the lower-dimensional space corresponds the high-frequency information extracted from the clean samples. Hence, the heterogeneous mixture of Gaussians model provides concrete instantiations of the intuition previously presented. These results further define the notion of the effective number of samples which captures how much actual information is in our dataset accounting for the per-sample corruption. This notion motivates the data pricing questions asked in Subsection 5.3
samples
dimension
classes
Theorem 4.2 (Upper bound). Let n, d. k N, R>
and ō (0, 1/21 Suppose 'D Ei wrSpp is Then, there is a procedure Algorithm 8) which when given n.
k-atomic distribution over Bad with ||m|l| & R.
independent samples Xn such that X; ~ D * N(0, 1 with 0; > 1 satisfying:
# effective samples
02
Σ i=1
max o & (d logglo(()00))) (1))))
max 2 a
log(1/6) + k log(k)
4k-2
0i
and 0, returns an estimate D with:
dimensionality reduction error
low-dim estimation error
1/4 d + logooo1111 (1/8) D. 1/0
k loo k + log(1/6)
1/(4k
(D,,DD &C
+ 1.
Σi_ 1/0 4h-2
with probability at least 1 - 8. Furthermore, the runtime of the algorithm is Öz(nd).
Discussion. The full proof of this result is given in Appendix C We adopt two-stage procedure where in the first stage we reduce the dimensionality of the problem, from the dimension d, to the number of components, k, by estimating the sub-space containing the means, μ4g and projecting all our data points onto that subspace. Next, we run a low-dimensional estimation procedure on the k-dimensional projected data (Algorithm to estimate the means within the subspace. The two terms in the error bound reflect the contributions of each of these steps. The first corresponds to the error in estimating the low-dimensional sub-space and the second corresponds the error of the low-dimensional estimation procedure. The two conditions (on max 1/0 and max 1/0," -2 lower bound the effective number of samples for the dimensionnlity-redutiiio and low-dimensional estimation steps respectively. The first requires at least (effective) samples for dimensionality reduction while at least are available for low-dimensional estimation.
Observing the terms of the bound, we see that, compared the high-quality points, the low-quality points have relatively more utility in the dimensionality-redee reduutioo step versus the nower-dimensionae estimation step. This obser- vation is made clearer in the following corollary in the simplified setting with 2 noise levels.
Percentage of "clean" points
Corollary 4.3. Assume the setting of Theorem 4.2 that 01, .1..... pm and ppn+1, ..... On T.
Furthermore, suppose that for [0, 1). we additionally have Then, the guarantees of Theorem 4.2 reduce
1/1
1/(1k-2)
d log(1/8)
l: log k log(1/5)
Wi(D,D) &C
+ 1.3
n(p+ (1 p)/pp///)
n n + (1 - p) / 1k 1k-2
Factor for dim. reduction
Factor for fine-grained estimation
6

---

Published as a conference paper at ICLR 2025
We see that the noisy samples are downweighted only by 1/o² for the dimensionality-reduce step whereas for the fine-grained estimation procedure, its discounting is much more substantial at 1/o Next, we present a matching lower bound establishing that the rate achieved by Theorem 4.2 optimal for learning with heterogenous samples. Theorem 4.4 (Lower bound). Let N. Let n, N. 8 E (0, 1/4), and {o,) 2 be such that and:
Σ
11
1 (CR))k-1 log(1/0) and
Σ
"
> C(d + log(1/8)
o.
For any estimator T, there exists a k-atomic distribution D supported on B3 such that for X ~ II D o00,0,)
Px { Wi( > cmax
d 1og(1/11))) Σ 1/0,
1/4
1
1/(4k- 2)
> 6.
k
log(115)
4k-2
In the remainder of the section, we present proof of the upper bound (Theorem 4.2) in the simplified setting of d = 1.
4.2 PROOF: ONE-DIMENSIONA SETTING
We draw upon the approach of Wu & Yang (2020) for the homogeneous setting. We start by recalling some notation from Wu & Yang 2020). For 1 E N and distribution, D, over I::
(D)
Ex=D [x'] and m;(D) = [mo mi (D),...,
The estimator of Wu & Yang 2020) utilizes the Hermite polynomials defined as: H1) = r! "/ ح x x"-2)
(n/21 (-1/2)
These polynomials satisty the following crucial denoising property: (xw.in,11|H,, p=".. Linearity of expecta- tion now allows for denoising general convolutions with Gaussians:
Lr/2]
(-1/2)²
= (no = o' H",,/o/))
Σ 1=0 ((r--j))
0 24 22 satisfies EX=D-N(ux>)(Tho(XX) EX-D|X"].
Hence, they allow approximate recovery of the moments of the k-atomic distribution that was convolved with a Gaus- sian to produce the final mixture. The main issue with this approach is that the moments are only recovered approxi- mately. The following technical result, implicit in Wu & Yang (2020) and proved in Appendix B shows that error in estimating the moments can be directly translated to an error in Wasserstein distance in an estimation procedure.
Lemma 4.1. (Wu & Yang (0200), Let k E N. E [0, Let 'D be a k-atomic distribution supported on [-1, 1] and Mi...., (22-1 1 be estimates satisfying m. - m, (D) & 8 for all i E [2k -1. 1]. Then there is a procedure running in time O& (1), which on input [m=] 2k-1 returns distribution D satisfying:
WD, D) < O(kk2.r).
Finally, the error in the moment estimates can be bounded by the variance of the Hermite polynomials. Lemma 4.5 (Wu& & Yang 22220). Let M 0 and X D (N0 with D supported [-M, M). Then, Vr E N: (X)) & (O(M +
Lemma 4.5 and Lemma 4.1 now reduce the problem of estimating the parameters of the mixture to that of estimating its first 2 moments. Our algorithm is presented in |lAloriihhm The key step in the algorithm is the addition of the weights, a;, which down-weight samples with large variance. These weights are chosen to minimize the variance of obtained moment estimates. Intuitively, samples with large variance are less reliable and their contributions discounted. Interestingly, the degree of down weighting also scales with the complexity of the distribution, measured by k. Next, we formally establish the correctness of Algorrihh 3 through the following simplified theorem.
Theorem 4.6. Let M > 1 be constant and k. E N. Suppose 'D is a k-atomic distribution supported on [-M, M) and that X = { are generated as X, ~ D * NO0 of) with a; 2 1. Then, Algorithm 3 given as input X and {ar (vE()) returns with probubility at least 3/4 k-alomic distribution DD satisfying:
-1((ak-2)
Wi(D,D) < CKK.
Σ 2k-2 o
7

---

Published as a conference paper at ICLR 2025
Proof. We start by rescaling the distribution so that M = 1. Next, we get from Lemma 4.5
that for all E [2k- 1]:
a Var(m,) L (Tr,,, (X.))
= (CVR)
Σ
0
4k-2
Therefore, we get by a consequence of Chebyshev's inequality for any r E 12k- -1:--1; 1|:
Im, m,l & 4Vkom
with probability at least 1 - 1/16k. Hence, we get by the union bound:
Vr E [2k 1I: : m, m.r
< 4v kom
with probability at least 3/4. Conditioned on this event, Lemma 4.1 concludes the proof of the theorem.
The proof of the high-dimensional setting is presented in Appendix C Algorithmically, the high-dimensional setting uses two different weighting schemes; one for computing the appropriate now-dimensional subspace that is indepen- dent of l and another for an exhaustive search algorithm similar to Doss et al. (2023). Furthermore, our algorithm and analysis diverge from and refine the results of Doss al. (2023). Consequently, the dependence on the failure probability improved from v (10) to the optimal (1/)) 17(1K-2) dependence. Our key technical improvement is due to a robustness analysis on the approximation of the high-dime dimensional Wasserstein distance by one-dimensional projections (seenApp C.2). This allows bypassing the chaining- based arguments Doss et al. (2023) and instead employing a median-of- -feanss based approach with a simple covering number argument.
5
EXPERIMENTS
5.1 TRAINING ONLY WITH CORRUPTED DATA
We start our experimental section by presenting results in the setting of prior work (Daras et al. 2024 2023b). i.e. using only noisy data. We train models at three different levels of corruption: i) a = 0.05, ii) o = 0.1, iii) = 0.2, across three different datasets of different sizes: CIFAR- 10 (60K samples), CelebA-HQ (30K samples) and ImageNet (<s 1.3M images). We underline that prior work (Daras et al., 2024) only finetuned with noisy data. Instead, we opt for training from scratch which allows to measure different quantities of interest in more controlled setting.
For reference, we visualize the corruption levels in Figure 3 We train models with and without consistency. For our experiments, training with consistency was 2-3x slower and used 2x GPUs. The full experimental results are provided in Appendix[] F For the models without consistency, we report results for both truncated (see Algorithm 2 and full sampling. For the models trained with consistency, we report results for the full sampling algorithm, as consistency is supposed to help mostly with times < ln- The results of this experiment are summarized in Table The findings are the following: i) the results very poor for model trained without consistency when the full-sampling algorithm is used, i.e. the model cannot extrapolate to times t < t,, if it was only trained for times t > fx, ii) Truncated Sampling helps, but still, even for low corruptions, (e.g. for a = 0.05) the performance is relatively weak, and, iii) training with consistency is beneficial, particularly for a = 0.05 and a = 0.1, but as the corruption increases the benefits of it are shrinking. Another interesting observation is that the performance deteriorates less (for the same corruption level) compared to the clean performance as the dataset size grows. This expected: in the limit of infinite data, models trained with solely noisy data can still, in theory, perfectly recover the distribution (Daras et al., 2024). That said, even for ImageNet level datasets, at high corruption the best performance, obtained by training with the expensive consistency loss, is significantly inferior to the performance obtained by training with clean data.
5.2 TRAINING WITH A MIXTURE OF CLEAN AND NOISY DATA
The previous experiments showed that training with solely highly noisy data leads to a significant performance deteri- oration, at least for datasets with sizes up to ImageNet, and this also comes at a significant computational cost because of the consistency loss. But what a small set of clean images is available? Arguably, this setting is fairly realistic since the dataset design process one can spend some initial effort (measured in money, computation, or otherwise) to collect some high-quality data points and then rely on cheaper noisy points for the rest of the dataset. To the best of our knowledge, this setting has not been explored by prior work. To study this, fix the dataset size and we change
8

---

Published as a conference paper at ICLR 2025
Dataset
Noise Level
Full Sampling
Truncated Sampling
Consistency Full Sampling
0.00
1.99 +0.02
NA
NA
0.05
8.78 10.02
4.53 10.08
2.82 10.02
CIFAR-10
0.10
25.55 10.10
7.55 10.07
3.63 10.03
0.20
60.73 +0.21
12.12 +0.03
11.93 +0.00
0.00
2.40 +0.07
NA 6.73 +o.02
NA 5.50 +0.03
0.05
12.77 +0.02
Ce
0.10
45.90 +0.08
10.27 +o.01
9.38 +0.02
0.20
61.14 1:.14
13.90 10.01
12.97 10.11
0.00
1.41 +0.03
NA 2.53 10.01
NA 2.26 10.01
0.05
2.39 $0.01
ImageNet
0.10
6.23 +0.01
3.67 10.01
2.99 10.05
0.20
18.08 +0.06
6.03 +0.02
5.32 +0.08
Table 2:
FID comparisons between models trained solely noisy data across datasets and noise levels. In the first two columns, we report results without consistency training, with and without sampling truncation. Training with consistency (third col.) significantly improves the results, but the performance is still poor compared to the clean data training for high corruption.
the percentage p% of clean data. For every value of p (0.0, 0.3, 0.5, 0.7, 1.0, we train models with: i) p% clean data, and, ii) with p% clean data and (1 p)% of noisy data at different levels of noise. To train with both clean and noisy data we used the method described in Section 3 and in A We underline that for these experiments we do not use consistency loss and hence the training cost stays the same as training with clean data.
We report our results in Table 3 and we highlight subset of the results in Table I The results show that even when we have 90% noisy data and high-corruption, i.e. 0.2, the performance stays near the state-of-the-art long as small set (10%) of clean data is available. In fact, the obtained performance is far superior to the performance obtained by training only with clean data and the performance obtained by training with only noisy data, indicating that the benefit comes from the mixture of the two. The difference is quite dramatic: i) 10% clean ImageNet samples = 10.57 FID, ii) 100% noisy samples (at a = 0.2) + 5.32 FII, iii) 90% noisy samples and 10% clean samples + 1.68 FID. This phenomenon is further illustrated in Figure [
Table 3: FID comparisons as we change the mix of clean and noisy data. Data availability is reported as percentage of the total dataset size: 60K for CIFAR, 30K for CelebA-HQ and ze 1.3M for ImageNet. Training with mix of clean and noisy data is significantly better than training purely on a few clean data points or purely on the full noisy dataset.
Noise Level
Dataset
Available Data
% of clean data
100%
90%
70%
50%
30%
10%
0%
ImageNet Cetebt-11 1 CIFAR-10
5% clean
N/A
2.07
2 2.200
2.40#c0.2
3.99
17.30en.4
N/A
0.05
1.99
2. 2.0420.2
2.04
2.06a oo
2.1120.0a
2.17a0.00 04
8.78a0
5% clean, (1-p)% noisy
0.10
2.06=0.cs
2.1ds
2.15+0.01
2.24+0.02
2.31+c.0 os
25.55=0..0
0.20
2.0620ca
2.14
2.24
2.4220.05
2.1140
60. 63.73.
5% clean
N/A
2.50en.1
2.68++..co
2.83+0.01
3.72+0.01
11.92+0.co
NIA
0.05
2.40 o.or
2.40eno0
2.15+001
2.15e0..2
2.50+0.01
2,50+e 02
12 77=
1l clean, (1-p)% noisy
0.10
2.40g001
2.
2.51
2.5110001
2.67
45.9020..0
0.20
2.50xaco
2.51
2.52+6.01
2.67#0.02
2,75 02
G1. 11
5% clean
N/A
1.30
1.65xo..1
2.15
4.34
10.37
NIA
0.05
1..0
1.46eac22
1.46:0.22
1.46+0.02
1.47+0.02
1.51+c.02
2.40+o.02
5% clean, (1-p)% noisy
0.10
1.48
1.484002
1.494600
1.4929.01
1.5740.02 02
6.23
0.20
1.50enca
1.51+0.22
1.51+0.2
1.59+s.05
1.68+c.02
18.08-a.0
We test the limits of our method by evaluating it in extreme corruption, either in terms of number of clean samples or in terms of the amount of noise. For computational reasons, we only present these results for CIFAR-10.
Higher corruption. We use 90% noisy and 10% clean data and we increase the corruption to a = 0.4. The FID becomes 3.56 + 0.03, which is still much better than the performance (17.30) obtained by using 10% of clean data.
Less clean data. We fix 0.2 and we severely decrease the number of clean data. Specifically, we evaluate perfor- mance when 1% of clean data and 99% of noisy data are available. The performance of this model is 3.53 0.03. For
9

---

Published as a conference paper at ICLR 2025
reference, the performance of the model trained with 100% noisy data at this noise level is 60.73 without Truncated Sampling and 11.93 with consistency training. Hence, 1% of clean data has a tremendous effect in performance.
5.3 How MUCH IS A NOISY IMAGE WORTH?
How much exactly is a noisy image worth? In what follows, we address the question of data pricing. Given finite resources for data curation, how should we allocate them to obtain the best performance? On the flip side, what a fair pricing scheme that reflects data utility? We approach this through the notion of effective sample size suggested by our theoretical model. Let:
1/04
T D 1/0,h-2
max; 1/0
max; 1/O,K-2'
be the two terms that appear in the bound of Theorem 4.2 Assume that we operate in the asymptotic setting with large n and with the fraction of clean and noisy data bounded away from by a constant independent of n. In this regime, the dominant term in Theorem 4.2 is the second due to its slower rate of convergence. Therefore, the effective sample size for low-dimensional estimation, 74, is the main determinant of the emror
This implies that we can use a fixed pricing scheme, largely independent of the sample size n. To validate this theoretical prediction, let's price clean samples at 1$ per unit and noisy samples at &, per unit, for a parameter Co that we will bound using data from our experiments. Specifically, to bound Co we can derive inequalities by comparing performances from Table For example, the CIFAR-10 10 performance using 90% clean data is 2.07 which is better than the 2.42 FID performance obtained using 30% clean and 70% noisy samples at 0.2, which implies that:
0.9n > 0.3n + Co.20.7n = Co.2 &
We repeat this computation for all pairs of the table and derive more inequalities. We restrict comparisons to settings with least 10% clean samples to ensure we remain in the asymptotic regime. The best upper and lower bounds are:
CIFAR-10, CelebA:
1.17 &
1.25
ImageNet:
1.125 E
1.17
00.05
00.05
CIFAR-10, CelebA:
1.25 <
<
1.5
ImageNet:
1.125 <
<
1.17
C0.1
C0.1
1
CIFAR-10, CelebA, ImageNet: 1.5
<
1.75
Co.2
The quantity 1/c, measures the number of noisy samples required to compensate for a clean one. In line with intuition, for larger values of (i.e. the noisier the sample), more noisy samples required to replace clean one. In addition, this ratio is the lowest for the largest dataset, ImageNet. The narrow ranges of the upper and lower bounds, lend credibility to this data pricing approach. Finer-grid evaluation at Table would allow for even narrower estimates.
6 LIMITATIONS AND FUTURE WORK
In this paper, we only studied the case of additive Gaussian Noise corruption. In practice, the corruption might be more complex or even unknown. We further focused on the scale of having two noise levels, i.e. clean data and noisy data. The approach can be naturally extended to arbitrary many noise levels. Further, all the results in this work were developed for pixel-space diffuuson models. A promising avenue for future research is to extend these findings to latent diffusion models. Finally, due to the high computational training requirements, we were only able to scale up to ImageNet and 64 64 resolution. It is worth exploring how these behaviors change as we further increase the dimension and the dataset size. On the theory side, our Gaussian Mixtures Model might not capture all the intricacies of real distributions and while being a useful tool, we should always interpret these results with caution.
ACKNOWLEDGMENTS
This research has been supported by NSF Grants AF 1901292, CNS 2148141, Tripods CCF 1934932, IFML CCF 2019844 and research gifts by Western Digital, Amazon, WNCG IAP, UT Austin Machine Learning Lab (MLL),
10

---

Published as a conference paper at ICLR 2025
Cisco and the Stanly P. Finch Centennial Professorship in Engineering. Constantinos Daskalakis has been supported by NSF Awards CCF-1901292, 292, DMS-2022448 and DMS-2134108, a Simons Investigator Award, and the Simons Collaboration on the Theory of Algorithmic Fairness. Giannis Daras has been supported by the Onassis Fellowship the Bodossaki Fellowship and the Leventis Fellowship.
(Scholarship ID: FZS 012- 1/1011/22222223)//
REFERENCES
Asad Aali, Marius Arvinte, Sidharth Kumar, and Jonathan I Tamir. Solving inverse problems with score-based gener- ative priors learned from noisy data. arXiv preprint arXiv:2305.01166, 2023.
Weimin Bai, Yifei Wang, Wenzheng Chen, and He Sun. An expectation-maxiiizatio algorithm for training clean diffusion models from corrupted observations. arXiv preprint arXiv:2407.01014, 2024.
Joshua Batson and Loic Royer. Noise2self: Blind denoising by self-supervision. In International Conference Machine Learning, pp. 524-533. PMLR, 2019.
James Betker, Gabriel Goh, Li Jing, Tim Brooks, Jianfeng Wang. Linjie Li, Long Ouyang, Juntang Zhuang, Joyce Lee, Yufei Guo, al. Improving image generation with better captions. Computer Science. https:/lcdn. openai. com/papers/dall-e33 pdf. 2:3, 2023.
Ashish Bora, Eric Price, and Alexandros G Dimakis. Ambientgan: Generative models from lossy measurements. International conference on learning representations, 2018
J. Bretagnolle and C. Huber. Estimation des densités: risque minimax. Z. Wahrsch. Verw. Gebiete, 1792)1119-137, 1979. ISSN 0044-3719. doi: 10.1007/BFO0S33278. Uttpstss: //coi 2ttp://00.001100/////333337
Clément L. Canonne. A short note on an inequality between kl and tv, 2023. URL
2202. 07198
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy as learning the score: theory for diffusiin models with minimal data assumptions. arXiv preprint arXiv:2209.12215. 2022.
Sitan Chen, Giannis Daras, and Alex Dimakis. Restoration-degraaatti beyond linear diffusions: A non-asymptotic analysis for DDIM-type samplers. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 4462 4484. PMLR, 23-29 Jul 2023. URL //proceedings... m wwwpspresssSse 2ttss///222ccche2eeeee .tmll
Sitan Chen, Vasilis Kontonis, and Kulin Shah. Learning general gaussian mixtures with efficient score matching, arXiv preprint arXiv:2204./8899 2024.
Muthu Chidambaram, Khashayar Gatmiry, Sitan Chen, Holden Lee, and Jianfeng Lu. What does guidance do? fine-grained analysis in simple setting. arXiv preprint arXiv:2409.13077 2024.
Hugo Cui, Florent Krzakala, Eric Vanden-Eijnden, and Lenka Zdeborová. Analysis of learning a flow-based generative model from limited sample complexity. arXiv preprint arXiv:2310.03575, 2023.
Giannis Daras, Yuval Dagan, Alexandros G Dimakis, and Constantinos Daskalakis. Consistent diffusion models: Mitigating sampling drift by learning to be consistent. arXiv preprint arXiv:2302.09057. 2023a.
Giannis Daras, Kulin Shah, Yuval Dagan, Aravind Gollakota, Alex Dimakis, and Adam Klivans. Ambient diffusion: Learning clean distributions from corrupted data. Thirty-sevnnth Conference on Neural Information Processing 2023b.
Giannis Daras, Alexandros G Dimakis, and Constantinos Daskalakis. Consistent diffusion meets tweedie: Training exact ambient diffusion models with noisy data. arXiv preprint arXiv:2404.10177, 2024.
Sander Dieleman. Diffusion is spectral autoregression, 2024.
URL http///anderrree wttpm/ee...//22//9///// /
spectral pecetrallauttoee att.reaalaattoreeessii.o.o.....
11

---

Published as a conference paper at ICLR 2025
Natalie Doss. Yihong Wu, Pengkun Yang, and Harrison H. Zhou. Optimal estimation of high high-dimensional Gaussian location mixtures. Ann. Statist., 51(1):62-95, 2023. ISSN 0090-5364. doi: 10.1214/22-a0s2207. URL htttps:
//60i.0xg/1..1214/222
aos2207
Samir Yitzhak Gadre, Gabriel Ilharco, Alex Fang, Jonathan Hayase, Georgios Smymnis, Thao Nguyen, Ryan Marten, Mitchell Wortsman, Dhruba Ghosh, Jieyu Zhang, et al. Datacomp: In search of the next generation of multimodal datasets, arXiv preprint arXiv:2304. 14108, 2023.
Khashayar Gatmiry, Jonathan Kelner, and Holden Lee. Learning mixtures of gaussians using diffusion models. arXiv preprint arXiv:2404.18800 2024.
Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Unraveling the smoothness properties of diffusion models: A gaussian mixture perspective. arXiv preprini arXiv:2405. 16418, 2024.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-665 1851, 2020.
Imagen-Team-Google. :, Jason Baldridge, Jakob Bauer, Mukul Bhutani, Nicole Brichtova, Andrew Bunner, Kelvin Chan, Yichang Chen, Sander Dieleman, Yuqing Du, Zach Eaton-Rosen, Hongliang Fei, Nando de Freitas, Yilin Gao, Evgeny Gladchenko, Sergio Gómez Colmenarejo, Mandy Guo, Alex Haig, Will Hawkins, Hexiang Hu, Huil- ian Huang. Tobenna Peter Igwe, Christos Kaplanis, Siavash Khodadadeh, Yelin Kim, Ksenia Konyushkova, Karol Langner, Eric Lau, Shixin Luo, Soña Mokrá, Henna Nandwani, Yasumasa Onoe, Aäron van den Oord, Zarana Parekh, Jordi Pont-Tuset. Hang Qi, Rui Qian. Deepak Ramachandran, Poorva Rane, Abdullah Rashwan, Ali Robert Riachi, Hansa Srinivasan, Srivatsan Srinivasan, Robin Strudel, Benigno Uria, Oliver Wang, Su Wang, Austin Waters, Chris Wolff, Auriel Wright, Zhisheng Xiao, Hao Xiong, Keyang Xu, Marc van Zee, Junlin Zhang, Katie Zhang. Wenlei Zhou, Konrad Zolna, Ola Aboubakar, Canfer Akbulut, Oscar Akerlund, Isabela Albuquerque, Nina Anderson, Marco Andreetto, Lora Aroyo, Ben Bariach, David Barker, Sherry Ben, Dana Berman, Courtney Biles, Irina Blok, Pankil Botadra, Jenny Brennan, Karla Brown, John Buckley, Rudy Bunel, Elie Bursztein, Christina Butterfield, Ben Caine, Viral Carpenter, Norman Casagrande, Ming-Wei Chang, Solomon Chang, Shamik Chaud- huri, Tony Chen, John Choi, Dmitry Churbanau, Nathan Clement, Matan Cohen, Forrester Cole, Mikhail Dek- tiarev, Vincent Du, Praneet Dutta, Tom Eccles, Ndidi Elue, Ashley Feden, Shlomi Fruchter, Frankie Garcia, Roopal Garg, Weina Ge, Ahmed Ghazy, Bryant Gipson, Andrew Goodman, Dawid Górny, Sven Gowal, Khyatti Gupta, Yoni Halpem, Yena Han, Susan Hao, Jamie Hayes, Amir Hertz, Ed Hirst, Tingbo Hou, Heidi Howard, Mohamed Ibrahim, Dirichi Ike-Njoku, Joana Iljazi, Vlad Ionescu, William Isaac, Reena Jana, Gemma Jennings, Donovon Jenson, Xuhui Jia, Kerry Jones, Xiaoen Ju, Ivana Kajic, Christos Kaplanis, Burcu Karagol Ayan, Jacob Kelly, Suraj Kothawade, Christina Kouridi, Ira Ktena, Jolanda Kumakaw, Dana Kurniawan, Dmitry Lagun, Lily Lavitas, Jason Lee, Tao Li, Marco Liang, Maggie Li-Calis, Yuchi Liu, Javier Lopez Alberca, Peggy Lu, Kristian Lum, Yukun Ma, Chase Malik, John Mellor, Inbar Mosseri, Tom Murray, Aida Nematzadeh, Paul Nicholas, João Gabriel Oliveira, Guillermo Ortiz-Jimenez, Michela Pagannii, Tom Le Paine, Roni Paiss, Alicia Parrish, Anne Peckham, Vikas Peswani, Igor Petrovski, Tobias Pfaff, Alex Pirozhenko, Ryan Poplin, Utsav Prabhu, Yuan Qi, Matthew Rahtz, Cyrus Rashtchian, Charvi Rastogi, Amit Raul, Ali Razavi, Sylvestre-Alvise Rebuffi, Susanna Ricco, Fe- lix Riedel, Dirk Robinson, Pankaj Rohatgi, Bill Rosgen, Sarah Rumbley, Moonkyung Ryu, Anthony Salgado, Sahil Singla, Florian Schroff, Candice Schumann, Tanmay Shah, Brendan Shillingford, Kaushik Shivakumar, Den- nis Shtatnov, Zach Singer, Evgeny Sluzhaev, Valerii Sokolov, Thibault Sottiaux, Florian Stimberg, Brad Stone, David Stutz, Yu-Chuan Su, Eric Tabellion, Shuai Tang, David Tao, Kurt Thomas, Gregory Thornton, Andeep Toor, Cristian Udreseu, Aayush Upadhyay, Cristina Vasconcelos, Alex Vasiloff, Andrey Voynov, Amanda Walker, Luyu Wang, Miaosen Wang, Simon Wang, Stanley Wang, Qifei Wang. Yuxiao Wang. Ágoston Weisz, Olivia Wiles, Chenxia Wu, Xingyu Federico Xu, Andrew Xue, Jianbo Yang, Luo Yu, Mete Yurtoglu, Ali Zand, Han Zhang, Jia- geng Zhang, Catherine Zhao, Adilet Zhaxybay, Miao Zhou, Shengqi Zhu, Zhenkai Zhu, Dawn Bloxwich, Mahyar Bordbar, Luis C. Cobo. Eli Collins, Shengyang Dai, Tulsee Doshi, Anca Dragan, Douglas Eck, Demis Hassabis, Sissie Hsiao, Tom Hume, Koray Kavukcuoglu, Helen King, Jack Krawezyk, Yeqing Li, Kathy Andras Orban, Yury Pinsky, Amar Subramanya, Oriol Vinyals, Ting Yu, and Yori Zwols. Imagen 3, 2024. URL fetps://arrist org/ ab/a/////2/4 07009)
Razavi,
Ajil Jalal, Marius Arvinte Giannis Daras, Eric Price, Alexandros G Dimakis, and Jon Tamir. Robust compressed sensing mri with deep generative priors. Advances in Neural Information Processing Systems, 34:14938-14958 14954, 2021.
12

---

Published as a conference paper at ICLR 2025
Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion uuffusion-based generative models. arXiv preprint arXiv:2206.0033 2022.
Bahjat Kawar, Noam Elata, Tomer Michaeli, and Michael Elad. Gsure-based diffusion model training with corrupted data. arXiv preprint arXiv:2305. 13/28, 2023.
Varun Kelkar, Rucha Deshpande, Arindam Banerjee, and Mark A Anastasio. Ambientflow: Invertible generative models from incomplete, noisy measurements. arXiv preprint arXiv:2309.0483 04856, 2023.
Alexander Krull, Vim-Oliver Buchholz, and Florian Jug. Noise2void-leame leamming denoising from single noisy images. In Proceedings of the IEEE/CVF conference on computer vision and puttern recognition, pp. 2129-2137, 2019.
Jeffrey Li, Alex Fang, Georgios Smyrnis, Maor Ivgi, Matt Jordan, Samir Gadre, Hritik Bansal, Etash Guha, Sedrick Keh, Kushal Arora, Saurabh Garg, Rui Xin, Niklas Muennighoff, Reinhard Heckel, Jean Mereat, Mayee Chen, Suchin Gururangan, Mitchell Wortsman, Alon Albalak, Yonatan Bitton, Marianna Nezhurina, Amro Abbas, Cheng- Yu Hsieh, Dhruba Ghosh, Josh Gardner, Maciej Kilian, Hanlin Zhang, Rulin Shao, Sarah Pratt, Sunny Sanyal, Gabriel Ilharco, Giannis Daras, Kalyani Marathe, Aaron Gokaslan, Jieyu Zhang, Khyathi Chandu, Thao Nguyen, Igor Vasiljevic, Sham Kakade, Shuran Song, Sujay Sanghavi, Fartash Faghri, Sewoong Oh, Luke Zettlemoyer, Kyle Lo, Alaaeldin El-Nouby. Hadi Pouransari, Alexander Toshev, Stephanie Wang, Dirk Groeneveld, Luca Soldaini, Pang Wei Koh, Jenia Jitsev, Thomas Kollar, Alexandros G. Dimakis, Yair Carmon, Achal Dave, Ludwig Schmidt, and Vaishaal Shankar. Datacomp-Im: In search of the next generation of training sets for language models, 2024.
Marvin Li and Sitan Chen, Critical windows: non-asymptotic theory for feature emergence in diffusion models. arXiv preprint arXiv:2403.01633, 2024.
Yvette Y Lin, Angela F Gao, and Katherine L. Bouman. Imaging an evolving black hole by leveraging shared structure. ICASSP, 2024.
Nick Moran, Dan Schmidt, Yu Zhong, and Patrick Coady. Noisier2noise: Learning to denoise from unpaired noisy data. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12064-12072, 2020.
Tongyao Pang. Huan Zheng, Yuhui Quan, and Hui Ji. image denoising. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 2043-2052, 2021.
Unsupervised deep learning for
François Rozet, Gérôme Andry, François Lanusse, and Gilles Louppe. Learning diffusion priors from observations by expectation maximization. arXiv preprint arXiv:2405. 13712, 2024.
Kulin Shah, Sitan Chen, and Adam Klivans. Learning mixtures of gaussians using the ddpm ob- jective. A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 19636-19649. Curran Asso- ciates, Inc., 2023. URL httpps:/ htgprp/ceeeaa...eerrrroo.opoppod fnver-filee htt.://eeee/ppee/22///l..
pdf
A. Shohat and J. D. Tamarkin. The Problem of Moments. American Mathematical Society Mathematical Surveys, Vol. I. American Mathematical Society, New York, 1943.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv:2010.02502, 2020a.
arXiv preprint
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456, 2020b.
Charles M Stein. Estimation of the mean of multivariate normal distribution. The annaly of Statistics, pp. 1135-1 1151, 1981.
13

---

Published as conference paper at ICLR 2025
Alexandre B. Tsybakov. Introduction to nonparametric estimation. Springer Series in Statistics, Springer, New York, 2009. ISBN 978-0-387-79051--0 doi: 10. 10.1007/b13794.
Revised and extended from the 2004 French original, Translated by Vladimir Zaiats.
Roman Vershynin. High-dimensional probability, volume 47 of Cambridge Series in Statistical and Probabilis- tic Mathematics. Cambridge University Press, Cambridge, 2018. ISBN 978-1-108-4151944, doi: 10.1017/ 9781 108231596. /ttpttss:://// http://doo..rg///////ooo wtt.g//..110///11111111 /ttp///1..0117777111223333333330 in data science, With a foreword by Sara van de Geer.
An introduction with applications
Pascal Vincent. A connection between score matching and denoising autoencoders. Neural computation, 23(7):
1661-1674, 2011.
Martin Wainwright. High-dimensional statistics, volume 48 of Cambridge Series in Statistical and Probabilis- tic Mathematics. Cambridge University Press, Cambridge, 2019. ISBN 978-1-108-49802-9, doi: 10.1017/ 108627777 URL /ttt::/s//0ool.or1111111///////
A non-asymptotic viewpoint.
Yifei Wang, Weimin Bai, Weijian Luo, Wenzheng Chen, and Sun. Integrating amortized inference with diffusion models for learning clean distribution from corrupted images. arXiv preprint arXiv:2407.11162, 2024.
Yihong Wu and Pengkun Yang. Optimal estimation of Gaussian mixtures via denoised method of moments. Ann. Statist. 48(4):1981 1-2007, 2020. ISSN 0090-5364. doi: 10.1214/1--OSS1777 URL
1214/19 ACS1873
Yihong Wu and Harrison H. Zhou. Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in (vyn) iterations. Math. Stat. Learn., 4(3 (((334):433-20)) -20, 2021. ISSN 2520-2316. doi: 10.4171/ msl/29. URL
0111g//1.11111111 4171 //s//////////// 1/29
Jun Xu, Yuan Huang, Ming-Ming Cheng, Li Liu, Fan Zhu, Zhou Xu, and Ling Shao. Noisy-as-clean: Learning self-supervised denoising from corrupted image. IEEE Transactions Image Processing, 29:9316-9322 2020.
A APPENDIX
Algorithm 2 Truncated Sampling Sampling Algorithm.
Input: network hg, time steps T. step size AI, noise schedule {ar (or) stopping time ot.
1: By oT)
> Initialization
2: for f = T.T 1,..,,1111 do
3: do + (ag 1)
4: if 01-11 < Tt.. then
return 2o end if
Truncated Sampling
7: Ft-1 3t oe-d1-1 (x: 2p)
8: end for
return 2D
B PROOF OF LEMMA 4.
In this section, we establish Lemma 4.1 used prove the weakened bound for the one-dimensional setting The- brem 4.6 This result is implicit in Wu & Yang (2020) and we include the proof here for completeness. Before we proceed, we reproduce the following result from Wu & (202) which shows that for two distributions with finite support and close moments, their Wasserstein distance is also close.
Proposition B.l. Let D and D' be k-atomic distributions supported on 1-1, 1]. If Im,(D) m,(D') < 8 for 1,..,,, 2h 1, then:
Wi(D,D) & O(k).'.).
14

---

Published as a conference paper at ICLR 2025
Algorithm 3 Denoised Method Moments with Heterogenous Variances
Input: Samples X, MDirae oZ)
Output: Candidate k-mixture MDirce Σ dds0s.
I: Define weights 04, for i E [n]:
1/0, 4
ai
2j=1 1/0,/ 4k-2
Define moment approx. for E [2k 1]:
n m, Σ
Iroo (Xi).
1=1
3: Return output of Lemma 4.1 input m.
We reproduce the statement of Lemma 4.1 and include its proof below.
Lemma 4.1. WWr & Yang 2020)). Let e N, 8 [0, 1). Let 'D be k-atomic distribution supported on [-1, 1] and Mi,..., M22x- be estimates satisfying - mm;-mm & 5 for all i E [2k - 1]. Then there is a procedure running in
time O& (1), which on input {m4 2k-1 returns distribution D satisfying:
W1,D, D) & O(k8TTT)
Proof. We recall some preliminaries from Wu & Yang 2020 First, the moment space defined for set K C R:
M,(K)= = (T) π is supported on }}.
Specifically when K = Ja, b), M, is fully characterized by the following convex constraints:
Ma.- > 0, + bJ+ > abMo,r-2 M2,, for even
M & M1, > Mo.r-1 for odd r,
(MOM-CHAR)
where the matrices Mi, are defined as follows for m E M,:
m++1
m
m
m1+1
m442
m +1
Maja
mij
ma
my
As noted in Wu & Yang (2020), these constraints are easy see necessary. Surprisingly, they also turn out be sufficient for characterizing the space M, Shohat & Tamarkin (1943).
The algorithm now establishing Lemma 4.1 is presented in Algorithm 4 By assumptions on the input, we have:
Vi E 22k 1]: [m m. < 5
- |, m. (D) & 5
where the first inequality follows from the fact that ñ is the minimizer of the convex program and D certifies that solution with small error exists and the second follows from the triangle inequality. Next, since m corresponds to the moments of a valid distribution from the sufficiency criterion for one-dimensional distributions, Algorithm 5 returns a k atomic distribution matching the moments m. An application of Proposition establishes the lemma.
C HIGH-DIMENSIONAL UPPER BOUND: PROOF OF THEOREM 4.2
In this section, we prove Theorem 4.2 Here, we adopt the techniques from Doss et al. (2023) which reduces the high dimensional setting to the one-dimensional setting through series of reductions. The first reduces the d-dimensional setting to the k-dimensional setting by projection onto the principal components of the data. This is standard
15

---

Published as conference paper at ICLR 2025
Algorithm 4 Estimate Distribution from Moments
Input: Moment estimates mi...... -22k-1
Output: Candidate k-mixture MDirce Ei=1 W2d2.
1: Let m be the solution to the following:
min m m| m satisfies MOM-CHAR where m (m1,... (.2,,..-1)))))) m1)
Return the output of Algorithm 5
on input m.
Algorithm 5 Gauss Quadrature
Input: Valid moment vector (m1 .......... m2x-1)
Output: Quadrate points (z1....,aa .x) and weights (Wi,..., wk)
I: Define the degree-k polynomial:
m
m7
P(x)
mk-1
mi
m2k-1
z
I
Now, define (I1,...,,IM xkk) as the roots of ((x) The weights (Wi,.... Ws) are defined as:
F1 D2
k-1 1
222
m
procedure that is frequently employed to reduce high-dimensional estimation their tractable low-dimensional counterparts. The second step follows by establishing result which shows that any candidate mixture whose one- dimensional marginals are approximately consistent with the original mixture is close to the original mixture in Wasserstein distance. In the remainder of the section, [Appendix C.I analyzes the low-dimensional projection step, Appendix C.2 presents the low-dimensional estimation algorithm and Appendixx C.3 establishes Theorem 4.2
C.1 REDUCTION TO LOW-DIMEN NOW-DIMENSIONS
Here, we establish concentration bounds on the matrix, ε, used to compute the low-dimensional projection in Algo- rithm We recall the following result that we will repeatedly use our proofs:
Lemma C.1 (Exercise 4.4.3 Vershynin 2018).. Let N and G be e-net of the unit sphere. Then, we have for any symmetric M Rdxd;
|M] < T
max v Mvl. weG
We first bound the noise terms that arise when computing the high-dimensional covariance.
i.id NOO, I) and o; 2 0. i [n] with Σn - 0g 1. Then, we have:
Lemma C.2. Let 5m
1 max ( (d+ (o(1/ Σ af (d + log(1/5)) max as
Σ
0.9.
with probability least 1 8.
Proof. As is standard, we note the following characterization of the spectral norm for any symmetric M e Rdxd,
|M = max v M
| =1
16

---

Published as conference paper at ICLR 2025
and start with a fixed v. The extension to the remainder of values is obtained through discretization argument, net over the unit sphere and a union bound. Now, for fixed ||:|| = 1, consider the random variable:
W = U² Σ 049. T - - 1=1
au (1gi, u)2 - 1).
We now prove that W is sub-exponential:
Claim C.3. We have for any [^] < 1/4 and g N200 1):
E/exp X(g² - 1)1 < exp(412).
Proof. We have for any ||| < 1/4 and g (0,
1
g²
E Elexp(A(g2
1)}1 e
exp
(Ag²)
2 dg
22T
(1-)
g² dg
exp
00 2T
2
vI 2X
e x
=
V1 21
vI 4X²
ex
1
E <
exp(41²)
4X
Ve Ve-8Az
8X
concluding the proof of the claim.
Hence, we have that each of the (19,, u) 1) are C-sub-exponential random variables for some constant C' 0. Hence, we have by Bernstein's 's inequality (Vershynin, 2018 Theorem 2.8.2):
P P(W. > t < 2 exx
-cmmin
-i of max; Oi
Now, let Q be 1/4-cover of the set {a : ||ا||| = 1} with [Q| < gd. Then, we have by the union bound:
Pf3r E Q: W. > f < 2- 9d exp -emin
Di=1 Oj
max;
Choosing t" as:
(d++ Σ ag (d + log(1/0)) max ai
t" = max
yields:
max W. < t" NEQ
with probability least 1 8. Observing that:
|M = max lo T Mvl
max v T Mu] w
||||=1
for any symmetric matrix M (Lemma C.1 concludes the proof.
Now, formally establish concentration of the second moment matrix E, in spectral norm.
Lemma CA. Let 'D be k-atomic distribution supported such that each element, x., in its support satisfies | R. Furthermore, suppose X1y...,
......,, Xn are independent samples with X; D * NO, of1) with of > 0 for all E [n].
Then, we have:
Σ
0; X - 8²1 Ex-D|XXT] 6
17

---

Published as conference paper at ICLR 2025
max (Ta (d Vuu+ log log(1/6)) Σ of max(o?, R2), (d + log(1/0) max 0,07; k log(k/6) E o
where 0i
1/07 Ej=1 1/03 and 0² = =Ei=1 o: with probability at least 1 6.
Proof. Note that we may write X; = Y + Jigi where Y, ~ D and () independently. Now, we write the error term as follows:
Σ a X - -00 - -xxxxxx
Σ D,YYY," - Ex_olxxT)) + (Ea -
021 + - a + g,,,)).
The proof proceeds by bounding the errors of each of the three terms separately. We start with the middle term which we bound with Wemma C.2 to obtain the following:
n
a.o - 0²1 < max (/d- log(10)))
Σ
Σ
ajot (d log(1/6)) max ago?
i=1
For the first term, note that the enror matrix may be written follows:
Σ a. Y,Y,Y, - Ex=o[XXX]] = Σ (w: w. wi)pmmy
where 0; = Σグ=1 ay = n.) corresponds to the empirical counterpart of the mixture weights. Now, we have for any ||||| =
T
Σ a, Y.Y
-ExDD[XX]]
< R2
w/
1=1
An application of Hoeffding's inequality and the union bound obtains:
Vi E [k] p mil & C, C log(k/0)
with probability least 1 8/4. Conditioned this event, have:
m
12
Σ ANYY ExxD[XX]]
< CR
log log(k/0 (2//)))
We now proceed the final term. Consider 1/4-net of the unit sphere, G. We have for any fixed
Σ (Y + +oxx))) v Σ 20,0 (v.
Noting that (v. 9i) is a standard Gaussian random variable and that ||Vill < R, we get that each term in the sum is sub-Gaussian and consequence, we get by Hoeffding's inequality:
Σ a
Σ
(Yig + 9. (.YTT) v < <c
log
with probability least 1 8'. Hence, we get by the union bound over all v e & and the size of G:
Σ (Y + + v < (d (d+ log
Ve Ve
T
Σ R2
Finally, this yields the same bound on spectral from Lemma C.I conclude the proof of the lemma by the triangle inequality.
The three bounds previously proved now
18

---

Published as a conference paper at ICLR 2025
C.2 ESTIMATION IN LOW-DIMENSIONS
The following lemma is generalization of key technical lemma in Doss et al. (2023). This lemma establishes that the Wasserstein distance between two k-atomic distributions over I can be approximated through various one- dimensional projections. While the version in Doss et al.] (2023) required the supremum in the conclusion to be taken over all vectors the unit sphere, our result only requires supremum over a grid of the unit sphere. Crucially, the size of the grid is independent of and hence, the final error. Our algorithmic approach benefits from this since to establish concentration over these one-dimensional projections, we may use more robust median-of-ment techniques of Doss et al. (2023)
based approaches
to obtain these individual estimates as opposed to the more intricate chaining- which necessarily incurs the sub-optimal v (1/6) dependence features in their final bound. The chaining- chaining-based techniques in Doss et al. (2023) are required since the grid size resulting from the previous approach is dependent on n and hence, the simple techniques we employ incur additional factors depending on n. Technically, our improvement arises from robustness analysis of the randomized one-dimensional projection argument employed in the proof.
Lemma C.5. Let d, k E N and 9 be 1/(32k2 Vd) gd TThen, for two k-atomic distributions, D and D':
Wi (D., < (D, < 16A² sup W (D,, D(). "EG
sup eEG
Proof. The lower bound follows from (Doss al., 2023 Lemma 3.1). For the upper bound, we proceed as in (Doss et al. 2023 Lemma 3.1) starting with simple probabilistic argument. However, we additionally analyze the robust- properties of their construction to account for the discretization in our bound. First, define the set of vectors:
Q =
y vll
x.y E {mi U f4A and + #V1
Note that Q is of size at most 2 We follow now the probabilistic argument also utilized in Doss et al. (2023) to establish the existence of a vector e E Sd-1 which satisfies:
Vu E Q ||a|| & (d u)l-
Now, draw from the uniform distribution on gd-1, For any u E Q. we have by standard results for t < 1/2:
T(d/2)
["
P (1(e, < VTl'((d 1))22)
x2)(dd3)/22 & 4lvd.
3)/2
Then, we get via a union bound:
Vu E Q 8h2 Vdlve u) >
with probability at least 1/2. Hence, we have for such a v::
Vx,y E (n:)
(nt : | yll < 8k2 Vdlkk, -
Now, let ö be the closest neighbor of u in G. We now have for any E Q:
16 u>) > ((,, u)l 1 all
16k2
For this U, observe that each of the elements in {1 U fn is mapped to a distinct real number. Hence, every coupling of and D' correspond to a coupling on the projections of the distributions Dj and D/ and vice-versa. Then, consider any coupling of Da and D/., C(Y, Y') and its corresponding high-dimensional analogue, Ca) Then, we have:
2 V dE (yr))-> ||Y - Y' > xxIx X'Il (D,,DD).
By maximizing over all such couplings, we derive the conclusion of the lemma.
The key benefit of Lemma C.3 is that it only requires us to obtain an candidate distribution whose marginals are close in Wasserstein distance to the marginals along a subset of directions independent of n. In the remainder of the proof, we will assume that = & as we may project the data down to dimensions by computing the PCA of the centered covariance matrix. Before we adapt the analysis of Doss et al. (2023). we will prove a moment concentration result which will enable tightening of the dependence on the failure probability. While Doss al, (023) obtain upper bound with a / (loo) dependence, our bound will instead grow was (log(1/8)) 17(
19

---

Published as a conference paper at ICLR 2025
Lemma C.6. Let k.m,n E N. (0.1/2), and R > 0 be constant. Suppose 'D be a k-atomic distribu- tion over T&& with each I. in its support satisfying ||ج|| & R. Then, there is a procedure which when given inde- pendent samples XI....,& Xn distributed according to X, ~ D * (O0,, 1) with Ø, 3 1 and max; 1/0, 1/0, 4k-- e c 1/0, Ak (10g(1/0) + k <log(k)), returns one-dimensional estimates, (Dr)weg: satisfying:
( ( (kllo(k)) + (og()))))
a
1/((R-22
VU E 9: WI(D,. D.) & CKP
1k-2
i=1 0,
where is a (1/ polp(k)))))k)))) net of with probability at least - 8.
Proof. We start by defining a partition π [xx - [m]]
where m C(log(1/6) + log(k)) satisfying the following:
Vj E [m]
Σ
1
1k-2
2m
d; 2k-2
(
For all E EG, E [m]. let Dr,, be the one-dimensional k-atomic mixture obtained by running Algorithm on the points {(X,, v) (() From Theorem 4.6, we get that:
Such partition may be found in linear time by Lemma C.7
11/(46-2) 2)
P Wi (D,, CCP
m
aj
4k-2
4
Defining the random variables Qu follows:
Qu = 1 If (D, & CK2.
-1/(4k-2
Σ 4
m
we get that [[Qu,e) > 3/4. Therefore, we get by an application Hoeffding's inequality for fixed E G:
P Σ Que & 0.6m
< <xp((-mm).
By a union bound, we get from our setting of m:
P
P 3o E:
Que < 0.6m <0.6m
< 9 exp(pcmm) <
We now condition on the above event. At this point, we have m estimates D,,e for each direction v G. To obtain single estimate for each direction, v, observe the following by the triangle inequality for any j.j [m]] such that Quiji Qu, =1:
11(44-22
W1 WI Duy') < Wi(D.,,, D.) + WD.D,, D.y) < CK2
m Σ
1k-2
Now, consequence, the following set exists:
j [m]: fee { [m] Wi(D & CK
-1/(4k-2) 2)
n
J J= 3=pjEn
m
> 0.6m
2k-2
J is computable from the estimates Dry and we now show that any arbitrary element of J suffices. Let j E J and notice by the pigeonhole principle and the definition of J. that there exists E [m]] such that Qu = and furthermore,
-1/(42-2)
-1/(4k-2)
n
Wi (D Do,e) < CK2
Σ
m
(Dngg,; < CI2
Σ
m
1k-2
14-2
by the triangle inequality and the definition of Qu,e. The lemma follows from the estimates (Du for G.
20

---

Published as conference paper at ICLR 2025
Our algorithm uses median -feaass means based approach to recover the moments of the one-dimensional projections. Since the variances are non-uniform, we use deterministic partitioning algorithm to partition points to ensure buckets of roughly equal size. The following lemma establishes guarantees on the sample partitioning algorithm.
Lemma C.7. Given k E and n numbers, 01...., Otp. 3 0 such that max, ag Eis 0u/1k, it is possible to find a
partition π [n] > [k] such that:
min Σ aj
-= a4
2k
Furthermore, the runtime of this procedure is O( log(k)).
Proof. We will analyze the simple greedy procedure in Algorithm where ties are broken arbitrarily. Define:
Mj
Σ ap.
(ε)x(()=)
We will prove by induction on that:
Yj, E [M] MM Mil & Omaxx-
The case for = trivially true. Suppose the condition is true for i = m. To extend to m + 1, let jas == arg max; M. and Jm = arg min; M.n. Then, we must arg max; M (im,im]- Note now that for all * Im:
MM M & Omax
|M - M 1(M Mym)) a241 04-1 & Omaxx
Finally, we have:
- 1 [M - MT aul < a & Qmax
Jm
concluding the proof of the inductive claim and consequently, establishes the correctness of the algorithm. The runtime follows from the fact that the scores may be stored in a self balaniannning binary tree.
Algorithm 6 Partition Mass
Input: Weights a...... On
Output: Partition π [m] - [k]]
1: for i = 11..n do
T(i) = arg min, Eecin(0=)) at
end for Return
In the next, we use the techniques of Doss et al. (2033 to improve the computational propertics of the estimation algorithm. This part of the proof is essentially identical to Doss et al. (2023). However, we include minor changes which allow tightening the bounds. The next lemma shows that the set defined in Algorithm 7, which defines the low-dimensional estimation algorithm, has good solution.
Lemma C.8. Let d, E N and let D = > widpp be a k-atomic mixture over Rd with I| & for all [6]. Furthermore, for each i E [d], let De, Ei= org0g be k-atomic distributions over IR each satisfying:
WI(De, Do,) Ev.
Then, for any (v/ Ri)RR)n-e -net over the probability simplex, W, there exists a solution Đ Ek= w. such that:
Wi (D, D) 2dv where w W and p. E (1/1 1031 185)).m.
Proof. We have consequence of the assumption of the lemma:
Vj E [d]
Σ
w; min (po, eq) - 1./1 s. (E(k)
21

---

Published as a conference paper at ICLR 2025
Algorithm 7 Low-dimensional Algorithm
Input: Data Points ,,,..,, X variances ....... On Output: Low-dimensional mixture M = Σi= Wz82.
and failure probability
Let be a 1/(32/2 / of S*-1 containing ci....,ck For each v E G, let D. be the output Lemma C.6
3: Let for each E [ki], let De: = Σラ= j== 0p
C= C= x (M x... ta
4: Let W be (1/n)/(4k-2)) net over the probability simplex over i elements
5: Define:
arg min arg max W (De, (1, @ B'EW NEG
Return D Ei=1 0zd7g
Finally, let
Defining now:
Vi E [k] M4 (i!....., R.) where /e
arg min (uerez) [il for all é [A], e [d].
pe pet
We have for the mixture D Et= Wzdpe::
WI D) willms - i0,1 wi Ilk - Poll1 =
Σ W
(pn. e,) -5x 1 = Σ
w.
Wil es) - - & dv.
1=1
j=1
Finally, let @ E W be such that |00 w|l1 $ V/R. R. We have for the mixture = 2=== 0:d7,:
4:
(D) < Wi(D, w (D, du + Σ 1
We max 1i -ell < du 2VdR >
[6 wil & 2dv
J1E
concluding the proof of the lemma.
C.3
PROOF OF THEOREM 4.2
The complete nigh-dimensional estimation algorithm is presented in Algorithm The algorithm splits the points into sets, and utilizes the first to compute low-dimensional sub-space that (approximately) contains the means of the components of the mixture and then, runs the low- wwwdimmnniioal estimation algorithm Algorithm 7 7nn the second set. Before proceeding with the proof, we recall another lemma from Doss et al. 2023) which relates the loss in accuracy caused by the low-dimensional projection to the error in estimating the low-dimensional projection in Lemmmma C.4
Lemma C.9. Let D Σ5= wrpps be k-atomic distribution. Let Σ Ex~D[UUT] Σ Wypge]] with eigenvalues λ > ...... da. Let E' be symmetric matrix and 11, be the projection matrix onto the subspace spanned by the top r eigenvectors of E'. Then,
W W (T, (ng) & k (Ar+1 + 2115 - -1
Proof Theorem 4.2) The algorithm that achieves the guarantees of the theorem is defined in Algorithm 8 We first show that the partitioning step induces balanced partitions for the subspace computation and low-dimensional estimation steps.
Claim C.10. We have the following:
Σ x,ex,
Σ
1
of
o0
22

---

Published as a conference paper at ICLR 2025
Algorithm 8 High-dimensional Gaussian Mixtures
Input: Point set X = [(X1,... Xn). Variances 01 nn Failure Probability 8
Output: k-atomic mixture Σ 0zd7, 1: Partition X into X₁ and X₂ by allocating each X, to X1 or X₂ uniformly at random
2: Define
1/0 and 0²
Σ= Σ a,X,X - -0²1 where at Ex,xx, 1/0, X;EX;
Σ X;EX,
ago.
Let U be the top-k singular subspace of Σ
4: Let X2 = (X2)
5: Return (0i, M1) the output of Algorithm 7 on input 2,, weights faitx,ex, and failure probability 6/4
C2 4(log(1/0) + klo((k)
Σ X,eX,
2k-2 0,
2k-2
with probability at least 1 - 6/4.
Proof. For the first, observe that:
Wr where W, = 1(x; E X1}
Σ
of
X,eX,
Now, have by Hoeffding's 's inequality:
P
Σ
W
E
W.
< -t
< exp
E 1/0
2t
< exp (-2
(1/of)
t
Em 1/0
t
Now, setting:
1
E 1/0,
> 4 log(11/))
m1x;(1/0;)
Σi=1 1/0
16
maxx(1/a7)
Observing that:
W
= 2 :=1
1=1
yields the first claim with probability at least 1 - 8/8. For the second, similarly define:
Qs where Q2 11x, X2)
Σ
1k-2
2k-2
X,EX,
As before, we have by Hoeffding's 's inequality:
P
Q.
E
Σ
Q
<
-1
exp
E
2t
1/0
8
exp -2
max, (1/0
t
Σ 1/0th-3
t
1h-2
Now, setting:
t
E 1/ 1/2
log(1/5).
2
max
(1/0,)
4k
2
-
1/0
2
16
max, 110,
Observing.
E
Σ
Q
Σ
1
2
2k-2
-=1
1=1
yields the second claim with probability at least 1 6/8. A union bound establishes the claim.
23

---

Published as a conference paper at ICLR 2025
We will now assume the event in the conclusion of ollii C.10 the remainder of the proof. We have consequence
Claim C.I Lemma C.4
- --EEXDXXXX]] max
(1 (1 log(1/6))
(d+
Σ X,ex,
afot (d 1og(1/6)) max a k log(k/0) Σ of X,EX,
For the second term, we have for any X; E X1:
+ log(1/6) Exex, 1/0!
(d + log((/8))a & (og((1)))))) (d log( 1og(1/6))oão} < sg
Hence, we get that the second is dominated by the first as:
(1/0,)*
aj X,EX, X,EX,
Σ
Σ
Ex,xx 1/0 Ex,xx 1/0
Finally, the third term dominated by the second as oi d 1. To conclude, we get by Claim C.10 and the previous discussion that:
| - [x-EXxD(XXX]]
(d log(1/6))
m Li-1 1/0.
Therefore, we have for the subspace U in Algorithm 8 by Lemma C.9
(d + log(1/8))
Wi(D,Dv) & Ck
E 1/0
with probability at least 1 5/4. Next, since X₂ are independent of X1 (and hence, the subspace U), we get by Claim C.10 and Lemmas C.6 and C.8 that the solution D = (0,, Ps ke()) satisfies:
-1/(4k-2)
Wi Wi Db) & CK (og()) log (18))
Ak-2
with probability at least 1 - 8/4. By union bound and the triangle inequality, we get:
D). < W.D Dv) + Wi (D(D,,
-1/(4k-2)
< (d (llo(((()))) Σ E 1/o
1/8)) (1d+))(())))
1/4
(k (k) + log (1)))
3.
2
with probability least 1 5 establishing the correctness of Algorithm 8
Finally, bound the runtime, the computation of the top-k right singular subspace can be computed in time (x(n)) and projecting the points in X₂ onto the low dimensional subspace also computable in time (nd). For the running of Algorithm observe that the procedure in Lemma C.6 runs in time (l = (n)... ( Finally, for the remainder of Algorithm 7 note that the number of candidate vectors in is at most k and the number of candidate weight vectors in W is at most n.. Therefore, the total number of candidates is at most (n).. The time taken to check candidate solution is at most (1) for each E G and since there are at most (1) of these, the time to check single candidate is (1). Thus the total runtime for the Algorithm 7 is most (s(n) and consequence, the runtime of Algorithm is bounded by Öx (nd).
D LOWER BOUND: PROOF OF THEOREM 4.4
In this section, we prove the lower bound Theorem 4.4 We prove the lower bound in three cases which will imply the final bound. Firstly, we prove the k-dependent term from the lower bound in Appendix D. and show that it holds in the one-dimensional setting. Then, we establish pair of bounds for high-dimensional setting, one for the dimension- dependent term in and another for the failure probability in Appendix D.2, We then combine these three results to obtain the final bound from Theorem 4.4] We will frequently make of the following inequality which will be crucial in obtaining the cighbbbbbabblitty lower bounds in the respective statements:
24

---

Published as conference paper at ICLR 2025
Lemma D.1 (Bretagnolle & Huber 1979); Tsybakov (2009)
Canonne (003)) ).
We have for any two distributions, P
and Q:
TV(P, Q) <
(XP(DLL(PIIQ))
2
D.I ONE-DIMENSIONAL LOWER BOUND
Here, we establish a lower bound in one dimension for the estimation problem with & components. We show that the k-dependent term in the lower bound is unavoidable even in the simpler one-dimensional setting. Our proof largely follows that in Wu & Yang (020)) but specialized to the setting of heterogeneous variances. We start by recalling some technical results from Wu & Yang (2020).
Lemma D.2. Let [0, and N. Suppose now that D and D' are centered distributions supported on [-c, salisfying mi mi(D) my (D'). Then, we have the following:
1+1 )
EE²
141
x² + N(0, + 1)) 1)) <
We also note the following simple corollary by the invariance of f f-Divergences to re-scaling of the distributions. Corollary D.3. Let [0, 1] and I N. Suppose now that DD and DD' are centered distributions supported on [-c,e]
satisfying (D) mi (D'). Then, we have the following for any o² > 1:
N(D N((,, ) so ((
1+
Es
(7 1)02
Lemma D.2 implies that two Dirac distributions supported on small range and matching large number of moments are challenging to distinguish from each other. The following result from Wu & Yang (2020) shows that when allowed support size of k, there exist two distributions and D' supported on [-s, and more than e/k apart but nevertheless matching their first 4k 2 moments.
Lemma D.4. For any and i N, there exists two distributions DD and D' supported on [-e, satisfying:
WP > (E) and m2k-2(D) m22 mD²))
Furthermore, D and D' are supported on at most k elements.
Next, we prove the main one-dimensional lower bound.
Theorem D.5. There exists an absolute constants C, such that the following holds. Let n, N, 8 (0,1/4) and oi forr e [ri] be such that:
Σ
- 0, (CVR) 4k- log((1/)))
Then, there exist two distributions, DD and D2, each supported at most k-points in [-1, 1}. such that the following holds for any estimator 0:
1/(4k-2)
max Px W)(D, De
> 8 where X
II D D
log(1/8)
0 2k-2
Proof. Let E [0, 1] be parameter be chosen later and and D' be two distributions whose existence is guaranteed Lemma D.4 Then, observe that have the following for all i E [n]:
(D - NNO, o' NN(, =0
(2k 50
<0
es
2k
1)o?
Recall the tensorization properties of the Xa divergence:
a
D + D of) I D' N((,,;))
+1 (D* (D= +N(0, + +1).
X2
25

---

Published as a conference paper at ICLR 2025
As a consequence, we get that:
cEa
2h-1
CE
26-1
II oO)
<
<
Σ
when
Σ
c
(2k: 1)07
(2k
1)07
i=1
i=l
i=1
1=1
for some absolute constants C, c O. Finally, picking as:
26-1
-1/(4
e (2k - 1)07
=
log(1/8)
1=1
for c > 0 yields:
n
log(1/0)
Il D N0 of) II D' N(
X2
As a consequence, we get:
log(1/0)
= DKL II D NO
of II D' * N(..0.))
Jml
By the BH-inequality (Lemma D.I.
we now get:
TV
II
DID ill II D' * ~((,,?))
1-
exp (-7) < 1
An application of Le Cam's (Wainwright
2019 Lemma 15.9) method now yields the result.
D.2 HIGH-DIMENSIONAL LOWER BOUNDS
Wu Here, adapt the techniques of Wu & Zhou| 2021) to establish lower bounds in the setting of heterogenous variances. The dimension-depeeneen lower bound is established for the simple setting with two equally weighted components with means distributed symmetrically across the origin. Hence, the set of candidates mixtures MDirac parameterized by Rd and defined below:
MDirac = 69 + 5
2 2
In the rest of this section, will Dg refer member of this family. We now reproduce technical result
from Wu & Zhou (202I) which bounds the KL-Divergence between two different Gaussian mixtures from this family in terms of the distance between their respective location parameters.
Lemma D.6. Then there exists a universal constant C' such that the following holds. For any s E [0, 1] and u, e such
that [lll = ||||| = 1, we have:
(D * (0, (D. * NNO, 1)) < C 0112
Furthermore, we have by the scale-invariance of the KL-divergence, the following corollary. Corollary D.7. Assume the setting of Lemma D.6, Then, for any a > 1, we have:
(D sm ( o NoO, o² o2)) Clllu u1/2 (-)
We now present the main lower bound the section:
Theorem D.8. There exist absolute constants C, 0 such that the following holds. Let dt 2 3, E N. and {o be such that 2 for all i E [n] and:
Cd.
Then, we have for any estimator T:
1/4
max Px
Do) 2 c Σn
>
BERS
1/0
2
where X = ( are independent random vectors with X, Dg NN00
26

---

Published as conference paper at ICLR 2025
Proof. The proof will use the standard testing to estimation framework for proving minimax lower bounds. First, let G denote a 1 144-packing of the unit sphere such that [ >/ 4d-1 Now, we have from Corollary D.7, for any u, v E g and o > and 8 E [0,1]: 1]:
DD + N N((,000)) Cl Clluueel
(1) < <40 (
Hence, we get by the tensorization of the KL-divergence:
n
DKL
Daw * 11)
II Dew * -V(0,
Σ DRL. Dan P D
&C$t Σ
Now, picking
1/4
c
Ei=l 1/0,
we get that:
DKL. DI NN0, II Da. * N( <
d
16'
An application of Fano's inequality (Wainwright 2019. Proposition 15.12) for the set of candidates fsulueg and
noting that [g] 4d yields the result from the observation that for any u, v E G. Wi su. D 3 8/4.
We now establish a separate high-probability version of the bound.
Theorem D.9. There exist absolute constants C, c > 0 such that the following holds. Let 2 2, E N. 8 (0, 1/4]
and {o,) n be such that o, 2 1 for all i [ni] and:
Σ 1=1
C'log(165)
Then, have for any estimator T:
(f() > c 1og(1/8) 1/4
Em= 1/0 )
max
Px
3 2
BER
where X {Xi]== are independent random vectors with X; Dø NO0. of
Proof.
Let Gj and C2. Then, we have by Corollary D.7 for any > and [0, 1]:
(Du ((0 o² D) * NN(0, < 2C (
We have by the tensorization of the KL-divergence:
DKL D * (N((007TT)
II Dav * *N
Σ DKL Dou D Der (..0..tt)
n
Cst
Σ
n
o.!
Now, setting:
log (1/8) 1/1
c
Σn 1/0,
we get:
n
m
log(1/8)
DKL
I
Dan * N o0,
D.o * N(0, 07
<
8
27

---

Published as a conference paper at ICLR 2025
Again, we get by the BH -H-inequality (Lemma D.I.
TV D (0, II N((,0211
< -1-6. <1
An application of Le Cam's method (Wainwright 2019
Lemma 15.9) concludes the proof of the result.
Finally, we combine the three bounds to prove the complete lower bound from Theorem 4.4
Proof of Theorem 4.4 The proof follows from Theorems D.5 lower bounds in the conclusions of the results.
D.8 and D.9 by choosing the largest out of the three
E ADDITIONAL RESULTS
E.1 PUSHING PERFORMANCE TO ITS LIMIT
In all our previous experiments, used the EDM (Karras et al. 2022 hyperparameters that were tuned for clean data training. Here, we ablate different parameters that can further increase the performance of training with data mixtures. The first observation is that data corruption increases the time for convergence. In Figure 4 we plot the FID as a function of training time for a model trained with data mixtures. As shown, the FID keeps dropping as we train, indicating that the default parameters might lead undertrained models when there is training data corruption. Hence, take the ImageNet training run with 90% noisy data and 10% clean data, which has reported performance 1.68 in Table and train the model for 500K more steps. This alone decreases the FID from 1.68 1.63.
We then argue that for times t & tn we should expect sub-optimal estimates since only a few (clean) samples were used. We attempt to balance the higher learning error with reduced discretization error by increasing the number of sampling steps spent on these noise levels during sampling. This further improves the performance from 1.63 1.60.
Next, we use consistency loss improve the learning for / l, that was previously trained only with the clean points. We note that only consistency loss for this final part of the 500k training steps. Consistency fine-tuning improves the FID to 1.58. Finally, we use weight decay as regularization technique to mitigate instabilities caused by the increased training variance. This further reduces the FID to 1.55. It is possible that more optimizations could further decrease the FID but at this point we are already close to the optimal 1.41 obtained using 100% clean samples.
Configuration (a = 0.2)
ImageNet FID
p = 10% clean and 90% noisy
Baseline Parameters
1.68
+ More training
1.63
C + Sampling Noise Scheduling
1.60
D Consistency Loss
1.58
E + Weight Decay
1.55
Clean Data Performance
1.41
Figure 2: Evaluation of training and sampling improvements for models trained with noisy data.
In what follows, present some additional results that did not fit in the main paper.
28

---

Published as conference paper at ICLR 2025
CIFAR
CelebA
ImageNet
0 0.0
T = 0.1
=
0.2
Figure 3: Dataset images with varying noise levels (o).
CIFAR FID for 10.00% clean data and 90.00% noisy data (sigma: 0.2)
4.5
4.0
3.5
3.0
25000
50000
75000
100000
125000
150000
175000
200000
Checkpoint Index
Figure 4: FID as a function of training steps for a model trained with a mix of clean and noisy data. FID continues to go down as we train more and more, indicating that the model at 200K iterations still undertrained.
F EXPERIMENTAL DETAILS
F.1 TRAINING
We train CIFAR-10 models for 200,000 steps, CelebA models for 100,000 steps and our ImageNet models for 2, 500, 000 steps. All of our images are normalized in [- prior to adding additive Gaussian Noise. We use the training hyperparameters from the EDM codebase (Karras et al. 2022). For our experiments with consistency, we use steps for the reverse sampling and 32 samples to estimate the expectations. We use a fixed coefficient to weight the consistency loss that chosen hyperparameter from the set of (0.1, 1.0, 10.0} maximize performance. Upon acceptance of this work, we will provide all the code and checkpoints accelerate research in this area. Consistency leads to a 2x increase in hardware requirements (memory footprint) and 2 (ImageNet) to 3x (CIFAR, CelebA) slowdown.
F.2 EVALUATION
We generate 50,000 images compute FID. Each FID number reported in this paper is the average of three indepen- dent FID computations that correspond to the seeds: 0-49,999, 50,000-99,999 9999, 100,000-149999.
29


Reviews:
[{"review_id": "4FsSTwDBcu", "reviewer": "Reviewer_MdgL", "summary": "The paper investigates the impact of noisy data on (ambient) diffusion models. The paper shows that noisy data can be leveraged to improve the performance of diffusion models. In addition they provide the data regime where the noisy data are useful.", "questions": "- ¨For example, a blurry image might get dismissed from the filtering pipeline¨ Can authors provide a real example of such a filtering, i.e., a real filter used and a real discarded image?\n- \"For realistic sample sizes\" Do you have an order of magnitude of \"realistic sample size\" in your context?\n- Figure 1: in addition to training on noisy data, are other data augmentation techniques used? if not, do you know how new noisy data would compare against already existing standard data augmentation?\n\n\n- The heteroscedastic model: I do not understand how the proposed model in Definition 4.1 is a heteroscedastic mixture of Gaussian. As currently written in the paper, it feels that all the points of the distribution are convolved with the Gaussian noise (which is coherent with the proposed setting). Following Shah (2023), shouldn't a heteroscedastic mixture of Gaussian write $X_i \\sim \\\\mathcal{N}(\\mu_i, \\sigma_i)$.\nIn other words, IMO maths matches the setting, but I am not sure of the ¨heteroscedastic mixture of Gaussian¨ terminology.\n\n- Regarding the cost of the augmentation, are all models trained with the augmentation, do you confirm that all models are trained with the same budget? (i.e., with the same number of images seen, since the datasets are different) I guess yes since EDM code takes ¨million number of images¨ as input\n\n\nTheorem 4.2:\n- what are $c_1$ and $c_2$? Absolute constants as defined in Vershynin (2018)?\n- \"Discussion\" I did not understand the discussion after Theorem 4.2, could you elaborate on the \"error in estimating the low-dimensional sub-space\" and the \"low-dimensional estimation procedures\"\n- \"Then, there is a procedure which when given n independent ....\" could you give a word on the procedure?\n\n- Algorithm 1: is the noise level of each sample require in Algorithm 1?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- the paper is well written\n- the tackled problem is very interesting\n- experiments are exhaustive and convincing (Figure 1 shows the regime of interest for using noisy data)", "weaknesses": "- I am not familiar with proof techniques for the mixture of Gaussian sample complexity, but I am not sure I understood the goal/take-away of Theorems 4.2-4.4. IMO much more discussion is needed here.\n- Lack of motivation: the tackled problem is overall very interesting, but I am not sure that the authors provided a concrete application where such new noisy data are available, and known as such.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N2ABe9tw9u", "reviewer": "Reviewer_brqJ", "summary": "This paper studies data scaling laws for ambient diffusion. The authors find that training on a small set of clean data and a large set of noisy data significantly outperforms training solely on either one of these sets. The paper provides both theoretical analysis and empirical results to verify their findings.", "questions": "see weakness", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The studied problem is interesting and important.\n2. The authors provide theoretical results to support their findings.", "weaknesses": "1. I'm a bit confused about the relationship between thm 4.2 and alg 1. The thm 4.2 states that there exists a procedure which can return a good estimate of D. Is Algorithm 1 the procedure referenced in this theorem?\n2. Alg 1 need to know whether each data is clean or noisy. Is it possible to generalize the proposed algorithm to handle cases where clean and noisy data are mixed?\n3. In the experiments, The paper only presents the empirical results of the proposed method and does not compare it with previous work. (Daras et al., 2024; 2023b).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l7W7fHy7UY", "reviewer": "Reviewer_zaEs", "summary": "Quick summary: This paper studies the performance of the diffusion model in the ambient diffusion scenario. Previous work shows that the diffusion model trained by noisy data is inferior to the model trained on clean data, and the consistent diffusion model requires the noisy samples to be infinity from the asymptotic view. This paper proposes to use the mixture of clean data (high-frequency feature) and corrupted data (low-frequency feature) to assist the ambient diffusion model to obtain a very close performance to the state-of-the-art and provide the theoretic analysis to support the experiment and evaluate the corresponding value of noise image using the inspiring sampling bounds from the theoretical results.\nQuality: The paper is well-written and well-motivated, and the proposed method is good with a theoretical foundation albeit a bit simple.\nOriginality: The theoretical analysis of the two sampling bounds is inspiring with practical meaning. \nSignificance: This is an important research direction because noise data is common in the real world.\nPros: * Important problem * theoretical foundation * nice results and sufficient experiments\nCons: * The solution is a bit simple and kind of engineering consideration.   \nSummary: This is a nice paper that gives a simple solution to the ambient diffusion models with theoretic analysis and while not groundbreaking, certainly merits a publication.", "questions": "What's the exact number of samples or dimensions in your settings in line 93, page 2?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The theoretical analysis of the two sampling bounds is inspiring with practical meaning.", "weaknesses": "The solution is a bit simple and kind of engineering consideration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IB58uNafYK", "reviewer": "Reviewer_vSSn", "summary": "First, the paper empirically shows that training on entire noisy data will lead to bad performance, but as long as a few clean data (~10%) are available, models trained by the proposed algorithm are comparable to models trained on clean data. Second, the paper derives minimax optimal estimation bounds to explain the phenomenon. Third, the paper pinpoints the price of noisy images for different datasets and noise levels, which has practical implications.", "questions": "1. How can we know the value $\\sigma_{t_n}$ in the inputs of Algorithm 1?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper is written clearly.\n2. In practice, we have small sets of clean data and large sets of noisy data, so the paper considers an important setting.\n3. The experiments on different realistic image datasets are sufficient to support the claim in the paper.\n4. The established estimation bounds are minimax optimal and discussed clearly. \n5. The price of noisy images is interesting.", "weaknesses": "1. The obtained $\\hat{D}$ is the ERM result for the Wasserstein distance loss, which is mismatched with the loss of diffusion models. Thus, there exists a gap between theory and practice.\n2. The proposed algorithm and proof technique are mainly based on existing works, which may decrease the novelty of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l7rTrHkltw", "reviewer": "Reviewer_kj8h", "summary": "This paper tackles a critical issue in training diffusion models with corrupted data when clean data is scarce or costly. The authors explore the effectiveness of a combination of a small clean dataset and a large noisy dataset, demonstrating that this approach can yield performance close to models trained solely on clean data. Theoretical analysis based on Gaussian Mixture Models (GMMs) with heterogeneous variances and experimental validation across multiple datasets support these claims. Additionally, the paper proposes a budget allocation mechanism for more efficient dataset curation by balancing the use of noisy and clean data.", "questions": "It remains unclear why an exponentially larger amount of corrupted data is necessary to compensate for the lack of clean data. Can the authors provide more clarification for this point?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The paper is well-written and logically structured, making the content easy to follow.\n* The theoretical analysis is rigorous and provides good intuition behind the proposed methods. The experiments are thorough, involving the training of more than 80 models across various datasets and noise levels.\n* The paper’s conclusions offer significant practical value for dataset curation and budget allocation strategies in real-world applications, where collecting clean data can be expensive.", "weaknesses": "* The analysis is limited to Gaussian noise corruption and discrete distributions with finite support. Expanding this framework to continuous distributions and non-Gaussian noise would increase its impact.\n* The proposed method assumes that the noise level is known in advance, which may not be the case in real-world scenarios. Incorporating techniques and analysis to handle unknown noise levels would make the approach more practical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)