On the Comparison between Multi-modal and Single-modal Contrastive Learning

Authors: wei  huang
riken  aip
andi  han
yongqiang  chen
yuan  cao
zhiqiang  xu
taiji  suzuki
Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-24 13:42:30

Abstract: Multi-modal contrastive learning with language supervision has presented a paradigm shift in modern machine learning. By pre-training on a web-scale dataset, multi-modal contrastive learning can learn high-quality representations that exhibit impressive robustness and transferability. Despite its empirical success, the theoretical understanding is still in its infancy, especially regarding its comparison with single-modal contrastive learning. In this work, we introduce a feature learning theory framework that provides a theoretical foundation for understanding the differences between multi-modal and single-modal contrastive learning. Based on a data generation model consisting of signal and noise, our analysis is performed on a ReLU network trained with the InfoMax objective function. Through a trajectory-based optimization analysis and generalization characterization on downstream tasks, we identify the critical factor, which is the signal-to-noise ratio (SNR), that impacts the generalizability in downstream tasks of both multi-modal and single-modal contrastive learning. Through the cooperation between the two modalities, multi-modal learning can achieve better feature learning, leading to improvements in performance in downstream tasks compared to single-modal learning. Our analysis provides a unified framework that can characterize the optimization and generalization of both single-modal and multi-modal contrastive learning. Empirical experiments on both synthetic and real-world datasets further consolidate our theoretical findings.

Main paper: 
 introduction: 
 Large-scale pre-trained models have achieved unprecedented success, including GPT series [6, 41] , LLaMa [53] , among many others. CLIP [42] as a typical example, uses a multi-modal contrastive learning framework to learn from a massive scale of image-caption data. The multi-modal contrastive learning in CLIP has shown significant capabilities to learn high-quality representations, which are ready to be adapted to a wide range of downstream tasks, forming the backbone of generative models like DALL-E2 [43] , prompt learning [61] as well as general purpose multi-modal agents [62, 35] . Given the huge success of models like CLIP that have stellar zero-shot and few-shot capabilities on a wide range of out-of-distribution (OOD) benchmarks, they have been widely recognized as foundation models (FMs). More similar examples are given by ALIGN [28] , Florence [59] , BLIP [33] , Flamingo [1] .Despite the unprecedented success achieved by multi-modal contrastive learning, the fundamental mechanism that leads to greater performance, especially compared to single-modal contrastive learning is still under-explored. Recently, several seminal works provided theoretical explanations for either single-modal [4, 5, 14, 48, 24, 7, 50, 49, 20] or multi-modal contrastive learning [38, 37, 44, 12] . For example, [56] studied how single-modal contrastive learning learns the feature representations for neural networks by analyzing its feature learning process. As for multi-modal contrastive learning, [12, 58] provided explanations for why multi-modal contrastive learning demonstrates zero-shot transferability, and robustness to distribution shifts, than supervised learning, which offer valuable insights. Although both lines of the existing works provide valid theoretical insights under the respective settings, rare work has compared the optimization and generalization of the two types of contrastive learning under a unified framework. This motivates us to establish a systematic feature learning analysis for both single-modal and multi-modal contrastive learning.In particular, we consider a data generation model that contains two modalities of data, which are generated from signal and noise features. The signal feature correlates in different modalities, while there is no correlation between noise features among modalities. We then study the optimization of single-modal and multi-modal contrastive learning under gradient descent training. By studying the trajectories of signal learning and noise memorization, we establish the convergence conditions and further characterize the generalization ability in the downstream tasks. The results show that, through the cooperation between modalities, multi-modal contrastive learning can achieve better generalization in the downstream task. In contrast, without the help of the second modality, singlemodal contrastive learning concentrates on learning noise from the data, and thus generalizes poorly on the downstream tasks. The main contributions of this work are summarized as follows:• This work establishes the first systematic comparative optimization analysis for single-modal and multi-modal contrastive learning under gradient descent training in non-convex settings. We show that both single-modal and multi-modal can achieve near-zero training error under InfoMax contrastive loss after polynomial number of iterations, by overcoming the non-convex difficulty.• By a trajectory-based analysis of the signal learning and noise memorization of the ReLU network from the data, we successfully characterize the difference in generalization between single-modal and multi-modal contrastive learning. The distinct SNRs of different modalities lead to a divergence in the generalization of downstream tasks for the two contrastive learning frameworks.• Our theory suggests that the advantage of multi-modal over single-modal contrastive learning comes from the high quality of the second modality and the cooperation between the two modalities through contrastive learning. This divergence is ultimately reflected in the difference in feature learning and the final gap in downstream task generalization. Experimental results on both synthetic and real-world datasets confirm our theoretical findings and understanding. 
related work: 
 Theoretical Understanding of Single-modal Contrastive Learning. The seminal work [4] started theoretical research on single-modal contrastive learning. They assumed that different positive samples are independently drawn from the same latent class, making a connection to supervised learning. [55] identified two key properties related to the contrastive loss: alignment and uniformity.Alongside, [32] illustrated that predicting auxiliary prediction tasks helps in learning representations effective for downstream prediction tasks, and [52] provided a theoretical analysis of contrastive learning in the multi-view setting. Besides, [51] proposed a theoretical framework to understand contrastive self-supervised learning from an optimization perspective. [21] proposed a loss that performs spectral decomposition on the population augmentation graph and can be succinctly written as a contrastive learning objective on neural net representations. [46] pointed out the importance of inductive biases of the function class and training algorithm in understanding contrastive learning. The most related work to us is the work by [56] . Similar to them, this work studies ReLU networks and considers the signal-noise data model. However, we do not require the adjustable bias term in the activation function, which plays a critical role in [56] . Furthermore, this work adopts a unified framework to compare with multi-modal contrastive learning, which is out of scope in [56] .Understanding of Multi-modal Contrastive Learning. As the multi-modal contrastive learning approaches such as CLIP received great success, recent works have been proposing explanations from empirical perspective. [36] empirically showed that high train-test similarity is insufficient to explain CLIP's OOD performance. [60] illustrated that CLIP behaves similarly to Bags-of-words in language-based image retrieval, i.e., the order of words in the input sentence does not largely affect CLIP to find the corresponding image. Besides, [16] demonstrated that training data diversity and the ability to leverage the diversity as supervised learning is the key to the effective robustness of CLIP.Theoretically, [13] proved that multi-modal contrastive learning can block-identify latent factors shared between modalities by the a generative data model. [44] analyzed the training dynamics of a simple multi-modal contrastive learning model and show that contrastive pairs are important for the model to efficiently balance the learned representations. Furthermore, [38] showed that each step of loss minimization by gradient descent can be seen as performing SVD on a contrastive cross-covariance matrix. Similar to us, [25] tried to answer why multi-modal learning is better than single model learning. However, they did not consider contrastive learning and thus cannot explain the success of multi-modal contrastive multi-modal learning.Data Quality Matters for Multi-modal Contrastive Learning. Aligned with our theoretical results, there is a lot of empirical evidence showing that improving the alignment quality with more descriptive captions improves multi-modal contrastive learning. [16] show that the training distribution mostly determines the generalizability of CLIP. Furthermore, [47, 40, 18, 17] find filtering poorly aligned image-caption samples used for training leads to further improvements. Besides, [45, 39, 15] demonstrate that improving the descriptiveness of the captions could further boost the performance of CLIP. Besides, [34] demonstrated that the caused by a combination of model initialization and contrastive learning optimization. However, their results do not take neural network architecture into consideration, and do not provide an analysis of test errors either. 
problem setting: 
 Notation. We use bold-faced letters for vectors and matrices otherwise representing scalar. We use ∥ • ∥ 2 to denote the Euclidean norm of a vector or the spectral norm of a matrix, while denoting ∥ • ∥ F as the Frobenius norm of a matrix. For a neural network, we denote σ(•) as the activation function and we adopt ReLU activation where σ(x) = max{0, x} in this work. To simplify, we denote [n] = {1, 2, . . . , n}.Data Model. In this work, we consider the following data model, which consists of signal and noise. In the first modality, example (x, y) ∼ D is generated as follows:EQUATIONwhere x ∈ R 2d is the input feature and y ∈ {-1, 1} is the corresponding label generated from Rademacher distribution. In particular, x (1) = yµ ∈ R d is the task-relevant signal vector, andx (2) = ξ ∼ N (0, σ 2 ξ I) ∈ R d is the task-irrelevant noise vector.Intuitively, if a network learns primarily from signal, it can effectively generalize to unseen data and vice versa. Similar data models have been adopted in recent theoretical works on supervised learning [2, 26, 8, 23, 31, 63, 22, 11] and self-supervised learning [56, 50, 30] .Similarly for the second modality, a sample ( x, y) ∼ D is generated asEQUATIONwhere the input feature x ∈ R 2 d and the label y is shared with the first modality. Besides, the signal is a given vector µ ∈ R d , and noise follows ξ ∼ N (0, σ 2 ξ I) ∈ R d. The linear data models for multi-modal learning have also been studied in previous work [44] . To simplify the analysis, we set d = d, σ ξ = σ ξ . However, we highlight that extensions to deal with unmatched dimension and noise level is possible.We use a single-layer neural network h : R 2d → R m with ReLU activation as our encoder, where m is the number of neurons, which represents the embedding dimension. More precisely, h(x) = [ h1 (x), . . . , hm (x)] ⊤ ∈ R m , where hr (x) = h r (x (1) ) + h r (x (2) ),here we let h r (x(i) ) = σ(⟨w r , x (i) ⟩) for r ∈ [m], i ∈ [2], and σ(•) is the ReLU activation function.We adopt a Gaussian to initialize the weights w (0) r ∼ N (0, σ 2 0 I), where σ 0 severs as the strength. Given a pair of positive data samples, the contrastive loss function is based on the similarity measure defined as the inner product between the representation of two samples x, x ′ ∈ R 2d :EQUATIONwhere the sg(•) is the stop-gradient operation, which is inspired by recent empirical works [19, 10] and theoretical work studying contrastive learning [56] . Here we define positive sample asEQUATIONIn particular, we consider the form of augmentation where the signal stays invariant while the noise vector is corrupted with added independent noise. Similar setup has been considered in [57] . We consider the contrastive loss presented as follows:EQUATIONwhere τ is the temperature parameter, n is the number of training samples, and M is the number of negative pairs. In this work, to efficiently optimize the loss to near zero, we require negative sample pairs do not share the same label, i.e., y j ̸ = y i in (6) . Note that this setting is aligned with supervised contrastive learning [29, 27] .We use gradient descent to optimize the contrastive learning loss, which leads to the gradient update:EQUATIONi )y i µEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONwhere we denoteh(t) r (x) = σ(⟨w (t)r , x⟩), η as the learning rate, and we define the loss derivatives asEQUATIONIntuitively, when the similarity between positive pair is high, and the similarity between negative time is low, we can see ℓ′(t) i ≈ 1 and ℓ ′(t) i,j ≈ 0, for i ∈ [n] and j ∈ [M ].Therefore, the gradient descent in Eq. ( 7) is close to zero, indicating the near convergence result. Furthermore, from Eq. ( 7), we observe that the evolution direction of weight is composed of signal vector µ and noise vectors ξ i for i ∈ [n]. This observation plays a critical role in our following theoretical analysis.We use two neural networks h : R d → R m and g : R d → R m to encode two input modality x and x respectively. Both neural networks use ReLU activation function. More precisely, h(x) = [ h1 (x), . . . , hm (x)] ⊤ ∈ R m , where hr (x) = h r (x (1) ) + h r (x (2) )g( x) = [ḡ 1 ( x), . . . , ḡm ( x)] ⊤ ∈ R m , where ḡr (x) = g r ( x (1) ) + g r ( x (2) )we let h r (x (i) ) = σ(⟨w r , x (i) ⟩) and g r ( x (i) ) = σ(⟨ w r , x (i) ⟩). Here σ(•) is the ReLU activation function, w r ∈ R d and w r ∈ R d for r ∈ [m] are the weights in two networks. Given the embedding, the similarity function of the two modalities is defined as (1) )sg(g r ( x (1) )) + 1 m m r=1 h r (x (2) )sg(g r ( x (2) )), Sim g,h ( x, x) = 1 m m r=1 g r ( x (1) )sg(h r (x (1) )) + 1 m m r=1 g r ( x (2) )sg(h r (x (2) )). The two similarity functions defined above are modality-centered with stop-gradient operation applied. The objective function of contrastive multi-modal learning can be expressed asSim h,g (x, x) = 1 m m r=1 h r (xL = - 1 n n i=1 log( e Sim h,g (xi, xi)/τ e Sim h,g (xi, xi)/τ + M j̸ =i e Sim h,g (xi, xj )/τ ) - 1 n n i=1 log( e Sim g,h ( xi,xi)/τ e Sim g,h ( xi,xi)/τ + M j̸ =i e Sim g,h ( xi,xj )/τ).Same to the single-modal learning whose objective function is governed by Eq. ( 6), the objective function for multi-modal contrastive learning adopt one positive pair and M negative pairs. Besides, we require the negative pairs do not share the same label. To optimize the objective function ( 9) for multi-modal learning, gradient descent is applied to train two encoders simultaneously. The gradient descent rule for the first modal network is governed by the following expression.EQUATIONi )h ′(t) r (x (1) )y i µEQUATIONEQUATIONEQUATIONHere with a slight abuse of notation, we use ℓ′(t) i , ℓ ′(t)i,j to represent the loss derivatives for both modalities. Compared to signal-modal learning, the main difference for the multi-modal learning is that the corresponding embedding is from another modality. The gradient update for the second modality can be derived similarly, which we omit here for clarity.To evaluate the out-of-distribution generalization of single-modal and multi-modal contrastive learning for downstream task, we consider a test distribution D test , where a samplex test = [y • ν ⊤ , ζ ⊤ ] ⊤ ∼ D test is generated as follows. The test signal ν satisfies ⟨ν, µ⟩ = O(∥µ∥ 2 2 d -1/2) and the test noise follows ζ ∼ N (0, σ 2 ξ I) and y follows Rademacher distribution. After the training is complete, we introduce a linear head on top of the learned embedding h(x test ) for adapting to test distribution, i.e., f (x test ) = ⟨w, h(x test )⟩. Specifically, we consider the task of classification and define the population 0-1 test error as L Dtest = P xtest∼Dtest yf (x test ) < 0 . 
