# Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and
Local Spectral Embedding Methods

Randall Balestriero
Meta AI Research
NYC, USA
<EMAIL_ADDRESS>
&Yann LeCun
Meta AI Research & NYU
NYC, USA
<EMAIL_ADDRESS>

###### 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…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 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 et al. This unification will then allow us to 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 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 downstream task, any SSL method can be employed successfully and will
recover the supervised method, but in the low data regime, VICReg’s invariance
hyper-parameter should be high; (ii) if the pairwise relation is misaligned
with the downstream task, VICReg with small invariance hyper-parameter should
be preferred over SimCLR or BarlowTwins.

##  1 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 $({\bm{X}})$, and supervised learning relies on inputs and outputs
$({\bm{X}},{\bm{Y}})$, SSL relies on inputs and inter-sample relations
$({\bm{X}},{\bm{G}})$ that indicate semantic similarity akin to weak-
supervision used in metric learning (Xing et al., 2002). The latter matrix
${\bm{G}}$ is often constructed by augmenting ${\bm{X}}$ through data-
augmentations known to preserve input semantics (Kanazawa et al., 2016;
Novotny et al., 2018; Gidaris et al., 2018) e.g. horizontal flip for an image,
although recent methods have went away from DA by using videos from which
consecutive frames can be seen as semantically equivalent (Sermanet et al.,
2018; Kim et al., 2019; Xu et al., 2019).

Although SSL originated decades ago (Bromley et al., 1993), recent advances
have pushed SSL performances beyond expectations (Chen et al., 2020; Misra and
Maaten, 2020; Caron et al., 2021). Due to those rapid empirical advances, an
urgent need for a principled theoretical understanding of those methods has
emerged e.g. to understand how well the learned transformation transfer to
different downstream tasks (Goyal et al., 2019; Ericsson et al., 2021).
Studies looking to provide a more fundamental and principled understanding of
SSL mostly take one of the three following approaches: (i) studying the
training dynamics and optimization landscapes in a linear network regime e.g.
validating some empirically found tricks as necessary conditions for stable
gradient dynamics Wang et al. (2021); Tian et al. (2021); Wen and Li (2021);
Pokle et al. (2022); Tian (2022), (ii) studying the role of individual SSL
components separately e.g. the projector and predictor networks Hua et al.
(2021); Jing et al. (2021); Bordes et al. (2021); Tosh et al. (2021), or (iii)
developing novel SSL criteria that often combine multiple interpretable
objectives that a SSL model must fulfill (Arora et al., 2019; Nazi et al.,
2019; Wang and Isola, 2020; Shi et al., 2020; Zbontar et al., 2021; Bardes et
al., 2021). While those branches have led to novel understandings and even
stem novel SSL methods, some fundamental questions remain open.

More recently and particularly relevant to our study, Qiu et al. (2018)
unified skip-gram/word2vec methods under the helm of matrix factorization.
Without much effort, those results could be used to unify pretext-task SSL
learning (Baevski et al., 2020; Bao et al., 2021b; He et al., 2021) (our focus
is on joint-embedding SSL). Closer to our topic, HaoChen et al. (2021, 2022)
developed a study of SimCLR (Chen et al., 2020) by proposing a modified
objective coined as Spectral Contrastive Loss based on graph representation of
pairwise similarities. A perhaps more direct connection between video-based
SSL and spectral methods (Laplacian Eigenmap in particular) can be found by
combining the Spectral Inference Networks (SIN) of Pfau et al. (2019) that
generalize Slow Feature Analysis (SFA) to arbitrary linear operators, and the
known relationship between SFA and Laplacian Eigenmap (Sprekeler, 2011).
Although SIN was not framed within an SSL viewpoint e.g. SIN has a well-posed
learned coordinate system while SSL methods coordinates can be arbitrarily
rotated; those studies paved our way forward as we propose in this paper a
broad analysis that unify most existing SSL methods as variants of known
spectral embedding methods, allowing us for the first time to provide provable
design guildelines to practitioners in their choice of architecture and
methods. We summarize our unification results in Fig. 1. The instrumental
results we obtain allow us to answer some long-standing questions such as:

VICRegBarlowTwinsSimCLR/NNCLR -Laplacian Eigenmaps (${\bm{z}}$-space)
-Kernel Locality Preserving
Projections (${\bm{x}}$-space) Kernel Canonical
Correlation Analysis (${\bm{x}}$-space) Canonical Correlation
Analysis Locality Preserving
Projection Linear Discriminant
Analysis $\ell_{2}$ Regression Principal Component Analysis -Multidimensional
Scaling (${\bm{z}}$-space)
-Kernel Multidimensional Scaling (${\bm{x}}$-space) alwayslinear $f_{\theta}$ \+ ${\bm{G}}={\bm{X}}^{T}{\bm{X}}$supervised ${\bm{G}}$linear $f_{\theta}$ \+ ${\bm{G}}={\bm{X}}^{T}{\bm{X}}$linear $f_{\theta}$linear $f_{\theta}$ \+ supervised ${\bm{G}}$alwayslinear $f_{\theta}$ \+ supervised ${\bm{G}}$linear $f_{\theta}$always $\approx$ (linear) symmetric ${\bm{G}}$

Figure 1: Summary of our unification of SSL methods to known local and global
spectral embedding methods. In doing so, we are able to find the exact
settings for which different methods provably become identical. In short, all
are concerned in preserving the left-singular vectors of the similarity matrix
${\bm{G}}$ (see Fig. 3) in the representation ${\bm{Z}}$.

Are the numerous flavors of SSL methods e.g. contrastive and non-contrastive
learning different representations? We demonstrate through this study that all
SSL methods’ optimal learn a representation ${\bm{Z}}$ whose top left singular
vectors align with the ones of ${\bm{G}}$, and that none of the SSL methods
constrain the right-singular vectors of ${\bm{Z}}$.

Can we guarantee that minimizing a SSL loss produces a representation that is
optimal to solve a downstream task? Yes, Section 6.3 demonstrates that a
representation learned from $({\bm{X}},{\bm{G}})$ with any SSL loss is
guaranteed to solve any downstream task $({\bm{X}},{\bm{Y}})$ as long as the
left spectrum of ${\bm{G}}$ and ${\bm{Y}}$ are aligned.

Are there fundamental differences between contrastive and non-contrastive
methods e.g. when ${\bm{G}}$ is unknown? We demonstrate that the optimal
VICReg representation can be made full-rank while learning from ${\bm{G}}$ by
carefully selecting the loss hyperparameters (Theorems 1 and 5), while SimCLR
and BarlowTwins strictly enforce
$\operatorname{rank}({\bm{Z}})=\operatorname{rank}({\bm{G}})$ (Figs. 8 and 9
respectively), hinting at a possible advantage of VICReg when ${\bm{G}}$ is
misspecified (Section 6.4).

How does connecting SSL methods to spectral embedding methods improve our
understanding and guide the design of novel SSL frameworks? We demonstrate
that contrastive and non-contrastive SSL corresponds to global and local
spectral embedding methods respectively (Sections 3.2 and 4.3). From that, we
easily identify the best use-cases for each of them e.g. contrastive methods
aim to be metric preserving and shine with low-dimensional or high-dimensional
but linear manifolds while non-contrastive shine with locally linear but
globally nonlinear manifolds.

The natural symbiosis between SSL and spectral methods formulations that will
be discovered throughout this study not only enables us to answer the above
challenging questions but also provides practical guidelines to practitioners.
One emblematic example is offered in Sections 3.3 and 5.2 where we obtain the
analytical network parameters of SSL methods in the linear regime; another
example is offered in Section 4.3 where novel and interpretable variations of
SimCLR are obtained from first principles; or even in Section 6.4 where we
identify the situations for which different SSL methods should be preferred.
We summarize our contributions below:

  1. 1.

Closed-form optimal representation for SSL losses. The DN representation
${\bm{Z}}$ of inputs ${\bm{X}}$ learned by minimizing any SSL loss given a
sample relation matrix ${\bm{G}}$ is obtained in closed-form, shedding light
to many spectral properties of those representation e.g. SSL only constrains
the left singular vectors and singular values of ${\bm{Z}}$ to align with the
ones of ${\bm{G}}$ (Sections 3.1, 4.1 and 5.1 for VICReg, SimCLR and
BarlowTwins).

  2. 2.

Closed-form optimal network parameters for SSL losses with linear networks.
The linear representation ${\bm{Z}}={\bm{X}}{\bm{W}}+{\bm{b}}$ parameters
obtained by minimizing any SSL loss given a sample relation matrix ${\bm{G}}$
are obtained in closed-form, providing insights into the type of input
statistics that a network parameters focus on to produce the optimal input
representation (Sections 3.3 and 5.2 for VICReg and BarlowTwins).

  3. 3.

Exact equivalence between SSL and spectral embedding methods. SSL methods
employ diverse criterion that can be tied to eponymous spectral analysis
methods both when employing a nonlinear DN as Laplacian Eigenmaps (VICReg,
Section 3.2), ISOMAP (SimCLR/NNCLR, Section 4.3), Canonical Correlation
Analysis (BarlowTwins, Section 5.2) and when employing a linear network as
Locality Preserving Projection (VICReg, Section 3.3), Cannonical Correlation
Analysis (BarlowTwins, Section 5.2), and Linear Discriminant Analysis for both
VICReg and BarlowTwins.

  4. 4.

Optimality conditions of SSL representations on downstream tasks (${\bm{Y}}$).
When the correct data relation matrix is given i.e. with left singular vector
associated to nonzero singular values that span the space of left singular
vectors of the target matrix, then perfect minimization of any of those SSL
losses will provide an optimal representation (Section 6.3) which —up to a
rotation of its right singular vectors— is identical to the one learned in a
supervised setting (Section 6.1) a necessary and sufficient condition to
perfectly solve a task at hand with a linear probe (Section 6.2).

We carefully prove each statement of this study in Appendix A. To ensure
clarity of our statements and results, we also provide code excerpts
throughout the manuscript.

##  2 Notations and Background on Self-Supervised Learning

We provide in 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.e.
input samples
${\bm{X}}\triangleq[{\bm{x}}_{1},\dots,{\bm{x}}_{N}]^{T}\in\mathbb{R}^{N\times
D}$ and a known pairwise positive relation between those samples e.g. in the
form of a symmetric matrix ${\bm{G}}\in\\{0,1\\}^{N\times N}$ where
$({\bm{G}})_{i,j}=1$ iff samples ${\bm{x}}_{i}$ and ${\bm{x}}_{j}$ are known
to be semantically related, and with $0$ in the diagonal. Commonly, one is
only given a dataset ${\bm{X}}^{\prime}\in\mathbb{R}^{N^{\prime}\times
D^{\prime}}$ where commonly $D=D^{\prime}$, and artificially constructs
${\bm{X}},{\bm{G}}$ from augmentations of ${\bm{X}}^{\prime}$ e.g. rotated,
noisy versions of the original samples and turning the corresponding entries
of ${\bm{G}}$ to be positive for the samples that have been augmented form the
same original sample. The positive samples are often denoted as views, and in
the situation where only ${\bm{X}}^{\prime}$ is given, ${\bm{X}}$ is often
formed as

$\displaystyle{\bm{X}}=[\operatorname{View}_{1}({\bm{X}}^{\prime})^{T},\dots,\operatorname{View}_{V}({\bm{X}}^{\prime})^{T}]^{T},$
(1)

where a row $(\operatorname{View}_{v}({\bm{X}}^{\prime}))_{n,.}$ is viewed as
similar to the same row of
$(\operatorname{View}_{v^{\prime}}({\bm{X}}^{\prime}))_{n,.},\forall
v\not=v^{\prime}$. Commonly, one employs $V=2$ i.e. only positive pairs are
used. If one desires to duplicate a sample multiple times to obtain multiple
positive pairs from the same original sample ${\bm{x}}_{n}^{\prime}$, it is
done by duplicating that sample within ${\bm{X}}^{\prime}$ prior applying Eq.
1. The $\operatorname{View}_{c}(.),c=1,\dots,C$ operator is a sample-wise
transformation e.g. adding white noise, masking, and the likes i.e. the same
row of different view-matrix are different transformations of the same
original sample from ${\bm{X}}^{\prime}$. In the case of Eq. 1, ${\bm{G}}$
—which will be of shape $(VN^{\prime}\times VN^{\prime})$— can be easily
formed via

⬇

1G = torch.zeros(Np * V, Np * V) #
${\bm{X}}^{\prime}\in\mathbb{R}^{N^{\prime}\times D^{\prime}}$, V is the
number of views

2i = torch.arange(0, Np * V).repeat_interleave(V - 1) # row indices

3j = (i + torch.arange(1, V).repeat(Np * V) * Np).remainder(Np * V) # column
indices

4G[i,j] = 1 # unweighted graph connecting the rows of
$\operatorname{View}_{1}({\bm{X}}^{\prime}),\dots,\operatorname{View}_{V}({\bm{X}}^{\prime})$

where a sparse matrix could be used for ${\bm{G}}$ to improve efficiency,
examples are provided in Fig. 3.

Lastly, we will also denote by ${\bm{Z}}\in\mathbb{R}^{N\times K}$ the matrix
of feature maps or embeddings obtained from a model $f_{\theta}$ —commonly a
Deep Network— such as
${\bm{Z}}\triangleq[f_{\theta}({\bm{x}}_{1}),\dots,f_{\theta}({\bm{x}}_{N})]^{T}$

VICReg. With the above notations out of the way, we can introduce the VICReg
loss Bardes et al. (2021) which is a function of ${\bm{X}}$ and ${\bm{G}}$
—although ${\bm{G}}$ was not explicitly employed originally— as

$\displaystyle\mathcal{L}_{\rm vic}=$
$\displaystyle\alpha\sum_{k=1}^{K}\max\left(0,1-\sqrt{\mathrm{Cov}({\bm{Z}})_{k,k}}\right)+\beta\sum_{j=1,j\not=k}^{K}\mathrm{Cov}({\bm{Z}})^{2}_{k,j}+\frac{\gamma}{N}\sum_{i=1}^{N}\sum_{j=1}^{N}({\bm{G}})_{i,j}\|{\bm{Z}}_{i,.}-{\bm{Z}}_{j,.}\|_{2}^{2}.$
(2)

The VICReg loss has a computational complexity of $\mathcal{O}(NK^{2}+PNK)$
with $P$ the average number of positive samples i.e. number of nonzeros
elements in each row of ${\bm{G}}$. Since $P$ is often small ($P\ll K$), the
computational cost is dominated by the covariance matrix,
$\mathcal{O}(NK^{2})$. The implementation of Eq. 2 is straightforward (details
in the proof of Theorem 1) as

⬇

1C = torch.cov(Z.t()) # ${\bm{Z}}\in\mathbb{R}^{N\times K}$

2var_loss = K - torch.diag(C).clamp(eps, 1).sqrt().sum() # $\epsilon$ avoids
inf. sqrt gradient at 0

3i,j = G.nonzero(as_tuple=True) # with G as in Fig. 3, i and j are vectors of
indices

4inv_loss =(Z[i]-Z[j]).square().sum(1).inner(G[i,j])/N # pairwise $\ell_{2}$
weighted by ${\bm{G}}_{i,j}$

5cov_loss = 2 * torch.triu(C, diagonal=1).square().sum() # 2x upper triangular
part

6loss = alpha * var_loss + beta * cov_loss + gamma * inv_loss # equals to (2)
with $\alpha,\beta,\gamma$

SimCLR. The SimCLR loss (Chen et al., 2020) consists in two steps. First, it
produces an estimate $\widehat{{\bm{G}}}({\bm{Z}})$ of the relation matrix
${\bm{G}}$ from the embeddings ${\bm{Z}}$, generally by using the cosine
similarity ($\operatorname{CoSim}$) as in

$\displaystyle(\widehat{{\bm{G}}}({\bm{Z}}))_{i,j}=\frac{e^{\operatorname{CoSim}({\bm{z}}_{i},{\bm{z}}_{j})/\tau}}{\sum_{k=1,k\not=i}^{N}e^{\operatorname{CoSim}({\bm{z}}_{i},{\bm{z}}_{k})/\tau}}{\bm{1}}_{\\{i=j\\}},$
(3)

with $\tau>0$ a temperature parameter. Notice that
$\widehat{{\bm{G}}}({\bm{Z}})$ is a right-stochastic matrix i.e.
$\widehat{{\bm{G}}}({\bm{Z}})\mathbf{1}=\mathbf{1}$. Then, SimCLR encourages
the elements of $\widehat{{\bm{G}}}({\bm{Z}})$ and ${\bm{G}}$ to match. The
most popular solution to achieve that is to leverage the infoNCE loss given by

$\displaystyle\mathcal{L}_{\rm
simCLR}=\underbrace{-\sum_{i=1}^{N}\sum_{j=1}^{N}({\bm{G}})_{i,j}\log(\widehat{{\bm{G}}}({\bm{Z}}))_{i,j}}_{\text{cross-
entropy between matrices}},$ (4)

where ${\bm{G}}$ is assumed to be a right-stochastic matrix as well. If not, a
simple renormalization can be applied before employing the infoNCE loss. The
only difference between SimCLR and its variants e.g. NNCLR (Dwibedi et al.,
2021) lies in the construction of ${\bm{G}}$ when only given
${\bm{X}}^{\prime}$ (the input samples without any augmentation applied,
recall the beginning of Section 2). As opposed to VICReg, the SimCLR loss has
computational complexity of $\mathcal{O}(N^{2})$ as it requires to compute all
the pairwise similarities in Eq. 3. Nevertheless, Eq. 4 can be easily computed
as follows (here using the $\operatorname{CoSim}$ again)

⬇

1Z_renorm = torch.nn.functional.normalize(Z, dim=1) #
${\bm{Z}}\in\mathbb{R}^{N\times K}$

2cosim = Z_renorm @ Z_renorm.t() / tau # N x N matrix, tau is the temperature
$\tau$ from (3)

3off_diag = cosim[~I.bool()].reshape(N, N-1) # for denom. of (3), I =
torch.eye(N, N)

