Towards Demystifying Representation Learning with Non-contrastive Self-supervision
Authors: Xiang Wang
Xinlei Chen
Simon Shaolei Du
Yuandong Tian
Venue: ICLR 2022 Submitted (2022)
Keywords: self-supervised learning
representation learning
non-contrastive methods
DirectPred
theoretical analysis

Abstract: Non-contrastive methods of self-supervised learning (such as BYOL and SimSiam) learn representations by minimizing the distance between two views of the same image. These approaches have achieved remarkable performance in practice, but it is not well understood 1) why these methods do not collapse to the trivial solutions and 2) how the representation is learned. Tian et al made an initial attempt on the first question and proposed DirectPred that sets the predictor directly. In our work, we analyze a generalized version of DirectPred, called DirectSet($\alpha$). We show that in a simple linear network, DirectSet($\alpha$) provably learns a desirable projection matrix and also reduces the sample complexity on downstream tasks. Our analysis suggests that weight decay acts as an implicit threshold that discard the features with high variance under augmentation, and keep the features with low variance. Inspired by our theory, we simplify DirectPred by removing the expensive eigen-decomposition step. On CIFAR-10, CIFAR-100, STL-10 and ImageNet, DirectCopy, our simpler and more computationally efficient algorithm rivals or even outperforms DirectPred.

Under review as a conference paper at ICLR 2022
TOWARDS DEMYSTIFYING REPRESENTATION LEARN- ING WITH NON-CONTRASTIVE SELF-SUPERVISION
Anonymous authors Paper under double-bling review
ABSTRACT
Non-contrastive methods of self seff-supervieed learning (such as BYOL and Sim- Siam) learn representations by minimizing the distance between two views of the same image. These approaches have achieved remarkable performance in prac- tice, but it is not well understood how the representation is learned based on the augmentation process. Tian et al. (2021) explained why the representation does not collapse to zero and proposed DirectPred that sets the predictor directly. In our work, we analyze a generalized version of DirectPred, called DirectSet(a). We show that in simple linear network, DirectSet(a) provably learns desirable projection matrix and also reduces the sample complexity on downstream tasks, Our analysis suggests that weight decay acts as an implicit threshold that discard the features with high variance under augmentation, and keep the features with low variance. Inspired by our theory, we simplify DirectPred by removing the ex- pensive eigen- decooposoonnniionn step. On CIFAR- 10, CIFAR- 100, STL-10 and Im- ageNet, DirectCopy, our simpler and more computationally efficient algorithm. rivals or even outperforms DirectPred.
INTRODUCTION
Self-supervised learning recently emerges as promising direction to learn representations without manual labels. While contrastive learning (Oord al., 2018: Tian al., 2019; Bachman et al., 2019; He et al., 2020; Chen et al., 2020a) minimizes the distance of representation between pos- itive pairs, and maximizes such distances between negative pairs, recently, non-contrastive self- supervised learning (abbreviated as nc-SSL. is able to learn nontrivial representation with only positive pairs, using an extra predictor and a stop-gradient operation. Furthermore, the learned representation shows comparable (or even better) performance for downstream tasks (e.g., image classification) (Grill et al., 2020; Chen & He, 2020). This brings about two fundamental ques- tions: (1) why the learned representation does not collapse to trivial (i.e., constant) solutions, and (2) without negative pairs, what representation nc-SSL learns from the training and how the learned representation reduces the sample complexity in downstream tasks.
While many theoretical results on contrastive SSL (Arora et al., 2019; Lee et al., 2020; Tosh et al., 2020; Wen & Li, 2021) do exist, similar study on nc-SSL has been very rare. As one of the first work towards this direction, Tian et al. (2021) show that while the global optimum of the non- contrastive loss is indeed trivial one, following gradient direction in ne-SSL, one can find local optimum that admits nontrivial representation. Based on their theoretical findings on gradient- based methods, they proposed a new approach, DirectPred, that directly sets the predictor using the digo-ddcoopposition of the correlation matrix of input before the predictor, rather than updating it with gradient methods. As a method for ne-SSL, DirectPred shows comparable or better perfor- mance in multiple datasets, including CIFAR-I0 10 (Krizhevsky et al., 2009), STL-10 (Coates et al., 201 and ImageNet (Deng et al., 2009), compared to BYOL (Grill et al., 2020) and SimSiam (Chen & He, 2020) that optimize the predictor using gradient descent.
While Tian et al. (2021) address the first question, i.e., why the learned representation does not collapse, they do not address the second question, i.c., what representation is learned in ne-SSL and how the learned representation is related to the data distribution and augmentation process and in turn whether it reduces the sample complexity in downstream tasks.

---

Under review as a conference paper at ICLR 2022
Main Contributions. In this paper. we make first attempt towards the second question, by study- ing a family of algorithms named DirectSet(a)) in which the DirectPred algorithm proposed by Tian et al. (2021) is special case with 1/2. Our contribution is two-folds:
First, we perform a theoretical analysis on DirectSet(a) with linear networks. Our analysis shows that there exists an implicit threshold, determined by weight decay parameter 77, that governs which features are learned and which are discarded. More specifically, the threshold is applied to the vari- ance of the feature across different data augmentations (or "views") of the same instance: nuisance features (features with high variances under augmentation) are discarded, while invariant features (i.e.. with low variances) are kept. We further make a formal statement on the sample complexity of the learning process and performance guarantees of the downstream tasks, in the linear setting similar to Tian et al. (2021). To our knowledge, this is the first sample complexity result in nc-SSI..
Second, we show that DirectCopy, a special case of DirectSet(a) when 1, performs comparably with (or even outperforms) DirectPred in downstream tasks in CIFAR- 10, CIFAR- 100, STL-10 and ImageNet. In DirectCopy, the predictor can be set without the expensive eigen-decomposition operation, which makes DirectCopy much simpler and more efficient than DirectPred.
Related works. In ne-SSL, different techniques are proposed to avoid collapsing. BYOL and Sim- Siam use an extra predictor and stop gradient operation. Beyond these, BatchNorm (including its variants (Richemond et al., 2020)), de-correlation (Zbontar et al., 2021; Bardes et al., 2021; Hua et al., 2021), whitening (Ermolov et al., 2021), centering (Caron et al., 2021), and online clus- tering (Caron et al., 2020) are all effective ways to enforce implicit contrastive constraints among samples for collapsing prevention. We study BYOL and SimSiam as representative nc-SSL methods.
Organization. The paper is organized as follows. Section 2-3 introduce DirectSet(a), prove it learns a projection matrix onto the invariant features, and the learned representation reduces sample complexity in downstream tasks. Section 4 demonstrates that DirectCopy achieves comparable or even better performance than the original DirectPred algorithm in various datasets, and Section 5 shows ablation experiments. Finally, limitation and future works are discussed in Section 6-7.
2
PRELIMINARIES
2.1 NOTATIONS
We use La to denote the d x d identity matrix and simply write I when the dimension is clear. For any linear subspace S in Rd, we use P' E igd to denote the projection matrix on S. More precisely, the projection matrix Ps equals UUT where the columns of U constitute a set of orthonormal bases for subspace S. We use (J, Σ) to denote the Gaussian distribution with mean μ and covariance E.
We use ||-I| to denote spectral norm for a matrix, or bg norm for a vector and use ||-1| r to denote Frobenius norm for a matrix. For real symmetric matrix A E dRdxd whose dggo-ddccomoositoon is EL Auuut use |A| to denote Σ |A/] u,u, If A is also positive semi-definite, use A to denote Ed X3 u for any positive a E R.
2.2 DIRECTSET(()) AND DIRECTCOPY
In ne-SSL, recent methods as BYOL (Grill et al., 2020) and SimSiam (Chen & He, 2020) employ dual pair of Siamese networks (Bromley et al., 1994): one side is a composition of an online network (including projector) and a predictor network, the other side is target network (see Figure I for a simple example). The target network has the same architecture as the online network, but has potentially different weights. Given an input x, two augmented views æ1, Z2 are generated, and the network is trained to match the representation of xi (through the online network and the predictor network) and the representation of i22 (through the target network). More precisely, suppose the online network and the target network are two mappings fe: Je, Rd + R² and the predictor network is a mapping gep- R + Rh, the network is trained to minimize the following loss:
[gg,, (x1)]] StopGrad ( for (22)
go, (fo(z1))
L(0,0p: 0.) 2 Bay.ar
(x2)
In BYOL and SimSiam, the online network and the target network are trained by running gradient methods on L.. The target network is not trained by gradient methods; instead, it is directly set with
2

---

Under review as a conference paper at ICLR 2022
Lz loss
BYOL: Gradient methods
Do, (x,))
Stop Gradient
Predictor (8,)
DirectSetla):
F
W = | + el, with F (x
fo().)
Gradient methods
Online W
Target (0,)
EMA of W
X1
X2
Augmentation
Figure 1: Problem Setup. Comparison between BYOL and DirectSet(a) linear network.
the weights in the online network (Chen & Hc, 2020) exponential moving average (EMA) of the online network (Grill et al., 2020; He et al., 2020; Chen al., 2020b).
The DirectSet(a)) algorithm, shown in Figure 1, directly sets the predictor based on the correlation matrix F the predictor inputs:
Fa
W
+ eT,
where == =E fozx In practice, F is estimated by a moving average over batches. That where Eg is the expectation over one batch.
is, F= =f (0l1-))Be
In the original DirectPred proposed by Tian al. (2021), is fixed 1 1/2. To compute 11/2 one needs to first compute the desempocoooooiioonn of F, and then taking the root of each eigenvalue. This step of cigen-decompositio can be expensive especially when the representation dimension is high. To avoid the decoopossoiiiionn step, we propose DirectCopy (a 1), in which the predictor W, is direct copy of the F (with normalization and regularization)'. As we shall see, DirectCopy enjoys both theoretical guarantees and strong empirical performance.
3 THEORETICAL ANALYSIS OF DIRECTSET(()
Deep linear networks have been widely used as a tractable theoretical model for studying nonconvex loss landscapes (Kawaguchi, 2016; Du & Hu, 2019; Laurent & Brecht, 2018) and nonlinear learning dynamics (Saxe al., 2013; 2019; Lampinen Ganguli, 2018; Arora et al., 2018). However, most of them are for supervised learning setting. Tian al. (2021) analyzed nc-SSL on linear network, but not analyze their proposed approach DirectPred. Here, we analyze the representation learn- ing process of DirectSet(a)) minimal setting where the online network fo is single linear layer. We also verify DirectSet(a) works for practical nonlinear deep models and realistic datasets.
3.1 SETUP
In this subsection, define the network model, data distribution and simplify DirectSet(a) algo- rithm for our theoretical analysis. We consider the following network model (see Figure 1), Assumption 1 (Linear network model). The online, predictor and target network are all single-layer linear network without bias, with weight matrices denoted as W, W,, W,, E 12dxd respectively.
For the data distribution, assume the input space is direct sum of invariant feature subspace and a nuisance feature subspace. Specifically, we assume
Assumption 2 (Data distribution). The input x is sampled from (0, Ta), and its augmented view I1, F2 are independently sampled from (zz o² PBP)) where B is (d r) diddinssio subspace. We denote as the orthogonal subspace of B in RRd
'Computing the spectral of F is much faster than computing the cigen-dccomposition F. because the former only needs the top eigen-vector of F. Table 4 shows that the spectral norm can also be replaced by Frohenius norm normalization, and similar performance can be achieved.
3

