Research map / Learning theory and algorithms / Sample complexity
Optimal Sample Complexity of Contrastive Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives tight PAC-style sample complexity bounds (via VC/Natarajan dimension) for contrastive learning with triplets under arbitrary distances, l_p distances, cosine similarity, tree metrics, and k negatives, and shows the bounds predict experiments on image datasets.
Problem
How many labeled contrastive triplets (anchor, positive, negative) are needed to learn a good distance function or embedding, for various distance families including l_p distances in R^d?
Approach
Frames contrastive learning as PAC learning of distance functions and characterizes sample complexity via VC/Natarajan dimension; for l_p distances, counts connected components of sign-pattern regions of degree-p polynomials (Milnor-Thom style bound) to get Theta~(min(nd, n^2)) with parity-dependent log factors.
Key results
- For integer p, sample complexity of l_p contrastive learning is Theta~(min(nd, n^2)) for even p, with an extra log n factor for odd p (odd-p upper bound open for tightness).
- For arbitrary distances the sample complexity is Theta(n^2), and for tree metrics it is between Omega(n) and O(n log n).
- For cosine similarity the sample complexity is Theta(min(n^2, nd)) up to polylog factors.
Surprising findings
- Upper bounds for quadruplet learning match triplet bounds despite the number of distinct quadruplets being Theta(n^4).
Limitations
- Tightness for odd p is open; upper bound has an extra log n factor.
- Experiments show asymptotic agreement but constant ratio between observed and predicted values tends to be small.
Experimental setup
Datasets: CIFAR-10 CIFAR-100 MNIST Fashion-MNIST
Metrics: error rate
Baselines: ResNet18 contrastive training
Builds on: VC dimension Natarajan dimension
Closest papers by meaning
- Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors (NeurIPS 2024 · similarity 0.89)
- Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings (ICML 2025 · similarity 0.89)
- Transductive Learning is Compact (NeurIPS 2024 · similarity 0.87)
- Generalization Analysis for Deep Contrastive Representation Learning (AAAI 2025 · similarity 0.87)
- The Complexity of Finding Local Optima in Contrastive Learning (NeurIPS 2025 · similarity 0.87)
- Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.