Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods
Authors: Randall Balestriero
Yann LeCun
Venue: NeurIPS 2022 Accept (2022)
Keywords: self-supervised learning
interpretability
understanding
local spectral methods
global spectral methods

Abstract: Self-Supervised Learning (SSL) surmises that inputs and pairwise positive relationships are enough to learn meaningful representations. Although SSL has recently reached a milestone: outperforming supervised methods in many modalities\dots the theoretical foundations are limited, method-specific, and fail to provide principled design guidelines to practitioners. In this paper, we propose a unifying framework under the helm of spectral manifold learning. Through the course of this study, we will demonstrate that VICReg, SimCLR, BarlowTwins et al. correspond to eponymous spectral methods such as Laplacian Eigenmaps, ISOMAP et al.
From this unified viewpoint, we obtain (i) the close-form optimal representation, (ii) the close-form optimal network parameters in the linear regime, (iii) the impact of the pairwise relations used during training on each of those quantities and on downstream task performances, and most importantly, (iv) the first theoretical bridge between contrastive and non-contrastive methods to global and local spectral methods respectively hinting at the benefits and limitations of each. For example, if the pairwise relation is aligned with the downstream task, all SSL methods produce optimal representations for that downstream task.

Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods
Randall Balestriero Meta AI Research, FAIR
Yann LeCun Meta AI Research, FAIR, NYU NYC, USA ylecun@meta.co com
NYC, USA rbalestriero@meta.
Abstract
Self-Supervised Learning (SSL) surmises that inputs and pairwise positive relation- ships are enough to learn meaningful representations, Although SSL has recently reached milestone: outperforming supervised methods in many modalities... the theoretical foundations are limited, method-specific, and fail to provide principled design guidelines to practitioners. In this paper, propose unifying framework under the helm of spectral manifold learning to address those limitations. Through the course of this study, we will rigorously demonstrate that VICReg, SimCLR, BarlowTwins et al. correspond to eponymous spectral methods such as Laplacian Eigenmaps, Multidimensional Scaling al. This unification will then allow us obtain (i) the closed-form optimal representation for each method, (ii) the closed- form optimal network parameters in the linear regime for each method, (iii) the impact of the pairwise relations used during training on each of those quantities and on downstream classification task performances, and most importantly, (iv) the first theoretical bridge between contrastive and non-contrastive methods towards global and local spectral embedding methods respectively, hinting at the benefits and limitations of each. For example, (i) if the pairwise relation is aligned with the be employed successfully and will recover
downstream task, any SSL method the supervised method, but in the low data regime, SimCLR or VICReg with high invariance apper-prramttr should be preferred; (ii) if the pairwise relation is mis- aligned with the downstream task, Barlow or VICReg with small invariance hyper-paramen parammee should be preferred.
Introduction
Self- Supervised Learning (SSL) is one of the most promising method to learn data representations that generalize across downstream tasks. SSL places itself in-between supervised and unsupervised learning as it does not require labels but does require knowledge of what makes some samples semantically close to others. Hence, where unsupervised learning relies on a collection of inputs (X), and supervised learning relies inputs and outputs (X, Y). SSL relies
inputs and inter-sample relations (X, G') that indicate semantic similarity. The latter matrix G is often constructed by augmenting X through data-augmentations known to preserve input semantics (143] e.g. horizontal flip for an image, although recent methods have went away from Data- Augmentation (DA)by using videos from which consecutive frames can be
semantically equivalent 6)
Although SSL originated decades ago 77, recent advances have pushed SSL performances beyond expectations [O]] Due to those rapid empirical advances, urgent need for principled theoretical understanding those methods has emerged [T]] [2]. Studies this direction often take one of the three following approaches: (i) studying the training dynamics and optimization landscapes of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

