Understanding the Gain from Data Filtering in Multimodal Contrastive Learning
Authors: Divyansh Pareek
Sewoong Oh
Simon Shaolei Du
Venue: NeurIPS 2025 poster ()
Keywords: Data filtering
Multimodal contrastive learning
Theory of contrastive learning
CLIP
Teacher-student filtering
Primary area: theory
TL;DR: We theoretically analyze the benefit of filtering a noisy training dataset on model performance in multimodal contrastive learning, and identify two regimes with different amounts of gain.

Abstract: The success of modern multimodal representation learning relies on internet-scale datasets. Due to the low quality of a large fraction of raw web data, data curation has become a critical step in the training pipeline. Filtering using a trained model (i.e., teacher-based filtering) has emerged as a successful solution, leveraging a pre-trained model to compute quality scores. 
To explain the empirical success of teacher-based filtering, we characterize the performance of filtered contrastive learning under the standard bimodal data generation model. Denoting $\eta\in(0,1]$ as the fraction of data with correctly matched modalities among $n$ paired samples, we utilize a linear contrastive learning setup to show a provable benefit of data filtering: $(i)$ the error without filtering is upper and lower bounded by $\frac{1}{\eta \sqrt{n}}$, and $(ii)$ the error with teacher-based filtering is upper bounded by $\frac{1}{\sqrt{\eta n}}$ in the large $\eta$ regime, and by $\frac{1}{\sqrt{n}}$ in the small $\eta$ regime.