4loss = (G * (torch.logsumexp(off_diag, dim=1, keepdim=True) - cosim)).sum() #
gives (4)

BarlowTwins. Lastly, BarlowTwins (Zbontar et al., 2021) proposes yet a
slightly different approach based on observing two views of a dataset
${\bm{X}}^{\prime}$ denoted as ${\bm{X}}_{\rm left}$ and ${\bm{X}}_{\rm
right}$ and with corresponding embeddings ${\bm{Z}}_{\rm left}$ and
${\bm{Z}}_{\rm right}$. The same row of those left/right matrices are the
positive pairs. Denoting by ${\bm{C}}$ the $K\times K$ cross-correlation
matrix between ${\bm{Z}}_{\rm left}$ and ${\bm{Z}}_{\rm right}$, we obtain the
loss

$\displaystyle\mathcal{L}_{\rm
BT}=\sum_{k=1}^{K}(({\bm{C}})_{k,k}-1)^{2}+\alpha\sum_{k^{\prime}\not=k}({\bm{C}})_{k,k}^{2},\;\alpha>0.$
(5)

Notice that $({\bm{C}})_{i,j}$ falls back to measuring the cosine similarity
between the $i^{\rm th}$ column of ${\bm{Z}}_{\rm left}$ and the $j^{\rm th}$
column of ${\bm{Z}}_{\rm right}$ i.e.
$({\bm{C}})_{i,j}=\frac{\langle({\bm{Z}}_{\rm left})_{.,i},({\bm{Z}}_{\rm
right})_{.,j}\rangle}{\|({\bm{Z}}_{\rm left})_{.,i}\|_{2}\|({\bm{Z}}_{\rm
right})_{.,j}\|_{2}+{\epsilon}}$ where one commonly adds an additional
constant $\epsilon$ for numerical stability. The computational complexity of
Eq. 5 falls back to $\mathcal{O}(NK^{2})$ and its computation is easily
performed as

⬇

1Z_lrenorm = torch.nn.functional.normalize(Z_left, dim=0, eps=eps) # includes
$\epsilon$

2Z_rrenorm = torch.nn.functional.normalize(Z_right, dim=0, eps=eps) # includes
$\epsilon$

3C = Z_lrenorm.t() @ Z_rrenorm # cross-correlation (K x K matrix)

4loss = (C.diag() - 1).square().sum() + alpha*C[~I.bool()].square().sum() #
gives Eq. 5

Note that if one possesses a dataset with arbitrary number of positive
samples, it is still possible to recover ${\bm{X}}_{\rm left},{\bm{X}}_{\rm
right}$ for $\mathcal{L}_{\rm BT}$ with the following simple strategy. Suppose
that we have $5$ samples ${\bm{a}},{\bm{b}},{\bm{c}},{\bm{d}},{\bm{e}}$, and
that ${\bm{a}},{\bm{b}},{\bm{c}}$ are related to each other, and that
${\bm{d}},{\bm{e}}$ are related to each other, based on ${\bm{G}}$. Then, one
can simply create the two data matrices as

$\displaystyle{\bm{X}}_{\rm
left}=[{\bm{a}},{\bm{a}},{\bm{b}},{\bm{b}},{\bm{c}},{\bm{c}},{\bm{d}},{\bm{e}}]^{T},\;{\bm{X}}_{\rm
right}=[{\bm{b}},{\bm{c}},{\bm{a}},{\bm{c}},{\bm{a}},{\bm{b}},{\bm{e}},{\bm{d}}]^{T},$
(6)

which can be easily obtained given ${\bm{G}}$ and the input matrix ${\bm{X}}$
via

⬇

1row_indices, col_indices = G.nonzero(as_tuple=True) # G as in Fig. 3

2X_left = X[row_indices] # equals the left-hand-side of (6)

3X_right = X[col_indices] # equals the right-hand-side of (6)

binary classification graph

“multi-crop-type” self-supervised graph

“pair-type” self-supervised graph

Figure 2: Depiction of the “knowledge graph” arising from different settings:
binary classification (left), SSL with multi-crop-style relation i.e. that
number of positive samples associated to each datum can be made arbitrarily
large (middle), and pair-style SSL where each sample is only associated to
another single sample (right). In this representation, each point can be
equivalently seen as an abstract node (blue circlr) or as a single signal
${\bm{x}}_{n},n=1,\dots,N$ (image in this case, depicted on top). In this
case, the underlying data comes from two classes depicted with red and blue
image borders. A model’s prediction on those signals
$f_{\theta}({\bm{x}}_{n})$ can be viewed as a signal on the graph (recall
Section 2). That graph is itself encoded as a symmetric, nonnegative matrix
similarity matrix ${\bm{G}}$, as depicted in Fig. 3.

binary classification

(2 classes ${\bm{X}}$=$[{\bm{X}}_{0}^{T},{\bm{X}}_{1}^{T}]^{T}$)

“multi-crop-type” SSL

(N/K classes, K>2)

“pair-type” SSL

(N/2 classes)

Figure 3: Examples of the $N\times N$ symmetric adjacency matrices ${\bm{G}}$
for the three cases of Fig. 2. In all cases, each nonzero entry
$({\bm{G}})_{i,j}$ represents the positive relation between sample $i$ and
$j$. The insight that will play a key role in our analysis is that the
eigenvectors of those matrices entirely encode the similarity information
between samples that SSL utilize to constrain the learned representation
(${\bm{Z}}$)’s spectrum (see Theorems 1, 5 and 6). Although ${\bm{G}}$ is
commonly symmetric, it is often not required (see Theorem 7).

Linear Algebra Notations. This study heavily relies on the Singular Value
Decomposition (SVD) of matrices (Eckart and Young, 1936; Hestenes, 1958) e.g.
${\bm{X}}={\bm{U}}_{x}{\bm{\Sigma}}_{x}{\bm{V}}^{T}_{x}$ that are denoted as
the left singular vectors ${\bm{U}}_{x}\in\mathbb{R}^{N\times N}$, the
singular values ${\bm{\Sigma}}_{x}\in\mathbb{R}^{N\times D}$ and the right
singular vectors ${\bm{V}}_{x}\in\mathbb{R}^{D\times D}$ of
${\bm{X}}\in\mathbb{R}^{N\times D}$. We will always specify as a lower-script
and lower-case the matrix that is being decomposed ($x$ in this case). It will
also be convenient to only consider the left/right singular vectors whose
associated singular values are $0$ that we will denote as
$\overline{{\bm{U}}}_{x}$ and $\overline{{\bm{V}}}_{x}$ respectively.
Conversely, the left/right singular vectors whose associated singular values
are $>0$ will be denote as $\widehat{{\bm{U}}}_{x}$ and
$\widehat{{\bm{V}}}_{x}$ respectively. Lastly, we will denote by
${\bm{\sigma}}_{z}$ the vector of singular values such as
${\bm{\Sigma}}_{z}=\operatorname{diag}({\bm{\sigma}})$ and without loss of
generality and unless otherwise stated, this will always be in descending
order.

Our goal in the following sections (Section 3 for VICReg, Section 4 for
SimCLR/NNCLR, and Section 5 for BarlowTwins) will be to find the optimal
representations ${\bm{Z}}$ of ${\bm{X}}$ whilst tying those methods to their
spectral embedding counterpart. Three surprising facts will emerge: (i) all
existing methods recover exactly some flavors of famous spectral method, (ii)
the spectral properties of the optimal representation ${\bm{Z}}$ of ${\bm{X}}$
can be obtained in closed-form, and (iii) from those properties, necessary and
sufficient conditions can be obtained to bounds the downstream task error of
those optimal SSL representations (Section 6).

##  3 VICReg Minimizes the Dirichlet Energy to Produce Smooth Signals on the
Graph ${\bm{G}}$ While Preventing Dimensional Collapse

We will first demonstrate in Section 3.1 that the optimal VICReg
representation can be obtained in closed form (Theorem 1) and that turning the
VICReg optimization as a constrained problem recovers (Kernel) Laplacian
Eigenmaps, an eponymous spectral embedding method Section 3.2. We then
consider that same constrained problem but under a linear network regime for
which we obtain the closed-form optimal network’s parameters (Theorem 3) and
in which case, VICReg recovers Locality Preserving Projections and Linear
Discriminant Analysis (Section 3.3).

###  3.1 Closed-Form Optimal Representation for VICReg

The first goal of this section is to build up some insights into VICReg by
demonstrating how the invariance term corresponds to the Dirichlet energy of
the signal ${\bm{Z}}$ on the graph ${\bm{G}}$. Then, replacing the variance
hinge loss at $1$ with the squared loss at $1$ as in
$\sum_{k=1}^{K}\left(1-\mathrm{Cov}({\bm{Z}})_{k,k}\right)^{2}$ —notice that
minimizing the latter implies minimizing the former— we obtain the closed-form
optimal representation ${\bm{Z}}^{*}$ of ${\bm{X}}$ which turns out to be a
function only of ${\bm{G}}$ and the loss’ hyper-parameters.

From invariance to trace minimization. As a first step, we propose to better
understand the impact of VICReg’s invariance term (recall Eq. 2) onto the
left-singular vectors of the representation ${\bm{Z}}$. Recalling from Section
2 that we denote the SVD of ${\bm{Z}}$ by
${\bm{U}}_{{\bm{Z}}}{\bm{\Sigma}}_{{\bm{Z}}}{\bm{V}}^{T}_{{\bm{Z}}}$ we obtain
the following

$\displaystyle\underbrace{({\bm{G}})_{i,j}\|({\bm{Z}})_{i,.}-({\bm{Z}})_{j,.}\|_{2}^{2}}_{\text{$(i,j)$
invariance term in
VICReg}}=({\bm{G}})_{i,j}\|{\bm{\Sigma}}_{z}^{T}(({\bm{U}}_{{\bm{Z}}})_{i,.}-({\bm{U}}_{{\bm{Z}}})_{j,.})\|_{2}^{2}\propto\underbrace{({\bm{G}})_{i,j}\|(\widehat{{\bm{U}}}_{{\bm{Z}}})_{i,.}-(\widehat{{\bm{U}}}_{{\bm{Z}}})_{j,.}\|_{2}^{2}}_{\mathclap{\text{acts
upon the rows of the left singular vector of ${\bm{Z}}$}}},$

where we recall that $\widehat{{\bm{U}}}_{{\bm{Z}}}$ are the left-singular
vectors of ${\bm{Z}}$ associated to nonzero singular values, and
$({\bm{M}})_{i,.}$ extracts the $i^{\rm th}$ row viewed as a column vector,
for any matrix ${\bm{M}}$. Hence, VICReg effectively minimizes the pairwise
distance between the $i^{\rm th}$ and $j^{\rm th}$ rows of
$\widehat{{\bm{U}}}_{Z}$ whenever $({\bm{G}})_{i,j}>0$. This connection can be
made more precise by rewriting the invariance loss of VICReg as the energy of
the signal ${\bm{Z}}$ on the graph ${\bm{G}}$ (Von Luxburg, 2007) since we
have (derivations in Section A.5)

$\displaystyle\underbrace{\sum_{i}\sum_{j}({\bm{G}})_{i,j}\|({\bm{Z}})_{i,.}-({\bm{Z}})_{j,.}\|_{2}^{2}}_{\text{invariance
term in
VICReg}}=2\underbrace{\operatorname{Tr}\left({\bm{Z}}^{T}{\bm{L}}{\bm{Z}}\right)}_{\mathclap{\text{Dirichlet
energy of ${\bm{Z}}$ on ${\bm{G}}$}}},$ (7)

where ${\bm{L}}$ is the graph Laplacian matrix ${\bm{L}}={\bm{D}}-{\bm{G}}$
with ${\bm{D}}$ the diagonal degree matrix of ${\bm{G}}$ i.e.
$({\bm{D}})_{i,j}=\sum_{j}({\bm{G}})_{i,j}$ and $({\bm{D}})_{i,j}=0,\forall
i\not=j$. From Eq. 7 it is clear that the invariance term depends on the
matching between the left singular vectors of ${\bm{Z}}$ and the eigenvectors
of ${\bm{L}}$. Hence, non-contrastive learning aims at producing non-
degenerate signals ${\bm{Z}}$ that are smooth on ${\bm{G}}$.

Analytical optimal representation. To gain further insights into VICReg, we
ought to obtain the analytical form of the optimal representation
${\bm{Z}}^{*}$ minimizing Eq. 2 —although this optimum is not unique e.g.
adding a constant entry to each column of ${\bm{Z}}$ does not change the loss
value (details in Section A.6). To that end, we will need to work with a
slightly friendlier variance term i.e. we replace the hinge loss at $1$ with
the squared loss centered at $1$ as in
$\sum_{k=1}^{K}\left(1-\mathrm{Cov}({\bm{Z}})_{k,k}\right)^{2}$. We can now
obtain the following characterization of ${\bm{Z}}^{*}$ as a function of the
spectral decomposition of the matrix that combines two Laplacian matrices
(details in Section A.7). The first, (left of Eq. 8) comes form the
variance+covariance term is the Laplacian of a complete graph i.e. where each
node/sample is connected all others, and the second (right of Eq. 8) is the
one of the graph described by ${\bm{G}}$ as in

$\displaystyle\underbrace{{\bm{I}}-\frac{1}{N}\mathbf{1}\mathbf{1}^{T}}_{\mathclap{\text{Laplacian
of a complete
graph}}}-\frac{\gamma}{\alpha}\overbrace{({\bm{D}}-{\bm{G}})}^{\mathclap{\text{Laplacian
of the SSL/sup.
graph}}}={\bm{P}}_{\alpha,\gamma}\operatorname{diag}({\bm{\lambda}}_{\alpha,\gamma}){\bm{P}}^{T}_{\alpha,\gamma},$
(8)

where the eigenvalues/eigenvectors are in descending orders. Combining the
eigenvectors of the combined Laplacians will be used to produce the optimal
VICReg representation as formalized below.

######  Theorem 1.

A global minimizer of the VICReg loss ($\alpha=\beta,\forall\gamma$) denoted
by ${\bm{Z}}^{*}_{\alpha,\gamma}$ is obtained from Eq. 8 along with the
minimal achievable loss which are given by

$\displaystyle{\bm{Z}}^{*}_{\alpha,\gamma}$
$\displaystyle=({\bm{P}}_{\alpha,\gamma}(\operatorname{diag}({\bm{\lambda}}_{\alpha,\gamma})N)^{1/2})_{:,1:K}\;\;\text{
and }\;\;\min_{{\bm{Z}}\in\mathbb{R}^{N\times K}}\mathcal{L}_{\rm
VIC}=\alpha(K-\|({\bm{\lambda}}_{\alpha,\beta})_{1:K}\|_{2}^{2}),$

and any $K$-out-of-$N$ columns of
${\bm{P}}_{\alpha,\gamma}({\bm{\Lambda}}_{\alpha,\gamma}N)^{1/2}$ is a local
minimum of $\mathcal{L}_{\rm VIC}$. (Proof in Section A.7.)

$\alpha=1,\gamma=0$

$\alpha=1,\gamma=0.1$

convex interp. between top $[k:K+k]$ eigenvectors of Eq. 8

$\min\mathcal{L}_{\rm VIC}$ / train acc. (%)

$\operatorname{rank}({\bm{G}})=K$ $\operatorname{rank}({\bm{G}})=4$

$\alpha=1,\gamma=0$

$\alpha=1,\gamma=0.1$

$\alpha=1,\gamma=0$

$\alpha=1,\gamma=0.1$