main results: 
 In this section, we introduce our key theoretical findings that elucidate the optimization and generalization result for both single-modal and multi-modal contrastive learning through the feature learning analysis. We use a trajectory-based analysis for the iterations induced by gradient descent, following a post-training analysis for the performance on the downstream test set. Below we provide the main assumption and main theorems.Assumption 4.1. Let SNR = ∥µ∥ 2 /(σ ξ √ d). Assume (1) d ≥ Ω(max{n 2 , nσ -1 0 σ -1 ξ , σ -2 0 ∥µ∥ -2 2 }). (2) η ≤ O(min{m∥µ∥ -2 2 , nmσ -2 ξ d -1 }). (3) σ 0 ≤ O((max{σ ξ √ d, ∥µ∥ 2 }) -1 ). (4) m, n ≥ Ω(1). (5) σ ϵ ≤ min{ Θ(∥µ∥ 2 ), σ ξ / Ω(1)}. (6) n • SNR 2 = Θ(1). (7) C µ ∥µ∥ 2 = ∥ µ∥ 2 , where C µ ≥ 2.66 is a constant.(1) We adopt a high dimensional setting to ensure enough over-parameterization. (2, 3) The learning rate and the strength of initialization are chosen to make sure the that gradient descent can effectively minimize the contrastive loss. (4) The choice of hidden size m and number of training sample n is to provide adequate concentration. (5) The strength of augmentation is set to keep the similarity between two positive samples. (6) The relation between number of sample and SNR is to distinguish the feature learning process between single-modal and multi-modal contrastive learning. (7) To differentiate single-modal and multi-modal contrastive learning, we introduce a constant C µ , which enables the cooperation between the two modalities in multi-modal contrastive learning. Theorem 4.2 (Single-Modal Contrastive Learning). Under the single-modal learning setup, suppose Assumption 4.1 holds. Then afterT * = Θ(η -1 mnσ -2 ξ d -1 + η -1 mnσ -2 ξ d -1 ϵ -1), the with probability at least 1 -1/d, it holds that (1) Training error L(T * ) ≤ ϵ and (2) Test error at down-stream task L Dtest (T * ) = Θ(1). Theorem 4.2 states that despite the small training error achieved by single-modal contrastive learning, the test error is large in the downstream task. Theorem 4.3 (Multi-Modal Contrastive Learning). Under the single-modal learning setup, suppose Assumption 4.1 holds. Then afterT * = Θ(η -1 mnσ -2 ξ d -1 + η -1 mnσ -2 ξ d -1 ϵ -1), the with probability at least 1 -1/d, it holds that (1) Training error L(T * ) ≤ ϵ and (2) Test error at down-stream task L Dtest (T * ) = o(1). Theorem 4.3 demonstrates that trained multi-modal contrastive learning can achieve both small training error and downstream test error. Compared to Theorem 4.2, Theorem 4.3 shows that the generalization of multi-modal contrastive learning in downstream tasks is better than single-modal contrastive learning. The reason behind this difference is that the two modalities can cooperate with each other; the higher quality in one modality can boost the feature learning in the target modality, helping to generalize to the downstream task. On the contrary, augmentation often maintains the same SNR as the original data, so single-modal learning hardly benefits from the augmentation and can only memorize the noise from the data, which is not applicable to downstream tasks. 
proof sketch for single modal contrastive learning: 
 The proof is constructed by a optimization analysis followed by a generlization analysis in the downstream task. Through the application of the gradient descent rule outlined in Eq. ( 7), we observe that the gradient descent iterate w (t) r is a linear combination of its random initialization w (0) r , the signal vector µ and the noise vectors in the training data ξ i for i ∈ [n]. Consequently, for r ∈ [m], the decomposition of weight vector iteration can be expressed:EQUATIONwhereγ (t)r and ρ(t)r,i serve as coefficients and represent signal learning and noise memorization respectively. Based on the the gradient descent update (7) , the iteration of γ r,i in decomposition (11) satisfy the following equations:EQUATIONi ) -EQUATIONEQUATIONi )y i ∥µ∥ 2 2 , (12)EQUATIONi ) -EQUATIONEQUATION)where the initialization γEQUATIONr,i = 0.Lemma 5.1 tells how the coefficients evolve under gradient descent update. In the following, we introduce a two-stage dynamics to characterize the whole training process based on Eq 12 and Eq 13.First Stage: Exponential growth. During the first stage, we show before γ(t) r or ρ (t)r,i grow to Θ(1), the embedding (3) is close to zero, suggesting the similarity is bounded by 1 ≤ Sim h (x, x ′ ) ≤ C ℓ for some constant C ℓ > 1. The loss derivatives defined in (8) can thus be bounded within some constant range.Signal learning. According to the update for signal learning in (12) , we see the propagation can be simplified based on the hard-negative sampling strategy, i.e., the negative pairs do not share the same labels. This suggests the negative term is always zero as n i=1 M j:yj ̸ =yi σ(⟨w (t) r , y j µ⟩)σ ′ (⟨w (t) r , y i µ⟩) = 0. The resulting update of γ (t) r reduces to γ (t+1) r = γ (t) r + η nmτ n i=1 (1 -ℓ ′(t) i )σ(⟨w (t) r , y i µ⟩)σ ′ (⟨w (t)U (t) -= U (0)-for all t ≥ 0. Noise memorization. Compared to signal learning, the behaviour of noise memorization requires more detailed analysis. This is mainly because the negative pairs can not be eliminated simply based on label difference, as the noise patch ξ i is generated independent of label y i . In addition, the added noise ϵ i by augmentation can also contribute to the noise dynamics. We first show when the noise level σ ϵ is much smaller compared to σ ξ , the dynamics of noise memorization is largely remains unaffected. By the sign of ⟨w (t) r , ξ i ⟩, we partition the samples into two sets, i.e., IEQUATIONI (t) r,-= {i : ⟨w (t) r , ξ i ⟩ < 0}. We can verify for i ∈ I (0) r,-, the value of ρ (t)r,i stays at zero based on the update (13) with an induction argument. For samples i ∈ I (0) r,+ with positive initialization, we analyze the noise memorization based on the joint dynamics of samples with the same label. In particular, we define total noise memorization of positive and negative samples respectively asB (t) r,+ ≜ i:yi=1 (ρ (t) r,i + ⟨w (0) r , ξ i ⟩)1 i∈I (t) r,+ and B (t) r,-≜ i:yi=-1 (ρ (t) r,i + ⟨w (0) r , ξ i ⟩)1 (t)i∈Ir,+ . The update of ρ B (t+1) r,+ ≈ B (t) r,+ + ησ 2 ξ d nmτ B (t) r,+ - 1 2 B (t) r,-, B (t+1) r,- ≈ B (t) r,-+ ησ 2 ξ d nmτ B (t) r,-- 1 2 B (t) r,+ ,where the coefficient of 1/2 appears as a result of the randomness of the sign of initialization. This result suggests, individual ρ(t)r,i:yi=1 cannot grow too slow compared to the ρ(t)r,i:yi=-1 . Following a similar induction argument, we are able to show ρ (t) r,i:yi=1 has an exponential growth lower bound. On the other hand, for samples with y i = -1 but with different neuron, we can use the same strategy to show an exponential growth lower bound for some neurons that satisfy the initialization conditions. Lemma 5.2. Under the Assumption 4.1, let T 1 = log 20/(σ 0 σ ξ √ d) / log 1 + 0.96ησ 2 ξ d nmτ , we have γ (t) r = O(1/ √ n) for all r ∈ [m] and 0 ≤ t ≤ T 1 and max r ρ (T1) r,i = Ω(1) for all i ∈ [n].Second stage: convergence and scale difference. At the end of first stage, the noise grows to a constant order while signal learning remains negligible. As a result, the loss derivatives are no longer bounded within some constant range. In the second stage, we aim to show the loss is able to converge to an arbitrarily small value ϵ. Despite the unsupervised learning setup, we are still able to show loss convergence thanks to the hard negative samples. Let F 0 (W, x i ) = Sim(x i , x i ) be the similarity to the argumentation and F j (W, x i ) = Sim(x i , x j ) for j = 1, ..., M be the similarity between the negative pairs. Then we can show there exists some W * such that ⟨∇F 0 (W (t) , x i ), W * ⟩ ≥ 2 log(2M/ϵ) while ⟨∇F j (W (t) , x i ), W * ⟩ ≤ log(2M/ϵ) for all j = 1, ..., M . Then we can bound ⟨∇L S (W (t) ),W (t) -W * ⟩ ≥ 1 n n i=1 L i (W (t) ) -ϵ/2. This as a result allows to show a monotonic decrease in the loss function as L(W (t) ) ≤ 1 η (∥W (t) -W * ∥ 2 F -∥W (t+1) -W * ∥ 2 F ) + ϵ which guarantees convergence by telescoping over the inequality. Upon the convergence, we can also show the scale difference obtained at the end of the first stage is maintained, i.e., γ(t) r = O(1/ √ n) while max r ρ (T1) r,i= Ω(1) for all i ∈ [n]. This suggests the non-linearly separability for the resulting embeddings and thus the downstream test error is non-vanishing. The formal convergence result is established in Lemma C. 18 . Combined with the generalization error demonstrated in Appendix C.3, this completes the proof of Theorem 4.2.Similar to single-modal contrastive learning, we decompose the decomposition of weight vector iteration for the network in the second modality and subsequently provide a two-stage analysis.EQUATIONwhereγ (t)r and ρ(t)r,i serve as coefficients for the weight decomposition in the text modal.Lemma 5.3 (Multi-Modal). The coefficients γ (t) r , ρ (t) r,i , γ (t) r , ρ (t)r,i in decomposition (11) satisfyEQUATIONEQUATIONEQUATIONEQUATIONwhere the initialization satisfy γEQUATIONEQUATIONEQUATIONr,i = 0First Stage: Exponential growth The first stage of multi-modal learning shares similar characteristics as single-modal learning.For signal learning, we analyze the trajectories for both γ(t)r and γ (t) r . To this end, we partition the neurons depending on their initialization status. Apart from U (t) + and U (t) defined in the single-modal learning, we additionally defineU (t) + ≜ {r : ⟨ w (t) r , µ⟩ > 0}, U (t) -≜ {r : ⟨ w (t)r , µ⟩ < 0} for the other modality. Then for r ∈ U(0) + ∩ U (0) + , we can show γ (t) r ≥ 0, ϕ (t)r ≥ 0 and are increasing. For neurons r ∈ U(t) -∩ U (t) -, we can show γ (t) r ≤ 0, γ (t)r ≤ 0 and are decreasing. Furthermore, the sign of inner product stays invariant, i.e., U(t) + ∩ U (t) + = U (0) + ∩ U (0) + and U (t) -∩ U (t) -= U (0) -∩ U (0)-. For neurons with only one of the modalities activated initially, i.e., r ∈ U(0) + ∩ U (0) -or r ∈ U (0) -∩ U (0)+ , we can show there exists some time t ′ ≥ 0 such that the neurons are either positively or negatively activated with r ∈ U(t ′ ) + ∩ U (t ′ ) + and r ∈ U (t ′ ) -∩ U (t ′ ) -.This shows synchronization of the signal learning patterns of two modalities. The pre-synchronization phase reduces the speed of learning and thus we can only focus on neurons with the same sign for the initialization in order to decide the lower and upper bound.Noise memorization. For noise memorization, we partition the samples into two sets for both modalities according to the initialization, namely,I (t) r,+ = {i : ⟨w (t) r , ξ i ⟩ > 0}, I (t) r,-= {i : ⟨w (t)r , ξ i ⟩ < 0}, and similarly for the second modalityI (t) r,+ , I (t)r,-. Because the noise memorization are correlated in the two modalities, we separately analyze the samples as follows.(1) For i ∈ I r,+ , without loss of generality, we consider upper bounding noise memorization for the first modality and y i = 1. To this end, we first define the individual and joint noise memorization for the first modality as(0) r,-∩ I (0) r,-, we can show ρ (t) r,i = 0, I (t) r,-= I (0) r,-and ρ (t) r,i = 0, I (t) r,-= I (0) r,-. (2) For i ∈ I (0) r,-∩ I (0) r,+ , we can show ρ (t) r,i = 0, I (t) r,-= I (0) r,-and ρ (t) r,i ≤ 0. (3) For i ∈ I (0) r,+ ∩ I (0) r,-, we can show ρ (t) r,i = 0, I (t) r,-= I (0) r,-and ρ (t) r,i ≤ 0.Ψ (t) r,i ≜ ρ (t) r,i + ⟨w (0) r , ξ i ⟩, and B (t) r,+,+ ≜ i:yi=1 (ρ (t) r,i + ⟨w (0) r , ξ i ⟩)1 i∈I (t) r,+ ∩ I (t) r,+ , B (t) r,+,-≜ i:yi=1 (ρ (t) r,i +⟨w (0) r , ξ i ⟩)1 i∈I (t) r,+ ∩ I (t) r,-. Similar definitions exist for the other modality. The joint dynamics of noise memorization can be first upper bounded by the other modality asΨ (t) r,i ≥ 101C ℓ M +1 (B (t) r,+,+ + B (t)r,+,-). Then we can upper bound the individual noise memorization byΨ (t) r,i ≤ (1 + 1.06ησ 2 ξ d nmτ ) t (Ψ (0) r,i + Ψ (0) r,i ).We show the combined dynamics of γ(t)r and ρ(t)r exhibits exponential growth while the magnitude of their difference shrinks exponentially. The results are summarized as follows Lemma 5.4. Under the Assumption 4.1, letT 1 = log 20/(σ 0 ∥µ∥ 2 ) / log 1 + 0.48C µ η∥µ∥ 2 2 mτ , we have ρ (T1) r,i = O(1/ √ n) for all r ∈ [m], i ∈ [n], and 0 ≤ t ≤ T 1 and max r γ (T1) r= Ω(1).Second Stage: Convergence and scale difference. The second stage presents similar patterns compared to single-modal learning. Thanks to the correlation between the two modality during gradient descent training, the two neural network converge at the same time, minimizing the training loss. Besides, The scale difference at the end of the first stage is carried over throughout the second stage until convergence. Therefore, it allows to show a monotonic decrease in the loss function asL(W (t) , W (t) ) ≤ ∥W (t) -W * ∥ 2 F + ∥ W (t) -W * ∥ 2 F -∥W (t+1) -W * ∥ 2 F -∥ W (t+1) - W * ∥ 2F + 2ϵ, which guarantees convergence by telescoping over the inequality. At the same time, until convergence, we can show the scale difference obtained at the end of the first stage is maintained, namely max r,i ρ(t) r,i = O(1/ √ n) and max r γ (t) r = Ω(1). This suggests the signal learning dominates the noise memorization and thus the resulting embeddings are linearly separable, which guarantees a small test error for downstream tasks. The formal convergence result is established in Lemma D. 15 . Combined with the generalization error demonstrated in Appendix D.3, this completes the proof of Theorem 4.3. 
experiments: 
 Synthetic experiments We conduct synthetic experiments to verify the theoretical results obtained in the previous sections. We generate samples following the theoretical setups, where we set the data dimension d = 2000, number of training samples n = 100, number of test samples n test = 200, and the hidden size of all encoders as m = 50. We adopt gradient descent with a learning rate of 0.01 as the optimizer to train the model by 200 epochs. In the single-modal setting, the µ is set to be [5, 0, ..., 0] T and the ξ ∼ N (0, I) for the in-distribution data, and the augmentation vector ϵ ∼ N (0, 0.01 * I). For the multi-modal setting, μ = [0, 15, 0, ..., 0] T . In addition, for the OOD test data x test = [ν ⊤ , ζ ⊤ ] ⊤ , we set ν = [2, 0, ..., 0] and ζ ∼ N (0, I). We perform logistic regression based on the learned features h(x test ) and apply the learned classifier head to evaluate OOD generalization error in terms of prediction accuracy.In Figure 1 , we see the training loss of both single-modal and multi-modal learning converges rapidly. At the same time, OOD test accuracy of multi-modal learning converges to nearly 1.0 while that of single-modal learning stagnates around 0.5. This is primarily because under the setup where the other modality μ has a higher SNR, signal learning of µ is lifted. This can be verified from the third plot of Figure 1 , where the signal learning of multi-modal framework is significantly higher than single-modal. Further, it can be observed that single-modal contrastive learning exhibits more severe noise memorization, which suppresses signal learning. In contrast, multi-modal contrastive learning exhibits less severe noise memorization which would further encourage signal learning. These phenomena again support and align with our theoretical results.We now extend the comparison of single-modal and multi-modal learning to realistic image data, ColoredMNIST [3, 54] , which is a typical benchmark studying the generalization capability under distribution shifts. The ColoredMNIST dataset is a variation of the standard MNIST dataset, where each digit is assigned a specific color based on its label. The two modalities are image, and text that describes the images. The task is a 10-class classification that recognizes the number of the colored MNIST images. Specifically, we have 10 colors to color 10 digits, and introduce spurious correlations via label noises following the literature:• For the training set, 10% of labels will be clipped to a random class. For images with class '0' (or '1'), they will be colored as red (or green) with a probability of 77.5%, and as another random color with a probability of 22.5%. The coloring scheme introduces a spurious correlation. • For the test set, 10% of labels will be clipped to a random class. For images with class '0' (or '1'), they will be colored as green (or red) with a probability of 77.5%, and as another random color with a probability of 22.5%. The coloring scheme can be considered as reversing the training spurious correlations. Therefore, the evaluation on test set can reflect to what extent the model learns to use the spurious features, i.e., colors, to classify images.We implement the multi-modal learning following the practice in [54] , where we consider an ideal language encoder that successfully encodes the caption of the images into onehot labels of colors and digits. For single-modal learning, we follow the implementation of the SimCLR [9] to construct a set of augmentations to learn the representations. Results. Under the distribution shift, we verify that multi-modal learning archives an out-of-distribution test accuracy of 82.13%, which outperforms that of singlemodal learning 12.68%. As a result, we can claim that the effective SNR of invariant features (the shape of the digit) will be degraded under the impact of the injected color. Therefore, the performance of single-modal may be suboptimal as it cannot effectively utilize the information of the digit's shape. On the other hand, multi-modal demonstrates a better capacity for handling this scenario. 
conclusions: 
 In this work, we have established a comprehensive comparison of the optimization differences during the pre-training stage and the generalization gap between single-modal and multi-modal contrastive learning for downstream tasks. With the cooperation between modalities, multi-modal contrastive learning can achieve better feature learning and generalization on downstream tasks compared to single-modal learning. On the other hand, data augmentation alone can hardly improve data quality and thus cannot boost the performance of single-modal contrastive learning. Together, these results quantitatively demonstrate the superiority of multi-modal learning over single-modal learning and emphasize the importance of data quality in multi-modal contrastive learning. 
 
 Appendix: While our theoretical analysis is novel in terms of optimization and generalization, the data model can be further modified to be more practical. Our theoretical analysis may be further used for empirical and theoretical studies of contrastive learning, especially multi-modal contrastive learning. However, we do not foresee a direct social impact from our theory.Before the proof, we introduce lemmas that are useful in proving our main theorem.Lemma B.1. Let x ∼ N (0, σ 2 ). Then P(|x| ≤ c) = 2erf c √ 2σ ≤ 2 1 -exp(-2c 2 σ 2 π ).Proof. The probability density function for x is given byf (x) = 1 √ 2πσ exp - x 2 2σ 2 .Then we know thatP(|x| ≤ c) = 1 √ 2πσ c -c exp - x 2 2σ 2 dx.By the definition of erf functionerf(c) = 2 √ π c 0 exp(-x 2 )dx,and variable substitution yieldserf c √ 2σ = 1 √ 2πσ c 0 exp - x 2 2σ 2 dx.Therefore, we first concludeP(|x| ≤ c) = 2erf c √ 2σ .Next, by the inequality erf(x) ≤ 1 -exp(-4x 2 /π), we finally obtainP(|x| ≤ c) ≤ 2 1 -exp - 2c 2 σ 2 π .Lemma B.1 introduces an anti-concentration result. In later sections, this lemma will be used to show that with a relatively large initialization for the weight vector, some initial properties hold.EQUATION)) , then with probability at least 1 -δ, we can show for all r ∈ [m],|⟨w (0) r , µ⟩| ≥ 100 • SNR 8 log(6n/δ) d n, |⟨ w (0) r , µ⟩| ≥ 100 • SNR 8 log(6n/δ) d n.Proof of Lemma B.2. By Lemma B.1, because ⟨w(0)r , µ⟩ ∼ N (0, σ 2 0 ∥µ∥ 2 2 ), we can showP |⟨w (0) r , µ⟩| ≤ c ≤ 2 1 -exp - 2c 2 σ 2 0 ∥µ∥ 2 2 π . Let c = 100 • SNR 8 log(6n/δ) d n = 100n∥µ∥ 2 σ -1 ξ d -18 log(6n/δ) and plug it into the RHS of the above inequality, which becomes:RHS = 2 1 -exp - 160000 log(6n/δ)n 2 σ 2 0 σ 2 ξ d 2 π.Then we can verify that when d satisfies that d ≥ 400nσ0σ ξ log(6n/δ) -π log(1-δ 2 /(4m 2 )), it holds that RHS ≤ δ/m. This suggests for a single neuron r ∈ [m], we have P(|⟨w(0) r , µ⟩| ≤ c) ≤ δ/m.Applying union bound, we can show the desired result.Similarly, with the same procedure, we can prove the result for the other modality.|⟨ w (0) r , µ⟩| ≥ 100 • SNR 8 log(6n/δ) d n. Lemma B.3 ([31]). Let S 1 = {i ∈ [n] : y i = 1} and S -1 = {i ∈ [n] : y i = -1}.Then with probability at least 1 -δ,|S 1 |, |S -1 | ∈ n 2 - n 2 log(4/δ), n 2 + n 2 log(4/δ) .Lemma B.3 states that when the label is randomly sampled, the number of positive samples and negative samples is close to n 2 , adequately. Lemma B. 4 ([8] ). Suppose that d ≥ Ω(log(mn/δ)), m = Ω(log(1/δ)). Then with probability at least 1 -δ, it satisfies that for all r ∈[m], i ∈ [n], |⟨w (0) r , µ⟩| ≤ 2 log(8m/δ)σ 0 ∥µ∥ 2 |⟨w (0) r , ξ i ⟩| ≤ 2 log(8mn/δ)σ 0 σ ξ √ d |⟨w 0 r , ϵ i ⟩| ≤ 2 log(8mn/δ)σ 0 σ ϵ √ d.and for all i ∈ [n]σ 0 ∥µ∥ 2 /2 ≤ max r∈[m] ⟨w (0) r , µ⟩ ≤ 2 log(8m/δ)σ 0 ∥µ∥ 2 σ 0 σ ξ √ d/4 ≤ max r∈[m] ⟨w (0) r , ξ i ⟩ ≤ 2 log(8mn/δ)σ 0 σ ξ √ d.). Suppose that δ > 0 and d = Ω(log(6n/δ))). Then with probability 1 -δ,σ 2 ξ d/2 ≤ ∥ξ i ∥ 2 2 ≤ 3σ 2 ξ d/2, |⟨ξ i , ξ i ′ ⟩| ≤ 2σ 2 ξ d log(6n 2 /δ) |⟨ξ i , µ⟩| ≤ ∥µ∥ 2 σ ξ 2 log(6n/δ) σ 2 ϵ d/2 ≤ ∥ϵ i ∥ 2 2 ≤ 3σ 2 ϵ d/2, |⟨ϵ i , ξ i ′ ⟩| ≤ 2σ ϵ σ ξ d log(6n 2 /δ) |⟨ϵ i , µ⟩| ≤ ∥µ∥ 2 σ ϵ 2 log(6n/δ) for all i, i ′ ∈ [n].C Single-modal Contrastive Learning: Proof of Theorem 4.2In this section, we provide the proof for Theorem 4.2, which states main results of single modal learning. The training dynamics are based on the coefficient iterations presented in Lemma 5.1. Below, we provide a proof for this lemma:Proof of Lemma 5.1. Recall that the weight decomposition is expressed asw (t) r = w (0) r + γ (t) r ∥µ∥ -2 2 µ + n i=1 ρ (t) r,i ∥ξ i ∥ -2 2 ξ i .We plug it into the gradient descent update as described by Equation 10yieldsEQUATIONi )y i µEQUATIONEQUATIONEQUATIONEQUATIONi )ξ i .By comparing the coefficients in front of µ and ξ i on both sides of the equation, we can obtainEQUATIONi ) -EQUATIONEQUATIONEQUATIONi ) -EQUATIONEQUATIONi )∥ξ i ∥ 2 2 ,which completes the proof.According to the behavior of the defined loss derivative (8), we split the entire training dynamics into two phases. In the first stage, the loss derivative remains close to its initial value as the similarity is small from initialization. Later, as the similarity grows to a constant value, the loss derivative is no longer close to the initial value, and the dynamics transition to the second stage. In this stage, the similarity increases logarithmically, and the empirical loss converges.In the first stage, the derivative of the loss is close to its initial value because the similarity is small. Below, we provide a useful lemma for establishing such a result.Lemma C.1. Suppose that γ(t) r = O(1) and ρ (t) r,i = O(1) for all r ∈ [m] and i ∈ [n]. Under Assumption 4.1, then for any δ > 0, with probability at least 1 -δ|⟨w (t) r -w (0) r , ξ i ⟩ -ρ (t) r,i | ≤ 5 log(6n 2 /δ) d n |⟨w (t) r -w (0) r , µ⟩ -γ (t) r | ≤ SNR 8 log(6n/δ) d n for all r ∈ [m], i ∈ [n].Proof of Lemma C.1. From the signal-noise decomposition of w(t)r , we derive|⟨w (t) r -w (0) r , ξ i ⟩ -ρ (t) r,i | (a) = |γ (t) r ⟨µ, ξ i ⟩∥µ∥ -2 2 + n i ′ =1 ρ (t) r,i ⟨ξ i ′ , ξ i ⟩∥ξ i ′ ∥ -2 2 | (b) ≤ ∥µ∥ -1 2 σ ξ 2 log(6n/δ) + 4 log(6n 2 /δ) d n (c) ≤ 5 log(6n 2 /δ) d n.Equation (a) results from the weight decomposition (see Equation 11). In the first stage, we used the upper bounds for |γ Further,|⟨w (t) r -w (0) r , µ⟩ -γ (t) r | = | n i=1 ρ (t) r,i ∥ξ i ∥ -2 2 ⟨ξ i , µ⟩| ≤ 2n • SNR 2 log(6n/δ) d ,where we have used Lemma B.5. Now, we proceed to the lemma concerning the derivative of the loss as follows:EQUATIONr,i } = O(1) and under Assumption 4.1, there exists a constantC ℓ > 1 such that 1 C ℓ (1 + M ) ≤ ℓ ′(t) i ≤ C ℓ 1 + M , 1 C ℓ (M + 1) ≤ ℓ ′(t) i,j ≤ C ℓ 1 + M , for all i ∈ [n].Proof of Lemma C.2. From the update of w(t)r , we have|⟨w (t) r , ξ i ⟩| (a) ≤ |⟨w (0) r , ξ i ⟩| + ρ (t) r,i + 5 log(6n 2 /δ) d n (b) ≤ 2 log(8mn/δ)σ 0 σ ξ √ d + ρ (t) r,i + 5 log(6n 2 /δ) d n (c) = O(1),where r,i } = O(1). At the same time,EQUATION≤ |⟨w (0) r , µ⟩| + γ (t) r + SNR (t) r , ρ (t) r,i } = O(1). Besides, |⟨w (t) r , ϵ i ⟩| = |⟨w (0) r , ϵ i ⟩ + γ (t) r ∥µ∥ -2 2 ⟨µ, ϵ i ⟩ + n i=i ρ (t) r,i ∥ξ i ∥ -2 2 ⟨ξ i , ϵ i ⟩| (a) ≤ |⟨w (0) r , ϵ i ⟩| + ∥µ∥ -1 2 σ ϵ 2 log(6n/δ) + 4 log(6n 2 /δ) d σ ϵ σ -1 ξ n (b) ≤ 2 log(8mn/δ)σ 0 σ ϵ √ d + ∥µ∥ -1 2 σ ϵ 2 log(6n/δ) + 4 log(6n 2 /δ) d σ ϵ σ -1 ξ n (c) = O(1),where (a) follows from Lemma B.5, (b) from Lemma B.4, and (c) from the conditions σ 0 ≤1 2 √ log(8mn/δ)σϵ √ d , σ ϵ ≤ ∥µ∥2 √ 2 log(6n/δ), d > n 2 log(6n 2 /δ), and σ ϵ < σ ξ .Next, we calculate the upper bound of the similarity measure. First, we examine the negative pair.For any i, j ∈ [n], we haveEQUATIONi ), sg(h(xEQUATIONi ), sg(h(x(2) j ))⟩ = 1 m m r=1 σ(⟨w (t) r , ξ i ⟩)σ(⟨w (t) r , ξ j ⟩) + 1 m m r=1σ(⟨w (t) r , y i µ⟩)σ(⟨w (t) r , y j µ⟩)≤ max{|⟨w (t) r , y i µ⟩⟨w (t) r , y j µ⟩|, |⟨w (t) r , ξ i ⟩⟨w (t) r , ξ j ⟩|} = O(1).Similarly, for positive pair,Sim h (x i , x j ) = 1 m m r=1 σ(⟨w (t) r , ξ i ⟩)σ(⟨w (t) r , ξ i + ϵ i ⟩) + 1 m m r=1 σ(⟨w (t) r , y i µ⟩)σ(⟨w (t) r , y i µ⟩) ≤ max{|⟨w (t) r , y i µ⟩⟨w (t) r , y j µ⟩|, |⟨w (t) r , ξ i ⟩⟨w (t) r , ξ i + ϵ i ⟩|} = O(1).According to the above result, we can say that 1 ≤ e Sim h (x,x ′ ) ≤ C ℓ , where C ℓ is a positive constant.Then we can provide the upper bound for ℓ ′ i andℓ ′ i,j ℓ ′(t) i = e Sim h (xi, xi)/τ e Sim h (xi, xi)/τ + M j̸ =i e Sim h (xi,xj )/τ ≤ C ℓ 1 + M , ℓ ′(t) i = e Sim h (xi, xi)/τ e Sim h (xi, xi)/τ + M j̸ =i e Sim h (xi,xj )/τ ≥ 1 C ℓ (1 + M ) , ℓ ′(t) i,j = e Sim h (xi,xj )/τ e Sim h (xi, xi)/τ + M j̸ =i e Sim h (xi,xj )/τ ≥ 1 C ℓ (M + 1) , ℓ ′(t) i,j = e Sim h (xi,xj )/τ e Sim h (xi, xi)/τ + M j̸ =i e Sim h (xi,xj )/τ ≤ C ℓ M + 1 .This completes the proof.In the first stage, the growth rate of signal learning is exponential. We establish an upper bound for the growth of signal learning.Then we consider the growth of signal learning coefficient γ Proof of Lemma C.3. We prove the claims by induction. To better understand the dynamics, we first derive the propagation for signal learning from the first step. For r ∈ U (0) + , i.e., ⟨w (0) r , µ⟩ > 0, we can seeγ (1) r = γ (0) r + η nmτ n i=1 (1 -ℓ ′(0) i )σ(⟨w (0) r , y i µ⟩)σ ′ (⟨w (0) r , y i µ⟩)y i ∥µ∥ 2 2 - η nmτ n i=1 M j̸ =i ℓ ′(0) i,j σ(⟨w (0) r , y j µ⟩)σ ′ (⟨w (0) r , y i µ⟩)y i ∥µ∥ 2 2 = γ (0) r + η nmτ n i:yi=1 (1 -ℓ ′(0) i )σ(⟨w (0) r , y i µ⟩)σ ′ (⟨w (0) r , y i µ⟩)y i ∥µ∥ 2 2 - η nmτ n i:yi=1 M j:yj =-1 ℓ ′(0) i,j σ(⟨w (0) r , y j µ⟩)σ ′ (⟨w (0) r , y i µ⟩)y i ∥µ∥ 2 2 = η nmτ n i:yi=1 (1 -ℓ ′(0) i )⟨w (0) r , µ⟩∥µ∥ 2 2 > 0,where last equality is by ⟨wEQUATIONr = 0, and the fact that negative samples satisfy y j ̸ = y i . Thus, we verify that the sign of γ Next, we show the propagation of inner product at t = 1, for r ∈ U (0) + , we have ⟨w (1) r , µ⟩≥ ⟨w (0) r , µ⟩ + γ (1) r -SNR8 log(6n/δ) d n (b) ≥ 0.99⟨w (0) r , µ⟩ + γ (1) r > 0,where inequality (a) is by Lemma C.1, the second inequality (b) is by Lemma B.2, and the last by γr > 0. Hence we verify UEQUATIONNow suppose at iteration t, the claims are satisfied, namely ⟨w(t)r , µ⟩ > 0 and γ(t) r ≥ γ (t-1) r ≥ 0 for r ∈ U (0) + . Then following similar argument, for r ∈ U (0) + γ (t+1) r = γ (t) r + η nmτ n i:yi=1 (1 -ℓ ′(t) i )⟨w (t) r , µ⟩∥µ∥ 2 2 ≥ γ (t) r ≥ 0,where we use the induction condition that ⟨w ⟨w (t+1) r , µ⟩ ≥ 0.99⟨w (0) r , µ⟩ + γ (t+1) r > 0,where we use γ (t+1) r ≥ 0. This completes the induction for r ∈ U+ .Similarly, for those neuron r that satisfies ⟨w 0 r , µ⟩ < 0, i.e., r ∈ U (0)-, we haveγ (1) r = γ (0) r + η nmτ n i=1 (1 -ℓ ′(0) i )σ(⟨w (0) r , y i µ⟩)σ ′ (⟨w (0) r , y i µ⟩)y i ∥µ∥ 2 2 - η nmτ n i=1 M j̸ =i ℓ ′(0) i,j σ(⟨w (0) r , y j µ⟩)σ ′ (⟨w (0) r , y i µ⟩)y i ∥µ∥ 2 2 = - η nmτ n i:yi=-1 (1 -ℓ ′(0) i )⟨w (0) r , y i µ⟩∥µ∥ 2 2 < 0,where the last equality is by ⟨w(0)r , µ⟩ < 0, y i = -1, the property of ReLU activation, and the fact that y j ̸ = y i in the negative pair term. Hence we see γ(1) r ≤ γ (0) r = 0.Similarly, for the inner product at t = 1, ⟨w (1) r , µ⟩ = ⟨w (0) r , µ⟩ + γ(1) r + n i=1 ρ (t) r,i ∥ξ i ∥ -2 2 ⟨ξ i , µ⟩ ≤ ⟨w (0) r , µ⟩ + γ (1) r + SNR 8 log(6n/δ) d n ≤ -0.99|⟨w (0) r , µ⟩| + γ (1) r < 0,where the first inequity is by Lemma C.1, the second inequality follows from Lemma B.2, and the last inequality follows from γ(1)r ≤ 0.Now suppose at iteration t, the claims are satisfied, namely ⟨w(t)r , µ⟩ < 0 and γ(t) r ≤ γ (t-1) r ≤ 0 for r ∈ U (0) + . Then following similar argument, for r ∈ U (0) - γ (t+1) r = γ (t) r - η nmτ n i:yi=-1 (1 -ℓ ′(t) i )⟨w (t) r , µ⟩∥µ∥ 2 2 ≤ γ (t) r ≤ 0,where we use the induction condition that ⟨wEQUATION≤ ⟨w (0) r , µ⟩ + γ (t+1)r + SNR 8 log(6n/δ) d n (b) < 0,where inequality (a) follows from Lemma C.1; we use γ A (t) r = -γ (t) r -⟨w (0) r , µ⟩ for r ∈ U (0)-. With probability at least 1 -δ, we haveA (t) r ≤ 1 + 0.52η∥µ∥ 2 2 mτ A (0) r .Proof EQUATIONwhere we use Lemma B.2 and γ (t)r ≥ 0.Then, the update equation for γ(t) r follows γ (t+1) r = γ (t) r + η nmτ n i:yi=1 (1 -ℓ ′(t) i )⟨w (t) r , µ⟩∥µ∥ 2 2 .Then we find thatEQUATIONwhere the first inequality (a) is by (19) and Lemma C.2. The second inequality (b) is by Lemma B.3 and 1 -1 C ℓ (M +1) < 1.The last inequality (c) is by the condition n ≥ 2500 log(4/δ).To establish the lower bound of noise memorization in the first stage, we require that the added noise level σ ϵ ≤ σ ξ /C ′ for sufficiently large, with C ′ ≥ Ω(1). We prove the following result that upper bound the scale of ⟨w(t)r , ϵ i ⟩. Lemma C.5. Under the same condition as Lemma C.1 and d = Ω(max{σ -2 0 ∥µ∥ -2 2 , nσ -1 0 σ -1 ξ }), there exists a sufficiently large constant C ξ > 0 such that|⟨w (0) r , ξ i ⟩| ≥ C ξ |⟨w (t) r , ϵ i ⟩| for all i ∈ [n].Proof of Lemma C.5. According to the decomposition of w (t) r , we can show |⟨w (t) r , ϵ i ⟩| = |⟨w (0) r , ϵ i ⟩ + γ (t) r ∥µ∥ -2 2 ⟨µ, ϵ i ⟩ + n i ′ =1 ρ (t) r,i ′ ∥ξ i ′ ∥ -2 2 ⟨ξ i ′ , ϵ i ⟩| ≤ |⟨w (0) r , ϵ i ⟩| + γ (t) r ∥µ∥ -2 2 |⟨µ, ϵ i ⟩| + n i ′ =1 |ρ (t) r,i |∥ξ i ′ ∥ -2 2 |⟨ξ i ′ , ϵ i ⟩| (a) ≤ 2 log(8mn)/δσ 0 σ ϵ √ d + ∥µ∥ -1 2 σ ϵ 2 log(6n/δ) + 4σ ϵ σ -1 ξ log(6n 2 /δ) d n ≤ 1/C|⟨w (0) r , ξ i ⟩|,P |⟨w (0) r , ξ i ⟩| ≤ c ≤ 2 1 -exp - 2c 2 πσ 2 0 σ 2 ξ d , When d ≥ 2c 2 -log(1-δ 2 /(4n 2 ))πσ 2 0 σ 2 ξ , we have P |⟨w (0)r , ξ i ⟩| ≤ c ≤ δ/n and by union bound, we have with probability at least 1-δ, it holds |⟨w(0) r , ξ i ⟩| > c. Here we let c = C 2 log(8mn)/δσ 0 σ ϵ √ d+ ∥µ∥ -1 2 σ ϵ 2 log(6n/δ) + 4σ ϵ σ -1 ξ log(6n 2 /δ) d n ≥ C|⟨w (t)r , ϵ i ⟩|. Then we can show the desired result with the condition d = Ω(max{σ-2 0 ∥µ∥ -2 2 , nσ -1 0 σ -1 ξ }).Define that We then show that neurons with negative inner products with the noise at initialization would stay negative and the corresponding ρ stays zero. Lemma C.7. Under the same condition as Lemma C.1 and Lemma C.6, for all t > 0, we haveI (t) r,+ = {i : ⟨w (t) r , ξ i ⟩ > 0} and I (t) r,-= {i : ⟨w (t) r , ξ i ⟩ < 0}.I (t) r,-= I (0)r,-and ρ(t) r,i = 0 for all i ∈ I (0) r,-.Proof of Lemma C.7. The proof is by induction. We first consider i ∈ IEQUATIONr,i = ρ (0) r,i + η nmτ (1 -ℓ ′(0) i )σ(⟨w (0) r , ξ i + ϵ i ⟩)σ ′ (⟨w (0) r , ξ i ⟩)∥ξ i ∥ 2 2 - η nmτ M j̸ =i ℓ ′(0) i,j σ(⟨w (0) r , ξ j ⟩)σ ′ (⟨w (0) r , ξ i ⟩)∥ξ i ∥ 2 2 = 0,where we have used the condition that ⟨w(0)r , ξ i ⟩ < 0 and the property of ReLU activation. Next we consider ⟨w (1) r ,EQUATIONr,i ∥ξ i ∥ -2 2 ξ i , ξ i ⟩ = ⟨w (0) r , ξ i ⟩ + γ (1) r ⟨µ, ξ i ⟩∥µ∥ -2 2 + ρ (1) r,i + n i ′ ̸ =i ρ (1) r,i ′ ∥ξ i ′ ∥ -2 2 ⟨ξ i ′ , ξ i ⟩ (a) ≤ ⟨w (0) r , ξ i ⟩ + 5 log(6n 2 /δ) d n (b) < 0,where inequality (a) is by Lemma C.1 and ρr,i = 0, and inequality (b) is by Lemma C.6.Suppose at iteration t, the claim is satisfied, i.e., ⟨wEQUATIONr,i = 0, for all i ∈ I (0) r,-. Thenρ (t+1) r,i = ρ (t) r,i + η nmτ (1 -ℓ ′(t) i )σ(⟨w (t) r , ξ i + ϵ i ⟩)σ ′ (⟨w (t) r , ξ i ⟩)∥ξ i ∥ 2 2 - η nmτ M j̸ =i ℓ ′(t) i,j σ(⟨w (t) r , ξ j ⟩)σ ′ (⟨w (t) r , ξ i ⟩)∥ξ i ∥ 2 2 < 0,Next we consider the update of inner product as⟨w (t+1) r , ξ i ⟩ = ⟨w (0) r + γ (t+1) r µ∥µ∥ -2 2 + n i=1 ρ (t+1) r,i ∥ξ i ∥ -2 2 ξ i , ξ i ⟩ = ⟨w (0) r , ξ i ⟩ + γ (t+1) r ⟨µ, ξ i ⟩∥µ∥ -2 2 + ρ (t+1) r,i + n i ′ ̸ =i ρ (t+1) r,i ′ ∥ξ i ′ ∥ -2 2 ⟨ξ i ′ , ξ i ⟩ ≤ ⟨w (0) r , ξ i ⟩ + γ (t+1) r |⟨µ, ξ i ⟩|∥µ∥ -2 2 + n i ′ ̸ =i |ρ (t+1) r,i ′ |∥ξ i ′ ∥ -2 2 |⟨ξ i ′ , ξ i ⟩| ≤ ⟨w (0) r , ξ i ⟩ + 5 log(6n 2 /δ) d n < 0,where the last inequality is by a anti-concentration analysis shown in Lemma C.6. This completes the induction for i ∈ I (t) r,-.Before formally stating the main lemma on the lower bound of noise memorization, we prepare several lemmas that will be useful. Lemma C.8. Suppose that δ > 0. Then with probability 1 -δ, for all r ∈ [m], we have:i:yi=1 1 i∈I (0) r,+ - n 4 ≤ n 2 log(4/δ).Proof. The proof is by Hoeffding's inequality, for arbitrary t > 0, we have thatP   i:yi=1 1 i∈Ir,+ -E   i:yi=1 1 i∈Ir,+   ≤ t   ≤ 2 exp - 2t 2 n .By the randomness of initialization and Rademacher distribution, we have:E   i:yi=1 1 i∈Ir,+   = n 4Setting t = n/2 log(4/δ) and taking a union bound over r ∈ [m], we conclude with high probability at least 1 -δ, it holds: i:yi=11 i∈Ir,+ - n 4 ≤ n 2 log(4/δ).To establish the lower bound for noise memorization we defineEQUATIONr,-≜ i:yi=-1(ρ(t) r,i + ⟨w (0) r , ξ i ⟩)1 i∈I (t) r,+.Lemma C.9. Suppose δ > 0, the with probability at least 1 -δ, we haveEQUATIONr,-≤ σ 0 σ ξ √ dn(1 + log(1/δ)/2).Proof. By Bernstein's inequality, for arbitrary t > 0, we haveP (|B (0) r,+ -σ 0 σ ξ √ nd| > t) ≤ exp(- t 2 2n/4σ 2 0 σ 2 ξ d).Setting t = σ 0 σ ξ nd log(1/δ)/2, we further haveB (0) r,+ ≤ σ 0 σ ξ √ dn(1 + log(1/δ)/2).Similarly, the same result holds for B (0) r,-.Lemma C.10. For arbitrary constant C > 0, under the condition n ≥8C 2 log(1/δ) log(1/(1-(δ/m) 2 )), then with probability at least 1 -δ, it satisfies|⟨w (0) r , ξ i ⟩| > CB (0) r,+ n , |⟨w (0) r , ξ i ⟩| > CB (0) r,- n .Proof of Lemma C.10. Here we want to show |⟨w(0) r , ξ i ⟩| > B (0) r,+n with high probability. To see this, because ⟨w (0) r , ξ i ⟩ is a random variable with positive mean and variance σ 2 0 σ 2 ξ d. Besides, by Lemma C.9, we haveB (0) r,+ n ≤ σ 0 σ ξ √ dn(1 + log(1/δ)/2) n .By Lemma B.1, we recallP |⟨w (0) r , ξ i ⟩| ≤ t ≤ 1 -exp - 8t 2 πσ 2 0 σ 2 ξ d , Thus when n ≥ 8C 2 log(1/δ) log(1/(1-(δ/m) 2)) , we haveP |⟨w (0) r , ξ i ⟩| ≤ Cσ 0 σ ξ √ dn(1 + log(1/δ)/2) n ) ≤ δ/mand by union bound, we have with probability at least 1 -δ, it holds |⟨w(0) r , ξ i ⟩| > B (0) r,+ n and |⟨w (0) r , ξ i ⟩| > B (0) r,- n .Besides, we defineΨ (t) r,i ≜ ρ (t) r,i + ⟨w (0) r , ξ i ⟩, with y i = 1, i ∈ I (t) r,+ Φ (t) r,i ≜ ρ (t) r,i + ⟨w (0) r , ξ i ⟩, with y i = -1, i ∈ I (t) r,+With all the results (lemmas) and definitions outlined above at hand, we are ready to state the lemmas that provide the lower bound for noise memorization as follows.Lemma C.11. Under the same condition as Theorem 4.2, then with probability at least 1 -δ,EQUATIONEQUATIONEQUATIONProof. The proof is by induction. We can checkρ (0)r,i:yi=1 1 i∈Ir,+ = 0, ΨEQUATIONBesides, by Lemma C.10 and M ∈ n 2 (1 ± o(n -1/2 )), it holds thatΨ (0) r,i = ⟨w (0) r , ξ i ⟩ ≥ 101 C ℓ M + 1 B (0) r,-.Assuming that the results hold at t, we continue the proof by calculating the propagation of B (t) r,+ and B (t) r,-respectively. First, we can see by Lemma C.1 and by induction, for y i = 1 and i ∈ I r,+ ,⟨w (t) r , ξ i + ϵ i ⟩ ≥ ⟨w (0) r , ξ i ⟩ + ρ (t) r,i -|⟨w (t) r , ϵ i ⟩| -6 log(6n 2 /δ) d n ≥ (1 -o(1))⟨w (0) r , ξ i ⟩ + ρ (t) r,i ≥ 0.We can show thatB (t+1) r,- = B (t) r,-+ η nmτ i:yi=-1   (1 -ℓ ′(t) i )⟨w (t) r , ξ i + ϵ i ⟩ - j̸ =i ℓ ′(t) i,j ⟨w (t) r , ξ j ⟩1 i∈Ir,+   1 i∈Ir,+ ∥ξ i ∥ 2 2 ≤ B (t) r,-+ η nmτ i:yi=-1 C ℓ (M + 1) -1 C ℓ (M + 1) (⟨w (0) r , ξ i ⟩ + ρ (t) r,i + |⟨w (t) r , ϵ i ⟩| + 6 log(6n 2 /δ) d n) - j̸ =i 1 j∈Ir,+ 1 C ℓ (M + 1) (⟨w (0) r , ξ j ⟩ + ρ (t) r,j -6 log(6n 2 /δ) d n) (σ 2 ξ d + σ 2 ξ d log(6n 2 /δ))1 i∈Ir,+ ≤ B (t) r,-+ η nτ m C ℓ (M + 1) -1 C ℓ (M + 1) 1.01B (t) r,-- i:yi=-1 1 i∈Ir,+ 1 C ℓ (M + 1) 0.99B (t) r,-(σ 2 ξ d + σ 2 ξ d log(6n 2 /δ)) - i:yi=-1 1 i∈Ir,+ 1 C ℓ (M + 1) (B (t) r,-- j̸ =i 6 log(6n 2 /δ) d n) (σ 2 ξ d + σ 2 ξ d log(6n 2 /δ)) ≤ B (t) r,-+ η nmτ 1.01B (t) r,-- 0.99 2 2C l B (t) r,+ 1.035σ 2 ξ d ≤ B (t) r,-+ η nmτ 1.05B (t) r,--0.5B (t) r,+ σ 2 ξ d ≤ B (t) r,-+ 1.05ησ 2 ξ d nmτ B (t) r,-,where the first inequality is by Lemma C.2, Lemma C.1 and Lemma B.5. Furthermore, the second inequality is by Lemma C.5, i.e., |⟨w(t) r , ϵ i ⟩| ≤ 1/C ξ |⟨w (0) r , ξ i ⟩| (for C ξ > 200), |0.01⟨w (0) r , ξ i ⟩| ≥ 6 log(6n 2 /δ)d -1 n, the definition of B (t) r,+ and B (t)r,-and the induction B(t) r,+ ≥ B (0) r,+ , B (t) r,-≥ B (0) r,-. The third inequality is by M ≥ 100C ℓ -1, M ∈ n 2 (1 ± o(n -1/2)), d > 10000 log(6n 2 /δ) and Lemma C.8. The last inequality is byB (t) r,+ ≥ 0.As a result, we conclude thatB (t) r,-≤ (1 + 1.05ησ 2 ξ d nmτ ) t B (0) r,-.Finally, the induction step forΨ (t)r,i can be calculated as follows:Ψ (t+1) r,i = Ψ (t) r,i + η nmτ   (1 -ℓ ′(t) i )⟨w (t) r , ξ i + ϵ i ⟩ - j̸ =i 1 j∈Ir,+ ℓ ′(t) i,j ⟨w (t) r , ξ j ⟩   1 i∈Ir,+ ∥ξ i ∥ 2 2 ≥ Ψ (t) r,i + η nmτ (M + 1) -C ℓ (M + 1) (⟨w (0) r , ξ i ⟩ + ρ (t) r,i -|⟨w (t) r , ϵ i ⟩| -6 log(6n 2 /δ) d n) - j̸ =i 1 j∈Ir,+ C l M + 1 (⟨w (0) r , ξ j ⟩ + ρ (t) r,j + 6 log(6n 2 /δ) d n) (σ 2 ξ d -σ 2 ξ d log(6n 2 /δ))1 i∈Ir,+ ≥ Ψ (t) r,i + η nmτ (M + 1) -C ℓ M + 1 0.99Ψ (t)r,i -C ℓ M + 1 1.01B (t) r,-(σ 2 ξ d -σ 2 ξ d log(6n 2 /δ)) ≥ Ψ (t) r,i + η nmτ 0.99 2 Ψ (t)r,i -1.01C l M + 1 B (t) r,-0.99σ 2 ξ d ≥ Ψ (t) r,i + ησ 2 ξ d nmτ 0.96Ψ (t) r,i ,where the first inequality is by Lemma C.2, Lemma C.1 and Lemma B.5. Furthermore, the second inequality is by Lemma C.5, i.e., |⟨w(t) r , ϵ i ⟩| ≤ 1/C ξ |⟨w (0) r , ξ i ⟩| (for C ξ > 200), |0.01⟨w (0) r , ξ i ⟩| ≥ 6 log(6n 2 /δ)d -1 n, the definition of B (t) r,+ and B (t) r,-. The third inequality is by M ≥ 100C ℓ -1.The last inequality is by induction (23) .Then we check induction induction (23) through following inequalities:B (t) r,-≤ (1 + 1.05ησ 2 ξ d nmτ ) t B (0) r,-, Ψ (t) r,i ≥ (1 + 0.96ησ 2 ξ d nmτ ) t Ψ (0) r,i .Together it confirms thatΨ (t) r,i ≥ 101C ℓ M +1 B (t) r,-.Finally, we check the sign of ρ(t)r,i for i : y i = 1 and i ∈ I(t)r,+ :ρ (t) r,i = Ψ (t) r,i -⟨w (0) r , ξ⟩ ≥ (1 + ησ 2 ξ d 2nmτ ) t Ψ (t) r,i -⟨w (0) r , ξ⟩ > ησ 2 ξ d 2nmτ Ψ (t) r,i > 0.This completes the induction proof. Lemma C.12. Suppose that δ > 0 and m ≥ Ω(1). Then with probability at least 1 -δ, we have1 m r∈U (0) + Ψ (0) r,i ≥ 0.2σ 0 σ ξ √ d, 1 m r∈U (0) - Φ (0) r,i ≥ 0.2σ 0 σ ξ √ d.Proof of Lemma C.12. Consider y i = 1. Note that ⟨w(0) r , ξ i ⟩ ∼ N (0, σ 2 0 ∥ξ i ∥ 2 2). We define that the eventA = {r ∈ [m], ⟨w (0) r , ξ i ⟩ > 0}.Then we can compute that ⟨w (0) r , ξ i ⟩1(A) becomes a half-normal distribution with the expectationE[⟨w (0) r , ξ i ⟩1(A)] = √ 2σ 0 ∥ξ i ∥ 2 √ π .We then apply the sub-Gaussian concentration inequality that with probability at least 1 -δr∈U (0) + Ψ (0) r,i - mσ 0 ∥ξ i ∥ 2 √ 2π ≤ O(m -1/2 ).Then we have 1 mr∈U (0) + Ψ (0) r,i ≥ 0.4σ 0 ∥ξ i ∥ 2 ≥ σ 0 σ ξ √ d,where we have used Lemma B.5. Similarly, we can show that for y i = -1, the same result holds.Proof of Lemma 5.2. From the upper bound on (21), we take the maximum over r ∈ U(0) + , which gives max r A (t) r ≤ 1 + 0.52 η∥µ∥ 2 2 mτ t max r A (0) r ≤ 1 + 0.52 η∥µ∥ 2 2 mτ t σ 0 ∥µ∥ 2 2 log(8m/δ).Under the SNR condition n • SNR 2 ≤ 1.8, we can see there exists a scale difference between max r,i Ψ(t)r,i and max r,i A(t)r at the end of first stage. At the same time, for noise memorization, from the lower bound established in Lemma C.11, we have that1 m r∈U (0) + Ψ (t) r,i ≥ (1 + 0.96ησ 2 ξ d nmτ ) t 1 m r∈U (0) + Ψ (0) r,i ≥ (1 + 0.96ησ 2 ξ d nmτ ) t 0.2σ 0 σ ξ √ d,where the second inequality is due to Lemma C.12.LetT 1 = log 20/(σ 0 σ ξ √ d) / log 1 + 0.96 ησ 2 ξ d nmτ .Then we have 1 m r∈U(0) + Ψ (t)r,i reach 3 within T 1 iterations by (22) . Similarly, we can also show that1 m r∈U (0) - Φ (t)r,i reach 3 within T 1 iterations.On the other hand, we compute the scale of max r A ησ 2 ξ d nmτ ) log(12/(σ 0 σ ξ √ d) σ 0 ∥µ∥ 2 2 log(8m/δ) ≤ exp (0.55 • n • SNR 2 + O(( η∥µ∥ 2 2 mτ ) 2 ) log(20/(σ 0 σ ξ √ d) σ 0 ∥µ∥ 2 2 log(8m/δ) ≤ exp (0.55 • n • SNR 2 + 0.01) log(30/(σ 0 σ ξ √ d) σ 0 ∥µ∥ 2 2 log(8m/δ) ≤ exp log(30/(σ 0 σ ξ √ d) σ 0 ∥µ∥ 2 2 log(8m/δ) = 20 2 log(8m/δ)SNR = O( log(m/δ)/n) = O(n -1/2 )where we choose η sufficiently small for the third inequality. The last inequality is by the SNR condition. Because we can choose n ≥ C log(m/δ) for sufficiently large constant C, max r A(T1) r = o(1).Proposition C.13. Let T * be the maximum admissible iteration and let α = log(3M T * ). Then we can show|γ (t) r | ≤ α, |ρ (t) r,i | ≤ α.Proof of Proposition C.13. We need to show ρ(t)r,i ≤ α. We prove the claim by induction. It is clear when t = 0, ρ(t) r,i = 0 ≤ α. Suppose for all 0 ≤ t ≤ T -1, we have ρ (t)r,i ≤ α. We aim to show the claim holds for T .By the update of ρ(t) r,i , ρ (t+1) r,i ≤ ρ (t) r,i + η nmτ (1 -ℓ ′(t) i )σ(⟨w (t) r , ξ i + ϵ i ⟩)∥ξ i ∥ 2 2 .Here without loss of generality, we consider the r, i pairs such that i ∈ IEQUATIONr , ξ i ⟩ > 0 with y i = 1. Let t r,i be the last time t such that ρ (t) r,i ≤ 0.5α. Then we haveEQUATION)The second term can be bounded asEQUATIONwhere the first inequality is by 1 -ℓ ′(tr) i F 0 (W, x i ) = Sim h (x i , x i )/τ = 1 mτ m r=1 σ(⟨w r , y i µ⟩)sg(σ(⟨w r , y i µ⟩)) + 1 mτ m r=1 σ(⟨w r , ξ i ⟩)sg(σ(⟨w r , ξ i + ϵ i ⟩)) F j (W, x i ) = Sim h (x i , x j )/τ = 1 mτ m r=1 σ(⟨w r , y i µ⟩)sg(σ(⟨w r , y j µ⟩)) + 1 mτ m r=1 σ(⟨w r , ξ i ⟩)sg(σ(⟨w r , ξ j ⟩)), for j = 1, ..., MNext, we show the bound for F 0 (W (t) , x i ) and F j (W (t) , x i ) for j = 1, ..., M asF 0 (W (t) , x i ) ≥ 1 mτ m r=1 σ(⟨w (t) r , ξ i ⟩)σ(⟨w (t) r , ξ i + ϵ i ⟩).Further, we have for j = 1, ..., MF j (W (t) , x i ) = 1 mτ m r=1 σ(⟨w (t) r , ξ i ⟩)σ(⟨w (t) r , ξ j ⟩).Then we can bound the difference between F 0 (W (t) , x i ) and F j (W (t) , x i ) asEQUATIONwhere the second inequality is by σ(⟨w(t) r , ξ i ⟩) ≥ 3 4 ⟨w (0) r , ξ i ⟩ + ρ (t) r,i ≥ ρ (t) r,i ≥ 0.5α for i ∈ I (0) r,+ . Further σ(⟨w (t) r , ξ i + ϵ i ⟩) ≥ 1 2 ⟨w (0) r , ξ i ⟩ + ρ (t) r,i , σ(⟨w (t) r , ξ j ⟩) ≤ 3 2 ⟨w (0) r , ξ j ⟩ + ρ (t)r,j . The fourth inequality is by induction and 1 2 ⟨w(0) r , ξ i ⟩ -3 2 ⟨w (0)r , ξ j ⟩ ≥ -0.15α. The last inequality is by the condition that α ≥ 20τ . Further, we bound the loss derivative asEQUATIONwhere the second inequality is by (27) .Finally, we boundEQUATIONwhere the first inequality is by Lemma B.5 and σ(⟨w(t) r , ξ i + ϵ i ⟩) ≤ 3 2 ⟨w (0) r , ξ i ⟩ + ρ (t)r,i ≤ 2α by induction. The last inequality is by the condition η ≤ 1 12 nmτ σ 2 ξ d . Combining ( 26) and ( 29) with (25) givesρ ( T )r,i ≤ 0.5α + 0.25α + 0.25α = α, which completes the induction.Lemma C.14. Under Assumption 4.1, for 0 ≤ t ≤ T * , we have∥∇L S (W (t) )∥ 2 F ≤ O(max{∥µ∥ 2 2 , σ 2 ξ d})L S (W (t) ).Proof of Lemma C.14. First, we can write the gradient of ∇ wr L i (W) as∇ wr L i (W) = M j=0 ∂L i (W) ∂F j (W, x i ) ∇ wr F j (W, x i ),where ,xi) , for j = 1, ..., M By the derivation of the gradient,∂L i (W) ∂F 0 = -1 + e F0(W,xi) e F0(W,xi) + M j=1 e Fj (W,xi) ∂L i (W) ∂F j = e Fj (W,xi) e F0(W,xi) + M j=1 e Fj (WEQUATIONwhere the first inequality is by triangle inequality and second inequality uses i a 2 i ≤ ( i a i ) 2 for a i ≥ 0 and the last inequality is by triangle inequality. Now we upper bound ∥∇ wr F j (W, x i )∥ 2 as∥∇ wr F 0 (W, x i )∥ 2 = 1 mτ ∥σ ′ (⟨w r , y i µ⟩)σ(⟨w r , y i µ⟩)y i µ + σ ′ (⟨w r , ξ i ⟩)σ(⟨w r , ξ i + ϵ i ⟩)ξ i ∥ 2 ≤ 1 mτ σ(⟨w r , y i µ⟩)∥µ∥ 2 + σ(⟨w r , ξ i + ϵ i ⟩)∥ξ i ∥ 2 ≤ 1 mτ σ(⟨w r , y i µ⟩) + σ(⟨w r , ξ i + ϵ i ⟩) O max{∥µ∥ 2 , σ ξ √ d} ,where the first inequality is by triangle inequality and the second inequality is by Jensen's inequality. Similarly, we can obtain for j = 1, ..., M∥∇ wr F j W, x i )∥ 2 ≤ 1 mτ σ(⟨w r , y j µ⟩) + σ(⟨w r , ξ j ⟩) O max{∥µ∥ 2 , σ ξ √ d} .For clarity letz r,0 = σ(⟨w r , y i µ⟩) + σ(⟨w r , ξ i + ϵ i ⟩) z r,j = σ(⟨w r , y j µ⟩) + σ(⟨w r , ξ j ⟩), for j = 1, ..., MSubstituting the above results into (30) gives∥∇L S (W (t) )∥ 2 F ≤ 1 nmτ n i=1 m r=1 M j=0 ∂L i (W) ∂F j (W, x i ) z r,j 2 O max{∥µ∥ 2 2 , σ 2 ξ d} ≤ 1 nτ n i=1 M j=0 ∂L i (W) ∂F j (W, x i ) ( 1 m m r=1 M j=0 z r,j ) 2 O max{∥µ∥ 2 2 , σ 2 ξ d} ,where the second inequality is byi a i b i ≤ ( i a i )( i b i ) for a i , b i ≥ 0.Next we can verify that M j=0 ∂L i (W) ∂F j (W, x i ) = 1 - e F0(W,xi)EQUATIONwhere the last inequality is by 1 -x ≤ -3 log(x) for x ∈ [0, 1]. Furthermore, we can show2 1 - e F0(W,xi) e F0(W,xi) + M j=1 e Fj (W,xi) ( 1 m m r=1 M j=0 z r,j ) 2 = O(1),which leads to∥∇L S (W (t) )∥ 2 F ≤ 1 nτ n i=1 M j=0 ∂L i (W (t) ) ∂F j (W (t) , x i ) 2 ( 1 m m r=1 M j=0 z r,j ) 2 2 O max{∥µ∥ 2 2 , σ 2 ξ d} ≤ 1 nτ n i=1 M j=0 ∂L i (W (t) ) ∂F j (W (t) , x i ) 2 O max{∥µ∥ 2 2 , σ 2 ξ d} ≤ O max{∥µ∥ 2 2 , σ 2 ξ d} 1 n n i=1 L i (W (t) ) ≤ O max{∥µ∥ 2 2 , σ 2 ξ d} L S (W (t)), where the third inequality is by (31) and Cauchy-Schwartz inequality.We definew * r = w (0) r + 2τ log(2M/ϵ) n i=1 ξ i ∥ξ i ∥ 2 2 .Recall in the first stagew (T1) r = w (0) r + γ (T1) r ∥µ∥ -2 2 µ + n i=1 ρ (T1) r,i ∥ξ i ∥ -2 2 ξ i ,and we have• max r |γ (t) r | = O(n -1/2 ) for all 0 ≤ t ≤ T 1 . • max r,i ρ (T1) r,i ≥ 2. Lemma C.15. Under Assumption 4.1, we have ∥W (T1) -W * ∥ F ≤ O(m 1/2 n 1/2 σ -1 ξ d -1/2 ).Proof of Lemma C.15. We have∥W (T1) -W * ∥ F ≤ ∥W (T1) -W (0) ∥ F + ∥W (0) -W * ∥ F ≤ r γ (T1) r ∥µ∥ 2 + O( √ m) max r ∥ n i=1 ρ (T1) r,i ξ i ∥ξ i ∥ 2 2 ∥ 2 + O(m 1/2 n 1/2 log(1/ϵ)σ -1 ξ d -1/2 ) ≤ O(m 1/2 n 1/2 σ -1 ξ d -1/2 ). Lemma C.16. Under Assumption 4.1, we have for all t ∈ [T 1 , T * ] ⟨∇F 0 (W (t) , x i ), W * ⟩ ≥ 2 log(2M/ϵ), ⟨∇F j (W (t) , x i ), W * ⟩ ≤ log(2M/ϵ).Proof of Lemma C. 16 . Based on the definition of W * and F j (W (t) , x i ), we can derive for j = 0,⟨∇F 0 (W (t) , x i ), W * ⟩ = m r=1 ⟨∇ wr F 0 (W (t) , x i ), w * r ⟩ = 1 mτ m r=1 σ ′ (⟨w (t) r , y i µ⟩)σ(⟨w (t) r , y i µ⟩)⟨w * r , y i µ⟩ + 1 mτ m r=1 σ ′ (⟨w (t) r , ξ i ⟩)σ(⟨w (t) r , ξ i + ϵ i ⟩)⟨w * r , ξ i ⟩ = 1 mτ m r=1 σ ′ (⟨w (t) r , y i µ⟩)σ(⟨w (t) r , y i µ⟩) ⟨w (0) r , y i µ⟩ + 2τ log(2M/ϵ) n i=1 ⟨ξ i , y i µ⟩∥ξ i ∥ -2 2 + 1 mτ m r=1 σ ′ (⟨w (t) r , ξ i ⟩)σ(⟨w (t) r , ξ i + ϵ i ⟩) ⟨w (0) r , ξ i ⟩ + 2τ log(2M/ϵ) + 2τ log(2M/ϵ) i ′ ̸ =i ⟨ξ i , ξ i ′ ⟩∥ξ i ′ ∥ -2 2 ≥ 1 mτ m r=1 σ ′ (⟨w (t) r , ξ i ⟩)σ(⟨w (t) r , ξ i + ϵ i ⟩)2τ log(2M/ϵ) I1 - 1 mτ m r=1 σ(⟨w (t) r , y i µ⟩) O(σ 0 ∥µ∥ 2 ) I2 - 1 mτ m r=1 σ(⟨w (t) r , y i µ⟩)2τ log(2M/ϵ) O(n∥µ∥ 2 σ -1 ξ d -1 ) I3 - 1 mτ m r=1 σ(⟨w (t) r , ξ i + ϵ i ⟩) O(σ 0 σ ξ √ d) I4 - 1 mτ m r=1 σ(⟨w (t) r , ξ i + ϵ i ⟩)2τ log(2M/ϵ) O(nd -1/2 ) I5where the inequality is by Lemma B.5.Next, we bound I 1 , I 2 , I 3 , I 4 , I 5 separately. For I 1 , we take maximum over r, which results in1 m m r=1 σ(⟨w (t) r , ξ i + ϵ i ⟩) ≥ 1 m m r=1 σ( 1 2 ⟨w (0) r , ξ i ⟩ + ρ (t) r,i ) ≥ 2.Thus we obtainI 1 ≥ 4 log(2M/ϵ).In addition, we can show by upper bound on ρ(t)r,i and γ(t) r , ⟨w (t) r , ξ i + ϵ i ⟩ ≤ 3 2 |⟨w (0) r , ξ i ⟩| + |ρ (t) r,i | ≤ O(1), ⟨w (t) r , µ⟩ ≤ 3 2 |⟨w (0) r , µ⟩| + |γ (t) r | ≤ O(1).This impliesI 2 ≤ O(σ 0 ∥µ∥ 2 ), I 3 ≤ log(2M/ϵ) O(nm∥µ∥ 2 σ -1 ξ d -1 ), I 4 ≤ O(σ 0 σ ξ √ d), I 5 ≤ O(nmd -1/2 ).Based on the conditions on σ 0 , d, we can show⟨∇F 0 (W (t) , x i ), W * ⟩ ≥ 4 log(2M/ϵ) -I 2 -I 3 -I 4 -I 5 ≥ 2 log(2M/ϵ).Now we prove for the claim for F j (W (t) , W * ) for j = 1, ..., M as follows.⟨∇F j (W (t) , x i ), W * ⟩ = 1 mτ m r=1 σ ′ (⟨w (t) r , y i µ⟩)σ(⟨w (t) r , y j µ⟩)⟨w * r , y i µ⟩ + 1 mτ m r=1 σ ′ (⟨w (t) r , ξ i ⟩)σ(⟨w (t) r , ξ j ⟩)⟨w * r , ξ i ⟩ = 1 mτ m r=1 σ ′ (⟨w (t) r , ξ i ⟩)σ(⟨w (t) r , ξ j ⟩)⟨w * r , ξ i ⟩ ≤ I 3 + I 4 + I 5 ≤ log(2M/ϵ),where the second equality is by y i ̸ = y j .Lemma C.17. Under Assumption 4.1, we have∥W (t) -W * ∥ 2 F -∥W (t+1) -W * ∥ ≥ ηL S (W (t) ) -ηϵ.Proof of Lemma C.17. First, we verify that for j = 0,⟨∇F 0 (W (t) , x i ), W (t) ⟩ = m r=1 ⟨∇ wr F 0 (W (t) , x i ), w (t) r ⟩ = 1 mτ m r=1 ⟨σ ′ (⟨w r , y i µ⟩)sg(σ(⟨w r , y i µ⟩))y i µ, w (t) r ⟩ + 1 mτ m r=1 ⟨σ ′ (⟨w r , ξ i ⟩)sg(σ(⟨w r , ξ i + ϵ i ⟩))ξ i , w (t) r ⟩ = 1 mτ m r=1σ(⟨w r , y i µ⟩)sg(σ(⟨w r , y i µ⟩))EQUATIONSimilarly, we can show for j = 1, ..., M , it satisfies thatEQUATIONBy the update of W (t) , we have∥W (t) -W * ∥ 2 F -∥W (t+1) -W * ∥ 2 F = 2η⟨∇L S (W (t) ), W (t) -W * ⟩ -η 2 ∥∇L S (W (t) )∥ 2 F = 2η n n i=1 M j=0 ∂L i (W (t) ) ∂F j (W (t) , x i ) ⟨∇F j (W (t) , x i ), W (t) -W * ⟩ -η 2 ∥∇L S (W (t) )∥ 2 F = 2η n n i=1 M j=0 ∂L i (W (t) ) ∂F j (W (t) , x i ) F j (W (t) , x i ) -⟨∇F j (W (t) , x i ), W * ⟩ -η 2 ∥∇L S (W (t) )∥ 2 F ≥ 2η n n i=1 ∂L i (W (t) ) ∂F 0 (W (t) , x i ) F 0 (W (t) , x i ) -2 log(2M/ϵ) + M j=1 ∂L i (W (t) ) ∂F j (W (t) , x i ) F j (W (t) , x i ) -log(2M/ϵ) -η 2 ∥∇L S (W (t) )∥ 2 F ≥ 2η n n i=1 L i (W (t) ) + log( e 2 log(2M/ϵ) e 2 log(2M/ϵ) + M e log(2M/ϵ) ) -η 2 ∥∇L S (W (t) )∥ 2 F = 2η n n i=1 L i (W (t) ) -log(1 + ϵ 2 ) -η 2 ∥∇L S (W (t) )∥ 2 F ≥ ηL S (W (t) ) -ηϵ,where the third equality is by (32) and (33) . The first inequality is by Lemma C. 16 . The second inequality is due to the convexity of negative log-Softmax function. The last inequality is by Lemma C.14 (and the conditions on η) and log(1 + x) ≤ x for x ≥ 0.Lemma C.18. Under Assumption 4.1, let T = T 1 +⌊∥W (T 1 ) -W * ∥ 2 F ηϵ ⌋ = T 1 + O(mnσ -2 ξ d -1 η -1 ϵ -1). Then we have max r |γ(t) r | ≤ O(1/ √ n) for all T 1 ≤ t ≤ T .In addition, we have1 t -T 1 + 1 t s=T1 L S (W (s) ) ≤ ∥W (T1) -W * ∥ 2 F η(t -T 1 + 1) + ϵfor all T 1 ≤ t ≤ T . Thus there exists an iterate W (s) for s ∈ [T 1 , T ] with training loss smaller than 2ϵ.Proof of Lemma C. 18 . By Lemma C.17, for t ∈ [T 1 , T ],∥W (s) -W * ∥ 2 F -∥W (s+1) -W * ∥ ≥ ηL S (W (t)) -ηϵ for all s ≤ t. Summing over the inequality and dividing both sides by t -T 1 + 1 yields1 t -T 1 + 1 t s=T1 L S (W (s) ) ≤ ∥W (T1) -W * ∥ 2 F + ηϵ(t -T 1 + 1) η(t -T 1 + 1) = ∥W (T1) -W * ∥ 2 F η(t -T 1 + 1) + ϵ ≤ 2ϵ,where the last inequality is by the definition of T , for all T 1 ≤ t ≤ T . In addition, we haveEQUATIONNext we prove the claim that max r |γ (t) r , ϕ (t+1) ≤ ϕ (t) + η nmτ i:yi=1 (1 -ℓ ′(t) i ) max r ( 3 2 ⟨w (0) r , µ⟩ + ϕ (t) )∥µ∥ 2 2 ≤ ϕ (t) + η nmτ i:yi=1 (1 -ℓ ′(t) i )( 3 2 2 log(8m/δ)σ 0 ∥µ∥ 2 + ϕ (t) )∥µ∥ 2 2 ≤ ϕ (t) + η mτ L S (W (t) )( 3 2 2 log(8m/δ)σ 0 ∥µ∥ 2 + ϕ (t) )∥µ∥ 2 2 ,where the third inequality is by (31) .Now summing over t = T 1 , ..., T -1, we haveϕ ( T ) ≤ ϕ (T1) + T -1 t=T1 η mτ L S (W (t) )( 3 2 2 log(8m/δ)σ 0 ∥µ∥ 2 + ϕ (t) )∥µ∥ 2 2 ≤ ϕ (T1) + O( η∥µ∥ 2 2 mτ )β T -1 t=T1 L S (W (t) ) ≤ ϕ (T1) + O(n∥µ∥ 2 2 d -1 σ -2 ξ )β ≤ ϕ (T1) + O(nSNR 2 )β ≤ ϕ (T1) + 2β ≤ 3βwhere the second inequality is by induction and the third inequality is by (34) . The last inequality is by the condition of SNR.Recall that after the pre-training stage on the training data at time T , the signal learning and noise memorization satisfymax r A (T ) r = O(1/ √ n), max r Ψ (T ) r,i = Ω(1) for i ∈ [n].Then, on the downstream task, the corresponding embedding can be calculated as follows:EQUATIONtest ) = σ(⟨w (T ) r , xEQUATIONtest ) = σ(⟨w (T ) r , xEQUATIONThen, it is straightforward to check that the embedding of a finite size of samples during the fine-tuning stage is not linearly separable. Thus, the downstream task performance follows L Dtest (T * ) = Θ(1).D Multi-Modal Contrastive Learning: Proof of Theorem 4.3Similar to the single-modal case, in the first stage, the loss derivative is close to its initial value for both modalities. Lemma D.1. If max{γEQUATIONr,i , γ (t) r , ρ (t) r,i } = O(1), there exists a constant C ℓ > 1 such that 1 C ℓ (1 + M ) ≤ ℓ ′(t) i ≤ C ℓ 1 + M 1 C ℓ (M + 1) ≤ ℓ ′(t) i,j ≤ C ℓ 1 + M for all i ∈ [n].|⟨w (t) r -w (0) r , ξ i ⟩ -ρ (t) r,i | ≤ 5 log(6n 2 /δ) d n |⟨w (t) r -w (0) r , µ⟩ -γ (t) r | ≤ SNR 8 log(6n/δ) d n, |⟨ w (t) r -w (0) r ξ i ⟩ -ρ (t) r,i | ≤ 5 log(6n 2 /δ) d n |⟨ w (t) r -w (0) r , µ⟩ -γ (t) r | ≤ SNR 8 log(6n/δ) d n for all r ∈ [m], i ∈ [n].We first analyze the dynamics of signal learning for both two modalities. Similar as in the singlemodal learning, we partition the neurons, depending on the initialization, i.e., UEQUATIONr , µ⟩ < 0}. Lemma D.3. Under Assumption 4.1 and the same condition as Lemma D.2, for all t > 0, we have + , there exists a time t ′ > 0 such that r ∈ U(t ′ ) + ∩ U (t ′ ) + or r ∈ U (t ′ ) -∩ U (t ′ ) -.Proof of Lemma D.3. We first analyze the neurons r ∈ UEQUATIONwhere the second equality is by y i = y j and the derivative of ReLU activation. Similarly for the other modality,EQUATIONHence we see at t = 0, the claim is satisfied as γ -.Next, we analyze the case where r ∈ UEQUATIONwhere the second equality follows from y i ̸ = y j . Similarly,γ (t+1) r = γ (t) r + η nmτ n i=1 (1 -ℓ ′(t) i )σ(⟨w (t) r , y i µ⟩)σ ′ (⟨ w (t) r , y i µ⟩)y i ∥ µ∥ 2 2 - η nmτ n i=1 M j̸ =i ℓ ′(t)i,j σ(⟨w (t) r , y j µ⟩)σ ′ (⟨ w (t) r , y i µ⟩)EQUATION)Then it is clear that the change of γEQUATIONr does not align with the sign of its initialization. Therefore there exists some time t ′ ≥ 0 such that either r ∈ U(t ′ ) + ∩ U (t ′ ) + or r ∈ U (t ′ ) -∩ U (t ′ )-. We prove this claim by contradiction. Suppose for all t ≥ 0, r ∈ U(t) + ∩ U (t)-, then by (37) and (38) , we see γ(t+1) r ≤ γ (t) r ≤ 0 and γ (t+1 r ≥ γ (t) r ≥ 0. Because ⟨w (t) r , µ⟩ ≤ 1.01⟨w (0) r , µ⟩ + γ (t) r and ⟨ w (t) r , µ⟩ ≥ 0.99⟨ w (0) r , µ⟩ + γ (t)r , this raises a contradiction as either ⟨w -. Then with probability at least 1 -δ, we haveA (t) r ≥ 1 + 0.48η∥µ∥ 2 2 C µ mτ t (A (0) r + A (0) r /C µ ) -1 A (t) r ≥ 1 + 0.48η∥µ∥ 2 2 C µ mτ t (C µ A (0) r + A (0) r ) -1.Proof. Without loss of generality, we consider r ∈ U+ ∩ U+ . Then by the update of γEQUATIONr , we have from ( 35) and ( 36)EQUATIONTo achieve the lower bound, we defineA (t) r ≜ γ (t) r + ⟨w (0) r , µ⟩, A (t) r = γ (t) r + ⟨ w (0)r , µ⟩. By (39), we have the lower bound of update equation,A (t+1) r = A (t) r + η nmτ i:yi=1 (1 -ℓ ′(t) i )σ(⟨ w (t) r , µ⟩)∥µ∥ 2 2 ≥ A (t) r + η nmτ ( n 2 -O( √ n))(1 - C ℓ 1 + M ) A (t) r ∥µ∥ 2 2 ≥ A (t) r + 0.48η∥µ∥ 2 2 mτ A (t) r .The inequality is by Lemma B.3, Lemma D.1 where we recall c 2 = 1 -C ℓ M +1 . Similarly, by ( 40) we arrive atA (t+1) r ≥ A (t) r + 0.48η∥ µ∥ 2 2 mτ A (t) r = A (t) r + 0.48ηC 2 µ ∥µ∥ 2 2 mτ A (t) r .Then by combining the above two inequalities, we conclude thatC µ A (t+1) r + A (t+1) r = C µ A (t) r + A (t) r + 0.48η∥µ∥ 2 2 mτ (C µ A (t) r + C 2 µ A (t) r ) ≥ 1 + 0.48η∥µ∥ 2 2 C µ mτ (C µ A (t) r + A (t) r ).Thus, we see the joint dynamics of γ (t) r and γ (t) r exhibits exponential growth, i.e.,EQUATIONTo characterize the dynamics of γ r by subtracting ( 40) from (39) , which givesC µ A (t+1) r -A (t+1) r = C µ A (t) r -A (t) r + η∥µ∥ 2 2 nmτ i:yi=1 (1 -ℓ ′(t) i ) C µ σ(⟨v (t) r , µ⟩) -C 2 µ σ(⟨w (t) r , µ⟩) ≥ 1 - ηC µ ∥µ∥ 2 2 nmτ i:yi=1 (1 -ℓ ′(t) i ) C µ A (t) r -A (t) r .Then from the the propagation, we notice that the gapC µ A (t) r -A (t)r exhibits exponential decay regardless of the sign. Thus, we haveEQUATIONTherefore, combining ( 41) and ( 42) yields:EQUATIONBefore we state the main result, we provide some useful lemmas. Lemma D.5. Suppose δ > 0, the with probability at least 1 -δ, we haveEQUATIONr,-,+ ≤EQUATIONr,-,+ ≤1 2 σ 0 σ ξ √ dn(1 + log(1/δ)/2).Proof. By Bernstein's inequality, for arbitrary t > 0, we haveEQUATIONr,+,+ -1 2 σ 0 σ ξ √ nd| > t) ≤ exp(- t 2 2n/4σ 2 0 σ 2 ξ d).Setting t = 1 2 σ 0 σ ξ nd log(1/δ)/2, we further haveB (0) r,+ ≤ 1 2 σ 0 σ ξ √ dn(1 + log(1/δ)/2).Similarly, the same result holds for B Next, we establish the following inequality For the second modality, with the same derivative, we could obtain the following inequalities: We definei:yi=1   (1 -ℓ ′(t) i )⟨ w (t) r , ξ i ⟩ - j:yj =-1 ℓ ′(t) i,j ⟨ w (t) r , ξ j ⟩1 j∈ Ir,+   1 i∈Ir,+∩ Ir,+ ∥ξ i ∥ 2 2 ≤ B (t) r,+,+ + η nmτ i:yi=1 1 i∈Ir,+∩ Ir,+ C ℓ (M + 1) -1 C ℓ (M + 1) (⟨ w (0) r , ξ i ⟩ + ρ (t) r,i + 6 log(6n 2 /δ) d n) - j:yj =-1 1 C ℓ (M + 1) (⟨ w (0) r , ξ j ⟩ + ρ (t) r,j -6 log(6n 2 /δ) d n)1 j∈ Ir,+ (σ 2 ξ d + σ 2 ξ d log(6n 2 /δ)) ≤ B (t) r,+,+ + η nτ m C ℓ (M + 1) -1 C ℓ (M + 1) ( B (t) r,+,+ + i:yi=1 1 i∈Ir,+∩ Ir,+ 6 log(6n 2 /δ) d n)) - i:yi=1 1 i∈Ir,+∩ Ir,+ 1 C ℓ (M + 1) ( B (t) r,-,+ + B (t) r,-,-- j̸ =i 6 log(6n 2 /δ) d n) (σ 2 ξ d + σ 2 ξ d log(6n 2 /δ)) ≤ B (t) r,+,+ + η nmτ 1.01B (t) r,+,+ - 0.99 2 4C l ( B (t) r,-,+ + B (t) r,-,-) 1.035σ 2 ξ d ≤ B (t) r,+,+ + η nmτ 1.05B (t) r,+,+ - 1 4 ( B (t) r,-,+ + B (t) r,-,-) σ 2 ξ d,EQUATIONΨ (t) r,i ≜ ρ (t)r,i + ⟨w (0) r , ξ i ⟩, i ∈ I (2) for i ∈ I (3) for i ∈ I Proof of Lemma D.9. We partition the dynamics of ρ At the same time, for signal learning, from the lower bound on signal learning in Lemma D.4, we have for the first modality thatA (t) r ≥ 1 + 0.48η∥µ∥ 2 2 C µ mτ t (A (0) r + A (0) r /C µ ) -1Taking a summation over the r ∈ U where we choose η sufficiently small for the second inequality. In third inequality, we have applied the condition that nSNR 2 = Θ(1) and σ 0 ≤ 1 ∥µ∥2 . The last inequality is by the SNR condition. Because we can choose n ≥ C log(m/δ) for sufficiently large constant C, max r,i Ψ (T1) r,i = o(1).We first show a similar result as in Lemma C.14 for both two modalities. Lemma D.11. Under conditions, for 0 ≤ t ≤ T * , we have ∥∇L S (W (t) )∥ 2 F ≤ O(max{∥µ∥ 2 2 , σ 2 ξ d})L S (W (t) ), ∥∇L S ( W (t) )∥ 2 F ≤ O(max{∥ µ∥ 2 2 , σ 2 ξ d})L S ( W (t) ).Proof of Lemma D.11. The proof follows from that of Lemma C.14 and hence is omitted for clarity.For notation convenience, we let F 0 (W, x i ) = Sim h,g (x i , x i )/τ 2 ) and ∥ W (T1) -W * ∥ F ≤ O(m 1/2 ∥ µ∥ -12 )Proof of Lemma D.12. The proof follows exactly the same as the proof in single-modal case. we include it here for completeness. Without loss of generality, we focus on the case for W (T1) .By the scale difference at T 1 , we have  


Decision: The authors develop a unified framework to analyze both single-modal and multi-modal contrastive learning. They explore why multi-modal contrastive learning might be more effective than its single-modal counter part. The reviewers noted some concerns about the clarity of the proofs and the underlying assumptions (which are found to be too strong), but the rebuttal resolved the main questions and concerns. The authors are urged to incorporate all suggestions and additional clarifications into the paper or the appendix of the paper. Despite the concerns, the theoretical framework can be valuable for the machine learning community.

Reviews: review: paper_summary: paper_summary: This paper provides a theoretical analysis comparing single-modal and multi-modal contrastive learning. The authors develop a unified framework to analyze the optimization dynamics and generalization capabilities of both approaches. Key findings include:

- Both single-modal and multi-modal contrastive learning can achieve small training error.
- Multi-modal contrastive learning generalizes better to downstream tasks compared to single-modal learning.
- The advantage of multi-modal learning comes from cooperation between modalities and higher quality data in the second modality.

The analysis is based on a two-stage optimization process and uses a signal-noise data generation model. Theoretical results are supported by synthetic experiments.
strength_weakness: strength_weakness: - The paper could benefit from more intuitive explanations of the key theoretical results to make them more accessible to a broader audience. For example, can you provide intuition for why the cooperation between modalities leads to better signal learning in the multi-modal case? How might this insight be leveraged to improve single-modal contrastive learning?

- The paper lacks discussion on how the insights could be applied to improve existing contrastive learning methods or guide the development of new approaches. Do your theoretical insights suggest any practical strategies for improving multi-modal contrastive learning, such as ways to select or preprocess data to increase the effective signal-to-noise ratio?

- The theoretical setup and assumption of the linear data generation model are somewhat simple and restricted. Do you expect the main insights to hold for more complex data distributions?

- The experimental validation is limited to synthetic data. Including experiments on real-world datasets, even if simplified, would strengthen the paper's impact.
questions: questions: Line 205: “On the contrary, augmentation often maintains the same SNR as the original data, so single-modal learning hardly benefits from the augmentation and can only memorize the noise from the data.” This claim significantly contradicts empirical experiments such as SimCLR and MoCo. How would you justify this?
limitations: limitations: See weaknesses.
paper_summary: paper_summary: This paper presents a theoretical framework to understand the differences between multi-modal and single-modal contrastive learning approaches. It emphasizes the impact of signal-to-noise ratio (SNR) on the generalizability of these learning methods in downstream tasks. The authors argue that multi-modal learning, through the cooperation of modalities, can achieve better feature learning and performance in downstream tasks compared to single-modal learning.
strength_weakness: strength_weakness: - **Strong assumptions made in the theoretical analysis** The analysis relies on some strict assumptions, such as specific signal-to-noise ratios and network initialization conditions, which might not hold in real-world applications. 
- **Some influential previous works are not introduced** such as UMT/UME[1], QMF[2], MMParato[3], and ReconBoost[4].

[1] On Uni-Modal Feature Learning in Supervised Multi-Modal Learning. ICML 2023.

[2] Provable Dynamic Fusion for Low-Quality Multimodal Data. ICML2023

[3] MMPareto: Boosting Multimodal Learning with Innocent Unimodal Assistance. ICML 2024

[4] ReconBoost: Boosting Can Achieve Modality Reconcilement. ICML 2024.
questions: questions: The theoretical analysis is predicated on rather strong assumptions. If the volume of data and the complexity of the models are significantly increased, would conclusions still be applicable?
limitations: limitations: None
paper_summary: paper_summary: In this paper, the authors performed theoretical analysis between single-modal and multi-modal contrastive learning. The authors proved theorems that indicates single-modal contrastive learning tend to perform worse on test datasets after converging on the training set, while multi-modal contrastive learning tend to perform better on the test set. They also conducted small-scale simulated experiments that confirmed their theoretical results.
strength_weakness: strength_weakness: There are many problems with the proof:

1. The starting point of the proof is Assumption 4.1. However, Assumption 4.1 contains many issues that puts the soundness and correctness of the entire proof as well as the usefulness of the results into question:

(a) Incorrect use of big-O-like notations. Big-O notations are formally defined only as sets of functions with variables, but in Assumption 4.1, the authors used big-O-like notation to bound constants, which doesn't make sense.

(b) Assumption (1) is extremely unrealistic. It basically requires that $d>n^2$, meaning that the input data's dimension is larger than the square of the number of data points we have in the dataset. In any real world scenario, your data's input dimension will not be anywhere close to the square of the size of your dataset. For example, OpenAI CLIP is trained with $n=400M$ data instances, and the instance dimension is in the order of $d<2\times 10^5$, so in this case, $d < \frac{1}{10^{11}}n^2$.

(c) Undefined variable $\sigma_0$. Technically $n$ and $\eta$ is also never formally defined in text, but we can guess that they mean the size of the dataset and learning rate respectively.

(d) It is also unclear how assumption (6) distinguishes between the single-modal and multi-modal features, as the assumption only applies to the first modality's SNR. 

2. Theorem 4.2 and 4.3, the main results of the paper, are not well-defined. $\epsilon$ is supposed to be a vector according to Eq(5), but the main result of Theorem 4.2 says that the train loss (which is scalar) is less than $\epsilon$.

3. Confusing definition of the loss derivatives in Eq (8). Are these definitions for $l_i^{(t)}$ or for $l'^{(t)}_{i}$? These expressions does not look like derivatives.

4. Lemma 5.1 is not proven anywhere, but is then directly used in proving Lemma C.3 and Lemma C.7. 

5. The overall proof is organized poorly. It's very difficult to understand what each Lemma is trying to achieve and how are the Lemmas connected to each other, especially between the main text and the Appendix. For example, it is very hard to find where Lemma 5.2 (in the main paper) is proved in the Appendix. Perhaps the authors should add references in the main paper to the appendix (for example, state after Lemma 5.2 "proof in Appendix X.X").

6. The proof roadmaps in Section 5 does not lead to conclusions in Theorems mentioned in Section 4. For example, the roadmap in Section 5.1 does not explicitly tell us how we end up with Theorem 4.2.

7. In proof of Lemma B.2, on Line 560, it is unclear what "RHS" is referring to. Is it the RHS of the last equation on the previous page? Or is it the one immediately before it on line 560? If it is the latter case, you shouldn't be allowed to "set" it to $\delta\/m$ since $\delta$ already appears in the expression before. 

In addition to problems in the proof, it is also unclear how the "noise memorization" and "signal learning" evaluation numbers are defined in the experiment in Figure 1.
questions: questions: 1. Please address the problems in the weakness section.

2. Does your theorems provide any new insight into future research contrastive learning? Any actionable suggestions?
limitations: limitations: Discussion is adequate.

Comments: title: Scores increased
Continued Discussion
Detailed Response to Follow-Up Question on Lemma B.2
Additional Discussion
Please Discuss
comment: Thank you for your positive support and for taking the time to review our rebuttal. We appreciate your thoughtful consideration throughout the review process.
I appreciate the author's great efforts in the rebuttal phase. I will keep my initial score as a final decision.
Thank you for your positive feedback. We are pleased that our ColoredMNIST experiment provided valuable intuition and helped clarify the benefits of multi-modal information. We appreciate your support and are grateful for your consideration in raising the score.
I thank the authors for their detailed explanation. The newly added MNIST experiments provide great intuition into how multi-modal information benefits over uni-modal information. I'll raise my score to 6.
Thank you very much for your positive feedback and for taking the time to review our clarifications. We are glad that our response helped in verifying the correctness of the lemmas.

We appreciate your suggestion to include more details in the proofs and to clearly state assumptions. In our revised version, we will ensure that:

- Assumptions and conditions are explicitly stated and clearly linked across lemmas.
- The inheritance of conditions is made explicit, so readers can easily track how assumptions carry forward throughout the proofs.
- Additional details are included in the proofs to make the logical steps more transparent and easier to follow.

Thank you again for your constructive feedback and for increasing your score.
Thank you very much for your detailed response! With your clarifications on the Assumptions, I was able to verify the correctness of more Lemmas in the Appendix. Therefore, I believe that your overall deductions are likely correct, and I raised my scores to marginally positive.

I still believe that the proofs need to include more details and the assumptions need to be clearly stated, such as "inheritance of conditions in lemma" that you mentioned above, to make verification of correctness by reviewers possible.
Thank you for your detailed feedback. We appreciate the opportunity to clarify the assumptions and structure of our proofs.

**Global and Local Assumption**:

Assumption 4.1 is indeed a global assumption that applies to the entire paper. The assumptions made within specific lemmas do not conflict with this global assumption. In other words, the assumptions in specific lemmas can be weaker but are still compatible with Assumption 4.1. If there is any uncertainty about which assumption should be applied within a lemma, Assumption 4.1 should be considered as the default.

**Regarding the Assumption on $d$**:

Assumption 4.1 provides a unified lower bound that encompasses the requirements from various lemmas, such as B.2, B.4, B.5, C.3, C.5, and C.6. The lower bound on $d$ in Lemma C.6 is indeed bounded by Assumption 4.1.

Specifically, the condition on $d$ in Lemma C.6 can be shown to satisfy Assumption 4.1:

$   \sqrt{\frac{300 \log(6n^2/\delta)}{-\log(1-\delta^2/4n^2) \pi \sigma_0^2\sigma_\xi^2}}
= \tilde{\Theta}(1/(\sigma_0 \sigma_\xi ) )  
$  

which is consistent with Assumption 4.1.

**Inheritance of Conditions in Lemmas**:

When a lemma is used in the proof of a subsequent lemma, the conditions from the earlier lemma are inherited. This ensures that the assumptions remain consistent and valid throughout the proofs.


**Proof Details and Organization**:

Regarding Lemma 5.2 and Theorem 4.2, Lemma 5.2 ensures that until convergence of the dynamics in the second stage, the maximum signal learning is on the order of $\tilde{O}(n^{-1/2})$, while the maximum noise memorization remains constant (as shown in Lemma C.17). The results in Theorem 4.2 are derived through the arguments provided in Section C.3.

In the appendix, we have organized the material using section and subsection titles to provide a clear structure. While some steps in the proofs are streamlined, this approach aligns with standard literature in deep learning theory [1, 2, 3]. We are more than willing to address any specific questions or concerns you may have.

We hope this clarification resolves your concerns. If you have any further questions or suggestions, please feel free to ask.

[1] Allen-Zhu, Zeyuan, et al. A convergence theory for deep learning via over-parameterization. ICML 2019.

[2] Cao, Yuan, et al. Benign overfitting in two-layer convolutional neural networks. NeurIPS 2022.

[3]  Xu, Z., Wang, Y., Frei, S., Vardi, G., & Hu, W. (2023). Benign overfitting and grokking in relu networks for xor cluster data. ICLR 2024.
Thank you for your positive feedback and further questions regarding the ColoredMNIST experiment. We are happy to provide additional details:

- Image: The ColoredMNIST dataset is a variation of the standard MNIST dataset, where each digit is assigned a specific color based on its label. We consider a 10-class classification task in order to better match with the realistic setting. Specifically, we have 10 colors to color 10 digits, and introduce spurious correlations via label noises following the literature.

  - For the training set, 10% of labels will be clipped to a random class. For images with class '0' (or '1'), they will be colored as red (or green) with a probability of 77.5%, and as another random color with a probability of 22.5%. The coloring scheme introduces a spurious correlation.
  - For the test set, 10% of labels will be clipped to a random class. For images with class '0' (or '1'), they will be colored as green (or red) with a probability of 77.5%, and as another random color with a probability of 22.5%. The coloring scheme can be considered as reversing the training spurious correlations. Therefore, the evaluation on testsets can reflect to what extent the model learns to use the spurious features, i.e., colors, to classify images.

- Text:  We also consider an ideal language encoder that successfully encodes the captions of the images into one-hot labels of colors and digits.



As a result, we can claim that the effective SNR of invariant features (the shape of the digit) will be degraded under the impact of the injected color. Therefore, the performance of SimCLR may be suboptimal as it cannot effectively utilize the information of the digit's shape. On the other hand, CLIP demonstrates a better capacity for handling this scenario.

We hope this additional explanation clarifies the experimental setup for the ColoredMNIST experiments. If you have any further questions, please feel free to ask. If our answer has clarified your concerns, we would appreciate it if you could consider reevaluating our submission.
Thank you for your response! Your line-by-line proof of Lemma B.2. is much clearer than what was available in the paper, and this allowed me to verify that the proof of Lemma B.2. is correct, and I continued to verify the correctness of the proofs afterwards that depends on it.

One problem I found is the inconsistency of scopes of symbols. There are global definitions/assumptions of symbols from the main paper, then some additional assumptions/definitions are made from the Lemma statement, which makes it confusing as readers are unsure which assumption still holds within the proofs of each Lemma. For example, the symbol "d" is bounded within Assumption 4.1, but is then again given a lower bound in Lemmas B2,B4,B5,C3,C5,C6, etc. The lower bounds does not have a clear relative size ordering, and is not necessarily bounded by Assumption 4.1 (such as the assumption of lower bound of d from Lemma C6). Technically, within each lemma's proof, the statements should assume the lower bound of d stated in the Lemma, not Assumption 4.1, unless explicitly stated. Therefore, for each following lemma that depends on a previous lemma, the lower bound assumption on d must be stronger than the one from the previous lemma. There are also different assumptions on the size n (lemma C4, lemma C10)
Therefore, can you (1) clarify the scopes of Assumptions/Definitions of all variables, and (2) explain why the earlier lemmas can be used in the proofs of later lemmas without proof of tighter/equal bound assumptions?

Also, regarding R6, it is not trivial to prove Lemma 5.2 from Lemma C.17, and I am unable to find the intermediate steps of this proof. Similarly, there needs to be proof of Lemma 5.1 from Lemma C.11, and steps of the proof of Theorem 4.2 from Lemma 5.1 and 5.2. If there is no space in the main paper, you should include them in the appendix at least. (same situation appear for Lemma D.* and theorem 4.3 and Lemma 5.3/5.4)

An additional comment/suggestion: the current full proof is very poorly written and poorly organized. They are extremely difficult to read. Some of the variable definitions/assumptions occurred more than 20 pages ago, and there should be reminders of the definitions/assumptions. The current proof writing quality would not be admissible to any mathematical journals where reviewers actually check the correctness of your proofs. If everything is written step-by-step and well-defined like the Lemma B.2. proof that you rewrited above, the writing quality would be good enough to allow reviewers to verify the correctness of your proofs.
Thanks for the author's response! Most of my concerns have been addressed. One remaining question: could you elaborate more on the experimental setting for ColoredMNIST experiments? What do the training data & test data look like?
Thank for your the follow-up question. Below, we provide a line-by-line proof for Lemma B.2. 

*Proof of Lemma B.2.* By Lemma B.1 (anti-concentration result for Gaussian random variable), and because $\langle \mathbf{w}^{(0)}_r, \mathbf{\mu} \rangle \sim \mathcal{N}(0, \sigma_0^2 \| \mathbf{\mu} \|^2_2)$, we can show 

$$
    \mathbb{P} \big( |\langle \mathbf{w}^{(0)}_{r} , \mathbf{\mu} \rangle| \leq c \big) \leq 2 \sqrt{1 - \exp\big(  - \frac{2 c^2}{\sigma_0^2 \| \mathbf{\mu} \|_2^2 \pi} \big)}.
$$


We first set $c = 100 \cdot \text{SNR} \sqrt{\frac{8\log(6n/\delta)}{d}} n$ and plug it into the RHS of the above inequality, which becomes

$$\text{RHS} = 2 \sqrt{1 - \exp\big(- \frac{16\times100^2 \cdot \log(6n/\delta) n^2}{\sigma_0^2 \sigma_\xi^2 d^2 \pi} \big)}.$$

Then we can verify that when $d$ satisfies the condition on Line 561, i.e., $d \geq \frac{400n}{\sigma_0 \sigma_\xi} \sqrt{\frac{\log(6n/\delta)}{-\pi \log(1- \delta^2/(4m^2))}}$, we can verify that 

$$\text{RHS} \leq \frac{\delta}{m}.$$

This suggests for a single neuron $r \in [m]$, we have

$$\mathbb{P}( |\langle \mathbf{w}_r^{(0)}, \mathbf{\mu} \rangle| \leq c ) \leq \frac{\delta}{m}.$$

Taking the union bound for all the neurons $r \in [m]$, we have 

$$ \mathbb{P}  \big( \cup\_{r =1}^m \{ | \langle \mathbf{w}\_r^{(0)}, \mathbf{\mu} \rangle | \leq c \} \big) 
\leq \sum_{r=1}^m \mathbb{P}( |\langle \mathbf{w}_r^{(0)}, \mathbf{\mu} \rangle| \leq c ) = \delta.
$$

This then implies that 


$$\mathbb{P}( \cap_{r =1}^m \{|\langle \mathbf{w}_r^{(0)}, \mathbf{\mu} \rangle| \geq c \} ) \geq 1 -\delta.$$

This concludes that with probability at least $1-\delta$, for all neurons $r \in [m]$, we have $|\langle \mathbf{w}_r^{(0)}, \mathbf{\mu}\rangle| \geq c = 100 \cdot \text{SNR} \sqrt{\frac{8\log(6n/\delta)}{d}} n$.

We hope the above line-by-line proof resolves your question and we believe the wording "set RHS to $\delta/m$" is what has caused the confusion. We will remove such wroding and make the proof clearer in the revised version.  

If you have any further questions, we are more than willing to address them. If you find that our responses have sufficiently addressed your concerns and questions, please consider increasing your score. Thank you for your time.
Thank you so much for your replies!

I still have some remaining concerns about Lemma B.2. Specifically, there still seems to be a double-definition of $c$ and $\delta$. You first defined $c =100n∥µ∥_2σ^{−1}_ξd^{−1}\sqrt{8log(6n/δ)}$ on line 560, so $c$ is defined depending on $\delta$; but then, you set RHS (which is an expression containing $c$) directly as $\frac{\delta}{m}$, which shouldn't be allowed.

The version available in the Appendix is too condensed for readers to fully grasp the details. Can you please provide a line-by-line detailed proof of Lemma B.2? This will help me better assess the correctness of the proofs too. Thank you!
Dear Reviewers,

the authors have provided an extensive rebuttal for all reviewers. Please have a look at their responses to see if they address your concerns. If you have further questions, you can now start a discussion with the authors.

Your AC
**References**

[1] Allen-Zhu, Zeyuan, et al. A convergence theory for deep learning via over-parameterization. In International conference on machine learning. 2019.

[2] Allen-Zhu, Zeyuan. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances in neural information processing systems. 2019.

[3] Cao, Yuan, et al. Benign overfitting in two-layer convolutional neural networks. In Advances in neural information processing systems. 2022.

[4] Meng, Xuran, et al. Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Data. In International Conference on Machine Learning. 2024.

[5] Wen, Z. and Li, Y., 2021, July. Toward understanding the feature learning process of self-supervised contrastive learning. In International Conference on Machine Learning (pp. 11112-11122). PMLR.

[6] Xu, Z., Wang, Y., Frei, S., Vardi, G., & Hu, W. (2023). Benign overfitting and grokking in relu networks for xor cluster data. ICLR 2024.

[7] Kou, Yiwen, et al. "Benign overfitting in two-layer ReLU convolutional neural networks." International Conference on Machine Learning. PMLR, 2023.