Optimal VC Dimension of Contrastive Learning with Margin
In the authors' words
Contrastive learning is a successful paradigm for learning -dimensional geometric representations from a collection of "anchor--positive--negative" triplets , indicating that "item is closer to than to ." Despite its success, understanding why contrastive learning leads to representations of high generalization quality---beyond the often pessimistic predictions from PAC-learning---remains a central question. Recently, \citet*{alon2024optimal} proved that, for PAC-learning -dimensional Euclidean representations of -point datasets, triplets are necessary and sufficient, while they posed as an open question whether their VC dimension bounds for the more realistic setting of contrastive learning with a margin can be improved. For a margin parameter , a triplet is satisfied by the embedding , if . In this work, we resolve their question by proving that the VC dimension of contrastive learning under any margin is in fact , improving on the previous bound of . We also establish that the bounds are optimal up to constant factors, by providing a matching lower bound of (the previously known lower bound was ), for .
Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: Main result obtained in April 2026 without the use of AI