# Optimal Sample Complexity of Contrastive Learning

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 69 references that are in the map.
- First posted on arXiv 1 Dec 2023.

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

- [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)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Exploring Simple Siamese Representation Learning](https://mlsanity.com/paper/2011.10566/) (2020)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [SimCSE: Simple Contrastive Learning of Sentence Embeddings](https://mlsanity.com/paper/2104.08821/) (2021)
- [Unsupervised Feature Learning via Non-Parametric Instance-level Discrimination](https://mlsanity.com/paper/1805.01978/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [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)
- [Learning Representations by Maximizing Mutual Information Across Views](https://mlsanity.com/paper/1906.00910/) (2019)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [On Mutual Information Maximization for Representation Learning](https://mlsanity.com/paper/1907.13625/) (2019)
- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Self-Supervised Learning with Data Augmentations Provably Isolates Content from Style](https://mlsanity.com/paper/2106.04619/) (2021)
- [Discriminative Unsupervised Feature Learning with Exemplar Convolutional Neural Networks](https://mlsanity.com/paper/1406.6909/) (2014)
- [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)
- [An efficient framework for learning sentence representations](https://mlsanity.com/paper/1803.02893/) (2018)
- [Contrastive learning, multi-view redundancy, and linear models](https://mlsanity.com/paper/2008.10150/) (2020)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)

## Built on by (most cited first, 15 of 15)

- [Self-Supervised Contrastive Learning is Approximately Supervised Contrastive Learning](https://mlsanity.com/paper/2506.04411/) (2025)
- [Directional Neural Collapse Explains Few-Shot Transfer in Self-Supervised Learning](https://mlsanity.com/paper/2603.03530/) (2026)
- [Seal Your Backdoor with Variational Defense](https://mlsanity.com/paper/2503.08829/) (2025)
- [Formal Models of Active Learning from Contrastive Examples](https://mlsanity.com/paper/2506.15893/) (2025)
- [On the Alignment Between Supervised and Self-Supervised Contrastive Learning](https://mlsanity.com/paper/2510.08852/) (2025)
- [The Complexity of Finding Local Optima in Contrastive Learning](https://mlsanity.com/paper/2509.16898/) (2025)
- [Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch](https://mlsanity.com/paper/2605.03346/) (2026)
- [Sorting from Counterexamples](https://mlsanity.com/paper/2608.21579/) (2026)
- [Towards Efficient Contrastive PAC Learning](https://mlsanity.com/paper/2502.15962/) (2025)
- [Contrastive Learning with Nasty Noise](https://mlsanity.com/paper/2502.17872/) (2025)
- [Contextual Tokenization for Graph Inverted Indices](https://mlsanity.com/paper/2510.22479/) (2025)
- [Learning Half-Spaces from Perturbed Contrastive Examples](https://mlsanity.com/paper/2602.02080/) (2026)
- [Strategic PAC Learnability via Geometric Definability](https://mlsanity.com/paper/2605.13426/) (2026)
- [Which Tasks Survive Self-Supervised Learning?](https://mlsanity.com/paper/2609.38393/) (2026)
- [Optimal VC Dimension of Contrastive Learning with Margin](https://mlsanity.com/paper/2609.38834/) (2026)

## Abstract (arXiv)

Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sample complexity of contrastive learning, i.e. the minimum number of labeled tuples sufficient for getting high generalization accuracy. We give tight bounds on the sample complexity in a variety of settings, focusing on arbitrary distance functions, both general ℓp-distances, and tree metrics. Our main result is an (almost) optimal bound on the sample complexity of learning ℓp-distances for integer p. For any p ≥ 1 we show that tilde Theta(min(nd,n2)) labeled tuples are necessary and sufficient for learning d-dimensional representations of n-point datasets. Our results hold for an arbitrary distribution of the input samples and are based on giving the corresponding bounds on the Vapnik-Chervonenkis/Natarajan dimension of the associated problems. We further show that the theoretical bounds on sample complexity obtained via VC/Natarajan dimension can have strong predictive power for experimental results, in contrast with the folklore belief about a substantial gap between the statistical learning theory and the practice of deep learning.