Figure 4: Left: depiction of the optimal VICReg loss with varying hyper-
parameters (blue line) when the representation is formed from the top
$[k:K+k]$ eigenvectors of Eq. 8 with convex interpolation in-between. Recall
from Theorem 1 that the global optimum is given by the $[1:K-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 on top of ${\bm{Z}}^{*}_{\alpha,\gamma}$ is able to
solve the task at hand thanks to the probability constraint that must sum to
$1$ i.e. the last component can be recovers from the first $C-1$. Right:
depiction of the loss landscape of $\mathcal{L}_{\rm VIC}$ around the optimal
$Z^{*}_{\alpha,\gamma}$ on the left using the directions provides by the top
$[2:K+1]$ and $[3:K+2]$ eigenvectors of Eq. 8, and then with random directions
in ${\bm{Z}}$-space. All experiments employed
$N=256,K=16,\operatorname{rank}({\bm{G}})=4$.

invariance coefficient $\gamma$ ($\alpha=\beta=1$)

$k$ $\min\mathcal{L}_{\rm vic}$ /train acc. (%)

Figure 5: Top: the minimal VICReg loss (blue line) and corresponding
downstream task performance (orange line). Bottom: evolution of
${\bm{Z}}^{*}_{\alpha,\gamma}$’s singular values. We observe that VICReg
benefits from a $(\alpha,\gamma)$-zone for which
${\bm{Z}}^{*}_{\alpha,\gamma}$ remains full rank and still incorporates enough
information on ${\bm{G}}$ to solve the downstream task. Hence, depending on
the confidence one has into ${\bm{G}}$, one can adjust $\gamma/\alpha$ to
either incorporate no information on ${\bm{G}}$, incorporate ${\bm{G}}$ and
maintain full-rank or entirely collapse to ${\bm{G}}$. All experiments
employed $N=256,K=32,\operatorname{rank}({\bm{G}})=8$.

The above result provides a few key insights. First, only the ratio
$\gamma/\alpha$ governs the VICReg representation. Second, there exists many
local minimum, some of which can be explicitly found by taking various
$K$-out-of-$N$ columns of
${\bm{P}}_{\alpha,\gamma}({\bm{\Lambda}}_{\alpha,\gamma}N)^{1/2}$ which we
display in Fig. 4 along with the loss landscape of $\mathcal{L}_{\rm VIC}$
around the optimal representation ${\bm{Z}}^{*}$. We also depict in Fig. 5 the
evolution of the eigenvalues $({\bm{\lambda}}_{\alpha,\gamma})_{1:K}$ for
varying $\gamma$ along with the downstream task (induced by ${\bm{G}}$)
training performance. We observe that VICReg benefits from a sweet-spot where
it can both preserve a full-rank representation ${\bm{Z}}^{*}$ and incorporate
enough information about ${\bm{G}}$ to solve the task at hand perfect. As will
become clear in Sections 4 and 5 this does not hold for all methods as SimCLR
and BarlowTwins collapse the rank of ${\bm{Z}}^{*}$. We also depict on the
left of Fig. 6 the convergence of the optimal representation of VICReg to the
true one with different flavors of gradient descent. Beyond interpretability,
Theorem 1 also clearly demonstrate the impact of ${\bm{G}}$ on the quality of
the obtained representation ${\bm{Z}}^{*}_{\alpha,\gamma}$. We will make the
ability of ${\bm{Z}}^{*}_{\alpha,\gamma}$ to solve a downstream task at hand
as a function of the spectrum of ${\bm{G}}$ in Section 6.3.

Computationally friendly solution. Before concluding this section we ought to
recall that Eq. 8, which needs to be decomposed to obtain
${\bm{Z}}^{*}_{\alpha,\gamma}$ is a dense $N\times N$ matrix e.g. as follows

⬇

1L = ch.diag(G.sum(1)) - G # Laplacian matrix ${\bm{L}}$ in Eq. 8

2Lam, P = ch.linalg.eigh(torch.eye(N) - 1 / N - (gamma / alpha) * L) #equals
to (8)

3Z_star = P[:, -K:] * ((Lam[-K:] * N).sqrt()) # equals to ${\bm{Z}}^{*}$ of
Thm. 1

4min_L = alpha * (K - Lam[-K:].norm().square()) # equals to
$\min\mathcal{L}_{\rm vic}$ of Thm. 1

However, we can equivalently find the optimal VICReg solution
${\bm{Z}}^{*}_{\alpha,\gamma}$ only as a function of ${\bm{L}}$ which is
sparse e.g. for SSL ${\bm{L}}$ contains $2N$ nonzero entries, and for
supervised settings with $C$ balanced classes, ${\bm{L}}$ contains $N^{2}/C$
nonzero entries. To do so, notice in Eq. 8 that the left term
${\bm{I}}-\frac{1}{N}\mathbf{1}\mathbf{1}^{T}$ mostly acts to ensure that the
found eigenvectors with nonzero eigenvalues have $0$ mean. Instead, we can
achieve the same goal by defining the following sparse and symmetric matrix

$\displaystyle\begin{pmatrix}0&\mathbf{1}^{T}\\\
\mathbf{1}&{\bm{I}}-\frac{\gamma}{\alpha}{\bm{L}}\end{pmatrix}\in\mathbb{R}^{(N+1)\times(N+1)},$
(9)

and by taking the top $[2:K]$ (and not $[1:K-1]$ as with Eq. 8) eigenvectors.
In short, while Eq. 8 was adding a connection from each node of the graph to
all others, Eq. 9 introduces a new node to the graphs and connects it to all
others, akin to the Hubbard-Stratonovich transformation (Hirsch, 1983). The
great advantage of Eq. 9 is the sparsity of the matrix allowing it to be
easily stored and for which there exists efficient routines to rapidly obtain
the top eigenvectors, even for large $N$. One popular solution is the Locally
Optimal Block Preconditioned Conjugate Gradient (Knyazev, 1987) which only
needs to evaluate matrix-vector products.

Prior to moving to other SSL methods, we first emphasize the ability of VICReg
to recover local spectral methods in the following sections.

K=8 K=32 K=64

# iterations $(t)$

$(\mathcal{L}_{\rm vic}({\bm{Z}}^{(t)})-\mathcal{L}_{\rm
vic}({\bm{Z}}^{*}))^{2}$

$(\mathcal{L}_{\rm vic}({\bm{W}}^{(t)})-\mathcal{L}_{\rm
vic}({\bm{W}}^{*}))^{2}$

K=8 K=32 K=64

# iterations $(t)$

Figure 6: Left: depiction of the convergence between a randomly initialized
representation ${\bm{Z}}$ and the optimal one ${\bm{Z}}^{*}$ from Theorem 1
measured as quadratic difference of the VICReg loss $\mathcal{L}_{\rm vic}$.
Right: depiction of the convergence between a random initialized linear weight
matrix ${\bm{W}}$ and the optimal one ${\bm{W}}^{*}$ from Eq. 12 also measured
as quadratic difference of the VICReg loss $\mathcal{L}_{\rm vic}$. We employ
$\alpha=1,\gamma=0$ on the top row and $\alpha=1,\gamma=0.01$ on the bottom
row and N=512, C=8, D=64. In both cases, the blue line corresponds to RMSProp
optimizer and the black line to SGD. Each setting is repeated $10$ times and
each line corresponds to a different random initialization. We observe that in
both settings gradient based learning is able to produce a final
representation (left) and linear weight (right) that match with the optimum
ones found analytically for VICReg.

###  3.2 VICReg Recovers Laplacian Eigenmaps in Feature Space and Kernel
Locality Preserving Projection in Data Space

From the previous section Theorems 1 and 8 we obtained that the ratio
$\frac{\gamma}{\alpha}$ entirely controls the mixing between the Laplacian
matrix of a complete graph and the one from ${\bm{G}}$. In other words, this
ratio controls the spectral properties of ${\bm{Z}}^{*}_{\alpha,\gamma}$ by
interpolating between the ones of
${\bm{I}}\frac{1}{N}\mathbf{1}\mathbf{1}^{T}$ and the ones of ${\bm{L}}$
(recall Fig. 5). The goal of this section is to study more precisely the
scenario where $\alpha\gg\gamma$ i.e. we prioritize the variance-covariance
terms, in which case VICReg recovers Laplacian Eigenmaps (LE) (Belkin and
Niyogi, 2003) in feature space, and kernel Locality Preserving Projection
(kLPP) (He and Niyogi, 2003) in data space.

In feature space. LE is a non-parametric method searching for a representation
${\bm{Z}}$ by minimizing the following Brockett (Brockett, 1991) optimization
problem

$\displaystyle\min_{{\bm{Z}}}\operatorname{Tr}\left({\bm{Z}}^{T}\left({\bm{D}}-{\bm{G}}\right){\bm{Z}}\right)\text{
s.t. }{\bm{Z}}^{T}{\bm{D}}{\bm{Z}}={\bm{I}},$ (10)

with ${\bm{D}}$ the diagonal degree matrix of ${\bm{G}}$ (recall Eq. 8). The
relation between Eq. 10 and VICReg comes by combining the following two facts.
First, minimizing Eq. 10 is done by taking the eigenvectors associated to the
$K$ smallest eigenvalues of ${\bm{I}}-{\bm{D}}^{-1}{\bm{G}}$ (see Liang et al.
(2021) and Corollary 4.3.39 from Horn and Johnson (2012)) yet, —LE disregards
the eigenvector associated to the eigenvalue $0$— to produce the optimal LE
solution denoted as ${\bm{Z}}^{*}_{\rm LE}$. Doing so, Belkin and Niyogi
(2003) produced a representation whose columns have $0$-mean since the only
eigenvector with nonzero mean is the one associated to the eigenvalue $0$
(details in Section A.8). Second, VICReg employs a graph ${\bm{G}}$ for which
${\bm{D}}=c{\bm{I}}$ with $c=2$ (positive pairs), $c=3$ (positive tirplets,
and so on. And thus, the eigenvectors associated to the nonzero eigenvalues of
${\bm{D}}-{\bm{G}}$ or ${\bm{I}}-{\bm{D}}^{-1}{\bm{G}}$ are the same i.e. the
optimal solution of the LE problem minimizes the VICReg criterion with strict
enforcement that the variance+covariance terms, denoted as
$\mathcal{L}_{var},\mathcal{L}_{\rm cov}$ hereon, are zero.

######  Theorem 2.

Given a dataset ${\bm{X}}$ and relation matrix ${\bm{G}}$, minimizing the
VICReg loss (Eq. 2) with constraint that the variance and covariance loss are
$0$ ($\alpha,\beta$ become irrelevant) as in

$\displaystyle\mathcal{L}_{\rm vic}({\bm{Z}}^{*}_{\rm
LE})=\min_{{\bm{Z}}\in\mathbb{R}^{N\times K}}\mathcal{L}_{\rm
inv}({\bm{Z}})\text{ s.t. }\mathcal{L}_{\rm var}=0\text{ and }\mathcal{L}_{\rm
cov}=0.$

(Proof in Section A.8.)

Hence, given a relation matrix ${\bm{G}}$, solving the LE problem is
equivalent to solving a constrained VICReg problem. We ought to highlight
however that a crucial part of LE lies in the design of that matrix
${\bm{G}}$, often found from a $k$-NN graph (Hautamaki et al., 2004) of the
samples ${\bm{X}}$ in the input space, while in SSL it is constructed from
data-augmentations or given.

Going beyond LE, one can easily obtain that if
$\left({\bm{D}}-{\bm{G}}\right)$ is idempotent —which is true for common
supervised and SSL scenarios as ${\bm{G}}$ corresponds to a union of complete
graphs— then LE also corresponds to Locally Linear Embedding (Roweis and Saul,
2000) and so does VICReg.

In data space. One difficulty arising from LE, and from non-parametric methods
in general, is the ability to produce new representations ${\bm{z}}$ for new
data samples that were not present when solving Eq. 10. This led to the
development of a two-step modeling process as

$\displaystyle{\bm{x}}\;(\in\mathbb{R}^{D})\mapsto{\bm{h}}=\phi({\bm{x}})\;(\in\mathbb{R}^{S})\mapsto{\bm{z}}={\bm{W}}^{T}{\bm{h}}(\in\mathbb{R}^{K}),$

with $S\gg K,{\bm{W}}\in\mathbb{R}^{S\times K}$, and where the first mapping
’s goal is to learn a generic input embedding that can be reused on new
samples ${\bm{x}}$. To see this, let’s collect those mappings for all the
training set into the $N\times S$ matrix $\Phi$. With that, the LE problem in
data space —known as the Kernel Locality Preserving Projection problem—
becomes

$\displaystyle\min_{\theta:{\bm{W}}^{T}\Phi^{T}{\bm{D}}\Phi{\bm{W}}={\bm{I}}}\operatorname{Tr}\left({\bm{W}}^{T}\Phi^{T}\left({\bm{D}}-{\bm{G}}\right)\Phi{\bm{W}}\right),$
(11)

so that the original LE representation ${\bm{Z}}$ can be obtained simply as
${\bm{Z}}=\Phi{\bm{W}}$. And more importantly, given a new sample ${\bm{x}}$,
one can simply obtain the new representation via
${\bm{z}}={\bm{W}}^{T}\phi({\bm{x}})$.

Most existing solutions have been leveraging the Moore-Aronszajn theorem
(Aronszajn, 1950) and the fact that we are in a finite data regime to shift
the question what nonlinear and high-dimensional operator $\phi$ should be
used? to the perhaps simpler question what symmetric positive (semi-)definite
matrix $\Phi\Phi^{T}$, i.e. what kernel, function should be used? (Bengio et
al., 2003; Cheng et al., 2005; Tai et al., 2022). Doing so,
${\bm{W}}^{T}\phi({\bm{x}})$ can now be easily implemented e.g. as a
Generalized Regression Network (Broomhead and Lowe, 1988; Specht et al.,
1991). The crucial result of interest for our study is the following one that
combine Theorem 2 with a result from He and Niyogi (2003) demonstrating the
equivalence between LE in feature space and KLLE in data space.

######  Proposition 1.

VICReg with variance/covariance constraint solves LE in embedding space and
KLLE in input space (recall Eq. 11) employing a DN for
${\bm{W}}^{T}\circ\phi$.

Equipped with those results, we can now propose a practical result by
obtaining in closed-form the optimal parameter weights that solve the
constrained VICReg criterion with a linear network.

###  3.3 With a Linear Network VICReg Recovers Locality Preserving Projections
and Linear Discriminant Analysis with Analytical Optimal Network Parameters

The goal of this section is to focus on the linear case i.e.
${\bm{Z}}={\bm{X}}{\bm{W}}$. In that setting, and still employing the squared
variance term as in Theorem 3, VICReg recovers two known spectral methods:
Locality Preserving Projections (LPP) (He and Niyogi, 2003) for an arbitrary
relation matrix ${\bm{G}}$, and Linear Discriminant Analysis (LDA) (Fisher,
1936; Cohen et al., 2014) when ${\bm{G}}$ is the supervised relation matrix.
In both cases we obtain the analytical form of the optimal weights ${\bm{W}}$.

Prior connecting linear VICReg to LPP and LDA we ought to highlight the
optimal weights ${\bm{W}}^{*}$ of the linear VICReg model (derivations in
Section A.9) given by

$\displaystyle{\bm{W}}^{*}=\left(\mathrm{Cov}({\bm{X}})^{-1}\left(\mathrm{Cov}({\bm{X}})-\frac{\gamma}{\alpha
N}{\bm{X}}^{T}{\bm{L}}{\bm{X}}\right)^{\frac{1}{2}}\right)_{.,1:K},$ (12)

which is easily computed as

⬇

1cov = torch.cov(X.t(), correction=0) # cov. w/o correction (otherwise scale L
by (N-1)

2B = cov - (gamma/ (N * alpha)) * (X.t() @ L @ X)

3Wstar = torch.linalg.solve(A, sqrtm(B)) # numerically stable solution of 12,
sqrtm(B)=$\sqrt{B}$

and we depict the gradient convergence towards this optimal solution is
depicted on the right of Fig. 6.

We now turn to connecting linear VICReg to LPP and LDA, heavily relying on
Theorem 2. In fact, we already saw that VICReg with a DN corresponds to the
Kernel LE methods. In the linear regime, it is already established that kernel
LE recovers LPP. The perhaps less direct result concerns the recovery of LDA
for which we first need to introduce the supervised counterpart of ${\bm{G}}$.
In that case, ${\bm{G}}$ describes the known class relation from
${\bm{y}}\in\\{1,\dots,C\\}^{N}$ as in

$\displaystyle({\bm{G}}_{\rm
s})_{i,j}=1_{\\{({\bm{y}})_{i}=({\bm{y}})_{j}\\}}1_{\\{i\not=j\\}},\;\;\;\text{(supervised
${\bm{G}}$)}$ (13)

which can be directly computed as

⬇

1Gs = torch.eq(target, target[:, None]).float() - torch.eye(N) # equals to Eq.
13

Note that the degree matrix of ${\bm{G}}_{\rm s}$ will contain for each
diagonal entry $i$ the number of samples that belong to the class
$({\bm{y}})_{i}$ of sample $i$.

######  Theorem 3.

Variance-covariance constrained VICReg (recall Theorem 2) with a linear
network ($K\leq D$) recovers LPP, and LDA (with ${\bm{G}}_{\rm s}$ from Eq. 13
and $K=C$). In both cases the optimal parameter ${\bm{W}}^{*}$ is given by the
top-$K$ eigenvectors of
$({\bm{X}}^{T}({\bm{D}}-{\bm{G}}){\bm{X}})^{-1}{\bm{X}}^{T}{\bm{G}}{\bm{X}}$
with ${\bm{G}}\mapsto{\bm{G}}_{\rm s}$ for LDA. (Proofs in Sections A.14 and
A.15.)

Interestingly, the eigenvalues associated to the eigenvectors of
${\bm{W}}^{*}$ exactly recover the multivariate analysis of variance (MANOVA)
sufficient statistics of the data (O’Brien and Kaiser, 1985; Huberty and
Olejnik, 2006). 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-fit of the model without requiring a downstream task (Mika et
al., 1999; Ioffe, 2006; Xue and Hall, 2014).

After a thorough analysis of VICReg we now propose to turn to another
important SSL loss which is SimCLR, and its variants.

##  4 SimCLR/NNCLR/MeanShift Solve a Generalized Multidimensional Scaling
Problem à la ISOMAP

Recall from Sections 2 and 3 that the SimCLR loss first computes a similarity
matrix $\widehat{{\bm{G}}}$ of some flavor that depends on the representation
${\bm{Z}}$, and then compares it against the known data relation ${\bm{G}}$.
Different ${\bm{G}}$ matrices lead to different variants of SimCLR (Chen et
al., 2020) such as NNCLR (Dwibedi et al., 2021) or MeanShift (Koohpayegani et
al., 2021), hence making our results general. The goal of this section is two-
fold. First, we demonstrate that different ${\bm{Z}}\mapsto\widehat{{\bm{G}}}$
mappings solve different optimization problems (Theorem 4) —all trying to
estimate the similarity matrix ${\bm{G}}$ from the signals ${\bm{Z}}$ akin to
Laplacian estimation in Graph Signal Processing. Second, we demonstrate that
SimCLR and its variants force ${\bm{Z}}$’s spectrum to align with the one of
${\bm{G}}$ (through $\widehat{{\bm{G}}}$) akin to the ISOMAP method, by means
of a Multi-Dimensional Scaling solution (Proposition 2).

Figure 7: Depiction of the regularization term $\mathcal{R}_{\rm log}$ (left)
and $\mathcal{R}_{\rm log}$ (right) from Eq. 15 for varying value of
$({\bm{W}})_{i,j}$ and three different temperatures $\tau\in\\{0.1,1,2\\}$
demonstrating how such regularization prevents $\widehat{{\bm{G}}}$ to
collapse to the trivial $0$ matrix in the optimization problem in Eq. 14.

###  4.1 Step 1: SimCLR Pairwise Similarities Solve a Graph Laplacian
Estimation Problem

Let’s first define the minimization problem that given a set of signals i.e.
rows of ${\bm{Z}}$ produces a relation estimate $\widehat{{\bm{G}}}$ of
${\bm{G}}$. To ease notations, we gather in the $N\times N$ matrix ${\bm{D}}$
all the pairwise distances
$({\bm{D}})_{i,j}=d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))$ with
$d$ any preferred metric. The standard problem of estimating
$\widehat{{\bm{G}}}$ from ${\bm{Z}}$ can be cast as an optimization problem
(Dong et al., 2016; Kalofolias, 2016) as