---

Under review as a conference paper at ICLR 2022
In this simple data distribution, subspace S corresponds to the features that are invariant to augmen- tations and its orthogonal subspace B is the nuisance subspace which the augmentation changes. We will prove that DirectSet(a) can learn the projection matrix onto S subspace. Note in the previous work (Tian et al., 2021), they assumed the covariance of the augmentation distribution to be o² and did not study what representation is learned.
For the convenience of analysis, we consider a simplified version of DirectSet(a). We compute the loss function without normalizing the two representations, the population loss is
1 L(W, W.. Wp) E WW, StopGrad (W.za)ll?
(1)
and the empirical loss
L(W, WT Wa) =
1 2n
n
W Way - StopGrad (Wa (0
(2)
where 200's are independently sampled from N(0, T), and augmented views (1) and x2 are inde- pendently sampled from ((x(()), PB). To train model, first, we initialize W as å with d positive real number. We run gradient flow or gradient descent on online network W with weight the
decay 77, and set the the target network W. W. For clarity of presentation, when training population loss, we set Wp as (WEzI W y = (WWT) instead (WE,, 2 WT) )o as in practice; when training on the empirical loss, we set Wp as (W -W (x(1) W T) Here, we set the predictor regularization
0 and its influence will be studied Section 5.
In the following, DirectSet(a)) is shown to recover the projection matrix Ps with polynomial number of samples. Furthermore, given that the learned matrix is close to Ps, the sample complexity on downstream tasks is reduced.
3.2 GRADIENT FLOW ON POPULATION LOSS
In this section, we show that DirectSet(o)) running on the population loss with infinitesimal learning rate and weight decay can learn the projection matrix onto the invariant feature subspace S. Theorem 1. Suppose network architecture and data distribution follow Assumption I and Assump- tion 2, respectively. Suppose we initialize online network W as ôI, and run DirectSet(ai oi) popu- lation loss (see Eqn. 1) with infinitesimal step size and weight decay. If we set the weight decay 1/(2o)
coefficient 17
(an-->>) 1)
and initialization scale ō >> (1 1--]-=
then W converges to
1+ 11-11 1/(2n) Ps when time goes to infinity.
Theorem 1 shows that when the weight decay is in certain range. and when the initialization is large enough, the online network can converge to the desired projection matrix Ps 2 In sequel, we explain how the dynamics of W leads to a projection matrix and how the weight decay and initialization scale come into play. We leave the full proof in Appendix B. We also consider the setting when W, is set as (WIE,, T W WT in Appendix B.4 and extend the result to deep linear networks in Appendix C.
Due to the identity initialization, can ensure that W is always real symmetric matrix and is simultaneously diagonalizable with Pg. We can then analyze the evolution each eigenvalue in W separately. Under our assumptions, it turns out that all the eigenvalues whose eigenvectors lie in the B subspace share the same value Åg, and all the eigenvalues in the S subspace share the value As as shown in the following time dynamics:
ÀB = AB [- 0²) [AB]" 40 + |AB - m
Às = As [1sss
+ |As -n
(3)
Next, we show λB converges to zero and \s converges to a positive number, which immediately implies that W converges some scaling of Ps.
1/(2a) in which case W
Note that Theorem also holds with negative initialization 8 < 11-V1
1/(2))) Ps. Our other results can be extended to negative 5 in similar way.
1++/I=
converges to
4

---

Under review as a conference paper at ICLR 2022
Exevereen of Egeevvliues of (-TTLL 150.100 weight decay-0)
Dveivement of Eigoivaluess of IC RAR 10. weight decay-0)
Raacn 10
50
taxch
Ag
Epeen Cpeen
-12
60
100
120
46
100
Sotted dkgrtake
is
verert Elgenro use (5TL-10 weight (.00)-1..000) vemeet Elgervatues of (CIIA 16, weight decacc0 0.000000000)
Bad
Good Basin
Rpace
Basin
trach
25
Spact
1og www.oraeee
Faich
Eoach
23
Spach
Spact 95
B-369
40 150 -29
40 60
200 1.2
gerrulac
Figure 2: Left: With appropriate weight decay, Äs always converge zero; Às converges to when it's initialized in the bad basin and converges positive Xğ when it's initialized the good basin. Middle: The evolvement of the eigenvalues of when it's trained by DirectCopy with e = 0.2 on STL-10, With weight decay 1 = 0.0004 (bottom), the cigen-spectrum at epoch 95 has sharp drop; while the drop is much milder when r7 = 0 (top). Right: Similar phenomenon CIFAR-10 with = 0.3.
Similar as the analysis in Tian et al. (2021), when vj > 3(1+02): we know A < for any AB and AØ = 0 a stable stationary point, as illustrated in Figure (top, left). Therefore, as long as
n 11+075 XB must converge zero. When 0 < 1 1. there are three non-negative solutions 1/(2a)
1/(2a)
to As = 0, which are 05 -1-VI~
As illustrated in Figure 2 (bottom, left), if initialization 8 Ag (good basin), Às converges to positive value Aţ; if 0 < 8 < Ag (bad basin), Äs converges to zero.
and A
[
Thresholding role of weight decay in feature learning: While Tian et al. (2021) shows why ne- SSL does not collapse, one key question is how ne-SSL learns useful features and how the method determines which feature is learned. Now it is clear: the weight decay factor 1) makes a call on what features should be learned. Nuisance features subject significant change under data augmentation has larger variance x² and 4([+025 < п, the eigenspace corresponds to this feature goes to zero; on the other hand, invariant features that are robust to data augmentation has much smaller o² and K[+o=] 1) and these features are kept. In our above analysis, B subspace corresponds to the nuisance features and collapses to zero; 5 subspace corresponds to the invariant features (whose variance was assumed as zero for simplicity) and is kept after training.
Figure 2 (middle and right) shows the spectrum of F (which is the correlation matrix of the predictor inputs) when the network trained by DirectSet(1) with and without weight decay v on STL.10 and CIFARIO: when 7) 0, the eigen-spectrum of F in later epochs does not have sharp drop compared with the case of = 0.0004. This means that the nuisance features are not significantly suppressed when 7 O.
Therefore, it is crucially important to choose weight decay appropriately: a too small may not be sufficient to suppress the nuisance features; too large 7) can also collapse the invariant features. As shown in Section 5, both cases lead to worse downstream performance.
3.3 GRADIENT DESCENT ON EMPIRICAL LOSS
In this section, we then proceed to prove that DirectCopy (one special case of DirectSet(a) with 1) successfully learns the projection matrix given polynomial number of samples.
Theorem 2. Suppose network architecture and data distribution are as defined in Assumption 1 and Assumption respectively. Suppose we initialize online network as 8I, and run DirectCopy on empirical loss (see Eqn. 2) with step size and weight decay. Suppose the noise scale o² 1+0²/4 1430"/4) and the initialization is positive constant, the weight decay coefficient v) E (11=02) 1(140=))
5

---

