acceptodds
Under review as a conference paper at ICLR 2027

Optimal VC Dimension of Contrastive Learning With Margin

13 views

Abstract

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, Alon et al. (2024) 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 .

Primary area:
learning theory
Keywords:
Contrastive Learning, Ordinal Embeddings, Learning Theory, VC dimension

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_L32BOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers the combinatorial sample complexity of learning Euclidean embeddings from anchor-positive-negative triplet comparisons. A triplet is labelled only when the relevant pairwise distances are separated by a specified multiplicative margin. Building on Alon et al. (2024), the authors resolve an open question by improving the margin-dependent VC-dimension upper bound from O(nlog⁡n/α2)O(n\log n/\alpha^2) to O(n/α2)O(n/\alpha^2), removing the logarithmic factor and the explicit dependence on embedding dimension. They also prove a matching lower bound in the regime where the margin is sufficiently large relative to the number of objects and embedding dimension: VCdim(H(n,d,α))=Θ(n/α2).VCdim(\mathcal H(n,d,\alpha))=\Theta(n/\alpha^2). The central proof technique randomly projects a high-dimensional margin-satisfying embedding onto one dimension, where each comparison retains a better-than-random probability of being correct. Combining this rounding argument with a one-dimensional Rademacher complexity bound yields the improved upper bound. The lower bound uses an explicit geometric shattering construction. Synthetic and CIFAR-100 experiments provide supporting evidence for the predicted generalization behavior.

Critical strengths
  1. The paper resolves a well-defined open theoretical problem and establishes matching upper and lower bounds in an explicit parameter regime. Removing the logarithmic factor gives a sharp, dimension-independent VC-dimension characterization for fixed positive margins.

  2. The proof strategy is elegant and informative. Gaussian projection turns a high-dimensional margin constraint into a one-dimensional weak classification advantage, which can then be combined with Rademacher complexity to control shattering.

Critical weaknesses

The scope is limited, even though the result is strong. The theoretical formulation concerns only triplet prediction over a fixed collection of nn objects with unrestricted embeddings. It does not directly analyze parameterized neural encoders, InfoNCE optimization, or efficient algorithms for learning such embeddings. The matching lower bound only applies under specified relationships among nn, dd, and α\alpha.

Questions for authors

Can the authors sharpen the VC-dimension characterization outside the matching regime, especially when d<1/α2d<1/\alpha^2 or the margin becomes very small?

1 comment

We thank the reviewer for their high score and positive evaluation of our paper. Regarding the reviewer’s question, we do not yet know how to extend the lower bound in the case when the margin is small. We believe this to be an interesting research question.

Reviewer_mD59OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies learning an embedding of nn items from triplet comparisons with a multiplicative margin α\alpha. It shows that the VC dimension is O(n/α2)O(n/\alpha^2) for α<1\alpha < 1 and O(n)O(n) for α≥1\alpha \geq 1. This improves the previous O(nlog⁡n/α2)O(n \log n / \alpha^2) bound, which follows from the Johnson–Lindenstrauss lemma, by a log⁡n\log n factor and resolves an open question of Alon et al. (2024). The paper also proves a matching Ω(n/α2)\Omega(n/\alpha^2) lower bound for α≥c⋅max⁡(n−1/2,d−1/2)\alpha \geq c \cdot \max(n^{-1/2}, d^{-1/2}), where cc is an absolute constant, improving the previous Ω(n/α)\Omega(n/\alpha) lower bound.

The upper-bound proof has two steps. First, projecting a margin-satisfying embedding onto a random Gaussian direction yields a one-dimensional embedding that satisfies at least a 1/2+α/51/2 + \alpha/5 fraction of the triplets without margin (for α≤1\alpha \leq 1). Second, a Rademacher-complexity argument shows that for m≳n/ε2m \gtrsim n/\varepsilon^2 triplets, some labeling exists that no one-dimensional embedding agrees with on more than a 1/2+ε1/2 + \varepsilon fraction. Taking ε<α/5\varepsilon < \alpha/5 gives a contradiction.

The theoretical results are complemented by experiments which suggest that the error barely depends on the dimension dd.

Critical strengths
  1. It answers a clearly posed open question from Alon et al. (2024), who asked whether the O(nlog⁡n/α2)O(n \log n / \alpha^2) bound could be improved. The paper shows the answer is O(n/α2)O(n/\alpha^2) and proves a matching lower bound, so the VC dimension is now known up to constant factors. The lower bound also improves on the previously known one.
  2. The proof is short and elegant, and the idea may be useful for other comparison-based learning problems.
  3. The paper is generally well-written. The technical overview in Section 2 explains why the earlier approach does not benefit from the margin and gives the intuition behind the new proof, which makes the argument easy to follow.
Critical weaknesses
  1. The improvement is modest. Over the previous bound, the gain is only a log⁡n\log n factor, which is small in practice. The paper presents the bound's independence from dd as surprising, but the previous O(nlog⁡n/α2)O(n \log n / \alpha^2) bound was already independent of dd. I think the main value of the paper is proving a tight/correct answer rather than a large improvement.
  2. The experiments do not really test the main result. The theorem is about the worst case: how many triplets are enough for any data. The experiments only show how one training method does on random triplets, which is an easier case.
Questions for authors

None

1 comment

We thank the reviewer for their positive feedback. We agree that the main contribution of our paper is theoretical, namely to derive tight bounds for the VC dimension of the problem. We agree that the experiments are limited, but we would like to emphasize that they are meant to complement our main result and to show that the bounds are meaningful in a plausible practical scenario.

Reviewer_JXrmOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper is a theory paper, aims to improve the VC dimension bound of contrastive learning with triplets and a margin α\alpha. It improves a better bound by removing the logarithimic factor and also provides a matching lower bound.

Critical strengths
  1. the problem of contrastive learning is important and deserved more theoretical analysis.
  2. the improvement by removing the logarithmic factor is meaningful in theoretical research
  3. the paper provides both and upper and matching lower bounds to make the results optimal
Critical weaknesses
  1. the main weakness is that the considered contrastive learning setting based on triplets is not very interesting in practice. In practice, we consider many more negatives and even all negatives.
  2. the paper should also discuss and comment on how the VC bound connects with the generalization error.
  3. The paper should include more related work on generalization analysis of contrastive learning.
Questions for authors

NA

1 comment

We thank the reviewer for their positive comments and high score. We will include a more detailed discussion of the generalization error guarantees that follow from our result. These follow from established theorems in learning theory, see for example [Alon, Haneke, Holzman, Moran 2021]. We would also like to point out that our upper bound can be extended to hold in the case where there are more negatives (there the Natarajan dimension is more appropriate), by Theorem C.1 in Alon et al. (adapted to the margin case) . We will make sure to make this explicit in our paper and thank you for pointing that out.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.