$\displaystyle\widehat{{\bm{G}}}_{d,\mathcal{R}}$
$\displaystyle=\operatorname*{arg\,min}_{{\bm{G}}\in\mathcal{G}}\sum_{i,j}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))({\bm{G}})_{i,j}+\mathcal{R}({\bm{G}})=\operatorname*{arg\,min}_{{\bm{G}}\in\mathcal{G}}\operatorname{Tr}({\bm{D}}{\bm{G}})+\mathcal{R}({\bm{G}}),$
(14)

with $\mathcal{G}$ the set (or subset) of symmetric matrices with nonnegative
entries and zero diagonal, and with $\mathcal{R}$ a regularizer preventing
$\widehat{{\bm{G}}}$ to be the trivial zero matrix e.g.

$\displaystyle\mathcal{R}_{\rm
log}({\bm{G}})=\sum_{i\not=j}\tau{\bm{G}}_{i,j}(\log({\bm{G}}_{i,j})-1)\;\;\text{
or }\;\;\mathcal{R}_{\rm
F}({\bm{G}})=\sum_{i\not=j}\tau{\bm{G}}_{i,j}({\bm{G}}_{i,j}-1).$ (15)

We provide in Fig. 7 a depiction of the impact of $\mathcal{R}({\bm{G}})$
which pushes the entries of the weight matrix to be close to $1$ with strength
depending on the temperature parameter $\tau$.

Hence $\widehat{{\bm{G}}}$ from Eq. 14 is the optimal graph —expressed as a
weight matrix— for which the signal ${\bm{Z}}=f_{\theta}({\bm{X}})$ on that
graph is smooth. For example on can solve Eq. 14 only on $\mathcal{G}_{\rm
rsto}$, the space of right-stochastic matrices i.e. a subset of $\mathcal{G}$
that only contains matrices whose rows sum to $1$ i.e. $\mathcal{G}_{\rm
rsto}=\\{{\bm{G}}\in\mathcal{G}:{\bm{G}}\mathbf{1}=\mathbf{1}\\}$. We now
propose the first formal result that ties the estimate $\widehat{{\bm{G}}}$
from Eq. 14 to the one of SimCLR/NNCLR/MeanShift whenever the regularizer
$\mathcal{R}$ is given by but with different spaces for ${\bm{G}}$.

######  Theorem 4.

Using $\mathcal{R}$ from Eq. 15 leads to the following graph weight estimate

$\displaystyle(\widehat{{\bm{G}}}_{d,\mathcal{R}_{\rm log}})_{i,j}$
$\displaystyle=e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}1_{\\{1\not=j\\}},$
(with $\mathcal{G}$) $\displaystyle(\widehat{{\bm{G}}}_{d,\mathcal{R}_{\rm
log}})_{i,j}$
$\displaystyle=\frac{e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}}{\sum_{j\not=i}e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}}1_{\\{1\not=j\\}},$
(with $\mathcal{G}_{\rm rsto}$) (16)

and thus if $d$ is the cosine distance, Eq. 16 recovers SimCLR similarity
estimate, and if $d$ is the $\ell_{2}$ distance, Eq. 16 recovers the Lifted
Structured Loss (Weinberger and Saul, 2009). (Proof in Section A.10.)

$({\bm{\Sigma}}_{Z})_{k,k}$ in log-scale

cosine+$\mathcal{R}_{\rm F}$

cosine+$\mathcal{R}_{\rm log}$

(SimCLR/NNCLR)

$\ell_{2}+\mathcal{R}_{\rm F}$

$\ell_{2}+\mathcal{R}_{\rm log}$

$k$

$k$

$k$

$k$

Figure 8: Depiction of the singular values ${\bm{\Sigma}}_{Z}$ of the
representation ${\bm{Z}}$ learned by the SimCLR/NNCLR loss with
$\mathcal{G}_{\rm rsto}$, varying
$\operatorname{rank}({\bm{G}})\in\\{8,16,32\\}$ (rows, green dotted lines) and
evolution during training (from blue to red, number in top-right corner) with
various ($d,\mathcal{R}$) configurations (columns, recall Theorem 4). We
observe that the rank of the learned representation matches exactly the one of
${\bm{G}}$ validating the result from Theorem 5 regardless of the chosen
hyper-parameters, making SimCLR’s performances more sensitive to the design of
${\bm{G}}$ than methods like VICReg whose representation preserves remains
full-rank (recall Fig. 5).

The above result plays a crucial role as it motivates the need to better
understand SSL from a theoretical perspective. Based on this maximization
principle, we can now obtain novel variations of SimCLR by solving Eq. 14 with
different constraints. For example one could obtain (derivations in Section
A.10) the following variations that are akin to the quantities used in Hadsell
et al. (2006); Weinberger and Saul (2009) i.e. with $d$ the $\ell_{2}$
distance and no exponentiation

$\displaystyle\widehat{{\bm{G}}}_{d,\mathcal{R}_{\rm F}}$
$\displaystyle=\operatorname{ReLU}\left(\mathbf{1}\mathbf{1}^{T}-{\bm{I}}-{\bm{D}}/\tau\right),$
$\displaystyle\text{(with $\mathcal{G},\tau>0$)},$ (17)
$\displaystyle\widehat{{\bm{G}}}_{d,\mathcal{R}_{\rm F}}$
$\displaystyle=\operatorname{ReLU}\left(\frac{1}{N-1}\left(\mathbf{1}\mathbf{1}^{T}-{\bm{I}}\right)-\frac{1}{\tau}{\bm{D}}\left({\bm{I}}-\frac{1}{N-1}\mathbf{1}\mathbf{1}^{T}\right)\right),$
$\displaystyle\text{(with $\mathcal{G}_{\rm rsto},\tau>0$)}.$ (18)

Now that we have demonstrated how SimCLR estimates the graph at hand, the next
section will focus on the second step: matching $\widehat{{\bm{G}}}$ to
${\bm{G}}$.

###  4.2 Step 2: SimCLR Fits the Estimated Graph $\widehat{{\bm{G}}}$ to the
Known Graph ${\bm{G}}$

SimCLR’s first step produced a graph estimate $\widehat{{\bm{G}}}$ from
${\bm{Z}}$. The second step now consists in measuring how fit is this estimate
compared to ${\bm{G}}$, so that the model’s parameters can be tuned to
increase this fitness. We demonstrate in this section that in doing so, SimCLR
forces ${\bm{Z}}$ to have the same nonzero left singular vectors as the
nonzero eigenvectors of ${\bm{G}}$, and that as opposed to VICReg, the rank
between ${\bm{Z}}$ and ${\bm{G}}$ matches.

The method used to compare $\widehat{{\bm{G}}}$ and ${\bm{G}}$ should reflect
the properties fulfilled by those matrices e.g. being doubly-stochastic or
right-stochastic and the type of measure one aims to impose. In all
generality, let’s denote the SimCLR comparison method to be one of the two
following variants (depending on the type of constraints put on
$\widehat{{\bm{G}}}$ and ${\bm{G}}$

$\displaystyle\mathcal{L}_{\rm
SimCLR}=\begin{cases}\|{\bm{G}}-\widehat{{\bm{G}}}({\bm{Z}})\|_{F}^{2},&\text{(Euclidean)}\\\
-\operatorname{Tr}\left(\left(\operatorname{diag}({\bm{G}}\mathbf{1})^{-1}{\bm{G}}\right)^{T}\log\left(\operatorname{diag}(\widehat{{\bm{G}}}({\bm{Z}})\mathbf{1})^{-1}\widehat{{\bm{G}}}({\bm{Z}})\right)\right),&\text{(Cross-
Entropy)}\end{cases},$ (19)

where the $\log$ is applied element-wise. When minimizing Eq. 19, SimCLR
learns an embedding ${\bm{Z}}$ so that its graph estimate $\widehat{{\bm{G}}}$
matches closely the known graph ${\bm{G}}$. To formalize below the form of the
optimal SimCLR representation, we first ought to recall that we denote by
${\bm{U}}_{G}$ and ${\bm{\Sigma}}_{G}$ the left singular vectors and singular
values of ${\bm{G}}$ respectively. Notice that since ${\bm{G}}$ is symmetric
semi-definite positive, ${\bm{U}}$ also corresponds to its eigenvectors and
${\bm{\Sigma}}_{G}^{2}$ to its eigenvalues.

######  Theorem 5.

A global minimizer of the SimCLR loss denoted by ${\bm{Z}}^{*}$ along with the
minimal achievable loss using Eq. 17 or Eq. 18, $\tau\geq\max_{i,j}(D)_{i,j}$
and with the LHS of Eq. 19 are given by

$\displaystyle{\bm{Z}}^{*}_{\tau}$
$\displaystyle=({\bm{U}}_{G}{\bm{\Sigma}}_{G}^{1/2})_{:,1:K}\;\;\text{ and
}\;\;\min_{{\bm{Z}}\in\mathbb{R}^{N\times K}}\mathcal{L}_{\rm
SimCLR}=\sum_{k=K+1}^{N}({\bm{\Sigma}}_{G}^{2})_{k,k},$

up to permutations of the singular vectors associated to the same singular
value, and regardless of the loss and graph estimation, the rank of
${\bm{Z}}^{*}_{\tau}$ is given by $\min(K,\operatorname{rank}({\bm{G}}))$.
(Proof in Section A.11.)

We illustrate the above theorem for many combinations of distances and
regularizers in Fig. 8 where we see that in all cases, SimCLR forces the
representations ${\bm{Z}}$ to have a dimensional collapse, a phenomenon first
observed in Hua et al. (2021) and that has been one of the unanswered
phenomenon in SSL (Arora et al., 2019; Tosh et al., 2021). In our goal to
unify SSL methods under the realm of spectral embedding methods, we now
propose the following section that ties SimCLR and its variants to global
spectral methods.

###  4.3 SimCLR is Akin to ISOMAP in Feature Space and Kernel ISOMAP in Input
Space

We now propose to tie the SimCLR method along with its variants e.g. NNCLR to
known global spectral methods, e.g. ISOMAP (Tenenbaum et al., 2000)
contrasting from VICReg which was tied to local spectral methods (recall
Sections 3.2 and 3.3).

In feature space. Let’s first recall that ISOMAP is a variation of Multi-
Dimensional Scaling (MDS) (Kruskal, 1964) also known as Principal Coordinates
Analysis. Classical MDS tries to learn embedding vectors that have similar
pairwise distance (usually $\ell_{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
$\min_{{\bm{Z}}}\|{\bm{G}}-{\bm{Z}}{\bm{Z}}^{T}\|_{F}^{2}$, where ${\bm{G}}$
is the Gram matrix of the inputs i.e. ${\bm{G}}={\bm{X}}{\bm{X}}^{T}$. At the
most general level, ISOMAP simply corresponds to solving that same
optimization problem but after redefining ${\bm{G}}$ to better capture the
geometric information of ${\bm{X}}$ e.g. using the shortest path distance of
the $k$-NN graph of ${\bm{X}}$ (Preparata and Shamos, 2012). The surprising
result that we formalize below is that SimCLR and in particular NNCLR recover
ISOMAP, the former by prescribing ${\bm{G}}$ given the known positive pairs,
and the latter by building a nearest neighbor graph.

######  Proposition 2.

Using the settings of Theorem 5, SimCLR recovers a Generalized MDS akin to
ISOMAP (and MDS iff ${\bm{G}}={\bm{X}}{\bm{X}}^{T}$). (Proof in Section A.12.)

In data space with DNs. From the above, we can extend Proposition 2 but in
input space, in a very similar way as was done in Section 3.2. In fact,
originating in Webb (1995), there was a search to extend MDS, and ISOMAP to an
input space formulation to solve the out-of-bag problem. In this setting, and
taking MDS as an example, the original similarity matrix
${\bm{Z}}{\bm{Z}}^{T}$ is replaced with $\Phi{\bm{W}}^{T}{\bm{W}}\Phi^{T}$
using the same notations as in Eq. 11 and already known relationship between
those models, we obtain the following.

######  Proposition 3 ((Williams, 2000)).

Whenever SimCLR recovers ISOMAP or MDS in feature space, it recovers kernel
ISOMAP or kernel PCA (Schölkopf et al., 1998) in input space.

We will now turn to BarlowTwins, another non-contrastive method akin to VICReg
(both of which fall back to LDA in the linear regime and with supervised
${\bm{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,
BarlowTwins will also fall back to a known spectral method in embedding space
(Section 5.1) 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 BarlowTwins Recovers Kernel Canonical Correlation Analysis

Recall from Sections 2 and 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 a known spectral method known
as Kernel Canonical Correlation Analysis.

There exists many different ways to formulate the CCA problem, we present one
here in the linear regime to simplify notations based on Cunningham and
Ghahramani (2015). The goal of (linear) CCA is to learn pairs of filters that
produce maximally correlated features as in

$\displaystyle\max_{{\bm{W}}_{\rm a}\in\mathbb{R}^{D_{\rm a}\times
K},{\bm{W}}_{\rm b}\in\mathbb{R}^{D_{\rm b}\times
K}}\frac{\operatorname{Tr}({\bm{W}}_{\rm a}^{T}{\bm{\Sigma}}_{ab}{\bm{W}}_{\rm
b})}{\sqrt{\operatorname{Tr}({\bm{W}}_{\rm
a}^{T}{\bm{\Sigma}}_{aa}{\bm{W}}_{\rm a})\operatorname{Tr}({\bm{W}}_{\rm
b}^{T}{\bm{\Sigma}}_{bb}{\bm{W}}_{\rm b})}},\text{ s.t.
}\begin{cases}\frac{1}{N}{\bm{W}}_{\rm a}^{T}{\bm{\Sigma}}_{aa}{\bm{W}}_{\rm
a}={\bm{I}}\\\ \frac{1}{N}{\bm{W}}_{\rm b}^{T}{\bm{\Sigma}}_{bb}{\bm{W}}_{\rm
b}={\bm{I}}\\\ {\bm{W}}_{\rm a}^{T}{\bm{\Sigma}}_{ab}{\bm{W}}_{\rm
b}={\bm{\Lambda}},\end{cases}$ (20)

with ${\bm{\Lambda}}$ a diagonal $(K\times K)$ matrix, and with
${\bm{\Sigma}}_{\rm aa}={\bm{X}}_{\rm a}^{T}{\bm{X}}_{\rm
a},{\bm{\Sigma}}_{\rm ab}={\bm{X}}_{\rm a}^{T}{\bm{X}}_{\rm b}$ and so on. We
thus observe that Eq. 20 is the BarlowTwins objective of Eq. 5 up to rescaling
of the weight matrices, as CCA aims to make ${\bm{W}}_{\rm
a}^{T}{\bm{\Sigma}}_{ab}{\bm{W}}_{\rm b}={\bm{W}}_{\rm a}^{T}{\bm{X}}_{\rm
a}^{T}{\bm{X}}_{\rm b}{\bm{W}}_{\rm b}={\bm{Z}}_{\rm a}^{T}{\bm{Z}}_{\rm
b}={\bm{\Lambda}}$ diagonal with maximal diagonal entries.

Going to the nonlinear regime i.e. kernel CCA follows directly be employing
$\phi({\bm{x}})$ embeddings of the input observations in-place of the inputs.
We thus obtain the following result that nicely parallels with the ones we
obtained for VICReg and SimCLR. In data space, BarlowTwins can be regarded
(put in perspective with Section 5.2) as a nonlinear canonical correlation
analysis (NLCA) (Dauxois and Nkiet, 1998) and in particular Kernel CCA (KCCA)
(Lai and Fyfe, 2000; Fukumizu et al., 2007) akin to how VICReg recovered
Kernel 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 as the
featurizer $\phi$ and produce a representation with rank
$\min(K,D,\operatorname{rank}({\bm{G}}))$. (Proof in Section A.13.).

In addition to the above, we can obtain further interpretation of the
components of BarlowTwins loss. For example, notice that Eq. 20 is only well-
defined if $K<\min(D_{\rm a},D_{\rm b})$. This limitation led to ridge-type
CCA regularization which as been introduced in Gretton et al. (2005) as a mean
to introduce numerical stability which in the context of linear CCA has been
introduced by Vinod (1976) under the name canonical ridge and recovers exactly
the addition of the $\epsilon$ constant in the denominator of the BarlowTwins
loss in Eq. 5.

$({\bm{\Sigma}}_{Z})_{k,k}$ in log-scale

$\operatorname{rank}({\bm{Z}}_{\rm init})=4$

$\operatorname{rank}({\bm{Z}}_{\rm init})=8$

$\operatorname{rank}({\bm{Z}}_{\rm init})=16$

$\operatorname{rank}({\bm{Z}}_{\rm init})=64$

$k$

$k$

$k$

$k$

Figure 9: Depiction of the singular values ${\bm{\Sigma}}_{Z}$ of the
representation ${\bm{Z}}$ learned by the BarlowTwins loss with ${\bm{Z}}_{\rm
a},{\bm{Z}}_{\rm b}$ formed from Eq. 6 given ${\bm{G}}$ with
$\operatorname{rank}({\bm{G}})\in\\{32,128\\}$ (rows, green dotted lines) and
with $N$=$512,K$=$128$ during training (from blue to red, number in top-right
corner) with various initialization of ${\bm{Z}}$ (columns). We observe that
the rank of the learned representation matches exactly the one of ${\bm{G}}$
validating the result from Theorem 6 regardless of the chosen hyper-
parameters, making BarlowTwins’s performances more sensitive to the design of
${\bm{G}}$ akin to SimCLR and opposite to VICReg whose representation
preserves full-rank (recall Fig. 5) when tuning the invariance parameter.

The above statement also brings yet another flavor of SSL methods. In fact,
where VICReg allows to control the rank of ${\bm{Z}}$ to be in-between $K$ and
$\operatorname{rank}({\bm{G}})$ through the loss hyper-parameters, BarlowTwins
and SimCLR enforce the rank of ${\bm{Z}}$ to be exactly the rank of
${\bm{G}}$. We depict in Fig. 9 the evolution of
$\operatorname{rank}({\bm{Z}})$ depending on the rank of the initialized
representation $\operatorname{rank}({\bm{Z}}_{\rm init})$ using a gradient
descent optimizer. We see that regardless of the initial rank of
${\bm{Z}}_{\rm init}$, training the representation to minimize the BarlowTwins
loss makes the representation dimension collapse. 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 (Kuss and Graepel, 2003), 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 BarlowTwins 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.2), we now obtain the
optimal weights for BarlowTwins in the linear regime. We can even provide
additional insights in this case since BarlowTwins is often seen as a key
method that allows the use of different parameters/architectures to process
${\bm{X}}_{\rm a}$ and ${\bm{X}}_{\rm b}$. We now show under what conditions
on ${\bm{G}}$ sharing parameters is sufficient by first demonstrating how
BarlowTwins recovers exactly CCA, and even LDA for supervised ${\bm{G}}$. To
streamline notations, we assume that our data is already centered, and thus
define the covariance and cross-covariance matrices as ${\bm{C}}_{\rm
aa}={\bm{X}}_{\rm a}^{T}{\bm{X}}_{\rm b},{\bm{C}}_{lr}={\bm{X}}^{T}_{\rm
a}{\bm{X}}_{\rm b}$ and so on.

######  Theorem 7.

In the linear regime BarlowTwins recovers CCA with optimal weights given by

$\displaystyle{\bm{W}}^{*}_{\rm a}=\text{ top-$K$ eigenvectors of
}\;\;{\bm{C}}_{\rm aa}^{-1}{\bm{C}}_{\rm ab}{\bm{C}}_{\rm
bb}^{-1}{\bm{C}}_{\rm ba}\text{ and }\;{\bm{W}}^{*}_{\rm b}={\bm{C}}_{\rm
bb}^{-1}{\bm{C}}_{\rm ba}{\bm{W}}^{*}_{\rm a},$

and (i) —with a symmetric ${\bm{G}}$ and same dimensional
${\bm{X}}_{a},{\bm{X}}_{b}$, weight-sharing naturally occurs— as the optimal
weights are ${\bm{W}}^{*}_{\rm a}={\bm{W}}^{*}_{\rm b}=\text{ top-$K$
eigenvectors of }\;\;{\bm{C}}_{\rm bb}^{-1}{\bm{C}}_{\rm ba}$ and (ii) if
${\bm{G}}$ is supervised and $K=C$ then BarlowTwins recovers LDA and thus
VICReg (recall Theorem 3). (Proof in Section A.16.)

⬇

1Caa = Xa.t() @ Xa + torch.eye(Da) * gamma #
${\bm{X}}_{a}\in\mathbb{R}^{N,D_{a}}$ regularized with gamma $(\gamma)$

2Cbb = Xb.t() @ Xb + torch.eye(Db) * gamma #
${\bm{X}}_{b}\in\mathbb{R}^{N,D_{b}}$ regularized with gamma $(\gamma)$

3RH = torch.block_diag(Caa, Cbb) # preparing the generalized eigenvalue prob.

4LH = torch.block_diag(Xa.t() @ Xb, Xb.t() @ Xa).roll(Da, 1)

5_, eigvecs = torch.lobpcg(LH, k=K, B=RH, niter=-1) # fast iterative solver

6Wa, Wb = eigvecs.split([Da, Db])

7Za = Xa @ Wa # ${\bm{Z}}_{\rm a}\in\mathbb{R}^{N,K}$

8Zb = Xb @ Wb # ${\bm{Z}}_{\rm b}\in\mathbb{R}^{N,K}$

The above result opens new venues to extend current SSL methods (BarlowTwins
in this case). For example, penalized matrix decomposition (PMD) from Witten
et al. (2009) formulates a novel sparse formulation of CCA. In our context,
this could lead to a new variation of BarlowTwins, in both the linear and
nonlinear regimes. With the above results, we now connected most SSL methods
to spectral methods, and found key properties that their
representations/parameters inherit.

We now move away from connecting SSL methods to spectral methods, and finding
the properties that their representations/parameters would inherit, to instead
exploit those results and understand how well those learned representations
can be to solve downstream tasks.

##  6 Optimality of Self-Supervised Methods to Solve Downstream Tasks

The goal of this section is to answer the following question: given a task
—encoded as a target matrix— ${\bm{Y}}\in\mathbb{R}^{N\times C}$, what are the
sufficient statistics of ${\bm{Y}}$ that a representation
${\bm{Z}}\in\mathbb{R}^{N\times K}$ must preserve to ensure that
$\min_{{\bm{W}},{\bm{b}}}\|{\bm{Y}}-{\bm{Z}}{\bm{W}}-{\bm{b}}\|_{F}^{2}=0$.
The first Section 6.1 will derive the optimal linear parameters (possibly non-
unique) that minimize that loss, and will highlight the spectral properties of
${\bm{Y}}$ that must be consistent in ${\bm{Z}}$. From that, Section 6.2 will
be able to provide necessary and sufficient conditions for ${\bm{Z}}$ to be
optimal —in term of its left-singular vectors— and finally, Section 6.3
extends the recent studies of Bao et al. (2021a); HaoChen et al. (2021, 2022)
to multiple SSL methods by demonstrating how and when SSL representations are
optimal for downstream tasks.

###  6.1 Characterizing a Representation Usefulness by its Ability to Linearly
Solve a Task

The goal of this section is to characterize the (possibly non-unique)
parameter ${\bm{W}}$ of the linear transformation that given any target matrix
${\bm{Y}}$ and representation ${\bm{Z}}$ minimize the Mean-Squared Error
(MSE). Results in this section are standard in the linear algebra literature
e.g. see Golub and Reinsch (1971) but we include it for completeness. We
should also highlight that although for classification the cross-entropy loss
is more common, it has recently been showed that $\ell_{2}$ could perform as
well (Hui and Belkin, 2020) with the correct parameter tuning, even on large
models e.g. on the Imagenet dataset with modern deep learning architectures.
Hence, we will leverage that loss function throughout this section.

Hence we consider that we are given representations ${\bm{z}}\triangleq
f({\bm{x}})$ from an input sample ${\bm{x}}$. Hence, we will denote the
dataset representation as
${\bm{Z}}=[f({\bm{x}}_{1}),\dots,f({\bm{x}}_{N})]^{T}\in\mathbb{R}^{N\times
K}$ given a dataset
${\mathbb{X}}\triangleq\\{{\bm{x}}_{1},\dots,{\bm{x}}_{N}\\},N\in\mathbb{N}^{*}$.
We are also given a task —encoded as a target matrix—
${\bm{Y}}\triangleq[{\bm{y}}_{1},\dots,{\bm{y}}_{N}]^{T}\in\mathbb{R}^{N\times
C}$ where each ${\bm{y}}_{n}$ is associated to each input ${\bm{x}}_{n}$.

Without loss of generality and to lighten our derivations, we will omit the
bias vector ${\bm{b}}$, it can be learned as part of ${\bm{W}}$ by adding $1$
to the features of ${\bm{z}}_{n}$. Our loss function thus takes the following
form $\mathcal{L}({\bm{W}})=\frac{1}{2}\|{\bm{Y}}-{\bm{Z}}{\bm{W}}\|_{F}^{2}$.
To minimize this loss function, we will first find what matrices ${\bm{W}}$
make the gradient of $\mathcal{L}$ with respect to ${\bm{W}}$ vanish. Hence,
we need to find ${\bm{W}}\in\mathbb{R}^{K\times C}$ such that

$\displaystyle\nabla_{{\bm{W}}}\mathcal{L}=$
$\displaystyle\mathbf{0}\iff-{\bm{Z}}^{T}({\bm{Y}}-{\bm{Z}}{\bm{W}})=\mathbf{0}\iff{\bm{Z}}^{T}{\bm{Y}}={\bm{Z}}^{T}{\bm{Z}}{\bm{W}}.$

If we assumed ${\bm{Z}}$ to be full rank, we would directly recover the usual
least square solution
${\bm{W}}^{*}=({\bm{Z}}^{T}{\bm{Z}})^{-1}{\bm{Z}}^{T}{\bm{Y}}$. However, we
would like to (i) avoid any assumption on the spectrum of ${\bm{Z}}$, and (ii)
avoid the use of any standard regularizer such as Tikhonov that is commonly
used to recover a unique solution to an ill-posed optimization problem. In
fact, our goal is to find the (possibly non-unique) family of parameters
${\bm{W}}^{*}$ that fulfill $\nabla_{{\bm{W}}}\mathcal{L}=\mathbf{0}$
regardless of the properties of ${\bm{Z}}$ and ${\bm{Y}}$. To that end, we
first start by using the SVD of ${\bm{Z}}=U_{z}{\bm{\Sigma}}_{z}V_{z}^{\top}$
—which always exists— to reformulate the above equality (see derivations in
Sections A.2 and A.3) into

$\displaystyle{\bm{Z}}^{T}{\bm{Y}}={\bm{Z}}^{T}{\bm{Z}}{\bm{W}}\iff$
$\displaystyle{\bm{W}}\in\left\\{({\bm{V}}_{z}{\bm{\Sigma}}^{-1}_{z}{\bm{U}}_{z}^{T}+\overline{{\bm{V}}}_{z}{\bm{M}}){\bm{Y}}:{\bm{M}}\in\mathbb{R}^{K\times
C}\right\\},$ (21)

with $\overline{{\bm{V}}}_{z}$ the $K\times(K-\operatorname{rank}({\bm{Z}}))$
matrix that horizontally stacks the right singular vectors of ${\bm{Z}}$ which
have their corresponding singular value $0$, with the special case that
${\bm{M}}=\mathbf{0}\iff\operatorname{rank}({\bm{Z}})=K$. We also slightly
abuse notations and define ${\bm{\Sigma}}^{-1}_{z}$ to be the $K\times N$
matrix which is zero for all off-diagonal elements, and with

$({\bm{\Sigma}}^{-1}_{z})_{i,j}\triangleq\begin{cases}\frac{1}{(\sigma_{z})_{i}}\iff
i=j\wedge(\sigma_{z})_{i}>0\\\ 0\text{ otherwise}\end{cases},$

hence ${\bm{\Sigma}}^{-1}_{z}{\bm{\Sigma}}_{z}$ is a $K\times K$ matrix which
is identity iff ${\bm{X}}$ is full rank, and is otherwise filled with
$K-\operatorname{rank}({\bm{X}})$ zeros and $\operatorname{rank}({\bm{X}})$
ones in the diagonal. On the other hand,
${\bm{\Sigma}}_{z}{\bm{\Sigma}}^{-1}_{z}$ is a diagonal $N\times N$ matrix
with $N-\operatorname{rank}({\bm{X}})$ zeros and
$\operatorname{rank}({\bm{X}})$ ones in the diagonal. Note that in the special
case where ${\bm{X}}$ is full-rank, $\overline{{\bm{V}}}$ is null (we slightly
abuse notations) and
${\bm{V}}_{z}{\bm{\Sigma}}^{-1}_{z}{\bm{U}}_{z}^{T}=({\bm{Z}}^{T}{\bm{Z}})^{-1}{\bm{Z}}^{T}$
recovering the standard least-square solution.

###  6.2 Necessary and Sufficient Conditions for Optimality of a
Representation

Given a target matrix ${\bm{Y}}$ and its SVD
${\bm{U}}_{y}{\bm{\Sigma}}_{y}{\bm{V}}^{T}_{y}$, we obtain the following
formal statement that demonstrates how the left-singular vectors of ${\bm{Y}}$
must related to the left-singular vectors of ${\bm{Z}}$ to allow for
$\min_{{\bm{W}}}\mathcal{L}({\bm{W}})$ to be $0$. This statement plays a
crucial role in our study as it answers the question what property ${\bm{Z}}$
must fulfill —regardless on how it was produced— to guarantee that $0$
training error is achievable on the considered task?

######  Theorem 8 (Necessary and sufficient condition).

Given a task ${\bm{Y}}\in\mathbb{R}^{N\times C}$ and a representation
${\bm{Z}}\in\mathbb{R}^{N\times K}$ —with left-singular vectors associated to
nonzero singular values denoted as $\widehat{{\bm{U}}}_{z}$— the minimum
linear loss is given by

$\displaystyle\min_{{\bm{W}}\in\mathbb{R}^{K\times
C}}\mathcal{L}({\bm{W}})=\frac{1}{2}\|{\bm{Y}}\|_{F}^{2}-\frac{1}{2}\|\widehat{{\bm{U}}}_{z}^{T}{\bm{U}}_{y}{\bm{\Sigma}}_{y}\|_{F}^{2},$
(22)

which is $0$ iff the columns of $\widehat{{\bm{U}}}_{z}$ spans the columns of
$\widehat{{\bm{U}}}_{y}$. (Proof in Section A.4.)

Figure 10: Depiction of typical target matrices ${\bm{Y}}$ and their
corresponding left singular vectors. Note that in this case all the nonzero
singular values are identical, but with class-imbalance the singular values
would be proportional to the class proportions. Hence it is clear that
approximating the left singular vectors of ${\bm{Y}}$ via SSL training (recall
Theorem 9) the learned representations will exhibit per-class clustering —as
long as the left-singular vectors of ${\bm{G}}$ correctly encode the task.

The proof consists in using the solution ${\bm{W}}$ from the set in Eq. 21,
and after a few algebraic manipulations, Theorem 9 result is obtained. From
that result alone we already obtain an interesting requirement on ${\bm{Z}}$,
namely that its top-$K$ left singular vectors must be the same —up to a
rotation— to the top-$K$ left singular of ${\bm{Y}}$. Theorem 9 also provides
us with a direct necessary condition but not sufficient condition for
optimality.

Understanding the inter-play between $\operatorname{rank}({\bm{Z}})$,
${\bm{U}}_{z}$ and ${\bm{U}}_{y}$ will play a crucial role in the next section
where we propose to study self-supervised learning criterion, and their
ability to produce optimal representations.

###  6.3 Contrastive and Non-Contrastive Learning can all be Optimal

We now demonstrate in this section that any representation ${\bm{Z}}$ learned
by any of the SSL method (VICReg, BarlowTwins, SimCLR) can be optimal for a
downstream task, as long as the data geometry encoded in ${\bm{G}}$ follows
the left-singular vectors of ${\bm{Y}}$, the target matrix which embodies the
considered downstream task.

######  Theorem 9.

Given a dataset ${\bm{X}}$ and relation matrix ${\bm{G}}$, minimizing the
VICReg -or- SimCLR -or- BarlowTwins loss produces a representation that is
optimal for a task ${\bm{Y}}={\bm{U}}_{y}{\bm{\Sigma}}_{y}{\bm{V}}_{y}^{T}$
iff the columns of $\widehat{{\bm{U}}}_{y}$ are in the span of
$\widehat{{\bm{U}}}_{g}$ as in

$\displaystyle\min_{{\bm{W}}\in\mathbb{R}^{K\times
C}}\|{\bm{Y}}-{\bm{Z}}^{*}{\bm{W}}\|_{F}^{2}=0\iff\widehat{{\bm{U}}}_{y}\in\operatorname{span}(\widehat{{\bm{U}}}_{g}),$

with ${\bm{Z}}^{*}$ the embeddings of the VICReg -or- SimCLR -or- BarlowTwins
model after convergence. (Proof in Section A.17.)

Although not explicitly stated in Theorem 9 the same applies e.g. to NNCLR and
MeanShift as they employ the same SimCLR loss, only the design of ${\bm{G}}$
is altered. The above is crucial in helping and guiding the design of SSL
methods and theoretically confirm the empirical findings from Geirhos et al.
(2020) that observed in different scenarios that SSL and supervised models
nearly fall back to the same thing.

###  6.4 Non-Contrastive Methods Should be Preferred: Best and Worst
Downstream Task Error Bounds

We demonstrated in Section 6.3 that all SSL methods can be optimal to solve a
task at ahdn as long as the spectral properties of ${\bm{G}}$ and ${\bm{Y}}$
are aligned. However, this is rarely the case in practical scenarios, and it
thus becomes crucial to understand the behavior of the learned representation
${\bm{Z}}$ on downstream task and if it varies with different SSL methods.
First, we propose the following bound which represent the best and worst case
downstream performances as a function of the rank of ${\bm{G}}$ which is
mostly a result of applying the Eckart-Young-Mirsky theorem. That is, we look
at all the possible similarity matrices ${\bm{G}}$ of rank $R$ and see, given
a task ${\bm{Y}}$ what is the best achievable performance if ${\bm{G}}$
correctly encoders the data geometry, and what is the worse possible
performance if ${\bm{G}}$ is “orthogonal” to the correct data geometry. For
clarity and without loss of generality we assume here that
$\operatorname{rank}({\bm{Y}})\leq K$ as otherwise no method would produce an
optimal representation in general and $K<N$ as otherwise we are in the kernel
regime.

######  Theorem 10.

Given fixed inputs ${\bm{X}}$ the lower and upper-bound over all possible
matrices ${\bm{G}}$ of rank $R$ of the downstream task training performances
(with fixed ${\bm{Y}}$) are given by

$\displaystyle\sum_{i=R}^{K}({\bm{\Sigma}}_{y}^{2})_{i,i}\leq\left(\min_{{\bm{W}}\in\mathbb{R}^{K\times
C}}\mathcal{L}({\bm{W}},{\bm{Z}}^{*}_{\rm
SimCLR}({\bm{G}}))-\min_{{\bm{W}}\in\mathbb{R}^{K\times
C}}\mathcal{L}({\bm{W}},{\bm{Z}}^{*}_{\rm
VICReg}({\bm{G}}))\right)\leq\|{\bm{Y}}\|_{F}^{2},$

and are tight. Hence one should prefer VICReg, then BarlowTwins and finally
SimCLR to maximize the downstream task performances.

The above result is a direct consequence of SimCLR forcing the representation
to have the same rank as ${\bm{G}}$ while VICReg always enforce a full-rank
representation. And although this difference becomes irrelevant with correct
${\bm{G}}$ (recall Section 6.3) it becomes an important distinctive attribute
between SSL methods when ${\bm{G}}$ is not optimal, which concerns most
practical scenarios.

##  7 Conclusions

We provided in this study a unifying analysis of the major self-supervised
learning methods covering VICReg (Section 3), SimCLR (Section 4) and
BarlowTwins (Section 5). In doing so, we were able to not only tie each of
those methods and their variants to common spectral embedding techniques, but
we were also able to find the commonalities between all those methods. Among
the many insights that we obtained, the most crucial one is that whenever the
similarity matrix ${\bm{G}}$ is correctly defined with respect to a downstream
task, any of those methods will produce an ideal representation that will
perfectly solve the task at hand. In short, there is no benefit of one method
versus any other. In the more realistic regime where ${\bm{G}}$ might be
misaligned with the downstream task, VICReg with lower invariance
regularization hyper-parameter should be preferred. In that regime, the
representation will include all the information from ${\bm{G}}$ while
preserving full-rank and thus allowing for the representation to be usable for
other downstream task that are not encoded within ${\bm{G}}$. This is in
contrast with BarlowTwins and SimCLR that collapse the representation to embed
all information about ${\bm{G}}$ and nothing else.

At a more general level, we were able to parallel the contrastive versus non-
contrastive dichotomy in SSL to the global versus local methods in spectral
methods respectively. This led to further highlights into the strengths and
weakness of each. For example, global approaches (contrastive SSL) tend to
give a more faithful representation of the data’s global structure as the
embedding aims to be metric-preserving. On the other hand, the local
approaches (non-contrastive) provide useful embedding on a broader range of
manifolds, whose local geometry is close to Euclidean, but whose global
geometry may not be (Silva and Tenenbaum, 2002).

Beyond those results, we hope that the ties provided in this paper will stem a
plurality of future work. One example would be to leverage the connection
between SSL methods and spectral embedding methods to port existing results
and techniques from one field to the other. In fact, such spectral methods
have fallen short when dealing with high-dimensional datasets such as
Imagenet. However, SSL methods have risen to become state-of-the-art on those
datasets. The only difference between those lies in how ${\bm{G}}$ is
constructed.

## Acknowledgements

We thank Prof. Pascal Vincent and Prof. Surya Ganguli for providing key
discussions, insights and related work references that played a key role in
making this study as complete and self-contained as possible.

## References

  * Aronszajn (1950) Nachman Aronszajn.  Theory of reproducing kernels.  _Transactions of the American mathematical society_ , 68(3):337–404, 1950.
  * Arora et al. (2019) Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi.  A theoretical analysis of contrastive unsupervised representation learning.  _arXiv preprint arXiv:1902.09229_ , 2019.
  * Baevski et al. (2020) Alexei Baevski, Yuhao Zhou, Abdelrahman Mohamed, and Michael Auli.  wav2vec 2.0: A framework for self-supervised learning of speech representations.  _Advances in Neural Information Processing Systems_ , 33:12449–12460, 2020.
  * Bao et al. (2021a) Han Bao, Yoshihiro Nagano, and Kento Nozawa.  Sharp learning bounds for contrastive unsupervised representation learning.  _arXiv preprint arXiv:2110.02501_ , 2021a.
  * Bao et al. (2021b) Hangbo Bao, Li Dong, and Furu Wei.  Beit: Bert pre-training of image transformers.  _arXiv preprint arXiv:2106.08254_ , 2021b.
  * Bardes et al. (2021) Adrien Bardes, Jean Ponce, and Yann LeCun.  Vicreg: Variance-invariance-covariance regularization for self-supervised learning.  _arXiv preprint arXiv:2105.04906_ , 2021.
  * Bartlett (1938) Maurice S Bartlett.  Further aspects of the theory of multiple regression.  In _Mathematical Proceedings of the Cambridge Philosophical Society_ , volume 34, pages 33–40. Cambridge University Press, 1938.
  * Belkin and Niyogi (2003) Mikhail Belkin and Partha Niyogi.  Laplacian eigenmaps for dimensionality reduction and data representation.  _Neural computation_ , 15(6):1373–1396, 2003\.
  * Bengio et al. (2003) Yoshua Bengio, Jean-françcois Paiement, Pascal Vincent, Olivier Delalleau, Nicolas Roux, and Marie Ouimet.  Out-of-sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering.  _Advances in neural information processing systems_ , 16, 2003.
  * Bordes et al. (2021) Florian Bordes, Randall Balestriero, and Pascal Vincent.  High fidelity visualization of what your self-supervised representation knows about.  _arXiv preprint arXiv:2112.09164_ , 2021.
  * Brockett (1991) Roger W Brockett.  Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems.  _Linear Algebra and its applications_ , 146:79–91, 1991\.
  * Bromley et al. (1993) 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.
  * Broomhead and Lowe (1988) David S Broomhead and David Lowe.  Radial basis functions, multi-variable functional interpolation and adaptive networks.  Technical report, Royal Signals and Radar Establishment Malvern (United Kingdom), 1988.
  * Caron et al. (2021) Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 9650–9660, 2021.
  * Chen et al. (2020) 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.
  * Cheng et al. (2005) Jian Cheng, Qingshan Liu, Hanqing Lu, and Yen-Wei Chen.  Supervised kernel locality preserving projections for face recognition.  _Neurocomputing_ , 67:443–449, 2005.
  * Cohen et al. (2014) Patricia Cohen, Stephen G West, and Leona S Aiken.  _Applied multiple regression/correlation analysis for the behavioral sciences_.  Psychology press, 2014.
  * Cunningham and Ghahramani (2015) John P Cunningham and Zoubin Ghahramani.  Linear dimensionality reduction: Survey, insights, and generalizations.  _The Journal of Machine Learning Research_ , 16(1):2859–2900, 2015.
  * Dauxois and Nkiet (1998) Jacques Dauxois and Guy Martial Nkiet.  Nonlinear canonical analysis and independence tests.  _The Annals of Statistics_ , 26(4):1254–1278, 1998.
  * Dong et al. (2016) 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–6173, 2016.
  * Dwibedi et al. (2021) Debidatta Dwibedi, Yusuf Aytar, Jonathan Tompson, Pierre Sermanet, and Andrew Zisserman.  With a little help from my friends: Nearest-neighbor contrastive learning of visual representations.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 9588–9597, 2021.
  * Eckart and Young (1936) Carl Eckart and Gale Young.  The approximation of one matrix by another of lower rank.  _Psychometrika_ , 1(3):211–218, 1936.
  * Ericsson et al. (2021) Linus Ericsson, Henry Gouk, and Timothy M Hospedales.  How well do self-supervised models transfer?  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5414–5423, 2021.
  * Ewerbring and Luk (1989) L Magnus Ewerbring and Franklin T Luk.  Canonical correlations and generalized svd: applications and new algorithms.  _Journal of computational and applied mathematics_ , 27(1-2):37–52, 1989.
  * Fisher (1936) Ronald A Fisher.  The use of multiple measurements in taxonomic problems.  _Annals of eugenics_ , 7(2):179–188, 1936.
  * Fukumizu et al. (2007) Kenji Fukumizu, Francis R Bach, and Arthur Gretton.  Statistical consistency of kernel canonical correlation analysis.  _Journal of Machine Learning Research_ , 8(2), 2007.
  * Ganea et al. (2019) Octavian Ganea, Sylvain Gelly, Gary Bécigneul, and Aliaksei Severyn.  Breaking the softmax bottleneck via learnable monotonic pointwise non-linearities.  In _International Conference on Machine Learning_ , pages 2073–2082. PMLR, 2019.
  * Geirhos et al. (2020) Robert Geirhos, Kantharaju Narayanappa, Benjamin Mitzkus, Matthias Bethge, Felix A Wichmann, and Wieland Brendel.  On the surprising similarities between supervised and self-supervised models.  _arXiv preprint arXiv:2010.08377_ , 2020.
  * Gidaris et al. (2018) Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  _arXiv preprint arXiv:1803.07728_ , 2018.
  * Golub and Reinsch (1971) Gene H Golub and Christian Reinsch.  Singular value decomposition and least squares solutions.  In _Linear algebra_ , pages 134–151. Springer, 1971.
  * Goyal et al. (2019) 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 on computer vision_ , pages 6391–6400, 2019.
  * Gretton et al. (2005) Arthur Gretton, Ralf Herbrich, Alexander Smola, Olivier Bousquet, Bernhard Schölkopf, et al.  Kernel methods for measuring independence.  2005\.
  * Guo et al. (2003) 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.  _Pattern Recognition Letters_ , 24(1-3):147–158, 2003.
  * Hadsell et al. (2006) Raia Hadsell, Sumit Chopra, and Yann LeCun.  Dimensionality reduction by learning an invariant mapping.  In _2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06)_ , volume 2, pages 1735–1742. IEEE, 2006.
  * HaoChen et al. (2021) 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.
  * HaoChen et al. (2022) Jeff Z HaoChen, Colin Wei, Ananya Kumar, and Tengyu Ma.  Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations.  _arXiv preprint arXiv:2204.02683_ , 2022.
  * Hardoon et al. (2004) David R Hardoon, Sandor Szedmak, and John Shawe-Taylor.  Canonical correlation analysis: An overview with application to learning methods.  _Neural computation_ , 16(12):2639–2664, 2004\.
  * Hastie et al. (1995) Trevor Hastie, Andreas Buja, and Robert Tibshirani.  Penalized discriminant analysis.  _The Annals of Statistics_ , 23(1):73–102, 1995\.
  * Hautamaki et al. (2004) 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 430–433. IEEE, 2004.
  * He et al. (2021) Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  _arXiv preprint arXiv:2111.06377_ , 2021.
  * He and Niyogi (2003) Xiaofei He and Partha Niyogi.  Locality preserving projections.  _Advances in neural information processing systems_ , 16, 2003.
  * Healy (1957) MJR Healy.  A rotation method for computing canonical correlations.  _Mathematics of Computation_ , 11(58):83–86, 1957\.
  * Hestenes (1958) Magnus R Hestenes.  Inversion of matrices by biorthogonalization and related results.  _Journal of the Society for Industrial and Applied Mathematics_ , 6(1):51–90, 1958.
  * Higham (1988) Nicholas J Higham.  Computing a nearest symmetric positive semidefinite matrix.  _Linear algebra and its applications_ , 103:103–118, 1988\.
  * Hirsch (1983) Jorge E Hirsch.  Discrete hubbard-stratonovich transformation for fermion lattice models.  _Physical Review B_ , 28(7):4059, 1983.
  * Horn and Johnson (2012) Roger A Horn and Charles R Johnson.  _Matrix analysis_.  Cambridge university press, 2012.
  * Hua et al. (2021) 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 on Computer Vision_ , pages 9598–9608, 2021.
  * Huberty and Olejnik (2006) Carl J Huberty and Stephen Olejnik.  _Applied MANOVA and discriminant analysis_.  John Wiley & Sons, 2006.
  * Hui and Belkin (2020) Like Hui and Mikhail Belkin.  Evaluation of neural architectures trained with square loss vs cross-entropy in classification tasks, 2020.  URL https://arxiv.org/abs/2006.07322.
  * Ioffe (2006) Sergey Ioffe.  Probabilistic linear discriminant analysis.  In _European Conference on Computer Vision_ , pages 531–542. Springer, 2006.
  * Jing et al. (2021) Li Jing, Pascal Vincent, Yann LeCun, and Yuandong Tian.  Understanding dimensional collapse in contrastive self-supervised learning.  _arXiv preprint arXiv:2110.09348_ , 2021.
  * Kalofolias (2016) Vassilis Kalofolias.  How to learn a graph from smooth signals.  In _Artificial Intelligence and Statistics_ , pages 920–929. PMLR, 2016.
  * Kanazawa et al. (2016) 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 Pattern Recognition_ , pages 3253–3261, 2016.
  * Kim et al. (2019) 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 8545–8552, 2019.
  * Knaf (2007) H Knaf.  Kernel fisher discriminant functions–a concise and rigorous introduction.  2007\.
  * Knyazev (1987) Andrew V Knyazev.  Convergence rate estimates for iterative methods for a mesh symmetrie eigenvalue problem.  1987\.
  * Kokiopoulou et al. (2011) 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.
  * Koohpayegani et al. (2021) Soroush Abbasi Koohpayegani, Ajinkya Tejankar, and Hamed Pirsiavash.  Mean shift for self-supervised learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10326–10335, 2021.
  * Kruskal (1964) Joseph B Kruskal.  Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis.  _Psychometrika_ , 29(1):1–27, 1964.
  * Kursun et al. (2011) Olcay Kursun, Ethem Alpaydin, and Oleg V Favorov.  Canonical correlation analysis using within-class coupling.  _Pattern Recognition Letters_ , 32(2):134–144, 2011.
  * Kuss and Graepel (2003) Malte Kuss and Thore Graepel.  The geometry of kernel canonical correlation analysis.  2003\.
  * Lai and Fyfe (2000) Pei Ling Lai and Colin Fyfe.  Kernel and nonlinear canonical correlation analysis.  _International Journal of Neural Systems_ , 10(05):365–377, 2000.
  * Li and Wang (2014) Cheng Li and Bingyu Wang.  Fisher linear discriminant analysis.  _CCIS Northeastern University_ , 2014.
  * Liang et al. (2013) Xin Liang, Ren-Cang Li, and Zhaojun Bai.  Trace minimization principles for positive semi-definite pencils.  _Linear Algebra and its Applications_ , 438(7):3085–3106, 2013.
  * Liang et al. (2021) Xin Liang, Li Wang, Lei-Hong Zhang, and Ren-Cang Li.  On generalizing trace minimization.  _arXiv preprint arXiv:2104.00257_ , 2021.
  * Mika et al. (1999) Sebastian Mika, Gunnar Ratsch, Jason Weston, Bernhard Scholkopf, and Klaus-Robert Mullers.  Fisher discriminant analysis with kernels.  In _Neural networks for signal processing IX: Proceedings of the 1999 IEEE signal processing society workshop (cat. no. 98th8468)_ , pages 41–48. Ieee, 1999.
  * Misra and Maaten (2020) Ishan Misra and Laurens van der Maaten.  Self-supervised learning of pretext-invariant representations.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6707–6717, 2020.
  * Nazi et al. (2019) Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, and Azalia Mirhoseini.  Generalized clustering by learning to optimize expected normalized cuts.  _arXiv preprint arXiv:1910.07623_ , 2019.
  * Novotny et al. (2018) 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.
  * O’Brien and Kaiser (1985) Ralph G O’Brien and Mary K Kaiser.  Manova method for analyzing repeated measures designs: an extensive primer.  _Psychological bulletin_ , 97(2):316, 1985.
  * Pfau et al. (2019) David Pfau, Stig Petersen, Ashish Agarwal, David G. T. Barrett, and Kimberly L. Stachenfeld.  Spectral inference networks: Unifying deep and spectral learning.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=SJzqpj09YQ.
  * Pokle et al. (2022) Ashwini Pokle, Jinjin Tian, Yuchen Li, and Andrej Risteski.  Contrasting the landscape of contrastive and non-contrastive learning.  _arXiv preprint arXiv:2203.15702_ , 2022.
  * Preparata and Shamos (2012) Franco P Preparata and Michael I Shamos.  _Computational geometry: an introduction_.  Springer Science & Business Media, 2012.
  * Qiu et al. (2018) Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang.  Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec.  In _Proceedings of the eleventh ACM international conference on web search and data mining_ , pages 459–467, 2018.
  * Roweis and Saul (2000) Sam T Roweis and Lawrence K Saul.  Nonlinear dimensionality reduction by locally linear embedding.  _science_ , 290(5500):2323–2326, 2000.
  * Schölkopf et al. (1998) Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller.  Nonlinear component analysis as a kernel eigenvalue problem.  _Neural computation_ , 10(5):1299–1319, 1998\.
  * Sermanet et al. (2018) 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.
  * Shi et al. (2020) Haizhou Shi, Dongliang Luo, Siliang Tang, Jian Wang, and Yueting Zhuang.  Run away from your teacher: Understanding byol by a novel self-supervised approach.  _arXiv preprint arXiv:2011.10944_ , 2020.
  * Silva and Tenenbaum (2002) Vin Silva and Joshua Tenenbaum.  Global versus local methods in nonlinear dimensionality reduction.  _Advances in neural information processing systems_ , 15, 2002.
  * Specht et al. (1991) Donald F Specht et al.  A general regression neural network.  _IEEE transactions on neural networks_ , 2(6):568–576, 1991.
  * Sprekeler (2011) Henning Sprekeler.  On the relation of slow feature analysis and laplacian eigenmaps.  _Neural computation_ , 23(12):3287–3302, 2011\.
  * Tai et al. (2022) Mariko Tai, Mineichi Kudo, Akira Tanaka, Hideyuki Imai, and Keigo Kimura.  Kernelized supervised laplacian eigenmap for visualization and classification of multi-label data.  _Pattern Recognition_ , 123:108399, 2022.
  * Tenenbaum et al. (2000) Joshua B Tenenbaum, Vin de Silva, and John C Langford.  A global geometric framework for nonlinear dimensionality reduction.  _science_ , 290(5500):2319–2323, 2000.
  * Tian (2022) Yuandong Tian.  Deep contrastive learning is provably (almost) principal component analysis.  _arXiv preprint arXiv:2201.12680_ , 2022.
  * Tian et al. (2021) Yuandong Tian, Xinlei Chen, and Surya Ganguli.  Understanding self-supervised learning dynamics without contrastive pairs.  In _International Conference on Machine Learning_ , pages 10268–10278. PMLR, 2021.
  * Tosh et al. (2021) Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu.  Contrastive learning, multi-view redundancy, and linear models.  In _Algorithmic Learning Theory_ , pages 1179–1206. PMLR, 2021.
  * Uurtio et al. (2017) Viivi Uurtio, João M Monteiro, Jaz Kandola, John Shawe-Taylor, Delmiro Fernandez-Reyes, and Juho Rousu.  A tutorial on canonical correlation methods.  _ACM Computing Surveys (CSUR)_ , 50(6):1–33, 2017\.
  * Vinod (1976) Hrishikesh D Vinod.  Canonical ridge and econometrics of joint production.  _Journal of econometrics_ , 4(2):147–166, 1976\.
  * Von Luxburg (2007) Ulrike Von Luxburg.  A tutorial on spectral clustering.  _Statistics and computing_ , 17(4):395–416, 2007\.
  * Wang et al. (2007) Huan Wang, Shuicheng Yan, Dong Xu, Xiaoou Tang, and Thomas Huang.  Trace ratio vs. ratio trace for dimensionality reduction.  In _2007 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 1–8. IEEE, 2007.
  * Wang and Isola (2020) Tongzhou Wang and Phillip Isola.  Understanding contrastive representation learning through alignment and uniformity on the hypersphere.  In _International Conference on Machine Learning_ , pages 9929–9939. PMLR, 2020.
  * Wang et al. (2021) Xiang Wang, Xinlei Chen, Simon S Du, and Yuandong Tian.  Towards demystifying representation learning with non-contrastive self-supervision.  _arXiv preprint arXiv:2110.04947_ , 2021.
  * Wathen and Zhu (2015) Andrew J Wathen and Shengxin Zhu.  On spectral distribution of kernel matrices related to radial basis functions.  _Numerical Algorithms_ , 70(4):709–726, 2015\.
  * Webb (1995) Andrew R Webb.  Multidimensional scaling by iterative majorization using radial basis functions.  _Pattern Recognition_ , 28(5):753–759, 1995.
  * Webb (2003) Andrew R Webb.  _Statistical pattern recognition_.  John Wiley & Sons, 2003.
  * Weinberger and Saul (2009) Kilian Q Weinberger and Lawrence K Saul.  Distance metric learning for large margin nearest neighbor classification.  _Journal of machine learning research_ , 10(2), 2009.
  * Wen and Li (2021) 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.
  * Williams (2000) Christopher Williams.  On a connection between kernel pca and metric multidimensional scaling.  _Advances in neural information processing systems_ , 13, 2000.
  * Witten et al. (2009) 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–534, 2009.
  * Xing et al. (2002) Eric Xing, Michael Jordan, Stuart J Russell, and Andrew Ng.  Distance metric learning with application to clustering with side-information.  _Advances in neural information processing systems_ , 15, 2002.
  * Xu et al. (2019) 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.
  * Xue and Hall (2014) 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_ , 37(5):1109–1112, 2014.
  * Yang et al. (2017) Zhilin Yang, Zihang Dai, Ruslan Salakhutdinov, and William W Cohen.  Breaking the softmax bottleneck: A high-rank rnn language model.  _arXiv preprint arXiv:1711.03953_ , 2017.
  * Zbontar et al. (2021) Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny.  Barlow twins: Self-supervised learning via redundancy reduction.  _arXiv preprint arXiv:2103.03230_ , 2021.

Supplementary Materials

The supplementary materials is providing the proofs of the main’s paper formal
results. We also provide as much background results and references as possible
throughout to ensure that all the derivations are self-contained. Some of the
below derivation do not belong to formal statements but are included to help
the curious readers get additional insights into current SSL methods.

##  Appendix A Formal Statements Proofs

###  A.1 VICReg Variance+Covariance Versus Representation’s Singular Values

This simple derivation demonstrates how minimizing the VCReg can be done
through an upper bound by constraining all the singular-values to be close to
$1$ although the general criterion only enforces for the variance term to be
—at least— 1 through the following derivations

$\displaystyle\min_{{\bm{Z}}}\min_{{\bm{u}}\in[1,\infty)^{K}}\|{\bm{Z}}^{T}{\bm{Z}}-\operatorname{diag}({\bm{u}})\|_{F}^{2}$
$\displaystyle=\min_{{\bm{Z}}}\min_{{\bm{u}}\in[1,\infty)^{K}}\|{\bm{V}}_{{\bm{Z}}}{\bm{\Sigma}}^{2}_{{\bm{Z}}}{\bm{V}}_{{\bm{Z}}}^{T}-\operatorname{diag}({\bm{u}})\|_{F}^{2}$
$\displaystyle=\min_{{\bm{Z}}}\min_{{\bm{u}}\in[1,\infty)^{K}}\|{\bm{\Sigma}}^{2}_{{\bm{Z}}}-\operatorname{diag}({\bm{u}})\|_{F}^{2}$
$\displaystyle=\min_{{\bm{Z}}}\min_{{\bm{u}}\in[1,\infty)^{K}}\|{\bm{\sigma}}^{2}_{{\bm{Z}}}-{\bm{u}}\|_{2}^{2}$
$\displaystyle\leq\min_{{\bm{Z}}}\|{\bm{\sigma}}^{2}_{{\bm{Z}}}-\mathbf{1}\|_{2}^{2}$

where we denoted by ${\bm{\sigma}}_{{\bm{Z}}}$ the diagonal part of the
diagonal ${\bm{\Sigma}}_{{\bm{Z}}}$ matrix.

###  A.2 Non-Unique Solution to Least-Square

The below derivation demonstrates that even in the representation ${\bm{Z}}$
(or any input matrix) is not full-rank, the least-square type of solution
${\bm{W}}$ to predict ${\bm{Y}}={\bm{Z}}{\bm{W}}$ can be found, it is just not
unique. In fact, it is possible to find an entire space of matrices that will
minimize the loss i.e. respect the below equality that makes the loss have a
gradient of $0$ and be at its minimum value, simply by moving within the
kernel space of the representation (input) matrix as in

$\displaystyle{\bm{Z}}^{T}{\bm{Y}}={\bm{Z}}^{T}{\bm{Z}}{\bm{W}}\iff$
$\displaystyle(U_{{\bm{Z}}}\Sigma_{{\bm{Z}}}V_{{\bm{Z}}}^{\top})^{T}{\bm{Y}}=(U_{{\bm{Z}}}\Sigma_{{\bm{Z}}}V_{{\bm{Z}}}^{\top})^{\top}(U_{{\bm{Z}}}\Sigma_{{\bm{Z}}}V_{{\bm{Z}}}^{\top}){\bm{W}}$
$\displaystyle\iff$ $\displaystyle
V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}U_{{\bm{Z}}}^{T}{\bm{Y}}=V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}\Sigma_{{\bm{Z}}}V_{{\bm{Z}}}^{\top}{\bm{W}}$
$\displaystyle\iff$
$\displaystyle{\bm{W}}^{*}\in\\{(V_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}U_{{\bm{Z}}}^{T}+{\bm{M}}){\bm{Y}}:{\bm{M}}\in\ker({\bm{Z}})\\},$

where we recall that $\ker({\bm{Z}})$ is the kernel space of${\bm{Z}}$, and
where we slightly abused notations by employing $\Sigma^{-1}_{{\bm{Z}}}$ to
represent the inverse only for the non-zero element of the diagonal matrix
$\Sigma_{{\bm{Z}}}$ (there are as many zeros in the diagonal as the dimension
of $\ker({\bm{Z}})$).

###  A.3 Any Linear Weight from Section A.2 Has Zero Least-Square Gradient

This section continues the previous derivations but now demonstrating that
using this optimal value for ${\bm{W}}$ denoted as ${\bm{W}}^{*}$ does fullfil
the equality i.e. we are at a global optimum for any matrix within the defined
subspace as in

$\displaystyle V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}U_{{\bm{Z}}}^{T}{\bm{Y}}=$
$\displaystyle
V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}\Sigma_{{\bm{Z}}}V_{{\bm{Z}}}^{\top}{\bm{W}}^{*}$
$\displaystyle\implies
V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}U_{{\bm{Z}}}^{T}{\bm{Y}}=$ $\displaystyle
V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}\Sigma_{{\bm{Z}}}V_{{\bm{Z}}}^{\top}(V_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}U_{{\bm{Z}}}^{T}+{\bm{M}}){\bm{Y}}$
$\displaystyle\implies
V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}U_{{\bm{Z}}}^{T}{\bm{Y}}=$ $\displaystyle
V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}\Sigma_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}U_{{\bm{Z}}}^{T}{\bm{Y}}$
$\displaystyle\implies
V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}U_{{\bm{Z}}}^{T}{\bm{Y}}=$ $\displaystyle
V_{{\bm{Z}}}\operatorname{diag}(\sigma_{{\bm{Z}}})^{2}\Sigma^{-1}_{{\bm{Z}}}U_{{\bm{Z}}}^{T}{\bm{Y}}$
$\displaystyle\implies
V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}U_{{\bm{Z}}}^{T}{\bm{Y}}=$ $\displaystyle
V_{{\bm{Z}}}\Sigma_{{\bm{Z}}}^{T}U_{{\bm{Z}}}^{T}{\bm{Y}}$