Understanding the Gain from Data Filtering in Multimodal Contrastive Learning
Divyansh Pareek
Sewoong Oh
Simon S. Du
Paul G. Allen School of Computer Science and Engineering University of Washington, Seattle, WA idpareek, ssdu) @cs www.wwwwwwwttonnooooo edu
Abstract
The success of modern multimodal representation learning relies on interet-scaaee datasets. Due to the low quality of a large fraction of raw web data, data curation has become a critical step in the training pipeline. Filtering using trained model (i.e., teacher-based filtering) has emerged as a successful solution, leveraging a pre-trained model to compute quality scores. To explain the empirical success of teacher- based filtering, we characterize the performance of filtered contrastive learning under the standard bimodal data generation model. Denoting 1j E (0, the fraction of data with correctly matched modalities among paired samples, we utilize a linear contrastive learning setup to show a provable benefit of data filtering: (i) the error without filtering is upper and lower bounded by 1/n/n, and (ii) the error with teacher- based filtering is upper bounded by 1/ V/yaa in the large 77 regime, and by 1/ /n in the small regime.
Introduction
The seminal work of Radford et al. 29 introduced CL.PP, a large-scale multimodal training paradigm that leverages contrastive learning image and language modalities. This marked a significant advancement in general purpose representation learning that enabled unprecedented zero-shot down- stream performance. A crucial factor in the success of CLIP and other lision-language models (VLMs) was the shift towards training on massive datasets 39 often comprising billions of image- text pairs scraped from the internet (e.g.. LAION-5B (30 and DataComp- 1B (TI.. The sheer quantity of data unlocks the capability to learn robust representations [.. However, due to the inherently noisy nature of web data, this introduces significant challenges regarding the quality, resulting the need for data curation. Smaller but higher quality subsets of the data have been observed to result in better models than larger but noisier datasets 33 25 [T] Gadre al. [I] Figure 2] observe that training on only a selected 30% of the dataset results in better performing model than training on the full corpus. handle such significant fraction low-quality data, data curation has become a critical step in modern internet-scale pretraining pipeline of foundation models 1
For vasion-language datasets, number of methods have been introduced for data filtering 10 35 18
8, (22). Among these, teacher-based filtering, where a pre-trained model is used to score samples and retain high-quality ones, has emerged as particularly effective strategy 10 K5 This approach marks progression from earlier efforts which relied on heuristic-based based filtering (e.g., the WIT400M dataset used in CLIP (29). Subsequent and ongoing curation efforts have increasingly leveraged strong existing models, like CLIP itself, to refine datasets further 30
In the theory community, the success of CLIP models has been attributed
factors: the choice of using a contrastive loss and the use multimodal datasets. series of modeling and analyses followed to explain the benefits from these two factors under various scenarios 24
13 6 7
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

However, despite the empirical successes of data filtering in the CLIP training pipeline, theoretical understanding of this phenomenon has been lacking. Our goal is to provide a deeper understanding of the benefits of using teacher-based data filtering in the CLIP training pipeline, i.e., multimodal representation learning with a contrastive loss. In particular, we aim to understand the benefits of data filtering against the baseline of contrastive learning without filtering by focusing on one key parameter of interest: the fraction of high-quality data present. Using r E (0, 1] to denote the fraction of high-quality data pairs within the dataset, for both the filtering and no-filtering approaches, we ask the question: How does the quality of the learned representation behave as a function of r)?
The choice of the data corruption model is crucial. In the related field of robust statistics, similar questions have been studied under adversarial corruptions. However, for large multimodal datasets, we posit that stochastic corruption model is more relevant in capturing the nature of real data. For instance, in vision-language data, a significant portion of the misalignment arises randomly: images paired with irrelevant or tangentially related captions due to the processes of automated web scraping and the uncontrolled nature of internet data (see, e.g.. [26] Figure 1] for examples). We adopt such a model (detailed in Section 3.I.. where fraction 7i of pairs are correctly aligned, while the remaining 1 - 1y fraction has mismatched modalities. Under the stochastic corruption model of Section 3.1 and the contrastive learning setup of Section 3.2 we analyze the performance of teacher-based filtering (Figure Ic and compare against the baseline of no filtering (Figure Ta
Contributions. We demonstrate a provable benefit of data filtering. The error of the unfiltered contrastive learning with n samples and 17 clean fraction depends as 1/nvT, as shown by an upper bound in [ (result from Nakada et al. [2 Theorem 3. and lower bound in Proposition [ On the other hand, for teacher-based filtering (Theorem [ main result), the dependency on v) is improved to 1/ 1/ when is large, and to 1/vl when 1) is small. Note that our result includes the training of the teacher model on the given dataset, i.c., we do not assume the existence of any strong pre-trained model. In Section 7 we empirically demonstrate the benefit of teacher- based data filtering synthetic experimental setting. Figure verifies the !/1 dependence of the unfiltered contrastive learning, and the improved dependence achieved by the teacher-based filtering in two regimes, namely 1/ve for large 1) and independent of for small 17. Figure 3b restates the finding of Fang et al. [IO] Figure 4] to show that the qualitative observation of improved 77 dependence via filtering holds true even with real data.
2 Related work
Our theoretical investigation of data filtering builds upon existing analyses of multimodal contrastive learning (24 14 (3). In particular, Nakada et al. [24] Theorem 3.1] gives the rate for the unfiltered contrastive learning, and we study the rate with data filtering. The theory of contrastive learning (CL) has been studied in many other contexts 13 6 77 (2)] Chen et al. [6] build a theoretical understanding for zero-shot transfer in CLIP-style style models. Huang et al. [13] theoretically compare unimodal and multimodal CL, and Daunhawer et al. 77 study identifiability of the latent factors with the CL. objective. We remark that the assumptions the data generative model across these works are related but sometimes subtly different.
The practical need for data curation arises from the inherent noise in web-scale datasets used for training vision-language models 33 25 and increasingly, large language models [1 20
38
34
37
In the multimodal context, numerous empirical techniques have been developed [10 35
18
22
with community benchmarks like DataComp [TT facilitating systematic evaluation.
Teacher-buat based filtering. the focus of our work, is widely adopted and effective empirical strategy
[5 33], but we note that other approaches have also been explored, in particular, editing bad data
(with some theoretical explanations (28 4T). However, theoretical studies of data filtering limited. Some works include the study of data selection under weak supervision in general statistical
26
models [19]. and selecting data during training [31]
3 Setup
Section 3. describes our model for multimodal data and the assumptions on the related parameters.
Section 3.2 formulates the contrastive learning objective on data pairs from the model.

---

3.1 Bimodal data model
Building on recent theoretical work in multimodal contrastive learning [36 14 24 the signal has a low-rank structure, while the noise is unstructured and dense. Adopting a linear generative model, the paired bimodal data, x E Rd and T E 12d, is expressed as:
we assume
U= E 3 U
representing, for example, image and text in the case of language data. Here 2, E R' denote the latent variables lying in a shared r-dimensional space that captures the common underlying concept. The first terms Uz and U represent the signals of interest, residing in r-dimensional subspaces spanned by the columns of U and U, and the terms Ç and & represent the dense noise. For simplicity, we assume that the maps U E R and U E Raxr are composed of unit-norm orthogonal columns, fixing the scale of this problem.
We say a bimodal paired example is corrupted if the individual modalities do not correspond to the same latent concept. This models how large fraction of image-text pairs found the internet corrupted by arbitrary captions that are unrelated to the content of the image. We formalize this in Assumption D1 with 7) denoting the clean fraction. Figure Appendix | provides an illustration. For the noise, we assume a Gaussian distribution with a diagonal covariance (Assumption 2.
Assumption 1 (Corruption model). Let 21, 22 .N(0, I,) be two independent draws from the r-dimensional standard Gaussian. For an 17 E (0, 11. the joint distribution on (2, 2) is induced by
w.p. 11
21 v, and
(Clean case)
w.p.
2= 21, 7/2
(Corrupted case)
Assumption 2 (Noise model). The noise { are mutually independent and independent of {z, 3}. and are zero-mean Gaussian variables given by N (0. Ia) and É N (0. "1))
The signal is unit-scale in r-dimensions since |U| = 1 and Cov(2) = L,,, hence the signal-to to--sosse ratios (SNRs) for the two modalities are y (r/d) and 7 (r/d) respectively. This model is parametrized by (1, U, 7,7,7,7 r. d, d),, and the aim is to recover U and U, given paired samples. This is a standard model in bimodal contrastive learning 36 14 24] and is inspired by the spiked covariance model 3,40). Consider an extreme case where the images are matched to randomly shuffled captions. This corresponds to 0, and recovering the subspaces U and Ú becomes akin to two separate unimodal estimation problems, whose optimal (up to constants) error rate known with tight upper and lower bounds 5 Eq. (9)]:
max d (1+x d d
ERR ( K)] x
72
where ERR is defined via the chordal distance between two subspaces in Eq. (4). This follows from the fact that [E[x::]] UUT + Ia. The v//n dependence is expected from the concentration, the /F dependence comes from the error metric being chordal (frobenius norm) as opposed to projection (spectral norm), and --122 dependence captures how the error vanishes with high SNR. Refer Appendix [B.2 for description of how to arrive at Eq. (2) using the result from Cai al. (5) Eq. (9)]. When y > 0 fraction of data is correctly matched, our goal is to characterize the error rate achieved by the contrastive learning on the paired data and show that data filtering can improve the error rate compared to the baseline of no filtering.
Notation. For matrix USVT and an integer a, let SVD. = V. denote the projection of Q onto its top-a components. Let 1sv(Q) denote the left singular vectors of Q, and 1sv. (Q) denote its top a left singular vectors. Similarly, let rsv(() and rsv.(Q) be defined for the right singular vectors. We use O(.) to denote asymptotic upper bounds, and Ö(.) denote upper bounds with only 17, factors (omitting the dimension and SNR parameters). Similarly, we use the standard notation (..),,(.) to denote asymptotic lower bounds. The notation 2, hides absolute constants, and we write a x b when S b and a Z b holds simultaneously. Additionally, we will sometimes use the random variable e ~ Ber(n) E (0, 1} to denote the (hidden) 'coin toss' in accordance with Assumption I with = 1 denoting to the clean case.
3

---

3.2 Contrastive learning formulation
We utilize a linear contrastive learning framework from 24 By linear we mean (i) the encoders that map the data, 2: and v. to the shared embedding space are linear, and (it) the contrastive loss computed on the embeddings is linear. This setting corresponds the choice of 0, & = Φ Id
maps in Nakada et al. [24, eq 2. an equation that captures a more general contrastive loss framework. We refer the reader to Tian [3 Figure I] for different contrastive learning setups achieved by different choices of dà and Φb
Let G E Rx and G R denote the Iearnable encoders for the input, and I respectively.
Figure S in Appendix A provides a helpful visualization. The similarity score of a pair (x, 2) is
computed as the inner product (Gr, GT)), which is widely used theoretically [24 14 15 33 and
empirically [29[[2) The multimodal contrastive loss maximizes the similarity of observed pairs, while minimizing the similarity of 'generated" pairs. Given n paired samples {(z, 2,)) the
parameters G, G are learned by minimizing the p-regularized objective given by:
G G) = 2n(n 1)
1
88j 88) + Σ (89s sn))) + (G
(3)
where 8, = (Gar,; GT,) for i.j E [n]] is the similarity score, and ( (6
the regularizer with strength p > 0. The regularizer ensures that the learned parameters have finite norms. Indeed, Eq. (6) shows that this objective has closed-form solution with a 1/p multiplier. which becomes infinite if p = O. Note that CLIP 29 does not need regularizer since the inner product taken with normalized vectors (i.e. (//GGa]) Ga: instead of Gz). The parameters and G assumee the knowledge of the latent dimension (since they are of sizes x and r x d). In practice, the latent dimension is typically design choice and is therefore known at training time. Theoretically, assuming the latent dimension is known allows us to isolate the effects of data filtering from the separate, well-studied problem of subspace rank estimation (for e.g., in Cai et (5).
Also note that this objective is in a full-batch setting, i.c. the entire n X n grid of similarities com- puted to maximize the diagonals and minimize the off-diagonals. This does not cause computational issues since the objective has a closed- form solution, given by Eq. (6).
To measure the quality of a solution, we use the chordal distance between two subspaces in Defini- tion 1 This is standard measure of how well G, G recover U, Ú respectively (24 [4].
Definition 1. The error metric for learned embedding G, G is defined as
ERR(G, G) == max {
sin O (rsv (G),
sin θ (rsv G (G).U)
(4)
We note two points. First, the metric only considers the right singular vectors. This is because the essential information in G, G is contained in the right subspaces. Indeed, the loss in Eq. (3) is only affected by G G. which is preserved under the transformation G t AG. G AG for any orthonormal matrix A. Second, the metric uses the sin θ distance, which a geometrically intuitive way to measure closeness between two subspaces (refer to Appendix B. for background).
4 Baseline: unfiltered contrastive learning
We study the error rate of the unfiltered contrastive learning (Figure la We show that the error is upper and lower bounded by Ō (1/n//). The upper bound given Corollary which is a result from Nakada et al. 24. We show matching lower bound in Proposition Corollary 1 (Corollary of (24, Theorem 3.1]). Given dataset of pairs [xx, 1 generated i..dd according to the bimodal data model in Eq. ① satisfying Assumptions and the solution of
minimizing the contrastive loss in Eq. (3) satisfies with probability - exp( (mmxxfd d))):
ERR(G. S 1
maxid, d) (1 1 11 11 +
!
provided the number of samples 2 (1/1²) max(d, d) (1+ ( (1+

---

Filter
Filter
Dataset
Dataset
Filtered
Dataset
Filtered
using Ø+
using Φτ
Train
Train
Train
Train
(a) filtering
(b) Oracle filtering
(c) Teasher-based filtering
Figure I: Our goal is to analyze the Truin-Filler-Tren Train approach illustrated in (c) and show that it improves upon the no filtering approach of (a). Here o² denotes the ground-truth parameters and ø denotes the learned version. In our setting, o² {U, UJ and & (G,
Remark 4.1 (Looseness in SNR parameters compared to Eq. 2)) The dependence on SNR parame- ters (n, () in Corollary 7 is looser than the unimodal estimation counterpart in Eq. (2) As stated, the enror upper bound in Corollary [ does not become zero when + cc. We remark that this is an artifact of the analysis. Indeed tighter analysis is possible that recovers //117-11 term also in the upper bound, for instance, using the ideas in Cai et al. [5] Section 7J, in particular [5] Eq. (39)).
A complete proof of Corollary is presented in Appendix D which is largely reconstruction from Nakada et 24 with some minor corrections. The analysis has three parts. First, the unregularized
term of the contrastive loss in Eq. (3) simplifies to Lo G) -Tr (GS, where Sn dd
denotes the cross-covariance matrix of the data, defined as
S 1
(x.
T
x.
<E(M]
iE(m
Second, the regularized contrastive loss, albeit nonconvex, admits closed-form solution as the SVD of S,,, given in Eq. (6). Due to this, we can directly analyze the solution without the need for optimization analysis.
Lp (G, (c. (G. - 1 SVD, (S.))
arg
min min G.G
(6)
The third key piece concentration of S.. We show finite sample concentration of S,, in operator norm, namely w.h.p. |[s, S E 1/evi, for the limiting quantity (7/2) UÜT, Using a Davis- Kahan like result, we can translate the operator norm concentration to distance between the angles of subspaces, for both left and right singular vectors, yielding w.h.p. ERR G, G) S 1/nvn. Note the dependence on the regularization strength p vanishes (as long as p >> 0) due its appearance in both the numerator (via op-norm concentration) and denominator (since the singular values of scale as 1/p). This sketch describes the 1/1 dependence of the unfiltered contrastive learning. In Proposition 1 show that this dependence is tight. We present proof of Proposition I in Appendix E by constructing a hard problem instance (parameterized by 7)).
Proposition 1. Under the setting of Corollary [ there a class of problem instances with latent dimension = such that the error achieved by the minimizer of Eq. (3) is lower bounded (up to
absolute constants) with probability - 1aap--((max(d d)))
max (dr-1,
ERR(G. G,
G
Our approach: teacher-based filtering
In the previous section, we concluded that the unfiltered contrastive learning achieves tight error dependence of 1/n, this section, we ask: can filtering algorithms improve upon the 1 dependency? Intuitively, expect the answer to be yes, since filtering can identify corrupted samples and remove
5

---

them (increasing the clean fraction 7). Indeed, if the filter could perfectly identify all clean samples, it would achieve a dependence of 1 (since this would be akin to the unfiltered contrastive learning with 1 <- 1 and <- spn). We will now study the dependence of teacher-based filtering.
Teacher-based filtering, which follows Train-Fileer-Tie approach, has proven to be successful method in practice [0]35) In the first training step, a teacher model is trained on (potentially a part of) the dataset. In the filter step, (the remaining part of) the dataset filtered by using the teacher to compute a similarity score to evaluate the quality of each sample. The filtering usually happens by selecting samples with score above a certain threshold 0 e R. the second training step, student model is trained on the filtered dataset. Refer to Figure Ic for an illustration. The student can be initialized the teacher's 's solution, or even at fresh random initialization. The intuition is that the teacher can extract useful signal from the dataset despite the presence of corrupted samples, which can help in identifying and discarding corrupted samples. Algorithm [ describes this process in the setup of Section The split of the dataset into two halves is for the convenience of analysis. by ensuring the filtering rule (which depends on the first half of samples and 6) is independent of the samples being filtered (the second n/2 samples). We now state our main result.
Algorithm 1 Teacher-based filtering in the setup of Section[3]
Input: Dataset D = {2,, Z J Threshold 0 E R.
Step (Train): Obtain GT, Gr by minimizing Eq. (3) on the first samples (x);):)))n//2
Step 2 (Filter): Create Dane (8) from {(z,, ((c,,,))ssa T/)/////2 by retaining sample i iff (GT 22, Gr 2,) 0.
Step 3 (Train): Output G0), G0)) by minimizing Eq. 3 on Dan
Theorem 1. Under the model in Eq. ① satisfying Assumptions and and with r 2 2, there exists threshold 0* R such that, given a dataset of pairs ".), generated i..dd according to the model, the output of Algorithm 1 satisfies with probability - 1app(-2(mmas d))):
ERR
((("), G(()) S min (To.., Tob
provided n Z (1/1²) max (d, d (1 2) (1 7-1). Here To.s, To are defined as
r max max(d, df poly (7 (1
To.s =
+0
np
13 max d} poly (7 11
To
+ +
We provide full proof in Appendix G and discuss the sketch in Section 6 Certain observations are in order. First, we see two regimes of behavior. The error behaves as 1/vg for large values of 1,, and becomes independent of r for small values of (note that 17 still needs large enough to satisfy the requirement of n Z !/n² for theorem to be valid). Both these regimes exhibit a better dependence on 7) than the unfiltered contrastive learning's s rate of 1/T. From the expressions, we note that the switch between the regimes happens at 1//2 (up to constants). Second, this result is stated for the optimal filtering threshold 8". The optimal choice of this hyperparameter depends on the problem quantities, particularly and 17. Understanding this dependence is an interesting direction of research, but outside the scope of the current work. Our analysis considers two fixed choices of that recover each of the regimes. We also present a small experiment varying the filtering threshold 0 in the vicinity of 6* in Appendix H Third, we remark that remains an interesting research question to study whether improved dependence on 17 (at least something better than 1/n) can be achieved with a single training loop on the data (as the reacher-basee filtering is a two-step training process).
It is perhaps surprising that the error can become independent of the clean fraction T), which is better than the oracle rate of 1/w7. This counter intuitive benefit stems from the use of the inner product to compute similarities (Section (32)) on the corruption model given by Assumption I Owing to this, the distribution of the similarity scores before filtering follows a very typical structure, explained in Figure 2 Filtering can retain samples from the right tail of the noisy score distribution Do. and these samples provide useful signal to recover the ground-truth U parameter. Finally, we remark on the assumptions needed for this result. Assumption 2 makes this setting somewhat special, since Nakada
6

---

et al. [24] allow for a general covariance Σş. Eg (with bounded norms) on the noise. Handling more general noise covariance is trivial for unfiltered contrastive learning, but significantly more challenging in the case of filtering. We argue that Assumption [preserves the essential characteristics of the problem though, while simplifying the analysis of filtering. In the following section, we discuss the proof ideas more detail.
Analysis of the filtering algorithm
In this section, we describe the main ideas behind the proof of Theorem [ In Section 6.1] we study the distribution of the scalar score used for filtering samples. In Section 6.2 we use the score characterization to understand filtering by thresholding on the scores.
6.1 The score used for filtering
For sample (ar, ..,, let S(x, 3; A) for matrix A E dædx denote the score of the sample, defined in Eq. (7). This scalar score is meant to capture the quality of the sample ()) Treating (at, .) as a random i.i.d. sample from the model in Section 3.1, we characterize the distribution of the score. Note that the teacher-basee filtering is simply using A G GT score the data (the GT
subscript is used to denote the teacher's parameters). To understand teacher-basee filtering, an intermediate step will be understand filtering using 'oracle' which has access to the ground-truth problem parameters (refer to Figure Lbp. The oracle scores data using A = UÜT, given in Eq. (8) Since G GT - (%/0 UÜT as the number of samples n - 0o, we expect the teacher filtering to resemble the oracle filtering in the large regime. The positive scaling factor of n/p does not affect threshold-baat base filtering, as the ordering of samples remains unchanged.
S(z, A) == x AT.
(7)
S(x, 5; -ŪT) - { T (ū=+t)-ZTZ+e" U C
- =
(8)
zero-mean terms involving (5,5)
Remark 6.1 (Two versions of oracle). There are two possibilities for an 'oracle' this setup. The first kind has access to the ground-truth problem paraneters, which is what we study. The second kind has access to the clean/corrupted status of each sample. The second kind can trivially achieve an error dependence of 1//mn by choosing to only use the clean samples.
Recalling Assumption ! since = z for clean samples, the score in Eq. (8 is defined through the independent randomness in 2, C. For corrupted samples, it is defined via the independent randomness in all E, We characterize the distribution in both cases, detailed in Appendix F The main observations are illustrated in Figure 2a Do denotes the distribution of the score in the corrupted
case, with mean p(Do) = 0 (since v independent), and variance oî (1 + 7 (1+ Similarly, Dj denotes the distribution in the clean case, with mean ((())) (since to squared term), and variance of = r + (1 --) (1 + 5-2). Note that oe < of < 20
2 leading
Since clean and corrupted data mixed with 17, 1 17 proportions, the score of a generic sample from the population is given by the mixture distribution D := ryD1 + D)) Figure 2 provides an illustration of the score distribution D. Due i.i.d. data, the oracle filtering algorithm's 's scores n i.i.d. draws from D. The filtering threshold 0 can be picked in various ways, leading to various algorithms for filtering. The threshold 0 Do corresponds to filtering.
the condition 7, 7, = w(VT) ensures that 7/a, (1), leading separation between the modes of Du and Dj. In this case, the clean and corrupted data become well-separated via the oracle score S(x, T.T).
Remark 6.2. Since du S o = //r (1+
6.2 Analysis of thresholding on the score distribution
In this section, we discuss analysis for the oracle filtering algorithm (Figure Tb which captures the main conceptual ideas of data filtering the setup of Section 3 The proof for the teacher-based filtering (Theorem is given in Appendix G which uses the ideas from this section, along with the
7

---

1-n
Histogram of scores (n=0.3)
Do
Clean
7
Corrupted
D1
000
0
IR
-20
20
40
(a) Theoretical (stylized).
(b) Observed.
Figure 2: Distribution of the oracle score S(x, ã; UÚT) is given by the mixture of Do, Dj with
weights (1 - 7), 17 respectively. Here oy. of depend on parameters T; 717% The threshold 0 E IR is used to filter the datapoints (score > 0 are retained, others are discarded). Subfigure (b) shows the observed histogram in synthetic setting for n = 50000 samples with r 16,
10
operator norm concentration in Corollary to bound the deviation caused by the difference between the teacher scores and the oracle scores. Given dataset ((r,, ..t) ] let (0) denote the number
of samples retained after oracle filtering, and let (0) C [nd] denote the indices of the samples
selected, defined by the condition i (0)( > define S,, (0) to be the empirical cross-covariance of the filtered data, given by Eq. (
S(x;, He; UÚT)= 0. Analogous to Eq. 5 we
(0) ==
Taal (0) Σ
(x: - x) 2
(0) = nP(0)
Σ iETal0)
(9)
ic (0)
( = S. (0)
B| 2T |S 7; UŪT) 0]
(10)
Observe that similar to Eq. (6) the closed-form solution of the optimization holds even on the filtered dataset. The step that changes is the concentration, namely, the characterization of how S,, concentrates as n increases, according to the distributions of the involved random quantities. In the following, we argue that (0) concentrates S(O), given by Eq. 10 and characterize the behavior of (0) to recover a guarantee akin to Theorem 1
Notation, We set up some useful notation on the score distributions Do, DD from Figure 2a For any a E R. let Po(a) of the upper tails of the corrupted and clean parts respectively, and let P(a) = (Z a) PP + (1 - Pa(a) denote the probability of selection from the mixture distribution. Similarly for expectations, define Ea(a) = EZ~D, [Z al. (a) = Ez~D, [Z| Z a).
Pz=D. (Z > a) and (a(a) = Pz=D, (Z > a) denote the probabilities
Concentration of (?) to S(0). We claim that (0) ~ (0) by using two approximations. First, the un-centered version in (!) approximates the centered version in S (0). Second, although (0) is random quantity, concentrates around n()) We formally bound the error due to both these approximations in the full proof. Since the filtering threshold is chosen independent of the samples being filtered, the selected samples satisfy the i.i.d property under the conditional law of the score being above 0. This allows to show that the approximate version, 5, (0), concentrates around its expectation, S(0), by bounding the spectral norm of the difference via a Matrix-Berrstein type inequality. Overall, we get
maxfd, d} TP((0)
w.p. 1 exp( wepppxp(mmxxxeeeee ((max(d, -0) $
(11)
Analysis of S(0) and P(0). Simplifying S(I) reveals that is simply a scaled version of U with the scaling coefficient depending 0 described by the conditional expectations (f) and E1 (0). Concretely, S0) 1/r (1) (0) + (1 - 7)) Fo) UÚT. Owing to this, the application of a Davis-Kahan result on Eq. will dictate the guarantee of recovering U, Ü for the filtering algorithm. The error behaves
1
ERR X (n FA
Po(0) Vn (1 7) Eo( +1) +1
8

---

The behavior of the functions (o), E (0) and Po))), (0) precisely quantify this rate. As sanity check, setting
0O recovers the 1/4 behavior of the unfiltered contrastive learning, as (- = т, (-(- = O and Pi (-xo) = 1, (-(-oc) = 1. Since (0), Fy (0) are increasing functions in 8, whereas (o) (0) are decreasing, we observe a tradeoff. A larger threshold 0 results in larger conditional expectations (0), F. (0), but smaller probabilities of selection Po(O), Pt (0). In the Appendix, we formally characterize this behavior, involving calculations on the conditional expectations and probabilities of the Gaussian distribution. Here, we discuss the two choices of that recover the two regimes of the filtering behavior. The threshold = results in 0.5, recovering the independent of 1) regime. And the threshold & = 7/2 results in E1 (7/2) 2 r. Eo(7/2) 2 7/2 (using a trivial lower bound for the conditional expectation). and Pi (1(r22
E1 (0) 2 r, (O) 2 3/7 and Pi (0) 0.5, (0(
0.5 (but Po(*/2) is small), recovering the 1/V7 regime. The optimal 0 will achieve a rate better than the above two special points, hence the upper bound on the error is given by the min of these two regimes, recovering the upper bound in Theorem T
7 Experiments
ERRIG G. G! v/s
ImageNet Accuracy v/s
No ttritg toxdes bosod Raving
No fitiing
Toacher bosed fitrinng
Accuawy
-2
0.80
(Enn
0.80
-4
0.75
(100%)
[30%]
[0.15]
50
0.26
0.5
0.75
1.8
lopoylLin) [cleen fraction]
(20)
[slcan fraction]
(a) Synthetic experiment.
(b) Real experiment, Fang et al. 110 Figure 4].
Figure 3: (a). Observed dependence of ERR(G, G) on r for a synthetic experiment. The error of the unfiltered contrastive learning follows a 1/n dependence, but deviates for small 7) since the requirement of n 2 1/,, in Corollary | gets violated. The error of the filtering algorithm follows 1/v7 dependence in the large 7) (or small 1/v) regime, and an independent of 1) dependence in the small regime. Going beyond to even smaller causes deviations since Theorem I Jalso requires ス 1/4². The teacher-based filtering is with the threshold f 0. (b). similar trend on real data observed by Fang et al. [10. The y-axis shows 1 - Accuracy, which is different than the error metric in (a). However, we note that the qualitative trend of the orange line having a smaller slope than the blue line still holds. Numbers from Fang et al. [10 are reproduced with permission.
In this section, we validate our theoretical results with synthetic setup. With parameters = 10, 8, = 4, and SNR y = 7 = 10 and with randomly generated U, U, we generate n = 10M samples according to the model in Section [.1] and vary the clean fraction r,. We experiment over 10 values of 7 geometrically decreasing from 1 to
This experiment was run on a cluster of 50 CPUs with 500G memory, and required less than 10 minutes. Figure 3a shows the result and discusses the observations, which validate Corollary I and Theorem [ To extend these observations to real settings, the main limitations are posed by the modeling assumptions in Section 33 Despite the limitations, Figure 3b shows evidence that the qualitative conclusions drawn from the theory hold with real image-text data too. Concretely, it shows that the downstream model performance on reducing the clean fraction degrades more steeply without data filtering.
8 Conclusion and Broader Impacts
This paper presents a theoretical investigation into teacher-based data filtering for multimodal con- trastive learning with stochastically corrupted data. We rigorously establish its benefit, demonstrating

---

that filtering improves the error dependence on the clean data fraction, 17. from 1/n (no filtering) to 1/ VT in the large 7 regime, and perhaps surprisingly, independent of 1) the small 7) regime. The latter finding suggests that reacher-based filtering can be particularly beneficial when data quality is low, achieving performance independent of the initial clean fraction. Our results provide a formal basis for the empirical success of teacher- based data filtering. The main limitations are posed by the assumption of linearity Section 3 and the model of stochastic corruptions in Assumption [| Future work could explore the optimal selection of filtering thresholds and investigate whether similar gains can be achieved with one-step filtering algorithms.
Our contributions are largely on the theoretical understanding of data filtering, and its potential benefits. At a high-level, effective data filtering can reduce the compute cost needed to train models, which has positive potential impacts through more judicious use of energy resources. On the other hand, data filtering can exacerbate the biases present dataset by selecting certain subpopulations more than the others. If this goes unchecked, it has potential negative impacts to society.
Acknowledgements
SSD acknowledges the support of NSF DMS 2134106, NSF IIS 2143493, the Sloan Fellowship, and the A12050 program at Schmidt Sciences. SO acknowledges the support of NSF grants no. 2112471, 2229876, and 2505865.
References
[1] A. Albalak, Y. Elazar, S. M. Xie, S. Longpre, N. Lambert, X. Wang, N. Muennighoff, B. Hou, L.. Pan, H. Jeong, et survey on data selection for language models. arXiv preprint 2401v:2402.16627, 2024.
[2] M. Bagnoli and T. Bergstrom. Log-concave probability and its applications. Economic Theory, 26(2), 2005.
[3] Z. Bai and J. Yao. On sample eigenvalues in a generalized spiked population model. Journal of Multivariate Analysis, 106, 2012. ISSN 0047-259X.
[4] F. Bunea and L. Xiao. On the sample covariance matrix estimator of reduced effective rank population matrices, with applications to fpca. Bernoulli, 21(2). 2015.
[5] T. Cai, Z. Ma, and Y. Wu. Optimal estimation and rank detection for sparse spiked covariance matrices, 2016. URL
orraaiiii.rraaaaaaaaaaoaaaoeeaae http//ab/11333 1305. 3235
[6] Z. Chen, Y. Deng. Li, and Q. Gu. Understanding transferable representation learning and zero-shot transfer in CLIP, 2024.
[7] I. Daunhawer, A. Bizeul, E. Palumbo, A. Marx, and J. E. Vogt. Identifiability results for multimodal contrastive learning, 2023.
[8] L. Engstrom, A. Ilyas, B. Chen, A. Feldmann, W. Moses, and A. Madry. Optimizing ml training with metagradient descent. arXiv preprint 25xxi::5503335// 2025.
[9] A. Fang, G. Ilharco, M. Wortsman, Y. Wan, V. Shankar, A. Dave, and I.. Schmidt. Data determines distributional robustness in contrastive language image pre-training (clip). In International Conference Machine Learning, pages 6216-6234. PMLR, 2022.
[10] A. Fang, A. M. Jose, A. Jain, L. Schmidt, A. Toshev, and V. Shankar. Data filtering networks.
arXiv preprint arXiv:23009. 17425, 2023.
[11] S. Y. Gadre, G. Ilharco, A. Fang. J. Hayase, G. Smyrnis. T. Nguyen, R. Marten, M. Wortsman, D. Ghosh, Zhang, al. Datacomp: In search of the next generation of multimodal datasets. Advances in Neural Information Processing Systems, 36, 2023.
[12] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 7729-97388 2020.
[13] W. Huang, A. Han, Y. Chen, Y. Cao, Z. Xu, and T. Suzuki. On the comparison between multi-modal and single-modal contrastive learning, 2024.
[14] W. Ji, Z. Deng, R. Nakada, Zou, and I.. Zhang. The power of contrast for feature learning: theoretical analysis. Journal of Machine Learning Research, 24(330):1-78) 2023.
10

---

[15] L. Jing, P. Vincent, Y. LeCun, and Y. Tian. Understanding dimensional collapse in contrastive self-supervised learning. arXiv preprint arXiv:2110.093488 2021.
[16] I. M. Johnstone. On the distribution of the largest eigenvalue in principal components analysis. The Annals of Statistics, 2001.
[17] S. Joshi, A. Jain, A. Payani, and B. Mirzasoleiman. Data-efficient contrastive language-image pretraining: Prioritizing data quality over quantity, 2024.
[18] W. Kim, S. Chun, T. Kim, D. Han, and S. Yun. Hype: Hyperbolic entailment filtering for underspecified images and texts. In European Conference on Computer Vision. Springer, 2024.
[19] G. Kolossov, A. Montanari, and P. Tandon. Towards a statistical theory of data selection under weak supervision, 2023.
[20] Z. Lin, Z. Gou, Y. Gong, X. Liu, Y. Shen, R. Xu, C. Lin, Y. Yang, J. Jiao, N. Duan, and W. Chen. Rho-1: Not all tokens are what you need, 2024.
[21] L. Lovász and S. Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms, 30(3). 2007.
[22] P. Maini, S. Goyal, 7. C. Lipton, J. 7. Kolter, and A. Raghunathan. T-mars: Improving visual representations by cireumventing text feature learning. arXiv preprint arXiv:2307.0311 00.00377.3,,,,. 2023.
[23] A. M. Mathai and S. B. Provost. Quadratic forms in random variables: theory and applications.
[24] R. Nakada, H. I. Gulluk, Z. Deng, W. Ji, J. Zou, and L. Zhang. Understanding multimodal contrastive learning and incorporating unpaired data, 2023.
[25] Nguyen, G. Ilharco, M. Wortsman, Oh, and I.. Schmidt. Quality not quantity: On the interaction between dataset design and robustness of clip. Advances in Neural Information Processing Systems, 35:21455- 469, 2022.
[26] Nguyen, Y. Gadre, G. Ilharco, S. Oh, and L. Schmidt. Improving multimodal datasets with image captioning. Advances in Neural Information Processing Systems, 36, 2023.
[27] K. Oko, L. Lin, Y. Cai, and S. Mci. A statistical theory of contrastive pre-training and multimodal generative ai. arXiv preprint arXiv:2501 04641, 2025.
[28) D. Pareek, S. S. Du, and S. Oh. Understanding the gains from repeated self-distillation, 2024.
[29] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, Mishkin, J. Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning. PmLR, 2021.
[30] C. Schuhmann, R. Beaumont, R. Vencu, C. Gordon, R. Wightman, M. Cherti, T. Coombes, A. Katta, C. Mullis, M. Wortsman, et al. Laion-5b: An open large-scale dataset for training next generation image-text models. Advances in neural information processing systems, 35: 25278- 27794,, 2022.
[31] V. Shah, X. Wu, and S. Sanghavi. Choosing the sample with lowest loss makes sgd robust. In International Conference on Artificial Intelligence and Statistics. PMLR, 2020.
[32] M. Shechter and Y. Carmon. Filter like you test: Data-driven data filtering for clip pretraining. arXiv preprint arXiv:2503.088 08800, 2025.
[33] Y. Tian. Understanding deep contrastive learning via coordinate-wise optimization. Advances in Neural Information Processing Systems, 35:19511 2022.
[34] J. T. Wang, T. Wu, D. Song. P. Mittal, and R. Jia. Greats: Online selection of high-quality data for 11m training in every iteration. Advances in Neural Information Processing Systems, 37, 2024.
[35] Y. Wang, Y. Chen, W. Yan, A. Fang. W. Zhou, K. G. Jamieson, and S. S. Du. Cliploss and norm-based based data selection methods for multimodal contrastive learning. Advances in Neural Information Processing Systems, 37, 2024.
[36] Z. Wen and Y. Li. Toward understanding the feature learning process of supervuue contrastive learning. In International Conference on Machine Learning, pages 11112-11122. PMLR, 2021.
[37] A. Wettig, A. Gupta, S. Malik, and D. Chen. Qurating: Selecting high-quality data for training language models. arXiv preprint arXwv:2402.09739, 2024.

---

[38] S. M. Xie, S. Santurkar, T. Ma, and P. S. Liang. Data selection for language models via importance resampling. Advances in Neural Information Processing Systems, 36:34201-34227, 2023.
[39] H. Xu, S. Xie, E. Tan, P.-Y. Huang, R. Howes, V. Sharma, S.-W. Li, G. Ghosh, L. Zettlemoyer, and C. Feichtenhofer. Demystifying clip data. arXiv preprint arXiv:2309. /6671, 2023.
[40] A. R. Zhang, T. T. Cai, and Y. Wu. Heteroskedastic pea: Algorithm, optimality, and applications, 2021.
[41] B. Zhu, M. Jordan, and J. Jiao, Iterative data smoothing: Mitigating reward overfitting and overoptimization in RLHF, 2024.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction are written to summarize the sections that follow. The main contributions are theoretical, and their key takeaways are mentioned in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations of the work include assumptions and settings, and are discussed with the text (e.g. section 3.1 discusses the modeling assumptions and their limitations).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: The theoretical results contributed are Proposition and Theorem | The assumptions discussed in section 3.1 and the proof' are provided in the Appendix (sections] and
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experiments (synthetic) are discussed in section and necessary details are provided (e.g. parameter settings).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification: We do not publish code, primarily because the synthetic experiments serve for the verification the theory and are relatively simple to implement.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
wublic//giide//Cdestbbmmsss www.aaammmiioooooooooooooooee for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips //ips.cc/ cttp:/scccpbblccgguiieeeeees guides /ttpp//bbb///.....o////////aaiaa
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: There is just one hyperparameter, the filtering threshold 6. Section (Figure Bal includes the necessary details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Figure 3a includes error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section includes these details.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
We adhere to the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Section discusses the broader impacts of this work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is a theoretical study and no real-world data/models have been used.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No existing assets (codebases/dattasetsstt)) have been used.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
No new assets have been introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not involve LLMs as any important, original, or non-standary components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standart components.
Please refer to our LLM policy ftteps://neuriiee /t/CCooffeeences//2222 for what should or should be described.
19

---

A Additional Illustrations
In this section, we provide some useful illustrations. Figure illustrates the corruption model described in Assumption 1 Figure iillssrates the linear maps G, G used to generate the embeddings from observed data (according to the model in F) Figure 6 accompanies Remark A.1
R2
Rd
2 IR
f
2, E R f
Rdd
Rd
(b) Corrupted data (w.p. 1 1)) 2, miid Pz- Figure 4: Model for stochastic corruptions. In this work, the forward maps f. are linear (refer to Eq. (T)) and the latent distributions are Gaussians.
(a) Clean data (w.p. 11): pz, =22.
Rd
G
R
E Rd
Figure 5: On seeing multimodal data (x, T). linear maps G, G (learnable parameters) create the embeddings that lie in R' (the knowledge of r, the true latent dimension, is assumed). The similarity is measured with the inner product (Ga, G.)
independent: (/ En)
correlated: (0,
Figure 6: Illustration of the joint distribution of (x, .). The overall distribution is mixture of two zero mean Gaussians: the independent case (w.p. - 11) and the correlated case (w.p. 1)).
Remark A.1. The distribution of (x, IRd+d from Section 3.1 is mixture of two zero-mean Gaussians. With weight 1, the covariance matrix is Ej (for I, i.e. the clean case). With weight 1 TJ, the covariance is Eo (for c= =0). Figure provides an illustration.
UU + "Ia
UÙT UÜ
UUT
+
Σ =
Σg
ÚUT
1
UÜ
I
20

---

B Background
This section covers some useful background concepts.
B.1 Measuring the distance between subspaces
The concept of principal angles provides geometrically intuitive way to measure the closeness between two subspaces. Let X' and y be two r-dimensional subspaces within a larger Euclidean space Rd. There exist principal angles 0 I 01 I 02 S -.. S 7/2 that describe the relative orientation of these subspaces.
f represents the smallest possible angle between any two unit vectors E X and y V.
Subsequent angles 0s capture the minimum angles within directions orthogonal to those defining the previous angles
The cosines (0s( measure the alignment (1 means aligned, 0 means orthogonal within that principal direction), while the sines sin(o.) measure the separation or angle.
To aggregate this information into a single distance metric, we often use the frobenius norm of the sine of the principal angles, denoted sin ((X,))) It is defined as
sin ((X,)))
Σ sin sin2 (0.)
This metric provides overall measure of the difference between the subspaces. It's zero if and only = (since all 02 = 0), and increases as the subspaces diverge.
Computing this metric relies on matrix operations involving orthonormal bases for the subspaces. Let
X E IR dR be matrix whose columns form an orthonormal basis for X' (so X X I,). Similarly, let Y E Rdxr be matrix with orthonormal columns forming a basis for y. The distance metric sin ((,))) can be computed using X and Y via the following formula
|| sin O(X, ] = |
Here, X is any d (d-r) matrix such that its columns form an orthonormal basis for the orthogonal complement of X. denoted X This means that the combined matrix [X X must be a d x d orthogonal matrix. Notationally, we often just write || sin ( Y)IlF instead of using X, N.
B.2 Optimal unimodal estimation rates in the spiked covariance model
Eq. [ uses the well-known spiked covariance model for each of the two modalities, originally introduced by Johnstone [16] and well-studied in the literature 3 optimal (minimax) estimation rates for the covariance matrix (i.c. UU +y +y=LL>) and the principal
40
5]. Cai et al. [5] establish
subspace (i.e. U) in more general sparse spiked covariance model. In partieular, [5] Eq. (7) describes the minimax rate for covariance estimation, and 5 Eq. (9)] describes the minimax rate for subspace estimation. We use the latter result to get Eq. (2) Since the problem of subspace estimation is invariant to scaling, we instantiate [5] Eq. (9)] for the estimation of data with covariance
JUU Ig (since a is assumed in (5) Eq. (I)] fix the problem scaling). With this, the paramaters map as À - P.P d and k = d (since our model is not sparse). This establishes a rate
(up constants) of di 1(17 for the estimation in 2-norm. An additional factor of /F appears since the Frobenius-norm (i.e. the chordal distance in Definition I and Eq. 2 follows.
C Lemmas
This section presents Lemmas used in the proofs. The first three Lemmas are standard results in the literature, and we include them without proof. Lemma 1 (Weyl's Inequality). For matrices A, B RRxx, let p min(m, n) and let a (M) 2 (2(M) 2 ... (M) 2 0 denote the singular values for M E (A,B). B}. Then, for all j = 1,....P
holds that
(((A)-o,CC)
< BlI2
21

---

Lemma 2 (Wedin's s Theorem). Let A, A, E R be matrices of the same size. Letr S min(m. m) be the rank of both A, A, and let the SVDs be A UVV and Å = Ú.VT. Let (, >> 0 denote the y singular value of A, and assume or (A() > || 2/ Then holds that:
11 Alle
sin sin
or (A) 11
All2
1 A
sin sin m/
or (A) - 11 All2
Lemma 3 (Whittle's Inequality). Let X2.... be a sequence of independent random variables such that: (3) 0 all k 2 and (ii) the distribution of each Xs is symmetric about zero (i.e., X5 and - k have the same distribution). Let Sn >k=1 Xx be the partial sum (with So = 0). Φ R IR is a convex function such that ((0) then the sequence (l(((,)) is non-decreasing
in n. That is, for all n 1:
[[)(S,)] 2 ([d(Sn
Lemma 4. Let A, B E RMxx with rank(A) 2 1. 151 Bl1 < or(A), then for every
t e [0, 11. it holds that rank +)A+ tB) 2 r.
Proof. Let X, = (1 - A + LB. For any matrices M, N and any k
(x(M) 2 (NV ||M N122,
which follows Lemmal 1 Applying this with M = X,, N = A, and k =r
(X,) 2 (A) |XX; All2 (A) A BlI2 2 (A ||4 Bll2 > 0,
for all t E [0, 1] because ||A B| < (A). Hence a, (X,)) > 0, so rank (X,) 2
L
Lemma 5. Let X be a random variable with a log- density, mean px. and variance x3x- holds that
E
X
0 < 0 + eox for 0 2 px
Proof. Let m(x) E[X - x x > x] be the mean residual life function. We want to bound E|X X > 0] 0 + m0)) for 0 2 px. Due to log-concavity of X, m(x) is non-increasing (see, eg, Bagnoli and Bergstrom 2 Theorem 6)). Since m(x) is non-increasing, m(0) S m(ux)
E[X- X > px]. We will now bound the conditional expectation for this case of f = PX-
Let X px. Then E|y] and V(Y) -xx m(ux) E|Y Y 0J
BY P(Y0)) where
Y- max(0, Y). We know E] B[ V| = ox. As for the denominator, know that for any random variable X with a Lon-concave density and mean μx, P(X 2 px) 2 1/e (see, eg, Lovász and Vempala [21] Lemma 5.4]). Thus, m(ux) S ex =oxx
I/e
Lemma 6. Let x, E Rd and N, 5 E Rd be random vectors. Assume that the pair (x. 3) is independent of the pair (y. ÿ). Let A be a fixed d matrix and let 0 E R be a scalar threshold. Define the events C. {x AF 0) and C {y T Aÿj > 0). Assume that these events have non-zero probability, i.e., P(C,) > 0 and P(C,) > 0. Then the conditional expectation of the outer product zÿ" given both events C₂ and Cy factorizes as follows:
)
E ry
A
A
A
0
E
A
Proof. The definition of conditional expectation given multiple events is conditioning on their intersection. Here I denotes the indicator function.
E [ Icnnc, P(C.nC,))
E [ Cz. C2
E .n |C,
The event C2 is determined solely by the random variables x and 7. The event Cg determined solely by the random variables y and ÿ. By the initial assumption, the pair (z, Z) is independent of
22

---

the pair (3. 17. Therefore, the event C2 is independent of the event Cg- This implies P(C,, n nCy)
P(C,)) P(Cy), Hence the denominator factorizes (and is non-zero since P(C,) 0 and P(C,) > 0).
Now consider the numerator. Since Cz and Cy are independent, Tc,nc, = Tc, No,, which implies
ay Ic,nc,l = B [zy Ic,ll,, = E [a llc.] E BT
again, due to independence of the pairs. Hence numerator also factorizes.
Lemma 7. Let x E T&d and ā E Rad be random vectors such that their j distribution is multivariate normal distribution with zero mean. Let A be fixed d matrix, and consider the conditioning event R {(x, x_ A > 0} for some threshold 0 E R. Assume that the probability of this event is non-zero. Le.. P(R) 0. Then
E x
A
8 = 0I
Proof. Let Z = (x. Rd+. The joint probability density function of Z, denoted by p(Z),
corresponds the (0, joinn) distribution for some covariance matrix Ejoint. The conditional expectation is defined as:
zxZ) dz JR dZ
JR x p() dz
x AF
8 E Z R
P(R)
We focus the numerator integral and show that it is zero owing to symmetry. First note that p( Z)
symmetric around the origin. That is, p(Z) = p(-Z) ) for all Z IR++d, Second, observe that
under the transformation + Z, the condition becomes (-u) A- > which simplifies to
Aũ Thus, the region symmetric with respect to the origin: Z
-Z R. D
Lemma 8. Consider the random variable 2 == where v are jointly Gaussian as
( ())~'(
(0.
oh 2
2)))
N
with o o and S G.
Let Yam be independent copies. The conditional expectation is upper and lower bounded as
{,,0 [1 for all 0 ER,
E
Zk
0
max
{:: 0 + +e
0200 + 22
E
21
2k >
8
S max
for 0 20
r
For the specific case of = (i.e. u, independent) and 0 = 0, a stronger lower bound is
2 πO
E
2k
0
2
oa o.
Proof. Simplify the expression. Observe that 24 are i.i.d. random variables. The expectation is
E[sa] = E(ue] = (since E[u] = E(v]). Let S = Σx= 2k, and let (.(.) denote the PDF of The expectation is EjS] = ry, and the variance is V[S] = r (a +
Due to the symmetry among the i.i.d. variables zk. the conditional expectation E| IS 0] the same for all i E {L,, {I,..., Let Q()) = E[z, S > 0J. By linearity of expectation, we have
E S 0 E
2k S> 0
Eizy S 0 =
k=1
Q(0) E[S|S>0)
(12)
23

---

Proof of lower bounds: general case lower bound 0. Observe that
aa
100
8 sps
(s)ds
E 0
(13)
J ps ps(s)
0 ps(s)
0
1g ps(s)ds
Combining this with Eq. shows the 0/r lower bound.
Proof of lower bounds: general case lower bound 7. For this, we show E[S] S 0] is non- decreasing in 0. Let h(0) | S 0). Using Eq. (13). its derivative is given by
psps( Jo (s(s) + ps(0) So sps(s)ds
k((0)
P(S 0)2
ps( P(S > 0)2
88 8- 0) 20
20.
(14)
Thus |[S| S > # non-decreasing limit in the limit 9 + -o)). Since E[s] = ry, using this in Eq. (12) shows the lower bound of 7
In particular, E[S S 0) 2 E[S] (i.e. the unconditional
Proof of lower bounds: the specific case of 7 0 and 0 0. Since the distribution of zμ is symmetric around zero, the distribution of S = Σx 2 is also symmetric around zero. Therefore, P(S > 0) = 1/2. Using this, we get
S0 sps(s)ds P(S >0
=2 / sps(s)ds.
E|S|S> S 0J
(15)
Also, the expectation of the absolute value is B[[s[] 1 (s)psss Due to symmetry (i.e. ps(-s) ps)))), we get
E||s|| 1 (-s) ps(s)ds + So² sps(s)ds= 2 / sps(s)ds.
(16)
Using Eq.
15 and Eq. 16). we get
E S 0] = B|S = E
(t) |1
Bl[m 0n
E [m |11 = B[|u]]] B[eel
(using independence)
= o.oo E[la|]2 = au
(for a ~ (0, 1))
Eq (f) holds intuitively. To formally show it, we invoke Lemma 3 (Whitlee's incquality) on the convex function ((x) |z]. Using this with Eq. (12) gives the desired result.
Proof of the upper bound. The probability density function of 2 ue is given by
1
(- pz
(
|z||
[2(x) 2o.ovvI- exp
Ko
p2)
where p 7=1((o,o,,) denotes the correlation factor. Note that lpl is ensured via 7 < 0, in the lemma statement. The function Ko(a|æl) is log-concave for 0. The term exp(hz) is log-linear (hence log-concave). The product of log-concave functions is log-concave. Thus, fx(x) log-concave. Since S is sum of r i.i.d. random variables with log log-concave densities, S also has
log-concave density. We use Lemma 5 to get that E S 0 < 0 +0 ereerrogo + for 0 2 my. For [0, we use the non-decreasing property of E Eq. I2 concludes the argument.
0) from Eq. 14 Plugging into
24

---

Lemma 9. Consider Gaussian random variables I, y E R,, such that
( ~ N N (0,, astr
axy I, ayt. ))
Ozy ozwLr) Ir
with ax, ay > 0, Dry 2 0.
For A E IR define A(f) == E [xy'
|x y > 0. It holds that A0) satisfies
( = f(0) I,
where [0) is scalar function of 0 E RR such that
0
agdy aay f(0) max
max
awy:
azy-
In the special case of Ozy O. it further holds that f(0) 2//aaa/TT..
Proof. We first build an intuition for the quantity (0) E RR'"" For = -0, (0)) becomes the unconditional expectation, which is Ozzy I according to the given covariance structure. As 0 increases in IR, we expect A (0) to increase.
(0) is diagonal. We first show that (0) is diagonal matrix. The (i,j)-th entry is A() B[r,y; 7 > 0). where Z = x y = Σ =1=1 Tri Consider the transformation T; R2rr - R22r that maps (xr, y) (x', 1/) where xf
for + +
T.t, and y/ = y for * V/ = ----
First, note that Z' Eiz Ziyn + (-x,)(-9) = Z. Hence the condition Z > is invariant under the transformation Tü Second, due to independence and the block diagonal structure of the covariance, the overall joint density is a product of univariate Gaussians centered around zero. Due to the symmetry of a univariate Gaussian, the overall density is also invariant under T,, Third, the entry z becomes -I under the transformation T,. Due this symmetry, we conclude that the off- off-diagonal entries are zero.
All the diagonal entries of A0) are equal by symmetry. The diagonal entries A());
B[a,y] Z > 0). Let Z; = z,yi, meaning Z Ei= Z4- Due to the block diagonal structure on (x, V), each Z; is independent and identically distributed. Hence, A Af)) A0) for any i, E [r].
Properties of f()). From the above two steps, we conclude that A = f(0) I, for some scalar function f R + R. Using the trace trick, we see that
S(0) Tr(I,) = Tr pyy
x > 0)
- E|
f()
> 0
Since the covariances of x. scaled identity, each 2,y4 E [r] is identically distributed. This distribution is akin to uv for u (O, az), v NO, ay) with Cor(u, v) = azy. Hence
((0) E WI
Σ u.u
for ui, v i.i.d. according to the described distribution. Lemma g shows the required properties on this conditional expectation, showing the desired inequalities in the statement of this lemma. O
Lemma 10. Let x &d and I E Rdd be jointly Gaussian vectors with mean zero joint covariance matrix Ejult which is positive definite. Consider Mo, M, E d satisfying rank(Mo) 2 and
[M - Moll < Trank(Ma) (Mo). For any A Bddd let YA == x A. For real 0 2 0, define:
AP()) = PPYM, > 0] - PPYMM > 07
(17)
AE (+) = B[rT T I(YM, > 0)] EExzT I(YM, > 1)]
(18)
where the randomness is over the Gaussian (x, J). Then, there exist constants Cr( Efult, Mo) > 0 and (e,0, Efuu; Mo) > 0 that depend on O, the covariance Exjult, and Mo. such that:
AP < Cp(0, Ejutt Mo) || M Molla
(19)
AE () I Cp(0, Ejuu, Mo) |My Molls
(20)
25

---

Proof. We prove the two bounds using differentiability arguments. Define AM := Mr Mo. and define the scalar y, := (Mo + +AM) Σ. Note that we have overloaded notation by reusing Y: shall be clear from the context that Y, for a scalar and YA for matrix A mean different things.
| Mo we conclude that rank(Mo fAM) 2 rank(Mo) 2 2 for all & E [0, 1]. Since (ær, σ) is jointly Gaussian, rank 2 2 ensures that Y, for all t E [0, 1] have a smooth and bounded density everywhere. This because the random variable YA is equivalent to the quadratic form on Gaussian, (1/2)2² H with
Using Lemma 4 with the given condition
A
2 =
(O, Maa)
H
AAT
0
This quadratic form has known characteristic function as below (Mathai and Provost
23 Sec 3.2])
(tt) ddet (I- - 2it yuu H)
One can see that rank(H) = 2- rank (A) and (o()) decays as It] trank((H) as |d] + c0. This shows
that rank 2 4 ensures at least | decay, which ensures boundedness everywhere.
(i) Probability Difference Bound (eq. 19 )
Define the path h(() == F(YY > 0} for [0.
Then by the Mean Value Theorem, it holds that
(P = Ih(1) h(0) = [E)( for some E (0, 1).
Since Y has a finite and bounded density everywhere, h(t) is differentiable and its derivative is
(1(1) d P(Y > 0) E (8(Y - 0) Y = E [ō(Y, 0) AM T
dt
where 5 the Dirac delta function. Using the Cauchy-Schwarr Schwarz inequality, we can write
In' (t) < E 18(%- 8) |a AM T|
S ||M]] E [6(Y; - 0) |
|ل||
|AM]| fr, (0) E [||=|| |
Y. Y==
where fy, (0) is the density of Y2 at 9. Because Y; is denenneeeettee for t [0. 1]. both (0) and the conditional expectation are finite and bounded over t. Thus the linear dependence on || in Eq. 19 follows, since any (0, satisfies the above conditions.
(ii) Expectation Difference Bound (eq. (0 Mean Value Theorem, we have
Define H(I) = B|xT T I[Y, > 0}} Then by the
(E [H()) - (0)] (E)ll for some & E (0.
Differentiating under the expectation gives
(L) = TE [ 5(y 0) x AMG].
For any matrix norm, we have
[()I))) < E B[[ |||||
|a AMØ 5(Y, 0)]
$ |
E ||| - | 8(Y, 0)]
|M fv. (0) ||| || Y. = 0].
Again, all terms other than |MI| are bounded for t e [0, 1]. yielding the desired Eq. 20
Lemma 11. Let 21, .., Fn E Rdd be n i...d. random vectors drawn from a Gaussian distribution NO,, Σ), where E is a d x d positive definite covariance matrix, d > 1, n 2 1. Let S be random subset of indices (1...., n) generated by including each index j [1,...,n]] n. independently with
probability E (0, 1). Let nt. |S| denote the number of selected samples, and define the sumple covariance matrix for na 0 Σm. (1/nz) Exes T.aIT For failure probability 8 (0, 1), assume that up 8log(2 (2/8) holds. Then, with probability at least 1 - ō, both nie 2 npp2 and the sample covariance matrix of the selected data satisfies:
|smm.
x|| S
|2
d + log
np
26

---

Proof.
Define kmin == np v 12pplog (2/8)
Note that Kmin np/2 due to the assumption. Let
ne Kmin and Smm 211 ||51
d + log 5
Fi == {ne < kmiad, F2
Kmin
denote the failure events. A union bound over the two failure probabilities will give the desired result. Below we bound the individual failure probabilities.
so that Amii = [(1 - Ao)np]. Since we assumed npp 8 log (2/6), Ao 0.5. By standard Chernoff bound for binomial distributions,
Bounding P(F:): Define Ao = /2log(2/6)
P(n, < (1 - Ao mpp) & exp( exp(-np43/2) = exp(- (20(( = 5/2. Since Kmin 2 (1 An)mp (due to the ceil operation), it follows that (FF Pn < kmii)) P(nn (1 Ao)mp) 5/2.
Bounding P(F2): Using the law of total probability, we write
+ log
((F2)
Σ
P
Σ
Iaa T E
> 1| V
P( = k)
kimin
k=mintt
:ES.1S|
For any l: 2 Kiminn we have
1/vb S 1/ Amin- Thus, for k kimin:
PP
Σ 1200
> Σ
>|E||2 V
d log 1 kaii
ne = k
I
d log k
P
Σ
x
2
|>ححla
Te = k
And the right hand side is bounded by 6/2 owing to standard matrix concentration results. So. P(F2) & Ek=kman (m. = k) s 8/2.
D A proof of Corollary 1
We present proof of Corollary 11 which follows the proof presented in Nakada al. 24] while fixing some typos. Before diving into the proof, we make some remarks.
First, the result stated in Corollary is tighter than its counterpart Nakada et al. 24 Theorem 3.1] by dimension factor. This is because we use tighter concentration, as detailed in the explanation between Eqs (28) and (29) Second, as remarked in Remark 4.1 Corollary [ not tight in the SNR parameters 7: 7. Third, the result in Nakada al. [24] is for a general covariance on the signal, Σz, and the noise, Σg. whereas our setting is more restricted from Assumptions I and This restriction required for the analysis of filtering in Theorem !
Fourth, the result in [24] is stated with probability 1 - (2/n). whereas we state it with probability 1 --) Due to this, Corollary [ as stated does not have log factor inside the square root,
unlike Nakada et al. 24 Theorem 3.1]. Fifth, there is a small subtle difference in the setting of
24 and ours. We use 1) to denote the fixed probability of clean samples in Assumption]] [ whereas Nakada et al. [24 use 77 to denote the fraction of clean samples in the sampled dataset, which is random quantity. Using n. denote the number of clean samples, we go through the additional step of controlling the error in Me/n 7/. which scales as 1/V5, since this source of error is I-dimensional. Sixth, the result in Nakada et al. [24 Theorem 3.1] is stated as min min(v While is true that the
sin θ metric can be at most /r, the final step in the proof is the application Lemma 2, which requires condition that translates to n 2 (2/1²) max(d, d) (1 + + (1 And this is how we state the result in Corollary which makes the stated upper bound always smaller than vr.
For clarity, write the algorithm:
Input. X E Iaaxd X ig r E E4, 24,.E E (0, oo).
Output. G T G E ddd (with rank r, since G grxd, G E RR* by minimizing Eq. 3
27

---

Step 1: Reduction of loss. We show that
G) = -Tr (GS, GT,,
(21)
where S, denotes the cross covariance matrix of the data, given by (Eq. 5
rewritten)
S 72
(z - x) ( z
E Rdxd
Proof. Expand the LHS as
Go G)= = 2n(n - 1)
1
NW 1
(81) s:)) +
(رHz 8;;))
1=1
(a)
Σ
Σ Sij 8H)
n - n(n-1) 1)
jk
1
ΣΣ
8ij - (n - 1)
Σ 81i
nnn
- 1)
AK
1
ΣΣ
si
1
Σ
8/
(X)
n(n
1)
n
jtti
where eq (a) holds because the overall sum over the similarity matrix is the same whether done over rows or columns.
For the RHS, we first rewrite S, as
n
S2
NIE
n
Σ
3/
n
n(n 1)
Σ
Σ
mtJ
n
nnn 1)
1
1
Σ
I
1
ΣΣ
n
n
n(n 101 1)
1
1
ΣΣ
T
nnn - 1)
jz1
Using the above, we rewrite the RHS as
C.ann 67))
-Tr (GS.G))= -Tr 1
Σ GareT
n(n 11)
1
ΣΣ Tr (Gr )
- Σ Tr Go (.G..T..)
nin 1)
i jp
(Linearity of Trace)
28

---

ΣΣ j7i
Gai Gay)
Σ
Gai GTa)
n(n 1)
(Cyclic nature of Trace)
n(n
ΣΣ
Sij
1
Σ
s
(Definition of 8ty)
Comparing the above to eq (X) concludes the proof.
Step 2: Closed-form solution. We show that (Eq.
(6
rewritten)
arg min L, G.G
(c,
dTā=
SVD, (S..)
P
Hence, even though the optimization problem is non-convex, there is a closed-form solution, and no optimization analysis is needed. In particular, the right singular vectors of G, G are determined independent of the choice of p. This result is from Nakada al. [24 Lemma 2.1].
Proof. Using Step I's result, we can write
(G G) = max Tr GG
P G
min G.
(22)
G.G
The objective can be rewritten
Tr GG. P G
P 2
Sn
2
G
G
Sp
The optimization variables appear only in the second term. Since rank (G G = r, by the Sekart-Young-Minsky Theorem, the solution is given by the best rank approximation of Sn/p. O
Step 3: Relating error to op-norm concentration of S.,. We show the below, where S,, concentrates
to S = UUT
svD, (S..) S|| s 2 |S, - S||
(23)
Proof. By triangle inequality, we have
||VD, (S..) S|| < SVD, (S..) S. + |S,. - -SI|
And for the first term on the right hand side, we use
||sD, (S.) S, = o,+1 (Sn)
<(t) 0r+1 (S) + SA S||
2 ||S S|
In Eq. (f), we used Lemma and Eq. (+t) holds because o (S) 0, since S is rank
Step 4: Concentration of S.. We show that with probability exp (oxp(-S(umm 1-aamax (d.))).
S.. S|| S max(d, d) (1 + - -5-1)
1
(24)
n
77
Before we prove this, remark that the condition of no (for the appropriate no stated in the statement of Corollary [ ensures that the Õ(1/n) term is at Ö(1?) whereas the first term Ō(7). This ensures that we the regime where the 1/vn Vn term dominates.
29

---

Proof. We start with the expansion of Sn
1
7
S
2
n(n
1)
im1
im
J
The main term that dictates the convergence is ( The term S concentrates around zero (since samples o j; i,j [n]] are independent), and the rate of convergence is (l1nn) due averaging over n² terms, which is a higher order term. Let ne be a random variable that denotes the number of clean data points. We expand the sum in ((1) below.
S
Σ x
U2 U2
U2
i=n+11
Ja
U
K1
K2
K3
We control the error each term separately. For terms J2, K133, we need result like Nakada et al.
124 Proposition C.I] the simple case of X 1 X. For term Jr, we need for =
The following two facts are going to be used multiple times. Here X,Y Y denote random quantities, and all others fixed quantities (matrices/vectors).
w.h.p. |X - All S FA, |Y B|| S EB = w.h.p. || + Y - (A + B) S EA EB, (25) w.h.p. |X All < EA
w.h.p. |MXN- - MAN]| < [|M]]]I]]
(26)
For the independent terms (J2, 1:3), we will use the below generic result. For TR 9 x (0, E.,) and R.dy 3 y [00 Σy) and N i.i.d draws from both, we have the below result from the application of Matrix-Bernsteii Bernstein result.
1 N
N
Exll |للل N
w.p. 1 -
xill
S
(t + log (dz + dgy)
(27)
For the dependent term (J1), we will use the below. Let Rd, 9 x ~ N Ex) and N ii.d. draws from this. This is also known in the literature, for e.g., Bunea and Xiao 4 Theorem 2.2].
N N
+ log (d,)
w.p. 1 e
T
Eg
S
E
1V
(28)
N
Note that the above two concentration results are tighter than Nakada et al. 22 Proposition C.1] by factor of dimension, since the proposition has trace terms too, whereas only operator norms appear in the above two equations. This manifests in Corollary[]] stated being tighter than Nakada et al. [24] Theorem 3. by dimension factor inside the square root (since we avoided log n but did not incur an additional dimension due to the failure probability of exp(-d)). Finally, since n. Bin(n, n)) the ratio Be/n concentrates to 17. with the error described by Hoeffding's inequality as
IP The
N 2exp (-2ne²)
(29)
Using these results, bound the individual terms of deviation. We first bound the independent terms using Eq. (7) with max(d, d). The choice of N is given with each setting. With probability 1 - exp( (2maxffd (d, d))), the following hold:
K2
Ex |g max(d, d}
max (oxx(d, d 7
(N := n)
n
n1
30

---

K2
|2=11
|| max (d,
max (d, 7- | max(d,
24
(N == n)
72
n
K3
Egll
max (dr df 1-1-11
(N == m)
n
J2
|2 max [d,
nhe max (d, d}
(N = ne)
n
We now bound the dependent term using Eq. (28). We need some additional machinery to deal with the random denominator, which we capture in Lemma II The requirement of mp 2 log(1/6) in the lemma translates to n 2 max(d,dl/n, since we have = 1y and ò := exp( 1i-xmaxfd, df). As we will see later, step 5 of the proof requires n 2 mux(d,d1/n". hence this requirement is already satisfied.
With probability 1 - exp( (maxx d))), it holds:
J1 UūT FCe
max d. d} T&r
U
(30)
J1 ne Uū
1he
max (d, d}
n
J1 1j UÜT
max (d, d}
Ne
17
72
n
For the concentration of Re/n, we use Eq. 29 to get that with probability - exp(exx(pmaapeeeeeeee Q(maxx (immaxfd, d)))):
max a)
Tee S
?
(31)
n
We now add all the error bounds. For the combined error from terms J1 and J2, we note that
/I - "e/n < 1, and (*o/nvr) S with high probability (since "e/n concentrates around 17). The failure probability of this can be absorbed into the overall failure probability. Eq. (24) follows. O
Step 5: Relating singular vector recovery error to operator norm concentration. We will apply
Lemma 2 (a Davis- type result) relate the sin @ metric to the operator norm. Combining
Eqs. 24 (3)
and (6). we get that with probability 1 1-exp(- exp((S((max (d, d))):
G 7 -Uū P
maxfd, d) (1 + (1+ +5-1
1
(32)
n
The instantiation for Lemma is as follows: A = _Uū Á G.G. Note that both A, Å are rank-r, and o, (A) n/p. We get
| T ||
sin θ (Isv(GTG).
(33)
| 2 D0 11
Now we will use three things. First, for the numerator, we use |M for any matrix M. Second, for the denominator, we will need the additional condition of 2 (1/1") max(d, (1 + + + -11) to ensure the second term is at most half of the first term. This also ensures that the ((1%)) does not dominate the 1/vm term. Third, triangle inequality with the fact that sin [Lsv(GTG), rs)
rran(M ||MM 1|2
= O gives the final result. To see this fact, write
G Va EoUTUUDEa)
VoPSQ
(Using SVD of the middle component)
31

---

Using the uniqueness SVD, we get that 1sv G V&P and rav (GT V.Q. Since P. Q are just orthogonal transforms, the subspace spanned by Va and Va are the same, implying sin (VV.. Va P)
(and analogously for Va and Q)
Combining Eqs. (32 and 333 gives the desired result. Since the upper bound is valid for recovery of both U and U, Corollary stated follows.
E A proof of Proposition
Consider the following construction for the hard problem instance (lower bound): (i) the latent dimension r = 1, and (ix) the noise = 0 (i.e. 7 = oc), but & * 0 (i.e. 7y is finite). This means the following proof recovers the d part from the max d term in Proposition
| A similar
argument can be made for the case when 0, ξ * leading to the max over both errors.
Owing to r = this becomes a I-dimensional vector recovery problem. Let u, E IR denote the vectors to recover. Upon seeing S., there is no error in estimating u since & = 0. but there is error in estimating u. To calculate this error, define u, be the top-left singular vector of Sn, Note that S, has only one non-zero singular value, since it fully lies on ü in the right singular vector space (i.c. S for any v 1 ü). Hence
S ||a u, u
(34)
Step Writing down S...
T
1
n
1
S
Z2
n
n(n - 1)
1
1
12
3.5
T
11
n (n
1)
j=1
J
(22)
We expand !! below, using n. denote the random variable denoting the clean samples. Note that En, = m,. Similarly one can expand s!²), however, the error of (22 will behave as (1/n)) due to averaging over n² samples, which is higher order term in the overall rate. That is, the behavior (in the large n regime) will be largely dictated by ((
1
the
(a.u + (2Gū) +
Σ (a.u ( im
π
As for the expectations, they are given by:
1
E
S
E [nd] uu 17 uū
71
72
E
(2)
(since all random quantities are zero-mean and independent).
Step 1. Decompose sin 9 metric. Our goal is a high probability lower bound on |sin A(1,, u)),
where u, is the random quantity. Note that
sin (uu, u) = (Ia
u
(35)
To see this, note that I = / (u ) Squaring both sides and expanding suffices.
Step 2. Compute the metric for this case. Using Eq. 33 in Eq.
(35)
we can write
(I, uu
S
Isin (u,, u)l
(36)
32

---

Step 3. Computing the high probability bound. We will give high probability lower bound on the numerator and denominator Eq. 36) separately.
Step 3.1. For the numerator: We first expand 5 as
- n
2 u + 2,Ei) +
Σ
(2
+ Z,E,)
i=ne+1
(Ia nu ) 0
(I un )
Σ
i=1
i=+++1
n2
d (L uu ))
71
Similarly, for ! we have
(I. uu I ) (La uu ))
n(n 1)
i= j=1
n
d (La uu
n(n
1)
i=1 ==1
37
Combining the two, we get
1
(La un!) I (I. un
[2 2) (E: E)
Wn
Now we want to compute high confidence lower bound on the norm of the above. We first relate [T un?) ) w. to w,.l. This is because w, is spherically symmetric, and (Ia - un is rank- (d - 1) matrix with all non-zere eigenvalues equal to one. We get
(I uu w.ll| ||w,|] / (u w
Now due to w,, being spherically symmetric, ||w,]| |l (the magnitude) and wn (the direction) are independent random quantities. Further, W,, is uniformly distributed on 8d-1
For |/w,.ll. will use sharp Gaussian concentration. The intuition is that [/,,] cannot be too smaller than yay 1/n, for large d. Concretely, holds that
1
(z. 2) (5s - 2 | VT
1 v2 (va (Va-V211
w.p. 1 8,
(37)
1=1
An appropriate choice of 8 = (ap(-d44). which results in
w.p. 1 - (-d/44)))) [[w,]] 2 dr-i
(38)
For the second term (with the direction w... this will be least ?(11 with high probability, since u w, will be large only with very small probability when then dimension ds big enough. Concretely, it holds that
[
w.p. 1 expp (-d/4), V1- (u w.n)
(39)
Overall, for the numerator, we conclude that
dy
w.p. 1 cexp (-4/4) Numerator
(40)
11
33

---

Step 3.2. For the denominator: We need high confidence upper bound on ||S, We can use Matrix-Bemstein type analysis. Note that E[S,] nuuü And the deviation is dominated by
s ES,
+
Σ
Y2
sE|n
(E(m(1-m))
Again, the dominating term is the first one, This means that we only have to show high confidence upper bound on || (11/n) , =iEill, and hence the problem has reduced to vector concentration instead of matrix concentration. Analogous to Eq. 37.. one can show
vva+
1
w.p. 1 - 6,
2
S
In
(41)
n
Overall, using the triangle inequality, we have
dy
w.p. 1 - exxp(pp(//), ||S < |ESS
+21
(42)
Step 4. Combined result: From 3.1 and 3.2, for 2 4d /n2 (so the high-conf UB for || is 2n).
d
w.p. 1 1 0 (exp(-4/1)), ssn (u,, u) 2
(43)
n
F
Characterizing the score distribution of the oracle
The Bernoulli variable e E (0. 1) captures the status of clean/corrupted nature of a sample. We first characterize the score distribution in both cases separately, and then create the relevant mixture distribution using the proportions 1 - for clean, corrupted samples respectively.
Before the calculations, state some Lemmas that will be used. Lemma 12. Let X distributed as N (1, Q.). For a fixed matrix A, il holds:
E[ T AX] Tr (Aft).
1 (A+AT))(A+A7))))
VIX AX|
Lemma 13. Let X be distributed (0, and X be distributed as (O, Q).. Let X, X be independent of each other. For a fixed matrix A, holds:
E[X AX] 0
V[X T AX Tr (NAñAT)
Consider block matrix X given as below
A B
C C
Lemma 14. For block matrix X given above, it holds that
Tr(X) Tr(A) + Tr(D)- Lemma 15. For block matrix X given above, with A, D square matrices, it holds that
A + BC AB + BD
x
CA DC
CB
Case 0: Corrupted samples (c = 0 case). Let Zo (8(,,5;UÚT) c= 0), with distribution Dg- This (scalar) random variable is equivalent to X TUU X, where X, X are independent and follow
X N (0, UUT + I.). X AV (o. ÜÜT + 7 - This is in-line with Remark A.1 We invoke Lemma 13 to get the first two moments.
34

---

1. Mean: 0.
2. Variance: r (1 (1+ 7-1).
Variance TF (UUT (UUT+ U (öū +;'1)) ÜUT)
Tr U (UU + U ūJ (oū + +5 U)
=Tr (I. (L.
3. Tails: Since X, X are independent, the tails are described by the quadratic form on two independent Gaussians. This random variable is (i) symmetric, and (wi uni-modal, and tails decay exponentially.
Case 1: Clean samples (c = case). Let Z1 This random variable equivalent to X BX, where X = [z, कं follows X ~ N (0, 21) (refer
(5(r, 1}, with distribution D
to Remark and B is block matrix given below. We invoke Lemma 12 to get the first two moments.
Oaxd
UÜT
B =
0 Txx
0 axd (a+d)x(d+d)
Mean: r.
Mean Tr(BE,)
= -Th( UUT
0
-Tr(UUT) Tr(I,) =r.
(Using Lemma 14
2. Variance: r + + (11
Variance = Tr
B + B T
E B + B E
UUT
UÜT
Tr
ÚUT UU
ÚÜ
T2
UUT + T.T
))
Ir
(Using Lemmal
15
T.
= Tr(I,) TT(T,T))
(Using Lemma
3. Tails: Since X, X are dependent, the tails are described by the quadratic form on two dependent Gaussians. The tails decay exponentially, and are described by the Hanson- Wright inequality. similar calculation as the variance provides the exact parameters, and the inequality becomes:
2
P P - EZI > 1) exp
exp
- -emin
r + (1 - (1 + サー))))²
V2t
(44)
(1
35

---

G A proof of Theorem !
We first define one additional piece of notation. For U, let U1 E Rdx(d-r) denote the completion of the orthonormal basis. That is, the matrix Usul
In this section, we present a proof of Theorem |
IU U_] E Rdxd is such that U fuull = La = Utun Uan- Similarly define U1 E (āx()-r)
Recall that we have n samples of the form {(z,, H= i.dd from the mixture distribution (with
7. 11-1--- 7) ratios for clean, corrupted respectively). Let nor samples be used to train the teacher, and samples be used to train the student. Let pr. P be the respective regularization parameters, and let (Gr, Gr), (G, G) denote the respective embedding matrices the solution of Eq. (3). Consider a general threshold E RR that is used to filter the dataset based on the teacher scores. Note that we have ensured that 0 is independent of the N samples to be filtered, since it depends only on the nr samples used for teacher training. For the teacher, from Corollary| T we know that with probability 1- - exp(-52 (max((, d))):
let N = Roy
S (v Pr
G
7 UūT Pr
1
mmxx (d, d) (1 (1+ +5-1)
(45)
nT
1&
Here (Gr, GT) are random quantities that depend on the ny samples used. For the rest of the analysis, we will assume them to be fixed (since they don't depend on the randomness of the remaining N samples). Finally, we will give a high probability guarantee that will use the confidence bound in Eq. (45) as one of the terms in the combined error bound, with an appropriate choice of nr and pr- We now study the student with data filtering. It is useful to define
: = G
UÜT.
(46)
These are the matrices used for scoring the samples by the teacher and its oracle version, respectively, Note that rank(Mo) = since both U, U are rank-r matrices. From the teacher guarantee in Eq. (45) it holds that Mr- + Mo as nr + Recall that the scoring function is S(x, T;; M) = x M क. and a sample (x, 2) is selected/retained iff (zz, x; My) > 8.
We define certain quantities that will be central to the analysis. Akin to Eq. (5) we define the
empirical cross-covariance matrix of the data after selection in Eq. (47). Let (()) be the number
of samples selected, which is random variable with TE. (E(Tset.(()) [0) N (+)).. Let (() S [N] denote the indices of the points selected. That is, E (.) - S(x,, ",; My) > B. Similarly, define (0) and (0). Construct the empirical cross-covariance matrix for the filtered dataset:
Σ (N) (0)), (E
(a; - x(0) (T. (a:)(())
=0))
(47)
(x)
To analyze its asymptotic limit, we define S(O) as the limit of the cross-covariance, for both the teacher and the oracle. Similarly, let P(0) denote the probability mass of data that is retained (also in the limit of n + 20), for both the teacher and the oracle. These are described in Eqs (48). (49).
ST = E [
S(x, T; Mr) > 0] E Rddx
Pr(0) P (S(a, 7. MT) 0}
(48)
(6) = E [ ((x,F; > 0] E Rdxd
Po(O) = P (S Mo) > 0 (49)
Note that S (o). are the limits of ( (N) as N + xo. The threshold 0 - 00 recovers the no filtering case, i.e. both (0). Sw.)( approach SN. We will now follow proof steps similar to Section [ Steps and hold for general eross covariance matrix, and can be used directly. Steps 3 and 4 are concerned with the limit of S, (0) as n + xo, and how it concentrates around the limit. These steps will change significantly. Finally, we will be able to reuse Lemma 2 for step 5. We detail each of these proof steps below.
Step 1. Following the exact same proof steps as in Section D. the unregularized contrastive loss objective on the (0)) samples is equivalent to
Lo G) = -Tr (orGGS (G)).)(0)TT)
(50)
36

---

Step 2. Again, following the exact same proof steps as in Section D the solution to the p-regularized
minimization problem is given by
arg min &p G, G = G.G
! - sVD, - (Sx:(1))
-
(51)
Step 3. This step changes from Section D We use the following:
|sv,, (S (S), So S or+1 (So(0) + +2 -
(52)
By triangle inequality, we have
|SV,, (Sw,r(0)) So(!) - SVD, (Sw.r(0)) - Sw.T (1x.((0)) (|S.(0) So(O)l
And for the first term on the right hand side, we use
||vD, (Sn,r(0)) (f)l 0r+1 (Sw,r(f))
(t) xrt1 (So(O) + ([),,(00)- So(O)],,
where we used Lemma in Eq (t).
Step 3'. Analysis of (0) The main difference in Eq. 23 and Eq. (52) is the term o (So (0)). This additional step the proof analyzes the properties (o) In particular, we will show that (0) is rank-r, and hence 7,+1 (0)) = 0. Additionally, we establish upper and lower bounds on the singular values (0) that will be used later in the proof. From Eq. (49). we simplify to write
0pr
(0)
E
F.
UU
1
where (x, 3) is drawn from the mixture model: 70, En) (1 1) (O, Eo). To simplify
notation, define = (6pc//n. From the conditioning event, it seems that U x and U T is a good "basis' for a decomposition. Pre-multiply and post-multiply to recover this basis for the x²" term inside the expectation
So( = fill
U
tull
E
ITC
x
Ütat U
rx(d-r)
Uni E
( 2) (U 3)
U (ŪTT) U
(U (TTT)((TT))
T
(d-r)xr
(d (d-r)x
Call the top left entry in this decomposition the 'dominant', and the other three as 'non- dominant'. We will show the non non-dominant entries will be zero. The following reparametrization makes things cleaner.
UT=z-UTS U U UlS; Úz= UTC Ú ULC
Let's further simplify the expressions with another transformation. The subscripts S, N denote the signal (containing some noise) and noise part.
Eg
t
EN
Is +
IN El ER--r
ERl
CRd-r
ER
Due to the diagonal structure of Eg. Egi we infer the distributions as
5 S~ N 1.). e1 ~ (0.00,, (a. E~ (0. 1.. El ~ (1.
37

---

And crucially, due to the diagonal structure of Σg. Zgz we infer that (,,EL,,,EL) are all mutually independent, and independent of 2, ž. This entails that the transformed vector is Gaussian with mean zero and covariance given as below.
S
1/- I
0 (I,) (1 I,
0
N Ø N
(a-))
0
0
0,
(53)
()
0 ((-))
(1/)
The above is for the corrupted case (w.p. 1 17. In the clean case (w.p. m. the blue entries change to
I, due the relation of 2 = Σ. Our E[]] notation includes the expectation over this randomness along with the randomness of z, I. Denote by Po and 22 the covariances the signal part, i.e. (zs, I 5) in these two cases:
ΩD == (1 (1+1/a1
(1+ (1+1/)),, 1 Ω1 = (1+ ((uttt I.
1
I
(54)
(1 (1+1/)),
Overall, under the transformation, the expectation simplifies to
ESIN T xNãN)
So(O) Unl E
Fg Fg
>0
U
full
(55)
Due to EN, EN being independent of all other entries via Eq. 53 and since the conditioning event in Eq. (55) only involves Ts, Is, we conclude that the non-dominant entries in the expectation will be zero. Hence we are left with the simplified rank-r form for the d x d matrix:
agEs > ø] U =U (1 (--pss,5s) 2 us >
So( = UE EgTg
+ (1 - Blzg
IςIS >
8) Ū
We will now use Lemma to simplify both the terms above. Note that Ω1, Ro satisfy the lemma's requirement of the block diagonal covariance.
So = U ( + (1-1) fo(0) UT (n)f(00) (1 1)) fo(0) UūT,
(56)
where the following conditions hold on fi, fo (converting back from Ø to 0):
(801)//r + (1++ (1+++ ")11// 2 (0) > max 11, (8p:)/nr)
max (0p1)/ar) / (1- 21+ 1))/r (o max (8p1)/ar)
Using the above equations, and the special case of in Lemma we conclude:
2
(1 2 1,
fo(0)
Z
(1 +
(57)
nr
r
r
fi
2 1, fo
(58)
2pT
2pT
2
We will use these inequalities in step 5. In particular, since ||So(0)] = f7 fo(O),
2 -1 (1+
for 0 E [0, m//20r]
[So())]]
(59)
nr
Step 4. Concentration of (f) to (t): We break this into subparts as below.
Step 4.1. Concentration of xx, (0) to ST(0): Using the below substeps, show that with probability
- d))):
max d) p,
(0) ST(0 V
+ NNP(())
(60)
N (+)
38

---

Step 4.1.1. Replacing the random denominator: Recall (f)
Σ I,, Mr) > 8 is
the (random) number of selected samples. Since the teacher's score matrix Mf and threshold 0 are fixed independently of these N samples, the indicators are i.i.d. Bernoulli random variables with mean (r()). By standard Chernoff bound for sums of independent Bernoulli variables, T (0) concentrates sharply around its expectation: for any 0 < 5 < 1,
P F( -NN((N)) -NP:(())2 28PP(0) s 2ex (((()N)
In partieular, choosing 8 (Vmox(cti// m1O0) we conclude that
max f d. d} N P+(0)
w.p. 1 - exeepp-p------pp (0pp-9((mx((4) (d))) (())
1
NP
(61)
On this high- high-probability event, the following holds (recall the definition of QN,r(0) from Eq. (47
(() N (r)
T (6) -1 QN:T(O) (0) - Qv.r(0)| = (meerr(0) (0) 1) (N Pr(0) 1) Qx,r(0))
2 (1) [see. N PT(0)] |QN.((0)
(N (O) - 1)2
2 (111) max Pi(0) N PT(0)
PN()) 1)²
max d)
QN: N P((0)
NP)
max dd, d}
5011
N+
In (t), we used Eq. (61) which implies that 0.5 N (O) S (0) S 1.5N Pr(0) when N Z max(d, d} (which is indeed true, since in Step we set N n/2 & n Z max,d, d) is assumed in Theorem [ and in Step 4.3 we ensure that (r) 2 1). In (++), we again used Eq. (61) directly. In (f++), we used that (Q),(()]l grows on the order of P+ (since it is the sum of ( i.i.d. outer products each with bounded expectation). Thus, overall, replacing the random (f) by
(r)) in the normalization incurs error of order v max m (d.3)//////((( with high probability. In the subsequent analysis, we may therefore work with the fixed denominator N (()) for convenience.
Step 4.1.2. The centered vs un-centered version: We have that
1
Σ
(s. (m,))(0))
(5. -00)
N P+(0) -
(EL,,)(0)
1
Σ
Σ
Σ
N (+( (E
N (N -
1 (0)
j$i
The second term on the right hand side concentrates to ayy x M 7 0,y MT D > 0) where (x. 7 and (y. 7) are i.i.d. from the joint mixture distribution. This expectation is zero, which we formally characterize in Lemmas 6 and The rate of concentration is Ō (NAT0)) ). due to averaging
over (N Pr)) 2 terms, and is hence a higher order term.
Step 4.1.3. Analysis of the fixed-denominator un-centered version: The selected samples satisfy the property of being i.i.d from the conditional law of the selection rule. In particular, for each i (a))(() the matrix X; = N. has expectation E E ST( and these matrices [X, i E (0)) are independent. Using a Merri--errnttenn concentration result (Eqs. 27 and 288 it follows that with
39

---

probability 1 - (xp(-S((mxx(dd d})):
max d) poly(>-1,7--))
Σ
2 ST(O)
N PT(0) (()
N P+(0)
Step 4.2. Error between teacher and oracle: We show that
[S) - So( scales proportionally
|ST
to M Moll, and the latter is precisely bounded by Eq.
45 To show this, we first simplify the
conditional expectation in (0) (0))), define Eo Er ()) as:
(o E
2 [(r Mo 0)] - (o (o(0)/Po(0)
(62)
(0) == E
στ 1(x M > 8)] = ST = E, (100//(00)
(63)
where II(.) denotes the indicator. Let (0 ( and A = Pr()) Pr()))PP((0) Also
define AT((; xz, x) = I(x Mr > 8) I(x MoT > 0). Then, we write
(0) (o)
ST( So Pr(0) Po(O)
(O) + AE(()) Po( (0) (Po(O) AP(O))
AE
AP(0)
Eo(0)
Pr(0) Po(
PT(0)
Pr(0)
Po
So(O)
1 (IAE()))2 + | ((s((())))))
- [|ST(0) So(0)l1
Pr(0)
We will now bound |AE(()] and | P(0) in terms of || - M Recall that (ar, follow the mixture distribution (Remark A.I. Decomposing the expectations and probabilities into respective mixtures, we get
AE 7) E ((,3))
x AI(O: 2. x) + (1 11) ((,,)) FT AI(O;, 2, x()) AO v (() AI(0;,,,)) + (1 11) (c [A x]
From the above, since both 77 1 77 are smaller than 1, we get that
|| < [ +
(0)(1 PQ) & +
where the subscripts 1, 0 denote the fully clean, corrupted cases respectively (i.e. 1, 71 0 respec- tively). Lemma captures the general form of this, and we invoke this lemma on both the clean data (with covariance Σ,) and the noisy data (with covariance Eo). Note that rank(Mo) 2 2 is satisfied since rank = r and we assumed r 2 in the statement of Theorem 1 Further, the condition
of |M Mol| < or (Mo) is satisfied due to n 2 (1/1P) max max(d, d) (1+7-1) (1 + 7-)) since Mo has r non-zero singular values all equal to 1/pr and Eq. (45) with the condition on n implics
that ||, - Moll S 7/er (note that implicitly the condition also ensures that the contribution of the Ö(1/n) term is bounded). The appropriate constants inside the 2 notation will ensure the required
condition. Overall, we get
1 + [So(0)]12 - P+(0)
[S) - -o((00))))0)la
| -
(64)
Step 4.3. Analysis of P+( and P0): In this part, we show that both (r( and (o can be lower bounded by an absolute constant (say, 1/10) for the relevant regime of filtering threshold 0.
Argument for Pr)) Using Step 4.2, we have (0) 2 Po(0) P(O), and the deviation is small since [AP())] S M Mo |. Using Eq. (45), we note that a large pr can make ||M Moll arbitrarily small. Indeed in Step we will set PT to large value. Since the deviation is small, we can use, for instance, (0) 2 (o(O). Hence, arguing Po(0) is large suffices, which we do below.
Argument for Po()): Next, we show that (o) is 'large enough' for the choices of 0 E {0, r7/2pr) and we will use these fixed points in Step 5. Recall from Section 6.2 due to the mixture distribution, the below holds. Here we have accounted for the scaling factor in the definition of Mo.
0pr
0PT
Po(0) = Pi
+ (1 - 17) Po
(65)
40

---

In Step 5, we will consider the fixed points E r0/ep/) and so we need lower bounds on Po and P1 We state them below:
Po( 2 0.5, (i c. Po(r/2) 0 Pt(r/2)
(66)
(67)
where 0 is an absolute constant. For Po(.), we have lower bounds 0.5 (due to symmetry) and 0 (trivially). For (-), we simply invoke the observation that both 7/2) are below the mean of the distribution (refer to Figure 2a), and so an appropriate constant e exists satisfying the above. Overall,
we conclude that (o( = 11) and Po(rn/20r) = S2(1).
Step 5. Final guarantee via application of Lemma 2
Using Eqs. 660 and 64 in Eq. 52 with
Eq. 51 and combining the guarantee from Eq. 45 with probability 1 exp( 52 (mmxx (d, d))
G
1 P
So(0)
-
1
max (d. d) poly()-1,55))
+0 Nr
N Pr(0)
1
1
[So(()]12]
(1
max {d, d} (1 (1+
+ p Pr
Pr(0)
We set ft n/2, and N chosen arbitrarily large to reduce the second term in the error above. This because any Pr > 0 will allow the teacher parameters GT. GT to recover the subspace spanned by U, Ú respectively, but large choice of pr will make the operator norm small. This does not cause the filtering change, since the threshold 0 changes multiplicatively with pr (effectively scaling the picture in Figure 2)
Wr = n/22 (as in Algorithm For pr, we note that it can be
The condition of n Z o/2 max(d, d (1 + - is inherited from Corollary 1 (to be able to use eq (45 The additional condition on n. from the application of Lemma 2 to the above equation results in a larger factor than 1/1², hence already satisfied.
(similar Eq.
33
Now we apply Lemma@oon on the above equation, and follow the argument similar to step 5 in Section D An additional factor of /r appears due to the norm being the chordal distance (frobenius norm). Using Eq. (56) and Eq. (65) we get that with probability exp(=S(maxx (d, d))), the error
ERR G. is upper bounded (up to constants) by:
r max (d poly()-1,7-1)
(1- vn PI Pi (om//s) + n) Po (9m1/n)
from [[]][
from / Pr(()
Finally, we plug in the values / E {0, m/2pp recover the terms To, To.s as stated in Theorem Using Eq. (57) and (66), the scaling term of the error above becomes
Vnc+ (1 7) (1/2) Sr for any v (0, 1]
In + (1 (3/=))
Using Eq.
and 67 the scaling term of the error above becomes
in + (1 1) (+/2) T
The above describes both regimes of behavior, and why an extra factor appears in the term To. compared to the term To.5, in Theorem
[
This concludes the argument.
H Discussion on robustness of the choice of filtering threshold
We note that the error achieved by teacher-based filtering can be fairly robust to the choice of the filtering threshold. Our synthetic experiment in Figure 3a was conducted with fixed, untuned threshold of 0 = O. Further, we conduct an experiment measuring the sensitivity of the final error with respect to the choice of 0, In the setting of Figure 3a with 10000 samples, fix 1 0.3
41

---

(in-line with the empirically observed clean fraction in CLIP data [T]] and (implicitly) vary the filtering threshold 0 of the teacher-based filtering (by explicitly varying the fraction of data retained in the filtering step). The below table shows that the error of teacher-based filtering is relatively flat for values of 9 in the vicinity of the optimal threshold 0* analogous experiment on real data [11 Figure 2] makes a similar observation.
Fraction of data retained
Mean error (#:1 σ) (x10-*)
1%
28.76 + 4.00
10%
11.79 + 1.20
20%
9.85 + 1.39
30% %
9.08 1.15
40%
8.97 1.09
50%
8.71 1.05
100%
16.51 + 2.03
Table 1: Mean emor fraction of data retained.
I Discussion on the potential of robust statistics for the analysis of filtering
An initial instinct based on Figure 2 is to use ideas from robust statistics. As discussed in Remark 6.2 can expect Do and Dj to be well-separated, which means there will exist some 0 RR (a reasonable guess is r/2) such that the selected data is mostly clean. After filtering, the picture resembles corruption
the clean distribution for reasonable approach overall, but has two shortcomings. First, this approach will not achieve zero error co. We shooting for f(n) 1/v5 which is better than 1/v + g()), since the latter is non-zero even when n - 0o. This approach will end up getting the latter. This is because the canonical rate in robust statistics is /a/ma + a. Under filtering, Thel and a are functions of 0. One can determine the optimal this will require some conditions on n, (possibly 17 bigger than a threshold, and n smaller than threshold). Since our case has stochastic corruption which is weaker than adversarial corruption, we can expect to prove something for all n and all Second, this approach performs a "reductive" operation of treating data as only clean v/s corrupted, and assuming the corrupted part provides no signal. This is closely linked argument to the first one above. The crucial observation is that the right tail of the corrupted data (i.e. Do in Figure 2 actually provides 'close clean' samples. This is because these just happened to be samples such that the 2, ã - albeit independently sampled in high-dimensional space happened to have high inner product (small angle). Our adopted approach, based on the conditional properties of the Gaussian distribution, formalizes this intuition that the right tail of Do also provides signal.
the robust statisties setting:
small a. This is
balance the tradeoff, but get final rate of the form f(n) 1/Vn,
42


Reviews:
[{"review_id": "lUYlSU6iH4", "reviewer": "Reviewer_cV4q", "summary": "The paper investigates the benefits of using teacher-based data filtering in multimodal contrastive learning.  It provides a theoretical analysis of how data filtering can improve the performance of contrastive learning models when dealing with noisy, web-scale datasets.  The authors characterize the performance of filtered contrastive learning under a standard bimodal data generation model and show that teacher-based filtering can significantly reduce the error dependence on the fraction of clean data.  Specifically, they demonstrate that the error rate can improve from 1/η to 1/√η in the large η regime and become independent of η in the small η regime, where η represents the fraction of correctly matched modality pairs.  The paper also includes synthetic experiments that validate the theoretical findings and highlight the effectiveness of teacher-based filtering in enhancing model robustness and accuracy.  The contributions provide a deeper understanding of the role of data quality in multimodal representation learning and offer insights into practical data curation strategies.", "questions": "see weaknesses.", "limitations": "see weaknesses.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength：\n1. This paper provides a theoretical explanation of the benefits of data filtering in multimodal contrastive learning. By analyzing the error dependence of contrastive learning before and after filtering, it proves the effectiveness of teacher-model-guided data filtering in improving data quality.\n\n2. This paper shows that when the data quality is poor, the teacher-guided data filtering can achieve an error rate independent of data quality, which breaks the dependence on data quality in traditional contras - tive learning and provides a new perspective for dealing with large-scale noisy data.\n\nThe theoretical results are verified by synthetic experiments. The experimental results are consistent with the theoretical analysis, which further confirms the performance improvement of data filtering guided by teacher model in different data quality scenarios, and provides guidance for data filtering strategies in practical applications.\n\nWeakness：\n1.For some emerging techniques related to data filtering, such as diffusion model-based data augmentation methods, the discussion may not be in-depth enough. These methods may have potential advantages when dealing with noisy data, but the paper does not compare the differences and connections between these methods and teacher model-guided data filtering in multimodal contrastive learning in detail.\n\n2.The paper assumes a linear contrastive learning framework and a Gaussian noise model, which may be limited in practical applications. For example, the noise in real data may have a more complex distribution, and the relationship between multimodal data may not be completely linear.\n\n3.The teacher-model-guided data filtering methods mentioned in the paper rely on a pre-trained teacher model, which may require additional computational resources and data to train and may not be practical enough for resource-limited scenarios. And how much impact does different pre-trained teacher models have on the results? Moreover, the paper does not discuss in detail how to select the optimal filtering threshold, which may be a critical issue in practical applications.\n\n4.To better demonstrate the effectiveness of the approach, one may consider conducting experiments on real-world datasets to evaluate the performance in more complex and diverse data environments.\n\n5. In addition, only the influence of data quality on model performance is considered in the experiment, and the influence of other factors (such as data volume, model architecture, etc.) on the results is not explored. The experiment can be further extended to analyze the interaction between these factors and data quality.", "was_revised": true, "final_justification": "The author has addressed some of my concerns and I will maintain the score.", "rebuttal": "We thank the reviewer for their detailed and constructive feedback, and we appreciate the positive comments about the theoretical contributions of the paper. In the following, we address the concerns raised.\n\n### (1) Did not compare with synthetic data augmentation methods.\n\nThe **empirical** study of data curation for multimodal learning has progressed rapidly, from (i) filtering data using a teacher model (e.g., [2, 3]), to (ii) augmenting with synthetic data (e.g., [13]); and finally to (iii) the combination of the above [5]. Meanwhile, **theoretical** understanding of the above progression has lagged significantly behind. Our contribution is to build a foundational understanding of the first phase, i.e., teacher-based filtering.\n\nHowever, we believe some of the models we study can be extended to study the second and third phases. For instance, synthetically generated 'clean' pairs could be modeled as new samples $(y,\\widetilde{y})$ being augmented to the original dataset comprising of $(x, \\widetilde{x})$, with $y$ and $x$ following different distributions through distinct priors on the latent $z$ and/or different properties on the noise $\\xi$. By controlling the distribution of $(y,\\widetilde{y})$, one could attempt to explain some empirically observed phenomena, such as adding synthetic data helps only up to some point, and either plateaus or starts to hurt performance. This is likely a fruitful direction for future research, but a rigorous investigation of these more complex scenarios is beyond the scope of this paper. \n\n### (2) Real data may not satisfy the assumptions about linearity and Gaussian noise.\n\nThe goal of our work is to provide theoretical justification for the common empirical observation that data filtering using a teacher CLIP model improves performance. The setup with Linearity and Gaussian noise provides a **tractable setting** to study this phenomenon, and is motivated by **past works** that make the same assumptions [6, 7]. Beyond CLIP filtering, **other phenomena in deep learning** have also been successfully characterized in the linear setup, e.g., benign overfitting [8] (also known as double descent), scaling laws [11], and implicit bias [14, 15]. These topics are foundations of what we call the Theory of Deep Learning, and are textbook materials in courses taught at top institutions. Overall, the linear assumption, though not directly applicable in some real cases, provides a useful abstraction that often **preserves the primary problem characteristics** and helps to build a deeper understanding through a theoretical lens. We believe our work (and the assumptions we have), although simple, is within the typical assumptions made in theoretical anlayses of deep learning, which has proven to be productive and insightful (e.g., [8, 11, 14, 15]). \n\n### (3a) Reliance on a pre-trained teacher model which requires additional data and compute.\n\nOur analysis **does not assume the need for an external pre-trained teacher model**. As mentioned in Lines 60-61 and detailed in Algorithm 1, our framework involves training the teacher also using the given (noisy) dataset. That is, the \"Train-Filter-Train\" approach uses the same initial dataset, making it a **self-contained approach** that reflects real-world usage. \n\nOne subtle difference is regarding sample splitting. For theoretical convenience (as mentioned in Lines 204-206), we split the initial dataset into two halves of $n/2$ to leverage independence of random variables. In practice, such data spliting is not necessary and it works just fine to use the entire dataset to train the teacher model, and filter the same dataset to train the student model.\n\nOn the other hand, as you correctly pointed out, the approach does require additional data and compute (in our case, it is 2x since teacher and student require equal resources since they are trained on $n/2$ samples each). This need for additional data/compute aligns with practical usage (e.g., [1, 2, 3]).\n\n### (3b) How to select optimal theta practically.\n\nThis is a great question, thank you for raising this. We would like to expand on the choice of the filtering threshold $\\theta$ by explaining two points:\n- We note that the error achieved by teacher-based filtering is fairly **robust to the choice of $\\theta$**. Our synthetic experiment in Figure 3(a) was conducted with a fixed, untuned threshold of $\\theta=0$. Further, we conducted an experiment measuring the sensitivity of final error with respect to the choice of $\\theta$. The experiment details and results are below (###).\n- In practice, this scalar hyperparameter can be **tuned like other commonly used hyperparameters in machine learning**. For example, convex optimization theory states its theorems for the optimal learning rate $\\alpha^{\\star}$ and in practice the learning rate $\\alpha$ needs to be tuned. Similarly, we state our theorem with the optimal threshold $\\theta^{\\star}$ and in practice the threshold $\\theta$ needs to be tuned. In practice, one should tune the size of retained dataset, instead of the parameter $\\theta$. A practical rule of thumb is to filter out between 70%~80% of training data, in the case of internet scale datasets [1].\n\n***### Experiment for error robustness to choice of filtering threshold $\\theta$:***\nIn the setting of Figure 3(a) with $n = 10000$ samples, we fix $\\eta = 0.3$ (in-line with the empirically observed clean fraction in CLIP data [1]) and vary the filtering threshold $\\theta$ of the teacher-based filtering. Note that we implicitly vary $\\theta$ by explicitly varying the fraction of data retained in the filtering step. The below table shows that the error of teacher-based filtering is relatively flat for values of $\\theta$ in the vicinity of the optimal threshold $\\theta^{\\star}$. An analogous experiment on real data [1, Figure 2] makes a similar observation.\n\n| Fraction of data retained   |  Mean error ($\\pm$ 1 $\\sigma$) |\n|------------|-------------------------|\n| 1%         |  $28.76 \\pm 4.00$ $\\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| 10%        |  $11.79 \\pm 1.20$ $\\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| 20%        |  $9.85 \\pm 1.39$ $\\text{ } \\text{ } \\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| **30%**    |  $9.08 \\pm 1.15$ $\\text{ } \\text{ } \\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| 40%        |  $8.97 \\pm 1.09$ $\\text{ } \\text{ } \\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| 50%        |  $8.71 \\pm 1.05$ $\\text{ } \\text{ } \\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| 100%       |  $16.51 \\pm 2.03$ $\\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n\n### (4) Limited experimental validation. \n\nThe teacher-based filtering (Figure 1c, Algorithm 1) has been relatively well-studied empirically, for instance in [1, 2, 3].  The focus of this paper is to theoretically analyze this approach, and demonstrate a provable benefit. Since this involved no new algorithmic modifications, we relied on synthetic experiments (Figure 3a) and reused a real-data experiment (Figure 3b), instead of a suite of new experiments. \n\nThat said, we plan to run small-scale CLIP training experiments (equivalent to the `small` scale in DataComp [1]) with a focus on the data quality, particularly focusing on the misalignment in image-text pairs. The main idea of this experiment is as follows:\n- Similar to Figure 3(b) replicated from [2], we would like to have two data sources: one *clean* and one *noisy*. We can sample data with $\\eta$, $1-\\eta$ proportions to create the training dataset. From this, we can observe the variation in the learnt model's performance with varying $\\eta$.\n- Further, we plan to study the effect of changing the clean data source (similar to the idea in [4]), model architecture and size, and the total dataset size.\n\n### (5) Other factors like data volume, model architecture, etc. not analyzed.\n\nThe central research question of our paper is to isolate and understand the specific role of the clean data fraction $\\eta$, a critical but less understood variable in the context of web-scale datasets. Our goal is to show that the train-filter-train paradigm achieves better dependence in $\\eta$ compared to the baseline of [6]. To study its effect rigorously, we deliberately kept other factors constant in our experiments. However, we agree that factors like data volume and model architecture are important variables in model performance (note that the theory does capture the dependence on data volume, i.e. number of samples $n$). \n\n### References\n\n[1] DataComp: In search of the next generation of multimodal datasets, arxiv:2304.14108.\n\n[2] Data Filtering Networks, arxiv:2309.17425. \n\n[3] CLIPLoss and Norm-Based Data Selection Methods for Multimodal Contrastive Learning, arxiv:2405.19547.\n\n[4] Quality Not Quantity: On the Interaction between Dataset Design and Robustness of CLIP, arxiv:2208.05516.\n\n[5] Improving Multimodal Datasets with Image Captioning, arxiv:2307.10350.\n\n[6] Understanding Multimodal Contrastive Learning and Incorporating Unpaired Data, arxiv:2302.06232.\n\n[7] The Power of Contrast for Feature Learning: A Theoretical Analysis, arxiv:2110.02473.\n\n[8] Benign Overfitting in Linear Regression, arxiv:1906.11300.\n\n[9] Towards a statistical theory of data selection under weak supervision, arxiv:2309.14563.\n\n[10] Iterative Least Trimmed Squares for Mixed Linear Regression, arxiv:1902.03653.\n\n[11] Scaling Laws in Linear Regression: Compute, Parameters, and Data, arxiv:2406.08466.\n\n[12] Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices, arxiv:1305.3235.\n\n[13] Going Beyond Nouns With Vision & Language Models Using Synthetic Data, arXiv:2303.17590.\n\n[14] The Implicit Bias of Gradient Descent on Separable Data, arXiv:1710.10345.\n\n[15] In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning, arXiv:1412.6614."}, {"review_id": "9dHaLlqo1M", "reviewer": "Reviewer_vAKC", "summary": "This paper studies the theory of teacher-based data filtering for multimodal contrastive training. The study analyzes the performance of filtered contrastive learning within the standard bimodal data generation framework. Compared with unfiltered contrastive learning whose error grows in proportion to the inverse of the clean-pair fraction, the teacher-based filtering reduces the dependence. In highly corrupted settings (i.e. very small fraction of clean data), the teacher-based filtering setup achieves an error rate that no longer depends on clean data fraction. Synthetic experiments validates the corollary and theorem, and supporting real experiments from Fang et al. [10] also show that the qualitative conclusions drawn from the theory hold with real image-text data too.", "questions": "See questions listed in the above weaknesses section.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Novel theoretical analysis into data filtering for multimodal contrastive learning. Data filtering has been widely adopted in contrastive learning. This paper analysed theoretically why teacher-based filtering improves multimodal contrastive learning. The surprising finding as mentioned in #2 is novel, that filtering can surpass the “oracle” that uses only clean data when the clean data fraction is low.\n- This paper includes validation experiments with synthetic data, showing that results from synthetic experiments align well with the theoretical rates from the corollary and the theorem. They also connect the results with the results from real experiments from Fang et al. [10].\n\n\nWeaknesses:\n- The experimental evidence is limited that the synthetic experiments may not capture all factors that matter in real-world datasets. And the real experiments from Figure 3(b) are created with an artificial setup that mixes CC-12M (high quality) and CommonPool (low quality). As a result, it is unclear how the theoretical analysis translates to actual improvements in downstream tasks or metrics.\n- The selected two-stage training procedure is very practical and relies on a lot of empirical iterations. The theory guarantees rely on an optimal threshold $\\theta^*$ that depends on unknown data parameters (e.g. clean data fraction). In practice with noisy web-scale data, choosing this threshold is non-trivial to make sure neither too many bad samples are kept nor too many good samples are dropped. It would be nice to demonstrate how the analysis could be useful for practitioners.", "was_revised": true, "final_justification": "I appreciate the value of theoretical analysis. The additional experiments from authors showed the robustness of choosing a reasonable $\\theta$. I also read other reviewers' comments and noticed the shared point around practical applicability as summarized by reviewer qb7P. Taking that into consideration, this paper still falls slightly above the acceptance threshold and I would keep my original rating.", "rebuttal": "We thank the reviewer for their detailed and constructive feedback. We appreciate the positive comments about the novelty of the theoretical contributions, and about the suprising finding of the independent-of-$\\eta$ regime in Theorem 1. In the following, we address the concerns raised.\n\n### (1) Experiments are in a controlled setting, theory's applicability to real data and real metrics is unclear.\n\nIt is true that both Figures 3(a) and 3(b) explicitly control for the clean fraction $\\eta$, and real data in the wild displays other factors of variation (e.g., data quality in the individual modalities -- image and text). Firstly, we'd like to point out that teacher-based filtering is known to work well in the wild too, with real data (e.g., [1, Figure 2], [2,3]). \n\nThe controlled experimental setting in this paper was a **deliberate choice to rigorously isolate the dependence** on $\\eta$. *Because* we varied only $\\eta$ in Figure 3(b), it demonstrates (with real data) that teacher-based filtering can help improve the $\\eta$ dependence on the downstream performance. Note the y-axis for Figure 3(b) is `1 - ImageNet Accuracy`, a **key downstream metric** that practitioners care about. This empirically validates what our theory predicts: (1) the fraction of aligned pairs is a critical factor that determines downstream model performance, and (2) teacher-based filtering improves the dependence on $\\eta$. \n\nOn the theoretical side, we believe it is indeed possible to extend the framework to include other factors of variation for a more complete picture. For instance, one could try to capture that a significant portion of the marginal distributions $D_x, D_{\\widetilde{x}}$ are individually noisy beyond the faulty pairings (i.e. many images and captions are simply garbage). This is an interesting and useful direction, but capturing this with the right mathematical assumptions and the subsequent analysis falls outside the scope of the current work.\n\n\n### (2a) Theory uses the optimal threshold $\\theta^{\\star}$, how to select $\\theta$ practically?\n\nIndeed, the choice of the filtering threshold $\\theta$ is an important hyperparameter and requires care in its selection. Let us explain two points in response to this query:\n- We note that the error achieved by teacher-based filtering is fairly **robust to the choice of $\\theta$**. Our synthetic experiment in Figure 3(a) was conducted with a fixed, untuned threshold of $\\theta=0$. Further, we conducted an experiment measuring the sensitivity of final error with respect to the choice of $\\theta$. The experiment details and results are below (###).\n- In practice, this scalar hyperparameter can be **tuned like other commonly used hyperparameters in machine learning**. For example, convex optimization theory states its theorems for the optimal learning rate $\\alpha^{\\star}$ and in practice the learning rate $\\alpha$ needs to be tuned. Similarly, we state our theorem with the optimal threshold $\\theta^{\\star}$ and in practice the threshold $\\theta$ needs to be tuned. In practice, one should tune the size of retained dataset, instead of the parameter $\\theta$. A practical rule of thumb is to filter out between 70%~80% of training data, in the case of internet scale datasets [1].\n\n***### Experiment for error robustness to choice of filtering threshold $\\theta$:***\nIn the setting of Figure 3(a) with $n = 10000$ samples, we fix $\\eta = 0.3$ (in-line with the empirically observed clean fraction in CLIP data [1]) and vary the filtering threshold $\\theta$ of the teacher-based filtering. Note that we implicitly vary $\\theta$ by explicitly varying the fraction of data retained in the filtering step. The below table shows that the error of teacher-based filtering is relatively flat for values of $\\theta$ in the vicinity of the optimal threshold $\\theta^{\\star}$. An analogous experiment on real data [1, Figure 2] makes a similar observation.\n\n| Fraction of data retained   |  Mean error ($\\pm$ 1 $\\sigma$) |\n|------------|-------------------------|\n| 1%         |  $28.76 \\pm 4.00$ $\\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| 10%        |  $11.79 \\pm 1.20$ $\\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| 20%        |  $9.85 \\pm 1.39$ $\\text{ } \\text{ } \\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| **30%**    |  $9.08 \\pm 1.15$ $\\text{ } \\text{ } \\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| 40%        |  $8.97 \\pm 1.09$ $\\text{ } \\text{ } \\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| 50%        |  $8.71 \\pm 1.05$ $\\text{ } \\text{ } \\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n| 100%       |  $16.51 \\pm 2.03$ $\\text{ } \\text{ } \\text{ }$ ($\\times 1e-4$) |\n\n### (2b) What are the practical implications of the analysis?\n\nBeyond its theoretical contributions, Theorem 1 can offer some useful guidance to practitioners by formalizing the trade-off between data quantity ($n$) and quality (via clean fraction $\\eta$). This allows practitioners to move from qualitative intuition to principled, **quantitative decision-making in common data curation scenarios**. The following examples illustrate this in detail:\n\n- **Dataset election:** Consider a practitioner faced with the choice to pick a dataset among many alternatives. Often the choice involves a large, noisy dataset (large $n$, small $\\eta$) versus a smaller, curated one (small $n$, large $\\eta$). Further, let's assume that the dataset provider also provides an approximation of the data quality in terms of estimated $\\eta$, but the actual datasets might be behind a paywall. By plugging these values into the error bounds from Theorem 1 (i.e., comparing which option yields a smaller error), one can make a more informed decision about which dataset is likely to produce a better model. \n\n- **Valuating Data Augmentation:** When considering whether to invest resources in collecting a small amount of clean data to augment a large, noisy corpus, our theorem provides quantitative guidance. It helps estimate the expected performance gain from the increased $\\eta$ and increased $n$, allowing a practitioner to assess if the return on investment is worthwhile.\n\nCrucially, the two distinct error regimes identified in Theorem 1 provide non-obvious insights. The $1/\\sqrt{\\eta}$ error rate in the low-$\\eta$ regime suggests that for very noisy datasets, simply increasing data volume ($n$) can be surprisingly effective, a practical takeaway that is not immediately intuitive.\n\n### References\n\n[1] DataComp: In search of the next generation of multimodal datasets, arxiv:2304.14108.\n\n[2] Data Filtering Networks, arxiv:2309.17425. \n\n[3] CLIPLoss and Norm-Based Data Selection Methods for Multimodal Contrastive Learning, arxiv:2405.19547.\n\n[4] Quality Not Quantity: On the Interaction between Dataset Design and Robustness of CLIP, arxiv:2208.05516.\n\n[5] Improving Multimodal Datasets with Image Captioning, arxiv:2307.10350.\n\n[6] Understanding Multimodal Contrastive Learning and Incorporating Unpaired Data, arxiv:2302.06232.\n\n[7] The Power of Contrast for Feature Learning: A Theoretical Analysis, arxiv:2110.02473.\n\n[8] Benign Overfitting in Linear Regression, arxiv:1906.11300.\n\n[9] Towards a statistical theory of data selection under weak supervision, arxiv:2309.14563.\n\n[10] Iterative Least Trimmed Squares for Mixed Linear Regression, arxiv:1902.03653.\n\n[11] Scaling Laws in Linear Regression: Compute, Parameters, and Data, arxiv:2406.08466.\n\n[12] Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices, arxiv:1305.3235.\n\n[13] Going Beyond Nouns With Vision & Language Models Using Synthetic Data, arXiv:2303.17590.\n\n[14] The Implicit Bias of Gradient Descent on Separable Data, arXiv:1710.10345.\n\n[15] In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning, arXiv:1412.6614."}, {"review_id": "tEUGw71Nd6", "reviewer": "Reviewer_AyoJ", "summary": "This paper explores the advantage of data filtering in improving the performance of contrastive learning in multimodal representation learning. Specifically, the paper provides a theoretical explanation for the empirical success of teacher-based data filtering, which uses a pre-trained model to filter out low-quality data from large-scale multimodal datasets. The authors establish bounds on the performance improvement obtained through data filtering and demonstrate the advantages of this method over traditional contrastive learning without filtering.", "questions": "Please check the former section.", "limitations": "Please check the former section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. The paper provides a detailed theoretical analysis of the benefits of data filtering in contrastive learning. \n2. The idea that removing low-quality data pairs improves multimodal contrastive learning is intuitive, and the analysis about it has a great potential.\n\nWeakness:\n\n1. The idea of filtering out low-quality data pairs to improve multimodal contrastive learning is highly intuitive. It's a common approach in many domains, like active learning, where selecting high-quality data is known to improve model performance. While the theoretical analysis is valuable, it doesn’t lead to the development of any new or better algorithms. The potential for algorithmic innovation stemming from the theory is not explored in the paper. How to leverage this theory to design more efficient or scalable algorithms for data filtering in real-world scenarios?\n2. The theoretical results provided by the authors are not sufficiently linked to real-world applications. It remains unclear how the theory could directly inform practices in real-world cases. For instance, how would one practically implement a better teacher-based filtering approach?\n3. The experiments are conducted only on synthetic data and one real-world dataset. A more diverse set of experiments is needed to validate the theoretical results.", "was_revised": true, "final_justification": "After the rebuttal, my major concerns are addressed by the authors, and I keep my positive score.", "rebuttal": "We thank the reviewer for their detailed and constructive feedback. We appreciate the positive comment about the comprehensiveness of the theoretical contributions, and also about the suprising finding of the independent-of-$\\eta$ regime in Theorem 1. In the following, we address the concerns raised.\n\n### (1) How to use the theory to get better algorithms?\n\nThis is a great question, thank you for raising this. To the best of our knowledge, this is the first work that provably shows a benefit of teacher-based data filtering. We believe this is a significant contribution, which lays the necessary theoretical groundwork that future algorithmic advancements can build upon. \n\nOne such idea is relaxing Assumption 2 to a general covariance matrix for the noise $\\xi$. This exercise indicated that teacher-based filtering can introduce an algorithmic bias. That is, the error with data filtering stays above zero even when $n \\rightarrow \\infty$ (i.e. a statistically inconsistent estimate). Future work could study the precise behaviour of this bias, which could in turn lead to algorithmic improvements. For instance, this might reveal that the standardization of data in the right basis could mitigate this (e.g., normalizing the images in certain ways). This is a very interesting direction, but requires a detailed investigation from both theoretical and empirical angles.\n\n\n### (2) What are the practical implications?\n\nBeyond its theoretical contributions, Theorem 1 also offers some useful guidance to practitioners by formalizing the trade-off between data quantity (i.e. $n$) and quality (via clean fraction $\\eta$). This allows practitioners to move from qualitative intuition to **quantitative decision-making in common data curation scenarios**. The following two examples illustrate this in detail:\n- **Dataset election:** Consider a practitioner faced with the choice to pick a dataset among many alternatives. Often the choice involves a large, noisy dataset (large $n$, small $\\eta$) versus a smaller, curated one (small $n$, large $\\eta$). Further, the high-level aggregates (like $n$ and $\\eta$ or approximate $\\eta$) are usually available, but the actual datasets might be behind a paywall. By plugging these values into the error bounds from Theorem 1 (i.e., comparing which option yields a smaller error), one can make a more informed decision about which dataset is likely to produce a better model.\n- **Valuating Data Augmentation:** When considering whether to invest resources in collecting a small amount of clean data to augment a large, noisy corpus, our theorem provides quantitative guidance. It helps estimate the expected performance gain from the improved $\\eta$ and increased $n$, allowing a practitioner to assess if the return on investment is worthwhile.\n\nCrucially, the two distinct error regimes identified in Theorem 1 provide non-obvious insights. The $1/\\sqrt{\\eta}$ error rate in the low-$\\eta$ regime suggests that for very noisy datasets, simply increasing data volume ($n$) can be surprisingly effective, a practical takeaway that is not immediately intuitive.\n\n### (3) Limited empirical validation.\n\nThe teacher-based filtering (Figure 1c, Algorithm 1) has been relatively well-studied empirically, for instance in [1, 2, 3]. The focus of this paper is to theoretically analyze this approach, and demonstrate a provable benefit. Since this involved no new algorithmic modifications, we relied on synthetic experiments (Figure 3a) and reused a real-data experiment (Figure 3b), instead of a suite of new experiments. \n\nThat said, we plan to run small-scale CLIP training experiments (equivalent to the `small` scale in DataComp [1]) with a focus on the data quality, particularly focusing on the misalignment in image-text pairs. The main idea of this experiment is to have two data sources (one *clean* and one *noisy*), similar to Figure 3(b) replicated from [2]. We can sample data with $\\eta$, $1-\\eta$ proportions to create the training dataset. From this, we can observe the variation in the learnt model's performance with varying $\\eta$.\n\n### References\n\n[1] DataComp: In search of the next generation of multimodal datasets, arxiv:2304.14108.\n\n[2] Data Filtering Networks, arxiv:2309.17425. \n\n[3] CLIPLoss and Norm-Based Data Selection Methods for Multimodal Contrastive Learning, arxiv:2405.19547.\n\n[4] Quality Not Quantity: On the Interaction between Dataset Design and Robustness of CLIP, arxiv:2208.05516.\n\n[5] Improving Multimodal Datasets with Image Captioning, arxiv:2307.10350.\n\n[6] Understanding Multimodal Contrastive Learning and Incorporating Unpaired Data, arxiv:2302.06232.\n\n[7] The Power of Contrast for Feature Learning: A Theoretical Analysis, arxiv:2110.02473.\n\n[8] Benign Overfitting in Linear Regression, arxiv:1906.11300.\n\n[9] Towards a statistical theory of data selection under weak supervision, arxiv:2309.14563.\n\n[10] Iterative Least Trimmed Squares for Mixed Linear Regression, arxiv:1902.03653.\n\n[11] Scaling Laws in Linear Regression: Compute, Parameters, and Data, arxiv:2406.08466.\n\n[12] Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices, arxiv:1305.3235.\n\n[13] Going Beyond Nouns With Vision & Language Models Using Synthetic Data, arXiv:2303.17590.\n\n[14] The Implicit Bias of Gradient Descent on Separable Data, arXiv:1710.10345.\n\n[15] In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning, arXiv:1412.6614."}, {"review_id": "lMf2Ga6TeR", "reviewer": "Reviewer_qb7P", "summary": "This paper derives **bounds for the error in the contrastive learning** setup when the **data is filtered using a teacher** that is trained from the same data.\n\nThe contrastive learning setup is **simplified** to make it amenable to mathematical analysis: the data pairs are assumed to be low rank signals (i.e. underlying vector $z$ with dimensionality $r$ is projected to dimensionality $d$ where signal $x$ is observed) to which zero mean isotropic Gaussian noise is added. With probability $\\eta$ the observed pairs are projected from the same $z$, and with probability $1-\\eta$ the pairs are sampled independently (in both cases sampled from standard multivariate Gaussian). The contrastive training process is modeled as learning  the projection that maps $x$ back to $z$. The data filtering is modeled as first learning a linear projection on half of the data, and the doing threshold-based filtering of the pairs after applying the learnt mapping. The error finally is defined as the chordal distance between the subspaces of the learned projection and the generating projection.\n\nIn this simplified setup, the authors show that the error is bounded by $\\eta^{-1}n^{-0.5}$ in the unfiltered setup, and by $\\eta^{-0.5}n^{-0.5}$ and $n^{-0.5}$ in the filtered setup (when $\\eta$ is large and when $\\eta$ is small). Note that the rate $n^{-0.5}$ is even better than the rate achieved when training on data that is filtered by an oracle (which is also $\\eta^{-0.5}n^{-0.5}$).", "questions": "1. What would the \"Slope = 1\" and \"Slope = 0.5\" lines look like on FIgure 3b? Is it possible to translate the error bounds as used in this paper (chordal distances of subspaces) to error rates that can be measured in a more realistic setup? Maybe it would be insightful to only remove some of the simplifications but keep others (e.g. generated data with more realistic non-linear training setup) to see which of the findings hold true?\n\n1. The paper argues that in the small $\\eta$ regime, teacher-based filtering has a better bound than oracle-based filtering. The authors explain in appendix H why this is the case. Under which circumstances could something similar be observed in a more realistic and practically relevant setup? Are there any insights from the presented analysis that would explain when filtering can be harmful?\n\n1. The introduction (lines 22-23) states \"smaller but higher quality subsets of the data have been observed to result in better models\". But there are other studies that show that similar models can be trained directly on noisy large scale datasets (e.g. [ALIGN](https://arxiv.org/abs/2102.05918)). The submission argues that filtering with a teacher that is trained on the same data distribution is better than oracle-based filtering. Could it be argued that oracle-based filtering is more similar to the manual filtering that was applied to the CLIP data, while teacher-based filtering could in fact be a mechanism that is more similar to a partly trained network that can learn to ignore noisy data from the same distribution?\n\nSmall comments:\n\n1. Legend Figure 2: consider writing $50000$ instead of $50k$ because the latter (with $k$ in italic font) reads like a variable.\n\n1. Lines 62-69, lines 223-234: Maybe also refer to Section H in this context since that section has some additional information about why something can be learned from corrupted samples.\n\n1. Line 541: Even if the code is simple, I would still find it useful to have it published. That would be beneficial to check some implementation details, and useful to build work on top of what is presented in the paper.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Disclaimer: I am a ML practitioner and have experience with data filtering setup with contrastive models, but I am a novice when it comes to their mathematical analysis. I have read all the parts from the main paper and appendix sections A, B, H – but have skipped appendix sections C-G because I could not give good feedback on the mathematical derivations. I hope that my review of the other parts is still useful and look forward to the discussions from the more mathematically oriented reviewers.\n\n**Strengths**\n\n1. The paper studies a **practically relevant problem**: contrastive learning is still very relevant, for example most state-of-the-art vision encoders are trained with a contrastive loss on image/text pairs. Data filtering is often an integral part in this context and it's important to understand its effects on the learning process.\n\n1. The paper is **well structured and clearly written**. The assumptions are clearly outlined, the main mathematical findings are presented in a concise manner that makes it possible to understand how the results were derived, while keeping all of the details for the long derivations in the appendix.\n\n1. The derivations build on top of an existing literature, like [5] and [22], and extend these previous studies by providing new insights into what happens when the data is filtered using a teacher trained on the same data distribution.\n\n**Weaknesses**\n\n1. From a practical perspective, all the **simplifying assumptions** that make the setup amenable to mathematical analysis create a **large gap with a realistic setup** used to train relevant models. It is hard to translate the final results to something other than \"data filtering can help in the contrastive learning setup\", which is also what is shown qualitatively in Figure 3b. There is a substantial difference between the theoretical results with all the strong simplifications, and a realistic setup like the ones cited in the introduction. Furthermore, the practical setup (Figure 3b) – which does not make reference to the derived bounds anymore but simply shows that performance without filtering decreases more quickly when $\\eta$ becomes smaller – operates at extremely low performance (best achieved accuracy with $\\eta=1$ is below 30%).", "was_revised": true, "final_justification": "I remain with my original rating 4=borderline accept.\n\nThe authors have been very responsive in the rebuttal period and given clear answers to all of my questions. Even though I'm not too familiar with the subject matter (theoretical analysis), after the review process I am fairly confident that the presented work is technically sound and well anchored in the existing literature.\n\nThe reason for not increasing my original rating is mainly that the **authors have still not entirely convinced me about the practical usability of the presented bounds** – the one weakness that I already mentioned in my original review.\nMy concerns could have been resolved, if the authors showed how the quantitative results from the paper could be applied to improve practically important decisions like \"dataset election\" or \"valuating data augmentation\" (as the authors have mentioned in some of the rebuttals, e.g. the [rebuttal to my review](https://openreview.net/forum?id=2xDdVkWrqq&noteId=TkuFczv3As)).\nTo clarify this point I have created a new thread about the [Practical Applicability of the Theoretical Findings](https://openreview.net/forum?id=2xDdVkWrqq&noteId=PffKfAm0vr), in which the authors have replied that this kind of practical decisions cannot be improved directly with the theoretical findings from the paper, but they promised to add more results to the paper that tries to bridge the gap partially, which I think would strengthen the paper.", "rebuttal": "We thank the reviewer for their detailed and constructive feedback. We appreciate the positive comments about the relevance of the theoretical analysis, and the practical impact of data filtering. In the following, we address the concerns raised.\n\n# Weaknesses\n\n### (1) Connection between theory and practice.\n\nIn the following, we will make two points to justify our choices and their usefulness.\n\n**1. Why the linear setup analysis is useful?**\n\nThe goal of our work is to provide theoretical justification for the common empirical observation that data filtering using a teacher CLIP model improves performance. The setup with Linearity and Gaussian noise provides a **tractable setting** to study this phenomenon, and is motivated by **past works** that make the same assumptions [6, 7]. Beyond CLIP filtering, **other phenomena in deep learning** have also been successfully characterized in the linear setup, e.g., benign overfitting [8] (also known as double descent), scaling laws [11], and implicit bias [14, 15]. These topics are foundations of what we call the Theory of Deep Learning, and are textbook materials in courses taught at top institutions. Overall, the linear assumption, though not directly applicable in some real cases, provides a useful abstraction that often **preserves the primary problem characteristics** and helps to build a deeper understanding through a theoretical lens. We believe our work (and the assumptions we have), although simple, is within the typical assumptions made in theoretical anlayses of deep learning, which has proven to be productive and insightful (e.g., [8, 11, 14, 15]). For a detailed justification of using linear models to study deep neural networks, we refer to a nice lecture note [16] by Andrea Montanari at Stanford.\n\n**2. What are the practical implications?**\n\nBeyond its theoretical contributions, Theorem 1 also offers some useful guidance to practitioners by formalizing the trade-off between data quantity ($n$) and quality (via clean fraction $\\eta$). Our analysis allows practitioners to move from qualitative intuition to principled, **quantitative decision-making in common data curation scenarios**. The following two examples illustrate this in detail:\n- **Dataset election:** Consider a practitioner faced with the choice to pick a dataset among many alternatives. Often the choice involves a large, noisy dataset (large $n$, small $\\eta$) versus a smaller, curated one (small $n$, large $\\eta$). Further, the high-level aggregates (like $n$ and $\\eta$ or approximate $\\eta$) are usually available, but the actual datasets might be behind a paywall. By plugging these values into the error bounds from Theorem 1 (i.e., comparing which option yields a smaller error), one can make a more informed decision about which dataset is likely to produce a better model.\n- **Valuating Data Augmentation:** When considering whether to invest resources in collecting a small amount of clean data to augment a large, noisy corpus, our theorem provides quantitative guidance. It helps estimate the expected performance gain from the improved $\\eta$ and increased $n$, allowing a practitioner to assess if the return on investment is worthwhile.\n\nCrucially, the two distinct error regimes identified in Theorem 1 provide non-obvious insights. The $1/\\sqrt{\\eta}$ error rate in the low-$\\eta$ regime suggests that for very noisy datasets, simply increasing data volume ($n$) can be surprisingly effective, a practical takeaway that is not immediately intuitive.\n\nLastly, in relation to a point raised by the reviewer, we would like to argue that a 30% zero-shot accuracy on ImageNet is non-trivial, since no explicit classifier was trained on top of the CLIP embeddings (ImageNet has a 1000 classes, so a random guesser would get 0.1% accuracy). \n\n# Questions\n\n### (1a) About the theoretical metric (chordal distance) v/s real-world metrics.\n\nSince the metric between Fig 3(a) and 3(b) is different (note the different y-axis), the \"slope 1\" and \"slope 0.5\" lines would not make sense on the metric used in Fig 3(b). Relatedly, note that the metric used in Figure 3(b) is not a theoretical distance like the chordal distance. Instead, it is `1 - ImageNet Accuracy`, a downstream metric that practitioners care about.\n\n### (1b) Weakening the assumptions (e.g., removing linearity).\n\nIndeed, weakening the assumptions can be insightful by showing the differences in the observed trends. For example, what would Theorem 1 look like without the linearity assumption? A full analysis of this requires non-trivial analysis that falls outside the scope of this work. That said, linear models have been successfully used to explain many phenomena in modern deep learning, e.g., benign overfitting [8] (also known as double descent), scaling laws [11], and implicit bias [14, 15]. The lessons learned from linear models generally serve as a useful qualitative guide to more complex scenarios. In this paper, we observed the same thing with respect to the real data experiment in Figure 3(b). As indicated in lines 73-74, the qualitative message of the improved dependence, derived from the linear modeling theory, holds true with nonlinear models as well.\n\n### (2) Can teacher-based filtering be harmful?\n\nThis is a great question, thank you for raising this. Indeed, it is a fruitful direction to study how filtering behaves in setups other than the one presented in Section 3.1. One such idea is relaxing Assumption 2 to a general covariance matrix for the noise $\\xi$. This exercise indicates that teacher-based filtering can introduce an algorithmic bias. That is, the error with data filtering stays above zero even when $n \\rightarrow \\infty$ (i.e. a statistically inconsistent estimate). Note that the no-filtering algorithm does not suffer from this.\n\nFuture work could study the precise behaviour of this bias, and how to mitigate this potential harmful effect of data filtering. For instance, this might reveal that the standardization of data in the right basis could mitigate this (e.g., normalizing the images in certain ways). This is a very interesting direction, but requires a detailed investigation from both theoretical and empirical angles.\n\n### (3a) Could it be argued that oracle-based filtering is more similar to the manual filtering that was applied to the CLIP data?\n\nNote that oracle based filtering assumes knowledge of ground-truth parameters (Figure 1b). In this sense, it is hard to compare it with manual filtering, which involves applying heuristics like length of text, quality of image, etc. to filter the dataset. Note that the datasets are huge (billions of samples), meaning that manual filtering can not involve human annotation. In light of this, we don't expect any manual filtering (heuristic-based) to be able to perform like oracle filtering.\n\n### (3b) Teacher-based filtering could in fact be a mechanism that is more similar to a partly trained network that can learn to ignore noisy data from the same distribution?\n\nThis is indeed true. Lines 201-203 posit that the teacher learns a useful signal despite the presence of noisy samples, which help in data filtering. The reason teacher-based can outperform even oracle filtering is the incidental alignment in some noisy samples (Lines 223-225). \n\n# Small comments\n\nThank you for rasining points 1 and 2, we will include them in the revised manuscript. For 3, we indeed plan to release the code publicly on github!\n\n# References\n\n[1] DataComp: In search of the next generation of multimodal datasets, arxiv:2304.14108.\n\n[2] Data Filtering Networks, arxiv:2309.17425. \n\n[3] CLIPLoss and Norm-Based Data Selection Methods for Multimodal Contrastive Learning, arxiv:2405.19547.\n\n[4] Quality Not Quantity: On the Interaction between Dataset Design and Robustness of CLIP, arxiv:2208.05516.\n\n[5] Improving Multimodal Datasets with Image Captioning, arxiv:2307.10350.\n\n[6] Understanding Multimodal Contrastive Learning and Incorporating Unpaired Data, arxiv:2302.06232.\n\n[7] The Power of Contrast for Feature Learning: A Theoretical Analysis, arxiv:2110.02473.\n\n[8] Benign Overfitting in Linear Regression, arxiv:1906.11300.\n\n[9] Towards a statistical theory of data selection under weak supervision, arxiv:2309.14563.\n\n[10] Iterative Least Trimmed Squares for Mixed Linear Regression, arxiv:1902.03653.\n\n[11] Scaling Laws in Linear Regression: Compute, Parameters, and Data, arxiv:2406.08466.\n\n[12] Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices, arxiv:1305.3235.\n\n[13] Going Beyond Nouns With Vision & Language Models Using Synthetic Data, arXiv:2303.17590.\n\n[14] The Implicit Bias of Gradient Descent on Separable Data, arXiv:1710.10345.\n\n[15] In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning, arXiv:1412.6614.\n\n[16] Six Lectures on Linearized Neural Networks, arXiv:2308.13431."}, {"review_id": "2gn74FaKJq", "reviewer": "Reviewer_M3vJ", "summary": "This paper provides a theoretical analysis of teacher-based data filtering in the context of multimodal contrastive learning. It builds on prior linear models of vision-language representation learning and studies how data filtering (particularly using a trained model to score and retain high-quality samples) affects learning performance under a stochastic corruption model.", "questions": "- how limiting is the linear assumption? or in other words, how far from real-world experiments are we when using the linear assumption? I understand the necessity/simplicity of using a linear assumption. Nevertheless, I would be curious to hear the authors' opinion on this. \n- is filtering mainly related to the multimodal pairing or also on noisy samples in general? does it make a difference at all to distinguish between the two cases?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strengths\n\n- Theoretical novelty: The result that filtering can outperform an “oracle” that uses only clean samples is surprising and nontrivial. The analysis highlights the interaction between stochastic corruption and contrastive inner product objectives.\n- Relevance to practice: Teacher-based filtering is increasingly used in real-world large-scale multimodal pretraining (e.g., CLIP, DataComp), yet lacked formal justification.\n- Clarity of analysis: The paper is well-structured and first builds intuition before going into formal details. The progression from baseline to teacher-based methods is systematic.\n\n\n### Weaknesses\n\n- Restrictive assumptions: The analysis relies on linear encoders, Gaussian noise, and exact knowledge of latent dimension $r$. These assumptions simplify analysis but limit applicability to realistic settings involving deep networks and complex noise.\n- Limited empirical validation: While a synthetic experiment is provided, real-world empirical evaluation is absent. The paper refers to past work (e.g., Fang et al.) but doesn’t test its theory in new real-world settings.\n- Teacher training is idealized: The teacher is assumed to generalize well in the corrupted regime, which may not hold in practice (especially when $\\eta$ is small). While this is acknowledged, more discussion on when this assumption breaks would help.", "was_revised": true, "final_justification": "Accept", "rebuttal": "We thank the reviewer for their detailed and constructive feedback. We appreciate the positive comments about the theoretical novelty of the analysis, and the practical relevance of the problem of data filtering. In the following, we address the concerns raised.\n\n# Weaknesses\n\n### (1) Restrictive assumptions.\n\n**Linearity + Gaussianity:** The goal of our work is to provide theoretical justification for the common empirical observation that data filtering using a teacher CLIP model improves performance. The setup of Linearity and Gaussian noise provides a **tractable setting** to study this phenomenon, and is motivated by **past works** that make the same assumptions [6, 7]. Beyond CLIP filtering, **other phenomena in deep learning** have also been successfully characterized in the linear setup, e.g., benign overfitting [8] (also known as double descent), scaling laws [11], and implicit bias [14, 15]. Overall, the linear assumption, though not directly applicable in some real cases, provides a useful abstraction that often **preserves the primary problem characteristics** and helps to build a deeper understanding through a theoretical lens. We believe our work (and the assumptions we have), although simple, is within the typical assumptions made in theoretical anlayses of deep learning, which has proven to be productive and insightful (e.g., [8, 11, 14, 15]). \n\n**Latent dimension $r$:** In practice, the latent dimension $r$ (i.e., the embedding space dimension) is typically a design choice and is therefore known at training time. Theoretically, assuming the underlying $r$ is known allows us to **isolate the effects of data filtering from the separate, well-studied problem of subspace rank estimation** (for e.g., in [12]). Thanks for pointing this out, we think it's useful to add this comment in Line 150.\n\n### (2) Limited empirical validation.\n\nThe teacher-based filtering (Figure 1c, Algorithm 1) has been relatively **well-studied empirically**, for instance in [1, 2, 3]. The focus of this paper is to theoretically analyze this approach, and demonstrate a provable benefit. Since this involved **no new algorithmic modifications**, we relied on synthetic experiments (Figure 3a) and reused a real-data experiment (Figure 3b), instead of a suite of new experiments. \n\nThat said, we plan to run small-scale CLIP training experiments (equivalent to the `small` scale in DataComp [1]) with a focus on the data quality, particularly focusing on the misalignment in image-text pairs. The main idea of this experiment is to have two data sources (one *clean* and one *noisy*), similar to Figure 3(b) replicated from [2]. We can sample data with $\\eta$, $1-\\eta$ proportions to create the training dataset. From this, we can observe the variation in the learnt model's performance with varying $\\eta$.\n\n### (3) Teacher training is idealized. What happens when $\\eta$ is small?\n\n**Meta comment:** We are somewhat unclear about what this question asks. Below we provide a response, but please clarify the question further if this does not answer it. In particular, please also point out which line number you are referring to when you say \"while this is acknowledged\".\n\n**Response:** The modeling assumptions result in the teacher achieving error $1/\\eta \\sqrt{n}$ for $\\eta > \\eta_0$, as shown in Corollary 1 for an appropriate $\\eta_0$. We would like to stress the condition of $\\eta > \\eta_0$, as this shows that even the current simplistic setup **captures that $\\eta$ needs to be large enough for the teacher to learn something meaningful** (the rightmost points in Figure 3(a) validate this empirically, via the growing error bars and deviation from the theoretical trend). That said, you are right to believe the threshold $\\eta_0$ in practice will be much higher than the one predicted by the Corollary 1. We believe the below two factors will play a crucial role in this:\n\n- Introduction of non-linearity, since parameter estimation becomes statistically harder with non-linear function classes.\n- The model in Section 3.1 only assumes a binary distinction of clean v/s noisy to model data quality. Real datasets display a broader range of data quality across samples.\n\nWe can include a discussion about this in the revised manuscript. However, a detailed study would involve a significant modification to the setup in Section 3.1, and falls outside the scope of the current work. \n\n# Questions\n\n### (1) Comment on the limitations of the linear assumption.\n\nLinear models have been surprisingly successful in explaining important empirical phenomena in highly nonlinear deep neural networks. This includes benign overfitting (also known as double descent) [8], scaling laws [11], and implicit bias [14, 15]. Closest to our problem might be [9], where the authors analyze linear regression to demonstrate the gain of data filtering. For a detailed justification of using linear models to study deep neural networks, we refer to a nice lecture note [16] by Andrea Montanari at Stanford.\n\nDespite these successes, linear models have notable limitations. They assume that learning operates in a regime where the deep neural network can be well approximated by its first-order Taylor expansion. It's crucial to understand that training within this regime is significantly less powerful than fully training neural networks. While it's possible to train neural networks in a way that makes them amenable to this first-order approximation, this often occurs as a side effect of very specific parametrization choices.\n\nThis implies that while we can restrict hyperparameter choices to make linear models more accurate at approximating actual deep neural network training dynamics, doing so would likely compromise the practical performance of the resulting models. Although the high-level insights derived from linear modeling have proven surprisingly successful, the specific theorems themselves may not accurately predict the behavior of nonlinear model training. Therefore, the lessons learned from linear models should generally be interpreted qualitatively, serving more as a justification or general guidance rather than providing immediate predictive insights.\n\nIn this paper, we observed the same thing with respect to the real data experiment in Figure 3(b). As indicated in lines 73-74, the qualitative message of the improved $\\eta$ dependence, derived from the linear modeling theory, holds true with nonlinear models as well.\n\n\n### (2) Discussion of data filtering beyond unaligned pairings.\n\nThis is an insightful question, thank you for raising this! Indeed, the community is increasingly observing the utility of data filtering in various settings. We will answer this in two parts:\n\n1. **Data filtering for multimodal data beyond unaligned pairings.** \n\nIndeed, beyond unaligned pairings, data filtering is also used to remove other kinds of noisy data (i.e., simply bad image or text quality). For example, empirically, the creation of large scale datasets (e.g. LAION-5B, DataComp-1B) involved various heuristic-based filters to remove data with 'bad' samples in individual modalities. \n\nTheoretically, we believe it does make sense to distinguish between these two cases. A better model to study the latter would try to capture that a significant portion of the marginal distributions $D_x, D_{\\widetilde{x}}$ are individually noisy beyond the faulty pairings. The generative model described in Section 3.1 does not capture this due to a common prior $D_z$ for both modalities.\n\nOverall, this would be akin to studying the $\\eta = 1$ case in the new setup described above, and asking, does filtering still help? This is a very valid direction of future work, but formulating the right mathematical assumptions and the subsequent analysis falls outside the current scope. \n\nNote that our main result -- improving the error dependence from $1/\\eta$ to $1/\\sqrt{\\eta}$ (or better) -- is a statement about solving the pairing problem. This **gain cannot be achieved by simply addressing per-modality noise**. Hence, it is needed to distinguish this case with others studied in the past. Of course, the practical reality is a mixture of these two cases (unaligned pairs + noisy samples in individual modalities). In this work, we focus on the alignment problem only.\n\n2. **Data filtering for general data.** \n\nBeyond multimodal data, data filtering has also been studied in the usual statistical framework, assuming access to $n$ samples (not necessarily multimodal) [9, 10]. Again, it is worth noting that none of these frameworks capture the pairing problem. Further, these works also largely study the linear case for their theoretical contributions.\n\n# References\n\n[1] DataComp: In search of the next generation of multimodal datasets, arxiv:2304.14108.\n\n[2] Data Filtering Networks, arxiv:2309.17425. \n\n[3] CLIPLoss and Norm-Based Data Selection Methods for Multimodal Contrastive Learning, arxiv:2405.19547.\n\n[4] (unused reference)\n\n[5] (unused reference)\n\n[6] Understanding Multimodal Contrastive Learning and Incorporating Unpaired Data, arxiv:2302.06232.\n\n[7] The Power of Contrast for Feature Learning: A Theoretical Analysis, arxiv:2110.02473.\n\n[8] Benign Overfitting in Linear Regression, arxiv:1906.11300.\n\n[9] Towards a statistical theory of data selection under weak supervision, arxiv:2309.14563.\n\n[10] Iterative Least Trimmed Squares for Mixed Linear Regression, arxiv:1902.03653.\n\n[11] Scaling Laws in Linear Regression: Compute, Parameters, and Data, arxiv:2406.08466.\n\n[12] Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices, arxiv:1305.3235.\n\n[13] (unused reference)\n\n[14] The Implicit Bias of Gradient Descent on Separable Data, arXiv:1710.10345.\n\n[15] In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning, arXiv:1412.6614.\n\n[16] Six Lectures on Linearized Neural Networks, arXiv:2308.13431."}]

Author rebuttal:

Meta-review: The paper was reviewed by 5 experts in the field. After extensive discussions, all reviewers reached a consensus to accept the paper. The AC reads the paper, the reviews, and the authors' responses carefully. The AC shares a similar concern with reviewer qb7P on the practical implications of the findings in this work. However, the AC understands the difficulty of dealing with the complexity of modern deep neural networks in a theoretical work. Overall, the AC believes this paper is a solid theoretical work that provides a nice way of explaining the effectiveness of using model-based data filtering CLIP-style contrastive models.
Decision: Accept (poster)