Optimal VC Dimension of Contrastive Learning with Margin

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).