W-MSESFA
Laplacian Dipemmass space
C contrai
Kennl Locality Presersing Projectoon (propaor)
Figure I: Summary of our unification SSL methods to known local and global spectral embedding meth- ods. In doing so, we able to find the exact set- tings for which different methods provably become identical. In short, all are concerned in preserv- ing left left-singular vec- tors of the similarity matrix G (see Fig, 6 in the repre- sentation Z.
VICReg
book Ja werrint
Localiy Presevvngg Projectian
Stston:
Canonical Correlation
Analysa
a. x
Licer Disciiinan Anilysis
Principul Component Amiysis
BarlowTwine
Regression
Canonical
Analysis (2 (2-space)
"Mulimmmiinal Sealing (+ space)
Kemee Matiodimensincal Scaling (2 spice)
SimCLR/NNCLR
SimSIAM BYOL
existing methods e.g. validating some empirically found tricks as necessary conditions for stable gradient dynamics (3-16), (ii) studying the role of each SSL component e.g. the projector and predictor networks 11711]. or (iii) developing novel SSL criteria that often combine multiple interpretable objectives that a SSL model must fulfill 25 While those branches have led to novel understandings and even stem novel SSL methods, some fundamental questions remain open.
More recently, few focused studies have started provide theoretical works e.g. Tian 27 on contrastive losses with deep linear networks, HaoChen et al. 28) (2 on SimCLR 8
30 on the
projector of contrastive models, [4] on BYOL [3I and SimSIAM 8 Those studies paved our way forward as we propose in this paper much broader analysis that applies to most (if not all) existing SSL methods allowing us for the first time to provide provable design guildelines to practitioners in their choice of architecture and methods. We do so by unifying most SSL methods as different flavors of spectral methods for embedding and clustering as summarized in Fig. [ The instrumental results we obtain allow us to answer some long- questions both when employing linear model and an infinite capacity one which we summarize as part of our contributions below:
1. Closed-form optimal representation for SSL losses. The Deep Network (DN)nepresentattonn Z of inputs X learned by minimizing any SSL loss given sample relation matrix G' is obtained in closed-form, shedding light to many spectral properties of those representations e.g. SSL only constrains the left singular vectors and singular values of Z to align with the ones of G (Sections 3.1 and 5.1 for VICReg, SimCLR and MarlowTwins))
2. Closed optimal network parameters for SSL losses with linear networks. The linear representation Z -XW- + parameters obtained by minimizing any SSL loss given a sample relation matrix G are obtained in closed-form, providing insights into the type of input statistics that a network parameters focuses on to produce the optimal input mapping (Sections 3.2 and 5.2 for VICReg and Barlow Twins).
3. Exact equivalence between SSL and spectral embedding methods. SSL methods employ diverse criterion that can be tied eponymous spectral analysis methods both in embedding space and in data space, and with a nonlinear or a linear DN e.g. Laplacian Eigenmaps
(VICReg, Section (.2),, ISOMAP (SimCLR/NNCLE Section 4.3) Canonical Correlation Analysis (Barlow Twins, Section 5.2) and when employing a linear network as Locality Preserving Projection (VICReg), Cannonical Correlation Analysis (BarlowTwins) and Linear Discriminant Analysis for both VICReg and Harlow/winss (summarized in Fig. M].
We also relegate Appendix [l study quantifying the relationship between the optimal representa- tion of each SSL method and the downstream classífication task performances e.g. when the correct data relation matrix is given (Appendix C.3) as those results, although not crucial to contributions, follow directly from the above ties between SSL and spectral embedding. We carefully prove each statement of this study in Appendix F
2 Notations and Background on Self-Supervised Learning
We provide this section a brief reminder of the main Self-Supervised Learning (SSL.) methods, their associated losses, and the common notations that we will rely on for the remaining of the study.

---

Dataset, Embedding and Relation Matrix Notations. Regardless of the loss and method employed, SSL relies on having access to a set of observations i.c. input samples X - [#1...., 'Nn" E I XD and known pairwise positive relation between those samples e-g. in the form of a symmetric matrix G' E (R+) N where (G), > 0 iff samples 2; and z; are known to be semantically related, and with the diagonal. Commonly, one is only given a dataset X' and artificially constructs X and G' from augmentations of X' e.g. rotated, noisy versions of the original samples and turning the corresponding entries of G to be positive for the samples that have been augmented form the same original sample. Lastly, Z E B- denotes the matrix of feature maps obtained from model fo : RDD + R commonly a Deep Network-
Z [fo(=)), ..... fo(œx)]
VICReg. With the above notations out of the way, we can remind the VICReg loss as defined in Bardes et al. [25] as function of X and G' in the following triplet loss
Cvic 0 Σ max 0,, (0.1- Cov (Z)ak) +.3 (CCCOr(
Y LEGNIZ i=1
Zz. 12 (1)
We will often refer to each term in Eq. ① as Lvar. Loov, and Linv respectively. SimCLR. The SimCLR loss (8] is slightly different and first produces an estimated relation matrix (Z) generally using the cosine similarity (CoSim) via
e CoSim(2z.a)1/
(G(Z))ss Lj=l CoStin(z,,21//
with 5 > 0 temperature parameter. Then SimCLR encourages the elements of G(Z) and G to match. The most popular solution to achieve that is to leverage the infoNCE loss given by
N N
CSmOLR = =- --ΣI (G), log (aagllogGG(()i G(Z))
1= A=1
The only difference between SimCLR and its varients e.g. NNCLR 32 lies in defining G.
BarlowTwins, Lastly, BarlowTwins (24) proposes yet slightly different approach where 2; must be close to z, if G.. >> 0. They do so with different flavors of losses and constraints to facilitate
training. Hence, and for those models only, it is common to explicitly group X into two subsets
Xlett and Yrghtt based on G so that ((Xiet) (Xright) vn are all the positive pairs from (X, G This does not lose any generality. In fact, suppose that we have samples a, e, d, e, and that G says that a, b, related to each other, and that d, are related to each other. Then, the two data matrices as
create
X = [a, a, b, b, c, e]. Xright = [b, a, c,a, b,
(4)
Once the two (left/right) views are obtained, the corresponding embeddings Ziek. Zright can be computed and the BarlowTwwie Twins is then defined as
CBT Σ (CoSim((Ziat) (Zrighs)..t 1)2 +a
Σ CoSim((Zoot)..... (Ziggh) (5)
1=1,k'<k
where one should notice that those terms correspond to the cross-correlation matrix between the two embeddings.
Our goal the following sections (Section g for VICReg, Section 4 for SimCLR/NNCLR, and Section (ooor BarlowTwing will be to find the optimal representations Z of X in various regimes. Three surprising facts will emerge: (i) all cxisting methods recover exactly some flavors of famous spectral methods, (ii) the spectral properties of Z can be provably characterized for each methods, and (iii) from those properties, we will provide necessary and sufficient conditions for a SSL representation to perfectly solve downstream task. We provide linear algebra notations in Appendix B that might be useful for readers unfamiliar with methods such as the Singular Value Decomposition (SVD) [3].
VICReg Minimizes the Dirichlet Energy to Produce Smooth Signals on the Graph G While Preventing Dimensional Collapse
Recall from Section 2 and Eq. (T) that VICReg is defined as a triplet loss (variance/ivvaiaane/cvvvi ance). We first demonstrate in Section 3.] that the optimal VICReg representation can be obtained in
3

---

closed form (Theorem ! and that turning the VICReg optimization as a constrained problem recovers Laplacian Eigenmaps embedding space and Kernel Locality Preserving Projection in data space (Section 3.2 We also consider the linear network regime where we obtain the analytical form of the optimal network's parameters (Theorem
3.1 Close-Form Optimal Representation for VICReg
First, we build up some insights into VICReg by demonstrating how the invariance term corresponds to the Dirichlet energy of the signal Z the graph G. Then, replacing the variance hinge loss at 1 K with the squared loss at 1 as in Ek=1 (1
Cov(Z) x.,) notice that minimizing the latter implies minimizing the former. With that, we are able to obtain the close-form optimal representation Z* minimizing Eq. I1 only as a function of G and the loss' hyperparameters.
From invariance to trace minimization. The first insight that we propose into VICReg is obtained by rewriting the invariance loss of VICReg as the energy of the signal Z the graph G [34 we have (derivations in Appendix F.5
since
N N
ΣΣ (Z),,l(Z),. Ai j=1
(.), 1 = 2Tr 2 LZ)
Dirichlet energy of Z on G),
(6)
where L is the graph Laplacian matrix == D G with D the diagonal degree matrix of G i.e. (D), E,(G) (G) and (D)s, = Vi + From Eq. (6) it is clear that the invariance term depends on the matching between the left singular vectors of Z and the eigenvectors of L. Hence, non-contrastive learning aims at producing non-degenerate signals Z that smooth on G.
Optimal representation. To gain further insights into VICReg, we ought to obtain the analytical form of the optimal representation Z minimizing Eq. ①I aathouugh this optimum is not unique e.g. adding a constant entry to each column of Z does not change the loss value (details in Appendix E6). We can now obtain the following characterization of Z as function of the spectral decomposition of the matrix that combines two Laplacian matrices (details in Appendix [.7).. The first, (left of
Eq. comes form the variance++ovvaiiance term is the Laplacian of a complete graph i.c. where
each node/sample is connected all others. The second comes from the SSL graph G to form the following (with its eigen-decompositton)
I- 11"1 7 G) Pa, diag diag()o,
Laplacian of complete graph
Laplacian of SSL/sup. graph
where the eigenvalues/eigeevectoo are descending orders. The eigenvectors of the combined
Laplacians will be key to produce the optimal VICReg representation as formalized below.
Theorem 1. global minimizer of the VICReg loss (a = B, V-y denoted by Zä. is obtained from Eq. 7 along with the minimal achievable loss which are given by
Ta (N) / ):,1:K and ZERN xK
min
Lvic = vvcc=a(K- 11(Aa, 11.kk1
and any K K-out-ofNN columns of Pa, N)1/2 a local minimumn. (Proof in Appendix F.7
The above result provides a few key insights. First, only the ratio 7/a governs the VICReg represen- tation. Second, there exists many local minimum, some of which can be explicitly found by taking various K-out-of-N columns of landscape of Lvic around the optimal representation Z We also depict in Fig. 3 the evolution of the eigenvalues (Aar)1: for varying y along with the downstream task (induced by G) training performance. We observe that ViCReg benefits from sweet-spot where can both preserve a full-rank representation z" and incorporate enough information about G' to solve the task at hand perfectly.
1/2 which we display in Fig. 2 along with the loss
Before moving to other SSL methods, we first emphasize the ability of VICReg to recover local spectral methods in the following sections.
3.2 VICReg Recovers Local Spectral Embedding Methods
The goal of this section is to relate VICReg to known local spectral embedding methods both in feature space (Z) and in data space (X).

---

a=1y=
a=l,y=0 o=1,y=0.1 am1,y00
oel1,y=0.
40130
391255
39.2.0
11.5
Evic
21.0
Fank GG)
20.5
111 convex interp. between top Je: + k) cigenvectors of Eq.
111.77711.19...00..22.. 2277)
Figure 2: Left: depiction of the optimal VICReg loss with varying syper-parameters (blue line) when the representation is formed from the top [k: K + in-between. Recall from Theorem D that global optimum given by the [1 A 1] case. We also depict the downstream task performance (orange line) and we clearly observe that both are closely related as expected (see Theorem 9). Notice that since we are considering classification, even without the correct first eigenvector the linear classifier top of Z.,, is able solve the task at hand thanks to the probability constraint that 1 i.e. the last component landscape of LviC around
cigenvectors of Eq. with convex interpolation
be recovered from the first C optimal Za,y on the left using directions provides by the top [2 K] and [3 K + 1] eigenvectors of Eq. 7 and then with random directions in Z -space. All experiments employed N 256, K 16, rank( (G)
Right: depiction of the loss
25
100
Figure 3: Top: minimal VI- CReg loss (blue) from Theorem I and corresponding downstream task performance (orange). Bot- tom: evolution of Za.y's sin- gular values. VICReg benefits from a (a, (a,,y)--one, for which Za, remains full rank and incorpo- rates enough information solve the downstream task. Hence, VICReg hyper-parameter 7/a should be adapted depending the confidence one has into G. All experiments employed N = 256, K = 32, rank(G) =
Evin Arain
-80
66
5-
8.00
0.02
0.04
0.06
0.08
0.10
to
0.00
0.02
0.04
0.06
0.08
0.10
invariance confficient (a fixed
In feature space. Laplacian Eigenmaps (LE) (35 is non-parametric method searching for representation Z by minimizing the following Brockett [36] optimization problem
min 8:2 DZ=I
Tr (Z G))
(8)
with the diagonal degree matrix of G (recall Eq. 7
Theorem 2. Given a datuset X and relation matrix G solving the LE optimization problem Eq. produces representation that minimizes the VICReg loss with constraint that the variance and covari- ance loss are O as Livie Z=ii)=minz Linv (Z) s.l. =v and Loo==0. (Proof Appendix F8
One important observation is that 8 recovers yet another SSL method known as W-MSE 37 which can now be seen as the constrained counterpart of VICReg, and the linear regime, recovers Slow Feature Analysis (SFA) although without the dimension ordering, and is thus also closely related to its extension presented
Pfau et al. [38] Furthermore, Eq. (8) and variants have been studied in Agrawal et al. 33 in the context of kernel PCA, some of which could provide interesting variations of the constrained VICReg setting. We also ought to highlight however that a crucial part of LE lies in the design of that matrix G, often found from k-NN graph 40) of the samples X in the input space, while SSL it constructed from aata-auumentttiins, or given.
In data space with DNs. The difficulty to produce new representations for new data samples (a shared difficulty among non nonpparametrie methods) led to the development of a two-step modeling process 41 (E It P) h ②(x) (E R WT, h (E RK) with S > K, W R MR

---

and where ó's goal is to learn a generic input embedding that can be reused on new samples z. To see this, we collect those mappings for all the training set into the matrix 4 E RNNx With that, the LE problem in data space known as the kernel Locality Preserving Projection (kLPP) 42 problem- becomes
min oF DOW=I
Tr (WT
so that the original LE representation Z can be obtained simply as Z = &W. And more importantly, given a new sample æ, one directly computes z = . cl ar). The crucial result of interest for our study the following one that simply combines Theorem 2 with result from He and Niyogi [42 demonstrating the equivalence between LE in feature space and KLLE in data space.
Proposition 1. VICReg with variancefcovariancee constraint solves LE in embedding space and KLLE in input space (recall Eq. (9) employing DN for ø.
In data space with linear models. We now consider a linear mapping Z = XW (the offset is taken care of by adding 1 column to X). In that case, VICReg with constrained L 0, Leov 0 (as in Theorem recovers two known spectral methods: Locality Preserving Projections (LPP) [42 for arbitrary relation matrix G, and Linear Discriminant Analysis (LDA) 43 44 when G is the supervised relation matrix. In both cases we obtain the analytical form of the optimal weights W, as long the within class/cluster variance positive.
Theorem 3. Linear VICReg recovers LPP for any G and K S N, and recovers LDA for supervised G and K- C, in both cases the optimal parameter W is given by the top-K eigenvectors of (X" - -X GX. G... (Proofs in Appendices F.13 and F.14
Interestingly, the eigenvalues associated to the eigenvectors of W exactly recover the multivariate analysis of variance (MANOVA) sufficient statisties of the data 45 46]. Hence, although not further explored in this study, we believe that important statistical results could be further obtained e.g. to
assess the goodness-of of-ffit fit of the model without requiring downstream task 47 49 another important SSL loss which is SimCLR and its variants.
We now turn to
SimCLR Solves a Generalized Multidimennional Scaling Problem à la ISOMAP
Recall from Section 2 and Eq. 2 that SimCLR first computes a similarity matrix G of some flavor
that depends the representation Z, and then matches it against the known data relation G. Different
Z G methods lead to different variants of SimCLR The goal of this section is two-fold. First, we demonstrate in Section 4.1 that different
g such as NNCLR 32
or MeanShift [50]. G
mappings are solutions of different optimization problems (Theorem similarity matrix G from the signals Z akin to Laplacian estimation in Graph Signal Processing.
all trying to estimate the
Second, we demonstrate in Section 4.2 that SimCLR and its variants force Z's spectrum to align
with the one of G as the training task falls back to a generalized (kernel) Multi-Dimensional Scaling method (Proposition 2)
4.1 Step 1: SimCLR Pairwise Similarities Solve Graph Laplacian Estimation Problem
Let's first define the minimization problem that given a set of signals i.e. rows of Z produces relation
estimate G of G. To ease notations, we gather in the N x N matrix D all the pairwise distances (D),,, = ddff (x:), fo (xx)) with d any preferred metric. The standard problem of estimating G from Z can be cast an optimization problem [51 52 as
GA.R = arg min
Σ i.j
fo fol; + R(G) = arg min Tr(DG) + R(G),
(10)
Geg
Geg
with G the set (or subset) of symmetric matrices with nonnegative entries and zero diagonal, and with R regularizer preventing G to be the trivial zero matrix e.g.
Riog (G) Σ (logglo - or R (G) = E Giy 1).
(11)
i
itj

---

cosine+ Riox SIRNCL/NNCLR)
cosinc+Rpp
f2 + Rp
Eg + Riog
Figure Depiction of rep- resentation's ' singular values during training (from blue to red with the SimCLR loss with Giato varying rank(G) E (8, 16, 32) (rows, green dotted lines), number in top-right cor- ner) with various (d. R) configura- tions (columns, recall Theorem + The rank of the learned representation matches exactly the one G validat- ing the result from Theorem S regard- less of the chosen hyper-parameters.
10
(z)),, in log-scale
10a
10"
0111-11
18:12113
08112-31
28.1-00
10:2-
10a
1660000
PAEA 2067
10'2
10
40
66
k
k
k
We provide in Fig. depiction of the impact of R(G) which pushes the entries of the weight matrix to be close to 1 with strength depending the temperature parameter Hence G from Eq. 10) is the optimal graph expresseed as a weight matrix- for which the signal Z = fo () on that graph solve Eq. (TO) only Gisto the space of right-stochastic matrices
is smooth. For example
ie. a subset of G that only contains matrices whose rows sum to i.e. Giato = {G E G1 = 1}.
Theorem 4. Using R. from Eq. 11 leads the following graph weight estimate
(Ga, Di.j d(fo(((aa))))) ( 1
(with G)
e (=
(Ga,Rion dij
Ejtte Jole)) 412h
(with Grsto)
(12)
and thus if d the cosine distance, Eq. recovers SimCLR's case. (Proof in Appendix
F9
Based on this result, deriving novel, principled and interpretable variations of SimCLR is streamlined as we demonstrate in Appendix E by solving Eq. (IO) with different constraints. Now that we understood the first part of the SimCLR method, we move to the second part, matching that graph estimate the given one.
4.2 Step 2: SimCLR Fits the Estimated Graph to the Known Graph G
After SimCLR estimates the graph with G as per the previous section, it employs a loss to enforce G be as close as possible to G with some desired metric. That metric should reflect the properties that G fulfills c.g. being a doubly-stochasee
night-stochastic or else. We demonstrate in this section that doing so, SimCLR forces Z to have the same nonzero left singular vectors as the nonzero eigenvectors of G, and that as opposed to VICReg, the rank of Z and G' always matches.
Let's first denote the SimCLR contrastive loss to be of the two following variants (depending on the type of constraints put on & and G
N
LSimCLR = IIG G1 or
1
Σ
Σ (G) log(( (og((G))on ).
(13)
N
==1===
When minimizing Eq. 13,, SimCLR will learn embedding Z that the graph estimate matches closely the known graph G. This already brings a contrast from VICReg showing that instead, SimCLR learns to produce signals such that the graph estimate is close the known graph. We now characterize the optimal SimCLR representation Z;, recalling that we denote by Uc and Σg the left singular vectors and singular values of G respectively. Notice that since G is symmetric semi-definite positive, U also corresponds to its eigenvectors and Σg to its eigenvalues.
Theorem 5. global minimizer of the SimCLR loss denoted by Z" along with the minimal achievable
loss using Eq. 16) or Eq. 17 T maxi, (D)iss and with the LHS of Eq. [3 are given by
N
:z = (UG21 1/2 J.1:K and
min LSiOCLR ZERNXA N
Σ
k=
7

---

up to permutations of the singular vectors associated to the same singular value. Also, for any loss of
Eq. (13) and graph estimation, the rank of Z min(K, rank(G)). (Proof in Appendix F.10
We illustrate the above theorem for many combinations of distances and regularizers in Fig. 4 where we see that in all cases, SimCLR forces the representations Z to have a dimensional collapse, a phenomenon first observed in Hua et al. 17] and that has been one of the unanswered phenomenon in SSL 20 30
In our goal to unify SSL methods under the helm of spectral embedding methods, we propose the following section that ties SimCLR and its variants to global spectral methods.
4.3 SimCLR Recovers Global Spectral Embedding Methods
We now propose tie the SimCLR method along with its variants e.g. NNCLR to known global spectral methods, c.g. ISOMAP 53 which is in contrast to VICReg which was tied to local spectral
methods (recall Section 3.2
In feature space. Let's first recall that ISOMAP is a variation of multi-Diiensional Scaling (MDS) [54] also known Principal Coordinates Analysis. Classical MDS tries to learn embedding vectors that have similar pairwise distance (usually (2) than the pairwise distance of the given input data. Often, MDS does this by using similarities instead of distances and thus by solving the following optimization problem minz |G - 1/. At the most general level, ISOMAP simply corresponds to solving that same optimization problem but after redefining G' to better capture the geometric information of X e.g. using the shortest path distance of the k-NN graph of X [55). The surprising result that we formalize below is that SimCLR and its variants recover ISOMAP.
Proposition 2. SimCLR, using the settings of Theorem 5 choice of G). (Proof in Appendix F.IIT)
recovers ISOMAP (and MDS for the correct
In data space with DNs. From the above, we can extend Proposition 2 but in input space, in very similar way as was done in Section 3.2] In fact, originating in Webb [56], there was search to extend MDS, and ISOMAP to an input space formulation to solve the out-of- problem. this setting, and taking MDS as an example, the original similarity matrix Z Zz is replaced with & W " using the same notations as in Eq. (9) and already known relationship between those models, we obtain the following.
Proposition 3 ((57)) Whenever SimCLR recovers ISOMAP or MDS in feature space, it recovers kernel ISOMAP or kernel PCA (58) in input space.
We now ought to turn BarlowTwins another non-contrastive method akin to VICReg (both of which fall back to LDA in the linear regime and with supervised G)..
5 BarlowTwins Solves a (Kernel) Canonical Correlation Analysis Problem and Can Recover VICReg
Our last step in our journey to unify SSL methods under spectral embedding methods deals with BarlowTwins Akin to the development for VICReg and SimCLR, Barlow Twins will also fall back to a known spectral method in embedding space (Section [.T] and in data space (Section (5.2] where in the later case we again obtain the close-form optimal network parameters in the linear regime.
5.1 BwrlowTwins Recovers Kernel Canonical Correlation Analysis
Recall from Section 2 and Eq. (5) that the BarlowTwins loss is based on a cross-correlation matrix between positive pairs of samples. As we did for VICReg and SimCLR, our goal here is to tie BarlowTwins to known spectral method known as Kernel Canonical Correlation Analysis.
Although we focus here on BarlowTwins for clarity. We hope that our results on Barlow Twins will stem the unification of those methods too in future works. Going back to BarlowTwins, we now obtain the following result that nicely parallels with the ones we obtained for VICReg and SimCLR. In data space, BarlowTwing can be regarded (put in perspective with Section (.2) as a nonlinear
canonical correlation analysis (NLCA) [59] and in particular Kernel CCA (KCCA) [60 61 akin to
8

---

how VICReg recovered Kernl Locality Preserving Projection and SimCLR Kernel ISOMAP. We leverage the same notations as in Section 3.2
Theorem 6. BarlowTwins recovers Kernel Canonical Correlation Analysis with a DN the featurizer é and produce a representation with rank min(K, D) for any value of a (recall Eq. 5 and with
orthogonal columns. (Proof in Appendix F.12).
We thus obtain from the above that Barlow employing a DN featurized is akin to the Deep CCA [62] that proposed this setting exactly, and further akin to SimSIAM and BYOL, [31] since Lee et al. [26] related the latter to Deep CCA. In addition to those links, the above provides further interpretation into the MarlowTwing loss c.g. the additional e constant added in the denominator of
the BainowTwins loss further corresponds to ridge-type regularization which been introduced in Gretton et al. 633 as a mean to introduce numerical stability.
The above statement also brings yet another flavor of SSL methods. In fact, where VICReg allows to control the rank of Z to be in- between K and rank G) throug the loss apprr-paramters,, and where SimCLR enforces the rank of Z to be exactly the rank of G. BarlowTwin enforces to have a full-rank representation. We depict in Fig. 8 the evolution of rank Z) depending on the rank of the initialized representation rank iiitt) using a gradient descent optimizer. We see that if the initialization is full rank but G is lower rank, the Barlow Twins loss does not collapse the extra nonzero singular values of Z. Vice-versa, if rank Zinis) rank(G) then Barlow loss will increase the rank of Z. lastly, although not further studied here, we should point out to the reader that regularized forms of KCCA can be shown to include kernel ridge regression and regularized kernel Fisher LDA as special cases [64], further tying the special cases for which different SSL methods would fall back to the same model.
In the following section we will demonstrate how BarlowTwins in the linear regime exactly recovers Canonical Correlation Analysis.
5.2 With a Linear Network Barlow Recovers Canonical Correlation Analysis and Linear Discriminant Analysis
The goal of this section is to further demonstrate the benefits of connecting SSL methods to spectral methods by exploiting the known techniques of the latter to help answer questions on the former.
As was done VICReg (we use linear settings of Section 3 p, we now obtain the optimal weights for BarlowTwiii in the linear regime. We can even provide additional insights in this case since Barlow Twins is often seen as key method that allows the use of different parameters/archiitccurr to process Xieft and righht- We now show under what conditions on G' sharing parameters is sufficient by first demonstrating how BarlowTwin, recovers exactly CCA, and even LDA for supervised G. To streamline notations, we assume that our data is already centered, and thus define the covariance and cross-covariance matrices as Cu X Xright: Ci X right. and so on.
Theorem 7. In the linear regime BarlowTwins recovers CCA with optimal weights given by
Wie top-K eigenvectors of Gi Cir Ca and W right Ca Wiet:
and (i) with symmetric G, weight-sharing naturally occurs- as the optimal weights are lent W right lop-K eigenvectors of C, On and (ii) G is supervised and K C then Barlow Twins recovers LDA and thus constrained VICReg (recall Theorem 3). (Proof in Appendix F.15)) F.155
The above result opens new venues to extend current SSL methods (Barlow Twins in this case). For example, penalized matrix decomposition (PMD) from Witten et al. [65] formulates novel sparse formulation of CCA. In our context, this could lead to a new variation of Barlow the linear and nonlinear regimes. With the above results, we now connected most SSL methods to spectral methods, and found key properties that their representatioos/paaameeee inherit. We provide for completeness few direct results in Appendix that directly leverage the above results to characterize downstream performances of each method.
in both
6 Conclusions and Limitations
We provided a unifying analysis of the major self-supervised learning methods covering VICReg (Section 3) SimCLR (Section 4 and BarlowTwin (Section 5) along with SimSIAM and BYOL

---

thanks to already existing results tying those to Deep CCA. In doing so, we were able to find the commonalities between all those methods and to provide general guidelines on how to derive alternative SSI. methods from first principles. At a more general level, we were able to parallel the many SSI. methods to global and local methods in spectral methods respectively. Among the many insights that we obtained, the most crucial one is that VICReg enables continue control on collapsing the representation's 's rank versus encapsulating information about G. This is in contrast to BarlowTwins and SimCLR that either always maintain full-rank, always collapse the representation none of which would be ideal. One major limitation is that for the nonlinear regime, we study the case of an infinite capacity model i.. implicit bias coming from the architecture comes into play. potentially insightful future work would thus be to perform a similar analysis as the one provided here but including the implicit bias on the nonlinear mapping that different architecture exhibit. This way, we would obtain not only insights into the various SSL methods but also in their combination with various model architectures.
References
[1] Angjoo Kanazawa, David W Jacobs, and Manmohan Chandraker. Warpnet: Weakly supervised matching for single-view reconstruction. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 3253-3261, 2016.
[2] David Novotny, Samuel Albanie, Diane Larlus, and Andrea Vedaldi. Self-supervised learning of geometrically stable features through probabilistic introspection. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3637-3645, 2018.
[3] Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint arXiv: 1803.07728, 2018.
[4] Pierre Sermanet, Corey Lynch. Yevgen Chebotar, Jasmine Hsu, Eric Jang, Stefan Schaal, Sergey Levine, and Google Brain. Time-contrastive networks: Self-supervised learning from video. In 2018 IEEE international conference on robotics and automation (ICRA), pages 1134-1141. IEEE, 2018
[5] Dahun Kim, Donghyeon Cho, and In So Kweon. Self-supervised video representation learning with space-time cubic puzzles. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 8555-8552, 2019.
[6] Dejing Xu, Jun Xiao, Zhou Zhao, Jian Shao, Di Xie, and Yueting Zhuang. Self-supervised spatiotemporal learning via video clip order prediction. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10334-10343, 2019.
[7] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using a" siamese" time delay neural network. Advances in neural information processing systems, 6, 1993.
[8] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597-1607. PMLR, 2020.
[9] Ishan Misra and Laurens van der Maaten. Self-supervised learning of pretext-invariant rep- resentations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6707-6717, 2020.
[10] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in sulf-supervised vision transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9650-9660, 2021.
[11] Priya Goyal, Dhruv Mahajan, Abhinav Gupta, and Ishan Misra. Scaling and benchmarking self-supervised visual representation learning. In Proceedings of the ieee/cvf International Conference computer vision, pages 6391 6391-6400, 2019.
[12] Linus Ericsson, Henry Gouk, and Timothy M Hospedales. How well do self-supervised models transfer? In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pages 5414-5423, 2021.
10

---

[13] Xiang Wang, Xinlei Chen, Simon S Du, and Yuandong Tian. Towards demystifying repre- sentation learning with non-contrastive self-supervision. arXiv preprint arXiv:2110.04947 2021.
[14] Yuandong Tian, Xinlei Chen, and Surya Ganguli. Understanding self-superviste learning dynamics without contrastive pairs. In International Conference on Machine Learning, pages 10268-10278. PMLR, 2021.
[15] Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. In International Conference on Machine Learning, pages 11112-11122. PMLR, 2021.
[16] Ashwini Pokle, Jinjin Tian, Yuchen Li, and Andrej Risteski, Contrasting the landscape of contrastive and non-contrastive learning. arXiv preprint arXiv:2203. 2502:::2003.5702,, 2022.
[17] Tianyu Hua, Wenxiao Wang, Zihui Xue, Sucheng Ren, Yue Wang, and Hang Zhao. On feature decorrelation in self-supervised learning. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 9598-9608, 2021.
[18] Li Jing, Pascal Vincent, Yann LeCun, and Yuandong Tian. Understanding dimensional collapse in contrastive self-supervised learning. arXiv preprint arXiv:2110.09344 2021.
[19] Florian Bordes, Randall Balestriero, and Pascal Vincent. High fidelity visualization of what your self-supervised representation knows about. arXiv preprint arXiv:2112.09164, 2021.
[20] Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv:1902.09222. 2019.
[21] Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. Generalized clustering by learning to optimize expected normalized cuts. arXiv preprint 111:02111..07623, 2019.
[22] Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. International Conference on Machine Learning. pages 9929 9939..99999.3 PMLR, 2020.
[23] Haizhou Shi, Dongliang Luo, Siliang Tang, Jian Wang, and Yucting Zhuang. Run away from your teacher: Understanding byol by a novel self-supervised approach. arXiv preprint arXiv:20/1 1. 10944, 2020.
[24] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self- supervised learning via redundancy reduction. arXiv preprint arXiv:2103..33230, 2021.
[25] Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: Variaace-iyarrane--vvaaane regular-
ization for self-supervised learning. arXiv preprint
2021.
[26] Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. Advances in Neural Information Processing Systems, 34:309-323, 2021.
[27] Yuandong Tian. Deep contrastive learning is provably (almost) principal component analysis. arXiv preprint 220. 2022.
[28] Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34, 2021.
[29] Jeff Z HaoChen, Colin Wei, Ananya Kumar, and Tengyu Ma. Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations. arXiv preprint vrXiv:2204.02683 2022.
[30] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. In Algorithmic Learning Theory, pages 1179-1206. PMIR, 2021.
11

---

[31] Jean-Bate Bean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch. Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to self- seff-super learning. Advances in Neural Information Processing Systems, 15:21221-212888 2020.
[32] Debidatta Dwibedi, Yusuf Aytar, Jonathan Tompson, Pierre Sermanet, and Andrew Zisserman. With a little help from my friends: Nearest-neighbor contrastive learning of visual representa- tions. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9588 9597, 2021.
[33] Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211-218, 1936.
[34] Ulrike Von Luxburg, A tutorial on spectral clustering, Statistics and computing, 17(4):395 416, 2007.
[35] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373-139) 2003.
[36] Roger W Brockett. Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems. Linear Algebra and its applications, 146:79-91, 1991.
[37] Alcksandr Ermolov, Aliaksandr Siarohin, Enver Sangineto. and Nicu Sebe. Whitening for self-supervised representation learning. In International Conference on Machine Learning. pages 3015-3024. PMLR, 2021.
[38] David Pfau, Stig Petersen, Ashish Agarwal, David G. T. Barrett, and Kimberly L. Stachenfeld. Spectral inference networks: Unifying deep and spectral learning. In International Confer- ence Learning Representations, 2019. URL BtRL:ttp:://// /oopooppeevieeeeeeeeeeeeeeeeeeee . net forum? d==
httpp:://openreiiee
SJYY
[39] Akshay Agrawal, Alnur Ali, Stephen Boyd, et al. Minimum-distortion embedding. Foundations and Trends@ in Machine Learning, 14(3):211-378 2021.
[40] Ville Hautamaki, Ismo Karkkainen, and Pasi Franti. Outlier detection using k-nearest neighbour graph. In Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004., volume 3, pages 433, IEEE, 2004.
[41] Yoshua Bengio, Jean-françcois Paiement, Pascal Vincent, Olivier Delalleau, Nicolas Roux, and Marie Ouimet. Out-of-sample extensions for Ile, isomap, mds, eigenmaps, and spectral clustering. Advances in neural information processing systems, 16, 2003.
[42] Xiaofei He and Partha Niyogi. Locality preserving projections. Advances in neural information processing systems, 16, 2003.
[43] Ronald A Fisher. The of multiple measurements in taxonomic problems. Annals of eugenics, 179-11998888 1936.
[44] Patricia Cohen, Stephen G West, and Leona S Aiken. Applied multiple regression//oorreattion analysis for the behavioral sciences. Psychology press, 2014.
[45] Ralph G O'Brien and Mary K Kaiser. Manova method for analyzing repeated measures designs: an extensive primer. Psychological bulletin, 97(2):316, 1985.
[46] Carl J Huberty and Stephen Olejnik. Applied MANOVA and discriminant analysis. John Wiley & Sons, 2006.
[47] Sebastian Mika, Gunnar Ratsch, Jason Weston, Bernhard Scholkopf. and Klaus-Robert Mullers. Fisher discriminant analysis with kernels. In Neural networks for signal processing IX: Proceed- ings of the 1999 IEEE signal processing society workshop (cat. no. 98th8468), pages 41-48. Icee, 1999.
[48] Sergey loffe. Probabilistic linear discriminant analysis. In European Conference on Computer Vision, pages 531-542. Springer, 2006.
12

---

[49] Jing-Hao Xue and Peter Hall. Why does rebalancing class-unbalanced data improve auc for linear discriminant analysis? IEEE transactions on pattern analysis and machine intelligence. (7(5):100-1111 2014.
[50] Soroush Abbasi Koohpayegani, Ajinkya Tejankar, and Hamed Pirsiavash. Mean shift for self- supervised learning. In Pruceedings of the IEEE/CVF International Conference on Computer Vision, pages 10326-10335, 2021.
[51] Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst. Learning laplacian matrix in smooth graph signal representations. IEEE Transactions on Signal Processing, 64 (23):6160-611) 2016.
[52] Vassilis Kalofolias. How learn graph from smooth signals. In Artificial Intelligence and Statistics, pages 920-929. PMLR, 2016.
[53] Joshua B Tenenbaum, Vin de Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319 22233, 2000.
[54] Joseph Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychomelrika, 29(1):1-27, 1964.
[55] Franco P Preparata and Michael Shamos. Computational geometry: an introduction. Springer Science & Business Media, 2012.
[56] Andrew R Webb. Multidimensional scaling by iterative majorization using radial basis functions. Pattern Recognition, 28(5):753-755 1995.
[57] Christopher Williams. On connection between kernel pea and metric multidimensional scaling. Advances in neural information processing systems, 13, 2000.
[58] Bernhard Schölkopf, Alexander Smola, and Klaus Robert Müller, Nonlinear component analysis as a kernel eigenvalue problem. Neural computation, 10(5):1299-1399 1998.
[59] Jacques Dauxois and Guy Martial Nkiet. Nonlinear canonical analysis and independence tests. The Annuls of Statistics, 26(4): 1254-127.. 1998.
[60] Pei Ling Lai and Colin Fyfe. Kernel and nonlinear canonical correlation analysis. International Journal of Neural Systems, 10(05)3365-23 -70,,,3777200 2000.
[61] Kenji Fukumizu, Francis R Bach, and Arthur Gretton. Statistical consistency of kernel canonical correlation analysis. Journal of Machine Learning Research, 8(2), 2007.
[62] Galen Andrew, Raman Arora, Jeff Bilmes, and Karen Liveseu. Deep canonical correlation analysis. In International conference on machine learning, pages 1247-1255. PMLR, 2013.
[63] Arthur Gretton, Ralf Herbrich, Alexander Smola, Olivier Bousquet, Bernhard Schölkopf, et al. Kernel methods for measuring independence. 2005.
[64] Malte Kuss and Thore Graepel. The geometry of kernel canonical correlation analysis. 2003.
[65] Daniela M Witten, Robert Tibshirani, and Trevor Hastie. A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Biostatistics. 10(3):515-53, 2009.
[66] Laurenz Wiskott and Terrence J Sejnowski. Slow feature analysis: Unsupervised learning of invariances. Neural computation, 14(4):715-770, 2002.
[67] Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust pea via outlier pursuit. Advances in neural information processing systems, 23, 2010.
[68] Magnus R Hestenes. Inversion of matrices by biorthogonalization and related results. Journal of the Sociery for Industrial and Applied Mathematics, 6(1):51-90. 1958.
[69] Han Bao, Yoshihiro Nagano, and Kento Nozawa. Sharp learning bounds for contrastive unsupervised representation learning, arXiv preprint 10X00221 2021.
13

---

[70] Gene H Golub and Christian Reinsch. Singular value decomposition and least squares solutions. In Linear algebra. pages 134-151. Springer, 1971.
[71] Like Hui and Mikhail Belkin. Evaluation of neural architecturee trained with square loss vs cross- entropy in classification tasks, 2020. URL
07322
[72] Robert Geirhos, Kantharaju Narayanappa, Benjamin Mitzkus, Matthias Bethge, Felix A Wich- mann, and Wieland Brendel. On the surprising similarities between supervised and self- supervised models. arXiv preprint a0X1v:2010.08377. 2020.
[73] Nicholas J Higham. Computing nearest symmetric positive semidefinite matrix. Linear algebra and its applications, 103:103-118, 1988.
[74] Octavian Ganea, Sylvain Gelly, Gary Bécigneul, and Aliaksei Severyn. Breaking the softmax bottleneck via learnable monotonic pointwise non-linearities. In International Conference Machine Learning, pages 2073-2082. PMLR, 2019.
[75] Zhilin Yang, Zihang Dai, Ruslan Salakhutdinov, and William W Cohen. Breaking the softmax bottleneck: A high-rank rnn language model. arXiv preprint arXiv:171..0395: 2017.
[76] H Knaf. Kernel fisher discriminant functions-a concise and rigorous introduction. 2007.
[77] Andrew Wathen and Shengxin Zhu. On spectral distribution of kernel matrices related to radial basis functions. Numerical Algorithms. 70(4):709-726, 2015.
[78] Xin Liang, Ren-Cang Li, and Zhaojun Bai. Trace minimization principles for positive semi- definite pencils. Linear Algebra and its Applications, 438(7):3085-3100) 2013.
[79] Effrosini Kokiopoulou, Jie Chen, and Yousef Saad. Trace optimization and eigenproblems in dimension reduction methods. Numerical Linear Algebra with Applications, 18(3):565 602, 2011.
[80] Andrew Webb. Statistical pattern recognition. John Wiley & Sons, 2003.
[81] Yue-Fei Guo, Shi-Jin Li, Jing- Yu Yang, Ting-Ting Shu, and Li-De Wu, A generalized foley- sammon transform based on generalized fisher discriminant criterion and its application to face recognition. Puttern Recognition Letters, 147--3) 2003.
[82] Huan Wang, Shuicheng Yan, Dong Xu, Xiaoou Tang, and Thomas Huang. Trace ratio vs. ratio trace for dimensionality reduction. In 2007 IEEE Conference Computer Vision and Pattern Recognition, pages 1-8. IEEE, 2007.
[83] Cheng Li and Bingyu Wang. Fisher linear discriminant analysis. CCIS Northeastern University, 2014.
[84] Maurice S Bartlett. Further aspects of the theory of multiple regression. In Mathematical Proceedings of the Cambridge Philosophical Sociery, volume 34, pages 33-40. Cambridge University Press, 1938.
[85] Trevor Hastie, Andreas Buja, and Robert Tibshirani. Penalized discriminant analysis. The Annals of Statisties, 23(1):33-00, 1995.
[86] MJR Healy. A rotation method for computing canonical correlations. Mathematics of Compula- tion. 11(58))83-86 1957.
[87] Magnus Ewerbring and Franklin T Luk. Canonical correlations and generalized svd: applica- tions and new algorithms. Journal of computational and applied mathematics, 27(1-2):37-52 1989.
[88] David R Hardoon, Sandor Szedmak, and John Shawe-Taylor. Canonical correlation analysis: An overview with application to learning methods. Neural computation, 16(12):2639-266 2004.
[89] Olcay Kursun, Ethem Alpaydin, and Oleg Favorov. Canonical correlation analysis using within-class coupling. Pattern Recognition Letters, 32(2):134-144, 2011. 2011.
14

---

[90] Viivi Uurtio, João M Monteiro, Jaz Kandola. John Taylor, Delmiro Fernandez-Reyer and Juho Rousu. A tutorial on canonical correlation methods. ACM Computing Surveys (CSUR), 50(6): 1066)1133,, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Each section of the study answers specific aspect of the abstract
(b) Did you describe the limitations of your work? [Yes] We discussed the assumptions of each result.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We do not believe that our work has any potential negative societal impacts
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] For each method we carefully state our assumptions and provide background and citations for known results/assumpptions
(b) Did you include complete proofs of all theoretical results? [Yes] All the proofs carefully expressed in multiple appendices with additional details to ensure full transparency on our results.
3. If you ran experiments...
(a) Did you include the code. data, and instructions needed reproduce the main ex- perimental results (either the supplemental material or as URL)? [Yes] Code to reproduce the figures is provided in the supplementary materials
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] For each figure we provided the exact hyper- paremeeersseterss used in each case within the caption
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No] We only provide empirical validation that do not require errors bars
(d) Did you include the total amount of compute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [No] We only provide empirical validation toy settings that do not require GPU cluster computations
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A] we did not use existing assets
(b) Did you mention the license of the assets? [Yes] No licence provided
(c) Did you include any new assets either in the supplemental material as URL? [Yes] include the supplementary material the code to reproduce the figures provides in this paper.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "mBnB4yV901C", "reviewer": "Reviewer_jF2D", "summary": "This paper proposed a unfied framework for self-supervised learning with the help of spectral manifold learning .the authors show that VICReg, SimCLR, BarlowTwins are specical cases of their proposed framwork. They points out the prerequisite about the production of optimal self-supervised representations for downstream tasks.", "questions": "1. how the loss of DINO can be reformulated into the way of Eq. (5)?\n1. can the sprectral manifold learning be applied on DINO so as to unify it into your proposed framework?\nif the authors can address my concerns, I will raise my rate.", "limitations": "No", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. this paper is well written and easy to follow\n2. the idea of specral manifold learning for unifying SimCLR(NNCLR), BarlowTwins and VICReg seems to interesting for me\n3. this paper is technically sound\n\nWeakness\n1. I think the authors overclaim their contributions of this paper. From my view, they have only consider VICReg, BarlowTwins and SimCLR in this paper. Although They have mentioned DINO in this paper, they do not reveal the connection between DINO and others.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "TCsc3767vFU", "reviewer": "Reviewer_W5rv", "summary": "This paper provides a theoretical study of the popular self-supervised learning (SSL) techniques VICReg, SimCLR and BarlowTwins. The main results are closed-form optimal representations for each method as a function of the training data and the sample-relation matrix (which indicates which samples are from the same class, e.g. this could be constructed as the matrix that indicates which samples are augmentations of the same image). The paper further provides simplified versions of these expressions in linear settings and uses them to show equivalence between the SSL methods and various spectral methods, and provides a study on downstream task performances.", "questions": "If the authors can provide additional explanation of Figures 2, 3, and 4 that would be helpful.", "limitations": "The limitations of the theory are not discussed, and an assumption is missing (see above). There are no potential negative societal impacts.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The paper studies the important problem of theoretically understanding increasingly popular SSL methods.\n\n2. To my knowledge, no other work has derived such expressions concerning SSL optimal solutions, or made the connections between SSL and spectral embedding methods.\n\n3. The scope of the paper is comprehensive: all of the most popular SSL techniques are analyzed. Clearly a lot of work went into writing this paper.\n\nWeaknesses\n\n1. It is difficult for me to understand the insights of this work because the writing is so dense. Often expressions are introduced without sufficient background and conclusions drawn without sufficient explanation and/or motivation. E.g. $\\mathcal{L}\\_{var}$ and $\\mathcal{L}\\_{cov}$ in Theorem 2 and equations (13) and (14) - intuitively how do these equations arise and why are they useful? The figures are especially information-overloaded and difficult to parse. The claims relating to downstream task performance are not clear. Overall, it should be abundantly clear what the key messages are from this paper, but they are lost in the density of the work.\n\n2. There is insufficient discussion of other theoretical studies of SSL (only a brief mention in the introduction).\n\n3. Some of the statements and proofs are not rigorous, as it is not formally defined what it means for one method to recover another. The proof of Theorem 3 requires an assumption that is not made in the theorem statement. Other proofs can use more formality (only English text is given and the reader is left to fill in the details) and the proof of Lemma 1 is missing.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Qy2g9aD5Xe", "reviewer": "Reviewer_VtRd", "summary": "This paper introduces a general framework that leverages spectral methods to unify the representative self-supervised learning (SSL) methods such as VICReg, SimCLR, BarlowTwins. The authors provide a detailed theoretical analysis of different SSL frameworks and demonstrate the properties of their learned representations.  ", "questions": "I am generally satisfied with the paper, but have an open question based on the analysis:\n\nAs these methods have different properties, while some of them are complementary, e.g., VICReg prevents dimensional collapse, while SimCLR could have a dimensional collapse, is there any way to propose a solution that complements each other's advantages? ", "limitations": "The authors have discussed the limitation of the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strength:\n\nUnifying existing self-supervised learning methods with spectral methods looks interesting. It also provides new insights into the community to help understand how SSL works. Both the motivation and the technical details in the experiment designs seem sound. The authors have cited most of the relevant papers and well summarized previous works. \n\n### Weakness:\n\nAlthough the paper provides an insightful view of understanding the mechanism of SSL, most of the analysis is only valid in the pre-assumptions, some of which might have a gap in practical usage. For example, the properties of VICReg are based on the linear network assumption, while in practice, the encoder backbones are often non-linear. As the authors claim this paper aims to provide some guidelines to practitioners, these gaps could limit their insights to them. \n\nThe example in Eq (4) and (5) is a little bit hard to follow. It is not obvious see the logical relation between these two formulations. \n\nThe presentation quality is fairly good but needs further polishing. It feels like the paper is finished in a rush, and some paragraphs are not clear to the readers. Some abbreviations are not explained with the full name or corresponding citation when first appearing in the text, e.g., DA, DN, which might confuse the readers.   \n\nThe experiment/simulation settings are not specified in the paper, although most validations are conducted on toy examples. For example, what datasets are used for these proof of concepts? \n\nMost of the discussions are based on the assumption that the downstream task is classification, while in practice, SSL methods are widely used in various settings, including detection, segmentation, generative modeling, etc. The insight to practitioners might be limited in the scope of the classification. \n\nMinors: \n\nThe notation $h$ in Eq (3) is not used; simCLR -> SimCLR\n\nLine 91: loose -> lose; \n\nLine 98: variosu -> various", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HRzPZVVNvnE", "reviewer": "Reviewer_ZYB8", "summary": "This paper explores the links between self-supervised losses, metric learning and spectral embedding methods. It specifically investigates which representations are learnt when the embedding is chosen to be linear, and carefully investigates how the choice of loss affects their rank. ", "questions": "**Clarification**\n1. Figure 3 is intruiging. Indeed, VIC is composed of three terms: the \"variance\" and \"covariance\" whiten the representation, while the \"invariance\" term incorporates \"downstream\" task information (e.g. an image and its rotation should have the same label). However, Figure 3 shows that the downstream task can be perfectly when the \"invariance\" term barely intervenes (gamma = 0.001, just enough to make Z full rank). In other words, this suggests that a (nonlinear) PCA or ICA would be enough to solve a downstream task, which is counter-intuitive to SSL which posits that injecting downstream task information via pairwise relations (matrix G) is essential. Could the authors comment on that?\n2. The spectral analysis VICReg and Barlow Twins are presented as separate contributions, but isn't Barlow Twins subsumed by VICReg (setting the 'variance' term to zero)?\n3. The authors reference \"BarlowTwins, DINO, BYOL, and SimSIAM\" but DINO and BYOL do not seem to appear subsequently in the analysis: could the authors clarify?\n4. It is not very clear to me how equation (4) is built and subsequently used.\n5. \"The authors write \"VICReg\" recovers [...] Linear Discriminant Analysis (LDA)\": can the authors specify is that is when the whitening is enforced (Theorem 2) or relaxed with alpha and beta (equation 1)?\n6. The sentence \"This already brings a contrast from non-contrastive methods showing that contrastive methods learn to produce signals such that the graph estimate is close to the known graph\" seems like it is over-reaching. I am not sure there is a clear definition of \"contrastive\" and \"non-contrastive\" methods in the first place: it could be possible after all to reformulate VICReg as a contrastive loss with implicit negative samples. Also, SimCLR learns a graph estimate (G_hat in equation 15) while VICReg does not (equation 1), but that is a choice in the loss. Perhaps it is clearer to compare VICReg with SimCLR directly, without extrapolating to \"non-contrastive\" vs. \"contrastive\"?\n7. [1] reformulates PCA and Kernel PCA using a Laplacian given in Section 3.3. \"Principal Component Analysis\", matrix Lij. This corresponds to solving the \"variance\" and \"covariance\" terms of VICReg in this submission, as they are enforced in Theorem 2. Could the authors comment on that? Does that connect with the authors' equation 9 which combines the Laplacians of the PCA terms (\"variance\" and \"covariance\") with the Laplacian of the downstream task (\"invariance\" to G)?\n\n\n\n\n **Minor Typos or Formulations**\n- \"We can directly remind the VICReg\" -> recall\n- \"variosu\" -> various\n- \"there exists many local minimum\" -> there exist many local minima\n- \"to solve the task at hand perfect\" -> perfectly\n- \"Prior to moving\" -> Before moving\n- \"unify SSL methods under the realm\" -> under the helm\n- \"similar pairwise distance (usually l2) than\" -> similar [...] to\n- \"we ought ot\" -> to\n- \"poitn\" -> point\n\n\n**Related Work**\n\nI believe there is very relevant work that could be referenced by the authors. \n- [1] unifies many embedding methods (e.g. PCA, spectral methods, MDS, UMAP, Isomap) under the helm of pairwise metric learning\n- [2] already draws a link between SiamSiam and nonlinear CCA\n- [3] connects spectral methods (over a Kernel, e.g. Covariance or Graph Laplacian) with SSL objectives, and possibly provides theoretical justification for tricks of the trade (e.g. 'stop-gradient' for so-called 'Non-Contrastive' SSL to avoid collapse). \n\n\nAbbreviation: SSL = Self-Supervised Learning.\n\n[1] Agrawal, Ali, Boyd, 2021. Minimum Distortion Embedding. \n\n[2] Lee, Lei, Saunshi, Zhuo, 2021. Predicting What You Already Know Helps: Provable Self-Supervised Learning.\n\n[3] Pfau, Petersen, Agarwal, Barrett, Stachenfeld, 2019. Spectral Inference Networks: Unifying Deep and Spectral Learning. \n", "limitations": "I have no potential negative societal impact to raise.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThough many connections between metric learning, SSL and spectral embedding methods have been previously explored [1, 2, 3], this paper is a welcome addition. Explicitly writing out the optimal representations in the linear regime is useful. Explicitly showing how the choice of SSL loss impacts the rank of the learnt representation (in comparison of the rank of the downstream information encoded in G) is  a welcome contribution to recent investigations on the \"dimensional collapse\" of SSL representations. \n\n\n**Weaknesses: better referencing known terminology and problems**\n\nGiven the authors are connecting SSL to known Spectral Embedding methods, it would add significant clarity to draw on known terminology as well. For example, VICReg is composed of three terms that are eponymously described as 'variance-invariance-covariance' with a rather new vocabulary of 'dimensional collapse' and 'semantic' similarity. On a simpler level, the VICReg loss is simply Robust Nonlinear PCA, where Terms 1 and 2 'whitens the signal' and Term 3 encourages robustness to perturbations (e.g. jitter or rotation) encoded in G. Specifically,\n- Term 1 removes the scaling ambiguity of PCA (by setting the variances to 1)\n- Term 2 encourages orthogonal representations\n- Term 3 encourages robustness to user-specified transforms (e.g. rotation)\n\nRelating this to known terminology (PCA) is useful because it *explains* the observations made by the authors, when they say\n- \"the optimum is not unique\" or \"there exist many local minima\": this is due to well-known indeterminacies for PCA (e.g. permutation, offset) and is not a new problem\n- Fig 2, gamma = 0 vs. gamma = 0.1 is essentially PCA vs. Robust PCA. Expectedly, PCA has known indeterminacies (Panel 3) and Robust PCA blurs the landscape (Panel 3) and smoothens the latent space (Panel 2) as it desensitizes the loss to local perturbations. \n\nIt seems like these observations are framed as a new problem of VICReg when they in fact inherit from PCA. \n\n\nAbbreviation: SSL = Self-Supervised Learning.\n\n[1] Agrawal, Ali, Boyd, 2021. Minimum Distortion Embedding. \n\n[2] Lee, Lei, Saunshi, Zhuo, 2021. Predicting What You Already Know Helps: Provable Self-Supervised Learning.\n\n[3] Pfau, Petersen, Agarwal, Barrett, Stachenfeld, 2019. Spectral Inference Networks: Unifying Deep and Spectral Learning. \n\n\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept