Neural Harmonics: Bridging Spectral Embedding and Matrix Completion in Self-Supervised Learning
Authors: Marina Munkhoeva
Ivan Oseledets
Venue: NeurIPS 2023 poster (2023)
Keywords: unsupervised learning
self-supervised learning
representation learning
matrix completion
TL;DR: self-supervised learning methods perform low-rank matrix recovery

Abstract: Self-supervised methods received tremendous attention thanks to their seemingly heuristic approach to learning representations that respect the semantics of the data without any apparent supervision in the form of labels. A growing body of literature is already being published in an attempt to build a coherent and theoretically grounded understanding of the workings of a zoo of losses used in modern self-supervised representation learning methods. 
In this paper, we attempt to provide an understanding from the perspective of a Laplace operator and connect the inductive bias stemming from the augmentation process to a low-rank matrix completion problem.
To this end, we leverage the results from low-rank matrix completion to provide theoretical analysis on the convergence of modern SSL methods and a key property that affects their downstream performance.

Neural Harmonics: Bridging Spectral Embedding and Matrix Completion in Self-Supervised Learning
Marina Munkhoeva
Ivan Oseledets
Abstract
Self-supervised methods received tremendous attention thanks to their seemingly heuristic approach to learning representations that respect the semantics of the data without any apparent supervision the form of labels. A growing body of literature is already being published in an attempt to build coherent and theoretically grounded understanding of the workings of a zoo of losses used modern self-supervised representation learning methods. In this paper, attempt to provide an understanding from the perspective of Laplace operator and connect the inductive bias stemming from the augmentation process low-rank matrix completion problem.
this end, we leverage the results from low-rank matrix completion to provide theoretical analysis on the convergence of modern SSL methods and a key property that affects their downstream performance.
Introduction
Self-supervised methods have garnered significant interest due to their heuristic approach to learning representations that capture the semantic information data without requiring explicit supervision in the form of labels. Contrastive learning based methods among the former would use the repulsion among arbitrary pair of points in the batch, while non-contrastive would rely on the consistency among different views of the same image. While self-supervised representation learning becomes more ubiquitous in the wild, especially in the important domain such as medical imaging [6], the theoretical grounding of these methods would potentially help avoid the pitfalls in applications. Unsurprisingly, researchers are already trying to build theoretically sound understanding of modern self-supervised representation learning methods.
The overall goal of this work to understand self-supervised representation learning through the lens of nonlinear dimensionality reduction methods (e.g. Laplacian Higenmaps R and low-rank matrix completion problem (28). To this end, we take on Laplace operator perspective on learning the optimal representations in the manifold assumption. We then derive a trace maximization formulation to learn eigenfunctions the Laplace operator the underlying data manifold. We adopt the heat kernel based embedding map that in theory under certain conditions is almost isometric embedding of the oiw-dimessional manifold into the Euclidean space. As a result, we discuss how existing several SSL methods (e.g. SIMCLR (9. BARLOWTWINS [.. VICREG 2 can be comprehended under this view.
It is important to note that our current understanding of the topic lacks one crucial aspect. Traditional spectral methods commonly operate with complete kernel matrices, whereas our approach deals with incomplete and potentially noisy ones. The only available similarity information among examples derived from the data augmentation process, which generates a positive pair. Meanwhile the
"Correspondence to marina. munkhoeva@tuebingen. www.ggen......e.e...
I Maa Planck Institute for Intelligent Systems, Tübingen, Germany Artificial Intelligence Research Institute (AIRI). Skolkovo Institute of Science and Technology (Skoltech), Moscow, Russian Federation
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

remaining examples in the batch are either seen as negative ones (contrastive) or are not considered all (non-oontrastive.
A pertinent and often overlooked question emerges: how can self-supervised learning methods effectively leverage such limited signals to converge towards meaningful representations? In response, we shed light on this matter by establishing a connection between SSL and a matrix completion problem. We demonstrate that these optimization problems are Lagrangian dual of each other, implying that optimizing the SSL objective simultaneously entails reconstructing the kernel matrix. We can summarize the contributions of this paper as follows:
fraction of observed entries
thouretical bound p
actual value p = 1/N
We propose an eigen-problem objective for spectral embeddings from graphs induced by augmentations and use to interpret modern SSL methods.
500
1,000
number of epochs
We show that SSL methods do Laplacian basedd nonlinear dimensionality reduction and low-rank matrix completion simultaneously. We leverage theory behind matrix completion problem to provide insights on the success of SSL methods and their use in practice.
Illustrative graph of the theoretical fraction of the observed entries required for matrix completion to succeed with high probability. As training proceeds, unmaterialized kernel matrix size increases and p", which is roughly log n/nn, decreases. Eventually, the actual (constant) fraction of observed entries under self-supervised learning augmentation protocol intersects the theoretical bound.
Figure 1:
While the number of observed entries required by theory decreases with epochs, we find that the actual number is constant and the former eventually intersects the latter.
We find possible explanation for disparity in downstream performance of the backbone and projection outputs.
2 Background
This work relies on the manifold hypothesis, a hypothesis that many naturally occurring high-dimensional data lie along a low-dimensional latent manifold inside the high-dimensional space. Since we can only observe a sample from the manifold in the ambient space, neither the true manifold nor its metric are available to us. Although we never explicitly work with operator, we still give a brief definition below to provide some grounding for the reasoning later.
Beltrami
Laplace operator Let M be a Riemannian manifold and be the Riemannian metric on M. For any smooth function on M,, the gradient Vu vector field on M. Let be the Riemannian volume on M. dv = det dx ...dx By the divergence theorem, for any smooth functions and v (plus smooth and compact support assumptions) J.M u div du = - S (Vu, Ve)de, where (.-) -..-). The operator A div is called the Laplace- Laplace-Beltrami operator of the Riemannian manifold M.
In practice, we usually work with finite samples, and Laplace operator is typically approximated with graphs or meshes. While the latter are typically used in computational mathematics, the former find a widespread use in machine learning. Below is a brief overview of the relevant graph notions, for detailed exposition please see 36)
Graph Laplacian and Spectral Embedding Given a graph I' = (V, E') with |V vertices and set of edges eig (U:, U5) that form a weighted adjacency matrix A,j Wiy with non-negative weight Waj 2 0, whenever there is eij E E, otherwise O. With degree matrix D = diag( A1), the graph Laplacian is given by D A, the corresponding random walk Laplacian is normalization
Lrw I D A. All graph Laplacians admit an eigenvalue decomposition, i.e. L - UAUT. where U B contains eigenvectors in columns and a diagonal matrix Raxn has eigenvalues show that the eigenvectors of the graph Laplacian of point-cloud dataset converge to the eigenfunctions of the Laplace-Beltee Beltrami operator under uniform sampling assumption.
on the diagonal. Note that there is a trivial eigenpair (0, 1). 5 4

---

Whenever one has an affinity matrix, positive semidefinite pairwise similarity relations among points, the classical way obtain embeddings for the points to perform spectral embedding. typical algorithm would include constructing graph based on the affinity matrix, computing k first eigenvectors of its Laplacian and setting the embeddings to be the rows of the matrix U RR that contains the eigenvectors as columns.
Matrix completion Let M E R=** is partially observed matrix with rank r. Under Bernoulli model, each entry M, is observed independently of all others with probability Let f be the set of observed indices. The matrix completion problem aims to recover M from m [S2] observations. The standard way to solve this problem is via nuclear norm minimization:
min X
|X|
subject to Xij = Míj for (1.j) E Ω
(1)
where X x|. is the nuclear norm of X, i.e. the sum of its singular values. large body of work g 28 27
10 has succeeded in providing and enhancing of the conditions that guarantee the optimal
solution X to be both unique and equal to M with high probability.
Notation Any matrix X R has singular value decomposition (SVD) x = UEVT where the columns of the matrix UE E Ra x are left singular vectors, the singular values T1 2 02 2 ... minn(n), mzg) lie on the diagonal of diagonal matrix Σ E I x and right singular vectors are the columns of E R=>xx. |||| ||. ||X|| = σ1, |X|| = Σ, og denote Frobenius, spectral and nuclear norms of X, respectively. |x||p denotes p-th vector norm.
3 SSL and Spectral Embedding
In this section, we will provide a construction that covers most of the self-supervised learning methods and gives SSL novel interpretation. First, formalize the setup from the perspective of the manifold hypothesis. Then, we make some modelling choices to yield an SSL formulation as trace maximization problem, a form of eigenvalue problem. Finally, describe how three well known representatives SSL. methods fall under this formulation.
Let X E RRn be a set of n points in Rd sampled from a www-dimensional data manifold observed in d' n'-dimensional ambient Euclidean space. However, data is rarely given in the space where each dimension is meaningful, in other words d' >> d", where d' is unknown true dimensionality of the manifold. The goal of nonlinear dimensionality reduction is to find useful embedding map into d-dimensional Euclidean space with d < d'. Two of the classical approaches, namely Eigenmaps D and Diffusion maps [T]) use eigenfunctions of the graph Laplacian, an approximation of the Laplace operator associated with the data manifold. Both can be loosely described as a variant of map
o(x) = [[ (x) d2(x)
<x(x)) ),
where de is k-th eigenfunction of the negative Laplace operator on the underlying manifold.
This type of map bears a direct connection to theoretical question how to find an embedding of certain types of manifolds into Euclidean spaces, studied in differential geometry. For instance, 6 construct embedding for a given smooth manifold by using its heat kernel. This approach has been subsequently enhanced through the application of truncated heat kernel expansion. Furthering this trajectory, (26) explore whether and when such embedding is close to being isometric, which is desirable as isometric embedding preserves distances.
Motivated by the heat kernel embedding literature, we provide a general construction for self-supervised methods in what follows. The heat kernel on manifold can be represented as an expansion H (p. q, - e -Xct (o Φu (q), where p and q are some points on the manifold, t > 0 and &e normalized eigenfunctions of the Laplace operator, i.c. -Ao d and 10x12 1. However, working with finite data, we can only operate with graph approximation of the manifold, and will make use of the heat kernel construction for graphs. The latter is given by matrix exponential H. = e IL alternatively represented through an expansion H, Σi e det oro where L is graph Laplacian and (Ac, is k-th eigenpair of L.
Consider Laplacian EigenMaps method, it first constructs a graph and weighs the edges with a heat kernel of the Euclidean space which takes the form of Gaussian kernel
3

---

hg(x,y, v, = exp(-1x-yll3 whenever the distance is less then some hyperparameter, i.c. | -yl2 c. y is among is nearest neighbours of x. Next, the method proceeds with finding the eigenvectors of the graph Laplacian constructed from the thus weighted adjacency matrix W.
Contrarily, the proposed construction acknowledges the cardinality and complexity typically associated with the modern day datasets, where it is challenging to select the cutoff' distance or the number of neighbours, and impractical compute all pairwise distances, Our ideal graph has edges reflecting the semantic similarity between points; c.g. there is an edge whenever the pair of points belong to the same class. The drawback is that this matrix is unknown. This is where augmentation comes into play as it provides peek into only fraction of the entries in the unmaterialized heat kemee matrix. Consequently, we claim that SSL implicitly solves a low-rank matrix completion problem by instantiating some of the pairwise similarity entries in H, via the augmentation process. However, prior to this, we need demonstrate the generality of the perspective we have formulated. To accomplish this, we articulate trace maximization problem.
3.1 Trace Minimization
To start, we construct an unmaterialized heat kernel matrix in accordance with the standard self-supervised learning protocol for augmentations. Given a dataset with N points, one training epoch generates views of each point. Typically, a 2 and training runs for Nepochs number of epochs. The whole training generates exactly Repochs X a views per original instance. As a result the total number of processed examples
N Nepochs: thereby we have that H, E Raxx
As a rule, SSL utilises architectures with a heavy inductive bias, c.g. ResNet 19 / Vision Transformers [14] for image data. Thus, may safely assume that the same instance views are close the embedding space and are connected. This results in a block diagonal adjacency matrix W, where i-th block of ones accounts for all the views of i-th image among N original images. The fraction of observed entries equal to p = N X (Repoohs x a)² /n² 1/N, a constant fraction for given dataset.
Note that in the ideal scenario, we would know the cluster/class affiliation for each point and would have connected same-class views with edges. However, in reality, only know instance affiliation of each view. Let us denote the ideal scenario heat kernel matrix as H, and its partially observed counterpart used in reality - -H; H;-
To obtain the heat kernel matrix, we use the normalized random walk Laplacian Ly for which the heat kernel matrix is as before: H, = cxp(-tt,ru) = Σh=o (xp(->xt)u,,ae where u is k-th eigenvector and d a corresponding eigenvalue of Lyw- To obtain spectral embeddings from an ideal He, one would then proceed with solving a trace minimization form of eigenvalue problem in where the optimal solution is exactly the eigenvectors of Lyus i.e. Z" U.
max 2
Tr H,Z)
max Tr
(3)
(4)
s.t. Zzz II
s.t. Z Zo
= Id, Z 10
However, for lack of a better alternative we resort to the incomplete H. and need to learn a parameterized map FX) Ze in (4). Apart from the specified eigenfunction pairwise orthogonality constraint, the resulting loss is comprised of implicit constraints on the trivial eigenfunction (identity) and function norm. But before we treat (3) with incomplete H, as matrix completion problem, we show that this formulation can be seen generalization for number of existing self-supervised learning methods. Specifically, several modelling choices differentiate the resultant methods.
3.2 Self-Supervised Methods Learn Eigenfunctions of the Laplace Operator
SIMCLR Consider the following contrastive loss, variants of which are widely adopted in self-supervised learning methods: LOL
Lij + Ljis where
t.Etppiire
(a(2)12))
li log Σ e (m))) k(Z,, 2j) log Σ c((zaaa))
(5)

---

with z; = fo(;) is embedding of input x; given by function f parameterized by a neural network with learnable parameters 9, which produces unit-norm embeddings, i... |zill2 1. One iteration of SIMCLR takes batch of N data points and creates 2N views, augmenting each sample to obtain a positive pair R2), while treating all the other samples and their augmentations as contrastive samples Z---
Let us include k i in the sum in denominator of (5) for moment. A goal of SIMCLR is obtain optimal representations Z E I2NN xd such that for each positive pair (i,j), their representations will be aligned as much as possible (z,, 2n} - Let Aij exp(1 ZZ 1gg) and diag(A1), then can rewrite (5)
2N
A log (Bg(D-AA) D.:
L/ = log Ai log Σ A. = log Ai log D log
(6)
k=
where we are interested in the right hand side log Al.. Let us note that [D [D-1A]; A]is from (6) normalized adjacency of graph G = (V, E", where node set V is the set of views. Since representations live on a unit (d --spher,, we have a choice of naturally arising distributions (von Mises-Fisher, spherical normal, etc) to instantiate the weighting function μ(x;, Xy). The model choice of SIMCLR to instantiate the weighting function with the density of the von Mises-Fisher distribution with (without the partition function):
Aij exp(1z2 2j).
where Aij equals ex, with a typical value k = 2, whenever i, is a positive pair, and ea 1 otherwise. Note that log((D1A)) = D-1A - I ((DD)1)))) & LL thus in loose terms the objective in (5) maybe be seen as a minimization of a trace of a negative of the graph Laplacian by learning z's is that shape A.
Decoupled Contrastive Learning 38 can be seen as reweighting the adjacency matrix by setting Aij (2) 2y), where w(z,, 2g) a reweighting function emphasize hard examples.
For non-contrastive methods (BARLOWTWINS, VICREG, etc) SSL methods (where no negative examples used, e.g. BARLOWTWINS, SIMSIAM), the respective losses could also be interpreted as learning a diffusion map. The key distinction with contrastive methods expresses itself in setting Ag 0 for view pairs (i,j) that do not have shared original, thus eliminating any signal from possibly negative pair.
BARIOWTWINS method normalizes the columns of representation matrices Z., Zo E R.d which is the same as the function norm constraint in (4). The overall objective is as follows:
J = Σ (Z - 1) + a E(z.z, 1);
(8)
and simultaneously aims at three things: (i) enforce the closeness of the rows, i.e. positive pair embeddings, (ii) restrict the norm of the columns, i.e. the eigenfunctions, (iii) orthogonalize columns, again the eigenfunctions. The kernel matrix choice in BARLOWTWIN is a simple bi-diagonal adjacency matrix A.j- as long (i.j) is positive pair, and 0 otherwise.
VICREG objective is a weighted sum of variance, covariance and invariance terms:
J var
max
Z 2 RK), JEOU Σ ZZ Jine = - Z2 2
A=1
leght
a similar formulation to the previous method, however, the choice for the adjacency matrix here little bit different. Individual terms of this loss have separate coefficients. The choice of these hyperparameters defines the implicit adjacency matrix entries, controls the maximum function norm allowed and the trade-off between orthogonality and the trace terms
4 SSL and Low-Rank Matrix Completion
In this section, we use low-rank matrix completion theory to show that the limited information from augmentations might be quite enough under certain conditions. First, we establish the connection between our self-supervised learning objective (4) and the low-rank matrix completion problem. We then draw practical insights from the existing convergence theory for matrix completion problem.
5

