Understanding the Role of Nonlinearity in Training Dynamics of Contrastive Learning
Authors: Yuandong Tian
Venue: ICLR 2023 poster (2023)
Keywords: contrastive learning
self-supervised learning
representation learning
nonlinearity
training dynamics
landscape

Abstract: While the empirical success of self-supervised learning (SSL) heavily relies on the usage of deep nonlinear models, existing theoretical works on SSL understanding still focus on linear ones. In this paper, we study the role of nonlinearity in the training dynamics of contrastive learning (CL) on one and two-layer nonlinear networks with homogeneous activation $h(x) = h'(x)x$. We have two major theoretical discoveries. First, the presence of nonlinearity can lead to many local optima even in 1-layer setting, each corresponding to certain patterns from the data distribution, while with linear activation, only one major pattern can be learned. This suggests that models with lots of parameters can be regarded as a \emph{brute-force} way to find these local optima induced by nonlinearity. Second, in the 2-layer case, linear activation is proven not capable of learning specialized weights into diverse patterns, demonstrating the importance of nonlinearity. In addition, for 2-layer setting, we also discover \emph{global modulation}: those local patterns discriminative from the perspective of global-level patterns are prioritized to learn, further characterizing the learning process. Simulation verifies our theoretical findings.  

Published as a conference paper at ICLR 2023
UNDERSTANDING THE ROLE OF NONLINEARITY IN TRAINING DYNAMICS OF CONTRASTIVE LEARNING
Yuandong Tian Meta AI (FAIR) yuandongemeta.com
ABSTRACT
While the empirical success of self-supervised learning (SSL) heavily relies on the usage of deep nonlinear models, existing theoretical works on SSL understanding still focus on linear ones. In this paper, we study the role of nonlinearity in the training dynamics of contrastive learning (CL) on one and two-layer nonlinear networks with homogeneous activation h(x)) = h (x)... We have two major the- oretical discoveries. First, the presence of nonlinearity can lead to many local optima even in I-layer setting, each corresponding to certain patterns from the data distribution, while with linear activation, only one major pattern can be learned. This suggests that models with lots of parameters can be regarded as a brute-force way find these local optima induced by nonlinearity. Second, in the 2-layer case, linear activation is proven not capable of learning specialized weights into diverse patterns, demonstrating the importance of nonlinearity. In addition, for 2-layer setting, we also discover global modulation: those local patterns discrimi- native from the perspective of global-level patterns are prioritized to learn, further characterizing the learning process. Simulation verifies our theoretical findings.
INTRODUCTION
Over the last few years, deep models have demonstrated impressive empirical performance in many disciplines, not only in supervised but also in recent self-supervieed setting (SSL), in which models are trained with surrogate loss (e.g.. predictive (Devlin al. [0188] He et al. [021]. ) contrastive (Chen
ctt al. 2020 Caron et al. 2020 He et al. 2020) or noncontrastive loss (Grill et al. 2020 Chen & He 2020 and its learned representation then used for downstream tasks.
From the theoretical perspective, understanding the roles of nonlinearity in deep neural networks is one critical part of understanding how modern deep models work. Currently, most works focus on
linear variants of deep models (Jacot et al. 2018 Arora et al., 2019a Kawaguchi 2016, Jing et al.
2022 Tian et al. 2021 Wang et al.) 2021). }. When nonlinearity involved, deep models are often
treated as richer families of black-box functions than linear ones (Arora et al. 2019b] HaoChen et al.
202I). The role played by nonlinearity is also studied, mostly on model expressibility (Gühring et al.
2020 Raghu et al. 2017 Lu et al. 2017) in which specific weights are found to fit the complicated structure of the data well, regardless of the training algorithm. However, many questions remain open: if model capacity is the key, why traditional models like k-NN (Fix & Hodges 1951) kernel SVM (Cortes& & Vapnik 1995) do not achieve comparable empirical performance, even if theoretically they can also fit any functions (Hammer & Gersmann 20033 Devroye al.) 1994). Moreover, while traditional ML theory suggests carefully controlling model capacity to avoid overfitting, large neural models often generalize well in practice (Brown al. 2020 Chowdhery et al. 2022).
In this paper, we study the critical role of nonlinearity in the training dynamics of contrastive learning (CL). Specifically, by extending the recent a-CL framework (Tian) 2022) and linking it to kernels (Paulsen & Raghupathi] 2016), we show that even with 1-layer nonlinear networks, nonlinearity plays a critical role by creating many local optima. As result, the more nonlinear nodes in I-layer networks with different initialization, the more local optima are likely to be collected as learned patterns the trained weights, and the richer the resulting representation becomes. Moreover, popular loss functions like InfoNCE tends to have more local optima than quadratic ones. In contrast, in the linear setting, contrastive learning becomes PCA under certain conditions (Tian) 2002). and only the most salient pattern (i.e., the maximal eigenvector of the data covariance matrix) is learned while other less salient ones are lost, regardless of the number of hidden nodes.
Based this finding, extend analysis to 2-1ayer ReLU setting with non-overlapping receptive fields. In this setting, we prove the fundamental limitation of linear networks: the gradients of multiple weights at the same receptive field are always co-linear, preventing diverse pattern learning.

---

Published as a conference paper at ICLR 2023
Finally, we also characterize the interaction between layers in 2-layer network: while in each receptive field, many patterns exist, those contributing to global patterns are prioritized to learn by the training dynamics. This global modulation changes the eigenstructure of the low-level covariance matrix so that relevant patterns are learned with higher probability.
In summary, through the lens of training dynamics, we discover unique roles played by nonlinearity which linear activation cannot do: (1) nonlinearity creates many local optima for different patterns of the data, and (2) nonlinearity enables weight specialization to diverse patterns. In addition, we also discover a mechanism for how global pattern prioritizes which local patterns to learn, shedding light on the role played by network depth. Preliminary experiments on simulated data verify our findings.
Related works. Many works analyze network at initialization (Hayou et al., 2019; Roberts et al. 2021) and avoid the complicated training dynamics. Previous works (Wilson et al.) 1997 Li & Yuan
2017, Tian et al. 2019; Tian 2017 Allen-Zhu & Li 2020) that analyze training dynamics mostly focus on supervised learning- Different from (Saunshi et al. (2022): Ji et al. (202T) that analyzes feature learning process in linear models of CL, we focus the critical role played by nonlinearity, Our analysis is also more general than Li & Yuan (2017) that focuses on I-layer ReLU network with symmetric weight structure trained on sparse linear models. Along the line of studying dynamics of contrastive learning. Jing et al. 2022) analyzes dimensional collapsing on and 2 layer linear networks. Tan (022) proves that such collapsing happens in linear networks of any depth and further analyze ReI.U scenarios but with strong assumptions (e.g., one-hot positive input). Our work uses much more relaxed assumptions and performs in-depth analysis for homogeneous activations.
PROBLEM SETUP
Notation. In this section, we introduce our problem setup of contrastive learning. Let me ~ PD(.) be sample drawn from the dataset, and æ ~ Paug(-1as (t)) be augmentation view of the sample Ey. Here both Vo and æ are random variables. f == f(x; 0) be the output of deep neural network that maps input æ into some representation space with parameter 0 to be optimized. Given a batch of size N, [ represent i-th sample (i.e., instantiation) of corresponding random variables, and æ and afi'] are two of its augmented views. Here x|-] has 2.V samples. 1 I S N and N +1 i' 2N..
Contrastive learning (CL) aims to learn the parameter 0 so that the representation f are distinct from each other: want to maximize squared distance diy := [ fb]l between samples i # and minimize df == If [ f('lll 2 between two views [ii] and æ from the same sample zo[i].
Many objectives in contrastive learning have been proposed to combine these two goals into onc. For example, InfoNCE (Oord et al. 2018) minimizes the following (here T the temperature):
N log
exp(-df/1)
Lnee
c ecxp(
/ f4z exp( (xp(-opp/T) dTy/T)
In this paper, we follow a-CI. Tian 2022) that proposes a general CL. framework that covers a broad
family of existing CL losses. o-CL. maximizes an energy function & (0) using gradient ascent:
0,41 0. VV
where 1 the learning rate, sg(.) is the stop gradient operator, the energy function (0) :
If fl and Col.. is the contrastive covariance TTin 2022 Jing et al. 2022
N
C. Ca b] = 2N2
Σ ビ-=1
ag [aal]] - abb - bbiiT - -aali] - alD D
(3)
One important quantity is the pairwise importance (0)) = [axy (0) [o)] which are N weights on pairwise pairs of N samples in batch. Intuitively, these weights make the training focus more on hard negative pairs, i.c., distinctive sample pairs that are similar in the representation space but are supposed to be separated away. Many existing CL losses (InfoNCE, triplet loss, etc) are special cases of a--CL Tian) 2 by choosing different (()), e.g., quadratic loss corresponds to aij const and InfoNCE (with e 0) corresponds to oij == exp( /T) Σソ exp( exp(-d?//T)
For brevity C. [x]] := C. æ). For the energy function E, (0) trC, (x; 0)], in this work we mainly study its landscape, i.e., existence of local optima, their local properties and overall
Compared Tian 2022.. our C. definition has an additional constant term 1/2N2 2 simply the notation.
2

---

