Optimal VC Dimension of Contrastive Learning with Margin
Abstract
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 \textit{generalization} 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, Θ(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 \textit{contrastive learning with a margin} can be improved. For a margin parameter α>0, a triplet (i,j+,k−)α is satisfied by the embedding ϕ:[n]→ ℝ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 Ω(n/α2) (the previously known lower bound was Ω(n/α)), for α≥ max(n−1/2,d−1/2).
Related
- Multi-Marginal Inverse Optimal Transport for Contrastive Learning Via Explicit Anchor-Positive-Negative Coupling
- Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning
- Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension
- Power-Optimal Risk Control via Standardized Margin Calibration
- Anchor Divergence for Semantic Geometry in Contrastive Learning
BibTeX
@misc{arvanitakis2026optimal,
title = {{Optimal VC Dimension of Contrastive Learning with Margin}},
author = {Dionysis Arvanitakis and Vaggos Chatziafratis and Yiyuan Luo and Konstantin Makarychev},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38834},
eprint = {2609.38834},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38834},
}
RIS
TY - UNPB
TI - Optimal VC Dimension of Contrastive Learning with Margin
AU - Dionysis Arvanitakis
AU - Vaggos Chatziafratis
AU - Yiyuan Luo
AU - Konstantin Makarychev
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38834
UR - https://arxiv.org/abs/2609.38834
AB - 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 \textit{generalization} 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, Θ(min(nd, n^2)) triplets are necessary and sufficient, while they posed as an open question whether their VC dimension bounds for the more realistic setting of \textit{contrastive learning with a margin} can be improved. For a margin parameter α>0, a triplet (i,j^+,k^−)_α is satisfied by the embedding ϕ:[n]→ ℝ^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 Ω(n/α^2) (the previously known lower bound was Ω(n/α)), for α≥ max(n^−1/2,d^−1/2).
ER -