mlsanityData to 14 Oct 2026

Optimal Sample Complexity of Contrastive Learning

arXiv 2312.00379 ↗First posted 1 Dec 2023cs.LG stat.MLcited by 15

Not on the map. Why?

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.

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

42 of 69 references.

References · 42

  1. 2020A Simple Framework for Contrastive Learning of Visual Representationscited by 12,049
  2. 2018Representation Learning with Contrastive Predictive Codingcited by 7,777
  3. 2019Momentum Contrast for Unsupervised Visual Representation Learningcited by 7,513
  4. 2013Efficient Estimation of Word Representations in Vector Spacecited by 4,375
  5. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  6. 2020Exploring Simple Siamese Representation Learningcited by 2,866
  7. 2015FaceNet: A Unified Embedding for Face Recognition and Clusteringcited by 2,849
  8. 2021SimCSE: Simple Contrastive Learning of Sentence Embeddingscited by 2,173
  9. 2018Unsupervised Feature Learning via Non-Parametric Instance-level Discriminationcited by 1,845
  10. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  11. 2020Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hyperspherecited by 1,405
  12. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
30 more
  1. 2019Contrastive Multiview Codingcited by 1,301
  2. 2018Learning deep representations by mutual information estimation and maximizationcited by 1,273
  3. 2019Learning Representations by Maximizing Mutual Information Across Viewscited by 734
  4. 2017Exploring Generalization in Deep Learningcited by 600
  5. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  6. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  7. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  8. 2019A Theoretical Analysis of Contrastive Unsupervised Representation Learningcited by 530
  9. 2019Fantastic Generalization Measures and Where to Find Themcited by 513
  10. 2019On Mutual Information Maximization for Representation Learningcited by 316
  11. 2021Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Losscited by 313
  12. 2021Self-Supervised Learning with Data Augmentations Provably Isolates Content from Stylecited by 312
  13. 2014Discriminative Unsupervised Feature Learning with Exemplar Convolutional Neural Networkscited by 300
  14. 2021Contrastive Learning Inverts the Data Generating Processcited by 221
  15. 2020Representation Learning via Invariant Causal Mechanismscited by 199
  16. 2018An efficient framework for learning sentence representationscited by 198
  17. 2020Contrastive learning, multi-view redundancy, and linear modelscited by 146
  18. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  19. 2020Intriguing Properties of Contrastive Lossescited by 130
  20. 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
  21. 2022Understanding Contrastive Learning Requires Incorporating Inductive Biasescited by 96
  22. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  23. 2021Investigating the Role of Negatives in Contrastive Representation Learningcited by 54
  24. 2023FFCV: Accelerating Training by Removing Data Bottleneckscited by 49
  25. 2022A Theoretical Study of Inductive Biases in Contrastive Learningcited by 40
  26. 2022Do More Negative Samples Necessarily Hurt in Contrastive Learning?cited by 39
  27. 2017Adaptive Hierarchical Clustering Using Ordinal Queriescited by 9
  28. 2015Sample complexity of learning Mahalanobis distance metricscited by 7
  29. 2019Landmark Ordinal Embeddingcited by 6
  30. 2015Crowdsourcing Feature Discovery via Adaptively Chosen Comparisonscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 8; 2026: 7.

15 papers.

Sort:

  1. 2025Self-Supervised Contrastive Learning is Approximately Supervised Contrastive Learningcited by 5
  2. 2026Directional Neural Collapse Explains Few-Shot Transfer in Self-Supervised Learningcited by 3
  3. 2025Seal Your Backdoor with Variational Defensecited by 2
  4. 2025Formal Models of Active Learning from Contrastive Examplescited by 2
  5. 2025On the Alignment Between Supervised and Self-Supervised Contrastive Learningcited by 2
  6. 2025The Complexity of Finding Local Optima in Contrastive Learningcited by 1
  7. 2026Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatchcited by 1
  8. 2026Sorting from Counterexamplescited by 1
  9. 2025Towards Efficient Contrastive PAC Learningcited by 0
  10. 2025Contrastive Learning with Nasty Noisecited by 0
  11. 2025Contextual Tokenization for Graph Inverted Indicescited by 0
  12. 2026Learning Half-Spaces from Perturbed Contrastive Examplescited by 0
3 more
  1. 2026Strategic PAC Learnability via Geometric Definabilitycited by 0
  2. 2026Which Tasks Survive Self-Supervised Learning?cited by 0
  3. 2026Optimal VC Dimension of Contrastive Learning with Margincited by 0