PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal VC Dimension of Contrastive Learning with Margin

Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, Konstantin Makarychev

arXiv:2609.38834v1cs.DScs.LGstat.ML

TL;DR

The paper studies how many triplet comparisons are needed to generalize learned embeddings, including in the margin setting where improving prior VC bounds was an open question. It combines geometric approximation with one-dimensional projections to prove an O(n/α^2) VC-dimension bound and a matching lower bound in a specified margin regime.

  • Problem

    Despite contrastive learning’s empirical success, its sample complexity and generalization guarantees for learning embeddings from triplets remain insufficiently understood.

    Source: §1 · p. 3, §1.1 · p. 3

  • Method

    The proof combines margin-based one-dimensional projections and geometric approximation with learning-theory bounds for triplet comparisons.

    Source: §1.2 · p. 5, §2 · p. 6, Conclusion · p. 14

  • Results

    O(n/α^2) VC dimension holds for α∈(0,1), with a matching lower bound when α≥max(n^-1/2, d^-1/2).

    Source: §2 · p. 6, Conclusion · p. 14

  • Takeaways & Limitations

    The margin-dependent VC bound is independent of d and takes a step toward understanding contrastive learning’s empirical success.

    Source: Conclusion · p. 14

    A similar polynomial-sign-pattern approach for α>0 would still yield a dimension-dependent Θ(nd) bound.

    Source: §2.1 · p. 7

Abstract

from arXiv · show

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, $\Theta(\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 $\alpha >0$, a triplet $(i,j^{+},k^{-})_{\alpha}$ is satisfied by the embedding $\phi:[n]\rightarrow \mathbb{R}^{d}$, if $\|\phi(i)-\phi(k)\|_2>(1+\alpha)\cdot\|\phi(i)-\phi(j)\|_2$. In this work, we resolve their question by proving that the VC dimension of contrastive learning under any margin $\alpha\in(0,1)$ is in fact $O(n/\alpha^2)$, improving on the previous bound of $O(n\log(n)/\alpha^2)$. We also establish that the bounds are optimal up to constant factors, by providing a matching lower bound of $\Omega(\frac{n}{\alpha^2})$ (the previously known lower bound was $\Omega(\frac{n}{\alpha})$), for $\alpha\geq \max(n^{-1/2},d^{-1/2})$.

1 Introduction

The introduction frames contrastive learning’s generalization guarantees as an open sample-complexity problem, then presents margin-dependent VC bounds and a geometric-approximation approach.

1.1 Sample Complexity of Contrastive Learning

  • PAC-learning asks how many anchor–positive–negative samples are needed to learn an embedding that generalizes to unseen triplets; prior bounds for the no-margin setting are O(min(nd, n^2)).For positive margins, the cited Johnson–Lindenstrauss route gives O(n log(n)/α^2), and Alon et al. (2024) left improving that bound open.Source: §1.1 · pp. 3–4, §1.2 · p. 4

1.2 Our Contribution: Generalization from O(n) samples, under any margin

  • For H(n,d,α), VC-dimension is O(n/α^2) for α∈(0,1) and O(n) for α≥1; lower bounds are Ω(n/α^2) for α≤1 and Ω(n) for α>1.Source: §1.2 · p. 5
  • A margin-based one-dimensional projection satisfies a 1/2+Ω(α) fraction of triplets independently of d, supporting the VC-dimension bound.The proof combines geometric approximation with a one-dimensional analysis and a probabilistic lower-bound argument.Source: §1.2 · p. 5

1.3 Further Related Work

  • Related work connects the question to theories of contrastive learning and to ordinal embeddings that seek geometric representations satisfying pairwise-distance comparisons.The paper identifies Alon et al. (2024) as its closest inspiration for sample-complexity results.Source: §1.3 · p. 6

2 Technical Overview

The proof exploits the margin to reduce the dimension-dependent learning problem to one dimension, where a rounding guarantee conflicts with the inability to fit enough noisy labels.

2.1 Our approach for α > 0: Algorithmic Advantage over Random

  • For α > 0, margin-aware geometric approximation replaces sign-pattern counting, which still gives a dimension-dependent bound.The approach uses a 1D random projection to achieve slightly better-than-random approximation, independently of embedding dimension.Source: §2.1 · p. 7

2.3 Putting things together

  • The proof combines a 1D rounding advantage with a noisy-label fit bound to rule out shattering large triplet sets.A margin-satisfying embedding can be rounded to satisfy more than half the constraints without margin; sufficiently many randomly labeled 1D constraints cannot be fit that well.Source: §2.2 · p. 8, §2.3 · p. 8

2.2 Rounding-vs-Noisy Labels in 1D

  • Rounding a feasible embedding to one dimension preserves a fraction greater than 1/2 of its constraints, even though the rounded constraints lose their margin.The rounding uses projection along a random direction; its advantage over chance is used in the proof.Source: §2.2 · p. 8
  • For m proportional to n/ε² arbitrary triplets, some labeling prevents every real-line embedding from satisfying more than a 1/2 + ε fraction.The argument uses random labels and the VC-dimension bound for 1D triplet classifiers.Source: §2.2 · p. 8

3 Improved VC-dimension: Upper bound of Theorem 1.4

The upper-bound proof projects margin-satisfying embeddings to one dimension, then combines that rounding with a noisy-label bound to obtain a VC-dimension bound independent of d.

3 Improved VC-dimension: Upper bound of Theorem 1.4

  • The VC-dimension is O(n/α²), linear in n and independent of the embedding dimension d.The proof considers α in (0, 1] and rules out shattering sets at a sufficiently large constant multiple of n/α².Source: §3 · pp. 9, 11
  • A margin-α-satisfiable set of triplets can be rounded to a one-dimensional embedding that satisfies some constraints without margin.The proof uses a random Gaussian projection and shows that one such projection attains at least its expected satisfaction fraction.Source: §3 · p. 9
  • For m ≥ c n/ε² triplets, some labeling cannot be fit by any real-line embedding on more than a 1/2 + ε fraction.The proof obtains this bound using random labels and Rademacher complexity controlled by the VC-dimension of the 1D class.Source: §3 · p. 10
  • The contradiction applies the 1D noisy-label bound to a shattered set after rounding its margin-satisfying embedding.The rounded embedding satisfies a fraction exceeding the noisy-label limit when ε is chosen sufficiently small relative to α.Source: §3 · pp. 9, 11

4 A Matching Lower Bound

A constructive shattering argument gives a lower bound matching the upper bound when α is at least max(n^-1/2, d^-1/2).

4 A Matching Lower Bound

  • For α ≥ max(n^-1/2, d^-1/2), the construction shatters Θ(n/α²) triplets, giving the matching lower bound.The condition ensures enough points and dimensions for the construction.Source: §4 · pp. 11–12
  • When α ≥ 1/4, fixing two points and varying the remaining points yields a shattered set of Θ(n) triplets.Each triplet uses the same anchor and positive point, with a different remaining point as its negative.Source: §4 · p. 11
  • The construction assigns shared standard-basis embeddings to the remaining points, decoupling the triplets associated with different pairs.For each labeling, embeddings of the pair can then be chosen to satisfy its triplets.Source: §4 · p. 12

5 Experiments

Experiments test whether generalization error depends on dimension when sample size is scaled by n/α², using synthetic embeddings and CIFAR-100 features.

5 Experiments

  • Training triplets are sampled uniformly, filtered by a ground-truth margin condition, and used to fit an embedding with multiplicative-margin triplet loss.Generalization error is measured on 5,000 held-out margin-separated triplets.Source: §5 · p. 13
  • The synthetic learner directly parameterizes embeddings of Gaussian-drawn points, while the real-data learner uses a linear head over frozen ResNet18 features.The real setup uses 5,000 CIFAR-100 test images and 512-dimensional penultimate features.Source: §5 · p. 13
  • At α = 0.2, curves for d = 16, 64, and 256 lie nearly on top of one another within each n-trajectory.The overlap is reported for both synthetic data and the real-data setup; dimension variation changes real-data error only slightly.Source: §5 · p. 13, Figure 1 · p. 14

Conclusion

The paper resolves an open question about the VC dimension of contrastive learning with a margin. It gives optimal bounds under a condition on the margin, independent of the ground-truth embedding dimension.

Conclusion

  • The work resolves Alon et al. (2024)'s open question about the VC dimension of contrastive learning with a margin.Source: Conclusion · p. 14
  • The paper establishes an optimal VC-dimension bound for learning a ground-truth embedding on n data points, with the lower bound requiring α ≥ max(n^-1/2, d^-1/2).Source: Conclusion · p. 14
  • The bound is independent of the ground-truth dimension d; the approach combines approximation algorithms, geometric projections, and learning-theory bounds for triplet comparisons.Source: Conclusion · p. 14

AI Disclosure

The authors disclose using generative AI tools for exposition, literature search, and experiments.

AI Disclosure

  • Generative AI tools assisted with exposition, literature search, and experiments; the authors state that they developed the main result, proofs, and technical ideas.Source: AI Disclosure · p. 14

A Reduction to 1D

The proof reduces the comparison to geometry in the two-dimensional span of the normalized vectors. It analyzes the resulting angular event and shows its probability is minimized when their angle is π/2.

A Reduction to 1D

  • After normalizing u and v, the proof sets β = 1 + α and reduces the comparison to the plane spanned by those vectors.Source: A Reduction to 1D · p. 19
  • Projecting g onto that plane preserves its inner products with u and v, so the comparison can be expressed using planar angles.Source: A Reduction to 1D · p. 19
  • The angular event is described by |cos(φ − θ)| < β|cos φ|; its geometry is illustrated by the vector configuration in Figure 2.Source: Figure 2 · p. 19, A Reduction to 1D · p. 20
  • F(θ)/π gives the event probability, and F is minimized at θ = π/2; concavity of arctan is then used to obtain a lower bound for α ∈ [0, 1].Source: A Reduction to 1D · pp. 20–21

B Additional Experiments

The additional experiments referenced from Section 5 were run on a standard CPU and could be completed within an hour.

B Additional Experiments

B.1 Synthetic α-sweep

In the synthetic α-sweep, empirical error collapses across (n, α) when plotted against mα^2/n, but curves separate by margin when the α^2 factor is removed.

B.1 Synthetic α-sweep

  • The experiment fixes d = 50 and sweeps α ∈{0.1, 0.2, 0.4}, n ∈{100, 300, 1000}, and m across seven sample sizes over five seeds.Source: §B.1 · p. 21
  • Plotting error against m/n instead separates the curves by margin, indicating the α^2 factor is precise in the bound.Source: §B.1 · p. 21
  • All nine synthetic (n, α) curves collapse against mα^2/n and fall from random-guess error to near zero once mα^2/n ≳1.Figure 3 shows the collapse and the threshold behavior.Source: Figure 3 · p. 21, §B.1 · p. 21

B.2 Real data α-sweep

On real data, empirical error curves decay together when ordered by mα^2/n, while removing α^2 separates them by margin; at matched effective sample size, errors are below synthetic results and decrease with larger n.

B.2 Real data α-sweep

  • For the real-data setup, the study fixes d = 64 and sweeps α over {0.1, 0.2, 0.4}, n over {500, 2000, 5000}, and m over {300, 103, 3·103, 104, 3·104, 105} across 5 seeds.Source: §B.2 · p. 21
  • At the same mα^2/n, real-data errors are well below synthetic errors, and larger n gives lower error.Source: §B.2 · p. 22
  • The linear head explores a structured subspace with O(d · 512) parameters independent of n, so larger n supplies more triplets constraining the same fixed-size matrix.Source: §B.2 · p. 22
  • Real-data curves ordered by mα^2/n decay together to zero error, whereas removing α^2 separates them by margin.Figure 4 shows both diagnostics.Source: Figure 4 · p. 22, §B.2 · p. 22

B.3 Dimension-independence across α

Across the tested margins, the dimension-independence curves overlap except for mild underfitting at d = 16 under tight-margin, high-sample conditions; the learned embedding satisfies the margin constraint on over 95% of test triplets once mα^2/n ≳1.

B.3 Dimension-independence across α

  • Across α ∈{0.05, 0.1, 0.4}, the d-curves overlap within each n-trajectory on synthetic and real data, with mild underfitting at d = 16 for small α and large mα^2/n.Figure 5 shows the dimension comparison; 16 dimensions cannot faithfully embed the synthetic d⋆=50 or CIFAR-100 ground truth up to 512, and tight margins are more sensitive to distortion.Source: §B.3 · p. 22, Figure 5 · p. 23

B.4 Margin sanity check

  • The multiplicative-margin loss is a continuous surrogate for the hypothesis class defined by embeddings satisfying (1 + α)-separation.Source: §B.4 · p. 23
  • Once mα^2/n ≳1, the learned embedding satisfies the hypothesis-class constraint on >95% of test triplets, compared with around 0.5 at the smallest m.The constraint requires the output embedding itself to satisfy (1 + α)-separation.Source: §B.4 · p. 23, Figure 6 · p. 24

Related papers

Loading 2609.38834v1…