where the last equality follows since
$\operatorname{diag}(\sigma_{{\bm{Z}}})^{2}\Sigma^{-1}_{{\bm{Z}}}$ will either
multiply $(\sigma_{{\bm{Z}}})_{i}^{2}$ with
$(\Sigma^{-1}_{{\bm{Z}}})_{i,i}=\frac{1}{(\sigma_{{\bm{Z}}})_{i}}$ if
$(\sigma_{{\bm{Z}}})_{i}$ is nonzero, and otherwise if
$(\sigma_{{\bm{Z}}})_{i}$ is $0$, then it will be the product between $0$ for
$(\sigma_{{\bm{Z}}})_{i}^{2}$ and $0$ for $(\Sigma^{-1}_{{\bm{Z}}})_{i,i}$
giving back the original value for $(\sigma_{{\bm{Z}}})_{i}$.

###  A.4 Achievable Loss with Low-Rank Representation

This section takes a last detour towards understanding the least-square loss
with a low-rank input/representation matrix. In this case we derive a various
set of quantities that quantify the minimum loss that is achieved by any of
the optimal matrix ${\bm{W}}^{*}$ found in Section A.2 as follows again
slightly abusing notations for $\Sigma^{-1}_{{\bm{Z}}}$ to only invert the
non-zero singular values of ${\bm{Z}}$ as