---

4.1 Low-Rank Matrix Completion Dual
with substitute incomplete kernel matrix H2 implicitly contains an objective for the low-rank matrix completion problem. To show this, we first introduce the general form of the nuclear norm minimization problem with affine subspace constraint in (
We argue that the objective in 3
min X
|X||
max b b
(9)
(10)
subject to A(X)= = b.
subject to (I)4 1
The subspace is given by linear equations A(X) = b and linear operator A R + R can be a random sampling operator. The dual for the nuclear norm I| is the operator norm |- The problem in (9) has been initially introduced as heuristic method for seeking minimum rank solutions to linear matrix equations, but has later been shown have theoretical guarantees under certain conditions on the linear operator A
228 27 32 17]. The Lagrangian dual of (9) is given by (TO), where operator
A" RP [R the adjoint of A.
We write down an instance of (9) in (TT) below to better reflect the specifics of our setting. Since the true underlying heat kernel matrix H, is observed only partially with known entries indicated by a collection of index pairs 5 induced by augmentation process, we can form a sampling symmetric matrix W: W = 1 if (i, E Ωt and 0 otherwise, indicating observed entries. Now,
the incomplete kernel matrix can be written down explicitly as H WoH, where @ denotes Hadamard (element-wise) product. The constraint in (9) instantiates A(X) vec @ex(.
min XESI
|
max
T HZ
(11)
ZeRuxd
(12)
subject to vec BecWooX (H)
subject to Z-z-I
We proceed by showing that maximisation of the trace formulation in (12) embraces reconstruction of the incomplete underlying kernel matrix with entries known to us only from the augmentation process and specified by the matrix W.
Proposition 4.1. The trace maximization problem given in is Lagrangian dual of low-rank matrix completion problem in [II.
Rexn + R be sampling vectorization vec W X). By trace of matrix product, we can rewrite the objective as Tr|Z HZ] Tr|āzz [ (vecH) vec((Z)) = bTq..
Proof. First, we show that 12 is an instance of (10). Let linear operator A(X):
The adjoint operator A (q) mat(De (w acts sampling matricization, i.e. it samples and maps back to R=*=; (q) = w and the constraint of the dual (10) becomes || ZZ
s 1.
As Z admits singular value decomposition Z U.V the constraint in 12 Z Z o, (Z) for all i.
I implies
To establish equivalence of the constraints in 10 and 12 i.e. Wozz
(wozz) <
given W and σ (Z) 1, we can use a result for singular values of Hadamard product []. specifically, for k = 1, ,..,, nt are column and row lengths of A, and a 2 02 2 ... 2 on. Let A = W and = Zz then = = VK, yielding 0i oWozZ" S K, where K = Nepocha X is a constant, consequently, can be accounted for by rescaling W and not affecting the maximization. Finally, since (II) an instance of ( we can conclude that (12) is dual to [II
Σ Simm (A O B) < >/
(A))o, where (A) and (A(
This result allows us make use of theoretical guarantees obtained matrix completion in what follows.
4.2 Convergence
is the key notion in the analysis of matrix completion problem. Intuitively, incoherence characterises the ability to extract information from small random subsample of columns in the matrix. More formally, it defined as an extent which the singular vectors aligned with the standard basis.
Incoherence Standard incoherence 7 23 20 17

---

Definition 4.2. Given matrix M E I with rank and SVD M = UEVT, M is said to satisfy the standard incoherence condition with coherence parameter μ if
max
e
S
max 15
II eyles
A0r 1/2
(13)
IS
n1
where e; is the i-th standard basis vector of a respective dimension.
Since the matrix we aim to recover is symmetric, n1 = n2 = n and its left, right singular and eigen- vectors are identical. The coherence parameter jr = # max [e,12 range from 1 (incoherent) to
(coherent).
To the best of our knowledge, optimal sample complexity bounds for matrix recovery via nuclear norm minimisation were obtained in [T0]_ Specifically, given M satisfies standard incoherence condition (3) with parameter μ., if uniform sampling probability p" 2 coprrog (m)//// for some co >
then M is the unique solution to ① with high probability.
Matrix recovery is easy when it is highly incoherent when information is spread more uniformly among its columns/rows, loosing a random subset of its entries is not as big of a deal as when information is concentrated in certain important columns/rows. On the other hand, high incoherence intuitively makes matrices harder when used as feature matrices in downstream tasks. This might explain why typical SSL methods rely on the output of backbone network (representations) rather than the output of projection head (embeddings).
It is easy to see that downstream performance depends on the alignment of the target matrix Y with the left eigenvectors of the feature matrix X. The target matrix Y in downstream classification task is typically a very simple binary matrix, and can be shown to have low incoherence. However, whenever X is obtained as the projection head output of a network learned via self-supervised learning method with spectral embedding type objective, the incoherence of X is inherently tied to the incoherence of the kernel matrix. The latter needs to have high incoherence to be recoverable. Consequently, we put forward the following proposition and find its empirical support in Section 5.2
Proposition 4.3. Projection head outputs (embeddings) yield lower performance on the downstream task due to their high incoherence. The complexity of the projection head correlates with coherence of the backbone output (representations).
Only a fraction of total entries in H2 is required for matrix recovery with high probability. We can further narrow down the bound on p" if we consider structured matrix completion problem in the form of some side information which has a direct connection self self-supervised setup. Let the column/row space of M lie in some known r'ddimensional subspace of IR." spanned by the columns of U. n r' 2 r. Then the nuclear norm minimization problem transforms into:
min |X||-
subject to (ÜXū 0ug = MMj, (1
(14)
In practice, we use neural network parameterisation to learn the heat kernel map, this choice inadvertently restricts the reconstructed kernel to be aligned with the column space of the network outputs, bringing the inductive bias of the architecture into picture.
The optimal sampling complexity bound for [14 extends as p" 2 (og(F))((F)) log n/n², where f and F are the coherence and the rank of U, respectively. Suppose we wanted recover some binary adjacency matrix A, such that Aij = 1 if i, belong to the same cluster, otherwise. Because A can be rearranged be block diik-diaaonna with blocks, its coherence μ(A) = 2/rnmins and exact
reconstruction is possible provided
(15) where mmii is the minimal cluster size. Heat kernel matrix constructed from such A will have its eigenspectrum closely resembling that of A, albeit smooth, yet still having same pattern in eigengaps. So we may safely adopt this bound for H,. For balanced class datasets M.nin n/c, and we can immediately see that the number of required observations m = =p"n² cpr log (ār) log n grows linearly with the number of classes e in the dataset.
p² Z pF (ol((((F)) log m//nmmin:
For illustrative purposes we plot the theoretical bound p" on the fraction of the observed entries for successful matrix completion from 15 in Figure I along with the actual fraction p of observed
7

---

Table 1:
Performance comparison for the trace maximization formulation (RQMIN) and VICREG. Mean and standard deviation for validation set accuracy across 5-10 runs for CIFAR- 10, CIFAR- 100 and ImageNet-1000
CIFAR- 10
CIFAR- 100
ImageNet- 100
top-1 1
top-5
top-1
top-5
top-1
top-5
VICREG
91.15 2016
99.64
= 0.5
67.57 0:00
89.90
= 0.13
78.89
a.3
93.94
2.177
RQMIN
91.19 0..13
99.67 0.04
68.12 0.66
90.12
78.98 0.3
94.45
entries under self-supervised learning augmentation protocol to demonstrate that the latter intercepts the former given enough training epochs. To be specific, we set the size of the training dataset N 50k (CIFAR-I0 size), the cluster size (number of same class examples) Amiin. 5000
10), the number of views a = 2, the number of epochs Nhepoch range from 1 to 1000, and r = 512 (embedding size), assume μ 20 (which seems to be a fair estimate in light of the experiments in Section 5) and co = 5, a constant used to control the probability of exact matrix recovery.
Based on this bound, we highlight the following factors that play important role in the success of any SSL method with spectral embedding type objective. The choice of the similarity function affects the incoherence parameter in the bound. The number of samples per class (alternatively the minimal cluster size mmin) should also be high enough for p" to decrease rapidly. Finally, though potentially in contrast the empirical observations (higher d on ImageNet yields higher downstream performance), the rank r, effectively the dimension of embedding d, should not be too large.
Experiments
First, we verify that the performance of the proposed formulation in and the corresponding loss function, denoted RQMIN, is at least on par with the state-of-the-art methods. We then study the effect of the complexity of the projection head on the incoherence and its connection with the downstream performance of the backbone against projection head outputs.
Here we report the training hyperparameters for all of the experiments, As VICReg is extremely sensitive to the choice of hyperparameters (e.g. increasing learning rate with increased batch size negatively affects training learning diverges), we adopt the same hyperparameters for training RQMIN for fair comparison. We follow the standard VICReg protocol adopted and finetuned for CIFAR- -IFAR-10/100 and ImageNet-1000 in the library for self-supervised learning methods for visual representation learning solo-learn [12]
We train ResNet-18 18 backbone architecture with 3-layer MLP projection head (respective hidden dimensions: 2048-2048-2048) The batch size is 256 for CIFAR datasets and 512 for ImageNet- 100. For pretraining, the learning rate schedule is linear warm-up for 10 epochs and cosine annealing, the optimizer is LARS with learning rate 0.3. For linear probe training. SGD with step learning rate schedule with steps at 60 and 80 epochs. The number of pre-training epochs is 1000 for CIFAR and 400 for Tet 100, downstream training 100 epochs.
5.1 Comparable performance
To demonstrate that our trace maximization objective is on par with existing SSL methods, we test our objective in (4) on standard ResNet-18 18 backbone neural network with 3-layer MLP projection head and obtain comparable results on CIFAR-10, 10, CIFAR-100, and ImageNet- to state-of-ar -rrt methods. As most of the latter yield almost identical performance given enough hyperparameter tuning, we pick VICREG as a representative to compare against. Following the standard protocol respectively,
with 1000 and 400 pre-training epochs for both CIFAR datasets and for ImageNet- linear probe for downstream evaluation is trained for 100 epochs. We do not tune hyperparameters and use default values. Mean and standard deviation for downstream accuracy across 5-10 trials with different seed values are reported in Table I
8

---

incoherence vs projection layers
projection head vs backbone
12
emb
Pep
15
RQMIN
10
VICREG
P
8
10
6
4
1
2
3
4
74
76
78
80
layers
accuracy
Figure 2: (left) Coherence of the backbone outputs (representations) grows with the increasing number of layers in the projection head. (right) Downstream accuracy versus incoherence. Green marks show downstream performance and incoherence of embeddings, blue marks representations. Embeddings and representations of the same type of model are almost always separable in these coordinates: embeddings cxhibit lower performance and lower coherence (small while representations perform better and have higher coherence (large μt).
5.2 Incoherence effect on downstream performance
To test whether incoherence could explain the performance disparity between the outputs of the backbone, termed representations, and the projection head, known as embeddings, we train several models with various configurations of projection heads against SSL objectives on the ImageNet-100 dataset and calculate incoherences of representations and embeddings along with respective downstream accuracies. The performance of the representations and embeddings of the pre-trained model is evaluated in a downstream classification task, while incoherence μ for both candidates is estimated on the training set.
Since the dimensionality of representations and embeddings differ, i.e. 512 for backbone output and 2048 for projection head output, need to pick the rank compute μ accordingly. The common way to pick rank in the numerical methods is through tolerance, i.e. thresholding based on the values of the normalized singular values, i.e. of = o E, Otherwise, one could use the notion of effective rank [30), given by re (A) exp(H (o)). where the entropy H(o)) E, a, log(o,) with vector of singular values a. Overall, we compute coherence as the following expression:
(AA) = Te (A) I5iS(r.]
max a
Incoherence and projection head complexity. (left), we embed the training set of ImageNet-100 to get representations matrix A E 2215952xx122 and compute incoherence pi A) using effective rank r. (A). We embed the training using three distinct pre-trained models for each of the projection head configurations characterized by the number of layers / 2,3, 3, 4}. and average the values across ten embedding runs. The resulting mean and standard deviation plot suggests that incoherence (low μ)) is higher for more shallow projection heads and decreases (/4 grows) as the number of layers in the head increase, a result we anticipated.
To estimmate coherence of representations in Figure
Embeddings and representations disparity. Figure 2 (right) plots distinct models representations and embeddings in the diamonds for VICREG and squares for RQMIN. While blue colour signifies the position of each model's 's representations, the green colour reflects the corresponding embeddings. Both objectives demonstrate a separation of the embedding (low coherence, low accuracy) and representation (high coherence, high accuracy) points, which is more distinctive in the case of RQMIN (squares).
plane. It encodes different type of loss with shape:
The resulting plots support our hypothesis in Proposition 4.3 that incoherence indeed plays a crucial role in explaining the use of the backbone outputs. For successful matrix completion, high incoherence of the partially observed affinity matrix is essential. However, for the downstream performance the representations, the opposite is preferred. The projection head functions disentangling buffer, enabling the representations to maintain low incoherence. Conversely, the embeddings inherit the incoherence of the affinity matrix.
While incoherence seems to be an attractive candidate for unsupervised embedding evaluation metric in scenarios with little to no test data, one should use caution as the coherence value does not reflect

---

the amount of relevant information stored in the matrix of embeddings due to normalization with reference its rank. This idea has been explored in 35 on embeddings of supervised models.
Related Work
38 39], especially in the domain of computer vision received great amount of attention since the learned representations ended up respecting the semantics of the data. There has been a great interest in trying to understand the inner workings of the seemingly heuristic objectives since.
Recent success of self-supervvsed methods [9 15
18 a particularly related to this work concurrent body of literature has adopted the view of the kernel or laplacian-basee spectral representation learning [1, [1) which we also share in this work. We highlight our main difference the results provided in these very recent papers. [ does brilliant job connecting and characterizing modern SSL methods into classical existing counterparts. However, does not answer an important question whether an incomplete priori knowledge about the data manifold stemming from augmentations can provide a good approximation to essentially nonlinear dimensionality reduction methods such as LLE 29
While there are many lenses one may take up to study the problem 21
37
MDS 24. and kernel PCA 3T
We not only show SSL methods to have an objective function similar to the objectives of classical spectral decomposition methods, e.g. LaplacianEigenmapp B], but also try address the problem of incomplete and noisy measurements that we get as an inductive bias during the augmentation process. We hope that this perspective via the low-matrix completion problem will yield further theoretical results on the success of self-supervised learning and practical benefits when applying these methods in the wild, e.g. in domains such medical imaging (16) and hard sciences 25
7 Conclusion and Future Work
In this work, we make an attempt to bridge modern self-supervised methods with classical Laplacian-based dimensionality reduction methods and low-rank matrix completion in hopes to provide theoretical insights on the recent successes of SSL. methods.
We show that these methods are not only doing Laplacian based nonlinear reduction but are able to approximate and recover the truncated version of the underlying Laplace operator given only noisy and incomplete information from augmentation protocol by adopting low-rank matrix completion extensive literature and results. However, when working with datasets with potentially large number of classes, it might be good idea to consider whether the size of the sample is large enough that the minimal cluster size allows the full data matrix to be considered low-rank, otherwise the SSL methods would possibly fail to converge.
We also spot direct influence of the inductive bias in the parameterization of the learned map on the column space of the recovered matrix. We also hypothesize that the disparity in downstream performance between backbone and projection head outputs can be explained by the high incoherence if the latter which is tied to the incoherence of the kernel one is recovering during training. The kernll should have high incoherence to be recoverable.
One of the possible avenues for future work stems from the notion of incoherence. We see it in exploring incoherence property of different types of the similarity or weighting functions one may use to instantiate the adjacency matrix with.
We hope that this work paves the way for deeper study of the connection between self-supervised methods and classical problems such as matrix completion to yield better practical and theoretical understanding of various applications of SSL in different domains, not only computer vision.
References
[1] Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learning recover global and local spectral embedding methods. arXiv preprint arXiv:2205. 1508, 2022.
IO
10

---

[2] Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: Saniance-invariance--oo regularization for self-supervised learning. arXiv preprint arXiv: 2021. []
[3] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373-133 1396, 2003.
10
[4] Mikhail Belkin and Partha Niyogi. Convergence of laplacian eigenmaps. Advances in neural information processing systems, 19, 2006.
[5] Mikhail Belkin and Partha Niyogi. Towards theoretical foundation for laplacian- based manifold methods. Journal of Computer and System Sciences,
2008 2
[6] Pierre Bérard, Gérard Besson, and Sylvain Gallot. Embedding riemannian manifolds by their heat kernel. Geometric & Functional Analysis GAFA, 4(4):373-398, 1994.
[7] Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization.
Communications of the ACM, 55(6):111-119) 2012.
[8] Emmanuel Candes and Benjamin Recht. Simple bounds for recovering low-complexity models. Mathematical Programming, (41(1-2):577-588, 2013.
[9] Ting Chen, Simon Korbllith, 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. [0
[10] Yudong Chen. Incoherence-optimal matrix completion. IEEE Transactions on Information Theory, (1):29900 2923, 2015. 7
[11] Ronald R Coifman, Stephane Lafon, Ann B Lee, Mauro Maggioni, Boaz Nadler, Frederick Warner, and Steven W Zucker. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. Proceedings of the national academy of sciences,
102(21):7466-4431 2005. 3
[12] Victor Guilherme Turrisi da Costa, Enrico Fini, Moin Nabi, Nicu Sebe, and Elisa Ricci. solo-learn: A library of supf-vupe methods for visual representation learning. Journal of Machine Learning Research, 23(56):1-6, 2022.
[13] Zhijie Deng, Jiaxin Shi, Hao Zhang, Peng Cui, Cewu Lu, and Jun Zhu. Neural eigenfunctions are structured representation learners. arXiv preprint arXiv:2210. 12637, 2022. TO
[14] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2021.
[15] Alcksandr Ermolov, Aliaksandr Siarohin, Enver Sangineto, and Nicu Sebe. Whitening for self-supervised representation learning. In International Conference on Machine Learning, pages 3015-3024. PMLR, 2021. I0
[16] Marc Fischer, Tobias Hepp, Sergios Gatidis, and Bin Yang. Self-supervised contrastive learning with random walks for medical image segmentation with limited annotations. Computerized Medical Imaging and Graphics, page 102174, 2023. I0
[17] David Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory, 57(3):
2011. R6
[18) 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:5000-5011, 2021. 10
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015.
[20] Prateck Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory
of computing, pages 665-674, 2013. 6
[21] Li Jing, Pascal Vincent, Yann LeCun, and Yuandong Tian. Understanding dimensional collapse in contrastive self-supervised learning. arXiv preprint urXiv:2110.09444 2021. IO
[22] Daniel D Johnson, Ayoub El Hanchi, and Chris Maddison. Contrastive learning can find an optimal basis for approximately view-invariant functions. arXiv preprint 10.00:2210.0/883
2022. [0
11

---

[23]
Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from few entries. IEEE transactions on information theory, 56(6):9900-299, 2010. 6
[24] Joseph Kruskal. Multidimensional scaling by optimizing goodness of fit nonmetric hypothesis. Psychometrika, 29(1):1-27, 1964. TO
[25] David Pfau, Stig Petersen, Ashish Agarwal, David GT Barrett, and Kimberly L Stachenfeld. Spectral inference networks: Unifying deep and spectral learning. arXiv: 02215, 2018. [0
arXiv preprint
[26] Jacobus Portegies. Embeddings riemannian manifolds with heat kernels and eigenfunctions. Communications Pure and Applied Mathematics, 69(3):478-518, 2016. 3
[27] Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
[28] Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rante solutions of
linear matrix equations via nuclear norm minimization. SIAM review, 52(3)471-501, 2010. [
6
[29] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 29065500):2333-23333 2000. TO
[30] Olivier Roy and Martin Vetterli. The effective rank: A measure of effective dimensionality. In
2007 15th European signal processing conference, pages 606-610, IEEE, 2007. |
[31] Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Nonlinear component analysis kernel eigenvalue problem. Neural computation, 10(5):1299-13199 1998. [0
[32] Abiy Tasissa and Rongjie Lai. Exact reconstruction of euclidean distance geometry problem using low-rank matrix completion. IEFE Transactions on Information Theory, 65(5):3124-3144, 2018.
6
[33] Yuandong Tian. Deep contrastive learning is provably (almost) principal component analysis.
arXiv preprint arXiv:2201.12680 2022. I0
[34] 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. 10
[35] Anton Tsitsulin, Marina Munkhoeva, and Bryan Perozzi. Unsupervised embedding quality evaluation. arXiv preprint vrXiv:2305.16562 2023. [0
[36] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395-416.
2007. L
[37] Yifei Wang, Qi Zhang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Chaos is a ladder: A new theoretical understanding of contrastive learning via augmentation overlap. arXiv preprint
arXiv:2203. 13457, 2022. TO
[38] Chun-Hsiao Ych, Cheng- Yao Hong, Yen-Chi Hsu, Tyng-Luh Liu, Yubei Chen, and Yann LeCun. Decoupled contrastive learning. arXiv preprint mrXiv:2110.066 06848, 2021.
5 10
[39] Jure Zhontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins:
Self-supervised learning via redundancy reduction. In International Conference on Machine Learning, pages 2310-12320. PMLR, 2021. 10
12


Reviews:
[{"review_id": "QnQKdOvhf3", "reviewer": "Reviewer_1mcz", "summary": "The authors observe that self-supervised learning (SSL) attracts growing attention and that, by now, numerous corresponding loss functions have been proposed. They systemize these from the point of view of Laplace operators (on Riemannian manifolds) and low-rank matrix approximation. Indeed, for SimCLR, BarlowTwins, and VICReg they show that these learn eigenfunctions of a Laplacian. They also demonstrate that models trained w.r.t. related trace maximization objectives reach performances that are on par with those resulting from modern SSL techniques.", "questions": "-", "limitations": "Given the scope of the paper (bridging a gap between modern learning techniches and classically \"well known\" models), I can't see any practical limitations. Neither are there any concerns regarding negative societal impact. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper is a blast from the past in the best possible sense. More rigorous theoretical underpinnings of recent self-supervised learning models are still very much lacking and this paper makes considerable progress in this regard and shows a connection to low-rank-matrix completion tasks. This contribution is theoretically rigorous and technically sound and solid. It also shows that “well known” trace maximization objectives lead to model which reach performances that are on par with those resulting from modern SSL techniques.", "weaknesses": "A minor point of criticism is that several interesting experimental findings are deferred to the supplementary material.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind and perceptive feedback.\n\nWe sincerely appreciate the reviewer’s high opinion of the strengths of this submission. We hope that additional experimentation results (attached as PDF, summarized in the global response) will only help reinforce this position. We will find a way to incorporate all interesting experimental findings in the main body."}, {"review_id": "PmHOFZLfBW", "reviewer": "Reviewer_JcEa", "summary": "This paper aims to provide a theoretical understanding of the recent successes of self-supervised learning methods by leveraging tools like Laplacian-based dimensionality reduction methods and low-rank matrix completion. The authors introduce an eigen-problem objective for spectral embeddings from graphs, which is used to interpret modern self-supervised learning methods.", "questions": "Could this approach help to understand the inner working of Large Language models (LLMs)?", "limitations": "The paper needs more numerical experiments. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Using an eigenproblem objective for spectral embeddings derived from graph augmentations, the authors explain the workings of contemporary self-supervised learning methods. This offers a fresh lens to understand self-supervised representation learning.\n2. The paper further shows that self-supervised learning techniques can concurrently execute Laplacian-based nonlinear dimensionality reduction and low-rank matrix completion. This dual functionality further explains the success of self-supervised learning methods.\n", "weaknesses": "The approach presented in the paper is significantly dependent on the incoherence between the outputs of the backbone and the projection head.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback!\n\nFirst, we would like to address the concern about the dependence on the incoherence between the backbone and the projection head.\n\nWe first would like to clarify that the underlying assumption for learning useful representations is that the similarity/kernel matrix of the data is somehow aligned with the downstream task. For example, if the measure of similarity between objects is ‘orthogonal’ to the downstream task, then we cannot hope to extract useful information into the representations.\n\nHowever, there is another aspect of whether we can produce useful representations. In this work, we argue that modern SSL methods perform spectral embedding and low-rank matrix completion. Successful matrix completion relies on the high incoherence of the matrix we want to complete. As all the methods considered in the submission could be seen as performing spectral decomposition, the produced representations inherit the incoherence of that matrix. We argue that this incoherence phenomenon could explain why the projection head is not used in the downstream tasks.\nAll in all, we could summarize the above by saying that the problem itself and thus all considered SSL methods assume and rely on the underlying similarity/kernel matrix to be incoherent and thus recoverable.\n\nWe would also like to note that we conducted more experiments with our trace maximization formulation and present the results in the PDF attached to the global response.\n\nRegarding the question about the inner workings of the large language models, we are enthusiastic to explore if this approach could offer insights into the representations learned by LLMs — one may find many similarities in the sense many NLP approaches are based on pretext tasks. However, now we cannot meaningfully elaborate on this matter further."}, {"review_id": "TkwJcmGvxs", "reviewer": "Reviewer_LpdS", "summary": "Self-supervised learning methods can effectively leverage limited signals to converge towards meaningful representations, but how is it made possible? This paper tries to give a response. This paper establishes a connection between SSL and a matrix completion problem by showing that these are Lagrangian dual of each other. This further implies that optimizing the SSL objsective simultaneously entails reconstructing the kernel matrix. This leads to some theoretical findings, including:\n\n- The trace maximization formulation entails several popular SSL methods: SimCLR, BarlowTwins, VICReg.\n- A less incoherent matrix is easier for matrix recovery, which explains why typical SSL methods rely on the representations (the incoherence is low) rather than the embeddings (the incoherence is high).\n\nBased on the theoretical insights, this paper proposes a trace maximization objective for SSL (eq. 4). Following are some findings from experiments:\n\n- The trace maximization objective is on par with existing SSL methods.\n- There is a negative correlation trend between the incoherence and the number of layers in the projection head.\n- The experiment findings support the hypothesis in proposition 4.3 — that incoherence indeed plays an important role in explaining the use of the backbone outputs.", "questions": "- Figure 2: What is RQ loss?\n- I’m not familiar with the SSL literature (I’m working on NLP), so the roles of the representation vs embedding appears differently from what I thought. Apparently, the representation is directly acquired from the backbone layers and is closer to the input. The embedding is further away from the input. In NLP, however, the embedding is the one that is closer to the input. But once I get my head around this discrepancy of terminologies, I see that many intuition and findings of this paper makes sense.", "limitations": "I do not see negative potential societal impacts of this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- This paper proposes a novel, matrix completion formulation for SSL that can entail several popular SSL methods.\n- The analysis of the matrix completion formulation provides insights about various parts of SSL.\n- Empirically, the trace maximization objective leads to performances on par with other approaches.", "weaknesses": "I have some minor points about the usage of terminologies — please refer to the comment section below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their perceptive feedback.\n\nThe review offers a very well-structured and observant summary of the submission. We would like to add an additional comment about the incoherence and the role of the projection head. We think there might be a typo in the following ---\n*''A less incoherent matrix is easier for matrix recovery, which explains why typical SSL methods rely on the representations (the incoherence is low) rather than the embeddings (the incoherence is high)''*,\nbut to be on the safe side, we would like to elaborate more.\n\nHigher incoherence intuitively means that information is *not* stored in the few important entries. Randomly sampling an incoherent matrix for a few of its entries will reveal more information than sampling a coherent one, which renders low-rank incoherent matrices possible to complete. Since common SSL methods train representations such that they recover spectral decomposition, the embeddings inherit this presumably high incoherence. But our proposition is that higher incoherence of representations makes them hard for downstream tasks. We posit that a projection head might play a buffer role for representations to be less incoherent and thus easier for downstream tasks.\n\nNext, we answer the reviewer's questions:\n- The RQ loss is a naming artifact, it denotes the trace maximization formulation. We apologize for this typo! We will change the notation accordingly.\n- Indeed, the terminology in NLP and SSL diverges in this regard causing confusion. We tried to compensate for that by reiterating the meaning of the used terminology in the submission as often as possible. We want to thank the reviewer for their patience and persistence!\n"}, {"review_id": "Nre3PkhUgi", "reviewer": "Reviewer_2Q8M", "summary": "In this paper, the authors provide theoretical analysis on convergence and downstream performance of self supervised representation learning (SSL) approaches using tools from low-rank matrix completion. \n\nIn particular, (i) they relate an eigenproblem objective to SSL methods, (ii) find that SSL methods perform a conjunction of laplacian embedding and low rank matrix completion, (iii) relate SSL augmentations to the number of observed entries required in matrix completion and (iv) provide some experimentation around incoherence as it relates to downstream performance.", "questions": "- Details on the experimentation run for CIFAR-10 would be helpful. Only a few short paragraphs are presented which claim equivalent performance to VICReg\n- Are there any ways to make use of distributed low-rank matrix completion approaches with theoretical guarantees? (i.e Mackey, JMLR 2015)", "limitations": "- It is unclear how the proposed trace maximization scales in runtime with $N$ and the number of view augmentations\n- Some of the assumptions only hold for the self-supervised case and not the supervised contrastive learning case (i.e. CLIP) such as positive anchor backbone representations being close to one another. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Writing and theoretical exposition is clear\n- Conceptually the trace maximization formulation is elegant. Specifically, the authors provide a broad framework through this line of reasoning to relate commonly used SSL objectives.\n- The results on incoherence are well-aligned to empirical findings on projection head vs backbone representations, provides a potential explanation for this phenomena ", "weaknesses": "- Additional experimentation on performance across the trace maximization approach for small scale datasets would be helpful\n- Further experimentation for the incoherence results in Figure 2 would be helpful, for instance how does incoherence compare across different SSL methods  (i.e. SimCLR, BarlowTwins, etc)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful feedback!\n\nWe would like to start the response by addressing the weaknesses pointed out by the reviewer. We first report additional experiments and details on the performance across small-scale datasets (CIFAR-10, CIFAR-100, and ImageNet-100), followed by additional experimentation for incoherence results. All results are summarized in the attached PDF for convenience. Hopefully, the following answers the concerns raised in the questions and limitations sections of the review. We finish by discussing the distributed low-rank matrix completion approach.\n\nWe have conducted additional experiments for the trace formulation on CIFAR-10, CIFAR-100, and ImageNet-100 along with a comparison to VICReg, one of the commonly used SSL methods. The setup is equivalent to one given in the supplementary materials, we reiterate it here. We use the ResNet-18 backbone with a 3-layer projector with the following dimensions: 2048-2048-2048. Number of the training epochs is 1000 for CIFAR and 400 for ImageNet-100. The batch size for CIFAR-10 and CIFAR-100 is 256, and for ImageNet-100 — 512. We use the LARS optimizer: learning rate = 0.3, weight decay = 1e-4, and momentum = 0.9. The learning rate schedule is cosine annealing with a linear 10-epoch warmup. These hyperparameters are typical for VICReg training (thus favouring VICReg) and we do not adjust them to train our trace maximization formulation.\n\nWhile VICReg has 3 special hyperparameters that weigh individual loss terms, our trace formulation only requires specifying parameter $t$ of the heat kernel, which controls the mass spread across views in a positive pair/set. We fix $t=2$ across all experiments. \n\nWe train each model on a single Nvidia V100 GPU with 16Gb memory. On CIFAR-100, VICReg runtime is 6h 7m, trace formulation - 5h 57m (similar timing difference for other datasets). The trace formulation does not incur additional runtime overhead. Since the approximate heat kernel matrix used in the trace maximization objective is sparse (essentially comprised of $m+1$ unique entries, where $m$ is the number of augmentations used) and can be stored and multiplied efficiently, the method scales similarly to other SimCLR-like methods with increasing batch size and number of augmentations. The major bottleneck for such methods is usually data preprocessing as augmentations are typically CPU-intensive.\n\nBelow, we report the linear evaluation results on the trained models — mean accuracy across 5 and 4 independently learned models (top-1 / top-5) for CIFAR-10 and CIFAR-100, respectively, and 1 run for ImageNet-100 (we hope to add more training runs as they should be finished before the final discussion period ends). The evaluation protocol is standard (please see details in Appendix 8.2).\n\n|      | CIFAR-10 | CIFAR-100      | ImageNet-100 |\n| ----------- | ----------- | ----------- | ----------- |\n| VICReg      | 91.15 / 99.64       | 66.76 / 89.39      | 79.28 / 94.64       |\n| Ours   | 91.19 / 99.67        | 67.35 / 89.91   | 78.36 / 94.3        |\n\nThese results are comparable to state-of-the-art even without any tuning for more favourable hyperparameters.\n\nPlease see the attached PDF for Figure 1 and its caption reporting results on the incoherence across three commonly used SSL methods: SimCLR, BarlowTwins, and VICReg.\n\nRegarding the question about distributed low-rank matrix completion, indeed, there is an immediate connection between distributed low-rank MC and the stochastic gradient descent in SSL in the sense that they both perform a random sampling of the submatrices. While the distributed MC performs optimal approximations for all of the sampled submatrices simultaneously and adopts their averaging as a final step, in SSL typically one processes random batches sequentially. While the goal of the latter method is to provide matrix reconstruction or its low-rank factors, SSL aims to learn the parameterized function that computes a set of eigenfunctions at a given point. We could adopt the distributed approach in SSL since the underlying approximation step is differentiable as we still need to facilitate a learnable mapping.\n\nThis review was particularly helpful in enhancing the submission and we hope that our response comprehensively addresses the concerns the reviewer had regarding our work.\n"}]

Author rebuttal:
We would like to thank all the reviewers for their time, effort, and considerate reviews! 

While we will address each review individually, in this global response, we would like to summarize the main pieces of those individual responses.

First of all, we would like to present more experimental results concerning the performance of the trace objective and the incoherence tested on common methods (SimCLR, BarlowTwins, and VICReg). We have compiled them into a PDF for your convenience. There, Table 1 reports the top-1 and top-5 downstream accuracy (mean and standard deviation across 3-5 runs) of our proposed formulation (Ours) and VICReg across three datasets: CIFAR-10, CIFAR-100, and ImageNet-100. In short, the performance of the proposed objective is comparable to the state-of-the-art.

Meanwhile, Figure 1 reports incoherence vs accuracy results for SimCLR, BarlowTwins, and VICReg on the same architecture and training/testing configuration. All methods reveal similar behaviour — backbone outputs are less incoherent and have better downstream performance, while projection head outputs have high incoherence and worse downstream performance. We caution, however, that incoherence should not be used to compare methods/models since it is not indicative of the information load in the representations/embeddings, which would typically be measured by metrics based on matrix rank.

While we do not necessarily strive to overtake the state-of-the-art — we do not optimize the hyperparameters in our favour, we would like to emphasize the importance of establishing the connection of augmentation-based self-supervised methods to spectral embedding methods and low-rank matrix completion, which our submission aims to provide. This connection also hints at the reason why one typically disposes of the projection head once the model is trained and used in a downstream task. We posit that incoherence of the matrix that one tries to recover is behind it and find empirical support for this phenomenon.

The reviews were instrumental in enhancing the presentation, shaping new experiments, and finding additional insights. We hope that our response provided better clarity on the submission, resolved any confusing aspects, and provided convincing reasons for a potential score increase.


Meta-review: This paper studies SSL methods & their effectiveness by providing a theoretical analysis using Laplacian and low-rank matrix completion methods. The objective is well motivated, proposed approach is definitely a nice & stand-out contribution (among a plethora of existing empirical results from common “transformer-X applied to task-Y” style studies), and a good direction towards better understanding why SoTA SSL methods “just” work. The authors also do a nice job in clarifying & addressing some of the concerns raised by reviewers in their comments such as runtime complexity, the effect of incoherence across different settings. 

A few areas & suggestions where the paper can improve and benefit from more detailed discussion/analysis is a) provide empirical results on more benchmark datasets/tasks, b) validate how the expected behavior conforms (or not) for larger models & more complex  tasks, c) adding more details (perhaps in future / discussion section) on the connection w/ approximations (distributed low-rank MC and other approx. from MC literature) & how this could be extended to other domains/tasks (for instance, when there is structure in the output space)

Overall, this is an interesting work & direction and the authors do a good job wrt coming up with a nice theoretical formulation to study the SSL efficacy. The authors are encouraged to use all the provided feedback and incorporate suggestions/comments from discussions to improve the final version of the paper.
Decision: Accept (poster)