# Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss

arXiv: https://arxiv.org/abs/2106.04156 · HTML: https://mlsanity.com/paper/2106.04156/

## Key facts

- Cited by 313 papers in the map (data through 14 Oct 2026).
- Placed in Sparse autoencoder training and evaluation, one of 13 directions in Mechanistic interpretability.
- Builds on 40 of its 77 references that are in the map.
- First posted on arXiv 8 Jun 2021.

## Placed in

- Mechanistic interpretability / [Sparse autoencoder training and evaluation](https://mlsanity.com/mechinterp/sparse-autoencoder-training-and-evaluation/)

## Builds on (most cited first, 30 of 40)

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [Bootstrap your own latent: A new approach to self-supervised Learning](https://mlsanity.com/paper/2006.07733/) (2020)
- [Exploring Simple Siamese Representation Learning](https://mlsanity.com/paper/2011.10566/) (2020)
- [Unsupervised Learning of Visual Features by Contrasting Cluster Assignments](https://mlsanity.com/paper/2006.09882/) (2020)
- [Improved Baselines with Momentum Contrastive Learning](https://mlsanity.com/paper/2003.04297/) (2020)
- [Unsupervised Feature Learning via Non-Parametric Instance-level Discrimination](https://mlsanity.com/paper/1805.01978/) (2018)
- [Barlow Twins: Self-Supervised Learning via Redundancy Reduction](https://mlsanity.com/paper/2103.03230/) (2021)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Big Self-Supervised Models are Strong Semi-Supervised Learners](https://mlsanity.com/paper/2006.10029/) (2020)
- [Contrastive Multiview Coding](https://mlsanity.com/paper/1906.05849/) (2019)
- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Unsupervised Data Augmentation for Consistency Training](https://mlsanity.com/paper/1904.12848/) (2019)
- [VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning](https://mlsanity.com/paper/2105.04906/) (2021)
- [What Makes for Good Views for Contrastive Learning?](https://mlsanity.com/paper/2005.10243/) (2020)
- [Self-Supervised Learning of Pretext-Invariant Representations](https://mlsanity.com/paper/1912.01991/) (2019)
- [Learning Representations by Maximizing Mutual Information Across Views](https://mlsanity.com/paper/1906.00910/) (2019)
- [Data-Efficient Image Recognition with Contrastive Predictive Coding](https://mlsanity.com/paper/1905.09272/) (2019)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Debiased Contrastive Learning](https://mlsanity.com/paper/2007.00224/) (2020)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Unsupervised Embedding Learning via Invariant and Spreading Instance Feature](https://mlsanity.com/paper/1904.03436/) (2019)
- [Contrastive Learning Inverts the Data Generating Process](https://mlsanity.com/paper/2102.08850/) (2021)
- [Representation Learning via Invariant Causal Mechanisms](https://mlsanity.com/paper/2010.07922/) (2020)
- [Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data](https://mlsanity.com/paper/2010.03622/) (2020)
- [Predicting What You Already Know Helps: Provable Self-Supervised Learning](https://mlsanity.com/paper/2008.01064/) (2020)
- [Contrastive learning, multi-view redundancy, and linear models](https://mlsanity.com/paper/2008.10150/) (2020)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)

## Built on by (most cited first, 30 of 313)

- [Understanding Dimensional Collapse in Contrastive Self-supervised Learning](https://mlsanity.com/paper/2110.09348/) (2021)
- [A Cookbook of Self-Supervised Learning](https://mlsanity.com/paper/2304.12210/) (2023)
- [A Survey on Self-supervised Learning: Algorithms, Applications, and Future Trends](https://mlsanity.com/paper/2301.05712/) (2023)
- [RankMe: Assessing the downstream performance of pretrained self-supervised representations by their rank](https://mlsanity.com/paper/2210.02885/) (2022)
- [Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods](https://mlsanity.com/paper/2205.11508/) (2022)
- [Self-supervised Learning is More Robust to Dataset Imbalance](https://mlsanity.com/paper/2110.05025/) (2021)
- [On the duality between contrastive and non-contrastive self-supervised learning](https://mlsanity.com/paper/2206.02574/) (2022)
- [Chaos is a Ladder: A New Theoretical Understanding of Contrastive Learning via Augmentation Overlap](https://mlsanity.com/paper/2203.13457/) (2022)
- [Towards the Generalization of Contrastive Self-Supervised Learning](https://mlsanity.com/paper/2111.00743/) (2021)
- [Understanding Contrastive Learning Requires Incorporating Inductive Biases](https://mlsanity.com/paper/2202.14037/) (2022)
- [How Mask Matters: Towards Theoretical Understandings of Masked Autoencoders](https://mlsanity.com/paper/2210.08344/) (2022)
- [Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Models](https://mlsanity.com/paper/2210.14199/) (2022)
- [Why Do Pretrained Language Models Help in Downstream Tasks? An Analysis of Head and Prompt Tuning](https://mlsanity.com/paper/2106.09226/) (2021)
- [Learning and Leveraging World Models in Visual Representation Learning](https://mlsanity.com/paper/2403.00504/) (2024)
- [Pushing the limits of self-supervised ResNets: Can we outperform supervised learning without labels on ImageNet?](https://mlsanity.com/paper/2201.05119/) (2022)
- [Connect, Not Collapse: Explaining Contrastive Learning for Unsupervised Domain Adaptation](https://mlsanity.com/paper/2204.00570/) (2022)
- [Diagnosing and Rectifying Vision Models using Language](https://mlsanity.com/paper/2302.04269/) (2023)
- [The Power of Contrast for Feature Learning: A Theoretical Analysis](https://mlsanity.com/paper/2110.02473/) (2021)
- [Theoretical Analysis of Weak-to-Strong Generalization](https://mlsanity.com/paper/2405.16043/) (2024)
- [Investigating Why Contrastive Learning Benefits Robustness Against Label Noise](https://mlsanity.com/paper/2201.12498/) (2022)
- [Orchestra: Unsupervised Federated Learning via Globally Consistent Clustering](https://mlsanity.com/paper/2205.11506/) (2022)
- [Neural Manifold Clustering and Embedding](https://mlsanity.com/paper/2201.10000/) (2022)
- [Beyond Separability: Analyzing the Linear Transferability of Contrastive Representations to Related Subpopulations](https://mlsanity.com/paper/2204.02683/) (2022)
- [Self-supervised learning of Split Invariant Equivariant representations](https://mlsanity.com/paper/2302.10283/) (2023)
- [Perfectly Balanced: Improving Transfer and Robustness of Supervised Contrastive Learning](https://mlsanity.com/paper/2204.07596/) (2022)
- [A Theoretical Study of Inductive Biases in Contrastive Learning](https://mlsanity.com/paper/2211.14699/) (2022)
- [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023)
- [InfoNCE: Identifying the Gap Between Theory and Practice](https://mlsanity.com/paper/2407.00143/) (2024)
- [Do More Negative Samples Necessarily Hurt in Contrastive Learning?](https://mlsanity.com/paper/2205.01789/) (2022)
- [Is a Caption Worth a Thousand Images? A Controlled Study for Representation Learning](https://mlsanity.com/paper/2207.07635/) (2022)

## Abstract (arXiv)

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. 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.