$\displaystyle\frac{1}{2}\|{\bm{Y}}-{\bm{Z}}{\bm{W}}^{*}\|_{F}^{2}=$
$\displaystyle\frac{1}{2}\|{\bm{Y}}-{\bm{Z}}(V_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}{\bm{U}}_{{\bm{Z}}}^{T}+\tilde{V}_{{\bm{Z}}}{\bm{M}}){\bm{Y}}\|_{F}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\|{\bm{Y}}-{\bm{U}}_{{\bm{Z}}}\Sigma_{{\bm{Z}}}{\bm{V}}_{{\bm{Z}}}^{\top}{\bm{V}}_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}{\bm{U}}_{{\bm{Z}}}^{T}{\bm{Y}}\|_{F}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\|{\bm{Y}}-{\bm{U}}_{{\bm{Z}}}\Sigma_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}{\bm{U}}_{{\bm{Z}}}^{T}{\bm{Y}}\|_{F}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\|({\bm{I}}-{\bm{U}}_{{\bm{Z}}}\Sigma_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}{\bm{U}}_{{\bm{Z}}}^{T}){\bm{Y}}\|_{F}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\|({\bm{U}}_{{\bm{Z}}}{\bm{U}}_{{\bm{Z}}}^{T}-{\bm{U}}_{{\bm{Z}}}\Sigma_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}{\bm{U}}_{{\bm{Z}}}^{T}){\bm{Y}}\|_{F}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\|({\bm{I}}-\Sigma_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}})U_{{\bm{Z}}}^{T}{\bm{Y}}\|_{F}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\|{\bm{Y}}\|_{F}^{2}-\frac{1}{2}\|\Sigma_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}{\bm{U}}_{{\bm{Z}}}^{T}{\bm{Y}}\|_{F}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\|{\bm{Y}}\|_{F}^{2}-\frac{1}{2}\|\Sigma_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}U_{{\bm{Z}}}^{T}{\bm{U}}_{y}\Sigma_{y}\|_{F}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\|{\bm{Y}}\|_{F}^{2}-\frac{1}{2}\sum_{i,j}1_{\\{(\sigma_{{\bm{Z}}})_{i}>0\\}}\langle({\bm{U}}_{{\bm{Z}}})_{i},({\bm{U}}_{y})_{j}\rangle^{2}(\sigma_{y})^{2}_{j},$

where it is clear that the minimum loss will in general not be $0$ unless
$\Sigma_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}={\bm{I}}$ which is not guaranteed
(recall that we abuse notation for the inverse and that
$\Sigma_{{\bm{Z}}}\Sigma^{-1}_{{\bm{Z}}}$ is only $1$ in its diagonal for the
nonzero singular values of ${\bm{Z}}$.

###  A.5 Equivalence Between VICReg Invariance Term and Trace with Graph
Laplacian

The goal of this section is to derive the first crucial result of our study
that ties VICReg to spectral embedding methods by doing a first connection
between VICReg invariance loss and the Dirichlet energy of a graph. The
equality follows from the Laplacian of the graph definition
${\bm{L}}={\bm{D}}-{\bm{G}}$ where ${\bm{D}}$ is the degree matrix of the
graph i.e. a diagonal matrix with entries corresponding to the sum of each row
of ${\bm{G}}$, and using the following algebraic manipulations which are
common in the spectral graph analysis community, see e.g. [Von Luxburg, 2007]

$\displaystyle\operatorname{Tr}\left({\bm{Z}}^{T}{\bm{L}}{\bm{Z}}\right)=$
$\displaystyle\sum_{d}({\bm{Z}}^{T}{\bm{L}}{\bm{Z}})_{d,d}=\sum_{i,j}{\bm{L}}_{i,j}\langle({\bm{Z}})_{j,.}.({\bm{Z}})_{i,.}\rangle$
$\displaystyle=$
$\displaystyle\sum_{i}\|({\bm{Z}})_{i,.}\|_{2}^{2}({\bm{D}})_{i,i}-\sum_{i,j}({\bm{G}})_{i,j}\langle({\bm{Z}})_{j,.}.({\bm{Z}})_{i,.}\rangle$
$\displaystyle=$
$\displaystyle\frac{\sum_{i}\|({\bm{Z}})_{i,.}\|_{2}^{2}({\bm{D}})_{i,i}+\sum_{i}\|({\bm{Z}})_{i,.}\|_{2}^{2}({\bm{D}})_{i,i}}{2}-\sum_{i,j}({\bm{G}})_{i,j}\langle({\bm{Z}})_{j,.}.({\bm{Z}})_{i,.}\rangle$
$\displaystyle=$
$\displaystyle\frac{\sum_{i}\sum_{j}\|({\bm{Z}})_{i,.}\|_{2}^{2}({\bm{G}})_{i,j}+\sum_{i}\sum_{j}\|({\bm{Z}})_{i,.}\|_{2}^{2}({\bm{G}})_{i,j}}{2}-\sum_{i,j}({\bm{G}})_{i,j}\langle({\bm{Z}})_{j,.},({\bm{Z}})_{i,.}\rangle$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i}\sum_{j}({\bm{G}})_{i,j}\|({\bm{Z}})_{i,.}-({\bm{Z}})_{j,.}\|_{2}^{2},$

which is a famous derivation in graph signal processing relating pairwise
distances to Dirichlet energy of the underlying graph with Laplacian
${\bm{L}}$.

###  A.6 Non-Uniqueness of a Representation to a Given VICReg Loss Value

In this section we provide a simple argument to demonstrate that the VICReg
representation that obtains a loss value of $c$ is not unique, regardless of
the (achievable) value of $c$. To see that, one can for example add a constant
vector to each row of ${\bm{Z}}$ and see that Eq. 2 is left unchanged. In fact
the computation of the covariance matrix is invariant to constant column shift
of ${\bm{Z}}$, and the invariance term will automatically cancel those added
vectors when comparing pairs of rows.

###  A.7 Optimal Representation and Loss for VICReg (Theorem 1)

The goal of this section is to obtain the closed-form optimal representation
of VICReg using the least-square variance loss, instead of the hinge-loss, and
to find the minimum loss associated to that (non-unique) optimum. Using the
Trace term derivations given in Section A.5 we obtain

$\displaystyle\mathcal{L}_{\rm
VIC}=\alpha\|\mathrm{Cov}({\bm{Z}}^{*}_{\alpha,\gamma})-{\bm{I}}\|_{F}^{2}+2\frac{\gamma}{N}\operatorname{Tr}\left(({\bm{P}}^{\prime}_{\alpha,\gamma}({\bm{\Lambda}}^{\prime}_{\alpha,\gamma}N)^{1/2})^{T}{\bm{L}}{\bm{P}}^{\prime}_{\alpha,\gamma}({\bm{\Lambda}}^{\prime}_{\alpha,\gamma}N)^{1/2}\right),$

where we use
${\bm{\lambda}}_{\alpha,\beta}^{\prime},{\bm{P}}^{\prime}_{\alpha,\gamma}$ and
${\bm{\Lambda}}^{\prime}_{\alpha,\gamma}$ to denote the first $K$
indices/columns of Eq. 8. Simplifying the trace term leads to

$\displaystyle\frac{\gamma}{N}\operatorname{Tr}\left(({\bm{P}}^{\prime}_{\alpha,\gamma}({\bm{\Lambda}}^{\prime}_{\alpha,\gamma}N)^{1/2})^{T}{\bm{L}}{\bm{P}}^{\prime}_{\alpha,\gamma}({\bm{\Lambda}}^{\prime}_{\alpha,\gamma}N)^{1/2}\right)$
$\displaystyle=\gamma\operatorname{Tr}\left({\bm{\Lambda}}^{\prime}_{\alpha,\gamma}{{\bm{P}}^{\prime}}_{\alpha,\gamma}^{T}{\bm{L}}{\bm{P}}^{\prime}_{\alpha,\gamma}\right)$
$\displaystyle=\alpha\operatorname{Tr}\left({\bm{\Lambda}}^{\prime}_{\alpha,\gamma}{{\bm{P}}^{\prime}}_{\alpha,\gamma}^{T}{\bm{M}}{\bm{P}}^{\prime}_{\alpha,\gamma}\right)$
$\displaystyle\hskip
71.13188pt-\alpha\operatorname{Tr}\left({\bm{\Lambda}}^{\prime}_{\alpha,\gamma}{{\bm{P}}^{\prime}}_{\alpha,\gamma}^{T}({\bm{M}}-\frac{\gamma}{\alpha}{\bm{L}}){\bm{P}}^{\prime}_{\alpha,\gamma}\right)$
$\displaystyle=\alpha\operatorname{Tr}\left({\bm{\Lambda}}^{\prime}_{\alpha,\gamma}{{\bm{P}}^{\prime}}_{\alpha,\gamma}^{T}({\bm{I}}-\frac{1}{N}\mathbf{1}\mathbf{1}^{T}){\bm{P}}^{\prime}_{\alpha,\gamma}\right)-\alpha\|{\bm{\lambda}}^{\prime}_{\alpha,\gamma}\|_{2}^{2},$

