Optimal Sample Complexity of Contrastive Learning
Authors: Noga Alon
Dmitrii Avdiukhin
Dor Elboim
Orr Fischer
Grigory Yaroslavtsev
Venue: ICLR 2024 spotlight (2024)
Keywords: learning theory
sample complexity
vc dimension
contrastive learning
metric learning
Primary area: learning theory
TL;DR: We provide tight bounds on the sample complexity of contrastive learning in various settings, without any assumptions on the data distribution

Abstract: Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sample complexity of contrastive learning, i.e. the minimum number of labeled tuples sufficient for getting high generalization accuracy. We give tight bounds on the sample complexity in a variety of settings, focusing on arbitrary distance functions,  $\ell_p$-distances, and tree metrics. Our main result is an (almost) optimal bound on the sample complexity of learning $\ell_p$-distances for integer $p$. For any $p \ge 1$, we show that $\tilde \Theta(nd)$ labeled tuples are necessary and sufficient for learning $d$-dimensional representations of $n$-point datasets. Our results hold for an arbitrary distribution of the input samples and are based on giving the corresponding bounds on the Vapnik-Chervonenkis/Natarajan dimension of the associated problems. We further show that the theoretical bounds on sample complexity obtained via VC/Natarajan dimension can have strong predictive power for experimental results, in contrast with the folklore belief about a substantial gap between the statistical learning theory and the practice of deep learning.

