summaries: 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, - 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. - This paper shows the guarantee can be extended to the finite-sample regime and learning the linear probe with labeled data. - 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.  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.  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.  My 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.   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.
abstractText: 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 datapoint, 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. 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.
authors.name: Jeff Z. HaoChen
authors.name: Colin Wei
authors.name: Adrien Gaidon
authors.name: Tengyu Ma
references.authors: E. Abbe
references.title: Community detection and stochastic block models: recent developments, 2017
references.authors: S. Arora S. Rao U. Vazirani
references.title: Expander flows, geometric embeddings and graph partitioning
references.venue: Journal of the ACM (JACM),
references.authors: S. Arora H. Khandeparkar M. Khodak O. Plevrakis N. Saunshi
references.title: A theoretical analysis of contrastive unsupervised representation learning
references.authors: P. Bachman R.D. Hjelm W. Buchwalter
references.title: Learning representations by maximizing mutual information across views
references.venue: arXiv preprint arXiv:1906.00910,
references.authors: Y. Bansal G. Kaplun B. Barak
references.title: For self-supervised learning, rationality implies generalization, provably
references.venue: arXiv preprint arXiv:2010.08508,
references.authors: A. Bardes J. Ponce Y. LeCun
references.title: Vicreg: Variance-invariance-covariance regularization for self-supervised learning
references.venue: arXiv preprint arXiv:2105.04906,
references.authors: S.G. Bobkov
references.title: An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in gauss space
references.venue: The Annals of Probability,
references.authors: J. Bromley I. Guyon Y. LeCun E. Säckinger R. Shah
references.title: Signature verification using a" siamese" time delay neural network
references.venue: Advances in neural information processing systems,
references.authors: T. Cai R. Gao J.D. Lee Q. Lei
references.title: A theory of label propagation for subpopulation shift
references.venue: arXiv preprint arXiv:2102.11203,
references.authors: M. Caron I. Misra J. Mairal P. Goyal P. Bojanowski A. Joulin
references.title: Unsupervised learning of visual features by contrasting cluster assignments
references.venue: arXiv preprint arXiv:2006.09882,
references.authors: J. Cheeger
references.title: A lower bound for the smallest eigenvalue of the laplacian
references.venue: In Proceedings of the Princeton conference in honor of Professor S. Bochner,
references.authors: T. Chen S. Kornblith M. Norouzi G. Hinton
references.title: A simple framework for contrastive learning of visual representations
references.venue: In International conference on machine learning,
references.authors: T. Chen S. Kornblith K. Swersky M. Norouzi G. Hinton
references.title: Big self-supervised models are strong semi-supervised learners
references.venue: arXiv preprint arXiv:2006.10029,
references.authors: X. Chen K. He
references.title: Exploring simple siamese representation learning
references.venue: arXiv preprint arXiv:2011.10566,
references.authors: X. Chen H. Fan R. Girshick K. He
references.title: Improved baselines with momentum contrastive learning
references.venue: arXiv preprint arXiv:2003.04297,
references.authors: C.-Y. Chuang J. Robinson L. Yen-Chen A. Torralba S. Jegelka
references.title: Debiased contrastive learning
references.venue: arXiv preprint arXiv:2007.00224,
references.authors: F.R. Chung F.C. Graham
references.title: Spectral graph theory
references.venue: Number 92. American Mathematical Soc.,
references.authors: J. Deng W. Dong R. Socher L.-J. Li K. Li L. Fei-Fei
references.title: ImageNet: A Large-Scale Hierarchical Image Database
references.venue: In CVPR09,
references.authors: C. Eckart G. Young
references.title: The approximation of one matrix by another of lower rank
references.authors: N. Golowich A. Rakhlin O. Shamir
references.title: Size-independent sample complexity of neural networks
references.venue: In Conference On Learning Theory,
references.authors: 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
references.title: Bootstrap your own latent: A new approach to self-supervised learning
references.venue: arXiv preprint arXiv:2006.07733,
references.authors: K. He H. Fan Y. Wu S. Xie R. Girshick
references.title: Momentum contrast for unsupervised visual representation learning
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: O. Henaff
references.title: Data-efficient image recognition with contrastive predictive coding
references.venue: In International Conference on Machine Learning,
references.authors: R.D. Hjelm A. Fedorov S. Lavoie-Marchildon K. Grewal P. Bachman A. Trischler Y. Bengio
references.title: Learning deep representations by mutual information estimation and maximization
references.venue: In International Conference on Learning Representations,
references.authors: R. Kannan S. Vempala A. Vetta
references.title: On clusterings: Good, bad and spectral
references.venue: Journal of the ACM (JACM),
references.authors: A. Krizhevsky G. Hinton
references.title: Learning multiple layers of features from tiny images
references.authors: Y. Le X. Yang
references.title: Tiny imagenet visual recognition challenge
references.venue: CS 231N,
references.authors: J.D. Lee Q. Lei N. Saunshi J. Zhuo
references.title: Predicting what you already know helps: Provable self-supervised learning
references.venue: arXiv preprint arXiv:2008.01064,
references.authors: J.R. Lee S.O. Gharan L. Trevisan
references.title: Multiway spectral partitioning and higher-order cheeger inequalities
references.venue: Journal of the ACM (JACM),
references.authors: J. Lei A. Rinaldo
references.title: Consistency of spectral clustering in stochastic block models
references.venue: Annals of Statistics,
references.authors: T. Leighton S. Rao
references.title: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
references.venue: Journal of the ACM (JACM),
references.authors: A. Louis K. Makarychev
references.title: Approximation algorithm for sparsest k-partitioning
references.venue: In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms,
references.authors: A. Louis P. Raghavendra P. Tetali S. Vempala
references.title: Algorithmic extensions of cheeger’s inequality to higher eigenvalues and partitions. In Approximation, Randomization, and Combinatorial Optimization
references.venue: Algorithms and Techniques,
references.authors: F. McSherry
references.title: Spectral partitioning of random graphs
references.venue: In Proceedings 42nd IEEE Symposium on Foundations of Computer Science,
references.authors: I. Misra L. v. d. Maaten
references.title: Self-supervised learning of pretext-invariant representations
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: M. Mohri A. Rostamizadeh A. Talwalkar
references.title: Foundations of machine learning
references.venue: MIT press,
references.authors: A. Ng M. Jordan Y. Weiss
references.title: On spectral clustering: Analysis and an algorithm
references.venue: Advances in neural information processing systems,
references.authors: A. v. d. Oord Y. Li O. Vinyals
references.title: Representation learning with contrastive predictive coding
references.venue: arXiv preprint arXiv:1807.03748,
references.authors: J. Shi J. Malik
references.title: Normalized cuts and image segmentation
references.venue: IEEE Transactions on pattern analysis and machine intelligence,
references.authors: K. Sohn
references.title: Improved deep metric learning with multi-class n-pair loss objective
references.venue: In Proceedings of the 30th International Conference on Neural Information Processing Systems,
references.authors: Y. Tian D. Krishnan P. Isola
references.title: Contrastive multiview coding
references.venue: arXiv preprint arXiv:1906.05849,
references.authors: Y. Tian C. Sun B. Poole D. Krishnan C. Schmid P. Isola
references.title: What makes for good views for contrastive learning
references.venue: arXiv preprint arXiv:2005.10243,
references.authors: Y. Tian L. Yu X. Chen S. Ganguli
references.title: Understanding self-supervised learning with dual deep networks
references.venue: arXiv preprint arXiv:2010.00578,
references.authors: C. Tosh A. Krishnamurthy D. Hsu
references.title: Contrastive estimation reveals topic posterior information to linear models
references.authors: C. Tosh A. Krishnamurthy D. Hsu
references.title: Contrastive learning, multi-view redundancy, and linear models
references.venue: In Algorithmic Learning Theory,
references.authors: T.W. Tsai C. Li J. Zhu
references.title: Mice: Mixture of contrastive experts for unsupervised image clustering
references.venue: arXiv preprint arXiv:2105.01899,
references.authors: Y.-H.H. Tsai Y. Wu R. Salakhutdinov L.-P. Morency
references.title: Self-supervised learning from a multi-view perspective
references.venue: arXiv preprint arXiv:2006.05576,
references.authors: T. Wang P. Isola
references.title: Understanding contrastive representation learning through alignment and uniformity on the hypersphere
references.venue: In International Conference on Machine Learning,
references.authors: C. Wei K. Shen Y. Chen T. Ma
references.title: Theoretical analysis of self-training with deep networks on unlabeled data
references.venue: arXiv preprint arXiv:2010.03622,
references.authors: Z. Wu Y. Xiong S.X. Yu D. Lin
references.title: Unsupervised feature learning via non-parametric instance discrimination
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: M. Ye X. Zhang P.C. Yuen S.-F. Chang
references.title: Unsupervised embedding learning via invariant and spreading instance feature
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: J. Zbontar L. Jing I. Misra Y. LeCun S. Deny. Barlow
references.title: twins: Self-supervised learning via redundancy reduction
references.venue: arXiv preprint arXiv:2103.03230,
sections.heading: 1 Introduction
sections.text: Recent empirical breakthroughs have demonstrated the effectiveness of self-supervised learning, which trains representations on unlabeled data with surrogate losses and self-defined supervision signals [4, 6, 10, 14, 23, 24, 35, 38, 41, 42, 50–52]. Self-supervision signals in computer vision are often defined by using data augmentation to produce multiple views of the same image. For example, the recent contrastive learning objectives [3, 12, 13, 15, 22] encourage closer representations for augmentations (views) of the same natural data than for randomly sampled pairs of data.
  Despite the empirical successes, there is a 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. [44, 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 a strong correlation, even conditioned on the label. For instance, two augmentations of the same dog image
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  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 a principled, practical loss function for learning neural net representations that resembles state-of-the-art contrastive learning methods. We prove that, under a simple and realistic data assumption, linear classification using representations learned on a polynomial number of unlabeled data samples can recover the ground-truth labels of the data with high accuracy.
  The fundamental data property that we leverage is a notion of continuity of the population data within the same class. Though a 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 [49] empirically demonstrates this type of connectivity property and uses it in the analysis of pseudolabeling algorithms.
  More formally, we define the population augmentation graph, whose vertices are all the augmented data in 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 is that for some proper m 2 Z+, the sparsest m-partition (Definition 3.4) is large. This intuitively states that we can’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 a graph-theoretic version of the continuity assumption on population data. We also assume that there are very few edges across different ground-truth classes (Assumption 3.5). Figure 1 (left) illustrates a realistic scenario where dog and cat are the ground-truth categories, between which edges are very rare. Each breed forms a 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-graphs corresponding to fine-grained classes, our assumptions allow the downstream task to have any r  m coarse-grained classes containing these 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 we consider directly learning continuous representations on the unlabeled data.
  We apply spectral decomposition—a 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 Rk) 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):
  L(f) = 2 · Ex,x+ ⇥ f(x)>f(x+) ⇤ + Ex,x0 ⇥ f(x)>f(x0) 2 ⇤ ,
  where (x, x+) is a pair of augmentations of the same data, (x, x0) is a pair of independently random augmented data, and f is a parameterized function from augmented data to Rk. Figure 1 (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 a larger representation dimension is needed when there are a 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 in the Rademacher complexity of the model family and other relevant parameters (Theorem 4.1 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-the-shelf 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 [12, 14, 15, 21] when evaluated using a linear probe.
sections.heading: 2 Additional related works
sections.text: Empirical works on self-supervised learning. Self-supervised learning algorithms have been shown to successfully learn representations that benefit downstream tasks [4, 6, 10, 12, 13, 15, 22– 24, 35, 38, 41, 42, 50–52]. Many recent self-supervised learning algorithms learn features with siamese networks [8], where two neural networks of shared weights are applied to pairs of augmented data. Introducing asymmetry to siamese networks either with a momentum encoder like BYOL [21] or by stopping gradient propagation for one branch of the siamese network like SimSiam [14] has been shown to effectively avoid collapsing. Contrastive methods [12, 15, 22] minimize the InfoNCE loss [38], 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] discussed in the introduction, several other works [5, 43, 47, 48] also theoretically study self-supervised learning. The work Tsai et al. [47] prove that self-supervised learning methods can extract task-relevant information and discard task-irrelevant information, but lacks guarantees for solving downstream tasks efficiently with simple (e.g., linear) models. Tian et al. [43] study why non-contrastive selfsupervised learning methods can avoid feature collapse. Cai et al. [9] analyze domain adaptation algorithms for subpopulation shift with a similar expansion condition as [49] while also allowing disconnected parts within each class, but require access to ground-truth labels during training. In contrast, our algorithm doesn’t need labels during pre-training.
sections.heading: 3 Spectral contrastive learning on population data
sections.text: In this section, we introduce our theoretical framework, the spectral contrastive loss, and the main analysis of the performance of the representations learned on population data.
  We use X to denote the set of all natural data (raw inputs without augmentation). We assume that each x̄ 2 X belongs to one of r 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 to be a finite but exponentially large set (e.g., all real vectors in Rd with bounded precision).1
  We next formulate data augmentations. Given a natural data sample x̄ 2 X , we use A(·|x̄) to denote the distribution of its augmentations. For instance, when x̄ represents an image, A(·|x̄) can be the distribution of common augmentations [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(·|x̄) for x̄ 2 X . As with X , we also assume that X is a finite but exponentially large set, and denote N = |X |.
  We will learn an embedding function f : X ! Rk, and then evaluate its quality by the minimum error achieved with a linear probe. Concretely, a linear classifier has weights B 2 Rk⇥r and predicts gf,B(x) = argmaxi2[r](f(x) > B)i for an augmented data x (argmax breaks tie arbitrarily). Then, given a natural data sample x̄, we ensemble the predictions on augmented data and predict: ḡf,B(x̄) := argmax
  i2[r] Pr x⇠A(·|x̄) [gf,B(x) = i] .
  Define the linear probe error as the error of the best possible linear classifier on the representations: E(f) := min
  B2Rk⇥r Pr x̄⇠PX [y(x̄) 6= ḡf,B(x̄)] (1)
sections.heading: 3.1 Augmentation graph and spectral decomposition
sections.text: 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 x, x0 2 X , define the weight wxx0 as the marginal probability of generating the pair x and x0 from a random natural data x̄ ⇠ PX :
  wxx0 := Ex̄⇠PX [A(x|x̄)A(x 0|x̄)] (2)
  Therefore, the weights sum to 1 because the total probability mass is 1: P
  x,x02X wxx0 = 1. The relative magnitude intuitively captures the closeness between x and x0 with respect to the augmentation transformation. For most of the unrelated x and x0, the value wxx0 will be significantly smaller than the average value. For example, when x and x0 are random croppings of a cat and a dog respectively, wxx0 will be essentially zero because no natural data can be augmented into both x and x0. On the other hand, when x and x0 are very close in `2-distance or very close in `2-distance up to color distortion, wxx0 is nonzero because they may be augmentations of the same image with Gaussian blur and color distortion. We say that x and x0 are connected with an edge if wxx0 > 0. See Figure 1 (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 as shown in spectral graph theory [17] for both worst-case graphs [11, 25, 29, 33] and random graphs [1, 30, 34]. In machine learning, spectral clustering [37, 39] is a classical algorithm that learns embeddings by eigendecomposition on an empirical distance graph and invoking k-means on the embeddings.
  We will apply eigendecomposition to the population augmentation graph (and then later use linear probe for classification). Let wx = P x02X wxx0 be the total weights associated to x, 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:
  A := D 1/2AD 1/2 (3) 1This allows us to use sums instead of integrals and avoid non-essential nuances related to calculus.
  where A 2 RN⇥N is adjacency matrix with entires Axx0 = wxx0 and D 2 RN⇥N is a diagonal matrix with Dxx = wx.2
  Standard spectral graph theory approaches produce vertex embeddings as follows. Let 1, 2, · · · , k be the k largest eigenvalues of A, and v1, v2, · · · , vk be the corresponding unit-norm eigenvectors. Let F ? = [v1, v2, · · · , vk] 2 RN⇥k be the matrix that collects these eigenvectors in columns, and we refer to it as the eigenvector matrix. Let u⇤x 2 Rk be the x-th row of the matrix F ?. It turns out that u ⇤ x’s can serve as desirable embeddings of x’s because they exhibit clustering structure in Euclidean space that resembles the clustering structure of the graph G(X , w).
sections.heading: 3.2 From spectral decomposition to spectral contrastive learning
sections.text: The embeddings u⇤x obtained by eigendecomposition are nonparametric—a k-dimensional parameter is needed for every x—and therefore cannot be learned with a 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 u⇤x can be represented by f(x) for some f 2 F , where F is the hypothesis class containing neural networks. As we’ll show in Section 4, this allows us to leverage the extrapolation power of neural networks and learn the representation on a finite dataset.
  Next, we design a 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 4, the resulting population loss function on f also admits an unbiased estimator with finite training samples. Let F be an embedding matrix with ux on the x-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
  min F2RN⇥k
  Lmf(F ) := A FF> 2 F . (4)
  By the classical theory on low-rank approximation (Eckart–Young–Mirsky theorem [19]), any minimizer bF of Lmf(F ) contains scaling of the largest eigenvectors of A up to a right transformation— for some orthonormal matrix R 2 Rk⇥k, we have bF = F ? · diag([p 1, . . . , p k])Q. Fortunately, 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. Lemma 3.1. Consider an embedding matrix F 2 RN⇥k and a linear classifier B 2 Rk⇥r. Let D 2 RN⇥N be a diagonal matrix with positive diagonal entries and Q 2 Rk⇥k be an invertible matrix. Then, for any embedding matrix eF = D · F ·Q, the linear classifier B̃ = Q 1B on eF has the same prediction as B on F . As a consequence, we have
  E(F ) = E( eF ). (5)
  where E(F ) denotes the linear probe performance when the rows of F are used as embeddings.
  The proof can be found in Section C.1.
  The main benefit of objective Lmf(F ) is that it’s based on the rows of F . Recall that vectors ux are the rows of F . Each entry of FF> is of the form u>x xx0 , and thus Lmf(F ) can be decomposed into a sum of N2 terms involving terms u>x ux0 . Interestingly, if we reparameterize each row ux by w 1/2 x f(x), we obtain a very similar loss function for f that resembles the contrastive learning loss used in practice [12] as shown below in Lemma 3.2. See Figure 1 (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 x̄ ⇠ PX be a random natural data and draw x ⇠ A(·|x̄) and x+ ⇠ A(·|x̄) independently to form a positive pair (x, x+). Draw x̄0 ⇠ PX and x0 ⇠ A(·|x̄0) independently with x̄, x, x+. We call (x, x0) a negative pair.3
  2We index the matrix A, D by (x, x0) 2 X ⇥ X . Generally we index N -dimensional axis by x 2 X . 3Though x and x0 are simply two independent draws, we call them negative pairs following the literature [3].
  Lemma 3.2 (Spectral contrastive loss). Recall that ux is the x-th row of F . Let ux = w 1/2 x f(x) for some function f . Then, the loss function Lmf(F ) is equivalent to the following loss function for f , called spectral contrastive loss, up to a additive constant:
  Lmf(F ) = L(f) + const
  where L(f) , 2 · Ex,x+ ⇥ f(x)>f(x+) ⇤ + Ex,x0 h f(x)>f(x0) 2i (6)
  The proof can be found in Section C.1.
  We note that spectral contrastive loss is similar to many popular contrastive losses [12, 38, 40, 50]. For instance, the contrastive loss in SimCLR [12] can be rewritten as (with simple algebraic manipulation)
  f(x)>f(x+) + log exp f(x)>f(x+) +
  nX
  i=1
  exp f(x)>f(xi)
  !
  .
  Here x and x+ are a positive pair and x1, · · · , xn are augmentations of other data. Spectral contrastive loss can be seen as removing f(x)>f(x+) from the second term, and replacing the log sum of exponential terms with the average of the squares of f(x)>f(xi). We will show in Section 6 that our loss has a similar empirical performance as SimCLR without requiring a large batch size.
sections.heading: 3.3 Theoretical guarantees for spectral contrastive loss on population data
sections.text: 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-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 a graph G = (X , w) and a subset S ✓ X , we define the Dirichlet conductance of S as
  G(S) :=
  P x2S,x0 /2S wxx0P
  x2S wx .
  We note that when S is a singleton, there is G(S) = 1 due to the definition of wx. We introduce the sparsest m-partition to represent the number of edges between m disjoint subsets. Definition 3.4 (Sparsest m-partition). Let G = (X , w) be the augmentation graph. For an integer m 2 [2, |X |], we define the sparsest m-partition as
  ⇢m := min S1,··· ,Sm max{ G(S1), . . . , G(Sm)}
  where S1, · · · , Sm are non-empty sets that form a partition of X .
  When r is the number of underlying classes, we might expect ⇢r ⇡ 0 since the augmentations from different classes almost compose a disjoint r-way partition of X . However, for m > r, we can expect ⇢m to be much larger. For instance, in the extreme case when m = |X | = N , every set Si is a singleton, which implies that ⇢N = 1.
  Next, we 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 x̄ ⇠ PX and y(x̄) be its label. Let the augmentation x ⇠ A(·|x̄). We assume that there exists a classifier g that can predict y(x̄) given x with error at most ↵. That is, g(x) = y(x̄) with probability at least 1 ↵.
  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 X to Rk. We assume that at least one of the global minima of L(f) belongs to 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.5 holds for ↵ > 0. Let F be a hypothesis class that satisfies Assumption 3.6 and let f⇤pop 2 F be a minimizer of L(f). Then, we have
  E(f⇤pop)  eO ⇣ ↵/⇢ 2 bk/2c ⌘ .
  Here we use eO(·) to hide universal constant factors and logarithmic factor in k. We note that ↵ = 0 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 ↵ to be an extremely small constant independent of k, whereas ⇢bk/2c increases with k and can be much larger than ↵ when k is reasonably large. For instance, when there are t sub-graphs that have sufficient inner connections, we expect ⇢t+1 to be on the order of a constant because any t+ 1 partition needs to break one sub-graph into two pieces and incur a large conductance. We characterize the ⇢k’s growth on more concrete distributions in the next subsection.
  Previous works on graph partitioning [2, 29, 31] often analyze the so-called rounding algorithms 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 [2] that can be exponentially large in our setting. The approximation ratio guarantee does not lead to a guarantee on the representations’ performance on downstream tasks. Our guarantees are on the linear probe accuracy on the downstream tasks and independent of the graph size. We rely on the formulation of the downstream task’s labeling function (Assumption 3.5) as well as a novel analysis technique that characterizes the linear structure of the representations. In Section C, we provide the proof of Theorem 3.7 as well as its more generalized version where k/2 is relaxed to be any constant fraction of k.
sections.heading: 3.4 Provable instantiation of Theorem 3.7 to mixture of manifold data
sections.text: In this section, we exemplify Theorem 3.7 on an example where the natural data distribution is a mixture of manifolds, and the augmentation transformation is adding Gaussian noise. Example 3.8 (Mixture of manifolds). Suppose PX is mixture of r  d distributions P1, · · · , Pr, where each Pi is generated by some -bi-Lipschitz 4 generator Q : Rd0 ! Rd on some latent variable z 2 Rd0 with d0  d which as a mixture of Gaussian distribution:
  x ⇠ Pi () x = Q(z), z ⇠ N (µi, 1
  d0 · Id0⇥d0).
  Let the data augmentation of a natural data sample x̄ is x̄+ ⇠ where ⇠ ⇠ N (0, 2
  d · Id⇥d) is isotropic Gaussian noise with 0 < . 1p
  d . We also assume mini 6=j kµi µjk2 & · p log dp d0 .
  Let the ground-truth label be the most likely mixture index i that generates x: y(x) := argmaxi Pi(x). We note that the intra-class distance in the latent space is on the scale of ⌦(1), which can be much larger than the distance between class means which is assumed to be & ·
  p log dp d0
  . Therefore, distancebased clustering algorithms do not apply. We apply Theorem 3.7 and get the following theorem: Theorem 3.9. When k 2r + 2, Example 3.8 satisfies Assumption 3.5 with ↵  1poly(d) , and has
  ⇢bk/2c & pd . As a consequence, the error bound is E(f ⇤ pop)  Õ
  ⇣ 2
  2·poly(d)
  ⌘ .
  The theorem above guarantees small error even when is polynomially small. In this case, the augmentation noise has a much smaller scale than the data (which is at least on the order of 1/). 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.
  4A  bi-Lipschitz function satisfies 1 kf(x) f(y)k2  kx yk2   kf(x) f(y)k2.
sections.heading: 4 Finite-sample generalization bounds
sections.text: In Section 3, 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 a training dataset {x̄1, x̄2, · · · , x̄n} with x̄i ⇠ PX , we learn a feature extractor by minimizing the following empirical spectral contrastive loss:
  bLn(f) := 2
  n
  nX
  i=1
  E x⇠A(·|x̄i) x+⇠A(·|x̄i)
  ⇥ f(x)>f(x+) ⇤ +
  1 n(n 1) X
  i 6=j E x⇠A(·|x̄i) x0⇠A(·|x̄j)
  h f(x)>f(x0) 2i .
  It is worth noting that bLn(f) is an unbiased estimator of the population spectral contrastive loss L(f). (See Claim E.2 for a proof.) Therefore, we can derive generalization bounds via off-the-shelf concentration inequalities. Let F be a hypothesis class containing feature extractors from X to Rk. We extend Rademacher complexity to function classes with highdimensional outputs and define the Rademacher complexity of F on n data as bRn(F) := maxx1,··· ,xn2X E h supf2F,i2[k] 1 n ⇣Pn j=1 jfi(xj) ⌘i ,
  where is a uniform random vector in { 1, 1}n and fi(z) is the i-th dimension of f(z). Recall that f⇤pop 2 F is a minimizer of L(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 some  > 0, assume kf(x)k1   for all f 2 F and x 2 X . Let f⇤pop 2 F be a minimizer of the population loss L(f). Given a random dataset of size n, let f̂emp 2 F be a minimizer of empirical loss bLn(f). Then, with probability at least 1 over the randomness of data, we have
  L(f̂emp)  L(f⇤pop) + c1 · bRn/2(F) + c2 · r log 2/
  n +
  ! ,
  where constants c1 . k22 + k and c2 . k2 + k24.
  We can apply Theorem 4.1 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 a corollary of Theorem 4.1 when F contains deep neural networks with ReLU activation. The theorem above shows that we can achieve near-optimal population loss by minimizing empirical 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. Theorem 4.2. Assume representation dimension k 4r + 2, Assumption 3.5 holds for ↵ > 0 and Assumption 3.6 holds. Recall i be the i-th largest eigenvalue of the normalized adjacency matrix. Then, for any ✏ < 2 k and f̂emp 2 F such that L(f̂emp) < L(f⇤pop) + ✏, we have:
  E(f̂emp) . ↵ ⇢2bk/2c · log k + k✏ 2 ,
  where := b3k/4c k is the eigenvalue gap between the b3k/4c-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 to 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.
sections.heading: 5 Guarantee for learning linear probe with labeled data
sections.text: In this section, we provide theoretical guarantees for learning a linear probe with labeled data. Theorem 3.7 guarantees the existence of a linear probe that achieves a small downstream classification error. However, a 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 in 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 a tuple (z, y(x̄)) where z 2 Rk is a representation of augmented data x ⇠ A(·|x̄) and y(x̄) 2 [r] is the label of x̄, for a linear probe B 2 Rk⇥r we define loss `((z, y(x̄)), B) := Pr i=1 min B > z ~y(x̄) 2 i , 1 , where ~y(x̄) is the one-hot embedding of y(x̄) as a r-dimensional vector (1 on the y(x̄)-th dimension, 0 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 [36].
  The following Theorem 5.1 provides a generalization guarantee for the linear classifier that minimizes capped quadratic loss on 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 i is the i-th largest eigenvalue of the the normalized adjacency matrix. Given a labeled dataset {(x̄i, y(x̄i))}ni=1 where x̄i ⇠ PX and y(x̄i) is its label, we sample xi ⇠ A(·|x̄i) for i 2 [n]. Theorem 5.1. In the setting of Theorem 3.7, assume k C for some C > 0. Learn a linear probe bB 2 argminkBkF1/C Pn i=1 `((f ⇤ pop(xi), y(x̄i)), B) by minimizing the capped quadratic loss subject to a norm constraint. Then, with probability at least 1 over random data, we have
  Pr x̄⇠PX
  ⇣ ḡf⇤pop, bB(x̄) 6= y(x̄) ⌘ . ↵
  ⇢2bk/2c · log k + r C · r k n + r log 1/ 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 n is polynomial in the feature dimension k. We note that this result reveals a tradeoff when choosing the feature dimension k: when n is fixed, a larger k decreases the population contrastive loss while increases the generalization gap for downstream linear classification. The proof of Theorem 5.1 is in Section F.
sections.heading: 6 Experiments
sections.text: We test spectral contrastive learning on benchmark vision datasets. We minimize the empirical spectral contrastive loss with an encoder network f 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 MLP and a projection function. The backbone network is a standard ResNet architecture. The projection MLP is a fully connected network with BN applied to each layer, and ReLU activation applied to each except for the last layer. The projection function takes a vector and projects it to a sphere ball with radius pµ, where µ > 0 is a hyperparameter that we tune in experiments. We find that using a projection MLP and a projection function improves the performance.
  Linear evaluation protocol. Given the pre-trained encoder network, we follow the standard linear evaluation protocol [14] and train a supervised linear classifier on frozen representations, which are from the ResNet’s global average pooling layer.
  Results. We report the accuracy on CIFAR-10/100 [26] and Tiny-ImageNet [27] in Table 1. Our empirical results show that spectral contrastive learning achieves better performance than two popular baseline algorithms SimCLR [12] and SimSiam [14]. In Table 2 we report results on ImageNet [18] dataset, and show that our algorithm achieves similar performance as other state-of-the-art methods. We note that our algorithm is much more principled than previous methods and doesn’t rely on large batch sizes (SimCLR [12]), momentum encoders (BYOL [21] and MoCo [22]) or additional tricks such as stop-gradient (SimSiam [14]).
sections.heading: 7 Conclusion
sections.text: In this paper, we present a 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.
sections.heading: Acknowledgements
sections.text: 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.
title: Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss