Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss
Authors: Jeff Z. HaoChen
Colin Wei
Adrien Gaidon
Tengyu Ma
Venue: NeurIPS 2021 Oral (2021)
Keywords: theory
deep learning theory
unsupervised learning theory
representation learning theory

Abstract: Recent works in self-supervised learning have advanced the state-of-the-art by relying on the contrastive learning paradigm, which learns representations by pushing positive pairs, or similar examples from the same class, closer together while keeping negative pairs far apart. Despite the empirical successes, theoretical foundations are limited -- prior analyses assume conditional independence of the positive pairs given the same class label, but recent empirical applications use heavily correlated positive pairs (i.e., data augmentations of the same image). Our work analyzes contrastive learning without assuming conditional independence of positive pairs using a novel concept of the augmentation graph on data.  Edges in this graph connect augmentations of the same data, and ground-truth classes naturally form connected sub-graphs. We propose a loss that performs spectral decomposition on the population augmentation graph and can be succinctly written as a contrastive learning objective on neural net representations. Minimizing this objective leads to features with provable accuracy guarantees under linear probe evaluation. By standard generalization bounds, these accuracy guarantees also hold when minimizing the training contrastive loss. In all, this work provides the first provable analysis for contrastive learning where the guarantees can apply to realistic empirical settings.

Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss
Jeff HaoChen
Colin Wei Stanford University col invei@stanford.edi
Stanford University jhaoche@sttanfrdd.ced
Adrien Gaidon
Tengyu Ma
Toyota Research Institute adrien. www.gggaiiiiiiglooooo global
Stanford University
tengyuma@stanford edu
Abstract
Recent works in self-supervised learning have advanced the state-of-the-art by relying on the contrastive learning paradigm, which learns representations by pushing positive pairs, or similar examples from the same class, closer together while keeping negative pairs far apart. Despite the empirical successes, theoretical foundations are limited - prior analyses assume conditional independence of the positive pairs given the same class label, but recent empirical applications use heavily correlated positive pairs (i.e., data augmentations of the same image). Our work analyzes contrastive learning without assuming conditional independence of positive pairs using novel concept of the augmentation graph on data. Edges this graph connect augmentations of the same datapoint, and ground-truth classes naturally form connected sub- srbbggrahs. We propose a loss that performs spectral decomposition the population augmentation graph and can be succinctly written as a contrastive learning objective on neural net representations. Minimizing this objective leads features with provable accuracy guarantees under linear probe evaluation. By standard generalization bounds, these accuracy guarantees also hold when minimizing the training contrastive loss. Empirically, the features learned by our objective can match or outperform several strong baselines on benchmark vision datasets. In all, this work provides the first provable analysis for contrastive learning where guarantees for linear probe evaluation can apply to realistic empirical settings.
Introduction
Recent empirical breakthroughs have demonstrated the effectiveness of self-supervised learning, which trains representations on unlabeled data with surrogate losses and self-defined supervision ICC |2!
signals [4] 6
24
35
38
411
(50,
[52]. self-supervision signals in computer vision
often defined by using data augmentation to produce multiple views of the same image. For example, the recent contrastive learning objectives S 12
encourage closer representations for augmentations (views) of the same natural data than for randomly sampled pairs of data.
13
15
Despite the empirical successes, there is limited theoretical understanding of why self-supervised losses learn representations that can be adapted to downstream tasks, for example, using linear heads. Recent mathematical analyses by Arora et al. [3] Lee et al. (28). Tosh et al. E 45 provide guarantees under the assumption that two views are somewhat independent conditioned on the label. However, the pair of augmented examples used in practical algorithms usually exhibit strong correlation, even conditioned on the label. For instance, two augmentations of the same dog image
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Naturl dasa
Hualy
Brittanys
Poy
Augmented 60
Class dog
Beagles
Cass OIT
Birmans
Invertible
D Britomy
Biman
Eigensectors
Features
Figure Left: demonstration of the population augmentation graph. Two augmented data are connected if they are views of the same natural data. Augmentations of data from different classes in the downstream tasks are assumed be nearly disconnected, whereas there are more connections within the same class. We allow the existence of disconnected sub-graphs within a class corresponding to potential sub-classes. Right: decomposition
the learned representations. The representations (rows in the RHS) learned by minimizing the population spectral contrastive loss can be decomposed as the LHS. The scalar ss, is positive for every augmented data H₁. Columns of the matrix labeled "eigenvectors" are the top eigenvectors of the normalized adjacency matrix of the augmentation graph defined in Section 3. The operator @ multiplies row-wise each ss, with the r;-th row of the eigenvector matrix. When classes (or sub-classes) are exactly disconnected in the augmentation graph, the eigenvectors are sparse and align with the sub-class structure. The invertible Q matrix does not affect the performance of the rows under the linear probe.
share much more similarity than augmentations of two different random dog images. Thus the existing theory does not explain the practical success of self-supervised learning.
This paper presents a theoretical framework for self-supervised learning without requiring conditional independence. We design principled, practical loss function for learning neural net representations that resembles state-of-the-ase contrastive learning methods. We prove that, under a simple and realistic data assumption, linear classification using representations learned a polynomial number of unlabeled data samples can recover the ground-trun -ttun labels of the data with high accuracy.
The fundamental data property that we leverage is notion of continuity of the population data within the same class. Though random pair of examples from the same class can be far apart, the pair is often connected by (many) sequences of examples, where consecutive examples in the sequences are close neighbors within the same class. This property is more salient when the neighborhood of an example includes many different types of augmentations. Prior work [4 empirically demonstrates this type of connectivity property and uses it the analysis of pseudolabeling algorithms.
More formally, we define the population augmentation graph, whose vertices are all the augmented data the population distribution, which can be an exponentially large or infinite set. Two vertices are connected with an edge if they are augmentations of the same natural example. Our main assumption that for some proper m E Z+, the sparsest m- m-partition (Definition 3.4 is large. This intuitively states that we can't 't split the augmentation graph into too many disconnected sub-graphs by only removing a sparse set of edges. This assumption can be seen as graph-theoress version of the population data. We also assume that there are very few edges across
continuity assumption different ground-truth classes (Assumption 3.5). Figure [ (left) illustrates realistic scenario where dog and cat are the ground-truth categories, between which edges are very rare. Fach breed forms sub-graph that has sufficient inner connectivity and thus cannot be further partitioned.
Our assumption fundamentally does not require conditional independence and can allow disconnected sub-graphs within a class. The classes in the downstream task can be also somewhat flexible as long as they are disconnected in the augmentation graph. For example, when the augmentation graph consists of m disconnected sub- nubggraphs corresponding to fine- -raiiee classes, our assumptions allow the downstream task to have any r < m coarse -rriined classes containing these fine-grad fine-grained classes as a sub-partition. Prior work 49 on pseudolabeling algorithms essentially requires an exact alignment between sub-graphs and downstream classes (i.e., r m)) They face this limitation because their analysis requires fitting discrete pseudolabels on the unlabeled data. We avoid this difficulty because consider directly learning continuous representations on the unlabeled data.

---

We apply spectral decomposition classical approach for graph partitioning, also known as spectral clustering 37 39 in machine learning- to the adjacency matrix defined on the population augmentation graph. We form a matrix where the top-k eigenvectors are the columns and interpret each row of the matrix as the representation (in RR*) of an example. Somewhat surprisingly, we show that this feature extractor can be also recovered (up to some linear transformation) by minimizing the following population objective which is similar to the standard contrastive loss (Section 3.2
(U) = -2 22 B2 ((x))((())) + Ea (((x) ((x'))
where (x, is a pair of augmentations of the same data, (x,x') is a pair of independently random augmented data, and f is a parameterized function from augmented data to T2 Figure I (right) illustrates the relationship between the eigenvector matrix and the learned representations, We call this loss the population spectral contrastive loss.
We analyze the linear classification performance of the representations learned by minimizing the population spectral contrastive loss. Our main result (Theorem 3.7) shows that when the representation dimension exceeds the maximum number of disconnected sub-graphs, linear classification with learned representations is guaranteed to have a small error. Our theorem reveals a trend that larger representation dimension is needed when there are larger number of disconnected sub-graphs. Our analysis relies on novel techniques tailored to linear probe performance, which have not been studied in the spectral graph theory community to the best of our knowledge.
The spectral contrastive loss also works on empirical data. Since our approach optimizes parametric loss functions, guarantees involving the population loss can be converted to finite sample results using off-the-shelf generalization bounds. The sample complexity is polynomial the Rademacher complexity of the model family and other relevant parameters (Theorem and Theorem 4.2
In summary, our main theoretical contributions are: 1) we propose a simple contrastive loss motivated by spectral decomposition of the population data graph, 2) under simple and realistic assumptions, we provide downstream classification guarantees for the representation learned by minimizing this loss on population data, and 3) our analysis is easily applicable to deep networks with polynomial unlabeled samples via off -he-hff-heef generalization bounds.
In addition, we implement and test the proposed spectral contrastive loss on standard vision benchmark datasets. We demonstrate that the features learned by our algorithm can match or outperform several strong baselines [2]
21 when evaluated using a linear probe.
2 Additional related works
Empirical works on self-supervised learning. Self-supervised learning algorithms have been shown to successfully learn representations that benefit downstream tasks
15 22
24
B5
38
41
42
522) Many recent self-supervised learning algorithms learn features with 50
siamese networks [ where two neural networks of shared weights are applied to pairs of augmented data. Introducing asymmetry to siamese networks either with momentum encoder like BYOL 21 or by stopping gradient propagation for one branch of the siamese network like SimSiam [4] has been shown to effectively avoid collapsing. Contrastive methods 112
15 22 minimize the InfoNCE
loss G8), where two views of the same data are attracted while views from different data are repulsed.
Theoretical works on self-supervised learning, In addition to works 3 28 44 45 the introduction, several other works 55 43 47 48 also theoretically study self-supervised learning. The work Tsai et al. 47 prove that self-supervised learning methods can extract tesk-relevant information and discard fask-irrelevant information, but lacks guarantees for solving downstream tasks efficiently with simple (e.g., linear) models. Tian et al. 43] study why non-contrastive self- supervised learning methods can avoid feature collapse. Cai et al. analyze domain adaptation algorithms for subpopulation shift with a similar expansion condition as 40 while also allowing disconnected parts within each class, but require access to ground-truth labels during training. In contrast, our algorithm doesn't 't need labels during pre-training.
discussed in
3

---

3 Spectral contrastive learning on population data
In this section, introduce theoretical framework, the spectral contrastive loss, and the main analysis of the performance of the representations learned on population data.
We use X' denote the set of all natural data (raw inputs without augmentation). We assume that each & E X belongs one of classes, and let y X + [r] denote the ground-truth (deterministic) labeling function. Let Px be the population distribution over X from which we draw training data and test our final performance. For the ease of exposition, we assume X be a finite but exponentially large set (e.g., all real vectors in R' with bounded precision)
We next formulate data augmentations. Given natural data sample F E X, we use A(- to denote the distribution of its augmentations. For instance, when F represents [12] that includes Gaussian blur, color distortion and random cropping. We use X' to denote the set of all augmented data, which is the union of supports of all A(-(z) for H E X. As with X, we also assume that X' is finite but exponentially large set, and denote N X
image, A(-[z) can be the
distribution of common augmentations
We will learn embedding function f f x and then evaluate its quality by the minimum error achieved with a linear probe. Concretely, a linear classifier has weights B E R and predicts gf. arg m (f((x) (f(x) B); for an augmented data (arg max breaks tie arbitrarily). Then, given a natural data sample F, we ensemble the predictions augmented data and predict:
( == arg max Pr <E(r] s>AA(-12)
[g) = il.
Define the linear probe error as the error of the best possible linear classifier on the representations:
E(f) min Pr BERK
(y(z) + + (T.)(T)]
(1)
3.1 Augmentation graph and spectral decomposition
Our approach is based on the central concept of population augmentation graph, denoted by G(X, w). where the vertex set is all augmentation data X' and w denotes the edge weights defined below. For any two augmented data 2, x' E X, define the weight Wayt as the marginal probability of generating the pair x and x' from a random natural data T Pxi
Wra := EE [A(x|z)A((*) [+)]
Therefore, the weights sum to 1 because the total probability mass is 1: Ex.''E War 1. The relative magnitude intuitively captures the closeness between and x' with respect to the augmentation transformation. For most of the unrelated æ and x', the value waz' will be significantly smaller than the average value. For example, when and x' are random croppings of a cat and dog respectively, Wzr' will be essentially zero because no natural data can be augmented into both x and x'. On the other hand, when and x' are very close in ly-distance very close in Ey-distance up to color distortion, Waz is nonzero because they may be augmentations of the same image with Gaussian blur and color distortion. We say that and x' are connected with an edge if Waxt See Figure D (left) for more illustrations.
Given the structure of the population augmentation graph, we apply spectral decomposition to the population graph to construct principled embeddings. The eigenvalue problems are closely related to graph partitioning shown in spectral graph theory [17] for both worst-case graphs |0| 25 20 33
and random graphs [1 30 <4]
In machine learning, spectral clustering 37 39 is classical algorithm
that learns embeddings by eigendecomposition on the embeddings.
empirical distance graph and invoking k-means
We will apply eigendecomposition to the population augmentation graph (and then later use linear probe for classification). Let w. = Ex'xx War' be the total weights associated to ær which is often viewed as an analog of the degree of x in weighted graph. A central object in spectral graph theory is the so-called normalized adjacency matrix:
Ā : D 1/2 1D1122
(3)
'Thi allows us to use instead of integrals and avoid non-essential nuances related to calculus.

---

where A E R.Vx N is adjacency matrix with entires Age Way and D E RNNN matrix with Dzx W
E is diagonal
Standard spectral graph theory approaches produce vertex embeddings as follows. Let N1, 72, be the k largest eigenvalues of A, and 01, 02, ... Up be the corresponding unit-norm cigenvectors. Let F* [t1, "2,... 2x] E R be the matrix that collects these eigenvectors in columns, and we refer to it as the eigenvector matrix. Let u. E IR* be the æ-th row of the matrix F", It turns out that " 's can serve as desirable embeddings of x's because they exhibit clustering structure Euclidean space that resembles the clustering structure of the graph G(X, w).
3.2 From spectral decomposition to spectral contrastive learning
The embeddings =ž obtained by eigendecomposition are nonparametric-a k-dimensional parameter needed for every æ-aan therefore cannot be learned with realistic amount of data. The embedding matrix F' cannot be even stored efficiently. Therefore, we will instead parameterize the rows of the eigenvector matrix F* as a neural net function, and assume embeddings uy can be represented by f() for some f E F, where F is the hypothesis class containing neural networks. As we'll show in Section this allows us leverage the extrapolation power of neural networks and learn the representation on a finite dataset.
Next, design proper loss function for the feature extractor f. such that minimizing this loss could recover F* up to some linear transformation. As we will show in Section g the resulting population loss function on also admits an unbiased estimator with finite training samples. Let F be an embedding matrix with u, on the z-th row, we will first design a loss function of F that can be decomposed into parts about individual rows of F.
We employ the following matrix factorization based formulation for eigenvectors. Consider the objective
(F) A FF FERNXE
min
(4)
By the classical theory on low-rank approximation minimizer of Cmr(F) contains scaling of the largest eigenvectors of A up to right transformation- for some orthonormal matrix R E g we have F = F diag(l multiplying the embedding matrix by any matrix on the right and any diagonal matrix on the left does not change its linear probe performance, which is formalized by the following lemma.
Yoauurt-oun---iin theorem 19 any
V vx)) Fortunately,
Lemma 3.1. Consider embedding matrix F E N and a linear classifier B E &kxxr, Let D NNNN be diagonal matrix with positive diagonal entries and Q E B be an invertible matrix. Then, for any embedding matrix F = = F Q, the linear classifier = 1110-111pp on F has the same prediction as B on F. As consequence, we have
B(F)=E(T)
(5)
where (FF) denotes the linear probe performance when the rows of F are used as embeddings.
The proof can be found in Section C.I
The main benefit of objective Lmr(F) F)) is that it's based on the rows of F. Recall that vectors are the rows of F. Each entry FFT is of the form u._ xz', and thus (FF(FF can be decomposed into a sum of 2 terms involving terms u. ug.. Interestingly, if we reparameterize each row u, by whs (z), we obtain a very similar loss function for f that resembles the contrastive learning loss used practice [12 as shown below in Lemma 3.2 See Figure I (right) for an illustration of the relationship between the eigenvector matrix and the representations learned by minimizing this loss.
We formally define the positive and negative pairs to introduce the loss. Let B Px be random natural data and draw A(-[E) and + A(-Iž) independently to form positive pair (x.x') x Draw E' ~ Px and ~ A(- independently with ž, x, x. We call (x, x') negative pair
We index the matrix A, D by (a, E X x X. Generally we index N-dimensional axis by x E X. 'Though x and x' are simply two independent draws, call them negative pairs following the literature 3
5

---

Lemma 3.2 (Spectral contrastive loss). Recall that ue is the x-th row of F. Let ug = ws 1/2 [ ) for some function f. Then, the loss function (m)(F) (F) is equivalent to the following loss function for f. called spectral contrastive loss, up to a additive constant:
mat (F) =f + const
where [() _ R [f(x) [(xx]] + By,
(6)
The proof can be found in Section
We note that spectral contrastive loss is similar to many popular contrastive losses instance, the contrastive loss in SimCLR [12] can rewritten as (with simple algebraic manipulation)
12
38
40
50
For
- -f(x) f(x*) + log exp ffxx))(xx))
f(x)))
+ exp (f(z) f(x.))
Here r and + are a positive pair and .1...... In are augmentations of other data. Spectral contrastive loss can be seen removing f(x) fxx+) from the second term, and replacing the log sum of exponential terms with the average of the squares of f [(x) [Ix:). We will show in Section 6 that our loss has a similar empirical performance as SimCLR without requiring a large batch size.
3.3 Theoretical guarantees for spectral contrastive loss on population data
In this section, we introduce the main assumptions on the data and state our main theoretical guarantee for spectral contrastive learning on population data.
To formalize the idea that G cannot be partitioned into too many disconnected sub-gru graphs,, we introduce the notions of Dirichlet conductance and sparsest m-partition, which are standard in spectral graph theory. Dirichlet conductance represents the fraction of edges from S to its complement:
Definition 3.3 (Dirichlet conductance). For graph G = (X' w) and subset S S X, we define the
Dirichlet conductance of S
(G ExES, x'S Wer'
Eves Wz
We note that when S' is a singleton, there is (c(S) = due to the definition of Wg. We introduce the sparsest m- m--artiiton to represent the number of edges between m disjoint subsets. Definition 3.4 (Sparsest m- m-partition). Let G = (X, w) be the augmentation graph. For an integer m E [2, [I], we define the sparsest m-partition as
= min max(oo(S))) da (Sm) S1." S.m.
where *1, Sm are non-emply sets that form partition of X.
When is the number of underlying classes, we might expect p, since the augmentations from different classes almost compose disjoint r-way partition of X' However, for m > we can expect Pm to be much larger. For instance, in the extreme case when m |X| N, every set S, is singleton, which implies that pN = 1.
Next, formalize the assumption that very few edges cross different ground-truth classes. It turns out that it suffices to assume that the labels are recoverable from the augmentations (which is also equivalent to that two examples in different classes can rarely be augmented into the same point).
Assumption 3.5 (Labels are recoverable from augmentations). Let ā. Px and y(ū) be its label. Let the augmentation I A(. assume that there exists a classifier g that can predict y()) given I with error at most a. That is, g(z) y(ā) with probability at least a.
We also introduce the following assumption which states that some universal minimizer of the population spectral contrastive loss can be realized by the hypothesis class.
Assumption 3.6 (Realizability). Let F be a hypothesis class containing functions from to R. assume that at least one of the global minima of L(f) belongs F.

---

Our main theorem bound from above the linear probe error of the features learned by minimizing the population spectral contrastive loss.
Theorem 3.7. Assume the representation dimension k 2r and Assumption 3.3 holds for a
Let F be hypothesis class that satisfies Assumption 3.6 and let Jppp E F be minimizer of L(.). Then, we have
((pop) S (0/Pi//a))
Here use Ö(-) to hide universal constant factors and logarithmic factor in k. We note that when augmentations from different classes are perfectly disconnected in the augmentation graph, in which case the above theorem guarantees the exact recovery of the ground truth. Generally, we expect a to be an extremely small constant independent of k. whereas P[a/2] increases with k and can be much larger than a when & is reasonably large. For instance, when there are sub-graphs that have sufficient inner connections, we expect Pt++1 to be the order of constant because any + partition needs to break one sub-graph into two pieces and incur large conductance. We characterize the Pk s growth on more concrete distributions in the next subsection.
Previous works on graph partitioning that conduct clustering based on the representations of unlabeled data and do not analyze the performance of linear probe (which has access to labeled data). These results provide guarantees on the approximation ratio the ratio between the conductance of the obtained partition to the best partition which may depend on graph size 22 that can be exponentially large our setting. The approximation ratio guarantee does not lead to guarantee on the representations' performance on downstream tasks. Our guarantees are on the linear probe accuracy on downstream tasks and independent of the graph size. We rely on the formulation of the downstream task's labeling function (Assumption (.5) as well as a novel analysis technique that characterizes the linear structure of the representations. In Section C provide the proof of Theorem 3.7 as well as its more generalized version where k/2 is relaxed to be any constant fraction k.
3l often analyze the so-called rounding algorithms
3.4 Provable instantiation of Theorem 3.7 to mixture of manifold data
In this section, we exemplify Theorem on an example where the natural data distribution is mixture of manifolds, and the augmentation transformation is adding Gaussian noise.
Example 3.8 (Mixture of manifolds). Suppose Px is mixture of S d distributions Pi.... Pr. where each P: generated by some k-bi-Lipschits generator Q IRd Rdd some latent variable E TR. with d' d which as mixture of Gaussian distribution:
1 d Iaxxa)) N
P. 2- ==
Let the data uugmentation of natural data sample x H + where & N(0, " Taxa) isotropic Gaussian noise with 0 < < 1
We also assume min;yj ||le Mill2 J
R.ylogd
Vā
Let the ground-truth label be the most likely mixture index i that generates r: y(x) == arg max; (z(z)) We note that the intra-class distance in the latent space on scale of (1(1). which can be much larger than the distance between class means which is assumed to be 2 k. Therefore, distance-
/a
based clustering algorithms do not apply. We apply Theorem 3.7 and get the following theorem:
Theorem 3.9. When & > 2r + 2, Example 3.8 satisfies Assumption 3.5 with S poly(dy and has
P[A/2] 2 v As consequence, the error bound is {(f < δ poly(a)
The theorem above guarantees small error even when a is polynomially small. In this case, the augmentation noise has much smaller scale than the data (which least the order of 1/k). This suggests that contrastive learning can non-trivially leverage the structure of the underlying data and learn good representations with relatively weak augmentation. The proof can be found in Section D
A bi bi-Lipschitz function satisfies 1 +If(x) f(w)l12 & I -e-vlla <<lf(<>) f(w)lla

---

Finite-sample generalization bounds
we provide guarantees for spectral contrastive learning on population data. In this section, we show that these guarantees can be naturally extended to the finite-sample regime with standard concentration bounds. In particular, given training dataset {ō1, Ø2. Fn with ã; Px. we learn a feature extractor by minimizing the following empirical spectral contrastive loss:
In Section 3
2,
2 n1 ΣE
[(x)]] [
E PRAcInD Σ
[((()) [((()) 1n1 =fAACIR))
A()1)
n(n
is worth noting that ( an unbiased estimator of the population spectral contrastive loss L()) (See Claim E.2 for proof.) Therefore, we can derive generalization bounds via off-the-shelf concentration inequalities. Let FF be a hypothesis class containing feature extractors from X to R We extend Rademacher complexity to function classes with high- dimensional outputs and define the Rademacher complexity of F on n data as (F)
max., ExE E. (e((j]) (Ej-1 f)fi(z)))
where a is uniform random vector in {-1, 11" and fi(z) is the i-th dimension of f(z).
Recall that fpop E F is a minimizer of C(f). The following theorem with proofs in Section E.1 bounds the population loss of a feature extractor trained with finite data:
Theorem 4.1. For minimizer of the population loss L(f). Given a random dataset of size let femp F be minimizer of empirical loss (f). Then, with probability at least 1 -8 over the randomness of data, we have
O, assume (z)]l k for all E F and x E X. Let frop E F be
(Vlog 2/5
[(femp) S ((Spp)) c1 (F) + 02
+
n
where constants 6₁ S k2k2 ks and C2 kx² k2
We can apply Theorem 4. to any hypothesis class F. of interest (e.g., deep neural networks) and plug in off-the-shelf Rademacher complexity bounds. For instance, in Section E.2 we give corollary of Theorem 4.1 when F contains deep neural networks with ReLU activation.
The theorem above shows that loss up to some small excess loss. The following theorem characterizes how the error propagates to the linear probe performance mildly under some spectral gap conditions.
achieve near-optimal population loss by minimizing empirical
Theorem 4.2. Assume representation dimension & 2 4r + 2, Assumption 3.5 holds for a >> 0 and Assumption 3.6 holds. Recall "/ the i-th largest eigenvalue of the normalized adjacency matrix. Then, for any c < 72 and femp E such that L(femp) [(pppp) + C, we have:
E(fomp) S a PiK/21
ke
log
AZ'
where Dy :- |3//44 - TTk is the eigenvalue gap between the [3k/4]-th and the k-th eigenvalue.
This theorem shows that the error on the downstream task only grows linearly with the error during pretraining. We can relax Assumption 3.6 approximate realizability in the sense that F contains some sub-optimal feature extractor under the population spectral loss and pay an additional error term in the linear probe error bound. The proof of Theorem 4.2 can be found in Section E.3
5 Guarantee for learning linear probe with labeled data
In this section, we provide theoretical guarantees for learning linear probe with labeled data. Theorem (areorem..7guaraann guarantes the existence linear probe that achieves a small downstream classification emor. However, priori it is unclear how large the margin of the linear classifier can be, so it is hard to apply margin theory to provide generalization bounds for 0-1 loss. We could principle control the margin of the linear head, but using capped quadratic loss turns out to suffice and mathematically more

---

convenient. We learn a linear head with the following capped quadratic loss: given tuple (z, (ā)) where = E IR is a representation of augmented data x: ~ A(-(a) and y(ι) E [r] is the label of I, for linear probe B E IR we define loss (((2,,(z)) B) = - min {B v())) 1), where ((z) is the one-hot embedding of y()) r-dimensional vector (1 on the y )-th dimension, on other dimensions). This is a standard modification of quadratic loss in statistical learning theory that ensures the boundedness of the loss for the ease of analysis 3d
The following Theorem 5.1 provides a generalization guarantee for the linear classifier that minimizes capped quadratic loss a labeled dataset. The key challenge of the proof is showing the existence of a small-norm linear head B that gives small population quadratic loss, which is not obvious from Theorem 3.7 where only small 0-1 error is guaranteed. Recall 7/ is the i-th largest eigenvalue of the the normalized adjacency matrix. Given a labeled dataset ((T;, v(T:))( where Ty ~ Px and (T.)) is its label, we sample x; A(-(a,) for E [n]]
Theorem 5.1. In the setting of Theorem 3.7 assume "ik 2 for some Cx > Learn a linear probe B E arg min Bll S1/Cs, Σi=1 (()fppp(a))) y( loss subject to a norm constraint. Then, with probability at least 8 over random data, we have
B) )) by minimizing the capped quadratic
B-Xx (1))) # v(z)
K V
log 1/6
Pr
x P (1/2)
log k: +
CA
n
Here the first term is the population error from Theorem 3.7 The last two terms are the generalization gap from standard concentration inequalities for linear classification and are small when the number of labeled data is polynomial in the feature dimension k. We note that this result reveals a trade- off when choosing the feature dimension k: when is fixed, a larger & decreases the population contrastive loss while increases the generalization gap for downstream linear classification. The proof of Theorem iis in Section
Experiments
We test spectral contrastive learning benchmark vision datasets. We minimize the empirical spectral contrastive loss with an encoder network / and sample fresh augmentation in each iteration. The pseudo-code for the algorithm and more implementation details can be found in Section A
Encoder feature extractor. The encoder f contains three components: a backbone network, a projection MIP and projection function. The backbone network is standard ResNet architecture. The projection MLP is fully connected network with BN applied to each layer, and ReLU activation applied to each except for the last layer. The projection function takes vector and projects it to sphere ball with radius VTa, where > 0 is a hyperparameter that we tune in experiments. We find that using projection MLP and projection function improves the performance.
Linear evaluation protocol. Given the pre-trained encoder network, we follow the standard linear evaluation protocol 14] and train supervised linear classifier on frozen representations, which are from the ResNet's s global average pooling layer.
Results. We report the accuracy on CIFAR- 10/100 26 and Tiny-ImageNet e in Table ! Our empirical results show that spectral contrastive learning achieves better performance than two popular baseline algorithms SimCLR [12] and SimSiam [1]. In Table 2 we report results on ImageNet [8] dataset, and show that our algorithm achieves similar performance as other state-of-the-as methods. We note that our algorithm is much more principled than previous methods and doesn't 't rely on large batch sizes (SimCLR [22) momentum encoders (BYOL, [1 and MoCo (2 or additional tricks such stop-gradient (SimSiam [4]
7 Conclusion
In this paper, we present novel theoretical framework of self-supervised learning and provide provable guarantees for the learned representations on downstream linear classification. We hope our study can facilitate future theoretical analyses of self-supervised learning and inspire new practical algorithms. For instance, one interesting future direction is to test the topology of the augmentation graph on empirical data distributions and design algorithms using tools from graph theory.

---

Datasets
CIFAR-10
CIFAR- 100
Epochs
200
400
800
200
400
800
200
400
800
SimCLR (repro.)
83.73
87.72
90.60
54.74
61.05
63.88
43.30
46.46
48.12
SimSiam (repro.)
87.54
90.31
91.40
61.56
64.96
65.87
34.82
39.46
46.76
Ours
88.66
90.17
92.07
62.45
65,82
66.18
41.30
45.36
49.86
Table 1: Top-1 accuracy under linear evaluation protocal.
SimCLR
BYOL
MoCo
SimSiam
Ours
(%)
66.5
66.5
67.4
68.1
66.97
Table 2: ImageNet linear evaluation accuracy with 100-epoch pre-training. All results but ours We use batch size 384 during pre-training.
reported from 14
Acknowledgements
We thank Margalit Glasgow, Ananya Kumar, Jason D. Lee, Sang Michael Xie, and Guodong Zhang for helpful discussions. CW acknowledges support from an NSF Graduate Research Fellowship. TM acknowledges support of Google Faculty Award and NSF IIS 2045685. We also acknowledge the support of HAI and the Google Cloud. Toyota Research Institute ("TRI") provided funds to assist the authors with their research but this article solely reflects the opinions and conclusions of its authors and not TRI or any other Toyota entity.
References
[1] E. Abbe. Community detection and stochastic block models: recent developments, 2017.
[2] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):1-37, 2009.
[3] Arora, H. Khandeparkar, M. Khodak, O. Plevrakis, and N. Saunshi. theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv:1902.0922) 2019.
[4] Bachman, R. D. Hjelm, and W. Buchwalter. Learning representations by maximizing mutual information across views. arXiv preprint arXiv: 190.000900000000/000 2019.
[5] Y. Bansal, G. Kaplun, and B. Barak. For self-supervised learning, rationality implies generalization, provably. arXiv preprint arXiv:2010.08500, 2020.
[6] A. Bardes, J. Ponce, and Y. LeCun. Vicreg: self-supervised learning. arXiv preprint arXiv:2105 04900, 2021.
regularization for
[7] S. G. Bobkov et al. An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in gauss space. The Annals of Probability, 25(1):206-214, 1997.
[8] J. Bromley, I. Guyon, Y. LeCun, E. Säckinger, and R. Shah. Signature verification using a" siamese" time delay neural network. Advances in neural information processing systems, 737-744, 1993.
[9] T. Cai, R. Gao, D. Lee, and Q. Lei. A theory of label propagation for subpopulation shift. arXiv preprint arXiv:2 102. /203, 2021.
[10] M. Caron, I. Misra, Mairal, Goyal, P. Bojanowski, and A. Joulin. Unsupervised learning of
visual features by contrasting cluster assignments. arXiv preprint arXiv:2006. 09882, 2020.
[11] J. Cheeger. A lower bound for the smallest eigenvalue of the laplacian. In Proceedings of the Princeton conference in honor of Professor S. Bochner, pages 195-199, 1969.
[12] T. Chen, S. Korbllihh, M. Norouzi, and G. Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597-1607. PMLR, 2020.
10

---

[13] T. Chen, S. Korblith,, K. Swersky, M. Norouzi, and G. Hinton. Big self-supervised models are strong sumi-super learners. arXiv preprint arXiv:2006. 10029, 2020.
[14] X. Chen and K. He. Exploring simple siamese representation learning. arXiv preprint arXiv:2011. 105666, 2020.
[15] X. Chen, H. Fan, R. Girshick, and K. He. Improved baselines with momentum contrastive learning. arXiv preprint arXi:22033.04297, 2020.
[16] C.-Y. Chuang, J. Robinson, I.. Yen-Chen, A. Torralba, and S. Jegelka. Debiased contrastive learning. arXiv preprint arXiv:2007.00224 2020.
[17] R. Chung and F. C. Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
[18] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPRO9, 2009.
[19] C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):1112218 1936.
[20] N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks. Conference On Learning Theory, pages 297-299 PMLR, 2018.
[21] J.-B. Grill, F. Strub, F. Altché, C. Tallec, P. H. Richemond, E. Buchatskaya, C. Doersch, B. A. Pires, Z. D. Guo, M. G. Azar, al. Bootstrap your own latent: A new approach to self-supervised learning. arXiv preprint arXiv:2006.07733 2020.
[22] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9729-97338 9738, 2020.
[23] O. Henaff. Data-efficient image recognition with contrastive predictive coding. In International Conference on Machine Learning, pages 4182-4192. PMLR, 2020.
[24] R. D. Hjelm, A. Fedorov, Y. Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2018.
K. Grewal, P. Bachman, A. Trischler, and
[25] R. Kannan, S. Vempala, and A. Vetta. On clusterings: Good, bad and spectral. Journal of the ACM (JACM), 5133):97-5555 2004.
[26] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. 2009.
[27] Y. Le and X. Yang. Tiny imagenet visual recognition challenge. CS 23/N, 7:7, 2015.
[28] D. Lee, Q. Lei, N. Saunshi, and Zhuo. Predicting what you already know helps: Provable self-supervised learning. arXiv preprint arXiv:2008.0006 2020.
[29] J. R. Lee, S. O. Gharan, and L. Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1-30, 2014.
[30] J. Lei, A. Rinaldo, et al. Consistency of spectral clustering in stochastic block models. Annals of Statistics, 43(1):215-25) 2015.
[31] T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM), 4666)777-88) 1999.
[32] A. Louis and K. Makarychev. Approximation algorithm for sparsest k- k-partitioning. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithmss, pages 1144-1255, SIAM, 2014.
[33] A. Louis, P. Raghavendra, P. Tetali, and S. Vempala. Algorithmic extensions of cheeger's inequality to higher eigenvalues and partitions. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 315-326. Springer, 2011.
11

---

[34] F. McSherry. Spectral partitioning of random graphs. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 529-537. IEEE, 2001.
[35] I. Mísra and L. d. Maaten. Self--uper learning of pretext-invarianl representations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6707-6711 17, 2020.
[36] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018.
[37] A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. Advances neural information processing systems, 14:849-855 2001.
[38] A. d. Oord, Y. Li, and O. Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv: /80.003788 2018.
[39] Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-905, 2000.
[40] K. Sohn. Improved deep metric learning with multi-class n-pair loss objective. Proceedings of the 30th International Conference Neural Information Processing Systems, pages 1857-1865, 2016.
[41] Y. Tian, D. Krishnan, and P. Isola. arXiv: /906:/996.00000 05849, 2019.
Contrastive multiview coding.
arXiv preprint
[42] Y. Tian, Sun, Poole, D. Krishnan, C. Schmid, and P. Isola. What makes for good views for contrastive learning, arXiv preprint PrXiiv2005.10244 2020.
[43] Y. Tian, Yu, X. Chen, and S. Ganguli. Understanding self-supervised learning with dual deep networks. arXiv preprint ar arXiv:2010.00578, 2020.
[44] C. Tosh, A. Krishnamurthy, and D. Hsu. Contrastive estimation reveals topic posterior information to linear models. arXiv:2003. 022334, 2020.
[45] C. Tosh, A. Krishnamurthy, and D. Hsu. Contrastive learning, multi-view redundancy, and linear models. In Algorithmic Learning Theory, pages 1179-1206. PMLR, 2021.
[46] T. W. Tsai, Li, and J. Zhu. Mice: Mixture of contrastive experts for unsupervised image clustering. arXiv preprint arXiv:2105.01899 2021.
[47] Y.-H. H. Tsai, Y. Wu, R. Salakhutdinov, and L..P. Moreney. Self-supervised learning from multi-view perspective. arXiv preprint arXiv:2006.05576 2020.
[48] Wang and Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In International Conference on Machine Learning, pages 9929 9939. PMLR, 2020.
[49] C. Wei, K. Shen, Y. Chen, and T. Ma. Theoretical analysis of self-training with deep networks on unlabeled data. arXiv preprint arXiv:2010.03622, 2020.
[50] Z. Wu, Y. Xiong, S. X. Yu, and D. Lin. Unsupervised feature learning via non-parametric instance discrimination. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3733- 3733-3742, 2018
[51] M. Ye, X. Zhang, P. C. Yuen, and S.-F. Chang. Unsupervised embedding learning via invariant and spreading instance feature. Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 6210-6219, 2019.
[52] J. Zhontar, L. Jing, I. Misra, Y. LeCun, and S. Deny. Barlow twins: Self-supervised learning via redundancy reduction. arXiv preprint arXiv:2 2021.
12


Reviews:
[{"review_id": "tI1DgOccPM2", "reviewer": "Reviewer_N3Yd", "summary": "The paper studies the theoretical foundations of contrastive self-supervised learning. To do so, the authors study contrastive learning through the lens of the augmentation graph - the graph of augmented examples, with edges connecting \"similar\" examples. The authors suggest a novel contrastive loss function, s.t. minimizing this loss is equivalent to spectral clustering on the augmentation graph. Using this, the authors prove that if the augmentation graph has few edges that cross between sub-graphs of different labels, then using a linear readout on the learned representation, a small loss can be achieved w.r.t the supervised objective. The authors also analyze the sample complexity of learning the representation and learning the linear probe from sampled data. Finally, the authors show empirically that the suggested contrastive loss performs similarly to some baseline contrastive loss functions.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think this is a very good paper. It is very clearly written, the results are novel, and give a new characterization of contrastive learning using the augmentation graph. The connection between self-supervised learning, graph theory and spectral clustering is very interesting, and to my knowledge this is the first work that connects these fields. The theoretical results are very clean, and their presentation makes it easy for the reader to understand and appreciate the results.\n\nOne thing that I think is still missing is a sample complexity analysis of learning both the representation and the linear probe. The paper studies the sample complexity of learning the representation, and then using the optimal linear classifier, or otherwise learning the linear probe from a finite sample using the optimal representation. However, in practice self-supervised learning uses large unlabeled data to learn the representation, and then a small labeled dataset to learn the linear classifier. Since the sample complexity is analyzed separately for the representation and the linear probe, it is not clear whether or not we gained anything from using self-supervised learning over supervised learning. That is - we have a trivial sample complexity bound for supervised learning of Bf(x), e.g. using Radamacher complexity. Is this sample complexity larger than the sample complexity of learning only B from labeled data? If so, what is the cost in unlabeled data?\n\nMinor:\nLine 189 - x_{x'} should be u_{x'}", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "hrTltDUYxI", "reviewer": "Reviewer_7GCn", "summary": "This paper derives generalization bounds for learning using a contrastive objective under realistic assumptions on the positive pair generation process. The approach taken is to consider the so-called augmentation graph - the set of nodes comprises all augmented views of population distribution, with edges connecting nodes that correspond to different views of the same input datapoint. The core assumption made is that this graph cannot be split into a large number of disconnected subgraphs. This set-up aligns well with the intuition that in order to generalize, the contrastive notion of “similarity” must extent beyond the purely single-instance-level, and must somehow connect distinct inputs points.\n\nMy view is that this work is the most significant advance in the statistical learning theory of contrastive learning since the paper “A theoretical analysis of contrastive unsupervised representation learning” by Arora et al. This paper under review addresses the primary weakness in the work by Arora et al., which used an unrealistic assumption on positive pair generation. I will strongly advocate for acceptance of this paper.\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n## Discussion:\n\nPrior work on contrastive and/or self-supervised learning theory typically either 1) assumes positive pairs are near-independent when conditioned on class label, or 2) is based on an information theoretic analysis (this is to the best of my knowledge, at least). The first case is clearly unrealistic, and the second suffers from at least a couple of drawbacks - a) the degree to which the success of contrastive learning (particular InfoNCE) can be attributed to its relation to mutual information has been experimentally disputed [1], and b) do not adequately explain why linear probes are sufficient to yield effective downstream performance. \n\nThis paper avoids both of these drawbacks by proposing a new set of assumptions on positive pair generation (which in my view are much more realistic that previous assumption used) and directly analyzing a contrastive loss (which they actually propose in this work) instead of relating contrastive leanring to information theoretic concepts.  \n\n**The assumptions on positive pair generation:**\n\nContrastive learning algorithms work on the level of individual instances - enforcing the similarity of embeddings of different views of *the same* individual instance. Despite this, the performance under linear probe is high on many downstream tasks. This empirical fact strongly indicates that learned encoders must be doing more than learning instance-level invariances. So how does the instance-level approach of contrastive methods extend to enforce relations between the embeddings of distance inputs? \n\nThe paper under review takes a step towards answering this question by showing that under what I consider to be a fairly intuitive set of assumptions (but which are hard to verify empirically) the error of a linear probe can be bounded. The plausibility of these assumptions is the key to this work. If other reviewers are critical, it will almost certainly be due to some misgivings around these assumptions. \n\nAs well as a fresh perspective on the assumptions underlying positive pair generation, this paper imports new tools (from spectral theory) to the analysis of contrastive leanring. The introduction of “new” analysis tools (new in the context of contrastive learning) is welcome in my eyes, and my be of use to others working on the theory of contrastive learning. \n\nI should note that due to time pressure I have not carefully checked the soundness of the proofs. From what I can tell so far I have seen nothing out of order.\n\n---\n## Minor criticisms:\n\nI have already made my overall assessment of this work clear. This section contains minor criticisms.\n\n- The finite sample bounds in Sec 4 are still somewhat separated from the objective used in practice. The finite sample objective in Sec 4 still takes expectations over the augmentation distribution: in practice this is approximated by drawing a single sample. \n- A very minor gripe: there are some suboptimalities in the experimental protocols. E.g. the authors report for SimCLR an accuracy of 46.5% on tinyImageNet with ResNet-50 backbone and 400 epochs of training, and batch size 512. In my own experiments in the past I have obtained over 53% using the same backbone, epochs, and batch size. This isn’t a big deal, though, and the experiments as they are suffice to illustrate the important point - that the proposed spectral loss can learn encoders with comparable performance to other popular methods of the day. \n\n---\n## Clarity:\n\n- l.179 I think R=Q here?\n- l.48 I suppose \\cal Z^+ denotes the positive integers. I would suggest using the more standard \\mathbb{Z}^+, or simply saying “positive integer m” instead. \n\n---\n## Questions: \n- You analysis, like many others, focuses on downstream classification tasks. How might your viewpoint relate to non-classifcation tasks that contrastive methods also enjoy empirically success on - e.g. object detection and image segmentation?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In my view the authors have adequately addressed the limitations and potential negative impacts of their work. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3hrs"}, "extra_text": {}}, {"review_id": "Jn5QVVoEScS", "reviewer": "Reviewer_1aqU", "summary": "The paper studies how does contrastive learning works from a theoretical perspective focusing on the spectral properties of the graph of the data induced by augmentations. They propose a new loss that is close up to a constant to the matrix factorization of the normalized adjacency matrix of the augmentations graph, under some assumptions they show that minimizing this loss provides downstream classification guarantees. Then, using standard Rademacher analysis they move from population guarantees to finite sample guarantees. Finally, they show empirically that their loss gives results close to state of the art. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is interesting and original. Connecting spectral graph theory with SSL is a surprising finding that I would not have foreseen a-priori. Moreover, the theory seems sound to my understanding and the paper is well written and accessible. I have few minor reservations:\n\nThe authors assume that \"G cannot be partitioned into too many disconnected sub-graphs\". This assumption seems rather strong for real data. Every *real* image therefore will be a disconnected subgraph with its augmentations, especially so for high resolution images. Where does this come about in the bounds? As far as I understand this should appear in \\rho in Theorem 3.7. However, for example, if \\alpha is 0 the bound should be 0. This seems unreasonable to me. What am I missing here?\n\nA related issue that I'm wondering about is when does this construction break? Do assumptions 3.5 and 3.6 suffice to guarantee good downstream performance (assuming perhaps that the Rademacher complexity is small)? If so why don't we get 99% accuracy on ImageNet in the experiments? \n\nOther comments:\n* Line 179 I think there is some confusion between R and Q.\n* Line 189 Is this u_x'?\n\n======\n\nI would like to thank the authors for their detailed an enlightening comments that addressed my main concerns. After reading the comments and discussion with the other reviewers I would like to raise my score to 7. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "FTW0BAUdHqQ", "reviewer": "Reviewer_HpLj", "summary": "This paper theoretically analyzes contrastive learning relying on a concept of population augmentation graph. In the graph, two augmented samples are connected if they can be augmented from the same original instance. Based on this setup,\n- This paper shows that spectral decomposition can be reformulated as a contrastive learning objective. Furthermore, this paper shows that minimizing the objective can guarantee a high linear probe accuracy under some mild assumptions.\n- This paper shows the guarantee can be extended to the finite-sample regime and learning the linear probe with labeled data.\n- This paper demonstrates the efficacy of the proposed spectral contrastive objective empirically in the standard setup: the proposed objective achieves similar performance as other state-of-the-art SSL methods.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- This paper is well-written and well-organized. I believe that this paper has good readability for not only theorists but also practitioners.\n- The proposed concept of the population augmentation graph and the spectral decomposition approach is convincing.\n- It seems that Assumption 3.5 is practically reasonable for contrastive learning analysis. This is because SSL methods often assume that two augmented samples have the same semantic (i.e., underlying class) information; in other words, they also assume that correct predictions from the augmented samples are available (with high probability).\n- This paper extends the guarantee (Theorem 3.7) to more practical scenarios. I feel that the result in Section 5 is interesting because the setting is almost the same as the standard linear evaluation benchmark.\n- The proposed spectral contrastive loss shows competitive performance compared to state-of-the-art SSL methods. I think more empirical studies could improve the performance.\n\nConcerns & Questions\n- There is no empirical study related to the theoretical results.\n  - This paper considers $k$ as a fixed constant, but one can choose $k$ arbitrarily in practice. In this case, how can we choose $k$? In Theorem 3.7 and 5.1, there is a trade-off in the upper bound. Therefore, we may need to choose proper $k$ for achieving the best performance. Can we observe the trade-off empirically, as stated in the theorems?\n  - I'm also interested in the $\\rho_k$'s growth because $\\rho_k$ is the main factor of the error bound. Although L246 said that the growth would be characterized in Section 3.4, I cannot fully understand which point explains the growth. Could you provide more details? Also, can we approximate $\\rho_k$ empirically? I wonder whether the error bound is still meaningful in practice or not.\n- What is the role of the projection MLP in a theoretical perspective? The projection MLP is commonly used in self-supervised learning, and this work also uses it in the provided experiments (Section 6). However, the guarantees are obtained without considering the projection MLP.\n- Can we omit $\\log k$ in Theorem 3.7? By definition, $\\rho_k\\le 1$. Also, intuitively, $\\rho_k\\approx 1$ when $k$ is sufficiently large. In this case, the upper bound becomes large due to $\\log k$. In my opinion, it would be better to do not hide $\\log k$ in Theorem 3.7 and do not use the $\\tilde{O}$ notation. This might confuse some readers: for example, one can think the upper bound goes to $\\alpha$ for sufficiently large $k$.\n\nTypos\n- In Eq. (7), the second term might be $f(x)^\\top f(x')$.\n- In L215, Why $\\phi_G(\\{x\\})=1$? In my opinion, $\\phi_G(\\{x\\})=\\frac{\\sum_{x'\\neq x} w_{xx'}}{\\sum_{x'} w_{xx'}}<1$ because $w_{xx}>0$ for any $x\\in\\mathcal{X}$.\n- In Eq. (11), does the second equality hold? I think the $\\sqrt{w_x}$ terms should be in the numerator.\n\n== after rebuttal ==\n\nI sincerely appreciate your efforts to address my concerns. Like other reviewers, I think this paper's theoretical contribution is convincing, and I like the empirical results based on the theoretical findings. Hence, I would like to keep my positive score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. This paper addressed the limitations and potential negative societal impact.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a new theoretical framework for contrastive learning. In particular, the authors find a new type of assumption, connecting spectral graph theory with self-supervised contrastive learning, which is much more realistic than what is common in prior statistical theory for contrastive learning. All reviewers agree on the significance of theoretical contribution provided by the paper. One of major concerns was on the connectivity assumption of the augmentation graph raised by Reviewer 1aqU. As the authors did in their rebuttal, it is quite useful to provide some concrete visual examples in the final draft, to avoid some misunderstanding. AC thinks it is also useful to provide some (real-world or synthetic) scenarios when the assumption breaks, possibly with supporting experiments (to see how much the assumption is crucial). In overall, AC thinks that the paper is very well written and could be a pioneering work, not only for theoretical purposes, but also for some better algorithmic solutions in the future.
Decision: Accept (Oral)