Published as a conference paper at ICLR 2024
OPTiMAl SAMPLE COMPLEXITY OF CONTRASTIVE LEARNING
Noga Alon'; Dmitrii Avdiukhin', Dor Elboim', Orr Fischer*) Grigory Yaroslavtser
Princeton University, "Northwestern University,
Inntittte for Advanced Study, *Weizmann Institute of Science, 'George Mason University, na malonmmath, princeton.... edu, dmitrii i www.:aawwwwwwinnnnrreeeeeeeeeeee edu, dore 1rreim@mm@@mlll com, orr www.ffiswseeeiieee www.:/wwwwiwamm......m.m.... grigory edu
ABSTRACT
Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sample complexity of contrastive learning, i.e. the minimum number of labeled tuples sufficient for getting high generalization accuracy. We give tight bounds on the sample complexity in a variety of settings, focusing on arbitrary distance functions, both general fp-distances, and tree metrics, Our main result is an (almost) optimal bound on the sample complexity of learning fp-distances for integer p. For any p 2 1 we show that ((min(nd, n²)) labeled tuples are neces- sary and sufficient for learning d-dimensional representations of n-point datasets. Our results hold for an arbitrary distribution of the input samples and are based giving the corresponding bounds the Samnii--hhervonenii/aaaaaee mension of the associated problems. We further show that the theoretical bounds on sample complexity obtained via VC/Natarajan dimension can have strong pre- dictive power for experimental results, in contrast with the folklore belief about substantial gap between the statistical learning theory and the practice of deep learning.
di-
INTRODUCTION
Contrastive learning (Gutmann & Hyvärinen 2010) has recently emerged powerful technique
for learning representations, see e.g. Smith & Eisner (2005); Mikolov et al. (2013) Dosovitskiy
al. (2014); Sccrroff al. (2015a); Wang & Gupta (2015); Wu al. (2018): Logeswaran & Lee
(2018a) 8a); Hjelm et al. (2019); He et al. (2020); Tian et al. (2020): Chen et al. (2020) Chen & He
(2021) Gao al. (2021): Chen et al. (2021).
this paper we study the generalization properties
of contrastive learning, focusing on its sample complexity. Despite recent interest in theoretical
foundations of contrastive learning, most of the previous work approaches this problem from other angles, e.g. focusing on the design of specific loss functions (HaoChen et al. (021), transfer learn-
ing (Saunshi et al., 2019; Chuang et al., 2020), multi-viww redundancy (Tosh et al. 202 inductive biases (Saunshi al. 2022 HaoChen & Ma 2023), the role of negative samples (Ash et al. 2022
Awasthi et al. 2022), mutual information (van den Oord et al. 2018 Hjelm et al. ( Bachman
al. 2019 schannen et al. al.]|220000 (2020), etc. (Wang & Isola 2020 sai al. [2221] 2 Zimmermann al.
2021
von Kügelgen et | Mitrovic et al. 2021] Wen & Li 2021).
Generalization is of the central questions in deep learning theory. However, despite substantial efforts, a folklore belief still persists that the gap between classic PAC-learning and the practice of generalization in deep learning is very wide. Here we focus on the following high-level ques- tion: can PAC-learning bounds be non-vacuous in the context of deep learning? Direct applica- tions of PAC-learning to explain generalization in neural networks lead to vacuous bounds due to the high expressive power of modern architectures. Hence, recent attempts towards understanding
Parrially supported by NSF grant DMS-2154082
I Partially supported by the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement No. 949083)

---

Published as a conference paper at ICLR 2024
generalization in deep learning involve stability assumptions (Hardt et al. 2016 PAC Bayesian
bounds (Langford & Caruana 2001; Dziugaite & Roy| 2017: Neyshabur et al. 2017 ,. capacity
bounds (Neyshabur et al. 2019). sharpness (Keskar et al. 201 Lyu et al. [2022] and kerneliza-
tion (Arora et al. 2019 Wei et al. 2019) among others (see e.g. Jiang et al. (2020) for an overview).
In this paper, we make step towards closing this gap by showing that the classic PAC-learning
bounds have strong predictive power over experimental results.
We overcome this gap by changing the assumptions used analyze generalization, shifting the emphasis from the inputs to the outputs. While it is typical in the literature to assume the presence of latent classes in the imput (Saunshi et al., 2019 Ash al., 2022] Awasthi et al.. 2022). we avoid this assumption by allowing arbitrary imput distributions, Instead, we shift the focus to understanding the sample complexity of training deep learning pipeline whose output dimension d, only assuming that by a suitable choice of architecture, one can find the best mapping of given set of samples into Rd. Hence, our assumptions about the architecture are very minimal, allowing us to study the sample complexity more directly. This is in contrast with the previous work, where typical approach in the study of generalization (see e.g. Zhang et al. (2017) ) is to assume that n input points are in Id while here we only assume the existence of embedding of these points into a (metric) space such as RR This avoids the challenges faced by Zhang et al. (2017) and related work, which shows that two-layer network with 2n + d parameters can learn any function of the input.
1.1
OUR RESULTS
Consider simple model for contrastive learning in which labeled samples (z, y² ,2 ........ ....,.2k are drawn i..d. from unknown joint distribution D. Here is referred to as the anchor, y is positive example and 2, are negative examples, reflecting the fact that the positive example is "more similar" to the anchor than the negative examples. Before the tuple is labeled, it is presented as an anchor x together with an unordered (k: + ))-tuple (II,..., Ik+1), from which the labeling process then selects a single positive example yt and negative examples 21 ,.....2..
The goal of contrastive learning is to learn a representation of similarity between the domain points, usually in the form of a metric space. For samples from a domain V, the learned representation is distance function p: V V R. A highly popular choice for the domain is the l,- fp-space under lp distancce Pp(x. y) = [z) f(y]lp p for some f: V Rd with p 2 used most frequently. Our central question is:
How many contrastive samples are needed for learning good distance function?
The number of samples is primary factor in the computational cost of training. While it is typical for the previous work to consider the number of samples required for generalization to be somewhat unimportant and focus on performance on the downstream tasks (in fact, contrastive learning is often referred to as an unsupervised learning method, see e.g. (aunshi et al. (2019)). here we focus specifically on the sample complexity. This is due to the fact that even if the samples themselves might be sometimes easy to obtain (e.g. when class labels are available and (I, y²) are sampled from the same class"), }. the computational cost is still of major importance and scales linearly with the number of samples.
Furthermore, in some settings, sample complexity might itself correspond to the cost of labeling. making the contrastive learning process directly supervised. Consider, for example, a crowdsourcing scenario (see e.g. Zou et al.] (2015)), where a triple is shown as (z, y, 2) to a labeler who labels according to whether or is more similar to x. In this setting, data collection is of primary importance since the sample complexity corresponds directly to the labeling cost.
In this paper, we state our main results first for the case k = in order to simplify the presentation. Our bounds for general i are obtained by straightforward modifications of the proofs for this case.
'This is substantially more general and hence includes special cases typical models used in the literature which make various further assumptions about the structure of 2> (e.g. (Saunshi et al. (2019): Chuang al. (2020); Awasthi et al. (2022))
"In this case, class information is still required, making this approach somewhat supervised. Supervision can be fully avoided, e.g. by creating a positive example from the anchor point (e.g. via transformations). although this can affect the quality of the learned metric due the more limited nature of the resulting distribution.
2

---

Published as a conference paper at ICLR 2024
Table 1: Sample complexity for contrastive learning for dataset of size n. The notation O.,s hides dependence on e and 6. Dimension of the representation is denoted as d. Let min(n, (n, d).
Setting
Lower bound
Upper bound
Even pt Oe (nd) (matching), Thm. 3.2
Ep for integer p
(eds( Thm. 3.1
Odd pt Oe, (n min(dlog n, ni)), Thm.
3.2
Constant d: Oc,(In) (matching). Thm. 3.2
(1 + a--spparate &
(%.a) Thm.
4.2
Óc.(1%/a Thm. 4.2
Arbitrary distance
(n,s("") Thm. 2.7
Oc.(nn²) (matching), Thm. 2.7
Cosine similarity
6e,6 Thm D.3
0 (nd) (matching) Thm D.3
Tree metric
(n)) Thm. D.2
On Thm. D.2
Generalizations, the same settings
Quadruplet learning
Same, Cor. C,3
Same, Cor. C.3
k negatives
Same, Thm. 4.1 C.1
Same, with extra log(A: + 1) factor, Thm. 4.1
Theoretical Results We address the above central question in the framework of PAC- learning (Valiant 1984) by giving bounds on the number of samples required for the prediction of subsequent samples. Recall that we use notation (x. y, v) to refer to unlabeled samples and br,yt,2 2 for their labeled counterparts. In contrastive learning, classifier is given access m labeled training samples {2,; y 2, ) drawn from D. The goal of the classifier is to correctly classify new samples from D. Lee. for every such sample with the ground truth label hidden and thus presented as (Ir, y, z), correctly label it either (ar, y+, ==" (ar, at, ; yy) For the resulting classifier, we refer to the probability (over D) of incorrectly labeling a new sample as the error rate.
Let H be hypothesis class (in our case, metric spaces, ép-distances, etc.). For parameters e, 6 >> O, the goal of the training algorithm is to find with probability at least 1 - a classifier with the error rate most + e", where E" is the smallest error rate achieved by any classifier from H (i.e. the best error achieved by metric embedding, Ep e--emedding, etc.). We refer to the number of samples required achieve the required error rate as sample complexity. See Appendix A for concrete example.
As is standard in PAC-learning, we state results in two settings: realizable and agnostic. Here realizable refers to the case when there exists a distance function in our chosen class (e.g. lg- distance) that perfectly fits the data, i.c. E" O, while in the agnostic setting, such a function might not exist. Let sampled from. We summarize our results in Table I To simplify the presentation, for the rest of the section assume that e, 8 are fixed constants (see full statements of our results for the precise bounds, which show optimal dependence on these parameters). We first give a simple baseline, which characterizes the number of samples required for contrastive learning.
[V] be the number of data points in the dataset, which the triples are
2.7p. The sample complexity of contrastive learning for arbitrary distance functions is (n²), where the lower bound holds even for metric distances.
Theorem 1.1 (Arbitrary distancd] full statement: Theorem
This basic guarantee is already substantially better than the overall (n number of different triples, but still be a pessimistic estimate of the number of samples required. We thus leverage the fact that in practice -p-spaces are typical choice for representation of the distance function between the data points. In partieular, fg-distance (and the related cosine similarity) is most frequently used as a measure of similarity between points after embedding the input data into Rd Here the dimension d of the embedding space is typically a fixed large constant depending on the choice of the architecture (e.g. d = 512, 1024, 4096 are popular choices).
Our main results are much stronger bounds on the sample complexity of learning representations under these E, distances. For any ly-distance we get the following result:
In this paper, the only requirement for arbitrary distances symmetry, i.e. p(x, v) p(y,
3

---

Published as a conference paper at ICLR 2024
Theorem 1.2 (lp-distance upper bound (informal), full statement: Theorem 3.2 For any constant integer P, the sample complexity of contrastive learning under l--distance is O n²)) if is even, and O (min( nd log n, n²)) if is odd. Furthermore, if d ((1), then the sample complexity Onn) for any positive integer p.
We show an (mmn((nd, n²)) lower bound for any ly-distance, essentially matching our upper bounds:
Theorem 1.3 (lp dii-tnttece lower bound (informal), full statement: Theorem 3.1 For any constant integer p, the sample complexity of contrastive learning under --iiitaance is [min((nd, n²² n²)).
For cosine similarity, we show the same result:
Theorem 1.4 (Cosine similarity (informal), full statement: Theorem D.3 The sample complexity
of contrastive learning under cosine similarity is @(min(nd, n²)).
Using the techniques we develop for the above results, also immediately get the following result:
Theorem 1.5 (Tree distance (informal), full statement: Theorem D.2 The sample complexity of contrastive learning under tree distance is (m) and On log
We also present multiple variations and extensions to complement the main results above. First, we show that the results above can be extended to the case where the positive example has to be selected among l options instead of just two, as is typical in the literature. This results in a log k increase in the sample complexity (see Theorem 4.1. J. Furthermore,
results can be extended to the case when the samples are well-separated, i.c. the distance to the negative example is at least a factor (1 + a)) larger than the distance the positive example. This is frequent case in applications when the positive example is often sampled to be much closer to the anchor, which is often referred to as learning with hard negatives. In this case, we give an (nnaa²) upper bound and an (2(n/a) lower bound (see Theorem 4.2
Finally, we show in Corollary C.3 that all of our results can be adapted to another popular sce- nario in contrastive learning, where instead of sampling triples. one instead samples quadru- ples ((x 22 ), (z5, 224 )) with the semantic that the pair (xf .z." is more similar than the pair (rz .x4) ). While the lower bounds transfer trivially, it is somewhat surprising that the upper bounds also hold for this case despite the fact that the overall number of different samples is ((n*).
Outline of the techniques To describe the main idea behind our techniques, consider the case of f2-metrics in d-dimensional space. Let f: V - Rd be function mapping elements to their representations, and then the query (z, y, 2) is labeled (x, yt. 22" () if ff((z) f(ylll < f((z)) where ft denotes the i-th coordinate of the representation. This condition can be written in the form fa())) < O, where P is some polynomial of de- gree 2. Hence, every input triplet corresponds to a polynomial such that the label of the triplet is decided by the sign of this polynomial. We show that the number of possible satisfiable sign combinations of the polynomials and hence the largest shattered set of triplets - is bounded.
[l.(())) f()) ll2. This is equivalent to Ei (z) fe(v))² < EE= (f((x)
( fa(z), fi (v)...., fi
Experimental results To verify that our results indeed correctly predict the sample complexity, perform experiments on several popular image datasets: CIFAR-10/100 and MNIST/Fashion- MNIST. We find the representations for these images using ResNet18 trained from scratch using various contrastive losses. Our experiments show that for fixed number of samples, the error rate is well approximated by the value predicted by our theory. We present our findings in Appendix
1.2 OTHER PREVIOUS WORK
For survey on metric learning we refer the reader the the monograph by Kulis (2013). A popular approach to metric learning involves learning Mahalanobis metrics, see Verma & Branson (2015) for PAC-like bounds in this setting. Wang & Tan (2018) study the sample complexity of this problem in the presence of label noise. We note that our bounds are more general since Mahalanobis distances only represent subclass of possible metries.
4

---

Published as a conference paper at ICLR 2024
Related problems are also studied in the literature ordinal embeddings, which requires adaptive queries in order to recover the underlying embedding. This is in contrast with our work where the samples are taken non-adaptive from an unknown distribution. For triplet queries,
Castro (217)) shows that it's possible to recover the embedding from the triplets queries, up to a trans- formation, and provide convergence rates for quadruplet queries. Ghhohh al. (2019) shows that Oldn log n) adaptive noisy triplet queries suffice for recovering an embedding
to a transforma-
tion with O(1) additive divergence. Terada & Luxburg (2014) shows that it's possible to recover the ground-truth points up to transformation assuming that these points are sampled from a continuous distribution assuming the kNN graph is given.
PRELIMINARIES
In order to state our main results, we first introduce formal definitions of contrastive learning in the realizable and agnostic setting and the associated notions of Yapnik-Chervonenkk and Natarajan dimension. We start by giving the definitions for the simplest triplet case.
Definition 2.1 (Contrastive learning, realizable case). Let H be hypothesis class and p E H be an unknown distance Sunction Given access to samples of the form (z,
from a distribution DD meaning p(x, y) < p(x, 2), the goal of contrastive learning is to create a classifier from H. which accurately labels subsequent unlabeled inputs. For an error parameter e E (0, 1/2) [ the sample complexity of contrastive learning, denoted as Sz(e, 8), is the minimum number of samples required to achieve error rate with probability at least 1 8.
Definition 2.2 (Contrastive learning, agnostic case). Let H be hypothesis class. Given access to labeled samples of the form (x, "²,2"""0000"""" from a distribution D, the goal of agnostic contrastive learning is to create classifier from H. which accurately labels subsequent unlabeled inputs. For an error parameter e > 0, the sample complexity of contrastive learning, denoted as S (c,8), 3), is the minimum number of samples required to achieve error rate c e" with probability at least 1 6, where e" is the best error rate that can be achieved by a hypothesis E H.
The above definitions can be naturally generalized to the case when instead of triplets we get inputs of the form
Ik+1) and the objective is to select x; minimizing p(x,
Definition 2.3 (Quadruplet learning). If instead of triplets as in the definitions above, the samples are quadruples of the form ((z, v). (z, w)) labeled according to whether the (I, pair is closer than the (z, w) pair, we refer to this problem as quadruplet contrastive learning and denote the corresponding sample complexities as 5) and
VC and Natarajan dimension The main tool used for sample bounds is the (VC) dimension for binary classification and the Natarajan dimension for multi-label classification.
Definition 2.4 (VC-dimension (Vapnik & Chervonenkis, 197I)). Let X be the set of inputs. Let H. C 2 be set of subsets of X, called the hypothesis space. We say that A C X is shattered by H if for any B C A there exists hypothesis h E H such that h n A = B. Finally, the Vapnik-Chervonl Chervonenkis (VC) dimension of H defined as the size of the largest shattered set.
Intuitively, a set A is shattered if all of A| possible labelings on A are realizable by H. In our case, the set of inputs X defined by all possible triplets on V. i.e C V3.
The set of distance functions A will vary depending on the setting. Below we show results when A contains 1) all possible distance functions @ 2) all metrics induced by the fp-norms over n points in Rdd and 3) other distance functions, such as tree metrics, cosine similarity etc.
For non-binary (finite) labels, the key property we use to characterize the sample complexity of problem is the Natarajan dimension, which generalizes the VC dimension Ben David et al. (1995):
'The inputs are labeled based on p. With a slight abuse notation, we refer to both the distance function and the hypothesis (i.c. a classifier) it defines as p-
'The 1/2 error rate can be achieved by random guess, which requires zero samples. Hence, theory makes prediction only for non-trivial values of e, as in Blumer al. (1999)
"We only consider functions such that all distances are different. This is reasonable assumption since in practice the probability of encountering exactly the same distances is zero. This assumption simplifies the analysis since we only need consider the binary classification case
5

---

Published as a conference paper at ICLR 2024
1989)). ). Let X be the set of inputs, Y be the set of labels, and let H C Y be a hypothesis class. Then S S X N-shattered by H if there exist fi, fo: X + Y such that fi (z) # f2(2) for all A and for every B S A there exists g H such that:
Definition 2.5 (Natarajan dimension Natarajan
g(x) = (a) for a B and g(x) f2(x) for a $ B
Finally, the Natarajan dimension Ndim of H is the maximum size of an N-shattered set.
Lemma 2.6 ((Ben David et al. 1995), Informal). If |Y] is finite, then for the sample complexity S(e, 8) of the realizable case holds that:
( log |Y|
(Ndim(H)
polylog 1 2 and (Ndim(H) polylog
S(e, -
6
In the agnostic case:
()) = =0 (ddimH) H) log Y
( 6²
(1) and Ω [Ndim(H) (H)
polylog
polylog {
22
VC-dimension is special case of iitarjanddimensonn when [Y] 2. In Appendix A we give
examples to illustrate the notion of shattering.
Before presenting our main results, we state the following simple baseline, which we prove in Ap- pendix D
Theorem 2.7 (Arbitrary distance). For an arbitrary distance function p: V x V + R and dataset the sample complexity of contrastive learning is Sa(c, 6) θ polylog (:: in the
size size
realizable case and Sig (E, = ( polylog (+) in the agnostic case. Furthermore, the lower bounds hold even if is assumed to be metric.
CONTRASTIVE LEARNING IN f--NORM
In this section, we show in most cases optimal bounds for the sample complexity of the contrastive learning problem for the f--metric in dimension Rd, for any constant integer 2 1. First, we give the following lower bound, whose proof deferred Appendix B.1 Recall that pp(ar, [=f f(y)lp for f: Edd
Theorem 3.1 (Lower bound for lp ép-distances). For any real constant p E (0.+ dataset V of size n, and the Ep distance Pp: V x V - R in d-dimensional space, the sample complex- ity of contrastive learning is S3(e, 8) = S2 (min(nd,n)) polylog ( 2)) in the realizable case and (e =52 min((d,n.))) 2²
polylog ( (e) in the agnostic case.
We then show that for integer p this bound can be closely matched by the following upper bounds:
Theorem 3.2 (Upper bound for f fi-dittanees for integer p). For integer dataset V of size n, and the Ep distance Pp: V learning is upper-bounded as shown in Table 2
R in d-dimensional space, the sample complexity of contrastive
Setting Even p
Realizable case
Agnostic case
min(nd. n²) n²)/e min(nd log n, n² n²)/e n/e
min(nd, n² )/² min(nd log n, n²²) n²2/ n/e²
Odd Constant
Table 2: Upper bounds on sample complexity bounds for é, distances up to polylog (1)
Proof. For the first two cases, we assume d n, since otherwise, the bounds follow from Theo-
rem 2.7 Our proof uses the following result of Warren (1968) from algebraic geometry:

---

Published as a conference paper at ICLR 2024
Fact 3.3 (Warren (1968). Let m 2 f 2 be integers, and let Pi....,,Pp ,m be real polynomials E variables, each of degree I k. Let
U(PI,...,PP'))
{ & P.(T) + for all i [m]]
be the set of points I IR. which are non-zero in all polynomials. Then the number of connected components in U (P,,...,PPm) is at most (4)km/E)².
In order to bound the sample complexity of the contrastive learning problem, by Lemma 2.6 it suf- fices to bound its Natarajan dimension, which in the binary case is equivalent to the VC dimension. In particular, we show that for a dataset V of size n, the VC-dimension of contrastive learning for lp- distances in dimension d is (n min n)) for even 2 2 and OOdd n) for odd p 2 1. For this it suffices to show that for every set of queries Q {uu 24, } of size 12(n min d, n)), there exists labeling of Q that cannot be satisfied by any embedding in a d-dimensional ép ép-saace We split the analysis into cases for even p and odd p.
Upper Bound for Even We associate each data point v E V with set of d variables (1(2).... ..... Ed(e), corresponding to coordinates of v after embedding the d-dimensional space. Let F (x) (v1). F.(l))))......)
(a(()) ..... (Un) ...., (((()))))((( For every constraint (u, v, w),, we define the polynomial P Pa.,,: Rnd T as
P P(u,pou) (2) = - (z)((u)- =z
Note that P u (i) < if and only if the constraint (u, ot, w- is satisfied, and P an) > and only if the constraint (u, wt, v)) ) is satisfied. Finally, we define Pı,..., J....,Pa P.. for E [m] as (7) = Pu Pa (i).
For any labeling @ of the queries Q and for any i E [m]] we define 8; (i) = the i'th query (u, Us. w:) E Q is labeled as (u, of wi ), and s; sx( = -1 otherwise.
We make the following observations, which are proven in Section B
Lemma 3.4. For E {-1,1)"m, define C, = fii Rd sign P(( s; for all i}. Then:
1. For distinct s, E (-1,,1 we have C. nC. 0.
2. Each C, is either empty or is a union of connected components of UPI..... Pm).
3. Let Q be labeling of Q. Then C2(²) # 0 if and only if there is mapping V Rd satisfying all the distance constraints of Q.
We now complete the proof for the case of even p. Defining Pi...., ....,P. Pm as above, by Theorem 3.3 there are at most (tepm// na) nd connected components in the set U(P.... iP...... Pm.. Since for two la- belings Q1, Q2 of Q holds that s(Â1) # s(22), then by Lemma 3.4 either the sets Caig,) and C.t are different connected components, or at least one of them is empty. Moreover, the number of possible labelings of Q is 2nh which is greater than (4epm/nd)nd when choosing m 2 end for sufficiently large constant c. Therefore, for at least one labeling Q it holds that C. Cx(@)) = Since there is no embedding satisfying the distance constraints of @ the claim follows.
Upper bound for odd p. In the case of odd p it suffices to show that for dataset of size n in dimension d, the VC-dimension of contrastive learning for -p-ditaances is ((nd logn). Unlike in the even p case, our distance constraints are comprised of sums functions of the form (w))= and are thus not polynomial constraints. On the other hand, we note that if we have some fixed ordering of the points w.r.t. each coordinate, these constraints become polynomials. To address the issue, enumerate all possible choices for the ordering of the points w.r.t. each coordinate and show that there is labeling Q such that embedding satisfies it, regardless of the ordering.
Similarly to the case of even p. we associate with each v E a set variables I (U)...., (.(
Let 7 (v1), .., (((() ) ....., 2n (va), ( F.(((,))))) For every coordinate [d] we fix the
7

---

Published as a conference paper at ICLR 2024
ordering of the points w.r.t. this coordinate, ie. we fix permutation x(); [n] + [n] such that Iy (1)) I z4 (2)(00)))) S ... I (1((000()))) and bound the number of satisfiable labelings which respect this ordering. We define a = if (v( 2 x²(1) and o = -1 otherwise, and refer the order. Then, for any constraint (u, w), define the polynomial Pu,., R + R:
P(u,,,w) (T)
Σ j=1
- 2)()) -2))))))))()
U' (w) - -I,
Note that P w.) uo) (I) < 0 if and only if the constraint (u, ut, w ) is satisfied for the selected order 7 ..... ((d) (and likewise for P(n,,,.) . (z) > and (u, wt v )). Similarly the case of even p, we define PI...., Pm for i E [mm] as P. Pugin ang (T), and for any labeling Q of queries Q, for all E [m]] we define (Q)) 1 if the i'th query (ug, ve, we) E Q labeled as (us, vi', w; and otherwise.
s((Q) =
As in the of even p. by Fact 3.3 there most (4epm/nd) connected components in the set UPP....., ). Therefore, there are at most (4epm/nd) nd choices of labels which are satisfiable in a manner that respects the ordering T())
(d)
Taking m [nnd l)) we have that 2 choices the permutations ,("),..., ........ T
Since there are (n!)d nnd possible (n) and hence at most as many orders Ø, there are at most (4epm/nd)md nd possible labelings for which there exists some order such that the set of constraints
4epm nd
satisfiable and respects this order. Since (4epm/nd) nd nd is less than 2mh there exists a choice of
labeling Q for which the constraints are not satisfiable for any order, i.e. Q is not shattered.
Upper Bound for Constant d. We will proof the following statement: for constant odd p (0, +00), dataset V of size n, and the lp distance Pp: V x V - IR in a d-dimensional space, the VC dimension of contrastive learning is O(nd)). This gives optimal bound for constant d.
Similarly the proof above, assume that d² n. We then prove the sample complexity bound by bounding the VC dimension of the problem by Ondd),, and obtain the sample bounds using Theorem 2.6
Similar to previous cases, we associate with each v E V set of d variables x (.)),..,..(()) Let (x) (v1). "((())))...,)))))......)))) (v,
We associate each constraint with 2nd polynomials in the following manner: for any constraint (u, v, w) and any choice {-1, 12 we define the polynomial Pr,u,,,: R Ra
d
Pr. Pr, (T)
Σ (1)=,(1)) x,())) 1=1
Σ rld -x) -
1=1
where T(J) is the value of the j'th coordinate of
We note that the sign pattern of the set of polynomials (e) z ()r determines the sign of Σÿ= (w)-;, - (u)- (")lP Therefore, for different choices signs for the constraints, the solutions satisfying them must be contained in different connected components of U UPP,...,,PPaa..
By Fact 3.3 there are at most mmnn)""m"")""" connected components the set UPP..... Pyad Therefore, taking 2 end? for sufficiently large (depending p), we get that 2m > (dey2"mm/nd)"" m/nd)rd, meaning there is a choice signs for which there no solution, iee. these samples cannot be shattered.
4 EXTENSIONS
Reducing dependence on n While our results show that the dependence on n is necessary, in practice be avoided by making additional assumptions. An extremely popular assumption is
8

---

Published as a conference paper at ICLR 2024
that the existence of &o < n latent classes in the data (see e.g. Saunshi al. (2019)). In this case, one can consider using an unsupervised clustering algorithm (e.g. pretrained neural network) to partition the points into & clusters and then apply our results classes instead of individual points, effectively replacing n with k in all our bounds.
Extension to l negative samples: In this extension, we consider setting in which each sample is a tuple (z, "i,...,,,x........... E y and a labeling x," ...... ff. -1-1:--- Fk++ is a choice of an example x; which minimizes minze[le+1] p(r, zy); ), i.e. p(z, vi) < p(a, for all j * i. As an immediate corollary our results, we obtain bound the sample complexity for the k negative setting (in fact, our results for all distance functions considered in the paper extend to this setting, see proof in Appendix C.I]:
Theorem 4.1. For constant p. dataset V of size n, and the ly distance Pp= V V d- d-dimensional space, the sample complexity of contrastive learning Ey e--distances with l negatives is bounded as shown in Table
IR in
P Even Even
Realizable?
Upper bound up to polylog (1)
Lower bound up to polylog
(2:
Realizable
min(nd, n²)) log(k + 1)/e
minn n n²) f/e
Agnostic
min(nd, n² log (k + 1)/e²
min (nd, n² /e2 n
Odd
Realizable
min(nd log n, n²) log(k + 11/e
min(nd, n )/e min(nd, n²² n///
Odd
Agnostic
min(nd log n²) log(k + 1)/e²
Table 3: Bounds sample complexity for Ep distances with k negatives
Well-separated samples: this extension, we focus on the most popular ly-distance and con- sider an "approximate" setting, where the positive and negative samples guaranteed to be well- separated, i.e. their distance from the anchor differs by at least a multiplicative factor. This scenario highly motivated in practice since the positive example typically sampled be much closer to the anchor than the negative example. We show that in this setting the sample complexity can be improved to be almost independent of d
For parameter O < a < 1, we assume that our sample distribution D has the following property: If (zz, att,,")) supp(D), then p(z,z) > (1+ + a)p(z, y), p(z, y) > (1 + a)p(z, =). We call a distribution with this property well-separated. We show that for the fy-distance, the sample complexity of the problem in this setting is between (n,s(n/o) and Or,(nn/²)). This result is proven in Appendix
Theorem 4.2. The sample complexity of (1 + a) -separae contrastive learning for la distance is Sa(c, 8) = ...s (3)) and 5) = 2e.55 (a).
Contrastive Learning for Other Distance Functions: In Appendix [ we show near-tight sample complexity bounds for contrastive learning in other distance functions, such as tree metries, cosine similarity, class distances, and prove tight general bounds for arbitrary metrics. We also extend our results to quadruplet contrastive learning.
5 CONCLUSION
In this paper we have given theoretical analysis of contrastive learning, focusing the general- ization in the PAC-learning setting. Our results show (in most cases) tight dependence of the sample complexity the dimension of the underlying representation. It remains open whether our results can be made optimal for fy-distances for odd It is also open how the results can be improved via a suitable choice of batched adaptively chosen comparisons (see e.g. Zou et al. (0155). Note that in the non- non-batched adaptive query setting optimal bounds on the query complexity are known be (n log n) (Kannan et al. [996] Emamjomeh-Zaun -Zdeh & Kempe 2018). On the experimental side, while we show asymptotic convergence between our theory and practice, it might be worth looking into further refinements of our approach which can better capture the fact that the constant ratio between the observed and predicted values tends to be small.
Disregarding polylog factors in d.

---

Published as a conference paper at ICLR 2024
REFERENCES
Ery Arias-Castro. Some theory for ordinal embedding. Bernoulli, 23(3): (33):1663-1192 August 2017.
ISSN 1350-7265. doi: 00.3150/15-BB5 BB-9999..
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 URL http://
of Proceedings of Machine Learning Research, pp. 322-332. PMLR, 2019. proceedings mlr.. wtw.:/innnn......es.s..ee. wwwpprewsvvviee aarra/aaoaaaaa0 9tm
Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the role of negatives in contrastive representation learning. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Re- search, pp. 7187-7209. PMLR, 2022. URL TtRL/htts:://// http:////ccceeen..c.ooo mml.iiinngmmm.....m.mmmmm.. mtt.ppess//1111 22h html
Pranjal Awasthi, Nishanth Dikkala, and Pritish Kamath. Do more negative samples necessarily hurt in contrastive learning? In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learn- ing Research, pp. 1101-1116. PMLR, 2022. URL v1 wthhstt.. 122.. html
.mlr. press/
Philip Bachman, R. Devon Hjelm, and William Buchwalter. Learning representations by max- imizing mutual information across views. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Achh-Bucc Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 15509-155199 2019. URL https: htwp:e/de////ooeeeennecoe. .ew.ee.ddd.nnn................. www.rpnu......... wwwpeeps...pppppee/eeeepee cc/paper/2011 hash/
-bbbeeesSsb-Abbtaaa..... htmll
Shai Ben David, Nicolo Cesabianchi, David Haussler, and Philip M Long. Characterizations of learnability for classes of (O.... n)-valued functions. Journal of Computer and System Sciences, 50(1):74-88) 86, 1995.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapmik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929-966) 1989.
Arthur Cayley. A theorem on trees. Quart. J. Math., 23:376-378, 1878.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 1597-1607. PMLR, 2020. URL http::////cccceeeg....o html
mlr. www.peess/v11//ceee
Ting Chen, Calvin Luo, and Lala Li. Intriguing properties contrastive losses. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 11834-1 1845, 2021. URL haaa1/2288116223333100000001 Aateraaattttttt---ttattttttc.t.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Computer Vision and Pattern Recognition, CVPR 2021, vir-
IEEE Conference
tual, June 19-25. 2021, pp. 15750-15758. Computer Vision Foundation IEEE,
2021. doi: 10.1099CCVP44444.0001....5
URL https://openaccees Exploring wtteoooonnnn____pm_eee11eeeeee Siamese
thecvf. com/ httpa///cootteee////////////////
html
10

---

Published as a conference paper at ICLR 2024
Ching- Yao Chuang, Joshua Robinson, Yen-Chen Lin, Antonio Torralba, and Stefanie Jegelka. De- biased contrastive learning. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, De- cember 6-12, 2020, virtual, 2020. URL htt.:tttpp://pprcceeetee 2020/hash/ htt.aa//s.cccccccccooaaaaeeeee1. 4a873 Abstract htmm
www..nn...nnnnnnennei.e...n..nne neur ps cc/paper/
Alexey Dosovitskiy, Jost Tobias Springenberg. Martin A. Riedmiller, and Thomas Brox. Dis- criminative unsupervised feature learning with convolutional neural networks. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.). Advances in Neural Information Processing Systems 27: Annual Conference on Neu- ral Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. 766 766-774, 2014. httpttppsssppppceeeignge.eeeeeee neure ips. httpppeer/1///aaeee 07563a3fe (eeeee3aa4443aaaaa
Abst html
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Gal Elidan, Kristian Kersting, and Alexander Ihler (eds.), Proceedings of the Thirty-Third Conference Uncertainty in Artificial Intelligence, UAI 2017, Sydney, Australia, August 11-15, 2017. AUAI Press, 2017.
uai 2017 http//////ceeeeee/////eeee/e//e/ http:///pw..ppppppppppaeaeeeeeee 173.pdf
Ehsan Emamjomeh-Zadeh and David Kempe. Adaptive hierarchical clustering using ordinal queries. In Artur Czumaj (ed.). Proceedings of the Tweety- Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pp. 415-429. SIAM, 2018. doi: 10.1 10.1137/1.978161 17157/99781111175031.22 URL 9781611 9750311 .28
Tianyu Gao, Xingcheng Yao, and Danqi Chen. Simese: Simple contrastive learning of sentence embeddings. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / 2021, pp. 6894-6910. Association for Computational Linguistics, 2021. doi: 10.18653/1/2221. emnlp-main.552 552.. URL httpt /oo. .ogg 10.
Punta Cana, Dominican Republic, 7-11 November,
emn 1o-main..55 552,
Nikhil Ghosh, Yuxin Chen, and Yisong Yue. Landmark Ordinal Embedding. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: new estimation prin- ciple for unnormalized statistical models. In Yee Whye Teh and D. Mike Titterington (eds.), Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13-15, 2010, volume of JMLR Pro- ceedings. pp. 297-304. JMLR.org, 2010. URL http:://proceeeeeeeeeee pttpeaddiii.ssm.....rssssss// gutmannn 0a html
mlr
Jeff Z. HaoChen and Tengyu Ma. A theoretical study of inductive biases in contrastive learn- ing. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, OpenReview.net, 2023. URL id-AuEqNlEAmed
net/pdf?
Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Ad- vances Neural Information Processing Systems 34: Annual Conference on Neural In- formation Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp- 5000 5011, 2021. URL
newrips wtt.cccccppeeeee wccpppppee//2///assssss -wteeag-bbbtrrttte .htttttetttmmmlll.l...
2
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochas- tic gradient descent. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.). Proceedings of the 33nd International Conference on Machine Learning. ICML 2016, New York City, NY. USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1225-1234. MM.R.rrg. 2016. JRI.tttp. htttt::/proceed:: www.eediinggg... ngs. www.rr.presssvveem 8/ha har 6. html

---

Published as a conference paper at ICLR 2024
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick. Momentum contrast for unsupervised visual representation learning. In 2020 IEEE/CVF Conference on Computer Vision and Pattemn Recognition, CVPR 2020. Seattle, WA, USA, June 13-19, 2020, pp. 9726- 9735. Computer Vision Foundation / IEEE, 2020. doi: 10.1 10.100//9R4222002200000000 1110://2R4200000... 202.02220000020002..020
URL.
R. Devon Hjelm, Alex Fedorov, Samuel Lavoie- Karan Grewal, Philip Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:
//openreview.
www.nntt..foroo wwt. d=
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL htttttts:///eeeeeeeesss
net / ftrumoormmoo S
William B Johnson. Extensions of lipschitz mappings into a hilbert space. Contemp. Math., 26:
189-206, 1984.
Sampath Kannan, Eugene I.. Lawler, and Tandy J. Warnow. Determining the evolutionary tree using experiments. J. Algorithms, (161:52,, 1996. doi: (9006/jagm1196.0033. URL https: 1936.0035
//doi.org/10.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In 5th International Conference on Learning Representations, ICLR 2017. Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. htt.t:t/p///ppptt
net. met/forumss i dd=11 o Ygg
Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Tront, 2009.
Brian Kulis. Metric Learning: A Survey. Foundations and Trends@ in Machine Learning, 5(4):
287-364, July 2013. ISSN 1935-8237, 1935-8245, doi: 10. 15111/2200000011.
John Langford and Rich Caruana. (not) bounding the true error. In Thomas G. Diet- terich, Suzanna Becker, and Zoubin Ghahramani (eds.), Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, Canada], pp. 809-816. MIT Press, 2001. URL httpss: hewp:rooceeeiii.....i........ee. neurips. oc/paper/2001/nast ott.://ccceceeaaaaaaaaaeaeaaaaaa
Abstract html
Guillaume Leelere, Andrew Ilyas, Logan Engstrom, Sung Min Park, Hadi Salman, and Aleksander Madry. FFCV: Accelerating training by removing data bottlenecks. / whgg...h.......... com/
libffcv/ffew/ 2022.
Lajanugen Logeswaran and Honglak Lee. An efficient framework for learning sentence representa- tions. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018a. URL
/tttps:/ccpenreviee
net fdrummidd=JJJJx2b00
Lajanugen Logeswaran and Honglak Lee. An efficient framework for learning sentence representa- tions. arXiv preprint arXiv: /83.0083,, 2018b.
Kaifeng Lyu, Zhiyuan Li, and Sanjeev Arora. Understanding the generaliza- tion benefit of normalization layers: Sharpness reduction. In NeurlPS, 2022. http:://papers.mipp wwtpssccppppppp..... fi wttp://faaee/eaa/eeeea22/ @FFolc22212255772e/3333339933933 Ctt.:p/possaaa--aaooaaat------ee
URL
html
Tomás Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. In Yoshua Bengio and Yann LeCun (eds.), 1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 2013, Workshop Track Proceedings, 2013. URL http:htt////aat org. htrg//bss/330 3001 33811
12

---

Published as a conference paper at ICLR 2024
Jovana Mitrovic, Brian McWilliams, Jacob C. Walker, Lars Holger Buesing, and Charles Blundell. Representation learning via invariant causal mechanisms. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
ew net/ wwtt/foouo//reoo formm? htt.:t/eeooommmm.dgg..e...e.e 9=
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foumdations of Machine Learning, Second Edition. MIT Press, December 2018. ISBN 978-0-262-35136--.
B. K. Natarajan. On learning sets and functions. Mach. Learn., 4:67-97, 1989. doi: 10.1007/ BF001 14804. /ttps::s:///o. http://///....oc/...0..00/////10
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gareet (eds.), Ad- vances in Neural Information Processing Systems 30: Annual Conference
Neurul In- formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp.
5947-5956, 2017. URL https::/proceddnnngts hew.reeeedddnns...ei...s.s....s. wwtp:eewwppppppppe//eeeeee.eee wttpp/pppp///////aaaaaapaaa
Awstrrasttttt.e.. html
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of ower-parametrriationn in generalization of neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA. May 6-9, 2019. OpenReview.net, 2019. Btt.tttts////peneeveee ottp:///eweeett.eoooooooooooooo.
net. feret/foorree www.mmrrrrrooo.ooomooooooooooorr Bagggggacyy
Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning, In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 5628 5028-666363 5637. PMLR, 2019. http:hht:///roceeeeee
mlr. w...ppess/vv/// www.ssunnssshiiie 9a. html
Nikunj Saunshi, Jordan T. Ash, Surbhi Goel, Dipendra Misra, Cyril Zhang, Sanjeev Arora, Sham M. Kakade, and Akshay Krishnamurthy. Understanding contrastive learning requires incorporating inductive biases. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference Machine Learning, ICML 2022, 17- 23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 19250 19286. PMLR, 2022. URL https:: htt.://nnnnmm...p.e./// press/ v1 1tmm
mlr
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In IEEE Conference on Computer Vision and Pattern Recog- nilion, CVPR 2015, Boston, MA, USA, June 7-12, 2015, pp. 815-823. IEEE Computer Soci- ety, 201 doi: 11109//VPR.2015.7996668 UtLhhttp:://dat /tttpp/://bl..orr//001111//////0 1109////..////PP 2015. 7298682]
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings the IEEE conference on computer vision and pattern recognition, pp. $15-823,10 2015b.
Noah A. Smith and Jason Eisner. Contrastive estimation: Training log-linear models on unlabeled data. In Kevin Knight, Hwee Tou Ng, and Kemal Oflazer (eds.), ACL 2005, 43rd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, 25-30 June 2005, University of Michigan, USA. pp. 2005. doi: 10.31 00.3115/2118440112219 121199880.111884444 URL
The Association for Computer Linguisties, oo0-aaolooo.oo//0000004000
Yoshikazu Terada and Ulrike Luxburg. Local Ordinal Embedding. In Proceedings of the 31st International Conference on Machine Learning, pp. 847-855. PMLR, June 2014.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (eds.), Computer Vision ECCV 2020 16th European Conference. Glasgow, UK, August 23-28, 2020, Proceedings, Part XI, volume 12356 of Lecture Notes in Computer Science, pp- 776-794. Springer, 2020. doi: 10.1007/
13

---

Published as a conference paper at ICLR 2024
978-3-030-58621-8//
URL /ttp:////////o/oo////////0000000
45
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view re- dundancy, and linear models. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato (eds.), Al- gorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pp. 1179-1206. PMLR, 2021. URL http:
//proceedings. mmx. pwwps/pesss........ wttpp//www/ttsssa///eeep
html
Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. Self- supervised learning from multi-view perspective. In 9th International Conference on Learning Representations, ICLR 2021, Viriual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL
https::/gpeenevil iew. net/ forum? ?id=- b jwp
Michael Tschannen, Josip Djolonga, Paul K. Rubenstein, Sylvain Gelly, and Mario Lucic. On mutual information maximization for representation learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenRe- net wwtteewwwoo.oommeddddeeeeeeee
view.net, 2020. URL httpt: http:::::///peerviiiiee
Leslie G. Valiant. theory of the learaale.. Commun. ACM, 17111:11344111 1984, doi: 10. 1145/1968. 1972. URLhttpss: //tp::///ooii wtt.d/do......111111......
1972
Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. CoRR, abs/1807 01118807773335 2018. URL httpp: wwtp:xixivorrgbbbbooo abs//805..11 03748
Vladimir N Vapnik and Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 1971.
Nakul Verma and Kristin Branson. Sample Complexity of Learning Mahalanobis Distance Metrics. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Julius von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmen- tations provably isolates content from style. In Mare' Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Informa- tion Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 16451- 16467, 2021. URL https::/pprcccedingssccco neurips.................. cc html
Dong Wang and Xiaoyang Tan. Robust Distance Metric Learning via Bayesian Inference. IEEE Transactions on Image Processing, 27(3):1542-1553 March 2018. ISSN 1941-0042, doi: 10.
1109/TP.2017.2722666
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity the hypersphere. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 9929-99399 PMLR, 2020. URL htt.hhttt:///occcceeiiii vvaaas/vllll /ttress/vl11/aaag2200 wttp////ww...hhcoc/m// html
m1
Xiaolong Wang and Abhinav Gupta. Unsupervised learning of visual representations using videos. In 2015 IEEE International Conference on Computer Vision, ICCV 2015. Santiago, Chile, De- cember 7-13, 2015, pp. 2794-2802. IEEE Computer Society, 2015. doi: 10. 10.1109/CCV222015.332 URL https: /doi .org 110. 1110//1CV..... 2015. 320
Hugh E. Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the
American Mathematical Society, 133:167-178 1968.
Colin Wei, Jason D. Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox. and Roman Garnet (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp-
14

---

Published as a conference paper at ICLR 2024
9709 9721, 2019. URL
html
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. In Marina Meila and Tong Zhang (eds.). Proceedings of the 38th Inter- national Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, vol- ume 139 of Proceedings of Machine Learning Research, pp. 11112-11123 PMLR, 2021. URL http://proceediinn
mlr. wtwps//wss wtt.3//wwen2c..... html
Zhirong Wu, Yuanjun Xiong, Stella X. Yu, and Dahua Lin. Unsupervised feature learning via non-parametric instance discrimination. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City. UT, USA. June 18-22, 2018, pp. 3733- 3742. Computer Vision Foundation / IEEE Computer Society, 2018. doi: 10.1109/CVPR.2018 00393. URL httt:::ttt//sssesccccss thecvf wtt.//ooo//ottcec _ccp 201 8/htm/ /We.
Baa11__aperrhta.. html
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnise a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint
077447777077770000 2017.
Lecun Yann. The mnist database of handwritten digits. R. 1998.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL / htt.://eee.eeeeoooo.o.eeeaaaaga/
Roland S. Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel. Contrastive learning inverts the data generating process. CoRR, abs/2102.008851 2021. URL
httts::/arxiv.. otg./viorrrreeoo abs 2102. 08850
James Y. Zou, Kamalika Chaudhuri, and Adam Tauman Kalai. Crowdsourcing feature discovery via
adaptively chosen comparisons. In Elizabeth Gerber and Panos Ipeirotis (eds.), Proceedings of the
Third AAAI Conference on Human Computation and Crowdsourcing, HCOMP 2015, November
8-11, 2015, San Diego, Califormia, USA, pp. 198. AAAI Press, 2015. URL http: /wwww//www
aaai. ortpocs///c/////ooooooooooooccoo index. /AAAAH/HHHHAAOPOC///////////////
15

---

Published as a conference paper at ICLR 2024
A EXAMPLE
Example and notation We are given 4 data points: images of a cat, a rat, a plane, and a train, which we denote as = [c, p, We consider the realizable case, i.e. there exists a ground truth metric p these points (e.g. general or Ep) with error rate e* O. For this example, we will assume that we embed these points into R, ie. = Hence the hypothesis class H. is just a class of all Euclidean metries on R.
For these data points, there are 12 possible input samples, corresponding to 4 choices an anchor and 3 choices of the two other query points. For this example, let 'D be the distribution of samples (z, x=) such that each input (æ, y, 2) is sampled uniformly, and the label is decided according closer x according
which of y and the ground truth to be that the cat is closer to the rat rather than to the plane, which we write as (c, .p)) Hence, this version of the problem is just a binary classification problem.
p. For example, if the input is (c, (e,r,)), we expect
Error rate If, for example, the ground -ruth embedding p was r 0, + 1.P 3.t 10, then, assuming the distribution on the inputs is uniform, we achieve the eπrоr rate 6. since only are not satisfied.
2 of 12 queries (p, et. rr and (p, ct
Sampling mechanism and learning scheme Since we have binary classification problem, with- out training set, we can only predict randomly, which gives the error rate 2- Now, suppose that we have a single training example (c, r+, r+,p"))) sampled from D. The algorithm that achieves the best worst-case guarantee is empirical risk minimizer (ERM), which seeks to find the embedding satisfying the maximum number of constraints. In this case, the constraint is satisfiable e.g. by p/=
embedding 0,r + 1,p 3, + 10, since |c rl =
Example of Shattering As example, the set S = {(e,r, p). (c, p, t), (c,r,t) is not shat- there exists no embedding such plc, l), and ple,r) > p(c,t). On the other hand, the set S' = [(c, (r, }}} is shattered: a labeling of S' determines for each of c, which point is closer between p and For any labeling of S", we can embed p. t arbitrarily and embed each of r closer to either p or t according to the labeling, thus satisfying the constraints imposed by the labeling.
tered since for the labeling {(c, rt (c,pt, (c, (c,,tt,7)) (),,P),((c,p)
that p(c,r)
B MISSING PROOFS FROM SECTION 3
Proof of Lemma 3.4
1. If H E C, and j E C. for and s and which differ in index j. we know that sign (z) * sign (T), and hence ž # T. Hence, C. and C., are disjoint.
2. First note that all C2 are open since polynomials are continuous functions, and preimages of open sets (-x0,0) 0) and (0, +oc) are open. Moreover, U,C, (P,,..... Pm)) and all C. are disjoint, and hence {Cx)s is a partition of UPI....., Pm)). By definition of connected set, it's impossible to partition connected component of (P...... Pm) into multiple open sets, and hence each C² must be a union some connected components of U U(P.....,
3. Follows from our choice of polynomials: P(n,,,o)) (Z) > Of is closer #(v) than to F(w), and P P(u,,,a) (Ø) 0 otherwise.
B. MISSING LOWER BOUND OF SECTION
Recall that our goal is to leamn a distance function V V + RR which can be produced by some allocation of points in the d-dimensional Euclidean space. In other words, the set of labeled queries
{(x,, yes 2x) is realizable if there exists a mapping f: V + Rd such that (x;) - f <
(I)))) (==)]]2-
16

---

Published as a conference paper at ICLR 2024
Theorem B.1. For dataset of size n, the VC-dimension of contrastive learning for ly ei-distances for any y E (0, +00) in dimension d is S2(min(1², (dd) nd))
Proof. We first assume that d < n, since otherwise the bound follows from Theorem 2.7 Let V be the set of points of size n. We will present set of queries S of size (((d)) that can be shattered. Recall that it means that for any T S S there exists a mapping f: V + R such that:
triplets from T are satisfied, i.e. each triplet (z.y, 2) E is labeled (z, (r,y*,²=), ,-), meaning p(a, p =);
triplets from S T are not satisfied, i.e. each triplet (x, v) S is labeled (a, 2r, meaning p(z; y) > 2).
First, note that for d any set of [n/a] disjoint queries gives Q(n) lower bound. For the rest of the proof, we assume that d >>> 1.
We partition V arbitrarily into disjoint sets A and B of sizes d and d respectively. Intuitively, the points from A always act like anchors, and points from B never act like anchors.
We first describe how to map B {ui,...,, va} (their mapping won't depend on the labels of the queries). For each i E [d], we map f(v,) e, where e, is the i'th standard basis vector.
Next, describe the queries. As defined above, A (311----;3pp Fn-d) is set of anchors, and for each anchor I,, the queries are of form (z,, U1, 22), (I;, U1 U3), .... (æ,, 01. va). Hence, there exist (d 1)(n - d) queries, as required by the theorem, and it remains to show that this set of queries can be shattered. Clearly, since the arrangement of points Ui...., is fixed, allocation of anchor 2, doesn't affect queries with another anchor Ty,, and hence suffices to map every anchor independently from each other.
Let's fix the anchor xi. Let the first coordinate of (xxx be 1/2. For j E [2 d]. if (I., vi, 15) is labeled (I,, of 1,), then we select the the j-th coordinate of fx;) to be 0, and otherwise we select to be 1. Note that then the query is satisfied: the summations for [x]x) - ei [lg and [.(())) - es 1B differ only in the first and the j-th coordinates. When the j-th coordinate is 0, we have
Ilf ea [x;);; e = (1/2)* ((1/2)² + 1²) < O, and hence (I,, uf 47 is satisfied. On the other hand, when the j-th coordinate is 1, we have
(x:;) en (fss)) e ((1/2) + 1P) (1/2)² > 0,
and hence (z,; 15t 0n is satisfied. Hence, we can construct fx;) that satisfies all the queries with anchor x,, Therefore, we can shatter the set of all (d - 1)(n - d) queries, finishing the proof. C
C VARIATIONS
C.I CONTRASTIVE LEARNING WITH I NEGATIVES
In the previous sections, we considered the queries of the form (anchor, positive, negative).In con- trastive learning. it's common to have multiple negative examples. In this section, we show the following result which can be used to derive bounds for the contrastive learning with i negatives.
Theorem C.I. Let A be the class of allowed metric functions. Let Ndim be the VC dimension of the contrastive learning problem on A with negative. Then the Natarajan dimension for the contrastive learning problem on A with negatives is at most Ndim.
Assume additionally that for any set of points S and any distance function E A on for any point o there exists distance function p' E A on SU {o} such that pll p'lsxs = p and p(z, v) < p(x, o) for any Z, y E S Then, for the dataset on n. points such that n - k = I(n), the Natarajan dimension of contrastive learning on A with negatives is ((Ndim).
Intuitivelyy, this condition implies that for any set S of points can find "outlier" point which is sufficiently far from the existing set of points. This assumption is naturally satisfied for e,p and tree distances.
17

---

Published as a conference paper at ICLR 2024
Proof. For the upper bound, assume that for some query (x), 21...... .......:........................ Ik+t), for the Natara- jan shattering we select the 24 and zj for some and j. i.c. the possible labels are Tk+1) and (f. ..tiii.......... -.j-11 3+1 "kti......,,,,1)) Then, the first query implies :,,,",,,]) and the second query implies (I, 2,,) Hence, any Natarajan- shattered set with l negatives corresponds to a VC-shattered set of queries with 1 negatives of the same cardinality, Hence, the Natarajan dimension is upper-bounded by the VC dimension the 1-negative problem.
Tk+1)-
For the lower bound, we split the set of points V into two sets: "outlier" points O= (01 for...... Ok- and the remaining points S {u1...... -n-A++)- Let Q {( Us: 2,)}: h be the VC-shattered set for the 1-negative contrastive learning on n - k + 1 points. Then, the Natarajan Natarajan-shattered -hatterdd set of queries for the k-negative contrastive learning For each query, for the Natarajan shattering we select and 2; meaning that possible labels are (1a, U3 23 01 ,.... 0 1) and (Ii, 1/ : 0x
points are Q' {2,, Yt, 24, 01..... 0k-1) h-
Since the set of Q is shattered, for any choice of labeling of { Ya 21) there exists distance function p E A satisfying this labeling. suffices to guarantee that p(z,, yi) < p(z;; and p(are, 2,) < p(z;, for all and j, and by assumption, there exists distance function satisfying this condition.
Corollary C.2. The same upper bounds on sample complexities for all distance functions considered in the paper (i.e. in Theorem 3.2 Theorem 2.7 Theorem D.2 and Theorem D.4 hold for k-negative contrastive learning Sk(c, 8) and (c, up to the log k-factor. The same lower bounds that hold
for contrastive learning in e norm and tree metrics (i.e. Theorem 3.1 and Theorem D.2) also hold for k-negative contrastive learning.
C.2 LEARNING ON QUADRUPLETS
Recall that we are given a set of quadruplets {((x "ilet,y*))x (2 (= w yyt) ((x*)
})}, where each quadruplet
(2 w w)) imposes constraint p(x*t .y*) p(z ,
Theorem C.3. For the VC dimension of contrastive learning quadruplets. have the same bounds as for the learning on triplets. Namely, for a dataset of size n, the following holds.
The VC dimension for arbitrary metric is O(n²).
The VC dimension for fn-distances in dimension d is M(nd) for all E (c).
The VC dimension for di-dittacces in dimension d is O(nd) for even p and O(nd log for odd p.
The VC dimension for the tree metric is ((n) n O(n log
Proof. First, we note that any lower bound in the triplet case is also lower bound for the quadruplet case, since triplet query (z, 2) is equivalent to the quadruplet query ((x,, v). (x).
For the upper bounds, for Ep and tree metric, we use the same approach: each constraint ((I, y). (2,w), w)) corresponds to polynomial (potentially after fixing the order of points or the tree structure). Since the number of variables and polynomials doesn't change, we get the same upper bounds. Finally, for arbitrary metric, similarly to Theorem 2.7] for each set of queries, we can con- struct a graph with vertices from x V: for each query ((z, y), (z, w)), we create an undirected edge, and labeling the query is equivalent to orienting the edge. If there is cycle, it's possible to get a contradiction, and hence we can't 't have more than O(VV x VI) = O(n²) queries.
D CONTRASTIVE LEARNING IN OTHER METRICS
In this section, we discuss related results. First, we show a bound for arbitrary distance functions: Theorem D.1 (Arbitrary distance). For arbitrary distance function p:: V V - IR and dataset of size n, the sample complexity of contrastive learning is Sa(e, 8) = e polylog (1. in the
18

---

Published as a conference paper at ICLR 2024
realizable case and (3(,,)) θ 2 polylog ()) in the agnostic case. Furthermore, the lower bounds hold even if p is assumed to be metric.
Proof. We prove this by showing a (n²²) bound on the VC dimension of contrastive learning with arbitrary distance functions.
Upper bound. Consider any set of samples {(z, yt. ==)))= of size k 2 n². There exists such that there are at least n samples which have x as their first element. We denote these sam- ples as (z, Mi =.,),... (2, Vé., Fi Consider a graph that has a vertex corresponding to each element in the dataset. Create an undirected edge in this graph between the n pairs of vertices
(3h, 24, ..... (y),,
2.,,).
Since the number of edges is equal to the number of vertices, there must exist a cycle C' in this graph. We can index the vertices along this cycle U1, ..,..., Up. Now consider the following labeling of the samples:
pl., v1) < p(z,, v2) < p(,,, v3) <... < 0z) < p(x, v1).
This labeling inconsistent with any distance function and hence not all different labelings of this sample are possible. Since the same argument applies for any sample of size at least n², an n² upper bound on the VC-dimension follows.
Lower Bound. Let V = {uI,..., J. We prove that the set of queries
Q Use[n] (12, U++1, 2142), (v); 1442, 2(43), .... (Vt, Un- Un]}
is shattered. Let @ be labeling of Q. For every i E [n]. we define a graph H; (fU++1,.... F E.) where E, contains directed edge (Uy, 1y+1) for each query, (2), Uy. 0y+1)), orientated towards the negative example according to Q. The graph H, is acyelic, as it is an ori- entation of path. Therefore we can topologically sort H;, and obtain some topological order Pi+1 P
p on the vertices U Cn-
Consider metric where the distance between two data items v, By is defined as p(ut, U2) == n Pj for each i < j S We note that this is indeed metrie: triangle inequalities are satisfied since all distances are in the range [n, 2n]. Finally, we note this distance function satisfies all the queries. Indeed, for j, k such that < j and [k - jl = 1, if (v,, uf,"" ""> E Q then the directed edge (uz, uk) E Eg, therefore p(u,, vx) p(er, uy) since Pk Pj
(6) (0)
A metric (V. p) is called a free metric if there exists tree T with weighted edges and n leaves, such that for each E V there is unique leaf I(v) associated with it, and such that for each u, E V, p(u, v) is equal to the sum of weights along the unique path between I(u), l(v) in T.
Theorem D.2 (Tree distance). For the tree metric distance function pr: V XV + R, corresponding to distances between the nodes of a tree with leaves from V, the sample complexity of contrastive
learning in the realizable case is Sa(e, =
n log polylog (2) and Ω (3 polylog (t) J)),
and in the agnostic case is (g 8) = 1olo polylog ( ))) and Ω (3 polylog (2. 4)).
Proof. We prove this by showing that the VC-dimension of contrastive learning for the tree metric On n). First, we may assume that the number of vertices the tree most 2n. Indeed, any induced path in the tree can be contracted to a single edge whose weight is the sum of weights along the path. After this procedure, the tree metric remains the same and the resulting tree has no vertices of degree 2. It follows by a counting argument that the number of vertices in this tree is at most 2n. The rest of the proof is similar to the odd case of the Theorem 3.2 we enumerate over all possible tree structures with at most 2n vertices and allocation of the data items onto the tree vertices. By Cayley's 's formula Caaleyy 1878), there exists 2(2m) 2n-2 such different tree structures and vertex allocations. For fixed tree, the distance between every pair of vertices can be expressed as a linear combination of the edge weights. Hence, every constraint becomes a linear inequality on the edge weights.
19

---

Published as a conference paper at ICLR 2024
The rest of the proof is analogous that of Theorem 3.2 Fix tree T. Let (r u) be the set of edges in the path between u, U in T. We have lo I 2n variables = (#1..... 2b). where zı
represents the edge weight of eq. For queries we define polynomials Pt ( Pm (T), one for each query, such that for query (u4, U2 wi) we define the polynomial
Pi
Z4.
(
E. (w).ww)
Le. (Us, DJ" w,,)) is satisfied if and only P.(e) < O. For m 3n log queries, by Theorem 3.3 the number of possible sign combinations is at most (4em/k)* < 22 Summing over all possible tree structures, the number of sign combinations is less than 2nh and hence the set of m queries can't be shattered.
2dd
The Cosine Similarity function cos Rd x IR - R a function which returns for each pair of points 2, y the cosine of their angle, i.e. cos ((x, v).
Theorem D.3 (Cosine Similarity). For the cosine similarity function, the sample complexity of con-
trastive learning (s(c, = miin("" polylog (2: b)) in the realizable case and is S (c,
min(n? nd) polylog ( t)) in the agnostic case.
Proof. As usual, we assume that d <, n, since otherwise the result follows from Theorem 2.7 We prove this by showing that the VC-dimension of contrastive learning for cosine similarity in Re is
((nd). Recall that cos (xx y) T ( TTalla I and hence w.l.o.g.
(a.z)
assume that
all points are unit vectors. For unit vectors x, we have || - =1ا || + | 2(zz y)
2 2-2 2 cos Z(x, y). and hence cos _(x, y²) > L(x, = is equivalent to || - y ||2 < || ||2-
To summarize, contrastive learning for cosine similarity is equivalent to contrastive learning for & distance of points on the sphere.
The upper bound ((nd) for VC dimension follows directly from the fact that for the cosine similarity we only consider unit vectors, and hence the hypothesis space is less than that for the di-distance (which allows arbitrarilynnomed vectors).
For the lower bound, we repeat the proof of Theorem B.1 with minor alterations that ensure that all points are embeddable in the unit sphere.
Similar to Theorem B.1 we partition into two sets A {ai..... ( - as set of anchors, and B = [w1,..., va). We define the query set Q as follows: for each anchor 24, the set Q contains the queries (r,, 01, U2), (I, U1, 03), .... (zt, 01, va).
We set fw:)) = ei. i.e. we embed to the i'th standard vector ei.
For each my we define vector g(xz)) Rd in the following manner. Let the first coordinate of g(:;) be 1/2. For j E [2 : d]. if (zy, U1, 0z) is labeled (xy, of 2y ). then we select the the j-th coordinate of g(z;) to be 0, and otherwise we select
be We map 2; to fzx = s(*x)/1lg(z))))
Next, we prove that all queries are satisfied: the summations for [x;) - -eill3 and Ilf(;;)) e differ only in the first and the j-th coordinates. When the j-th coordinate is O, we have
2
2 +12
- e,
211
[9((1))12 < 0,
Hence (I,, "r u,) is satisfied. On the other hand, when the j-th coordinate is 1, we have
((1 11-211((0a011> (11-211224)1
1
2 +12) - = =2 )==
[g(x;)]l2 0,
where the inequality holds since [1g(x))]12 > (due to the first coordinate and the j-th coordinate). Hence (x,, of vT) is satisfied. Therefore, we can construct fxx) that satisfies all the queries with anchor F,. Therefore, we can shatter the set of all (d - 1)(n d) queries.
20

---

Published as a conference paper at ICLR 2024
Theorem D.4 (Class distance). Consider domain V partitioned into any number of disjoint classes
Ci..... Cm. where m 2 2. For the class indicator function pc: V x V - {0,1), defined as
PC y) = 0 iff there exists such that x, y Cs the sample complexity of contrastive learning is
Sa(e. = θ (a polylog (2) 2)) in the realizable case and θ polylog ( ()) in the agnostic case
Proof. We prove this by showing an (n) bound on the VC dimension of contrastive learning with class distances.
Upper bound. Consider any set of samples {(z,, Mi, 2))]=..... of size h 2 Fix an arbitrary labeling of this set. Note that in any triple, one pair (e.g. (di;, Vi)) from the same class and the other (e.g- (ara, =:)) is from different classes. Create a graph on vertices, where each vertex corresponds to an element in the dataset. For each labeled sample create an edge in this graph corresponding to the pair of vertices, which are from the same class. Since this graph has n edges, there must be cycle C' in this graph and all the vertices on this cycle must be in the same class according to the labeling. Consider any edge (I, y) the cycle and change the labeling of the triple corresponding to this edge. This forces x and to be from different classes and leads to contradiction, since æ and y must be in the same class due the existence of path between them.
Lower bound. Partition V into disjoint sets of size 3, and associate a query with each set, i.e.
{(V1, U2, 03); (Ug, UG, us)..... (Un-2) 2; Un-1, vn)].
For each labeled query (w,, w 2(42) E Q. place v and 0/41 in C1. and 0142 in C2. For each labeled query (wi, 2 11+1) Q place vy and U142 in C₁ and 0:41 in C2-
By Theorem C.3 our bounds extend to the quadruple contrastive learning setting.
Corollary D.S. The same bounds as in Theorem 3.1] Theorem 3.2 Theorem 2.7 Theorem D.3 hold for quadruplet contrastive learning.
Theorem D.2
E LEARNING LABELS UNDER A WELL--SEPARATER ASSUMPTION
In this section, we show that under well-separated setting (i.e. when the two distances of each triplet are guaranteed to be separated by some multiplicative factor), the sample complexity can be improved to be almost independent of d (disregarding polylog factors).
More formally, given parameter a > 0, each labeled query (z, (x,y*²²)) implies the constraint (1 + p)p(s, v) < p(x; 2).
Lemma F.1. Let d be integers and < < 1. Let (n, d) be the VC dimension of the contrastive learning problem and T(n, d, or) be the VC dimension of the (1 + a)) -ss-paraeee contrastive learning problem.
T(n, d, = 0 nd, n log n/a2)), T(n,d, = 2( (mnn(n?, .nd, n/a)).
We start with the lower bound in Theorem F.1 Recall the embedding f given in the proof of Theorem B. From this embedding it follows that T(n, d, c/d) = ((dd) for a sufficiently small constant c 0. Indeed, for all & n d and j < d, if (z,, ut 0z is satisfied then
(f(x,) f(2,) [1,(),,) f(x)) > 1 llf(z;) f (v1))l//dd
where the last inequality follows as all the coordinates are bounded by 1. Rearranging we obtain (1+ c/4))l((2)) flr))l2.
ll((z) f(r,)lla 2 /i+1/d [lf((z)) f(er)ll2 (1
Similarly we have
llf(z)) - f(r))ll (1+c/d)]f(aa) - f(u,)ll2- when (I&, u5t vr is satisfied. This shows that T(n, d, c/d) ((nd).
For this distance function also allow "equality" label (zr, v+ 2t,, which implies (r) ())
21

---

Published as a conference paper at ICLR 2024
Next, when < c/d we have that T(n, d, 2 T(n, d, c/d) 1((dd). When c/d we have that [(n, d, a) 2 T(n, d1, c/d1) ) = Q(n/a), where d1 == a
Next, prove the upper bound. We first show dimension reduction argument, which intuitively shows that in separate contrastive learning can always be reduced to (log dimensions. Lemma E.2. Let d1 = [1000 log n/a²1. We have that
T(n, d, a) S T',, d1, a/2).
The lemma is simple application of the Johnson-LLindenstraus lemma (Johnson 1984. given below.
Fact E.3 (The Johnson-Lindenstran Lindenstrauss lemma), For any 1>> 3 > 0, set X of n points Rd and an integer d1 2 15 log n/3?, there is an embedding f X + Rd such that for all y X have
(1 (1- (|13 ulla l1f(x)) f()))l2 (1 3) |2 vll2.
We can now prove Lemma
Proof of Lemma E.2 Suppose that T(m, d, a) 2 m for some integer m. By definition, there exists
a set of queries Q {[u,, V; w;) i S m] such that for any labeling of the queries Q. there
an embedding f : V + R2 such that if the query (u, Vs wx) is labeled as (u,, 0 w. then Ilf f(w;)( 2| 2 (1 a)llf(u)
lemma in order to embed the points [f(e) : v E V} in lower dimensional space without distorting the a/7 we have embedding y V + Rd such that if the query (ug, 84, w.) is labeled as (u,, 2 w; then
f(u))l22. Next, we use the
distances too much. By Fact E.3 with
[lg(u:) - ((w))ll 2 2 (1- ())) - (ww))ll 2 a1 ())) - f(x))l2
(1 + a) 3)
(1)
1 1 [1((u,) - g(v:))l2 2 (1+ a/2)loo())) - -0(;))l
where the last inequality holds for all 0 < a 1. This shows that d1, m and completes the proof.
Given this lemma, our claim follows since
T(n, d, a) < T(n,d1, a/2) S ((n,dd) = O(nd1) = O(n noa?).
Where the first inequality holds due to Lemma E.2 the second since for any integers n', d' and value a' >> 0 we have that T(n', d', a²))"))))) < T(n', d') (i.e. the exact version is at least as hard to learn as the separate version, since the hypothesis space of the latter is contained in the former), and the third equality holds due to Theorem 3.2 This concludes the proof of Lemma E.
Using Lemma 2.6 we obtain our sample complexity bounds.
Theorem E.4. For any > O, the sample complexity of a--sppaaate contrastive learning (n [n n a=.e
is Ss(e, 8) O case, and 5)(c, O agnostic case.
polylog( !) and Sz(e,8) = Ω 1 polylog (:: for the realizable
n 22.22 polylog (2. 1)) and Sz(e, 8) P (,a> polylog (2) for the
We note that the case of 2 is relaxed version of e.g. a 0.99, therefore we immediately obtain the following near-tight bounds:
Corollary E.5. For any a 2 1, the sample complexity of (1 + a) sesprratee contrastive learning is Sa(e, 8) = O (" [llg polylog( 1) and Sa(e. 8) Ω ( polylog ( 1)) for the realizable case, and Sa(e, = logg polylog (t) and Sa(e, 6) = (3 polylog ( 1)) for the agnostic case.
As an interesting open problem, we leave open whether the upper bound of O(n logn)) can be improved for large enough values of
22

---

Published as a conference paper at ICLR 2024
Empirical and predicted (scaled) generalization error
Empirical and predicted (scaledi generalization error
d=33
d-128
d=256
50
d-100
d-1000
d-1024
40
Predicted
1 Predicted
30
Eror
20
19
10
10a
10*
10*
The number of samples (loc scale)
The mumber
(a) Fashion-MNIST dataset
(h) CIFAR-10 dataset
Figure 1: Training with triplet loss. For various embedding dimensions we show the empirical and the scaled predicted generalization errors. The scaling factor is chosen as /1/320 (Mohri ee al.) 22018). In this scenario, consider the well-separated case, and hence the predicted error the same for all d. Data points are averaged over 10 runs, error bars show 10% and 90% quantiles.
F EXPERIMENTS
In this section, we empirically verify our theoretical findings real-world image datasets. We compute image embeddings using the ResNet-18 network, with the last layer being replaced with a linear layer with the output dimension matching that of the target embedding dimension. The neural network is trained from scratch for 100 epochs using a set of m E {10?, 10 10*} training samples, and is evaluated a different test set of 10* triplets from the same distribution. We show that our theory provides a good estimation of the gap between the training and test error.
We consider the standard experimental setup used in the literature where the positive example is sampled from the same class as the anchor, and negative examples are sampled from a different class, e-g. [Saunshi al. (2019); Awasthi et al. (2022). Note that it means that the ground-truth distances are well-separated, and hence we are in the setting of Theorem 4.2 (see Section F for experiments in the non-well-separated case). Since the neural network doesn' It perfectly fit the data, the setting is agnostic, and hence for data points and eтror parameter our theory predicts that m R a labeled samples are required, where we estimate
320 based on Mohri et al. (2018)
Page 48). Hence, given m samples, our theory predicts that e ze v 320m We compare this value to the empirical generalization error ē, defined as the difference between training and test errors.
We consider two settings: when each sample has a single negative example and when it has multiple negative examples.
Single negative example: When every sample has only one negative, we train the model from seratch on CIFAR-10 (Krizhevsky 2009) and Fashion-MNIST (Xiao et al. 2017) datasets using the marginal triplet loss (Schroff et al. 2015b)
AMr(z,v+,23) = max(0, || - -11 - || ||
1 +1,, 1),
where a and yt are points from the same class and =- is point from a different class.
We present our results Figure T For a small number of samples, there is a discrepancy between the predicted and the empirical generalization errors, which is due to the fact that the random guess trivially achieves 50% accuracy, while our results hold only for the non-trivial error rates (see Def- inition I. First, the results for different embedding dimensions match closely, which shows that the error doesn't 't depend on the dimension, as predicted by our theory. Note that the scaled predicted within a constant factor, which is hard to attribute to coincidence given
and the empirical results the choice of the scaling factor. Hence, these experiments support the theory by showing that provides good predictor of practical generalization error.
23

---

Published as a conference paper at ICLR 2024
70
Empirical and predicted (scaled) generalization error
120
Empirical predicted generalization
k= (Empirkall
I k=1 (Empiicall
60-
1
(hediced)
[Prodicted]
k=2 (Emprical)
k=2 [Empricall
50
(Prediczed)
k=2 [Predicted]
K-4 (Empriiall
(Empi fiall
40
(Preaczed)
K-4 |Predicted
k=0 (Empiricall
Enor
60
(Empii iall
30-
(Prediczed)
k= (Predicted
20
10
The number samples (loq scale)
The number of samples (og scalel
(a) MNIST dataset
(b) CIFAR-100 dataset
Figure 2: Training with the contrastive loss with & E (1,2,4,8) 8 negatives. We show the empirical and the scaled predicted generalization errors. The data points correspond to the average over 10 runs, and the error bars show 10% and 90% quantiles
Multiple negative examples: For the case of multiple negative samples, we train the model using the contrastive loss (Logeswaran & Lee 20185)
exp(x y²)
Lo(x,y+,2)
2 = - -log
exp(x* y+) + Σi= === exp(xx22
We train the model from scratch on the MNIST Yannn 1998) and CIFAR- (Kizzeeskyy 2009) datasets, and report 8/c for different numbers of negatives k 11 2, 4. 8). Recall that for h negatives we have e ( n O R log(k: + 1)). and for our experiments we use the upper bound. The results are shown in Figure 2 As before, the values are within constant factor for all values of k and numbers of samples m. Figure b) shows that the log(k: + 1) factor in the sample complexity is observable in practice (we it when computing the predicted error and the curves for different k match closely after this normalization). The lack of convergence in Figure ((b) is most likely at- tributable the fact that the sample size is too small. Similarly to other plots, we expect convergence for larger sample sizes, which were computationally prohibitive to include in this version.
Non-well- wepp-ssa-ae case Finally, we conduct experiments for the case when the positive example is not necessarily sampled from the same class as the anchor. While the experiments above corre- spond to one of the most conventional contrastive learning approaches, the experiments this sec- tion more closely match our theoretical settings. In particular, we don't use any data augmentation for the training, and we use the same set of points (but not the same set of triplets) for both training and testing. Since the VC-dimension depends on the number of points (Theorems and 3.2 to verify those results, we subsample n E {10?, 10 10*3 points.
In contrast with the previous experiments, where the positive example is sampled from the same class as the anchor, in this section, all elements of a triplet are sampled uniformly from the chosen points. We determine negative and positive examples based on the distance between ground-truth embeddings computed using a pretrained ResNet- 18 network.
We compare the empirical generalization error to the theoretically predicted error rate (compared to the best classifier). We perform experiments on the training set of CIFAR-10 10 and the validation set of ImageNet by training ResNet-18 from scratch on m E (2, 10, 10 10xs 10a 10a} randomly sampled triplets, and evaluating the model on the 10 triplets sampled from the same distribution In Figure 3 the predicted and the empirical errors show the same tendencies and the same relative behavior between different choices of n. As before, the empirical and the scaled predicted errors are within a factor of of each other.
We express our thanks to the FFCV library Leclere al. 2022) which allowed us to significantly speed up the execution
24

---

Published as a conference paper at ICLR 2024
Empirical and predicted (scaled) generalization errors
Empirical and predicted (scaled) generalization errors
100
T
(Empiricz!)
+
(Empirical)
(Predicted)
+ 1=10 (Predicted)
80
=0000 (Eriiikal
80
1000 (Empprkal)
r-1000 (Pradictad)
I E-1030 (Pradictad)
r=10000 (Empanca))
r-10000 (Empincal)
%
60
T 1-10000 (Precicted)
T r- 100000 (Fredicted)
40
10a
10a
10a
10a
10a
10*
10a
number samples (lag
The number samples scale)
(a) ImageNet dataset
(b) CIFAR-10 dataset
Figure 3: Training with the contrastive loss with negative with embedding dimension 512. For each n E (10", 10", 104), we subsample n points from dataset for m E {10", 10 10 100) input triplets. For various that the theoretical predicted error is bounded by 50% which a achieved by a random guess. Data points are averaged over 10 runs, error bars show 10% and 90% quantiles.
show the empirical and the scaled predicted generalization errors. Note
25


Reviews:
[{"review_id": "BHjEPoNzKi", "reviewer": "Reviewer_MJ3x", "summary": "This paper studies the sample complexity of contrastive learning, which learns the similarity (usually the distance in a metric space) between domain points, given tuples each labeling a most-similar input point to a given point (anchor).\n\nThis paper proves matching (or some almost matching) bounds on the sample complexity for contrastive learning of different metrics (arbitrary distance, cosine similarity, and tree metric), with generalization to learning with hard negatives (separated $\\ell_2$ distance), quadruplet learning, or learning with $k$ negatives.\n\nThe results are based on an output-based assumption: there is an embedding into a $d$-dimensional vector space. This enables reasoning on the VC/Natarajan dimension to study the PAC learning framework, both for the realizable and the agnostic cases, to get non-vacuous PAC-learning bounds with predictive powers.\n\nThe proof is on representing the decision boundary of contrastive learning under such metrics as a low-degree polynomial, and upper bounding its number of possible satisfiable sign changes (Lemma 3.5 proved in Section B), hence the largest shattered set of tuples, and VC/Natarajan dimension.\n\nThe theoretical result is also experimentally verified on popular image datasets (CIFAR-10/100 and MNIST/Fashion-MNIST), by learning the representations with a ResNet18 trained from scratch with different contrastive losses.", "questions": "While the experimental results (in Appendix F) verify the growth of error rates as predicted by the theory for ResNet18 on certain parameter ranges, there is not much explanations regarding, e.g., what representations (e.g., deep learning architectures) are expressive enough to achieve the sample bounds as predicted by the theory. That is, the representations (given by the theory) are somehow non-explicit/ineffective, is that the case?\n\n### Typos?\n\nStatement of Theorem 1.3 (Page 4):\nThe sample complexity of contrastive learning ~for contrastive learning~ under cosine similarity is...", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The proof is by _understanding the problem via transforming it_ to another equivalent representation: the decision boundary of contrastive learning under common metrics as a low-degree polynomial, and bounding its number of possible satisfiable sign changes. There is no loss until invoking the algebraic-geometric bounds on number of connected components by Warren, and the sample complexity bounds on Natarajan dimension by Ben David et al. \n\nAnd at a high level, the paper shows that when the learned representation is expressive enough (such as ResNet18), PAC-learning bounds (e.g., by VC/Natarajan dimension) can have predictive powers.\n\nThe theoretical result is also experimentally verified on popular image datasets (CIFAR-10/100 and MNIST/Fashion-MNIST), by learning the representations with a ResNet18 trained from scratch with different contrastive losses (Appendix F).", "weaknesses": "The proof arguments are somewhat non-constructive, due to using a counting argument/pigeonhole principle, and hence while the theory may explain certain observations (e.g., the experimental results in Appendix F), it is unlikely to give effective learning algorithms and the constants in the resulting bounds are unlikely to be sharpened. This may be nitpicking, but are weaknesses nonetheless.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O5IhNlQrm8", "reviewer": "Reviewer_m7mJ", "summary": "Given labeled sample $(x_1,y^+_1,z^-_1),\\ldots,(x_n,y^+_n,z^-_n)$, the goal of contrastive learning is to create a distance function $\\rho$ such that $\\rho(x,y) < \\rho(x,z)$. This study comes in theoretical flavour, providing lower and upper bound for sample complexity of contrastive learning via PAC-learning framework. The main ingredient of the proof of the bound is the Natarajan dimension (which is a generalization of the VC dimension) and the results from Ben David et al. (1995). \n\nReference:  \nS. Bendavid, N. Cesabianchi, D. Haussler, P.M. Long, Characterizations of Learnability for Classes of {0, ..., n)-Valued Functions, Journal of Computer and System Sciences, Volume 50, Issue 1, 1995, Pages 74-86.", "questions": "See Weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The study covers a wide range of distance functions, both in lower bounds and upper bounds.\n- Interesting use of an algebraic geometry result to prove the upper bound.\n- The theory is well-supported by the empirical results.\n- The authors discuss possible directions for future work.", "weaknesses": "Personally, I find it hard to follow the results by chapter. For example, Section 3 should be all about the bounds in $\\ell_p$ norm, and so Theorem 3.1 (Arbitrary distance) should come before this section. And I think it would be easier to follow if Section 3 is only for $k=1$ and Section 4 is only for $k>1$.\n\nI have some comments for Table 1:\n- I would put \"$(1+\\alpha)$-seperable $\\ell_2$\" in the same category as $\\ell_p$.\n- The \"Same\" labels for quadruplet learning and $k$ negatives have different meaning; while the former refer to all distance functions above, the latter only refers to the $\\ell_p$ distances. Could the authors modify the table so that this distinction becomes clearer?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1L6fpQQyhm", "reviewer": "Reviewer_Tspf", "summary": "The paper explores the efficacy of contrastive learning, a method for learning data representations based on labeled tuples that detail distance relationships within the tuples. The main focus is on understanding the sample complexity of this method, which refers to the minimum number of labeled tuples needed to achieve accurate generalization. \n\nThis work provides specific bounds for sample complexity across various settings, especially for arbitrary distance functions, $\\ell_p$-distances, and tree metrics. A central finding is that for learning $\\ell_p$-distances, a minimum of $\\Theta(\\min(nd,n^2))$ labeled tuples is sufficient and necessary for depicting $d$-dimensional representations of $n$-point datasets. These results are applicable regardless of the input samples' distribution and derive from bounds on the Vapnik-Chervonenkis/Natarajan dimension of related problems. \n\nThis paper also demonstrates that theoretical boundaries derived from the VC/Natarajan dimension correlate strongly with experimental outcomes.", "questions": "1. What do you think is the primary season/insight that the upper bounds for $\\ell_p$-distances are different between odd and even $p$?\n2. Do you think it is possible to characterize the sample complexity bound when the cardinality of $V$ is infinite? \n3. Minor:\n- In the paragraph \"Outline of the techniques\" on Page 4, why \"P is some polynomial of degree $2d$\"?\n- In the paragraph above \"Outline of the techniques\" on Page 4, $(x_1^-, x_2^-)$ ->  $(x_3^-, x_4^-)$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. This paper primarily studies the sample complexity of contrastive learning, and provides tight bounds in some settings, including arbitrary distance functions and $\\ell_p$-distances for even $p$ and almost tight bounds for odd $p$. For constant $d$, this work also provides a matching upper and lower bound. \n2. This paper studies both realizable and agnostic settings, as is standardly considered in PAC learning. The sample complexity bounds in terms of $\\epsilon$ coincide with the standard results in PAC learning in both realizable and agnostic settings. \n3. The proposed proof idea extends to various settings, including the cases where $k >1$ (multiple negative examples in one tuple) and quadruple samples.", "weaknesses": "1. It would be good to provide a thorough comparison with the known sample complexity bounds that appeared in the existing literature. \n2. While I understand the page limit of the main body, there seems to be relatively less than enough content on the main results of this work in the main body. Perhaps consider moving more technical parts from the appendix into the main body. \n3. The structure of the paper could be reorganized a bit: e.g., the paragraph \"Reducing dependence on $n$\" could be part of the discussions after presenting the full main results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0JpaYb8dFi", "reviewer": "Reviewer_YPGd", "summary": "Suppose $V$ is a set of $n$ data points, each embedded into a $mathbb{R}^d$. Suppose we observe $m$ triplets $(x,y,z) \\in V^3$ and their labels in $\\{ -1, 1\\}$ where the label is $1$ if $x,y$ are closer than $x,z$ in the embedding space in $\\ell_p$ distance and $-1$ otherwise. The paper gives optimal order for sample complexity $m$ required to get to a misclassification error of $\\epsilon$. \n\nThe high level technique is to derive VC dimension (and Natarajan dimension for larger tuples, but we ignore results in the larger tuple case for now). The authors derive nearly tight order for VC dimension of such triplet classifiers. For upper bounding the VC dimension, they formulate the classification function as the sign of a polynomial in $nd$ dimensions. The key ingredient here is a fact from Warren (1968) that there are at most $(4epm/nd)^{nd}$ connected components in $\\mathbb{R}^{nd}$ where in each connected component, the signs of the $m$ polynomials are fixed. For proving the lower bound on VC dimension, the authors give a clever construction of a set of triplets which can be shattered.\n\nAuthors give their results to realizable and agnostic cases. They extend their results to several distance functions and tuples of size more than 3. They also study the well-separated case where the labeled triplets $(x,y^+,z^-)$ satisfy $\\rho(x,z) \\geq (1+\\alpha) \\rho(x,y)$ etc. for some $\\alpha > 0$.", "questions": "Typos/Minor comments:\n* page 4: Outline of techniques: P is a polynomial of degree $2$, not $2d$.\n* Reducing dependence on $n$: It may be good to state bounds with the assumptions mentioned ($k$ latent classes etc.)\n* Theorem 3.3 proof, first line: Should it be $d < n$ here?\n* In Definition 2.1, the symbol $S_3$ seems to be used before definition.\n* Please search for \"Kulis Kulis\" and \"Warren Warren\" in the paper and remove such duplicates.\n* page 8, second line: Should $<$ be replaced by $\\leq$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The derivations are interesting, short and non-trivial.\n* The results are relevant because contrastive learning is practical.", "weaknesses": "Nothing significant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)