Published as a conference paper at ICLR 2023
distributions, where f is nonlinear network with parameters 0. Note that in Equ. 2 the stop gradient operator sg(a) means that while the value of a may depend on 0, when studying the local property of 0, makes no contribution to the gradient and should be treated as independent variable.
Since Ca is an abstract mathematical object with complicated definitions, as the first contribution, we give its connection to regular variance V..). if the pairwise importance has certain kernel structures (Ghojogh et al. 2021 Paulsen & Raghupathi, 2016):
Definition 1 (Kernel structure of pairwise importance a... There exists a (kernel) function K(---) so that aij [i wo [i]). Here K. satisfies the decomposition K(a, b) Φ (a)
E ( (b) with non-negative high-dimensional mapping Φ6.)) [dx(+)] 0.
Definition 2 (Adjusted PDF fr(x)), For l-th component 61 of the mapping Φ, we define the adjusted
density (1; a:) == =.( oi (x; P) (z). where a(a)) := ( 2 is the normalizer.
Obviously 0aj (uniform a corresponding to quadratic loss) satisfies Def. I with ID mapping Φ=1. 1. Here we show non-trivial case, Gaussian a, whose normalized version leads to InfoNCE:
Lemma 1 (Gaussian o:). For any function g(.) that is bounded below, if we use Cij exp(-Ilg(zzo[i) g (22) as the pairwise importance, then it has kernel structure (Def.
Note that Gaussian a computes 2 pairwise distances using un-augmented samples Lo. while InfoNCE (and most of CL losses) uses augmented views and x' and normalizes along one dimension to yield asymmetric a'jy. Here Gaussian a is a convenient tool for analysis. We now show Ca a summation of regular variances but with different probability of data, adjusted by the pairwise importance a that has kernel structures, Please check Appendix A. for detailed proofs.
Lemma 2 (Relationship between Contrastive Covariance and Variance in large batch size). If a satisfies Def. [ then for any function g()), C. [a()) is asymptofically PSD) when N +00:
Co (o)g(()) + Σ V (vra)(()a)) [aa-paee (1200) ((=))(())(())
(4)
Corollary (No augmentation and large batchsize). With the condition of Lemma 2 if we further assume there is augmentation (i.e., Pang (x| = ō(x σo)). then C. Eg]g] - 2 lg.
3 ONE-LAYER CASE
Now let us first consider 1-layer network with K hidden nodes: f(x; 0) h(Wx), where W [w....., wx] E R Kxd
{W} and h(z) the activation. The k-th row of W is a weight
wt and its output is f& == hww x). In this case, trCa[f] = Σk= [fk]. We consider per-filter normalization [wxl 2 which can be achieved by imposing BatchNorm (Ioffe & Szegedy 2015)
at each node k Tian 2022). In this case, optimization can be decoupled into each filter wt:
K
max E. (0)
=
max 2 || DSKK
CrC [f]=
= 2
Σ
max Ca (N x:)
(5)
1
Now let's think about, which parameters Wi maximizes the summation? For the linear case, since C. [h(w] æ)]= Ca[w x] w Ca([] w. all wy converge to the maximal eigenvector of C, [x] (a constant matrix), regardless how they are initialized and what the distribution of x is. Therefore, the linear case will only learn the most salient single pattern due to the (overly-smooth) landscape of the objective function, a winner-take-all effect that neglects many patterns in the data.
In contrast, nonlinearity can change the landscape and create more local optima in Ca[h(w" [T),, each capturing one pattern. In this paper, we consider a general category of nonlinearity activations:
Assumption 1 (Homogeneity (Du et al. /ever/ieyyy (Tian et al. 2020 The activation satisfies h(x) = h' (z)x.
Many activations satisfy this assumption, including linear, ReLU, Leaky and monomial activa- tions like h(x) x² (with an additional global constant). In this case have:
h(w xx) w h a:) 5
3

---

Published as a conference paper at ICLR 2023
070
Power Iteration
h(W*x)
0,223
w
Cul x1
C |
0.055
0.000
[al 2layer network
Linear
Non-
Figure 1: Left: Summary of Sec. (a) We analyze the dynamics of one-layer network ((w 2) under CL loss (Eqn.2) (b) With linear activation h(x)
then there is only one fixed point (PCA direction). (c) Non-linear activation h(x) creates many critical points and proper choice of pairwise importance a make them local optima, enabling learning diverse features. Right: Convergence patterns (iteration f versus iteration discrepancy [/ + 1) 2 of Power Iteration (Eqn. PI) in latent summation models, when ||
T|]2
is small but non-zero. In this case, Theorem 3 tells there still exist local optima close to each umm-
where Tnd := x (2ww" x) is the input data after nonlinear gating. When there is no ambiguity, we just write - as ä and omit the weight superscript. One property is C., [h(w æ)] w C=( Jw.
Now let A(w) Ca(a With the constraint ||l|| = 1, the learning dynamics is:
Lemma (Training dynamics of I-layer network with homogeneous activation in contrastive learn- ing). The gradient dynamics of Equ. 5is is (note that o is treated as an independent variable):
wy Pub. A(wx))w
Here Pw. : I- --1- projects vector into the complementary subspace spanned by wk-
See Appendix B.2 for derivations. Now the question that: what is the critical point of the dynamics and whether they are attractive (i.e., local optima). In linear case, the maximal eigenvector is the one fixed point; in nonlinear case, we are looking for locally maximal eigenvectors, called LME.
Definition 3 (Locally maximal eigenvector (LME)). w. is locally maximal eigenvector of A(w), if A(w.)w. = X_ w., where X = Amax (A(w.) (w)) ) is the distinct maximal eigenvalue of A(w.).
It is easy to see each LME is critical point of the dynamics, since P.l,, A(w, A(w.)w. Ww AP w. 0.
3.1 EXAMPLES WITH MULTIPLE LMES IN RELU SETTING
To see why the nonlinear activation leads to many LMEs Eqn. 7 we first give two examplar generative models of the input that show Eqn. F multiple critical points, then introduce more general cases. To make the examples simple and clear, we assume the condition of Corollary [ (no augmentation and large batchsize), and let aij = 1. Notice that zt is deterministic function of therefore A(w)= := Ca [ = V(z"). We also use ReLU activation h(z) = max( 0).
Let U [u...... und be orthonormal bases (u,,, um I(m m')). Here are two examples:
Latent categorical model. Suppose y is a categorical random variable taking M possible values, P(æly m] 6(x ). Then we have (see Appendix [..] for detailed steps):
A(w) u= = C, [ = V[ = Pfy = m] Ply = ml)umm um
(8)
Now is clear that w um an LME any m.
Latent summation model. Suppose there is latent variable so that x Uy. where
y : [y1, //. )- Each yon standardized Bernoulli random variable: Efym] and E v = This means that ym = yhh = v(1 - qm)/ qm with probability Im and Um Um = 9m 9m) with probability 1 - Jm- For my # m2, Dmn and Dm, are in-
dependent. Then we have:
A(w) w=u... := C, [
V +
(1 ) un + 9m (I u Tn)
(9)
which has maximal and distinct eigenvector of um with unique eigenvalue (1 9m) when 4m 2 (3 v5) x 0.382. Therefore, different w leads to different LMEs.
In both cases, the presence of ReLU removes the "redundant energy" so that A(w) can focus on specific directions, creating multiple LMEs that correspond to multiple learnable patterns. The two examples can be computed analytically due to our specific choices on nonlinearity h and a.
4

---

Published as a conference paper at ICLR 2023
3.2 RELATE LMES TO LOCAL OPTIMA
Once LMEs are identified, the next step is to check whether they are attractive, or stable critical points, or local optima. That is, whether the weights converge into them and stay there during training. For this, some notations are introduced below.
Notations. Let (x(w)) be the i-th largest eigenvalue of A(w), and (r(w)) the corresponding unit eigenvector, Agap (w) := A1 (w) X2( (2) the eigenvalue gap. Let p(w) be the local roughness measure: p(w) is the smallest sealar to satisfy [I(A()) A(w))urll2 S p(w)) ((ww)]lo-e 11l---ll--0000 ([ in local neighborhood of w. The following theorem gives a sufficient condition for stability of w.:
Theorem (Stability of w*). If w. is LME of A(w.) and ( > p(w,), then w. stable.
This shows that lowering roughness measure p(w.) at critical point w, could lead to more local optima and more patterns to be learned. To characterize such behavior, we bound p(w.):
Theorem 2 (Bound of local roughness p(w) in ReLU setting). If input || S Co is bounded, has kernel structure (Def. and batchsize N + +o0, then p(w.) S C3v) r r(w,, a), where
r(w, a) Σt zi =a) m P((;,))
From Thm. 2 the bound critically depends on r(a) that contains the adjusted density pr (a;; a) (Def. 2 at the plane w. a: 0. This is because local perturbation of w. leads to data inclusion/exclusion close to the plane, and thus changes p ((w.). Different a leads to different Pi (z; a),, and thus different upper bound of p(w.). creating fewer or more local optima (i.e., patterns) to learn. Here is an example that shows Gaussian a (see Lemma D]. whose normalized version is used in InfoNCE, can lead to more local optima than uniform a, by lowering roughness bound characterized by r a):
Corollary 2 (Effect of different 0:). For uniform Ou (aij == 1) and I-D Gaussian og (Oij == - h(w w zo (13)))11//22) we have r(w,, ag) = 20 zo(ag))(( (r.. au) with zo (ogg)) == (epp--A2(e)) /2) dx S 1. As result, zu(ag) << 1 leads to r(w., ag)) < r(w,, au).
exp(- exp(-1[h(w' ( T =oll))
In practice, zu =u(( can be exponentially small (e.g., when most data appear on the positive side of the weight w.) and the roughness with Gaussian a can be much smaller than that of uniform a, which is presumably the reason why InfoNCE outperforms quadratic CL loss (Tian 2022).
3.3 FINDING CRITICAL POINTS WITH INITIAL GUESS
In the following, we focus on how can we find an LME, when A(w) does not have analytic form. We show that if there is an "approximate eigenvector" of A(w) C. [#=), then real one is nearby.
Let L be the Lipschitz constant of A(w): [[A(w) - A(w") A(w')l2 < L|| - w'll2 for any w, w' on the unit sphere |/|| 1, and the correlation function c(w)= == w Φi (w) be the inner product between w and the maximal eigenvector of A A(w). We can construct a fixed point using Power Iteration (PI) (Gllb & Van Loan 2013), starting from initial value
(0))
wwl 1) ((zn()))ur())) ((ur(())ur())l
(PI)
We show that even A(w) varies over |ul|| 1, the iteration can still converge to fixed point w., if the following quantity (ww), called irregularity, is small enough.
Definition 4 (Irregularity w(w) in the neighborhood of fixed points). Let p(w) = .5(1 c(w))c [1 (ww) Agap (w) (w) (ww) and w(w) = w(c(w), Agap \1 L, 2 0 defined
as
w (w) == u(w) + 2xL2 (1 + u(w)c(w)) + 2LA gap (w) / / w (1 + (1 ((w)c(w)), here x is the high-order eigenvector bound defined in Appendix (Lemma
(10)
Intuitively, when w()) is sufficiently close to any LME w., i.c. w()) is an "upproximate" LME, we have w (w)( < 1. In such a case, (0) can be used to find w, using power iteration (Eqn. Pl.
Theorem (Existence of critical points). Let Co := c(w(O)) # 0. If there exists 7 < so that: sup w(w) S 7: wEB,
where By =
{ ww: w (()) 2 so := T-c,
2 is the neighborhood of initial value w()). T+a
Then Power Iteration (Fqn. P7 converges to a critical point w. E B., Eqn.
5

---

Published as a conference paper at ICLR 2023
z= 0
==
z=
U
R2
[Wam]
[Wam
[Wam]
R₂
Ra
X1
X2
X3
R₁
R₂
R₂
(a] 2-layer network
(b) Conditional Independence
Figure 2: Our setting for 2-layer network. (a) We use W for low-layer weights and V for top-layer weights. There are K disjoint receptive fields (abbreviated RF) Rs, each with M weight vectors in the low-layer, denoted as Wkm. The activation function of hidden layer nodes h(x) and can be linear or nonlinear. (b) Conditional independence in Assumption 2 there exists a global categorical variable 2. Given 2, variation in different RFs are assumed to be independent.
See proof in Appendix B.4. Intuitively, with L and small, co close 1, and Agap large, Eqn. can always hold with < and the fixed point exists. For example, for the two cases in Sec.3..17 U [u....., uMd] is only approximately orthogonal (i.e., U - I is not zero but small), and/or the conditions of Corollary hold roughly, then Theorem tells that multiple local optima close to Ume still exist for each m (Fig. D We leave it for future work further relax the condition.
Possible relation to empirical observations. Since there exist many local optima in the dynamics (Eqn. 77. even if objective involving Wi are identical (Eqn. [5), each wt may still converge to different local optima due to initialization. We suspect that this can be a tentative explanation why larger model performs better: more local optima are collected and some can be useful. Other empirical observations like lottery ticket hypothesis (LTH) (Frankle & Carbin 2019; Morcos et al.) 2019 Tian jet al. 2019: Yu et al. 2020), recently also verified in CL (Chen et al. [2021), may also be explamed similarly. In LTH, first large network is trained and pruned to be small subnetwork S, then retraining S using its original initialization yields comparable or even better performance, while retraining S with different initialization performs much worse. For LTH,, our explanation is that S contains weights that are initialized lnckily, i.c., close to useful local optima and converge to them during training. We leave a thorough empirical study to justify this line of thought for future work.
Given this intuition, it is tempting to study the distribution of local optima of Eqn. 7 their atfractive basin Basin(w.) := (w : (0) w. lim;-++0c w(t) w. for each local optimum w., and the probability of random initialized weights fall into them. Interestingly, data augmentation may play an important role, by removing unnecessary local optima with symmetry (see Appendix B.5). focusing the learning on important patterns. Theorem 3 also gives hints. A formal study is left for future work.
4 TWO-LAYER SETTING
Now we understand how 1-layer nonlinearity learns in contrastive learning setting. In practice, many patterns exist and most of them may not be relevant for the downstream tasks. A natural question arises: how does the network prioritizes which patterns to learn? answer this question, we analyze the behavior of 2-layer nonlinear networks with non-overlapping receptive fields (Fig. (a)).
Setting and Notations. In the lower layer, there are K disjoint receptive fields (abbreviated as RF) {Ra}, J. each has input &y and M weight Wkm Rd where -1...M M. The output of the bottom-layer is denoted as fi, fikm for its km-th component, and [i for i-th sample. The top layer has weight V E Ro KKM Define S V V. As the (km, k m') entry of the matrix S, 8km R'mm
[S] -um Uk'm'.
At each RF Rg. define 3km as an brief notation of gated input T.. == Dg
2x). Define H = [K11: Dzz; L E Md as the concatenation of 2km and finally ø := ...::.: Øx] E Mdd is the concatenation of all ž,. Similarly, let wa [wmmlM
R Md be concatenation of all Wkm in the same RF Re. and w == w E IR Mdd be a column concatenation of all wn.
1M
Finally, P.L = diagam! [P.L_ Wem. is a block-diagonal matrix putting all projections together.
Lemma (Dynamics of 2-layer nonlinear network with contrastive loss).
V = VC.lff)
i P [(S 1.17) C. [
(12)

---

Published as a conference paper at ICLR 2023
where 1a is d-dimensional all-one vector, @ is Kronecker product and o is Hadamard product.
See Appendix C.I for the proof. Now we analyze the stationary points of the equations. If [f]] has unique maximal eigenvector then following similar analysis as in Tian (202)), a necessary condition for (W, V) to be stationary point is that V vs" where v is any arbitrary unit vector. Therefore, we have S = V = 88 as rank-1 matrix and 8km.k'mm 8km88 Note that 8, as a unique maximal eigenvector of C. [fi], is a function of the low-level feature computed by W.
On the other hand, the stationary point of W can be much more complicated, since it has the feedback term S from the top level. A more detailed analysis requires further assumptions, as we list below: Assumption 2. For analysis of two-layer networks, we assume:
Uniform a, large batchsize and no augmentation. Then Calg(x)] V[g(æ)] for any
function g(-) following Corollary
Fast top-level training. V undergoes fast training and has always converged to its stationary point given C. That is, S = ss" a rank-1 matrix;
Conditional Independence. The input in each Rg are conditional independent given a latent global random variable z taking C different values:
K
II P[æx|=] R=1
(13)
Explanation of the assumptions. The uniform a condition mainly for notation simplicity. For kernel-like the analysis is similar by combining multiple variance terms using Lemma
1
The no augmentation condition is mainly technical. Conclusion still holds if Ep..n (g(x) [c)] R
glEppane [x æol) for gæx) := v i.e., augmentation swaps with nonlinear gating. For conditional independence, intuitively z can be regarded as different type of global patterns that determines what input æ can be perceived (Fig. ()). Once 2 is given, the remaining variation resides within each RF RR and independent across different Rg- Note that there exists many patterns in each RF Rg. Some parts of the global pattern z, and others may come from noise. We study how each weight Wkm captures distinct and useful patterns after training.
With all the assumptions, we can compute the term Ag (wx) == [a( V( Our Assumption is weaker than orthogonal mixture condition in Tian 2022) that is used to analyze CL, which requires the instance of input æ [i] to have only one positive component.
4.1 WIYY NONLINEARITY CRITICAL: LINEAR ACTIVATION FAILS
Since in each RF R2, there are M filters (w)m) it would be ideal to have one filter to capture one distinct pattern in the covariance matrix Ag. However, with linear activation, Ty and as result, learning of diverse features never happens, no matter how large M is (proof in Appendix C.4]: Theorem 4 (Gradient Colinearity in linear networks). With linear activation, W follows the dynamics: Wmm = 8km ba (W.V) V)
(14)
where by (W,V) C.. [Bg Ex. m mk W W. Dx is a linear function w.r.t. W. As a result, (1) imm are co-linear over m, and (2) If 8km + O, from any critical point with distinct {wkmm }, there exists a path of critical points to identical weights (Wkm= wy))
This brings about the weakness of linear activation. First, the gradient of Wem within one RF R during CL training all points towards the same direction by: Second, even if the critical points Whe have any diversity within RF Rx. there exist path for them to converge to identical weights. Therefore, diverse features, even they reside in the data, cannot be learned by the linear models.
4.2 THE EFFECT OF GLOBAL MODULATION THE SPECIAL CASE OF C 2 AND M 1
When z is binary (C = 2) with a single weight per RF (M = 1). wn 's dynamics has close form. Let иy represent Wk1, the only weight at each Rg. Ae E f 1 E. [ 0). We have:
Theorem 5 (Dynamics of we under conditional independence). When C = and M 1, the dynamics of wy is given by (sk and dz 2 0 are scalars defined in the proof):
tik
PiL. (se (xxx)) 5g Ax wk
(15)
7

---

Published as a conference paper at ICLR 2023
ACCEBIAFDS
concat( Mei Mg, Mga.. Me.
"'C'B'A'D*
Positive pairs
CECIBEAEDA
concat( Up, Me, Mp ... M4d
Negative pairs
G'E.B.DF"
GAECBEDPGC
concat MA. Mp. Mg Mc)
Generator
Input sequence
Input
Figure 3: Experimental setting (Sec. 5). When generating input, we first randomly pick one generator (e.g.- ** = from a pool of G generators, generate the sequence by instantiating wildcard with arbitrary token, and then replace the token a of sequence with an embedding vector u. to form the input æ. Inputs from the same generator are treated as positive pairs, otherwise negative pairs for contrastive loss.
conditate takens
candidate
P-5 can dandidate tokons por
P-10 candidate
Inas
cuedrali:
Deg
rupprnmdattttion P-1 canditite tokees
Degres oxspenmdattaadn
P-1 cendidate tokens per RF
P-1 randidate tntess per 8p
P-11 candidae tobens BT
Ortee JUP02
10
38-
Iolkyrkk
Ovrrdt mareing
Octte www.orrrrrroooooo
ugmid
10
Degrns oeveperrendetcaaan
Dog copparameeeeeeoo
Degres toepod/opaaaaaatttaaaoooooo
Degrne deveppermdoetealln
Figure 4: Overall matching score X+ (Eqn. 16) with InfoNCE (top row) and quadratic loss (bottom row).
When P = 1, linear model works well regardless of the degree of oovatttrrattiiiizationn B3, while ReLU requires large over-parameterizaaion perform well. When each Rg has multiple patterns (P 1) related generators, ReLU models can capture diverse patterns better than linear ones the wer-parameterizztton region We found similar trend for other homogeneous activations such as LeakyReLU (with negative slope 0.05) and quadratic. In contrast, linear models are much less affected by over parameteriizttinn While the trends are similar, quadratic loss is not effective InfoNCE in feature learning. Each setting repeated times and mcan/std reported. See Appendix (Fig. 9 and Fig. 10) for X-
See proof in Appendix C.3 There are several interesting observations. First, the dynamics are decoupled (i.e., wh (+ and other wy with k' * k only affects the dynamics of wa through the matrix A (W). Second, while Ag (wx) contains multiple patterns (i.e., local optima) in Rg, the additional term A, A the global modulation from the top level, encourages the model to learn the pattern like A& which is discriminative feature that separates the event of = = 0 and
1. Quantitatively:
Theorem (Global modulation of attractive basin). If the structural assumption holds: Ag(w)) Σ, (u, uuu with g(-) > 0 a linear increasing function and {wi} orthonormal bases, then for A + cuju, its attractive basin of wt us is larger than Ag 's for e >> 0.
Therefore, if A is LME of Ag and we is randomly initialized, Thm tells that P(ws AA] is higher than the probability that uy goes to other patterns Ag. i.e., the global variable z modulates the training of the lower layer. This is similar to "Backward feature correction" (Allen-Zhu & Li 2020) and "top-down modulation" " (Tian et al. 2019) in supervised learning, here we show it in CL.
We also analyze how BatchNorm helps alleviates diverse variances among RFs (see Appendix D
EXPERIMENTS
Setup. To verify our finding, we perform contrastive learning with a 2-layer network on a synthetic dataset containing token sequences, generated follows. From a pool of G 40 generators, we pick a generator of length K in the form of * C A (here K = 10) and generate EFCDBAACDE by sampling from d 20 tokens for each wildcard The final input æ is then constructed by replacing each token a with the pre-defined embedding u, E Rd {u,) forms a orthonormal bases (see Fig. 3). The data augmentation is achieved by generating another sequence from the same generator.
8

---

Published as a conference paper at ICLR 2023
14
14
16
16
26
12-
14
14
14
Figure 5: Visualization of learned weights with P P= 3 (3 local patterns related to generators at cach RF) and B 5 (5x over parmmcteriization.... Each of the K = 10 subfigures corresponds RF (Ro-Rs). In each subfigure, the left panel is the learned weight by ReLU, while the right panel is from lincar activations. 15 rows corresponds to M 3P 15 weights and each weight d = dimensional. With ReLU activation, learned weights clearly capture the 3 candidate tokens within R2 at each RF Rg. while linear activation cannot.
While there exists 20 tokens, each RF R& we pick subset R of P d tokens as the candidates used in the generator, to demonstrate the effect of global modulation. Before training, each generator is created by first randomly picking 5 receptive fields, then picking one of the P tokens from Rf at each RF Rs and filling the remaining RFs with wildcard s. Therefore, if token appears Rg but a & R. then a must instantiated from the wildcard. Any a & R is noise and should not to be learned in the weights of R₃ since it is not part of any global pattern from the generator.
We train a 2-layer network on this dataset. The 2-layer network has K = 10 disjoint RFs, within each RF, there are M 3P filters. Here 3 > is hyper-parameter that controls the degree of over-parameterizatioon
The network is trained with InfoNCE loss and SGD with learning rate 2 10 momentum 0.9, and weight decay 5 10 for 5000 minibatches and batchsize 128. Code is in PyTorch runnable on a single modern GPU.
Evaluation metric. We check whether the weights corresponding to each token is learned in the lower layer. At each RF Rg, we know Re the subsets of tokens it contains, as well as their embeddings au due the generation process, and verify whether these embeddings model is trained. Specifically, for each token a R. we look for its best match on the learned filter {Wkm). ). as formulated by the following per-RF RF score X+ (Rx) and overall matching score
learned after the
X+ E [-1, as the average over all RFs (similarly we can also define X- for a & R$):
(+(R))
1
Σ ag R
W km
X+
1
X
(16)
[/ 12 Uulll
K
5.1 RESULTS
Linear v.s ReLU activation and the effect of over-parameterization (Sec. 4.1) From Fig. 4 we can clearly see that ReLU (and other homogeneous) activations achieve better reconstruction of the input patterns, when each RF contains many patterns (P > 1) and specialization of filters in each RF needed. On the other hand, when P linear activation works better. ReLU activation clearly benefits from over over-varanen parameterization (5 > 1): the larger 3 is, the better X- becomes. In contrast, for linear activation, over-vveeaaaae vver-parameterization does not quite affect the performance, which consistent with our theoretical analysis.
Quadratic versus InfoNCE, Fig. shows that quadratic CL. loss underperforms InfoNCE, while the trend of linear/ReLU and over-parameterizaaion remains similar. According Corollary 2 non- uniform a (c.g., Gaussian a, Lemmal] [) creates more and deeper local optima that better accommodate local patterns, yielding better performance. This provides novel landscape point of view why non-uniform a is better, expanding the intuition that it focuses more on important sample pairs.
Global modulation (Sec. 4.2 As shown in Fig. 5 the learned weights indeed focus the token subset R that receives tow- support from the generators and no noise token is learned. We also verify that quantitatively by computing X- over multiple runs, provided in Appendix (Fig. 10)

---

Published as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zin and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning, arXiv preprint arXiv:2001.044: 2020.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. In International Conference on Learning Representations, 2019a.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv: 1902.0929,, 2019b.
Mary I. Boas and Philip Peters. Mathematical methods in the physical sciences, 1984.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neurul information processing systems, 33:1877-1901, 2020.
James R Bunch, Christopher P Nielsen, and Danny C Sorensen. Rank-one modification of the symmetric eigenproblem. Numerische Mathematik, 31(1):31-48, 1978.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. In NeurIPS, 2020.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Michael Carbin, and Zhangyang Wang. The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 19306-16316 2021.
Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp- 1597-1607. PMLR, 2020.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In CVPR, 2020.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick. Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyc7, Er- ica Moreira, Rewon Child, Öleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language model- ing with pathways. CoRR, abs/2204.02311, 2022. doi: 10.48550/axi..2244..3311 URL
22110
Corinna Cortes and Vladimir Vapnik. Support- networks. Machine learning, 20(3)27332977, 1995.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 1966)141-143 2012.
2012.
Jacob Devlin, Ming-We Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: /8 10.04805, 2018.
Lue Devroye, Laszlo Gyorfi, Adam Krzyzak, and Gábor Lugosi. On the strong universal consistency of nearest neighbor regression function estimates. The Annals of Statistics, 22(33:1371-133 1994.
10

---

Published as a conference paper at ICLR 2023
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. arXiv preprint arXiv: 100.00000000000, 2018
Francisco Fernández. Introduction to perturbation theory in quantum mechanics. CRC press, 2000.
Evelyn Fix and Joseph Lawson Hodges. Nonparametric discrimination: consistency properties. Randolph Field, Texas, Project, pp. 21-49, 1951.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019. URL https
Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, and Mark Crowley. Reproducing kernel hilbert space, mercer's 's theorem, eigenfunctions, nystr\ om method, and use of kernels in machine learning: Tutorial and survey. arXiv preprint 1.kiv:2106.0844:: 2021.
Mike B Giles. Collected matrix derivative results for forward and reverse mode algorithmic differen- tiation. In Advances in Automatic Differentiation, pp. 35 44. Springer, 2008
Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
Alain Goriely and Craig Hyde. Finite-time blow-up in dynamical systems. Physics Letters A, 250 (4-6):311-318 1998.
Jean-Basticn Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent: A new approach to self-supervised learning. NeurlPS, 2020.
Ingo Gühringg Mones Raslan, and Gitta Kutyniok. Expressivity of deep neural networks. arXiv preprint wrXiv:2007.04759 2020.
Barbara Hammer and Kai Gersmann. note on the universal approximation capability of support vector machines. neural processing letters, 17(1):43-555 2003.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self supe-suue deep learning with spectral contrastive loss. NeurlPS, 2021.
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. On the impact the activation function on deep neural networks training. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2672-2680 PMLR, 09-15 Jun 2019. URL https://
proceedings mlr. www.m.rr..esseeem.mmme press wwt.pp/ees///////////// 9a. html
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729-9738, 2020.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. arXiv preprint arXiv:2111.06377 2021.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Wenlong Ji, Zhun Deng, Ryumei Nakada, James Zou, and Linjun Zhang. The power of contrast for feature learning: A theoretical analysis. arXiv preprint 10.04:21 2021.
Li Jing, Pascal Vincent, Yann LeCun, and Yuandong Tian. Understanding dimensional collapse in contrastive self-supervised learning. ICLR, 2022.
Kenji Kawaguchi. Deep learning without poor local minima. NeurIPS, 2016.

---

Published as a conference paper at ICLR 2023
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. Advances in neural information processing systems, 30, 2017.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems, 30, 2017.
Ari Morcos, Haonan Yu, Michela Paganini, and Yuandong Tian. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. Advances neural information processing systems, 32, 2019.
Aaron den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint /807.03745 2018.
Vern I Paulsen and Mrinal Raghupathi. An introduction to the theory of reproducing kernel Hilbert spaces, volume 152. Cambridge university press, 2016.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In international conference on machine learning, pp. 2847-2854. PMLR, 2017.
Daniel A. Roberts, Sho Yaida, and Boris Hanin. The principles of deep learning theory. CoRR, abs/2106.10165, 2021. URL
Nikunj Saunshi, Jordan Ash, Surbhi Goel, Dipendra Misra, Cyril Zhang, Sanjeev Arora, Sham Kakade, and Akshay Krishnamurthy. Understanding contrastive learning requires incorporating inductive biases. arXiv preprint arXiv:2202.14037. 2022.
John Michael Tutill Thompson, H Bruce Stewart, and Rick Turner. Nonlinear dynamics and chaos. Computers in Physics, 4(5):562-563, 1990.
Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In International Conference on Machine Learning, pp. 3404 3413. PMLR, 2017.
Yuandong Tian. Understanding deep contrastive learning via coordinate-wise optimization. NeurIPS. 2022.
Yuandong Tian, Tina Jiang, Qucheng Gong, and Ari Morcos. Luck matters: Understanding training dynamics of deep relu networks. arXiv preprint arXiv: 1en::9905..333. 13405, 2019.
Yuandong Tian, Lantao Yu, Xinlei Chen, and Surya Ganguli. Understanding self-supervised learning with dual deep networks. arXiv preprint arXiv:2010.00578, 2020.
Yuandong Tian, Xinlei Chen, and Surya Ganguli. Understanding self-supervised learning dynamics without contrastive pairs. In International Conference on Machine Learning, pp. 10278.10778 PMLR, 2021.
Xiang Wang, Xinlei Chen, Simon S Du, and Yuandong Tian. Towards demystifying representation learning with non-contrastive self-supervision. arXiv preprint arXiv:2110.04944 2021.
Charles I. Wilson, James I. Blue, and Omid M Omidvar. Training dynamics and neural network performance. Neural Networks, 10(5):907-922 1997.
Haonan Yu, Sergey Edunov, Yuandong Tian, and Ari S. Morcos. Playing the lottery with rewards and multiple languages: lottery tickets in rl and nlp. International Conference on Learning Representations, 2020. URL
net/ www.ooooduuiiiiooo S1x.xxx
12

---

Published as a conference paper at ICLR 2023
A PROOFS
A.1 PROBLEM SETUP (SEC.
Lemma (Gaussian a)) For any function g()) that is bounded below, if we use aij exp(-Ilg(zoli)) (zzo15i)1B/22) the pairwise importance, then it has kernel structure (Def. 7
Proof. Since (()) is bounded below, there exists vector vs so that each component of g 27 is always nonnegative for any a: y [i] = ( E Rdd, then y 2 0 and we have:
y [i]
asg = exp
(17)
2T
B [i]l
y
[yb
exp
exp
exp
(18)
2r
2r
And using Taylor expansion, we have
y [
y
[
y
1
exp
=
+ +...
+ +... (19)
7
7
2
kd!
Let
T 1/2 1112y
AllChoose (T
( =
(20)
AICChoos(T--12gg)
be an infinite dimensional vector, where AllChoose(y) k)) is a d di-dinnnsoaa column vector that enumerates all possible d products Vi, Via ..- Va. where I i I d and is the i-th component of y. Then it is clear that exp(y" [+/b////)] o ( and thus
0aj Φ (mo(i)))((amol)))
Σ ((mo())))()) 1=
(21)
which satisfies Def. 1 Here
| 1
[lg(()) 0112
Φ(x) = exp
x(v)
exp
Ö(g(z) v)
(22)
2r
the infinite dimensional feature mapping for input æ, and (xx))) is its 1-th component.
Lemma 2 (Relationship between Contrastive Covariance and Variance in large batch size). a
satisfies Def. 1 then for any function g(.), C. [g(x)) is asymptotically PSD when N - +00:
Calg(a)) + Σ 77 ( EEr-paee (- (
(4)
Proof. First let
N
Cinter (a,b) b)
any (a (b])) b(D)
(23)
2N
j
Cintra (a.b) b)
aij
(a(i) a [b] b(D
(24)
2N
N
1=1
jzt
and Cinter [a] = Cinter (a, a), Cintra
[a]
Cinter
[a, a].
Then we have
C. [g] Cittr g Cintra [g]
(25)
13

---

Published as a conference paper at ICLR 2023
With the condition, for the first term Chater [g], have
Cinter 9 2N2
Σ x(am001 g(=l))))(())) g(>bi))
(26)
When NV + +00, we have:
2 f
1
Cinter
- - g(y)) P( Poy yo)drdydaaddo
We integrate over zy and yo first:
/ (0(x)) ((v))(((() - g(v)) PP zo
IP (((r))))))))))))))
Doldy
(27)
E. mg 9g 1 +++,
E. 120 1gg 11 E. | gg 1p0 9 - B, yo gg mo mg 1
(28)
We now compute the four terms separately. With the condition that ( yo) = E, oi (2 oi (vo).
and the definition of adjusted probability pr(x=) =- के (()) where = f or (z) P dac, for the first term, we have:
f σn (1))) se lgg
/ E.10o l9g (20g))
(29)
of Panor F. 120 .9
(30)
So we have:
Cinter
Σ
of (B 9gg
[g] Baown E. (g lg
(31)
Σ
27 mon-rr ot (1
(32)
On the other hand, for Clatra [g]. when N + t00, we have:
Σ (( + / K(aro (o)o
Σ
ag
(33)
N
jz
= Σ (1(()) / ((oo))(( = Σ (10)
(34)
Therefore, have:
Cintra [g] + Σ f (1(2))(((x)) s(<'))(g(x) T(xx))TF(xx. FF(x, (o))(( dæy (35)
Similarly,
/ [(((x) - (o(z))-(='))(ol g(x1)) TP() (ooo))dd
(36)
2 f g(x)g (x))((((2))d - 2 g ((z)))((((0))) / g (a)))((a))))))
(xo)da'
(37)
2 2B (100)) lgg
B. paus (le0)) Bal æ0) mn)lg
(38)
23 a Paux (200) [g]
(39)
So have:
- Σ / dr(x0)2V x ampane (- Pg)
Cintra [g]
+
(40)
2
Σ 2f Eeeggrp W Vampau (m))
(41)
Using the law of total variation, finally we have:
Calgl + Σ 2f Wannp Eampane(-ann
(42)
14

---

Published as a conference paper at ICLR 2023
B ONE-LAYER MODEL (SEC.
B.I COMPUTATION OF THE TWO EXAMPLE MODELS
Here assume ReLU activation h(x) max(x; 0), which is homogeneous activation h(x) (x)x. Note that we consider (0) = 0. Therefore, for any sample 2, if w x = 0, then we don't
consider it to be included in the active region of ReLU, i.e., x= . x:) 0.
Let be a hidden binary variable and we could compute A(w) (here == Pp[= - 0] and p ==
F(z 1])
V(ø"1 = V. [ i w |=] + [V =]] pop pop: ( T (w) + Cow(() + p1 Eiii((M) (w)
(43)
where A(w) Ela
E[ 0] and (w) == V[
Latent categorical model. = Um let == I = m)) This leads to Σ₁ [u(m) Eo (2(mm =
and A (m Um Therefore, we have:
A(w) w= C. [x"] V[ I ml (1 Ply ml) Um Un
(44)
Latent summation model. If w = Um first notice that due to orthogonal constraints we have w Em ml Dm u Vmm Let == I(ym > 0), then
compute A(um) V Um
E1 (Um) I Um u and Eo (um) = 0. Therefore, have:
A(w) W=
C. [ "1
[ (1 9m) Um u + 9on (I- Un um
(45)
B.2 DERIVATION OF TRAINING DYNAMICS
Lemma (Training dynamics of I-layer network with homogeneous activation in contrastive learn- ing). The gradient dynamics of Eqn. 5 is (note that a is treated as an independent variable):
wh P.l. A(wy)
Here P 1 wwww projects a vector into the complementary subspace spanned by wk-
Proof. First of all, it is clear that from Eqn. 5 each uy, evolves independently. Therefore, we omit the subscript and derive the dynamics of one node w.
To compute the training dynamics, we only need to compute the differential of C, [h(w]] x:). We use matrix differential form (Giles) 2008) to make the derivation easier to understand.
Note that for one-layer network with K Ca [h(w]] x)) hwwT((awa x)] be the objective function be maximized. Using the fact that
1 nodes, E(w)
[C. x)]
C. [x. y] a bilinear form (linear w.r.t æ and y) given fixed a,
for any vector a and b, we have a' Ca (x yjb = [a(a" x; bTyy.
for scalar x and y. Ca(z, y] = Ca
and by the product rule d(x y) dx + x dy. we have:
dg = ] 1 ca(l(w" x)) h)), hww""'" u ")) m] L Calli(u ")d x, h(w m))
= Calh(WTad x), 1 N'ww x))xxjj
(46)
Now use the homogeneous condition (Assumption for activation h: h(x) = (2(2xx, which gives h(w" x) = nww x x)w x, therefore, we have:
d w Ca(h'(w (w h' (oooT))ajpe x))|dw T A(w)dw
(47)
where A(w)= == C. (w TT: J 1'(w x) = C. w w.. Therefore, by checking the coefficient associated with the differential form du, we know de = A(w)w. By gradient ascent, we have vó dw
A(w)w. Since has the additional constraint ||w|| 1, the final dynamics is ı P. A(w) where P.l := ww I is projection matrix that projects a vector into the orthogonal complement subspace of the subspace spanned by w.
15

---

Published as a conference paper at ICLR 2023
Remarks. Note that alternative route is to use homogeneous condition first: Calh(w Ca]h(w==))] w A(z)w, then taking the differential. This involves an additional term w (dA)w. In the following will show it is zero. For this we first compute dA::
dA dCa [h' (od"waa Tx]]
(48)
Cal () (dlwTw))ar ax)ar N'ww'" (uuTa)a x)a)] + C. CalM(w a),, (wo" (w=T x) Tr) (49)
Therefore, since a Calæc y|b Calaa x. b y). we have:
w (dA) Calldw" (w x)w T Jar h(w" [[)]])]]==-- + Calh(w (an(wwTT)),k a)) x) x x) axl
2C, (ddw [(d"")))""(( =))" (w/"""))""" x)w" (e)wuT.rr xr, nn,h(w"" Tx]]
(50)
Note that we now see the term l"ww" ""(wTx))u x)w æc. For ReLU activation, its second derivative h" (x:)
6(x), where ((x) is Direct delta function (Boas Peters, 1984). From the property of delta function,
we have zh" (z) zz(x) 0 even evaluated at r O. Therefore, h² h"(w" x)w x 0 and
w (dA) = 0. This is similar for LeakyRel.U as well.
B.3 LOCAL STABILITY
Theorem (Stability of w²). If w. is LME of A(w.) and )gap(w.) > p(w,). then w. is stable.
Proof. For any unit direction |/u/|2
so that u uTw Tw. 0, consider the perturbation v we have |1ol|2 =1.
VI-ew. + eu. Since ||w= 12
Now let's compute P. A(v)o. v. First, we have:
T
P I - vo = (VI - VV--2w, + +Eu (VI-ew,
e + EEU
(51)
= I - w-w. _ =(uw, + +wuu + O(E))
(52)
= pL. e(uw, + w.u + O(E2)
(53)
So we have:
P.l A(w.)
Put, A(w-) <(uw. + w.u )(ww))+
(54)
= P A(w,))eu c\,u + O(e2)
(55)
P (A(w.) A.T)ccu + 0(22)
(56)
The previous derivation is due to the fact that Pal, A(w,) = 0, u T A(w,) = and Pul, u.
Therefore, for Pe- A(v)a, we can decompose to two parts:
A(u)u = P A(w.)u + P. (A(v) A(w-))v
(57)
= P.l. (A(w,) X, Teu. P. (A(v) - (
(58)
Therefore, since u W. O. we have: u. P.d. (A(w.)) - X.Tu
u. (T w.w, T (A(w.) X.T)cu
(59)
cu (A(w.) X. T)u -Agup (w. (g. 0((2))
(60)
and since ||u||2 ||u||2 1 and || 1|2 1, we have: |u P.- (Avv) A(w.) ol < (A(()) A(w,))(w
(61)
By the definition of local roughness measure p(w.). ), we have:
[[((vv) A(w.)) )) < p(w.)llv - w. + O(1 w.ll3) = p(w.)e + O(e2)
(62)
This leads
[[A(v) A(w.))ulls
[I(A()) A(w.))(wwllll + (I((())
w.
(63)
p(w.)c + +(63)
(64)
Therefore, we have:
u P.J A(o)o (w. p(w.)) e O(e2)
(65)
When Agap (w.) > (..) and we have u T p A(v)u < 0 for any u 1 w, and sufficiently small e. Therefore, the critical point w, is stable.
16

---

Published as a conference paper at ICLR 2023
Theorem 2 (Bound of local roughness p(w) in ReLU setting). If input || Co is bounded, has kernel structure (Def. and batchsize N + +o0, then p(w,) I Covol(Co) r(w.: a), where r(w, a) Eto of (a) max (t a.)
Proof. Suppose w. and its local perturbation are on the unit sphere || || ||2 1. Since w is local perturbation, we have w T uz, 2 1 - for e < 1.
In the following we will check how we bound [I(A(w) A(w,)) )w. ll2 in terms of ||w w., ll and then we can get the upper bound local roughness metric p ((w.).
Let the function ( v". apply Corollary | with augmentation and the large batch limits, we have
A(w) C. [i")
Σ
V [T").
(66)
where (x) 1 ( (t) the probability distribution the input æ, adjusted by the mapping of the kernel function determined by the pairwise importance a. (Def. DT. 21 is its normalization constant.
21
To study (A(w) A( (w.) w.. we will study each component (Vp. [ Ve. [a="))) w..
Note that since x" xl(w x 2 0), have Vp. [ Ep, (xx I(w T x 2 0)] Ex, [xl((w To
0)} (or "[(ww 0)]. Let
ex == / <
e ==
xpr (x)
(67)
T=20
Jw
E. = / xx pr
E =
wx (a()dd
(68)
T220
w wI#20
So write
V 1e = ee
[p E. - e,
(69)
and Vp [
V w.
(E E.) + (c.e. ce eeT).
Define the following regions
Ω4 = {x: w. x 2 0, w < 5
(70)
Ω = (a w. S 0, w 2 0)
(71)
Ω = Ωt UΩ
(72)
Now let's bound (E - E.)w, and (e.e. - ee Jw..
Bound (E E.)w,. We have:
E B-E.- = /
J vx (i(x) - / xx T (f(xdd
(73)
Sa.
and thus
(E E.)w. / xx w. w.p((x))
/ xx Jurun u. (x))dæ
(74)
22
For any x E S4,, we have:
S w._ x = wt T x + (w, TT)xr x S (us. w) Txx S Collun. w/l2
(75)
Therefore, T x < Mlw - w|l2 and we have
1/1 xw T w. (x))d < / |w. x || (x)dæ
(76)
Rt
S collu; l. w/l2 max (x()
dx
(77)
ze
(Co)
w,ll,, - wll2 max pu (x)
arccos w w.
(78)
2T
17

---

Published as a conference paper at ICLR 2023
where vol(Cu) is the volume of the d-dimensional ball of radius Co. Similarly for E Q_ we have
0 2 w. T w (w. w) T x (w. w) x -Colle, -wl12
(79)
hence |w-_ æ]| S Gollw. w|l2 and overall we have:
C8vol(Co)
II - E., E.)w,lla S
w., wll2 max (r(x))
arccos w To w.
(80)
π
#EN
Since for E (0, 1J. aresin vI -x2 xx2
--
we have:
arccos w W. = aresin
- (w T w.,
v
W
w. )²
(81)
1 W
+ w W. 1 2 w.)
v 22(1 w w..
(82)
Wx
w w.
1 1+
(83)
we have:
Civol(Co) 1 -l,, w112 max (a
[[E ).. 1l2 I
(84)
1-e
well
Therefore, 11 - w..,.ll |l2 is second-order term w.r.t. 1|w--w) ---llll. 12.
Bound (e.ee - ee T Jw., On the other hand:
ee -e.e._ =é(e- c(e-ee) + (( -
(85)
We have ||e||2, ||e_]] ||2 bounded and
e = //2 S
xpp(ax)dx - / a
(86)
Using similar derivation, we conclude that lle(e - eT) Te))TW. "/=wwll 112 is also second-order term. The only first-order term is [[(e e.)e. w.ll2:
x)] / |a||2p (x)
ll(e e.e.. w. S Ep,1h(u0 [x)]]
(87)
o/ / (((x))da S C0 max (
dn
(88)
went
Covo arccos w w, max Pr (x: #Ell
(89)
π
Co)o
1 | w. la
max (3c) weft
(90)
π
Overall we have:
((A(w) A(w. (...)))=lll 5
V [
w.,l2
(91)
in
CCvol(Co) 1
Σ
of
max p((x))
||
w. 12 + +[I w ww.l3)
(92)
1-e
#eft
Since p(w.) is the smallest scalar that makes the local roughness metric hold and is arbitrarily small, we have:
p(w.) < Cāvol(Co) r(w,,a) a:)
(93)
where r(w, a)) = =1 #/ max, o o (x;
Corollary 2 (Effect of different a). For uniform ou (aij := 1) and 1-D Gaussian ag (aij have r(w., (g) = zo(az)((w, Ocu) with zo (Oig)
exp(-I]b( (ooli) - h(w" (=(5)))(//2)) (exp(-1i( (e)//rrpp(())) S 1. As result, 2o(agg) & leads r(w.; ag)) < r r(w,, On)-
18

---

Published as a conference paper at ICLR 2023
Proof. For uniform aus it is clear that the mapping Φu(x:) is 1-dimensional. Therefore, Po(a;; au) = 2o(ow) Quo( = pD(œ) with av() = ( (p)((()d (x)dæ = This means that
+00
r( (w)
2 (an) max (a;; (.a)
(94)
w m=
1=0
20 (Qn)
max Po 0n))
max PD(
(95)
w a=
mo ==0
For Gaussian ag. from Lemma ! we know that its infinite-dimensional mapping (x) has the following form for w = w.:
1/2 w x)) ///2 1ta (w,
(ww 2
(5(x)
(96)
+//6/ (w, x)
When / > 1, P ag) 20 (x) for any the plane w x 0, since (x)
aRtw] m)
on the plane. On the other hand, (x) = Therefore, have:
On the plane, (g)(x) = 1 and is a constant.
to0
r(w,, az)
= Σ
z max pi( 0g) = =z((a) max (z)
(97)
w. a=
un -/===0
1=0
20(0g) max Øg0 (g0(2))D(())
(98)
w ==
zo(ag)
max po(x) = wi==
(99)
Here
20(ag) / (2)(=)) / c
h m) 27
PD(x)dæ
(100)
B.4 FINDING CRITICAL POINTS WITH INITIAL GUESS (SEC. 3.3
Notation. Let A (w) and (ww) be the i-th eigenvalue and unit eigenvector of A(w) where Φ1 (w) is the largest. We first assume A(w) is positive definite (PD) and then remove this assumption later. In this case, Xı (ww) > A2(w) ... Na(w) 0. Let c(w) (ww be the inner product between w and the maximal eigenvector of A(w).
Consider the following Power Iteration (PI) format:
+ w(t 1)
w(t + +1) + ((w(tt)w((t,
w(t +
(101)
1 + 1)ll2
Along the trajectory, let dx(t) == Φ2 (A( (t))) be the i-th unit eigenvector of A(w(t)) and (t) to be the i-th eigenvalue. Define 5w(() = wit 1) wt)), 5A(t) == A(w(t + 1)) A(w(t)), and
C = c()())) o1 (1)w(1), := oI (t)ur(t 1)
(102)
Then 1 < cz d. < since they are inner product two unit vectors. Theorem (Existence of critical points). Let Co == c(w(()) + 0. If there exists 7 so that:
sup w(w) < wEB,
(11)
where By = { ww: w (()) > 5
2 is the neighborhood of initial value w(0). T-o, T+7
c=
Then Power Iteration (Eqn. P7 converges critical point w. B., of Eqn.
19

---

Published as a conference paper at ICLR 2023
Proof. Note that if co O, always - (w) the maximal eigenvector.
First we assume A(w) is positive definite (PD) over the entire unit sphere | = 1, then follow
Lemma 11 and notice that ||w - -w(0)l2 - 2 - w w0))), so
- w0)0l I 2 + 71 co) 1-
w w(() 2 Cg C
(103)
1 Cy
When A(w) is not PD, Theorem 3 still applies to the PD matrix A(w) = A(w) Amin (w)) + cl with L and k specified by A(w), where > 0 is a small constant.
This transformation keeps since the eigenvectors of A(w) are the same A(w). wwThe resulting fixed point wü is also the fixed point of the original problem with A(w), due the fact that
P A(w)w P A(w)w
(Amin (w) E) w P A(w)w
(104)
Remarks. Note that Lemma assumes that along the trajectory {wo()), /r + S holds. In Theorem this can not be assumed true until we prove that the entire trajectory is within By.
B.5 THE EFFECT OF DATA AUGMENTATION ON LOCAL OPTIMA
While the majority of the analysis focuses on the cases where there are no data augmentation (i.e., using Corollary the original formulation Lemma 2 can still handle contrastive learning in the presence of data augmentation.
In fact, data augmentation plays important role by removing unnecessary local optima. First, when K 1, takes the following form:
Lemma 2 tells that the objective Eqn.
5
(w) C. [hww æ)]
Σ 7 (sa))(())) [6(([2)))
(105)
where b(wr/w)) == Rewepau (-1w)) [h (ooTT>)(ma) [=))
Now let us consider the following simple data augmentation of æp:
x
R(f) zo.
Uniform(T)
(106)
where R(t) E Raxd is some rotation parameterized by which is drawn uniformly from parameter family T.
We assume (R(T))ET forms 1-dimensional Lie group parameterized by T. This means that
Closeness, For any t, t T, there exists t" T that R(t") R(t)
Existence of inverse element. For each R((), there exists an inverse element '' E T so that R(t') = R (t) = R (t). The last equality is due to the fact that R(t) is a rotation.
Existence identity map. R(O) T.
Then for any small transformation R(t') applied the weights w (here "small" means [[((t') All2 is small), we can write down 6( ((R(t))u (z)) using reparameterization trick:
b( (R())a))o)) = Ex- (ew) ((((((())u)) Ta)) = N(w R. (11)
[ R (()
(107)
[n(w ((t")=))P((""d) = b(w) (wo)
(108)
Note that the last equality is due to the fact that (R(t) is a Lie group, so that R Rt))(t)) always maps another group element R(("), and 1" as the resulting parameterization is still uniform.
20

---

Published as a conference paper at ICLR 2023
Due stop gradient, and thus (i a) is treated as constant term when checking the local property of the current parameters w. This means that the local neighborhood of w, (a( = &a (R(t') )()))w)
Now notice important observation: if w' R(t')w * w. then & (w) Ea (a(((t')w)) Ea (w')
and therefore, w cannot be a local optimal.
Intuitively, this means that the data augmentation not locally invariant (i.e., R(t')w ww & w) to the transformation of the data augmentation. Therefore, augmentation removes certain patterns in the input data and their local optima in the training, to only keep patterns (local optima) that are most relevant to the tasks.
remove certain local optima of w, if they
Here only 1-dimensional rotation group may not globally form a Lie group, and there could be multiple different types of augmentations, yielding high-dimensional transformation space. Therefore, we may Lie algebra instead to capture the local transformation structure, without making assumptions about the global structure. We will give formal study in the future work.
simple example. In practice, the augmentation
C TWO LAYER CASE (SEC.
C.I LEARNING DYNAMICS
Lemma (Dynamics of 2-layer nonlinear network with contrastive loss).
À = [f].
i = P.u [(S 1213) C. Ca[
(12)
where 1 is d-dimensional all-one vector, @ is Kronecker product and o is Hadamard product.
Proof. The output of the 2-layer network be written the following:
fu
vuhhww xxk))
(109)
For convenience, we use fi : [h(w]] mx)] to represent the column vector that collects all the outputs of intermediate nodes, and 2, the 1-th row vector in V.
According to Theorem in Tian (2022), the gradient descent direction of contrastive loss corresponds the gradient ascent direction the energy function (0). From Eqn. 25 of that theorem, have:
Taax 00
Σ
Ca
f21
(110)
00
Therefore, for = [Ua]] we have:
30
[8 f21 Ov,
0;
= Σ Ca
Ca
(111)
Ov:
C. [f vo_ fi
(112)
= C. [f1, fil
(113)
So have 6; (filu or VCa(fi]
21

---

Published as a conference paper at ICLR 2023
V V
Ez
+
V E x 2
R1
Multiple nodes in the same receptive field
+
R2
R3
Low-Rank matrix
Block-diagonal matrix
Figure Decomposition of the variance term V(ø).
Now we compute 8E @rwg:
30
W Swn
E Ca
Orox f21
(114)
Σ Ca (unll'(wr ax Dake of fi]
(115)
E un Calkki Vi fil
(116)
Σ
ΣonCa Co
Dkk Σ
(117)
Σ Σ ViN Ca [ wklww ww
(118)
Σ Ski (ik Iwo wk
(119)
where [sge]] =TV=
= E0o
Let w = [wi;...; wxl and leads to the conclusion.
When M 1, the proof is similar.
C.2 VARIANCE DECOMPOSITION
Let Pe == P(z be the probability that the latent variable takes categorical value Lemma (Close-form of variance under Assumption 2}.
With Assumption we have
C-1
V = diag, [Lx] +
Pe pc) (c) (c)
(120)
0=0
where L; := [. E Md and A(c) El cj E| + c) E RMd, In particular
when C C= 2, the second term becomes PoP1 AA
rank-1 matrix. Here A A(0) for brevity.
Proof. Use variance decomposition, we have:
V = E, V + +V [[]22]
(121)
Remember that Ekm is abbreviation of gated input:
km
3Kk h (T T.
(122)
By conditional independence, we have
Cov Cov|@xmm T |2] = 0
vk + K'
(123)
This is because 3em and Dx are deterministic functions of og and By and thus are also indepen- dent of each other.
22

---

Published as a conference paper at ICLR 2023
Let
Øk2
ig ==
(124)
3kM
and La := E2 V[ Then we know that E, [. diag, is block diagonal matrix (See Fig. 6
On the other hand, V E. [ is a low-rank matrix:
R j F, [(*[)==] R [[))(( [[
(125)
Let q. == E2 [ c] and - = |= + c). then we have:
|[ø|= = cl
[
q. Epdee
Pole- = = (1- (pp)
--- ---
Pe
qo
(126)
Pc
ctc
(1 -p))
9: 9c- - Fl c/2 1/ + clqe
(127)
d'sc
(1 1-pe){ge q-c)
(128)
Therefore, we have:
V, [
E, [E |
(129)
Σ Pé(1 - Pp)) - q q-c)(ae 9-c)
(130)
P (c)
(131)
where
An(())
A(c) = A(: = ge q-c
E R2 KMd
(132)
AkM(()
and
Amm (c) Aum (c, Wkm) = E El@xmm c) Kl 1= # c)
(133)
We can see that VzE[ø]2] l2] is at most rank-C: CC, since it is a summation of C' raak-1 1 matrix. In particular, when C' 2, clear that (0) -11 and thus A(0) ((1)AT(I) (1) and PePo Pc) Pop? + PIPă = PoP1 Hence the conclusion.
C.3 GLOBAL MODULATION WHEN C' = 2 AND M =
Theorem 5 (Dynamics of we under conditional independence). When C = and M 1, the dynamics of Wy is given by (s and ôz 2 0 are scalars defined in the proof):
w = Pil.
+ 5gA wy
(15)
Proof. Since M = 1, each receptive field (RF) Ra only output a single node with output fx- Let:
L = E, [[aa<]]
(134)
dg = w/ L = E, 2
(135)
D [iag
(136)
b = [bx] == w Av] E K
(137)
and À be the maximal eigenvalue of V[fi]. Here La is PSD matrix and D is diagonal matrix.
Then
v(fi D Popibb bb
(138)
23

---

Published as a conference paper at ICLR 2023
is diagonal matrix plus rank-1 matrix. Since PoP1 is always PSD. À Amax (D) = max; dę- Then using Bunch-Nielsen -ielsen-Sorenseen formula (Bunch et al. 1978). for largest
Amax
(v(f)) 2
eigenvector have:
bk
3k.
(139)
Z d2
where is the corresponding largest eigenvalue satisfying + PoP1 E de -e_x = O, and Z
Ex de dx Note that the above well-defined, since if ks = arg max; du and by o 0. then
> max d2 = de- So bx/(de- - X) won't be infinite.
So we have:
Σ Ca (ack, Fee June
(140)
Σ sk5w (Loll(k = k') + PoPI A Ax 2 wa
= $ V u2 + PoPIstAk
E
Sk A
(141)
= of V 20 + PoPi bk
bg.
Do
(d A)
dR - A
V + 6 A wk
= ( + 6g - A wk
(142)
where
PoPI
byg
5% = Zz(A - dx)
(143)
X
dy
Since À 2 max di, we have ox 2 0 and thus the modulation term is non-negative. Note that since bg
PoP1 Σx X-d, 1, we can also write 8n
PoPi DZ
A-de
Theorem 6 (Global modulation of attractive basin). If the structural assumption holds: As(w))
Ee gu, wx J with g(.) > 0 a lineur increusing function and {ui} orthonormal bases, then for A + cujul its attractive basin of wy = uu is larger than A 's for e >> 0.
Proof. Since Ax(w) = Eig(ue S(u, w) uu)uu we could write down its dynamics (we omit the projection P.l. for now):
i Au(w)u Eo(ur gluu w) uuuu w
(144)
Let (t) == un (t), i.e., (t) the projected component the weight w(t) onto the 1-th direction, ie.. change bases orthonormal bases ). then the dynamics above can be written as
g(31)
(145)
which is the same for all I, so we just need to study á = g(z).. g(x) > 0 is a linear increasing function, so we can assume g(x) ax + b with 0. Without loss of generality, we could just set 1.
Then we just want to analyze the dynamics:
(yi + br)m
by
(146)
which also includes the case of A + cuju, that basically sets b, = b Solving the dynamics leads to the following close-form solution:
(t)
(n( bie
(147)
y1 (t) + b (0) + by
24

---

Published as a conference paper at ICLR 2023
v((t)
)1(0)) >
0
(0) < 0
b (0)
ti
In
+
b
-b
Figure 7: The one-dimensional dynamics (Eqn. 146 (b: > 0). There exists a stable critical point
y1 -b; and one unstable critical point yı 0. When (0) 0, the dynamics blows up finite
time t7 1/ In b
(0)
25

---

Published as a conference paper at ICLR 2023
The 1-d dynamics has an unstable fixed points y 0 and stable one yt -b; < 0. Therefore, when the initial condition yu (0) < O, the dynamics will converge to (1(000) = -b,, which is a finite number. On the other hand. when yr (O) > O, the dynamics has finite-time blow-up Thompson et al.
(1990): Goriely& & Hyde 1998), i.e., there exists a critical time ij < +00 so that yr(4)) = +00. See Fig.1 7
Note that this finite time ulow-up is not physical, since we don't 't take into consideration of normal- ization Z(1), which depends on all y (t). The real quality to be considered is ()()) z (t).
Fortunately, we don't need to estimate (t) since we are only interested in the ratio:
Tife (t) = in (1) (l(()
(148)
(t) (t (t)
If for some and any 1' # 1, (1/r oo, then y (t) dominates and (t) 1, i.e., the dynamics converges to uq-
Now our task is to know which initial condition of yr and by makes rirr - +.c. By comparing the critical time we know which component / shoots up the earliest and that 1" = arg miny 17 is the winner, without computing the normalization constant (().
The critical time satisfies
(0)
(149)
(0) + b
so
1
bt (n
In
1
+
(150)
bi
clear that when (0) is larger, the critical time 17 becomes smaller and the 1-th component becomes more advantageous over other components.
For bj > 0, we have:
ar 1 (// - In(1 + bbbb/(())))))))))))))))))))))+ 0
(151)
ab, by 1 + bi/ (0)
where the last inequality is due to the fact that 1+r < In(1 + 2) for x > 0. Therefore, larger by leads to smaller ti. Since adding cur, with e >> 0 As increase by, it leads to smaller t7 and thus increases the advantage of the 1-th component.
Therefore, larger by and larger y (0) both leads smaller 17. For the same 1j. larger by can trade for smaller (0), i.e., larger attractive basin.
Remark. Special case. We start by assuming only one a * 0 and all other cr 0 for 1' + 1, and then we generalize to the case when all } are real numbers.
To quantify the probability that a random weight initialization leads to convergence of u,, we setup some notations. Let the event E, be "a random weight initialization of y leads to cquivalently w - uy Let Yi be the random variable that instantiates the initial value of (0) due to random weight initialization. Then the convergence event Ej is equivalent to the following: (1) Y > 0 (so that the l-component has the opportunity to grow), and (2) Yi + E, is the maximum over all Y/ for any 1' 1, where e is an advantage (> 0) disadvantage (< 0) achieved by having larger/smaller by due to global modulation (e.g., c). Therefore, we also call 6 the modulation factor.
er", or
Here we discuss about simple case that Y; UI-1, 1] and for 1' + L, and Yr are independent. In this case, for a given I, maxy eft Yr is a random variable that is independent of Y,, and has cumulative density function (CDF) Fanax (I) == Pfmmxyy Yy. S x] = (x:) where F(x)) is the CDF for Yi.
Then we have:
P P(A
P
Y> P 0, + 2 max Yr
(152)
1211
IP
max Yv S Yı + ez e Yi= 911
PlY: = yildyr
(153)
/ +00
pd-1 + ((r)((n)
(154)
26

---

Published as a conference paper at ICLR 2023
When Y, ~ U1,1, F(x) min (5(2 + 1),1} has close form and we compute the integral:
El
PLE =P > 1.
max Yv 171
to 2
+
0 4 1
(155)
[11
(
<1<
We can see that the modulation factor e plays important role in deciding the probability that + ui
w
No modulation. c 0, then P 3- This means that each dimension of has equal probability to be the dominant component after training;
Positive modulation. If e O, then PP[E]] 2 T. and that particular 1-th component has much higher probability to become the dominant component, independent of the dimension- ality d. Furthermore, the stronger the modulation, the higher the probability becomes.
Negative modulation. Finally, if < since 1 + a/2 1, P[E] - 5 + g)d decays exponentially w.r.t the dimensionality d.
General case. We then analyze cases all q are real numbers. Let arg max, e and c(k) be the k-th index of & in descending order, i.e., c(1) = -
For | c(1) = 1", et the largest over {Er}. Since
P
P
Yi 2 0,Yi max Yp +
P'pt
M
P
Yi 2 0,
Ec(1) Ec(2)
max Yr
where C((1) Cx(2) is the gap between the largest q and second largest et. Then this case is similar to positive modulation and thus
1
P P[ 2 (<o(1) Ec(2))
(156)
For / with rank (i.e., c(r) l), and any < r, we have:
PE = P
Yi 2 0, + 2 max Yv + tep
Paft
< P
Y 0, +
max
Yv +
P
Y 2 0 + kc(r') 2
max
Yo + Ev - kc(r))
Pie St)
< P Y 0, e Ec(P)) Pio
Yr
(")
Then reduces to the case negative modulation. Therefore, we have:
P(E S min 1 (1- Ec(r') - Ec(r)
P<r yd +1 (1-<((r)
(157)
and the probability is exponentially small if is large, i.c., et ranks low.
C.4 FUNDAMENTAL LIMITATION LINEAR MODELS
Theorem 4 (Gradient Colinearity in linear networks). With linear activation, W follows the dynamics:
tbkm 8tmn (W,
(14)
where by (W, = Ca. Dbs Ex mn m w k' mm Ix is linear function w.r.t. W. As a result, (1)
wem are co-linear over m. and (2) If 8km + 0, from any critical point with distinct {wamh there exists a path of critical points identical weights (Wkkm wg).
27

---

Published as a conference paper at ICLR 2023
Proof. In the linear case, have 3em 25 since there is gating and all M shares the same input zg. Therefore, we can write down the dynamics of Wkm as the following:
Wkm
Σ
Skm, m Ca kem Dk/mm Wwemm
(158)
Σ
kkmmk'm Ca Ikk Dgr Wism
(159)
Now we use the fact that the top-level learns fast so that Skem, k'mm = 8km Skmmm which gives:
Wkm
8 kem
Σ
Sk
Coi (30 2y Jwwm
(160)
k k/mm
8km Ca
Strmm W W Dkk
(161)
ke mmm
Let by (W, = Ca Lk: EN mi Steme W mo Lo
be a linear function of W, and we have:
Wem 3km by (W, V)
(162)
Since by independent of m, um are co-linear.
For the second part, first all if W is critical point, we have the following two facts:
Since there exists m so that 8km * O, we know that by (WV)
If W* contains distinct filters wk1 14 * Wx2 μ2 covering the same receptive field Rg. then by symmetry of the weights, W in which wa1 #2 and W22 = fl, is also critical point.
Then for any e E j0, 1]. since by (W) is linear w.r.t. W. for the linear combination W := cW' + c)W', we have:
by (W9) (cW" + (1 o) = cbg (W + (1 c)
(163)
Therefore, W is also critical point, in which ux1 cps + (1 - cc)12 and 132 = (1 c) + cu2- In particular when e = 1/2, 211 = Wk2. Repeating this process for different m, we could finally reach a critical point in which all Wkm wk.
D ANALYSIS OF BATCH NORMALIZATION
From the previous analysis of global modulation, it is clear that the weight updating can be much slower for RF with small dg, due the factor x-d. in both s (Eqn. 139) and 88 (Fqn. 143) and max; dg. This happens when the variance of each receptive fields varies lot (i.e., the fact that some dy are large while others are small). In this case, adding BatchNorm at each node alleviates this issue, shown below.
We consider BatchNorm right after f: [ba[j] = (fa(i) pk)/Okk where fi and a are the batch statistics computed from BatchNorm on all 2.N samples batch:
14 =
2N Σ
[x[i] + fx('')
(164)
of
[(Al 14)² + (fu('') - 1
(165)
2N
When N + +00, we have #4 + E[fa] and of + v[fa] = w. Vakk/wk.
bbu 3
Let @bn b= 0x Tb. and bb
When computing gradient through BatchNorm layer,
consider the following variant:
28

---

Published as a conference paper at ICLR 2023
Definition 5 (mean-backpin BatchNorm). When computing backpropagated gradient through BatchNorm, we only backprop through pk-
This leads model dynamics that has very similar form as Lemma
Lemma 6 (Dynamics with mean-ben mean-backpre backprop BatchNorm). With mean-backen cann-bbckprop BatchNorm (Def. 5 the dynamics is:
= "f
W [(S @ lald) C. w
(166)
Proof. The proof similar to Lemma input to the top layer.
For V is the same by replacing fi with flmm which the
For w similarly we have:
f Ourk
wk
Co.
f21
(167)
Oun
Σ Co
Utk: Own
Σ Usk' Jik
(168)
=
Σ
Ca
Ulk
Owa
Σ
Me yo
(169)
Note that CaI.s - = 0 since pa and de are statistics of the batch and is constant. On the other hand, for 0 0 /0wkk, we have:
0fh
0fik Öwv
0pk
thr Ook
(170)
Owr
Ows
dy Ow
Note that
0us
Esample [xx]
(171)
Ow.
where Esample[] is the sample mean, which is constant over the batch. Therefore C. 1: 0uwx/Ows] = 0. For mean-backprop BatchNorm, since the gradient didn't backpropagate through the variance, the second term simply zero. Therefore, we have:
Ofik Dwo
ib
Ca
BIRO
Σ
Uik fuN
(172)
Σ
C. DiRO -1 Lk.. Σ Uhe 2
(173)
Σ
sky Ca iox 'ix, oN www
(174)
bu
Let aba ox - and bb =
E BRdd The conclusion follows.
bb
Corollary (Dynamics of wy under conditional independence and BatchNorm). Let
A V(ahr) = ox -2 A
(175)
den
of 2d
(176)
Abn
ok * E
Elab"" 2 0]
(177)
and bn be the maximal eigenvalue of ([bb)) Then we have
(1) An max; abn.
29

---

Published as a conference paper at ICLR 2023
(2) For A the associated unit eigenvector is
w A bn
IR
7 bn
Abn xx
where hh is the normalization constant;
(3) the dynamics of wy is given by:
~ (( A +8 (Ak")
20
(178)
where
(w
8/
PoP1
(179)
(7 bn (
dbu
Abn
Proof.
Similar to Theorem
Remarks In the presence of BatchNorm, Lemma 5 still holds, since it only depends the generative structure of the data. Therefore, we have
of
vifal
W Vaxlww du pop1 (w]Ax)) Ax)
and thus
dx
1
dom
k 2 dx + d; + PoPi (m)) Ax) 1 1 pop (w) / /dz)
becomes more uniform. This is because dę := w. L E, 2 2 0 (Eqn. 135 is approx- imately the variance of [k. and thus wx A&/ Ae/Vie normalized across different receptive field k reducing the effect of magnitude of the input.
Since there no much variation within {abe }, bn d becomes almost constant across different receptive field R& and won't 't lead to slowness of feature learning.
30

---

Published as a conference paper at ICLR 2023
Giwe durngs unit weight vertical ports.
alanth
Figure 8: Local optima of objective & (w) under uniform a == 1. w = [cos 8, sin 0] is parameterized by 9 E [-T, r). and cach vertical dotted line is a data point. Dotted line is Ea with linear activation h(x)) = 2, and solid line is using ReLU activation l1()) = max(2, 0). Both lines are scaled so that their maximal value is 1.
E ADDITIONAL EXPERIMENTS
E. VISUALIZATION OF LOCAL OPTIMA IN 1-LAYER SETTING
We added a simple experiment to visualize the local maxima of & (w)) = 2 [Ca(h(w [[)] when w [cos 0, sin 0] is a 2D unit vector parameterized by 0, and h is ReLU activation. For simplicity, here we use a uniform a
We put few data points {x;} on the unit circle, which are also parameterized by 6. The data points are located at { objective function (0) is plotted in Fig.
Am T
5 dn and no data augmentation is used. The
5 2
From the figure, we can see many local maxima (2 8) caused by nonlinearity (solid line), much more than 2 x 2 = 4, the maximal possible number of local maxima counting all PCA components in 2D case (i.e., = and = where Φ1 and d2 are orthogonal PCA directions this 2D example). Moreover, unlike PCA directions, these local optima are not orthogonal to each other.
the other hand, in the linear case (dotted line), the curve is much smoother. There are only two local maxima corresponding to =ő1, where Φ1 is the largest PCA eigenvector.
E.2 2-LAYER SETTING
We also do more experiments on the 2-layer setting, to further verify our theoretical findings.
Overall matching score X and overall irrelevant-matching score x- As defined in the main text (Eqn. [6), the matching score xRx) is the degree matching between learned weights and the embeddings of the subset RŘ of tokens that allowed in the global patterns at each receptive field Rg. And the overall matching score X+ is X+ averaged over all receptive fields:
X+ (Bx)
Σ GERE
W
km
Ua
X+
1 K
Ex+(RR)
(180)
P
Similarly, also define irrelevant score (Rx) which is the degree of matching between learned weights and the embeddings the tokens that are NOT in the subset R at each receptive field Rg. And the overall irrelevant-matching score X- is defined similarly.
x- (R
Σ max
km Ua
8
1 Σx (Rx) K
(181)
Ideally, we want to see high overall matching score X and low overall irrelevant-matee X-, which means that the important patterns in R (i.e., the patterns that are allowed in the global generators) are learned, but noisy patterns that are not part of the global patterns (i.e., the generators) not learned. Fig. Fig. shows that this indeed is the case.
score
Non-uniformity Ç and how BatchNorm interacts with it. When the scale of input data varies a lot, BatchNorm starts matter in discovering features with low magnitude (Sec. DD. To model the
31

---

Published as a conference paper at ICLR 2023
scale non-uniformity, we set |aall2 Ç for [d/2] tokens and ||ua||2 1/5 for the remaining tokens. Larger corresponds to higher non-uniformity across inputs.
Fig. I1 shows that BN with ReLU activations handles large non-uniformity (large () very well, compared to the case without BN. Specifically, BN yields higher X+ in the presence of high non- uniformity (e.g., < - 10) when the network is wver-parameterized (3 1) and there multiple candidates per Rg (P > 1), setting that is likely to hold in real-world scenarios.
Note that in the real-world scenario, features from different channels/modalittes indeed will have very different scales, and some local features that turn out to be super important to global features, can have very small scale. In such cases, normalization techniques (e.g., BatchNorm) can be very useful and our formulation justifies it in a mathematically consistent way.
Selectively Backpropagating μa and o in BatchNorm. our analysis of BatchNorm, assume that gradient backpropagating the mean statistics but not variance of (see Def. 5). Note that this different from regular BatchNorm, in which both μæ and of get backpropagated gradients. Therefore, we test how this modified BN affects the matching score X+: we change whether and of gets backpropagated gradients, while the forward pass remains the same, yielding the four following variants:
bn [i]
pbu [t] =
(Vanilla BatchNorm)
0k
fhn [X] stop-gradin gradient(dd))
fh =
(BatchNorm with backpropated oy2)
bb 1 pak
[b] :=
(BatchNorm with backpropated j4;)
stop noopgradienn((xy,
[b] stop-gradient(ua)
(BatchNorm without backpropating statistics)
(oo-grradent((x))
As shown in Tbl. 1 is interesting to that if of is not backpropagated, then the matching score X actually better. This justifies our BN variant.
Quadratic versus InfoNCE loss. Fig. 10 shows that quadratic loss (constant pairwise importance a) shows worse matching score than InfoNCE. A high-level intuition is that InfoNCE dynamically adjusts the pairwise importance (i.e., the focus of different sample pairs) during training focus on the most important sample pairs, which makes learning patterns more efficient. We leave comprehensive study for future work.
32

---

Published as a conference paper at ICLR 2023
candidate
Pw10 candidate
Oroud -Ahir SOAR
Inilynkk
Degine ceceanamdeetaiiin
Doyrer of copponeentt 007en
Drorce of seeprrretetttttoo
Degrre censannddevtaiii
Orear inworrtrrrieteeeg wow. xone--
candlatte
candidate
candidate tokend per
52
-34
-04
Dagrox of coepetemeaar dulion
Degros of tvaggoonsttrceein
Degres cnapp aretoriation
Dugru of comremmcattttonnn
Figure 9: Overall matching
X+ (Eqn. 180 the top row) and irrelevant-matee matching score X- (Eqn. 181 the
bottom row). This is an extended version Fig. (a) When P 1, linear model works well regardless of degree of wver-parameterization B. while ReLU model requires large parameterizaaiinn to perform well; (b) When each Rg has multiple local patterns that are related to the global patterns (P > 1) related to generators, ReLU models can capture diverse patterns better than linear ones the wer-paraamtterzzation region / > 1 and stay focus relevant local patterns that related the global patterns (i.c., low X-). Among all activations (homogeneous or ho--hooegeeoos) ReLU shows its strength by achieving the lowest irrelevant-mant matchinn score X- In contrast, linear models are much less affected by over-parameterization Each setting is repeated times and mean/standard derivations are reported.
Pw1
candidate
dinii
Pw10 candidats
Ove motorreoooee
Ore mo0OO SOURE
meating
Degine ceeeanneveetaiii g
Doyres www.pooeeeeeee.... porian
Drove of wweppnreetttiitiioo
Deggee www.raaaeeeeiiiiioooooooo.o.
Over intorat www.eeewooooooooooooooooooooo van... vane--
candldate
candidate
candidate
Ove mndoouee tng 220N-
candidate tokend
22
muschng
22
-02
-14
-3.
-04
Deg of coorppmmeeeeeret
Bagma of www.ponetttttiiii
Degnre Coupperrettttsttte
Degrte of coeeaaannetttttoo
Figure 10: Overall matching score X (top row) and overall irelevant-matchhin score X- (Eqn. 16 bottom
row) using quadratic loss function rather than InfoNCE. The result using InfoNCE shown Fig with all experiments setting being the same, except for the loss function. While we see similar trends as in Sec. 5.1 quadratic loss is not effective as InfoNCE in feature learning.
33

---

Published as a conference paper at ICLR 2023
Po1 canditate tokens
candidate
Par candidtte
P=:10 candidate
Degras overcanmitetttaaon Po1 candidate toleens per
Degres dovprnnmeearrr
Depres of cpepraretattttoon candiatte tokens per
Cegro of ovstenmittttbbi
P-3 candidale tnter per
P-10 candisate tokens
Coae maloin APF--
Coand maccove
via Bn
P-1 candidate takens per IF
P-3 candidate tokens RF
P-3 candiaate tokers par
P-10 candidito tokers RF
Orend mestii SoMe
24
Degiee eeceparanntteiiaaiie
Degret Cuoppnaree 20110
Deorce www.porattttttiiii.oo....
Degree www.gaannntteeeeeooo....
The effect of BatchNorm (BN) with ReLU activation in the presence of non-uniformity. Ç of the input data. The non-uniformity is be < 2 (top), < 5 (middle) and < 10 (bottom). For small non-uniformity, BN doesn't help much. For larger nonuniformity, over-parameetrizztion region (large 3) and multiple tokens per RF (large P).
Figure 11:
yields better matching score X+ the
no backprop
jt backprop
P
of no backprop
of backprop
of no backprop
af backprop
I
0.31 = 0.24
0.23 = 0.06
0.30 0.24
0.23 = 0.06
3
0.65 0.09
0.01 -0.03 0.01
0.64 + 0.07
0.24 = 0.11
5
0.61 + 0.06
-0.00
0.62 0.02
0.38 = 0.04
10
0.66 + 0.06
0.53 + 0.05
0.70 0.03
0.56 + 0.04
0.36
0.27 1 0.06
0.63 1.13
0.33 0.12
3
0.78 + 0.01
0.00 + 0.01
0.80 0.02
0.41 + 0.07
2
5
0.78 0.02
0.22 0.21
0.77 0.07
0.56 0.02
10
0.83 - 0.08
0.72 + 0.06
0.80 0.04
0.71 0.05
1
0.63 0.06
0.43 4.12
0.67 0.06
0.46 = 0.06
3
0.90 0.06
0.45 0.07
0.90
0.60 0.08
5
5
0.90 + 0.01
0.72 + 0.01
0.88
0.74 = 0.02
10
0.88 = 0.01
0.88 0.04
0.92 0.03
0.90 0.03
1
0.63 + 0.12
0.37 + 0.15
0.70 0.17
0.46 + 0.15
3
0.95 0.05
0.72 0.06
0.94 0.05
0.80 = 0.03
10
5
0.98 + 0.02
0.84 + 0.05
0.96 - 0.06
0.92 0.01
10
0.90 + 0.01
0.97 0.02
0.89 0.03
0.97 - 0.02
Table The effect backpropagating different statistics under nonuniformity < = 10. Backpropagating the gradient through the sample mean μa but not the sample variance of gives overall good matching score X+, justifyyng our setting of mean-bal bann-backprop BatchNorm (Def, 5
34

---

Published as a conference paper at ICLR 2023
Receptive T
Recestive feid
Recestive feld
Recestive feed
Figure 12: Learned filters (of the 4 disjoint receptive field) in MNIST dataset without using augmentation. The 4 receptive fields corresponds upper left (0), upper right bottom left (2) and bottom right (3) part of the input image.
Receptive T
Recestive feld
Recestive feld
Recestive feedd
Figure 13: Same as Fig. 12 but with data augmentation during contrastive learning. The learned filters smoother. According the tentative theory Soc. B.5 data augmentation removes some the local optima.
E.3 MNIST EXPERIMENTS WITH 2-LAYER SETTING
We also the same 2-layer network (as in Sec. E.2p MNIST (012)) dataset. In its training, the MNIST dataset consists of 50, 000 images, each with the size of 28 by 28. We split the 28-by-28 images into 4 disjoint receptive fields, each with size of 14 by 14, just like Fig. ((). In each region, we vectorize the receptive field into 14 * 14 = 196 dimensional vector. We use smaller batchsize (8), since there are only 10 classes in MNIST, and the probability that two samples from the same class are incorrectly treated as negative pair increases with large batchsizes. We train for 50000 minibatches and start new pass (epoch) of the dataset if needed.
Fig 12 shows the initial results. We could see that indeed filters in each receptive field capture a diverse set of pattern of the input data points (e.g., part of the dig- its). Furthermore, with additional data augmentation (i.e., random cropping and resizing with transform transforms RandomResizeddrrrr ratio- 5, 1.5) in PyTorch), the resulting learned patterns becomes smoother with much weaker gigh-frequency components. This is because the augmentation implicitly removes some of the local optima (Sec. [B.). leaving more informative local optima.
(28, 28), scale= (0.1e=(0.5) (0.5, 1.0),
35

---

Published as a conference paper at ICLR 2023
F CONTEXT AND MOTIVATIONS OF THEOREMS
Here are the motivations and intuitions behind each major theoretical results:
First of all, Lemma 2 and Corollary try to make connection between a relatively new (and somehow abstract) concept (i.e., contrastive covariance [.) and well-known concept (i.e., regular covariance V[-). This will also enable us to leverage existing properties of covariance, in order to deepen our understanding of this concept, which seems to play an important role in contrastive learning (CL).
After that, we mainly focus on studying the CL energy function E,, which can be represented in terms of the contrastive covariance [.]-). One important property of the energy function is whether there exists any local optima and what are the properties of these local optima, since these local optima are the final destinations that network weights will converge into. Previous works in landscape analysis often talk about local optima in neural networks as abstract objects in high-dimensional space, but here, we would like to make them as concrete possible.
For such analysis, always start from the simplest case (e.g., one-layer). Therefore, naturally we have Lemma 3 that characterizes critical points (as a superset of local optima), few examples in Sec. 3.2 properties of these critical points and when they become local optima in Sec. 3 Finally, Appendix further gives preliminary study on how the data augmentation affects the distribution of the local optima.
Then we extend our analysis to 2-layer setting. The key question is to study the additional benefits of 2-layer network compared to K independent 1-layer cases. Here the assumption of disjoint receptive fields is to make sure there an apple-to-apple comparison, otherwise additional complexity would be involved, e.g., overlapping receptive fields. As demonstrated in Theorem 5a and Theorem 6 we find the effect of global modulation in 2-layer case, which clearly tells that the interactions across different receptive fields lead to additional terms in the dynamics that favors patterns related to latent variable z that leads to conditional independence across the disjointed receptive fields.
As a side track, in 2-layer case, we also have Theorem 4 that shows linear activation does not learn distinct features, which is consistent with 1-layer case that linear activation h(x)) = x only gives to maximal PCA directions (Sec. 6
G
OTHER LEMMAS
Lemma 7 (Bound of 1 - de). Define
p(w) = 1+ c(w)
(>²(A(w((t))) 2 (ww (A((A(()))
1 c(w)
1 Aep (
2
(182)
d1 (A(tt)
and pt == p(w(t)). I > and A (t())== > 0, then
de S He(1 - c.).
Proof. We could write de:
(f)) +1)
(t)oT (t)w(t)
de
(183)
(t + 1)ll2
v E, (2(1) (oT (f))(t))²
(t)
> X((1)02 + (2(t)(1 - 2)
(184)
V1
Aa(t)) Ax(()
2
1/2
(2(()
1
1+
1
(185)
(t)
(a(())
>
-1 1)
=: 1 - 11 (c)
(186)
2
(t)
36

---

Published as a conference paper at ICLR 2023
The first inequality is due to the fact that Σi>1 (7(1) (0] (1)) = of (Parseval's identity). The last incquality is due to the fact that for -1, (1 + 2) 2 11 + az when 1 0
(Bernoulli's 's inequality). Therefore the conclusion holds.
L
Lemma 8 (Bound of weight difference). If es and (t) for all i, then [|ōu(()]l2 - 22(1 + (1 ++)
Proof.
First, for w T (t + ()))()), we have (notice that 2,(t) 2 0): >x)(( (0 (1) (t))
w Tt + 1)w(()
(187)
VE, AE(0(( (OT (t)
((())) VX((1) + (2(1)(1 2)
2 ue(1 ca)
(188)
Therefore,
1|w(1 + 1) - -w(1)l2 = -/ w -
+1 S V 2(1 + prex) -4.
(189)
Lemma 9. Let 8A A'
A, A, then the maximal eigenvector Φ1 := (A)) and 0i = Φ1 (A') has the
following Taylor expansion:
&i = + AΦ1 + -(16A11)
(190)
where Xj is the i-th eigenvalue of A, Ao1 Ej>1 0.7 6dτh
-1= dy is the first-order term of eigenvector
perturbation. In terms of inequality, there exist K > so that:
1 (ői + 1 S K xx|6 6
(191)
Proof. See indeeindeeendent perturbation theory in Quantum Mechanics (Fernández) 2000).
Lemma 10. Let L be the minimal Lipschitz constant of A so that ||A(ww") - A(w)ll2 S L|| - w w'lla
holds. If c2 > 0 and (t) > 0 for all i, then we have:
ld 441ll = (0b (1) - dh 1I) 1)) w0l1 ve((+1)
S svi(1 -+)
(192)
where
v(w) = 2xL (AA
2
(193)
and v == v(w(
Proof.
Using Lemma 9 and the fact that ||w0(1 + 1)]l2 = 1, we have:
|d -+1 = (t) - +t(++ wot + 1) < A (t) 1)1 +111)((0))
(194)
where
A0) = Σ T (1), (1) (1())
(195)
(1 (1)
and 6A(t)= = 1()))) For brevity, we omit all temporal notation if the quantity is evaluated iteration t. E.g., 8w means (t(() and Φ1 means (t)..
Now we bound A wt + 1)). Using Cauchy-Schware Schwarz inequality:
Φ A
AΦ wt + 1)] =
Σ i>
(0) wll + +1))
(196)
2 d1 - 2,
$J TT
(o] w(t + 1))
(197)
i>1
1>1
(T
[0] (1(++)))
+ (1)²
(198)
Agap( (A)
j>
37

---

Published as a conference paper at ICLR 2023
Since {Φ,} } is set of orthonormal bases, Parseval's identity tells that for any vector v, its energy under any orthonormal bases preserved: (0) w)² | Therefore, we have: | w(t + +11
118 10A01112/1 d3
(199)
Ayup (A)
L
(200)
Apap (A)
Note that using -1 de S and Lemma
we have:
1 di 1 d S 2(1 do) S 2u -a)
(201)
Finally using bound weight difference (Lemma
we have:
dd c+11l
2xI 14cr((1 at) + LA gap v 2(1 + p4c) c2) d3
(202)
S v1(1 - c))
(203)
Here vs = 2xI p(c)) + 2L ( / 14(1 pece).
Lemma 11. Let co c(w(()) w (0))) (A(w(()))(0))
Define local region Byi
/ + 7) co)
By = w: : ||m - -0()) S
(204)
VT
Define w(w) == u(w) + v(w) to be the irregularity (also defined in Def. 4 If there exists y < 1 so that
sup
w(w) S
(205)
wEB,
then
The sequence {ee increuses monotonously and converges to 1;
There exists w. so that lim4-++00 w((t) W.
w. is the maximal eigenvector of A(w.) and thus fixed point of gradient update (Eqn. 7):
(2(147)(1-o))
For any I, [())(() w0(0)l2
1-v7
(1(+))((-00) 1-V7
l|w. - w00]l2 &
That is, is in the vicinity of the initial weight w (0).
Proof. We first prove by induction that the following induction arguments true for any
c+1 2 0;
1- 5 co):
w(l) is not far away from initial value un()):
(1)( - w0 z - op)
(206)
P=0
which suggests that w(t) Byy.
Base case (1 1). Since 2 > 0, (lw) 2 0. and A(w) is PD, applying Lemma g to
[10(1) (0)]l2, is clear that
[10( (0))l22 [1)m(()]l2
(1 co) 22 +1 co)
(207)
38

---

Published as a conference paper at ICLR 2023
Note that the last inequality is due μo I Note that
- = 1 - do + do c1 - 1 - d + do cil S (No - vo) - co) S 7(1 - co)
(208)
and finally we have 01 2 1 - 7(1 co) 2 co > 0. So the base case is satisfied.
Inductive step. Assume for t, the induction argument is true and thus w(t) By, Therefore, by the condition, we know 14 + 14 S 7.
By Lemma know that
| + 1) - w(t)ll2 = [[ów(t)ll2 & 2 (ca)(1-)))))) & co)
(209)
Therefore, we know that w(t + 1) also satisfies Eqn. 206
1| + 1) =0)]ll2
s ||=(()) u<00)l2 1(o2(())22
(210)
s (2(1+ - co)
Σ
1/12 + 712/
(211)
1'=0
2211 +1)++(11--- -oo
Σ 7f/2
(212)
t'=0
Also we have:
1 - C++1
= 1 de + 941 S - de + dd, c++1l
(213)
< (14 + 11 -)) S 7 - at)
(214)
S (1
(215)
and thus we have c++1 2 - 7(1 a)) 2 4 Therefore, we have
1 S 7 (1-c1))) co) +
(216)
thus is monotonously increasing to 1. This means that:
lim C: lim o (t)w(t)
(217)
Therefore, we can show that wt() is also convergent, by checking how fast [[ów(t)ll2 decays:
| 2 (1 - -c)= S By Cauchy's convergence test, w() = w()) + Σi-1 Sw((t) also converges. Let
- c0)
(218)
lim (1) = w. ++
(219)
This means that A(w, )w,, A.w, and thus Pdt A(w, 0.i.e w. is fixed point of gradient update (Eqn. 7b. Finally, we have:
2 + 71 cn)
((((t) - w00)l22 S 22(1+))(11- - co)
2 1/22
< 1 /
(220)
f'=0
Since || ||2 is continuous, have the conclusion.
39


Reviews:
[{"review_id": "s7XJQS-BwQ", "reviewer": "Reviewer_Nm96", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors present an interesting training dynamics perspective on the role of nonlinearity in contrastive learning, specifically geared towards self-supervised learning. To this end, they leverage the $\\alpha$-CL loss formulation and study the training dynamics for a single layer and 2-layer MLP. Firstly, the authors show that a linear single-layer MLP is only capable of learning the principal directions in the data but a single-layer MLP with reversible nonlinearity (e.g. ReLU) has several attractors in the state space and can thereby learn more complex data distributions. Furthermore, they extend their analysis to two-layer MLPs and demonstrate the ability to learn specialized weights and the phenomenon of global modulation that alters the structure of the attractor basin. Taken together, this work advances our theoretical understanding of contrastive learning dynamics and enables better network design for specific applications.", "summary_of_the_review": "I think this work has interesting insights about dynamics of contrastive learning and would be highly valuable to the SSL community. In its present form, it might be a bit hard to distill the information to the community, but with minor rewriting, it can be a very impactful paper.", "strength_and_weaknesses": "Strength:\n1. This work presents a strong theoretical analysis of the dynamics of contrastive learning. \n2. The analysis spans both single and 2-layer MLPs. Although it is unclear to me immediately if these results could be extended (using some form of induction) to deeper networks, it is still useful to see the effect of depth and how it interacts with non-linearity.\n3. The theoretical inferences are validated using simple empiricial simulations, which supports the theoretical result and also indicates the robustness of the theoretical results even when the assumptions are not satisfied in practice.\n\nWeaknesses:\n1. In its current form, I feel the paper might be a bit hard to parse for deep learning practitioners who are also interested in theoretical understanding of contrastive learning. I believe this limits the impact of this paper. Furthermore, it would be nice to have a better intuition into what each assumption entails and the context behind each theorem or theoretical result. Currently, the context seems to follow the theoretical result, explaining what it implies to the reader, but adding some context of what theoretical insight is desired might help the reader follow the work better. \n2. The core results of this work rely on the $\\alpha$-CL formulation and is validated using toy data simulations. It would be nice to extend this to slightly complicated datasets, like maybe MNIST, to illustrate how valid the results are for realistic setups. I believe this would greatly enhance the utility of the work and can be impactful to the SSL community.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "oZhbHM0GOs", "reviewer": "Reviewer_TWc2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers training dynamics of simple neural networks on contrastive learning tasks, and studies the effect of non-linearities such as the ReLU on the resulting optima. In the setting considered, the authors find that linear activations lead to simple solutions involving leading eigenvectors of some fixed covariance-like matrix, while the use of non-linear activations leads to a significantly richer picture, with different choices of stationary points that may lead to more diverse features. In the two-layer case, the authors show a \"global modulation\" effect which may better capture latent variables. These theoretical results are illustrated with numerical experiments on a synthetic dataset involving token sequences with some latent structure.", "summary_of_the_review": "good paper. Some questions should be clarified re: non-linear learning vs simply finding multiple principal components", "strength_and_weaknesses": "The paper provides interesting and novel insight on the role of non-linear activations in contrastive learning. In particular, the finding that non-linearities induce more diverse representations, while linear activations only recover leading components, is quite interesting and significant.\n\nThe theoretical analysis also provides useful formulations of the training dynamics for a few different network models, and studies useful conditions for convergence to certain relevant stationary points, namely what the authors call \"locally maximal eigenvectors\" (Definition 3).\n\nThe work also points to interesting directions for future work, for instance on obtaining the probability of finding specific stationary points and on the role of over-parameterization for this setup.\n\nIn this sense, this is a good paper and I support acceptance.\n\nSome aspects of the work could nevertheless be improved to strengthen the paper:\n\n* it is currently unclear if the benefits of the non-linearity are due to (i) the fact that linear activations only recover the top principal component instead of all components, or (ii) non-linear activations are allowing a truly non-linear behavior that is not captured by PCA. It would help to discuss whether the provided examples (in section 3.1, and in the latent-variable model used in the experiments) are an instance of (i) or (ii), and whether a simple procedure like PCA could already recover these latent features. (on this point: are there variants of these CL algorithms/losses that can recover multiple PCA components instead of just the leading one?)\n\n* various results in the paper are still valid even when there are no augmentations, a setting which is often considered difficult in practice due to the risk of collapse. How is the present work positioned in this regard? Is such a collapse avoided here by having a restricted model? If so, could this have practical implications for CL without augmentations?\n\n* the presentation could sometimes provide more insight and intuition. For instance, in the two-layer case (section 4) it would be useful to see what the involved quantities are in a specific example, such as the one from section 5. In Theorem 5, what is the intuition behind the $Delta_k Delta_k^\\top$ term, and how it arises?\n\nminor additional comments:\n- related work: it would be helpful to include other works on training dynamics for CL here and provide a clear comparison to them (e.g. Tian 2022 or Jing et al. 2021), even if they are cited elsewhere in the manuscript.\n- \"$alpha$ is fixed\": some comments on what is lost by considering $alpha$ fixed instead of having it evolve would be a helpful addition\n- after Thm 1 \"lowering roughness could lead to more local optima\": this should be clarified\n- sec. 3.3 \"Let L be the Lipschitz...\": the existence of L should be an assumption\n- Def. 4: add a brief explanation of $\\kappa$?\n- sec. 4 \"how does the network prioritizes\" -> prioritize\n- \"receptive field\": \"patch\" or \"token\" seems more appropriate? but feel free to keep unchanged\n- it would be helpful to write the precise form of the 2-layer network before Lemma 4.\n- after Thm 4 \"the gradient\" -> gradients? \"all points\" -> all point?\n- sec 4.2 \"close form\" -> closed form\n- Figure 5: d = 8 seems to be inconsistent with the d=20 in the text? does it mean you have fewer tokens in this experiment?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jU45HCxnVL", "reviewer": "Reviewer_U4MU", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the role of nonlinearity in training dynamics of contrastive learning. In general, understanding the role of nonlinearity is a very important problem in deep learning. Basically, the authors show that nonlinear models can recover multiple patterns while the linear model can only recover the single pattern that corresponds to the maximal eigenvalue. Moreover, the authors provide simulations to validate their theory.", "summary_of_the_review": "Please see the strength and weaknesses section.", "strength_and_weaknesses": "## Strength \n- This paper studies a very important problem, i.e., what is the role of nonlinearity in contrastive learning? They study 1/2 layer neural networks with a general $\\mathbb{C}_{\\alpha}$ loss function. In particular, they show that linear neural networks can only learn one feature corresponding to the maximal eigenvalue, while the nonlinear neural network can recover multiple features.\n\n- This writing is quite good.\n## Weaknesses\n- Though the authors provide simulations to verify the proposed theory, it is still not clear how realistic the theory is and what is the gap between the considered scenario and the realistic settings. \n- At the end of page 2, the authors mention that in this paper they consider the case that $\\alpha$ is fixed. My concern is how realistic is this assumption. Taking InfoNCE as an example, $\\alpha$ depends on the neural network parameter $\\theta$. I suspect the reason that one reason the authors think $\\alpha$ can be fixed is the existence of the stop gradient operator. However, in reality, people will modify it dynamically even if the existence of stop gradient operator. Hence, the setting considered in this paper might not be realistic.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "F1elpmXWGSi", "reviewer": "Reviewer_h1XP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies the role of nonlinearity in the training dynamics of contrastive learning on one and two-layer nonlinear networks with homogeneous activation. The authors obtain two major results. First, for one-layer neural networks, the nonlinearity can lead to many local optima and each corresponding to certain patterns from the data distribution, while sfor the linear counterpart only one major pattern can be learned. Second, in the two-layer case, the nonlinearity is capable of learning specialized weights into diverse patterns. Besides, the authors discover global modulation namely those local patterns discriminative from the perspective of global-level patterns are prioritized to learn. Finally, the authors conduct experiments to verify theoretical findings.", "summary_of_the_review": "The paper presented a relatively novel idea (to me) that studies nonlinearity in contrastive learning. It presented a set of thorough theoretical analyses and experiments to validate the method. I tend to accept this paper. However, the authors are encouraged to address the weakness I list above.", "strength_and_weaknesses": "**Strength**\n\n* This work studies the role of nonlinearity in contrastive learning which is a critical problem and of great interest to the deep learning theory community.\n\n* The paper presents an insightful and novel idea by introducing $\\alpha$-CL that proposes a general CL framework that covers a broad\nfamily of existing CL losses.\n\n* I like the solid theoretical analyis of this work most. From one-layer to two-layer neural network, the authors fully demonstrates the role of nonlinear activation functions in contrastive learning, by contrasting with linear activations. \n\n* The empirical analysis connecting the presented theory is very interesting.\n\n\n**Weakness**\n\n* The related works part is somewhat inadequate. A missing related work [1].\n\n* The mathematical notation of the article is somewhat comfusing, especially when demontrating the energy function $\\mathcal{E}_\\alpha(\\boldsymbol{\\theta})$. Perhaps, the authos could unify the representatin of vector, matrix and scalar.\n\n* Assumption 2 is strong, especially for no augmentation. In my understanding, the augmenttation is indispenable part of contrastive learning.\n\n[1] On the Impact of the Activation function on Deep Neural Networks Training. ICML 2019. Soufiane Hayou, Arnaud Doucet, Judith Rousseau", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster