# Optimal VC Dimension of Contrastive Learning with Margin

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 25 of 25)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [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)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Contrastive Learning with Hard Negative Samples](https://mlsanity.com/paper/2010.04592/) (2020)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Matryoshka Representation Learning](https://mlsanity.com/paper/2205.13147/) (2022)
- [Understanding Contrastive Learning Requires Incorporating Inductive Biases](https://mlsanity.com/paper/2202.14037/) (2022)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Do More Negative Samples Necessarily Hurt in Contrastive Learning?](https://mlsanity.com/paper/2205.01789/) (2022)
- [Generalization Analysis for Contrastive Representation Learning](https://mlsanity.com/paper/2302.12383/) (2023)
- [Optimal Sample Complexity of Contrastive Learning](https://mlsanity.com/paper/2312.00379/) (2023)
- [Insights into Ordinal Embedding Algorithms: A Systematic Evaluation](https://mlsanity.com/paper/1912.01666/) (2019)
- [Adaptive Hierarchical Clustering Using Ordinal Queries](https://mlsanity.com/paper/1708.00149/) (2017)
- [Foundations of Comparison-Based Hierarchical Clustering](https://mlsanity.com/paper/1811.00928/) (2018)
- [Landmark Ordinal Embedding](https://mlsanity.com/paper/1910.12379/) (2019)
- [Generalization Bounds for Adversarial Contrastive Learning](https://mlsanity.com/paper/2302.10633/) (2023)
- [Learning Lines with Ordinal Constraints](https://mlsanity.com/paper/2004.13202/) (2020)
- [Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors](https://mlsanity.com/paper/2312.13490/) (2023)
- [Tree Learning: Optimal Algorithms and Sample Complexity](https://mlsanity.com/paper/2302.04492/) (2023)
- [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)

## Abstract (arXiv)

Contrastive learning is a successful paradigm for learning d-dimensional geometric representations from a collection of ``anchor--positive--negative'' triplets (i,j+,k-), indicating that ``item i is closer to j than to k.'' Despite its success, understanding why contrastive learning leads to representations of high textitgeneralization quality---beyond the often pessimistic predictions from PAC-learning---remains a central question. Recently, citet*alon2024optimal proved that, for PAC-learning d-dimensional Euclidean representations of n-point datasets, Theta(min(nd, n2)) triplets are necessary and sufficient, while they posed as an open question whether their VC dimension bounds for the more realistic setting of textitcontrastive learning with a margin can be improved. For a margin parameter α >0, a triplet (i,j+,k-)α is satisfied by the embedding φ:[n]rightarrow ℝd, if |φ(i)-φ(k)|2>(1+α)·|φ(i)-φ(j)|2. In this work, we resolve their question by proving that the VC dimension of contrastive learning under any margin α∈(0,1) is in fact O(n/α2), improving on the previous bound of O(nlog(n)/α2). We also establish that the bounds are optimal up to constant factors, by providing a matching lower bound of Omega(fracnα2) (the previously known lower bound was Omega(fracnα)), for α≥ max(n-1/2,d-1/2).