Under review as a conference paper at ICLR 2022
scale 8 is constant at least 1/v2. Choose the step size ry as small enough constant. For any
accuracy è > 0, given n 2 poly(d, 1/2) number of samples, with probability at least 0.99 there exists t = (1log(1/0) such that (here W, is the online network weights at the t-th step):
41 2
W
Ps
Se
The proof proceeds by first proving that gradient descent on the population loss converges in linear rate and then couples the gradient descent dynamics on empirical loss and that on population loss. See the detailed proof in Appendix B.2.
3.4 SAMPLE COMPLEXITY ON DOWNSTREAM TASKS
In this section, we show that the learned representations can indeed reduce the sample complexity on the downstream tasks. We consider the following data distribution for the down-stream task:
Assumption 3 (Downstream data distribution). Each input x is sampled from (0, Ia) and its label y( = =xx(1), w²) + g(t), where w" is the ground truth vector with unit &z norm and g(0) is independently sampled from (0, We assume the ground truth w lies on an r-dimensional subspace S and denote the projection matrix on subspace S simply as P.
In practice, usually the semantically relevant features (S subspace here) invariant to augmenta- tions and the nuisance features (orthogonal subspace of S) have high variance under augmentations. Therefore, by previous analysis, expect DirectSet(a)) learn the projection matrix P.
Suppose {x(() y M+ Raxd (for example the learned online network W) get its representation Px((9, The regularized + |w||2. In the below theorem, loss is then defined as L(w)= == E [ (Px()), w) -y00
training samples. Each input (+)) is transformed by matrix P
we show that when P P p|| is small, the above ridge regression can recover the ground truth w given only Orr) number of samples.
Theorem 3. Suppose the downstream data distribution is as defined in Assumption 3. Suppose P P-P P F S with < 1. Choose the regularizer coefficient p = 21/3, For any ( < 1/2, given Or log(1/() number of samples, with probability at least 1 - Ç. the training loss minimizer w satisfies
Prù w =01l=0(00))
-0/11 3 VF+ vlo((1()
vn
In the above theorem, when is least O (00"(ttoug(1/)) we have P w 0(21/3)
Note that if we directly estimate i without transforming the inputs by P, we need ((d) number of samples ensure that || wIll S o(1) (Wainwright, 2019). The proof of Theorem 3 follows from bounding the difference between P& and w" by matrix concentration inequalities and matrix perturbation bounds. The full proof is in Appendix B.3.
4 EMPIRICAL PERFORMANCE OF DIRECTCOPY
In the previous analysis, we show DirectSet(a)) and in particular DirectCopy (DirectSet(a) with 1), could recover the input feature structure with polynomial samples and make the down- stream task more sample efficient in a simple linear setting. Compared with the original DirectPred (DirectSet(a) with 1/2), DirectCopy is simpler and computationally more efficient algorithm since it directly set the predictor as the correlation matrix F, without the eigen degempeccomooitionn step. By our analysis in Theorem 1, DirectCopy also learns the projection matrix Ps with larger scale
Recall that in Theorem under DirectSet(a), online matrix W converges to with larger o, the scalar in front of P3 becomes larger.
1+ 1++VI-r
1/(2n)
Ps. So

---

Under review as a conference paper at ICLR 2022
compared with DirectPred, which suggests that the invariant features learned by DirectCopy stronger and more distinguishable. Next, we show that DirectCopy is on par with (or even outper- forms) the original DirectPred in various datasets, when coupling with deep nonlinear models on real datasets.
4.1 RESULTS ON STL-10, CIFAR-I0 AND CIFAR- 100
We use ResNet-18 (He et al., 2016) as the backbone network, two-layer nonlinear MLP as the projector, and linear predictor. Unless specified otherwise, SGD is used as the optimizer with weight decay 17 0.0004. To evaluate the quality of the pre-trained representations, we follow the linear evaluation protocol. Each setting is repeated 5 times to compute the mean and standard deviation. The accuracy is reported as "td". Unless explicitly specified, we use learning rate 0.01, regularization = 0.2 on STI.-10; ? 0.02, = 0.3 on CIFAR-10 1- and 0.03, = 0.3 on CIFAR-100, See more detailed experiment settings in Appendix
Num of epochs
100
300
500
STL-10
DirectCopy DirectPred
77.83
82.0110.28
82.95
77.86110.16 16
78.7710.97
1..8
DirectPred (freq=5)
77.5410.11
79.90
80.28.10.22
SGD baseline
75.06=0.52
75.25=0.74
75.25=#0.74
epochs
CIFAR-10
100
CopyctCopy
84.02=0.377
89.17:0.12
89.62=0.100
ImageNet
DirectPred
85.21+0.23
08.8
89.52+0.04
CoryctCopy
68.8
DirectPred (freq=5)
84.93310.29
88.8311.110
89.56.10.13
DirectPred
68.5
SGD baseline
84.49:10.20
08.57
89.33:10.27
SGD Baseline
68.6
CIFAR 700
Table 2: ImageNet Top-1 accu-
DirectCopy
55.40:10.19
61.06.10.14
62.23:10.06
racy DirectCopy, DirectPred and BYOL baseline.
DirectPred
56.60+1..2 27
61.65=0.188
62.68+0.35
DirectPred (freq=5)
56.43::0.21
62. 02.01+0.22 22
63. 15.15 27
SGD baseline
04.54
60.88=0.59
61.42:0.89
Top-1 accuracy of DirectCopy. The numbers for DirectPred, DirectPred (freq=5) and SGD baseline on
Table 1: STL-IIOCITAR-IIOCTTAAR
STL-10/CIFA 10 are obtained from Tian et al. (2021).
We evaluate the quality of the learned representation after each epoch, and report the best accuracy in the first 100/300/500 epochs in Table 1. DirectCopy achieves substantially better performance than the original DirectPred and SGD baseline, especially when trained with longer epochs. DirectPred (freq=5) means the predictor is set by DirectPred every 5 batchs, and is trained with gradient updates in other batchs, which outperforms DirectPred later epochs, but is still much worse than DirectCopy. The SGD baseline is obtained by training the linear predictor using SGD,
STL-10:
CIFAR-10/100: For CIFAR-10, DirectCopy is slighly worse than DirectPred at epoch 100, but catches up and gets even better performance in epoch 300 and 500 (Table 1). For CIFAR-100, earlier epochs, the performance of DirectCopy is not as good as DirectPred, but the gap gradually diminishes in later epochs. Both DirectCopy and DirectPred outperfoms the SGD baseline. Direct- Pred (freq=5) achieves even better performance, but at the cost of a more complicated algorithm.
4.2 RESULTS ON IMAGENET
Following BYOL (Grill al., 2020), we use ResNet-50 as the backbone and a two-layer MLP as the projector. We use LARS (You et al., 2017) optimizer and trains the model for 100 epochs. See more detailed experiment settings in Appendix A.
For fairness, we compare DirectCopy to the gradient-basede baseline which uses the same-sized linear predictor as ours. As shown in Table 2, at 100-epoch, this baseline achieves 68.6 top-1 accuracy, which is already significantly higher than BYOL with two-layer predictors reported in the literature (e.g.. Chen & He (2020) reports 66.5 top-1 under 100-epoch training). DirectCopy using normalized F accumulated with EMA μ 0.99 on the correlation matrix, regularization parameter 0.01 achieves 68.8 under the same setting, better than this strong baseline. In contrast, DirectPred (Tian al., 2021) achieves 68.5, slightly lower than the linear baseline.
7

---

Under review as a conference paper at ICLR 2022
Bad Basin
Good Baain
Good Dasin
Bad Basin
increase
Az
AS
A
Builed
Figure 3: Left: Change of Äs when predictor regularization e increases. Right: Eigenvalues F' when
trained by DirectCopy under different on CIFAR-10 for 100 epochs.
ABLATION STUDY
In this section, we study the influence predictor regularization 6, normalization method, weight decay and degree on the performance of DirectCopy.
Predictor regularization: Table 3 shows that when the predictor regularization increases, the performance of DirectCopy on STL-10 and CIFAR-10 improves at first and then deteriorates. On STL-10. DirectCopy with = completely fails. On CIFAR-10. 10, although DirectCopy with c = achieved reasonable performance epoch 300, it's still much worse than e 0.3.
To better understand the role of we analyze the simple linear setting as in Section 3.1 while setting W WWT cI. Recall that λB the eigenvalue of W in B subspace and Äş that in S subspace. When the weight decay is appropriate, AB still converges to zero. On the other hand, the dynamics for Às is as follows:
2/ + VI 4n
X + 1+ I 1-11-44 4n
As = -s
2
Increasing shifts the two positive stationary points X A towards zero. As illustrated Figure (left), as e increases, when X is still positive, the good attraction basin expands, which means As can converge to a positive value from a smaller initialization; when A shifts to zero, Ag converges to zero regardless the initialization size. See the full analysis in Appendix D.
Intuitively, a reasonable can alleviate representation collapse, but too large e also encourages representation collapse. As shown in Figure 3 (right), when increases from zero, more eigenvalues of F' becomes large; but when e exceeds 0.3, eigenvalues of begin to collapse.
Normalization on F: In our experiments, have been normalizing F by its spectral norm before adding the regularization: W, = [|| + cI. It turns out that we can also normalize F by its Frobenius norm simply skip the normalization step. In Table 4, we comparable performance from DirectCopy with Frobenius normalization or no normalization, especially when trained longer.
Number of epochs
Number of epochs
100
300
100
300
STL-10
STL-10
= 0
10.67
81.1910.39
0.1
78.05
81.60.10.15
Spectral
77.8310.56
82.01:10.28
Frobenius
77.71+0.18
82.06-0.22
0.2
77.8310..56
82.0110.22
None
77.81+00.20
82.00+1.24
31.10+0.80
31.10+0.80
CIFAR-JO
CIEAR-10
Spectral
84.02+0.37
89. 17+0..1
< 0
80.53+1.114
86.07=0.71
Frobenius
84.33.10.22 25
89.62 69.624
6 0.1
83.97#0.25
88, 88.58+0.11
None
81.7610..4
89.2110.17
E 0.3
84.02-1..37
89.17-10.12
6=1
57.38=11.62
43.15
Table 4: 1TL-10/CIFAR-10 Top-1 accuracy of DirectCopy with F matrix normalized by spectral norn/Frohenius norm or normalization.
Table 3: STL-IO/CIFAR-10 Top-1 accuracy of DirectCopy with varying regularization
Weight decay: Table shows that when weight decay 7j increases, the performance DirectCopy improves first and then deteriorates. This fits analysis simple linear networks. Basically, when the weight decay 77 increases, it can suppress the nuisance features more effectively. but a too large weight decay also collapses the useful features.
8

---

Under review as a conference paper at ICLR 2022
Number of epochs
Number of epochs
100
300
100
300
ST7.-10
STL-10
O
71.9410.93
78.5310.40
0 = 2
76.80=0.22
80,90=0.18
17 = 0.0004
0..83+0.56
82.01+0.28
Q = 1
77.83+0.556
82.01+0.28
1 = 0.001
77.65+00.16
80.28+0.16
1/2
77 0.73
77.83-0.37
0.01
58.12+0.94
58.53+0.76
1/4
76.82+00.66
76.82=0.36
CIFAR-1O 10
CIFAR-IO
1 == 0
79.15:10.08
85.35.10.31
a = 2 1
82.9610.56
88.60
1 = 0.0004
84.02210.37
89.1710.12
04.02210.37
89.17:10.12
17 = 0.001
03.91=0.33
87.75+0.16
a 1/2
84.8811.21
88.32=0.57
17 0.01
65.31=1.19
13.63+1.30
a 1/4
84.78:10.21
87.82=0.32
Table 5: 1T1--10CIFAR-10 Top-1 accuracy of DirectCopy with varying weight decay.
Table 6: STL-10/CIFAR-10 Top-1 accuracy of DirectSet(a)) with varying degree
Predictor degree: We compare DirectCopy against DirectSet(a)) with a = 2.1/2, Table shows that DiryctCopy outperforms other algorithms STL--10. On CIFAR-10, DirectCopy is slightly worse at epoch 100, but catches up in later epochs.
BEYOND LINEAR MODELS: LIMITATIONS AND DISCUSSION
Evchvement Elgenwalues o (DinectCops)
vement Egenvo (BYOL. predictord
Evolvement Eigenvslues (BYOL predictori
1og of opereaoo maiee
Spoch 100
Opech
Epcin
Epcis 300
tpech don Spock 500
Eprcn 4cc
op 50e
-10-
-22
0axt 193
300
2437 203
29x71 523
-20
42
03
100 120
23
60
60
1.0 120
40
00
100
320
Figure 4: Figenvalues of F when trained by DirectCopy, BYOL with linear predictor and BYOL with two- layer nonlincar predictor CIFAR-10 for different epochs. Top-1 accuracy 500 epoch is 89.62 for Direct- Copy, 88.83 for BYOL with linear predictor and 90.25 for BYOL with two-layer nonlinear predictor.
As a linear model used study the behavior of nc-SSL, our model does not capture all of its intriguing empirical phenomena. For example, we observed that the discarded nuisance features gradually come back after training over longer epochs. Moreover, whether comes back or not related to the downstream task performance. In Figure 4 on CIFAR-10 10 dataset, both DirectCopy and BYO with two-layer nonlinear predictor show this resurgence of nuisance features, as well as strong performance, while BYOL with linear predictor does not seem to learn new features even when trained longer, which might explain its worse performance.
One conjecture is that at the beginning of training, weight decay prioritize the invariant features (i.e., low variance under augmentation) over nuisance ones. The invariant features then grow, building their own supporting low-level features. After that, the nuisance feature, which is also useful, gradually picked up in later stage. Since the low-level features are already trained through previous steps of propapropag,tion, the nuisance features are encouraged use them the supporting fea- tures, rather than creating their own. In contrast, if we train both the invariant and nuisance features simuitaneously, they will compete over the limited pool of low-level supporting features defined by the capacity of the network, leading to worse learned representations. We believe understanding these phenomena require analysis on the non-linear networks, and we leave it as future work.
7 CONCLUSION
In this paper, we have proved DirectSet(a) can learn the desirable projection matrix in a linear network setting and reduce the sample complexity down-stream tasks. Our analysis sheds light on the crucial role of weight decay ne-SSL, which discards the features that have high variance under augmentations and keep the invariant features. Inspired by the analysis, also designed simpler and more efficient algorithm DirectCopy, which achieves comparable or even better performance than the original DirectPred (Tian et al., 2021) various datasets.
We view our paper as an initial step towards demystifying the representation learning in ne-SSL. Many mysteries lie beyond the explanation of the current theory and we leave them for future work.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. ICML. PMLR, 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. In ICLR, 2019.
Philip Bachman, R Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. arXiv preprint arXiv: (XXi:19900000100, 2019.
Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: Varaane-ivvrrane--vvaanne regularizaioononooo for self-suue learning. arXiv preprint arXiv:2105.04906, 2021.
Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verifi- cation using a" siamese" time delay neural network. NeurIPS, 1994.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. NeurIPS, 2020.
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. arXiv preprint arXiv:2104. 14294, 2021.
Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint 2rXtv:2002.05709, 2020a.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. arXiv preprint arXiv:2011. 2020.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003. 04297, 2020b.
Adam Coates, Andrew Ng. and Honglak Lee. An analysis single-layer networks in unsupervised feature learning. In International conference artificial intelligence and statistics, 2011.
J. Deng, W. Dong, R. Socher, L.J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR, 2009.
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In ICML, 2019.
Alcksandr Ermolov, Aliaksandr Siarohin, Enver Sangineto, and Nicu Sebe. Whitening for self- supervised representation learning. In International Conference on Machine Learning, pp. 3015- 3024. PMLR, 2021.
Rong Ge, Qingqing Huang, and Sham M Kakade. Learning mixtures of gaussians high dimen- sions. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 761-770. ACM, 2015.
Lean-Bastien 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. arXiv preprint arXiv:2006.07333 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, 2020.
Tianyu Hua, Wenxiao Wang, Zihui Xue, Yue Wang. Sucheng Ren, and Hang Zhao. On feature decorrelation in self-supervised learning. ICCV, 2021.
Kenji Kawaguchi. Deep learning without poor local minima. NeurlPS, 2016.
10

---

Under review as a conference paper at ICLR 2022
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Andrew K Lampinen and Surya Ganguli. An analytic theory of generalization dynamics and transfer learning in deep linear networks. In ICLR, 2018.
Thomas Laurent and James Brecht. Deep linear networks with arbitrary loss: All local minima are global. In ICML, pp. 200-2290229222 2907. PMLR, 2018.
Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps:
Provable self-supervised learning. arXiv preprint arXiv:2008.01064 2020.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprini arXiv: 1807.0378, 2018.
Pierre H. Richemond, Caan-Bastien Grill, Florent Altché, Corentin Tallec, Florian Strub, Andrew Brock, Samuel Smith, Soham De, Razvan Pascanu, Bilal Piot, and Michal Valko. Byol works even without batch statisties. arXiv, 2020.
Andrew M Saxe, James McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6122 2013.
Andrew M Saxe, James L. McClelland, and Surya Ganguli. A mathematical theory of semantic development in deep neural networks. Proc. Natl. Acad. Sci. U. S. A., 2019.
Gilbert W Stewart. On the perturbation of pseudo-inverses, projections and linear least squares problems. SIAM review, 19(4):634 662, 1977.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. arXiv preprint 19Xx009906.05849. 2019.
Yuandong Tian, Xinlei Chen, and Surya Ganguli. Understanding self- supervupe learning dynamics without contrastive pairs. arXiv preprint arXiv:2102.068// 2021.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redun- dancy, and linear models. arXiv preprint arXiv:2008. 10150, 2020.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Roman Vershynin. High- digh--iimessooal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Martin J Wainwright. High--imensional statistics: A non-asymptolic viewpoint, volume 48. Cam- bridge University Press, 2019.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. arXiv preprint arXiv:2105.15134 2021.
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. 1708.008888.8 2017.
Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. ICML, 2021.
11

---

,then W converges to Under review as a conference paper at ICLR 2022
A DETAILED EXPERIMENT SETTING
STL-10, CIFAR-10, CIFAR-100 We use ResNet-18 (He ct al., 2016) as the backbone network, two-layer nonlinear MLP (with batch normalization, ReLU activation, hidden layer width 512, output width 128) as the projector, and a linear predictor. Unless specified otherwise, SGD used the optimizer with momentum 0.9, weight decay d 0.0004 and batch size 128. The EMA parameter for the target network is set 0.996 and the EMA parameter μ of the correlation matrix F is set as 0.5. Our code is adapted from Tian et al. (2021)* and we follow the same data augmentation process.
To evaluate the quality of the pre-trained representations, we follow the linear evaluation protocol. Each setting is repeated times to compute the mean and standard deviation. The accuracy is reported as "st" Unless explicitly specified, we use learning rate = 0.01, regularization é = 0.2 on STL-10; y = 0.02, e 0.3 on CIFAR-10 and 7 = 0.03, e = 0.3 on CIFAR-100.
ImageNet Following BYOL (Grill et al., 2020), we use ResNet-50 as the backbone and a two- layer MLP (with batch normalization, ReLU, hidden layer width 4096, output width 256) as the projector. We use LARS (You et al., 2017) optimizer and trains the model for 100 epochs, with batch size 4096. The learning rate is 7.2, which is linearly scaled from the base learning rate 0.45
at batch size 256. Other setups such weight decay (n = 1e-e), "), target EMA (scheduled from 0.99 to 1), augmentation recipe (color jitters, blur, etc.), and linear evaluation protocol are the same as BYOI..
B PROOFS OF SINGLE-LAYER LINEAR NETWORKS
B.1 GRADIENT FL.w ON POPULATION Loss
In this section, we give the proof of Theorem I, which shows that DirectSet(a)) running on the population loss with infinitesimal learning rate and weight decay learn the projection matrix onto subspace S.
Theorem 1. Suppose network architecture and data distribution follow Assumption I and Assump- tion 2, respectively. Suppose we initialize online network W as ōT, and run DirectSet (x) on popu- lation loss (see Eqn. 1) with infinitesimal step size and n) weight decay. we set the weight decay 1/(2o)
coefficient =2) 4) and initialization scale 8
(1-V2-1))
1--
1/(2o) Ps when time goes to infinity.
As we already mentioned in the main text, Theorem proved by analyzing each eigenvalue of W separately. We show that the eigenvalues in the B subspace converge to zero, and the eigenvalues in the 5 subspace converge to the same positive number, which immediately implies that W converges to scaling of the projection matrix Ps.
Proof of Theorem 1. We can compute the gradient terms of W follows,
VL(W) =Ez,,2, W (W,W21 - Warz) T
=W, W,WWE,,115 W, W.Bnn,
Note that the two augmented views æ1, 22 are sampled by first sampling input x from (((,,((0,)) La), and then independently sampling Ti, T2 from Niz, V(z,a2P2 PB). Therefore, know EE, "Ι + o² PPPB and E X22 = I. Recall that we run gradient flow on W with weight decay so the dynamics on W is as follows:
W WW (- + P²Pp) + W.) ,,W,
where the first term comes from the gradient and the second term is due to weight decay.
Since W is initialized as 81, and W, W. W, (WWT)o, we know initially W, Wp. W. I and PB are all simultaneously diagonalizable, which then implies W is simultancously diagonalizable
*Their open source code http://tthhcemoeieeeoeeeeeeeeeee
12

---

Under review as a conference paper at ICLR 2022
with W. This argument continue to show that any time point. W, Wp. Wa I and Py all simultancously diagonalizable. Since W is always a real symmetric matrix, we have W = (WWT)o = |w The dynamics on W can then be written as
W | 20x (- |W| 20 W(I PB) + W) n/W
=W (-((++PPm))WWT W + 1w|20-11 -n)
Let the eigenvalue decomposition of W be Ex=1 Awauy with (u ma}) equals to subspace B. We can separately analyze the dynamics of each AG. Furthermore, we know A1.-... A have the same value Às and Ad-r+1:" Ad have the same value Åg. Next, we separately show that An converge to zero and Ag converges to a positive value.
Dynamics for AB: We can write down the dynamics for XB follows:
Åв AB
- + o²) |A da
+ AB
-
Similar as the analysis in Tian al. (2021), when vj 4(1+o²) know Å 0 for any λB and An = 0 is critical point. This means, long 114005 Xn must converge to zero.
Dynamics for As: We can write down the dynamics for As follows:
As As [- |As! da +Ass| 1
When 0 7 know ás 0 for 22 1--I--47 1+ 1+vI-4y and 's 0 for X
Therefore, as long as 0 K) < and initialization δ2 > 1-vI-4n we know 2 converges 1+v1-4y
++vI-4 00 Furthermore, we know Äs when 2
1+v1-1
2
1/(2a)
Overall, we know when [[1-0"] 11 1 and 8
1-VI-4n
we have XB converge to 12(x)
zero and Äs converge to 1+V1-4n 1/(2a)
That is, matrix W converges to I+VI-4
Ps-
B.2 GRADIENT DESCENT ON EMPIRICAL Loss
In this section, we prove that DirectCopy successfully learns the projection matrix given polynomial number of samples.
Theorem 2. Suppose network architecture and data distribution are as defined in Assumption and Assumption 2, respectively. Suppose initialize online network 81, and run DirectCopy on empirical loss (see Eqn. 2) with "I step size and weight decay. Suppose the noise scale o² [1+02/2 /1 1+30" and the initialization positive constant, the weight decay coefficient v (4(1-0")' 4(1+0=5)
scale 8 is a constant at least 1/v2. Choose the step size " as small enough constant. For any accuracy è > 0, given Z poly(d, 1/2) number of samples, with probability least 0.99 there exists f = (log(11)) such that (here We is the online network weights at the t-th step):
4n Ps
W.
SE
2
When running gradient descent on the empirical loss, the eigenspace of W, can shift and become no longer simultaneously diagonalizable with P3- So we cannot independently analyze each eigenvalue of W. as before, which brings significant challenge into the analysis. Instead of directly analyzing the dynamics of Wt, we first show that the gradient descent iterates W, on the population loss converges Ps in linear rate, and then show that W. stays close to W, within certain iterations.
13

---

Under review as a conference paper at ICLR 2022
Lemma 1. In the setting of Theorem 2, let We be the gradient descent iterations the population loss L. Given any accuracy >> for any 2 Cllog(/E), we have
+
I 4n Ps
W
Se
2
where C' a positive constant.
The proof of Lemma similar as the gradient flow analysis in Section 3.2. Next, we show that gradient descent trajectory on the empirical loss stays close to the gradient descent trajectory on the population loss within ((log(1/E) iterations.
Lemma 2. In the setting of Theorem 2, let W, be the gradient descent iterations on the population loss and let W. be the gradient descent iterations on the empirical loss. For any accuracy > 0, given poly(d, 1/2) number of samples, with probability at least 0.99, for any t S Cooo(1/2),
we have
W
se.
where the constant C' comes from Lemma 1.
Then the proof of Theorem 2 directly follows from Lemma and Lemma 2.
Proof of Theorem 2. According to Lemma 1, we know given any accuracy é', for C' Colog(1/0), we have
4n Ps se
W
where C' is positive constant.
According to Lemma 2, we know given n 2 poly(d, 1/E") number of samples, with probability at least 0.99,
W₁ W. S
Therefore, we have
41
1 VI
4n
W.
Ps
S
W,
Ps + W, W, s 28'.
2
2
Replacing ě' by 8/2 finishes the proof.
In section B.2.1, give the proof of Lemma and Lemma 2. Proofs of some technical lemmas left in Appendix B.5.
B.2.1 PROOFS FOR LEMMA AND LEMMA 2
Proof of Lemma 1. Similar as Theorem 1, we can show that at any step t, W, is simultaneously diagonalizable with Wa,ts W, p,,, I and PB. The update W, is follows,
W41 = W. + w. (-(T PBP)W + W
m)) -))
Let the eigenvalue decomposition of We be Ede T,,T, with span( (ann((u-r44)) {Ug-r+1. (ehh equals to subspace B. We can separately analyze the dynamics of each Xi,- Furthermore, we know Ar. Ay,s have the same value Äs and \g-r+1,11"" Ad, have the same value AB, Next, separately show that AB converge zero and λs converges positive value in linear rate.
Dynamics of An.z We show that
0 ABς (1- 7C,)'8 (1-
for any step size 7 S C2, where C1, C2 are positive constants.
14

---

Under review as a conference paper at ICLR 2022
According to the gradient update, have
X An ydB, [- + + *B,1 77.
We only need to prove that for any AB, E [0, we have
-11 -2 + XB. 7) = (1).
1400/4 1430"/4 /4 and o², 6 are two positive constants. ((1+04)) 1((+02)
This is true since r) E
Dynamics of As:
We show that
1
41
+ vI 4sj
2 (1 (1- 82
2
for any step size y v Ca. where Cs, Ca are two positive constants.
There are two cases to consider: when the initialization scale 8² [1/2,
1+vI-17
prove
1 I 47
1 /1 4n
0 S 2
XB.t S (1 (C-))
82)
2
when the initialization scale 82
|+/1-4
I+
prove
+ I 4n
I (1 - )Ca) (8²
1 vI -I 4n
0 S A B,t
(1-)0a²²
2
We focus on the second case; the proof for the first case is similar. According to the gradient update, we have
As. =ÀS, + 7AS, - + S,t 17]
1 VI 477
1+ VI 4n
=Às, 7Asee
1
We only need to show that As, X5,1
1-v1 O(1) for any X 1- 1'-v1-4 8). This is
1402/4 14302/4 /4 and 0² are two positive constants.
true because 17 E
4(1++2]) 4(1+022)
Overall, we know that there exists constant step size such that after t = O(log(1/ē)) steps, we have
1
41 ē
AB, S and As,
This then implies,
1 V
41
W
Ps
SE
2
Proof of Lemma' 2. We know the update on W2 is
1
n Wa. ( -mW, [o) (3]T]
WH+1 W. TWT pst
W. W
n
and the update on W, is
W W. = TW, (-W,,, W, (T+ o²)))) + Wa.)) W,,
Next, we bound
W W. - -WW+1 - W₂)
According to Lemma 3, we know with probability
at least 1 - O(d²) exp (-Q(((2n//(?)
-- 0² PB
(0 2
1
Σ
(1) [1 (i)T - EE
n
:
n i=1
x
1=1
15

---

Under review as a conference paper at ICLR 2022
Recall that we set Wa,t = We and set Wa, as W,, so we have | - Wa.t = W - Wi
Also since set W... p.t
Wi ( E xtt) [T) W.T and set Wptt W.W,", we have
W.pt - Wp. = W. Wi|| + 2 since || O(1).
Combing the above bounds and recall is constant, we have
W++1 - W. (W2+1 W.) - iw, W. W:ll+ +
Therefore,
W. - W. S Cia',
where C₁ is a constant larger than 1. So for any S C log(1/ē), we have
W -W:-Wa w. - CT ( & (1/))
for some positive constant Cz. Choosing eCut1 we know as long as n poly(d, 1/6), with probability least 0.99, for any s C' (log(1/²), we have
W₂ W; S.
B.3 SAMPLE COMPLEXITY ON DOWN-STREAM TASKS
In this section, we give a proof for Theorem 3, which shows that the learned representations can indeed reduce sample complexity downstream tasks.
Theorem 3. Suppose the downstream data distribution as defined in Assumption 3. Suppose
with 1. Choose the regularizer coefficient p E2/3, For any ( < 1/2, given Orr+ lo)(1/()) number of samples, with probability at least - C, the training loss minimizer w satisfies
P- p|| P-Pl_
(213+ Pw w/ w0 (0(20 svr
f + Vlog(1/S)
VT
Suppose (x((1, ())) are n training samples in the downstream task, let X E Raxdd be the data matrix with its i-th row equal to n00), Denote E IR as the label vector with its i-th entry ( Each input (0) is transformed by matrix P E IR Rddd to get its representation Pz The regularized loss can be written as
L(w)
2n 9ow-1// w/
1 |xPu
P |!ll
This is the ridge regression problem on inputs v has the following close form:
(1
( and the unique global minimizer
i (1 PT PTxxxxx+pp
-1 pTX n
(4)
With the above closed form of ú the proof of Theorem follows by bounding the difference be- tween Púù and w² by matrix concentration inequalities and matrix perturbation bounds. Some proofs of technical lemmas are left in Appendix B.5.
Proof of Theorem 3. Denoting P as P - A, we know || < é by assumption. We can also write y Xw" + where E IR" is the noise vector with its i-th entry equal to g(o) Then, can divide
20 into two terms.
x
X x +p
pT xT
=
n
"
-1 " ATXT (Xw" + (
"
P + 01)
LP x (Xw"
(X+++ +
n
Let's first give upper bound for the second term that comes from the error term AT.
16

---

Under review as a conference paper at ICLR 2022
(+PTXTXP+D)) -1 AT (Xw* + + We first bound the norm of
Upper bounding
X Xw According to Lemma 5, we know with probability at least - exp( exp(-S((n)),
A I O()). Since Xw" is standard Gaussian vector with dimension π, according
I O Therefore, have to Lemma 8, with probability at least exp(-S((n)), Xw" || A TAATXTu" s (()).
Then we bound the norm of A x. "
According to Lemma we know S 0(8). According Lemma 6, we
with probability at least exp(-S((n)), 1 know with probability at least 1 - c/3, A E
< 0 0 (évlog(1/() Therefore, we have
Biv /ORTOR()/C)
(1PTXTXP + pl) 2 P, we have XXPTXTXP-2 x
-1 - Combining with
Since Amnin (n
above bound on - (Xw" + +)]] we know with probability at least - cxpp (2())) - C/3,
( n (H -AXXT (Xw" +5)
é +
B8 (og(g()
00
P
PVn
Analyzing
(1PTxTXP + pl)
1PT x (Xw" +E)
We can
write
LP x as
I 1P X E, where
E B XP 1
Let's first bound the spectral norm of XP. Since P is projection matrix on an r-dimensional subspace S, we can write as UUT, where U gdxr has columns as an orthonormal basis of subspace S. According to Lemma 4, we know with probability at least exp(-
1 vn
S Tmax (v (2ax0) s O()).
2(1) S amin
XU
Since ||U||| < 1, we have - x =
XUUT| S 0()).
According to Lemma 5, we know with probability at least exp(-9(n)),
1
XA
00(
nn
F
So overall, we know |E
Then, we can write
(x = - (- +..
n
According to the perturbation bound for matrix inverse (Lemma 11), we have ||]]| {(({ Then, we have
PT (Xw" + = 1 1PP (=
PP x
n
n
+ ==-pxxTxx
-1 1 (HDT
17

---

Under review as a conference paper at ICLR 2022
We first show that the first term is close w". Let the eigenvalue decomposition of 1 PT X XP be VEVT, where V's columns
orthonormal basis for subspace S. Here Σ Rexr is the diagonal matrix that contains all the eigenvalues of 4P x XP. According to Lemma 4, we know that with probability at least 1 (xxp(Q((n)) all the non-zero eigenvalues of _P XPP are (1)-
Then, it's not hard to show that
1 ( (H "
" P <
This immediately implies that
( (
- x Xw w²
< 0
Next, we bound the norm of the second term F! P_pTT T with probability at least exp(-I(n)), v fore, we have
Similar as before, we know
Xw" S 01)) and
+
PT X
S 0(1). There-
F P X Xw"
1 Vni
x
T
1
Xw"
0
? p2
Finally, let's bound the third term x XP pl) -1 + F))
STpTTT g. We first bound the know |KEll 23 Therefore,
norm of " 1 X ç. with probability at least exp(-s(n)), I ((8/vz) || T E||, where { // |kll According Lemma 7, x with probability at least - </3, we have || X s VF + O O(vlog(1/(). Overall, with probability at least (xp(--((n)) - C/3,
know 1
VTB + /log(1/()))) 1 xT g 5o n
vn
Rd in the subspace S, we have ( ( + pT) -1 + F) oll < O(1lel). Since 1 1 x lies on subspace S, we have
It's not hard to verify that for any vector
(( P pt) -1
VFB+ + log (1/{)s
+F
T x 50
n
Vn
Combining the above analysis and taking a union bound over all the events, we know with probability at least exp(- exp(-R(n)) - 2C/3,
(p+ - + Bč B8vlon log(L/)) 1
VFB + (lg(1/))
10 - w01l =
PVn n
Suppose n 2 O(log(1/()) and setting
21/3
we further have with probability at least C,
21/3 322/3 Tox(1/C) ||0 - w"1 =0
VrB+ + Mlg(11{)a
Vn
Vn
VF + /Tog(1/C) 50 2/3 + gVVF++
nn
where the last inequality assumes é < 1.
18

---

Under review as a conference paper at ICLR 2022
We can also bound
P w²
as follows,
PD w'
Pú Pw Pw Pw"
< Pû Pw
P Pw"
-
P P
|| + ||| || ww w'll
1 2/3 Vr vlos(1/()
+ +BV vlog(1/()
020
+
2/3
vn
vn
00 21/ 21/3+ 1/++BV1 gv + vlog(1/S)
nn
B.4 ANALYSIS WITH W, := (WE,,, 22 T
In this section, prove that DirectSet(a) can also learn the projection matrix when set Wp (WEg, [ W ya For the network architecture and data distribution. we follow exactly the same setting as in Section 3.2. Therefore, we know W, == (WE,, 2 ) = (W o PT)
Theorem 4. Suppose network architecture and data distribution are defined in Assumption I and Assumption 2, respectively. Suppose we initialize online network W as 51, and run DirectPred(a)) on population loss (see Eqn. with infinitesimal step size and n weight decay. Suppose we set W..
W and Wp [WEZ,KIT) W WT)c
ya. Assuming the weight decay coefficient v) E [1++0>1--
and initialization scale 8 > when time goes to infinity.
4n (L 2
1/(2x)
we know W converges to [1+VT=41
1/(2a)
Ps
The only difference from Theorem 4 is that now the initialization ō is only required to be larger than 4(1+o4)=12a- The proof almost the same as in Theorem
Proof of Theorem 4. Similar as the proof of Theorem 1, we can write the dynamics on W is as follows:
W
PB) W.) nnW
-IW'(T+0PPp)) (- o2 W(I 02 + W) n
- PB) |i| + 1w/20 -
P2) 1+2a
Dynamics for AB= We can write down the dynamics for ÅB as follows:
ÅB AB [-(1 1111+0 1422 |i 4a
|>Bl 2xx
When 7) 1(1+=))1TZa> we know ÅB < for any Ag and XB is a critical point. This
means, as long ~[[+)")ााe. An must converge to zero.
Dynamics for Ast The dynamics is same as when setting W, = (WWT)a
Åg Au [- |As 40
|ts 20 n)
so when 0 < < 1 and initialization 520 > I-
we know 2 converges to 1+VI-47 47
2
2
17 < and (-
1/(2a)
Overall, we know when 4(1+02)1125 zero and Äg converge to [+vI-4n 2
we have Xg converge to
1/(2n)
1/(2n)
That is, matrix W converges to
1+vI-4n
Ps.
2
19

---

Under review as a conference paper at ICLR 2022
B.5 TECHNICAL LEMMAS
Lemma 3. Suppose (x(0) (6) O(d/²), with probability at least exp (-Q(Een/d))) we have
2 fi=1 are sampled as decribed in Section 3. Suppose n >
[5 T - - PB
x (x(00) -1 Se.
1=1
1=1
Proof of Lemma 3. For each (f) we can write it as x(() + 21 where x(0) ~ NNO0 1) and 2/0)
(0, o² P²B.. So we have
Σ 1=1
1 (1) + +2 + 12(1T + 21 (x(0T))
11 1=1
According to Lemma 9, we know as long exp(=S(("nn),
2 O(d/2²), with probability at least 1
1 [1] S E.
Similarly, with probability at least 1 - expl Q(((n)))
n
(0) 1
P²Pp Se
n i=1
Next we bound
| E
(0 We know each entry in matrix 1 Er= [=[1]] is the
average of n zero-mean ((1) (u)-ssubexponnttial independent random variables. Therefore, according the Bernstein's 's inequality, for any fixed entry (k:, l). with probability at least exp (-ē2n/d²)
1
oo
S 2/d.
k.l
Taking a union bound over all the entries, we know with probability at least - exp (-En/d)))
x 191
12
191
Se
The same analysis also applies to probability at least 1 - O(d²) exp
Combing all the bounds, we know with
1
o2Pp SE
Similarly, prove that with probability at least Oxd2) exp (-I((En/d"))
n
M
(3)
( 2
- -1 S 4é.
n
1=1
Changing to //44 finishes the proof. Lemma 4. Let X E ignxd be a standard Gaussian matrix, and let U E gaxe be matrix with orthonormal columns. Suppose 2 2r, with probability at least 1 - exp(p ex)(-S(n)), we know
2(11= & Amin [LTTTT xu)
(LUTXTXU)
< Amax (LUT x (XXU 50()).
20

---

Under review as a conference paper at ICLR 2022
Proof of Lemma 4. Since U has orthonormal columns, know XU is n x matrix with each entry independently sampled from (0, 1). According to Lemma 9, we know when n 2 2r, with probability least 1 - exp(-S((n))
1 x)) I maax
XU (JaxU)
211)= I Omin
(vox
= 0(1).
Vn
This immediately implies that
(LUTXTTU)
('UTX ( (TUXXTXU) 00
22(1) & Xmin
< Amax
Lemma 5. Let A be a d d matrix with Frobenius norm é, and let X be x d standard Gaussian matrix. We know with probability at least
XA
S O()).
Vn
F
Proof of Lemma 5. Let the singular value decomposition of A be UEVT, where U, V have or- thonormal columns and 2' is a diagonal matrix with diagonals equal to singular values o, s. Since
|| é, know Σ of =²
Since U is orthonormal matrix, we know X XU is still n x d standard Gaussian matrix. Next, bound the Frobenius norm of X X'. It's not hard verify that all the entries in X are independent Gaussian variables and Xi₃ NV(,,f). According to the Bernstein's 's inequality for sum of independent and sub-exponential random variables, we have for every > 0,
12
Pr
X2 nē2
2 < 2xx -emin (Eeeni of maxje(d) o3)
iE(N),JE[d]
Since E3=03
of
|||| 22 we know maxjeld of S e. We also have Ejetg o3 x
(E)E(g = Therefore, we have
nēt 2z )
82
Pr
Σ
X nē²
21
< 2exp
-emin
[E(M]JE[d]
Replacing by ne? we concluded that with probability at least -exp(-(((())))p)))))- 2 S 2nε
Furthermore, since A = 1, we have
XA
1 Vn
X
XVT
1 nn
5(())
vn
Lemma 6. Let T be dxxd d matrix with Frebenius norm é and let X be d n standard Gaussian matrix. Let & be unit vector with dimension n. We know with probability at least - C/3,
A x < 0 To(e/)))))/))).
Proof of Lemma 6. Let the sigular value decomposition of A be UEVT, We know X E is a d- dimensional standard Gaussian vector. Further, we know VT X E is also d-dimensional standard Gaussian vector. So ΣVT X has independent Gaussian entries with its i-th entry distributed as (0, of). According to the Bernstein's ' inequality for sum of independent and sub-exponential random variables, we have for every >> 0,
]
Pr E
x
x
{2l 22
s 2exp
-emin
21

---

Under review as a conference paper at ICLR 2022
Choosing as O log(1/()), know with probability at least 1 - </3, have
L x E S Log(L/))
Since ||U]| 1, we further have
x El =
& | VV
x x
SO ( (éVlog(L/S))
Lemma 7. Les P E Rexxd be projection matrix on r-ddmmensional subspace, and let & be unit vector Rd. Let X be a x n standard Gaussian matrix that is independent with and &, With probability at least C/3, we have
| x VF + O(
Proof of Lemma 7. Since P is a projection matrix on an r-dimensional subspace, we can write P as UT where U E Rd has orthonormal columns, We know X is still standard Gaussian matrix with dimension X n. Furthermore, U X & an r-dimensional standard Gaussian vector. According to Lemma 8, with probability at least 1 C/3, we have
||U X
T
f + 0 log(1/))
Since ||U|| = 1, we further have
x YUU
x
E S | U
x
E S VF++ O llgg)())))
C ANALYSIS OF DEEP LINEAR NETWORKS
In this section, we extend the analysis in Section 3.2 to deep linear networks. We consider the same data distribution as defined in Assumption 2. We consider the following network,
Assumption 4 (Deep linear network). The online network is l-layer linear networks WiWi-1-- ... W1 with each W, E IRddd, The target network has the same architecture with weight matrices Wa, Wa.111 Wa,1. For convenience, denote W W.W.-1 .., and denote W. as Wa,WWo,11 Wa,1.
Training procedure: At the initialization, we initialize each W, as 51/1,, Through the training, we fix Wd as (WWT)* " and fix each Wa,s as We. We run gradient flow on every W, with weight decay n. The population loss is
L([W)), Wp, (Wa,s)) 2 | WWWWWi-1---. Wix1 - StopGrad (Wo,:W,,-11 Wa, 22,1
Theorem 5. Suppose the data distribution and network architecture satisfies Assumption 2 and As- sumption 4, respectively. Suppose we train the network as described above. Assuming the weight decay coefficient
201(201-2-2))d-- (4al42122)
22 (1+02)++--1 (4od+212))
n
EE
and initialization scale 2
2a1+21-2
we know W converges to cP's as time goes to infinity, where e is a positive number
4a
221141122 2n!+21-2
within
Similar as the setting of single-layer linear networks, we prove Theorem 5 by analyzing the dynamics of the eigenvalues of W. Note that with constant the upper/lower bounds for 7 and scalar in the Theorem are always constants no matter how large is.
Proof of Theorem S. For j 2 i, we use Wise to denote W, Wi-1-..- W; and for j < have Wia We use similar notations for W Wa.paaj. For each W;, we can compute its dynamics as follows:
W. (WeW)) (W,
PPPB) o2
(WR-1aj) + (W (WaWa, T W. (Wa,ft-aj)) nWW
22

---

Under review as a conference paper at ICLR 2022
It's clear that through the training all W,'s remains the same and they are simultaneously diagonal- izable with Wp, and PB. We also have Wa W and Wp |W| Since will ensure that W
always positive semi-definite so W - |W|2 2a W2a W?al So the dynamics for each W; can be simplified as follows:
W₂ -W.40422-11 PB) + W? n,W,
Let the eigenvalue decomposition of W; be E yuu T with subspace B. We separately analyze the dynamics of each vs- Furthermore, we know v1; :.: Mr have the same value Vs and Va-r+1,'- ... Ma have the same value un. We can write down the dy- namics for ug and UB follows,
(p equals to
is V 2 + 5/
221221-1 IjUs,
Aol421 ²B VB 1(16+211(111)) 02 VB
201+21-1
TVBB
Let Ay be the eigenvalue of W corresponding to eigen- diceedirestions u1,... and let Ag be the eigenvalue W corresponding rigen-direction ud-r+1,'.. ud- We know As v's and Xø V/2- So we can write down the dynamics for Xø as follows,
ÅB = Lv
L/ Anf++1 22 21 (2) + Iv 20t+3t-2 1np
1A
44 2/1 (1+ + 0²) 11
2-+3-2/1 In
and similarly for Às we have
As 1X5
1x + 115 122043- 22244-2//1 Inds.
Dynamics for AB:
We can write the dynamics on AB as follows,
ÅB (>Bg(AB),
where g(BB) : -> 2 o2) + AB 2--2- 17. We show that when is large enough,
g(XB) negative for any positive λB. We compute the maximum value of g(AB) for AB O. We first compute the derivative of follows:
g' (AB) (4xx + 2 2/1)(1 + ) 40+1 2/1 (2a + 2 = 20-1111-11 2-/1-2/1
=> 2//1-2/1 (-(4a + 2 2--2/1)(111111 0 + (2a: 2/1))
It's clear that (AB) 0 for X (0, 201+21-2 and d(()B) 0 for X
(4o142) +) too). Therefore, the maximum value of g(\B) for positive \g takes X
2a1+21-2
2al+21 2
and
(4n/+22 (1:22(22) ()(++
2+ + (1+0?) (
1+
2nd 21 2
2al 2
g(\/)
(4al + 21 2) 02)
(4al + 21 -2) + 02)
11
2al(2al + 21 -2) 1)
(4al + 21 2) - 3/4 (1 02) 1 7
2a((2a(221-2) -
As long 17 (4al-21-2) - al (1+02)1+ we know g(AB) 0 for any d > 0, which
further implies that Xn 0 for any An 0. So An converges zero
Dynamics for As We can write down the dynamics on As as follows,
Äs IAgh(As),
where l((ss) - 44422221 -4422-2/1 + 22 2a+2-2/1 7)- We compute the derivative of h as follows:
M((ss) = 22011-2/1 (-(4a 2 2/1) (2a: + 2 -2/1))
23

---

Under review as a conference paper at ICLR 2022
(2al+11-2 20 and decreasing in ( 4al+21-2
(2alt21-3 (1at4112
20 00). The maxi-
So h(As) is increasing in (0,
2al+21_2 क
mum value of h for positive Äs takes at Ag = 1od+21-2
and we have
2al(2al + 21 2) 2)1+ 7
h(Ag))
(4al + 2)
As long as 2o1(2ot4 2)
(4 2)-2) at we have 1(x3) > 0. Furthermore, since h is increasing in (0, Az) and is decreasing in (Agr o0) and h(0), )((0))=- < 0, we know there exists Xg E (0, Xg). A e
(Ag, oo) such that h(As) < 0 in (0. Xg), h(As) > 0 in . ^ and h(As) < 0 in (Ag. oc).
Therefore, as long as 2 x A5. we have Äs converges to Xg. Since h(1) < 0, we know
X
20-+21-2 2e 1a!+21-2
1).
2all + 7
2ol(2olt21-22) -
Overall as long 17
we know W
(4a/+2122)* क (1+ (4al+21-2)2+)
converges cPs, where e is a positive number within
20l+21-2
1).
4ol+21-2
D ANALYSIS OF PREDICTOR REGULARIZATION.
In this section, study the influence of predictor regularization in simple linear setting. In particular, we consider the same setting as in Section 3.2 except that we set W, == (WW ) tel. Theorem 6. In the setting of Theorem except that we set W (WW yo + cT. We have
when [0, 1+v[-In) as long as 8 [max [- e,0)) we have W con-
2
verges to
Ps;
when 14vT-40
W always converges to zero.
Proof of Theorem 6. We can write the dynamics of W as follows.
W =W, (-W,W(T- + o² PP) + Wa) nn
=W -( (1i7 +c1) (Iw)2a + +cl) -n)
Let the eigenvalue decomposition of W be Ed Xuuu, with ppan(fudrrt,-- ual) equals to subspace B. We can separately analyze the dynamics of each A, Furthermore, we know " Ap have the same value Äg and 'd-rt1,'.- Ad have the same value Ag.
Dynamics for Ag:
We can write down the dynamics for Ag as follows:
AB - + 0 (11 2ax + +))² =)² + (1>B) 2a + =
ÅB
When 17 > I-++o_ we still know Åp < for any AB > 0 and AØ = O is critical point. So Ap converges to zero.
Dynamics for As:
We can write down the dynamics for As follows:
[- (1As12a =e) + (1251 20 +e)
Às =As
= As (Mss +c- 1- v1 4n
MMsl +c-
1+ /1 1-441 4n
2
2
where the second inequality assumes < < 7- We have
24

---

Under review as a conference paper at ICLR 2022
2.0)) 2x
when e E [0.
1-vl-an)
as long as 8 >
max 1-vI--57
.e have As con-
2
2
verges to
1-vI-1n
1-
0;
when 2
1tv1-4n 4n
As always converges to zero.
E TECHNICAL TOOLS
E.
NORM OF RANDOM VECTORS
The following lemma shows that a standard Gaussian vector with dimension n has norm concen- trated at vn.
, Lemma 8 (Theorem 3.1.1 in Vershynin (2018)). Let X = X2,, ... (x) E RR be a random
X2,
vector with each entry independently sampled from (0, 1). Then
Pr[|||=||| - vnl 2 S 2exp(-12/0)
where C. is an absolute constant.
E.2 SINGULAR VALUES GAUSSIAN MATRICES
The following lemma shows a tall random Gaussian matrix is well-conditioned with high probability. Lemma 9 (Corollary 5.35 in Vershynin (2010)). Let be an N x n matrix whose entries are independent standard normal random variables. Then for every 2 with probability at least 1 - 2 (exp(-(2/2) one has
VN- Vn -n-ts (min((A S Smax (A) S VN vn+t
E.3 PERTURBATION BOUND FOR MATRIX PSEUDD-INVERSE
With lowerbound min (A),
get bounds for the perturbation of pseudo-inverse.
Lemma 10 (Theorem 3.4 in Stewart (1977)). Consider the perturbation of a matrix A E Rmxx, B A + E. Assume that rank A) rank ()) n, then
Bt A < 2 A |
The following corollary is particularly useful for us.
Lemma 11 (Lemma G.8 in Ge et al. (2015)). Consider the perturbation of a matrix E Rmxx
B A + E where || mmin (A)/2. Assume that rank( A) rank [) n, then
|| B A'll s 22/2 mmin (A)².
25


Reviews:
[{"review_id": "dTP4w3p8-V3", "reviewer": "Reviewer_racS", "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": "- the main paper seems correct. Technically it is strongly inspired by the analysis in Tian et al. 2021. In chapter 2 their algorithm is generalized by the additional exponent of the correlation matrix F. From reading the paper it remains a bit elusive why this is done (apart from the nice consequence that for alpha=1 the method is simpler). It would be great to have add an intuition why this was/is done.\n- I see the main contribution of the paper in the analysis of the representation learning on the simple toy data with linear invariant & nuisance spaces, which is nice and novel to my knowledge. This result is not surprising - as all nc-ssl methods are designed to perform exactly this separation. But it's great to have a mathematical analysis on this.\n- the empirical analyses follow the same experiments as in Tian et al. 2021, with comparable results. The results of Section 4.2. on ImageNet should be put into a table (and the best methods bolded). Like this it feels like the results are hidden.\n\n\nMinor Issues.\n- I find the point in the abstract \"why these methods do not collapse to the trivial solutions\" quite strong, as Tiang et al have made quite a good analysis on this. So, I'd suggest to rephrase and focus instead on your contribution (the 2nd point), and refer to this point being already analyzed (instead of having an enumeration).\n- Figure 2: please add X axes labels on the leftmost plots. On the rightmost plots: can the eigenvalues corresponding to eigenvectors in the invariant subspace and the ones from the nuisance subspace be visually separated? Right now, one has to assume, instead of know, that the smaller ones are the nuisance ones.\n- Theorem 2: eps is overloaded, which might be confusing to the reader. It's already been used as the regularization parameter in the description of the algorithm.\n- please check again all verb forms throughout the paper, also singular and plurals are often wrong. Some sentences are very long and could be reduced in length for better readability (a style taste issue of course).", "summary_of_the_paper": "The paper \"Towards demystifying representation learning with non-contrastive self-supervision\" presents and analyzes a family of algorithms, DirectSet(\\alpha), for non-conctrastive self-supervised learning with only positive pairs. The theoretical analysis assumes linear layers, and focuses on a special data distribution assumption, where the input space is separated in two linear subspaces, one invariant under the 'data augmentations', the other being the complement. It is then shown that the proposed algorithm converges to the projection matrix onto the invariant sub-space. Further it is shown theoretically that this has the down-stream advantage reduced sample complexity for learning on this representation. Empirically, it is shown that the method performs on par, or sometimes slightly better, than the previously proposed closely related method DirectPred (Tian et al. 2021). ", "summary_of_the_review": "The paper seems overall technically correct. It presents a nice analysis that illustrates how the representation learning happens in a toy data setting and proposes a slightly more simple algorithm than in previous work. This is great, though not a major step forward (as ssl methods are designed to do this, the results are expected IMHO). Further, the experimental analyses indicate no significant improvements over previous work.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RnmS0bH_5Nv", "reviewer": "Reviewer_5xNt", "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": "Positives:\n- The work highlights the important role weight decay plays in learning a good representation.\n- The work replaces an existing algorithm, DirectPred, with DirectSet and DirectCopy, which has comparable performance while being cheaper and more efficient.\n- This work has strong theoretical proofs that support their arguments.\n\nWhereas the proofs are sound, I struggle with appreciating the intended novelty of this work.  The work performed in this paper seems heavily preoccupied with two parts: 1) analyzing DirectCopy, which seems to be a cousin of a previously proposed algorithm DirectPred, as well as the DirectSet family as a whole, and 2) using DirectCopy to show the importance of weight decay.\n\nThe analysis of DirectSet and DirectCopy succeeds at proving that it can successfully learn a projection matrix onto an invariant feature space subspace, but essentially boils down to a similar approach as DirectPred (albeit more efficient).  Regarding weight decay, explaining its role, as well as that of other hyperparameters, and why they are important for ncSSL has already been previously explored in [1], and specifically for the BYOL model in prior work.\n\n[1] Tian et al., Understanding Self-Supervised Learning Dynamics without Contrastive Pairs, 2019.", "summary_of_the_paper": "In this paper, the authors make theoretical progress on understanding non-contrastive self-supervised learning (ncSSL).  ncSSL has previously demonstrated strong empirical performance, even outperforming contrastive learning, but the theory behind it is still unclear.  In this work, the authors build off of prior analysis by [1], and showcase the role weight decay has in learning a desirable representation; it acts as a threshold that discards noisy features with high variance introduced by the data augmentation, and keeps stable features with low variance.  \n\n[1] Tian et al., Understanding Self-Supervised Learning Dynamics without Contrastive Pairs, 2019.", "summary_of_the_review": "Overall, I appreciate the incremental theoretical analysis the authors supply to try to understand non-contrastive self-supervised techniques.  I believe their work is sound and thorough, but would welcome more novel insights in this direction.  I would therefore recommend a weak rejection.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KTkfH0tYakX", "reviewer": "Reviewer_G6yG", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "*Contributions*:\n\nThe authors present a generalized formulation, which they call DirectSet(ꭤ), for setting the weights of the predictor network along the lines of DirectPred (Tian et al) and show that there exists an implicit threshold that governs what features are learnt, based on the weight decay 'η'. They show that for the special case with ꭤ = 1, we can obtain higher top-1 accuracy than BYOL on Imagenet, learn more distinguishable features in polynomial number of samples, and reduce the sample complexity on downstream tasks.\n\n*Strengths*:\n\nThe authors present an interesting take on the evolution of invariant and nuisance features throughout training, and how this is acutely affected by the weight decay. Their findings are also well backed-up by experiments: they demonstrate the performance of their method on three different datasets (STL-10, CIFAR-10/100, and Imagenet) along with ablations of important parameters on STL-10 and CIFAR-10. Overall, the paper is well-structured.\n\n*Weaknesses*:  \n- *Major*: The paper seems to be a derivative of previous work (Tian et al) and hence lacks novelty in my opinion. \n\n*Relevance and impact*:\n\nI think this work presents some interesting analysis with the proposed method DirectSet(ꭤ): how it learns useful features, and reduces sample complexity on downstream tasks, but it is not very clear why it doesn’t collapse to a trivial solution. Moreover, it is unclear how their analysis extends more generally to other non-contrastive SSL methods such as BYOL or Sim-Siam. Based on the above reasoning, in my opinion, the paper doesn’t seem to have a strong impact.\n\n*Comments/Questions*:\n\n1. In the ablation study with varying weight decay, the authors also test out ꭤ = 2, which should learn features that are stronger and more distinguishable (as claimed in section 4). Is this the case? Or do such features not translate to better downstream performance? Why aren’t more cases with ꭤ > 1 explored?\n2. Is there some intuition behind why DirectCopy doesn’t perform as well on CIFAR-100, as seen in Table 1?\n3. The authors mention in Section 6 that whether the nuisance features come back or not is related to the downstream task performance. Why is this the case?\n4. The paper is not well-written and is peppered with multiple typos (including the method being called DirectPred in Theorem 1 instead of DirectSet. Also, the related works section could have been a bit more extensive for better context. Figures can be more informative as well with some labels for the regions demarcated by the basins.\n\n", "summary_of_the_paper": "This paper attempts to investigate the reasons behind why non-contrastive SSL methods such as BYOL and Sim-Siam do not collapse to trivial solutions, how they learn representations that are related to the data distribution and augmentation process, and how these reduce the sample-complexity of downstream tasks. It heavily draws upon DirectPred (Tian et al) and generalizes the method for directly setting the weights of the predictor network via a parameter that seems to be tied to the strength and distinguishability of the learnt features. \n\nTian et al: https://arxiv.org/abs/2102.06810", "summary_of_the_review": "I think the paper itself can benefit from clearer writing and some emphasis on how their analysis scales up to explain other non-contrastive SSL methods.\n\nHowever, if I am to evaluate it in a broader context, I think in its current state it lacks novelty to be seen as a standalone piece of work. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7h8yljHiw3x", "reviewer": "Reviewer_6aGh", "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": "\\textbf{Originality & Novelty}: The motivation of the paper is to understand why non-contrastive SSL can learn meaningful representations. The paper does provide a new view point on this question by highlighting the importance of the weight decay coefficient. So far as I know, the analyses and the algorithm is novel. At least the paper is a reasonable improvement over DirectPred. \n\n\\textbf{Strength}: (1) The paper argues that the weight decay coefficient is the key factor that makes ncSSL learns meaningful representations. This argument is very interesting and deserves more investigation in the future. (2) The paper carefully examines nearly all aspects of DirectCopy with experiments.\n\n\\textbf{Weakness}: I think the paper is overall in good shape, with a few minor points: (1) In Fig. 2, even when weight decay is 0, the curves show that some of the eigenvalues are very small after training, and there still exists a 'drop' in the figure, though not as sharp as when weight decay > 0. I wonder why this happens. (2) Basically the analyses are based on SGD. I wonder whether the phenomena will change if other optimizers, like Adam, are used. (3) Another interesting empirical analysis overlooked by the authors is evaluation on more down-stream tasks, like object detection. ", "summary_of_the_paper": "The paper provides a new method for self-supervised learning (SSL), called DirectCopy, based on a previous work DirectPred. An important contribution of this work is theoretical analyses on DirectSet($\\alpha$), a theoretical model on linear neural networks that work with arbitrary $\\alpha$. The authors prove that the weight decay coefficient $\\eta$ has the ability to filter out unnecessary features and hence helps learn useful representations. DirectCopy is a special case of DirectSet($\\alpha$) when $\\alpha=1$. The new algorithm does not require to compute the burdensome eigen-decomposition while enjoying similar empirical performance as DirectPred. ", "summary_of_the_review": "The paper is solid in both theory and experiments. The argument of this paper that the weight decay coefficient is responsible for learning powerful representations, is valuable and intriguing. To summarize, I recommend acceptance of the paper. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper furthers recent work by Tian et al. 2021 to explain how representation learning with non-contrastive self-supervision works. The paper accomplishes this by analyzing a family of algorithms in which DirectPred from Tian et al. (2021) is a special case. Their theoretical analysis is performed with linear networks. Overall, the reviewers questioned the added value relative to Tian et al. 2021, noting that

"The analysis of DirectSet and DirectCopy succeeds at proving that it can successfully learn a projection matrix onto an invariant feature space subspace, but essentially boils down to a similar approach as DirectPred (albeit more efficient)"

The authors in their reply state "how the representation is related to the data distribution and augmentation process," however the relative contribution and why its important isn't transparent.
Decision: Reject