Contrastive Learning VC Dimension Gets a Tight O(n/α²) Bound

A Clean Answer to an Open Question

A team of theorists has settled how many samples, in the worst case, a margin-based contrastive learner needs to generalize. Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo and Konstantin Makarychev have posted a paper titled "Optimal VC Dimension of Contrastive Learning with Margin." It is cross-listed from data structures and algorithms into machine learning on arXiv. 3 The authors attach an unusual note to the listing: the main result was "obtained in April 2026 without the use of AI." 3

The headline result is that the VC dimension of contrastive learning under any margin α between 0 and 1 is O(n/α²). This improves on the previously known O(n log n/α²). 1 The authors pair that upper bound with a matching lower bound of Ω(n/α²), which replaces the earlier Ω(n/α). That makes the characterization tight up to constant factors. 1 The work answers a question raised by Alon et al. in 2024. The authors note that it settles the question for every positive margin, not only the large-margin regime the original question had in mind. 1 Formally, the upper bound is stated as O(max{n/α², n}). 1

Why the Dimension Disappears

The most striking feature of the upper bound is what it leaves out. The embedding dimension d does not appear in it. The bound depends only on n, the number of points being embedded, and on the margin. 1 The authors describe going "beyond the above approach based on JL." This refers to Johnson–Lindenstrauss-style dimensionality reduction, the tool that previously produced the extra log n factor. 1

This is a familiar pattern in learning theory. Once a margin is imposed, the geometry of the problem rather than the raw size of the ambient space governs capacity. Large-margin classifiers have long enjoyed dimension-free guarantees for the same reason. Seen that way, the missing d is not a defect. It is the point of the result.

The dimension does not vanish entirely, though. The matching lower bound only holds when α is at least max(n^(-1/2), d^(-1/2)). 1 For very small margins, relative to the number of points or to the dimension, the tightness claim does not apply. So d still marks the edge of the regime where the characterization is known to be exact. Calling the bound dimension-blind overstates things. It is more accurate to say the bound is dimension-free inside a band of margins that the dimension partly defines.

How It Fits the Broader Theory

The result sits within a growing body of formal work on contrastive learning. A survey of the area notes that contrastive learning with linear embeddings has been cast in a PAC learning framework. 2 In that framework, direct optimization is intractable because of non-convexity. A semidefinite-programming relaxation, however, yields efficient algorithms with Rademacher-complexity guarantees, provided a large-margin condition holds. 2

The same overview cites work showing that the VC dimension of triplet comparison functions can reach Ω(N²) for arbitrary metrics on N inputs. 2 Read against that, the new paper shows what a margin buys. Without one, sample complexity can grow quadratically. With one, it drops to linear in n, scaled by 1/α². 12 The authors frame this as "generalization from O(n) samples." 1

The Gap Between Theory and Practice

The practical significance is more complicated. Practitioners building contrastive systems mostly tune other things. They choose embedding width, temperature, batch size and how negatives are sampled. The survey lists these as areas where theoretical understanding remains incomplete. 2 It specifically flags the effects of temperature, batch size, negative sample selection and margin-based gradient scaling as open problems. 2

A worst-case VC bound that ignores d therefore says little about a question engineers face constantly: how large should the embedding be? The new result answers a different question. It asks how many labeled comparisons suffice for any learner in this hypothesis class, given a margin. That question is well posed, and the answer is now tight. But it is not the knob being turned in production training runs, where the margin is implicit, temperature-mediated and rarely measured directly.

The Reading

This is a genuine theoretical advance. It removes a logarithmic factor, raises the lower bound by a full 1/α, and closes a question posed only two years earlier. 1 Its independence from d is a strength of margin-based analysis, not an oversight. The dimension still constrains where the lower bound applies. 1 The theory-practice gap the result exposes is real. It is best read as a map of what remains unexplained, which the survey's open problems already outline. 2 The more useful next step would connect the margin α to quantities practitioners actually control, such as temperature and embedding width.