plugging this value into the loss we obtain

$\displaystyle\mathcal{L}_{\rm VIC}=$
$\displaystyle\alpha\left(\|\mathrm{Cov}({\bm{Z}}^{*}_{\alpha,\gamma})-{\bm{I}}\|_{F}^{2}+2\operatorname{Tr}\left({\bm{\Lambda}}^{\prime}_{\alpha,\gamma}{{\bm{P}}^{\prime}}_{\alpha,\gamma}^{T}({\bm{I}}-\frac{1}{N}\mathbf{1}\mathbf{1}^{T}){\bm{P}}^{\prime}_{\alpha,\gamma}\right)-2\|{\bm{\lambda}}^{\prime}_{\alpha,\gamma}\|_{2}^{2}\right)$
$\displaystyle=$
$\displaystyle\alpha\left(\|\mathrm{Cov}({\bm{Z}}^{*}_{\alpha,\gamma})\|_{F}^{2}+K-2\operatorname{Tr}(\mathrm{Cov}({\bm{Z}}^{*}_{\alpha,\gamma}))+2\operatorname{Tr}\left({\bm{\Lambda}}^{\prime}_{\alpha,\gamma}{{\bm{P}}^{\prime}}_{\alpha,\gamma}^{T}({\bm{I}}-\frac{1}{N}\mathbf{1}\mathbf{1}^{T}){\bm{P}}^{\prime}_{\alpha,\gamma}\right)-2\|{\bm{\lambda}}^{\prime}_{\alpha,\gamma}\|_{2}^{2}\right)$
$\displaystyle=$
$\displaystyle\alpha\left(\|\mathrm{Cov}({\bm{Z}}^{*}_{\alpha,\gamma})\|_{F}^{2}+K-2\|{\bm{\lambda}}^{\prime}_{\alpha,\gamma}\|_{2}^{2}\right)$
$\displaystyle=$
$\displaystyle\alpha\left(\left\|\frac{1}{N}({\bm{Z}}^{*}_{\alpha,\gamma})^{T}{\bm{M}}{\bm{Z}}^{*}_{\alpha,\gamma}\right\|_{F}^{2}+K-2\|{\bm{\lambda}}^{\prime}_{\alpha,\gamma}\|_{2}^{2}\right),$

now one should recall that ${\bm{Z}}^{*}_{\alpha,\gamma}$ contains the
eigenvectors of ${\bm{M}}-\frac{\gamma}{\alpha}{\bm{L}}$ and that each of
those eigenvector that has nonzero singular value has $0$ mean since

$\displaystyle({\bm{M}}-\frac{\gamma}{\alpha}{\bm{L}}){\bm{v}}$
$\displaystyle=\lambda{\bm{v}}$
$\displaystyle\iff{\bm{M}}({\bm{I}}-\frac{\gamma}{\alpha}{\bm{L}}){\bm{M}}{\bm{v}}$
$\displaystyle=\lambda{\bm{v}}$ (Laplacian rows/cols sum to $0$)
$\displaystyle\implies\mathbf{1}^{T}{\bm{M}}({\bm{I}}-\frac{\gamma}{\alpha}{\bm{L}}){\bm{M}}{\bm{v}}$
$\displaystyle=\lambda\mathbf{1}^{T}{\bm{v}}$ $\displaystyle\implies 0$
$\displaystyle=\lambda\mathbf{1}^{T}{\bm{v}}\implies\mathbf{1}^{T}{\bm{v}}=0$
(for any eigenvector ${\bm{v}}$ with $\lambda>0$)

hence we obtain the following simplifications

$\displaystyle\mathcal{L}_{\rm VIC}=$
$\displaystyle\alpha\left(\left\|\frac{1}{N}({\bm{Z}}^{*}_{\alpha,\gamma})^{T}{\bm{M}}{\bm{Z}}^{*}_{\alpha,\gamma}\right\|_{F}^{2}+K-2\|{\bm{\lambda}}^{\prime}_{\alpha,\gamma}\|_{2}^{2}\right)$
$\displaystyle=$
$\displaystyle\alpha\left(\left\|\frac{1}{N}({\bm{Z}}^{*}_{\alpha,\gamma})^{T}{\bm{Z}}^{*}_{\alpha,\gamma}\right\|_{F}^{2}+K-2\|{\bm{\lambda}}^{\prime}_{\alpha,\gamma}\|_{2}^{2}\right)$
$\displaystyle=$
$\displaystyle\alpha\left(\left\|{\bm{\lambda}}^{\prime}_{\alpha,\gamma}\right\|_{2}^{2}+K-2\|{\bm{\lambda}}^{\prime}_{\alpha,\gamma}\|_{2}^{2}\right)$
$\displaystyle=$
$\displaystyle\alpha(K-\|{\bm{\lambda}}^{\prime}_{\alpha,\gamma}\|_{2}^{2})$

which conludes the proof.

###  A.8 Proof of VICReg Recovering Laplacian Eigenmaps (Theorem 2)

This section takes on proving the first key result of our study that
thoroughly tie VICReg to the known local spectral embedding method Laplacian
Eigenmap. The only difference would be that in our case the graph ${\bm{G}}$
is given from an SSL viewpoint and not constructed from a k-NN graph and
geodesic distance estimate as in LE. We already know from Section A.5 that the
invariance term of VICReg corresponds to the Trace term (times $2$) that LE
tries to minimize. The only thing that we have to show to have the equivalent
between the two is that the constraint ${\bm{Z}}^{T}{\bm{D}}{\bm{Z}}={\bm{I}}$
is equivalent to the one that imposes an exact minimization of the variance
and covariance terms. To see that, first notice (or recall from Section A.7)
that the variance+covariance term can be expressed as
$\|\frac{1}{N}{\bm{Z}}^{T}{\bm{M}}{\bm{Z}}-{\bm{I}}\|_{F}^{2}$. Now, recall
that the minimizer of LE consists in taking the $[2:K+1]$ eigenvectors of the
Laplacian matrix ${\bm{I}}-{\bm{D}}^{-1}{\bm{G}}$ which is equivalent (up to a
rescaling of the eigenvalues) to taking the eigenvectors of
${\bm{D}}-{\bm{G}}$ as long as ${\bm{D}}$ is isotropic. We also already saw
that those eigenvectors either have zero mean and nonzero eigenvalue, or have
arbitrary means and zero eigenvalue. As LE only considers the eigenvectors
with nonzero eigenvalues, it is direct to see that those eigenvectors are
centered. This translates to
$\|\frac{1}{N}{\bm{Z}}^{T}{\bm{M}}{\bm{Z}}-{\bm{I}}\|_{F}^{2}=\|\frac{1}{N}{\bm{Z}}^{T}{\bm{Z}}-{\bm{I}}\|_{F}^{2}$.
Hence, up to a rescaling, as long as $D$ is isotropic ($D=c{\bm{I}}$) which is
always the case in SSL, enforcing $\mathcal{L}_{\rm var}=0,\mathcal{\rm
cov}=0$ is equivalent to ${\bm{Z}}^{T}{\bm{Z}}=\frac{N}{c}{\bm{I}}$.

###  A.9 Proof of Linear VICReg Optimal Parameters (Eq. 12)

We are again using the quadratic variance term in-place of the hinge-term at
$1$. In that setting, the linear VICReg loss falls back to

$\displaystyle\mathcal{L}_{\rm
vic}=\alpha\left\|\frac{1}{N}{\bm{W}}^{T}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}}-{\bm{I}}\right\|_{F}^{2}+\frac{2\gamma}{N}\operatorname{Tr}({\bm{W}}^{T}{\bm{X}}^{T}{\bm{L}}{\bm{X}}{\bm{W}}),$

which can be written in term of traces only to simplify differentiation as

$\displaystyle\mathcal{L}_{\rm vic}=$
$\displaystyle\frac{\alpha}{N^{2}}\operatorname{Tr}({\bm{W}}^{T}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}}{\bm{W}}^{T}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}})$
$\displaystyle-\frac{2\alpha}{N}\operatorname{Tr}({\bm{W}}^{T}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}})+\frac{2\gamma}{N}\operatorname{Tr}({\bm{W}}^{T}{\bm{X}}^{T}{\bm{L}}{\bm{X}}{\bm{W}})+{\rm
cst}$ $\displaystyle=$
$\displaystyle\frac{\alpha}{N^{2}}\operatorname{Tr}({\bm{W}}^{T}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}}{\bm{W}}^{T}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}})+\frac{2}{N}\operatorname{Tr}({\bm{W}}^{T}{\bm{X}}^{T}(\gamma{\bm{L}}-\alpha{\bm{H}}){\bm{X}}{\bm{W}})+{\rm
cst}$

which we can now differentiate with respect to the ${\bm{W}}$ parameter to
obtain

$\displaystyle\nabla_{{\bm{W}}}\mathcal{L}_{\rm
vic}=\frac{4\alpha}{N^{2}}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}}{\bm{W}}^{T}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}}+\frac{4}{N}{\bm{X}}^{T}(\gamma{\bm{L}}-\alpha{\bm{H}}){\bm{X}}{\bm{W}},$

which we need to set to $0$ and thus can be simplified to (since $\alpha>0$)

$\displaystyle\nabla_{{\bm{W}}}\mathcal{L}_{\rm
vic}=\frac{1}{N}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}}{\bm{W}}^{T}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}}+{\bm{X}}^{T}\left(\frac{\gamma}{\alpha}{\bm{L}}-{\bm{H}}\right){\bm{X}}{\bm{W}}.$

First, let’s consider that ${\bm{X}}^{T}{\bm{H}}{\bm{X}}$ is invertible i.e.
the data lies on a $D$-dimensional affine space. If not, the original data
${\bm{X}}$ can simply be projected onto its subspace prior applying VICReg. In
that setting and if $K=D$, we directly obtain

$\displaystyle\nabla_{{\bm{W}}}\mathcal{L}_{\rm vic}=$
$\displaystyle\mathbf{0}$
$\displaystyle\iff\frac{1}{N}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}}{\bm{W}}^{T}{\bm{X}}^{T}{\bm{H}}{\bm{X}}{\bm{W}}=$
$\displaystyle{\bm{X}}^{T}\left({\bm{H}}-\frac{\gamma}{\alpha}{\bm{L}}\right){\bm{X}}{\bm{W}}$
$\displaystyle\iff{\bm{W}}{\bm{W}}^{T}\mathrm{Cov}({\bm{X}}){\bm{W}}=$
$\displaystyle\frac{1}{N}\mathrm{Cov}({\bm{X}})^{-1}{\bm{X}}^{T}\left({\bm{H}}-\frac{\gamma}{\alpha}{\bm{L}}\right){\bm{X}}{\bm{W}},$

denoting for clarity ${\bm{A}}\triangleq\mathrm{Cov}({\bm{X}})$ and
${\bm{B}}\triangleq\frac{1}{N}{\bm{X}}^{T}\left({\bm{H}}-\frac{\gamma}{\alpha}{\bm{L}}\right){\bm{X}}=\mathrm{Cov}({\bm{X}})-\frac{\gamma}{\alpha}{\bm{X}}^{T}{\bm{L}}{\bm{X}}$
we have

$\displaystyle{\bm{W}}{\bm{W}}^{T}{\bm{A}}{\bm{W}}=$
$\displaystyle{\bm{A}}^{-1}{\bm{B}}{\bm{W}},$

which is solved for ${\bm{W}}={\bm{A}}^{-1}\sqrt{{\bm{B}}}$. Now, if $K<D$
then there are multiple local minimum, all with the same loss value, and those
are obtained by extracting any $K$-out-of$D$ columns of the above solution.
For Eq. 12 we considered the first $K$ columns arbitrarily.

###  A.10 Proof of Laplacian estimation with contrastive learning Theorem 4

The first step of the proof consists in recovering the softmax with any metric
$d$ that computes the distance (whatever distance desired) between pairs of
inputs.

Graph Laplacian Estimation recovers the step 1 of contrastive methods using
$\mathcal{R}_{\rm log}$. To prove Eq. 16 (the case with $\mathcal{G}$ and not
$\mathcal{G}_{\rm rsto}$ can be done similarly be removing the row-sum-to-one
constraint), we need to solve the following optimization problem

$\displaystyle\operatorname*{arg\,min}_{{\bm{W}}\in\mathcal{G}_{\rm
rsto}}\sum_{i\not=j}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j})){\bm{W}}_{i,j}+\tau\sum_{i\not=j}{\bm{W}}_{i,j}(\log({\bm{W}}_{i,j})-1),$

which we solve by introducing the constraint in the optimization problem with
the Lagrangian to

$\displaystyle\mathcal{L}=$
$\displaystyle\sum_{i\not=j}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j})){\bm{W}}_{i,j}+\tau\sum_{i\not=j}{\bm{W}}_{i,j}(\log({\bm{W}}_{i,j})-1)+\sum_{i=1}^{N}\lambda_{i}(\sum_{j\not=i}W_{i,j}-1)+\sum_{i}\beta_{i}{\bm{W}}_{i,i}$
$\displaystyle\implies\frac{\partial\mathcal{L}}{\partial{\bm{W}}_{i,j}}=$
$\displaystyle\begin{cases}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))+\tau\log({\bm{W}}_{i,j})+\lambda_{i}\iff
i\not=j\\\ \beta_{i}\iff i=j\end{cases}$
$\displaystyle\implies\frac{\partial\mathcal{L}}{\partial\lambda_{i}}=$
$\displaystyle\sum_{j\not=i}{\bm{W}}_{i,j}-1$
$\displaystyle\implies\frac{\partial\mathcal{L}}{\partial\beta{i}}=$
$\displaystyle{\bm{W}}_{i,i},$

we first solve for $\frac{\partial\mathcal{L}}{\partial{\bm{W}}_{i,j}}=0$ for
$i\not=j$ to obtain an expression of ${\bm{W}}_{i,j}$ as a function of
$\lambda_{i}$ as

$\displaystyle\frac{\partial\mathcal{L}}{\partial{\bm{W}}_{i,j}}=0\iff$
$\displaystyle
d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))+\tau\log({\bm{W}}_{i,j})+\lambda_{i}=0$
$\displaystyle\iff$
$\displaystyle\tau\log({\bm{W}}_{i,j})=-d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))-\lambda_{i}$
$\displaystyle\iff$
$\displaystyle{\bm{W}}_{i,j}=e^{\frac{-1}{\tau}(d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))+\lambda_{i})}$
$\displaystyle\iff$
$\displaystyle{\bm{W}}_{i,j}=e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}e^{\frac{-1}{\tau}\lambda_{i}},$

and now using $\frac{\partial\mathcal{L}}{\partial\lambda_{i}}=0$ we will be
able to solve for $\lambda_{i}$ as follows

$\displaystyle\frac{\partial\mathcal{L}}{\partial\lambda_{i}}=0$
$\displaystyle\iff\sum_{j\not=i}{\bm{W}}_{i,j}-1=0$ $\displaystyle\iff
e^{\frac{-\lambda_{i}}{\tau}}\sum_{j\not=i}e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}=1$
$\displaystyle\iff
e^{\frac{-\lambda_{i}}{\tau}}=\frac{1}{\sum_{j\not=i}e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}},$

which allows us to finally obtain an explicit solution for
$\frac{\partial\mathcal{L}}{\partial{\bm{W}}_{i,j}}=0$ that does not depend on
$\lambda_{i}$ as follows

$\displaystyle\frac{\partial\mathcal{L}}{\partial{\bm{W}}_{i,j}}=0$
$\displaystyle\iff{\bm{W}}_{i,j}=e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}e^{\frac{-\lambda_{i}}{\tau}}$
$\displaystyle\iff{\bm{W}}_{i,j}=\frac{e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}}{\sum_{j\not=i}e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}}$

which holds for $i\not=j$. Now for the case $i=j$ simply using the constraint
and solving for $\beta_{i}$ directly gives ${\bm{W}}_{i,i}=0$. Notice that we
did not enforce the ${\bm{W}}_{i,j}={\bm{W}}_{j,i}$ constraint, however, the
optimum found fulfills it and thus we are in a scenario akin to undirected
graph Laplacian estimation.

Recovering SimCLR with Cosine Similarity. Now, since we are using the cosine
distance, defined as
$f({\bm{x}},{\bm{y}})=1-\frac{\langle{\bm{x}},{\bm{y}}\rangle}{\|{\bm{x}}\|\|{\bm{y}}\|}$,
we can plug it in the above to finally obtain

$\displaystyle{\bm{W}}_{i,j}=\frac{e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}}{\sum_{j\not=i}e^{\frac{-1}{\tau}d(f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j}))}}1_{\\{i\not=j\\}}=\frac{e^{\frac{1}{\tau}\frac{\langle
f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j})\rangle}{\|f_{\theta}({\bm{x}}_{i})\|_{2}\|f_{\theta}({\bm{x}}_{j})\|_{2}}}}{\sum_{j\not=i}e^{\frac{1}{\tau}\frac{\langle
f_{\theta}({\bm{x}}_{i}),f_{\theta}({\bm{x}}_{j})\rangle}{\|f_{\theta}({\bm{x}}_{i})\|_{2}\|f_{\theta}({\bm{x}}_{j})\|_{2}}}}1_{\\{i\not=j\\}},$

which is exactly the features used by SimCLR or NNCLR. The last step is
direct, take the graph of known positive pairs of nearest neighbor, apply the
cross entropy between those and the above, and one obtains that Eq. 16
recovers exactly the loss of those models.