Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors
Authors: Dmitrii Avdiukhin
Vaggos Chatziafratis
Orr Fischer
Grigory Yaroslavtsev
Venue: NeurIPS 2024 poster (2024)
Keywords: Representation Learning
Ordinal Embedding
Metric Space
Nearest Neighbors
k-NN
Contrastive Learning
Embedding Dimension
Primary area: other

Abstract: We study the embedding dimension of distance comparison data in two settings: contrastive learning and $k$-nearest neighbors ($k$-NN). In both cases, the goal is to find the smallest dimension $d$ of an $\ell_p$-space in which a given dataset can be represented. We show that the arboricity of the associated graphs plays a key role in designing embeddings. Using this approach, for the most frequently used $\ell_2$-distance, we get matching upper and lower bounds in both settings.
    
In contrastive learning, we are given $m$ labeled samples of the form $(x_i, y_i^+, z_i^-)$ representing the fact that the positive example $y_i$ is closer to the anchor $x_i$ than the negative example $z_i$. We show that for representing such dataset in:

- $\ell_2$: $d = \Theta(\sqrt{m})$ is necessary and sufficient.
- $\ell_p$ for $p \ge 1$: $d = O(m)$ is sufficient and $d = \tilde \Omega(\sqrt{m})$ is necessary.
- $\ell_\infty$: $d = O(m^{2/3})$ is sufficient and $d = \tilde \Omega(\sqrt{m})$ is necessary.

We also give results for the more general scenario when $t$ negatives are allowed.

In $k$-NN, for each of the $n$ data points we are given an ordered set of the closest $k$ points. We show that for preserving the ordering of the $k$-NN for every point in:
- $\ell_2$: $d = \Theta(k)$ is necessary and sufficient.
- $\ell_p$ for $p \ge 1$: $d = \tilde O(k^2)$ is sufficient and $d=\tilde \Omega(k)$ is necessary.
- $\ell_\infty$ : $d = \tilde \Omega(k)$ is necessary.

Furthermore, if the goal is to not just preserve the ordering of the $k$-NN but also keep them as the nearest neighbors then $d = \tilde O (\mathrm{poly}(k))$ suffices in $\ell_p$ for $p \ge 1$.

Embedding Dimension of Contrastive Learning and k--Nearest Neighbors
Dmitrii Avdiukhin
Vaggos Chatziafratis
Computer Science Department Northwestern University Evanston, IL 60657, USA
Computer Science and Engineering Department University of California Santa Cruz Santa Cruz, CA 95064, USA vaggosQucsc.edd
Orr Fischer
Grigory Yaroslavtsev
Computer Science Department Bar-Ilan University
Computer Science Department
George Mason University Fairfax, VA 22030, USA
Ramat- Gan, Israel
fischeo@biu. ac.
grigory0gmu.co edu
Abstract
We study the embedding dimension of distance comparison data in two settings: contrastive learning and k-nearest neighbors (A-NN). Our goal find the small- est dimension d of an ly-space in which a given dataset can be represented. We show that the arboricity of the associated graphs plays key role in designing embeddings. For the most popular f2-space, we get tight bounds in both settings.
In contrastive learning, the fact that the positive example yi is closer to the anchor 2; than the negative example 2, (we also give results for É negatives). For representing such dataset in: necessary and sufficient, consistent with our experiments. lp for 2 1: d = ((m) is sufficient and = (2(mm) is necessary.
are given labeled samples (x,, y 2g representing
Eg: d O ((mm)
Exo: d = O (m223) is sufficient and d = f1(mm) is necessary.
In k-NN, for each of the n data points we are given an ordered set of the closest k points. We show that for preserving the ordering of the k-NN for every point in:
f2: d = (A)) is necessary and sufficient.
tp for 2 1: d = Ō(k²) is sufficient and d = Šū(k) is necessary.
fxx : d = 52(k)) is necessary.
Furthermore, if the goal is not just preserve the ordering of the k-NN but also keep them the nearest neighbors, then d ((poly(k)) suffices in Ep for p 2 1.
Introduction
Embedding vectors play important role in machine learning, with the embedding dimension being a key parameter of interest when choosing a deep learning architecture. this paper, we ask the following question: given a dataset labeled with distance relationships between its points, what is the smallest embedding dimension required to represent it? We answer this question for two types of distance comparison data: contrastive labels and A-NN.
Contrastive Learning Contrastive learning GH10 has recently become a popular technique
for learning representations, see e.g. SE05 MCCDLE DSRB14 SKP15a WG15 WXYL18
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

LL18
HFL "FL*19
CLL21 Recent interest in the- 19 HFW 20 TK120 CKNH20 CH21 GYC21
oretical foundations of contrastive learning has resulted in extensive research focusing on gen-
eralization [AA design of specific loss functions [HWGM21] transfer learning [SPA 19
CRL++00 multi-view redundancy [TK221] inductive biases [SAG 22 HM23], the role of neg-
ative samples [AGKM22] ADK22 mutual information [vdLLv18 HFL 19 [HB19] TDR+200
and other topics [W120] TWSM21
ZS 21
MMW 21 WL21]
In on of the most common forms of contrastive learning, we are given m labeled data points {(2,, yi" 2 ) (or more generally, {(.,. 21,1: 21,2..... 2,,) Ii=1) over dataset of size n. Each point represents the fact that the distance between the anchor 2i and the positive example yi is smaller than the distance between I; and the negative example z; (or, more generally, L negative examples 2,,1,...,, -i,t). We study the problem of emhedding such data into Ep-spaces, i.e., con- structing embedding F: V Rd such that ((,(),,) F(y))lpp [lF((z)) F(zi)ll, for all í (more generally. [IF(x;) - F(n)lla < [1((x) Fl for all i,j). In particular, we focus on
the embedding dimension:
the Given a collection of m triplet comparisons of the form "x; is closer to yi than to zi", what is the smallest dimension d of an Ep-space in which the relative order of distances can be preserved?
k-NNs We also study a similar question for k-Nearest Neighbor (k-NN) data, which has major applications in machine learning since the seminal work of [CH67]. In this setting, are given set of n items and the information about the k-NN of each item {a Ti (Iz). T (z:),..., (x;) are the K-NN of x; ordered by their distance from 24.- Since k-NN classifiers extremely popular in deep learning pipelines, understanding the embedding dimension required for preserving k-NN is a question of fundamental importance. In particular:
(x:))))> where
Given n items and their k-NN, what is the smallest dimension d of an Ep-space in which the ordering of the k-NN can be preserved? What if the k-NN have to remain k-NN in the ep-space?
1.1 Our Results and Techniques
Let V be the set of n points. Our goal is to construct an embedding V + Rd. For an integer n, we let [n]] = 2 ..... nt. For vector v E Ed let rli] be the 7th coordinate of v. For vectors U1 U2, we denote their concatenation as (vi, 02). In graph, denote by N (x) the neighbors vertex x. For standard definitions (e.g. metric and norm) and basic facts see Appendix
Contrastive Learning For set of samples Q = {(01, v (Im, ynt }, we call an embedding F consistent with Q if FF(;)) (0)=((x))) (w)))p> < [[)()))) F(=))lp ((=)))) for all i. W.l.o.g., we can assumeT that m < n We call a set of samples non-contradictory if one can't 't derive a contradiction from the inequalities between the distances. In particular, this implies the existence of a metric p which is consistent with Q (Fact(25)
We prove the following theorems in Section 2 Appendix D.2 and Appendix D respectively.
Theorem 1 (Embedding in E2). Let Q be a set of m non-contrudictory triplet samples on a set V.
There is an embedding of V into E2-space Om (2) which is consistent with Q.
Theorem (Embedding in &gc). Let Q be a set of m non-contradictory triplet samples on a set V.
There is an embedding of V into -space (mm3) which is consistent with Q.
Theorem (Embedding in ep). Let Q be a set of m non-contrudictory triplet samples on a set V. For any integer p 2 1, there is an embedding V into Ey-space (mm)) which is consistent with Q.
The lower bounds are shown in Appendix Flannddxxaanddd Eland experimental results are in Section 4 Our results for the more general version of the problem with negatives and the lower bounds are given in Table
In Appendix F we give additional results, including an extension to t-negatives, NP-hardness of fining an embeddding in the minimum dimension needed to satisfy a of contrastive constraints, and results for an approximate setting in which we only need to satisfy a fraction of the constraints.
'This is since n² triplet samples are enough to describe all comparisons - for each anchor, it suffices to know the order of other points w.r.t. their distance to the anchor. Hence, for any embeddable set of samples Q. there exists set of most n² samples which is also embeddable and at least as restrictive Q.

---

Table Our results for contrastive learning
Setting
Upper bound
Lower bound
O ml/m), Theorem
$2
m))
Theorem
l with negatives
(vvm). Theorem
52
v m Theorem
lg with t-ordering loo
0 (v Theorem
mt)) Theorem
O(m2/3), Theorem
(( Theorem 43
8 integer p 21
((m). Theorem
Even pi [0(mm) odd p: 52( /m). Theorem 43
Table 2: Our results for N--N
Setting
Upper bound
Lower bound
4p (k-NN and ordering)
O(k19). Theorem
even p: ((k)) odd p: ((kk). Theorem 43
l (ordering of k-NN)
Ö(k²). Theorem 10
(ordering of k--NN
O(k) Theorem
[C
Lo (ordering of NN-N)
(2(k)) Theorem
k-NN the k-NN setting, we are given the following information for each data point.
Definition 4 (k-NN), For distance function ô: V x V + Rz0. let π (z),.... T Tn (x)) be an ordering of V \. } such that ö(x, TI(x)) < 8(x, π2(x)) < ... < 5(I, (xn-((x)) We define k-NNa( = (T (z), ...,, Tx(x)) as the ordered set of k closest points to x.
For function F: V - Rd. we denote by k-NNF the k-nearest neighbors in the E, ep-seace corre- sponding to the image of F. We prove the following theorem in Section
Theorem 5. Let 8: V x V + R2o be distance function, and let p 2 1 be constant. There exists an embedding F; V - Rd of into ly Ep-space of dimension d O(k log "0 n) such that k<NN,(x) = L-NNr(x), iee. the embedding preserves the ordered set of k-nearest neighbors of any point E V under the distance function 8!
We note that the above result is very surprising: k-NN graph fact corresponds to n(n - 1) triplet constraints - for each anchor, k- 1 comparisons between its k-NN and n k comparisons between the k'th nearest neighbor and the rest of the points - and Theorem I provides only an O(n) up- are able to exploit the structure of the
per bound dimension for the l case. Nevertheless, contrastive constraints to avoid polynomial dependence on n.
The following theorem addresses the setting when only the ordering of the k-NN has to be preserved. This, as well as other results for k-NN, are presented in Table
Theorem 6. There is an embedding of into Ez-space (kk) that preserves the k-NN ordering.
Our Techniques The key tool in our results is the notion of graph arboricity [NW6] NW64 ap- plied to the associated constraint graph. Arboricity of undirected graph is the minimum number of forests in which its edges can be partitioned. More intuitively, arboricity measures the "den- sity" of the graph: sparse graphs have low arboricity, while graphs with dense subgraphs such as cliques- - have high arboricity.
Fact 7 (Folklore; see e.g. [BE13 DHS91 and Appendix B.2 The arboricity r of a graph G with m edges is at most /m/2]. Moreover, if graph G has arboricity r, then the following hold.
(a) There is an ordering I1,... In of V such that (xx) 2r for each < i S n, where N- = (z, E N(x) < i} is the set of neighbors of x; in G preceding x; in the ordering.
(b) G is 2r-vertex colorable.
Definition 8 (Constraint graph). In contrastive learning, for a set Q of samples on V, we define the constraint graph G = (V, F)) as follows: for each sample (I,, V." -,-) E Q, we add two edges {xx, Vj} ) and (s,, 2;) F,, unless they already exist. In the k-NN setting, for each x and its nearest neighbors कi (z),.... ..., Tyk (x), we add edges {I, Ti Tz(x)) for < i k.
In subsequent versions of our paper, we have improved the analysis show dimension bound of Ō(k3).
3

---

Note that by Fact 7 the arboricity of the constraint graph resulting from m samples is at most mm. The arboricity of the N-NN constraint graph is at most k + (See Lemma (7]. We show bounds on the embedding dimension in terms of arboricity, e.g. for & we prove the following in Section 2
Theorem 9. Given set of non-contradictory inequalities among pairwise distances in V whose constraint gruph has arboricity v, there exists an embedding of V into E2-space TR.tr which satisfies all these inequalities.
Theorem follows from Theorem by using r S [vm/2] (Fact) 7 Moreover, since the arboricity of the constraint graph for k-NN at most k + 1 (Lemma 27). Theorem | shows that preserving the ordering of the k-NN in l requires ((k) dimension. Furthermore, the following theorem, proven in Section 3.1 implies that (k2)) dimension suffices to preserve orderings of the k-NNs in Ey-
Theorem 10. Given a set of non-cortrudictory inequalities among pairwise distances in V whose constraint graph has arboricity r, for any real p 2 1, there exists an embedding of V into Ey-space RO( a) which satisfies all these inequalities.
While the above constructions suffice for the contrastive learning case and for preserving the order- ing of the k-NN, the set of the nearest neighbors can change under the embeddings above. Hence, in order to preserve the k-NN, we increase the dimension to separate neighbors from non-neighbors. In particular, we construct the extended part of the embedding randomly, using sampling scheme which is guaranteed to embed neighbors much closer than non-neighbors. See Section 3.2 for more details and a proof of Theorem 5
For loc, instead of arboricity, we use a related fact: by removing a set Vhigh of (mm2/3) high-degree vertices, we reduce the maximum degree of the remaining graph (i.e. View = V Vhigh) to at most O(m2/3). We handle each differently (points in Vlo using graph colorings, and points in Vhigh using a Frechét-like embedding). See Appendix D.2 for the details and the proof of Theorem
1.2 Previous Work
Understanding the underlying geometry of a given set of n points based only on comparisons be- tween pairs of distances is basic question studied in the literature of non-metric embeddings (also known as ordinal embeddings or monotone maps). In a wide range of applications such as ranking, crowdsourcing, nearest-neighbor search, ad placement, recommendation systems, etc., the exact distances are not as important as their relative order. In fact, some of the early results in the field were motivated by applications in mathematical psychology [Tor5 She62 She74] CS74 Kru64a| Kru64b), and since then ordinal information and embeddings have been used in ranking [0G08 Ail12 [JJ13), metric learning [CHX+ 19), clustering (VD16 GPvL.19 KVH16),
crowdsourcing [TBB 11 JNI1a [N11b] and modeling human perception [ML09]. Note that the goal in ordinal embeddings is quite different from the vast literature metric embeddings (e.g.,
see [M [MSI7) where the goal is to approximately preserve the numerical values of distances.
We study the question of finding the smallest dimension d required to represent a given set of points such that given set of m distance comparisons are preserved. Related questions have been studied under statistical assumptions and it is known [KL14] TL14 GCY19] that for the large regime, upon knowledge of the ordinal relationships, the set of points can be approximately recov- ered (up to certain transformations). This serves further motivation for studying ordinal informa- tion as it highlights its power in recovering the underlying geometry of the data points.
However, determining the exact relationships between the dimension d, the number of points n and the number of given constraints m has been clusive. Most papers assume that all known.
(nn²) distance comparisons 8(2,, Z,,) $ 5(IK, æ1) among the pairwise distances * 08 BDH 08), for example, lower bounds are given for the dimension needed to preserve these comparisons. However, having access to such large number of comparisons is prohibitive in practice. We only assume access to a set of m distance comparisons and hence these lower bounds do not apply.
In [BL05] ABD
Contrastive learning has been studied for d = (embedding on the line) by 2 for dense in- stances, i.e. = (1²²). J. For higher dimensions, C1144] gives an Ω (n) lower bound on the smallest dimension (only for f2) that preserves all @(n²) triplet comparisons. Our Theorem improves this bound for the general case when triplet samples are given, without density assumptions. Then,

---

e sets inner products according to edge ranks
f makes norms of all vectors equal
Figure I: & is chosen so that if w(x, v) > w(x', w(',,y)) .y),, then (2, < (2', ). & ensures that all vectors have the same norm, i.e. || = W for all æ V.
(1 34) = w w(1 24)
G2 Ba) w/ w(f22 Rt)
(fs, F.) = w (f3, 2t)
J1
a
JG
Figure 2: Example construction of Ο. The embedding Р is computed based on the embeddings of its already processed neighhors é1, f2, f3.. We find the solution i4 to the linear system so that, for each edge preceding neighbor, the inner product equals the rank of the edge.
our Theorems and 3 go beyond & other f.- norms... Our results can also be seen as the reverse direction of the recent work by [AA In [AAF+24]. the central question is quantifying the amount of data required for generalization contrastive learning, assuming that the data can be em- bedded into an Sp-space of fixed dimension. Here we assume that the data is fixed instead and study the embedding dimension. Combined with [4]=+24), this completes the picture the relationship between the size of data, its embedding dimension and generalization.
Our second setting (k-NNs) was also studied in [C144] who showed lower bound of d (2(k) for preserving the ordering of the neighbors (again in &2). To the best of our knowledge, prior to our work, there was no known upper bound for the smallest dimension and here we provide a matching upper bound. Furthermore, we provide new results for k-NNs embeddings (both upper and lower bounds) under various lp metrics and results for the stronger setting when not just the ordering of the neighbors but also their status as k-NN has to be preserved.
Contrastive Learning in & Norm
In this section, we prove Theorem 9 that contrastive queries with the constraint graph G (Definition of arboricity r preserved when the points are embedded into l2 space of dimension 4r- from which Theorem and Theorem (oleowwwwwwww Fix a distance function 8: V x + R20 that satisfies the given set of iequalities (such function exists by Fact 25 We order all pairs of neighboring vertices by the distance function 8 in descending order, and let w(z y) = {z, y) is the i-th pair in the ranking. Recall that [z(()) - (2)ll = [[F(()) (22 + [F - 2 (F(x), FFF)(()(()))))) F(y)). In our construction, all embeddings have the same norm, and hence the distances depend only on the inner products between the embeddings.
We split the embedding F: V + t into two parts, i.c. for point x let F(x) (#, 2), where e R and i e R²r, For neighboring points x and y. our choices of â and I ensure that (á, 9) so w(x,y) y). We embed the points one by one into H in the arboricity ordering 21...., In. which by Fact F ensures that for every vertex, the number of neighbors with smaller indices is at most h. When embedding Z,, we make sure that for any neighbor T, E N (x.)) (i.e. a neighbor 2, of o; such that j < i) it holds that (2,, 2T) w(x,, x,). This requires solving a linear system over 4; with at most equations, and hence with h variables, with slight perturbations, the solution always exists.
The choices of è ensure that all vectors have the same norm while preserving the inner products. This is done by coloring the vertices of the constraint graph in colors using Fact 7 and assigning each color to unique basis vector, which is scaled to equalize the norms. Since these hasis vectors are orthogonal, the inner product between any two neighboring points v; and x. (it, R.).
Construction of it Assume .I,..., have already been chosen. Let N (xx) = {z, E ((x))) j i) be the set of preceding neighbors of x; in G. For each xj E N (æx), let linear equation P(i,j) be (æ;, ) = w(r,, I;),, where we consider the coordinates of é; as variables (recall that á, already for all 2, E N (z. Appendix C we show the following.
5

---

Lemma 11. The set of vectors {ā, m. E N (x(2))) is linearly independent.
By Lemma 11 the system of linear equations P. {P(i.j) 2j (x;)) has a solution
E "R Let ((() be ball centered at v with sufficiently small radius such that for any v' B(v) holds that (g)) w((r,,z)) xg)1 < 1/3 for all z; E (z; Choose a point v' uniformly at random from B(v), and 3. u/: this random perturbation guarantees that, with probability 1, Lemma [T holds in future iterations. By construction, the following property holds.
Proposition 12. For any x and any y E (1)),, we have (Ø. ()) w(x, y) < 1/3.
Construction of è; Let W = 2 max || By Fact there exists vertex coloring C: V - [h] of G, such that (x)) # C(y) for any pair {x, y) E F. Set (z)(((z), where <C(x) is the standard basis vector in the C(x))-h coordinate, and On is chosen so that [1)(x)] = | + || = W (note that 0g exists because || 12 < W). By construction, the following property holds.
Proposition 13, For any edge {a, v) E E, we have (it, 0) = O.
Proof of Theorem 9 (sufficient dimension for &g embeddings). For any edge {u, v) E E it holds that [F(u)) - F())11 [12(3)) + [|F(2))12
2 (û, 6) 2 (ú, 8)
By the choice of and i; we have [1F [F(2)] W. By Proposition 13 (ū, 8) and
hence the distance depends only on (ú, 0). For any (x. y+ =-) E Q. we have [(x) F F(v)l <
[[(()) F(z) | iff (.. 0) (i. By Proposition 12 for any edge {a,, y G holds that
(it, () wr( v) < 1/3. Since the function w assigns only integer values, it holds that (t. ú) >
(f if and only w(x y) < w(x 2), hence preserving the ranking of the edges.
Preserving k Nearest Neighbors
Let G= -V, E) be the constraint graph (Defimition { for given k-NN input. In Section 3.1 we show how to preserve the order between the neighbors in this graph, and in Section 3.2 we show how to separate neighbors from non-neighbors. Combined, these results fully preserve the k-NNs.
In this section, we focus on l nearest neighbors, and namely prove Theorems and 10
To simplify the presentation, we focus on the case p 1 - the construction for other p is identical, with the change being that each embedding coordinate value e should be replaced with e-/p, In this section, let 6(u,v) òē, (u, v). For non-contradictory set of samples Q, by Fact 25 there exists metric 8' consistent with Q. We order all pairs of neighboring vertices by the value of 8' in descending order, and let w(x, y) t (z, y) is the t-th pair the ranking. Given an embedding F, let a F be re-scaling of the embedding by factor of a, i.e. multiplying each coordinate by a.
3.1 Preserving the Ordering of the k-NN
In this section, show Theorem 10 This embedding is also used as a part of Theorem 5 shown in Section 3.2 Our embedding uses a new coloring scheme we call Neighbor-Collectan Coloring. Let 1i..... ......... , In be the arboricity ordering (Fact 7) and N N~ {xy (xi E, < <i} be the set of neighbors of I; preceding x; in the ordering.
Definition 14 (NCC Scheme). neighbor--oolletion coloring scheme is a set of K O(r log n) ,...,.c C((K) where c(U)) E for any x E V and [K], such that for any the following holds:
vertex colorings ((I), .....
(Collection) for any y E N=))), there exists a coloring j E [K] such that C/u = =C(i, and c. + cLu) for any = E N (x) (v).
(Load) for any j E [K]. the number of prior neighbors with j-th color being the same as Ci is small: Hy E N (x) cli -G() Ologn))
Intuitively, each coloring corresponds to part of the embedding. When the colors cli cfu) are different, the j'th part of the embedding always contributes the distance between x and y- Otherwise, we can select the j'th part so that it contributes either 2 or 0, and the collection property

---

guarantees that for any y E N (x)x) part we always have enough choices to get distance Finally, we represent (x, y) in binary format for all x, y. and, using an NCC scheme, we recover w(x, v) bit-by-bit.
(x) such part exists. The load property guarantees that for each
Lemma 15. There exists an NCC scheme for the constraint graph G.
Proof. For each E V and j E [K], we choose C. ii.d. uniformly at random from [r]. First, note that the load property holds: for any j E [K] and y E -NN((x) we have P
c -
1/r.
By Fact 7 we have (x)) & 2r, and by the Chernoff bound, color C(2) occurs no more than Ollog n) times in N (z) w.h.p. By the union bound, the load property holds w.h.p. for all j.
Next, for any fixed E V. y E (xr), and j E [K]. let (,) v) be the event that y is the only point in N N=(x) such that CP) Cli) Since the colorings are selected uniformly at random, we have P [At)) 3)] (11/r). Since K = Orr log n), by Chernoff, w.h.p. there exists j E [K] such that A 1) occurs. By the union bound, the collection property holds w.h.p.
Definition 16 (NCC-Embeddinng) Given a graph G and an NCC scheme, an NCC-embedding is an embedding of dimension O(r² log" n) of the following form. Associate each color E [r] with M = =Oogg n) unique basis vectors B(i) = {c(i-1)M++ C(i- (MMi1)) Ciss)- The embedding of point x is comprised of K parts z00) ,...,.,.. ,(K), where each part is a basis vector z15) E =B(Cl)),
i.e. a15) is one of the basis vectors associated with color c())
Lemma 17. Let D: E - {0, 13 be mapping of each edge, with 1 meaning "close" and O meaning "far". For each E V there exists embedding å into O log" n) dimensions such that for any {z, y) E E, it holds that 8(i, ú) = K D(x, y).
Proof. Let (CW,...., C(K)) be NCC scheme of G. We embed the points one by one according to ,...., the arboricity ordering Ti,..., In as in Fact We assume by induction that all nodes Ti,... T4-1 embedded using an NCC-embedding. For each y E N (x). fix one index j(y) such that under CUG)) the points x; y have the same color, which is different from colors of other points from (x) (such j(y) exists by the collection property). Let J = (i(y) ly E (x)),. and, since for any two points in N (x)) the chosen index is distinct, [J| = IN (z)).
For each part j E [K] [J]. we choose 2(i) to be a basis vector from B(CL that is different from all basis vectors (60) y E N- (x:).. This can be done, since, the one hand, for each cP" + cl., all basis vectors of B(CL)) are different from g(0), and, on the other hand, by the load property there are less than O(log n) points y E (x) such that c(u) = cl Therefore, we can choose basis vector that is different from any taken by these Olog n) points.
For each part j(v) E [J], we select the basis vector based on D. If D(x = 1, then we take a((())) g(ito)) Otherwise, we pick a basis vector ((((w)) B(C((())) such that (((e)) # (((())
We now show that distance between embeddings is 2(K - 1) if the points are close, and is 2K otherwise. The result follows by scaling the embedding. Let {ar
E such that y N (xr). Let [() (I. y) 1 if g6) # أ(o), and [(i (z, = 0 otherwise. Since each part is basis vector, 8(2 9) 2 2 (x) (x. y). By construction, for any j E [J] (i()) it holds that 100) 9) = 1. For j(y) we have ((())) (I,z) = D(x,)) y). i.c. 8(2, Ø) = 2(K - D(x, v)). Rescaling the embedding vectors by factor of 1/2 completes the proof.
Corollary 18. Let a' be a power of 2 such for all {x, E E we have az E (o....,,''s d'}. Then there exists an embedding F VfV into O(r log" 2 loggg a') dimensions such that for any (z. v) E E, we have 5 ((F(x), F(y)) = K(aa' - -1 Oz..y
Proof. Let (1) (ar, y) be the i'th bit of the binary encoding of ar using a string of size logg a' bits. Let F1...., Flog, of be embeddings as in Lemma 17 where for each F, we choose D, =
7

---

Bin (r, For embedding F(x) =
(2a o' (x)) we have
logg a'
((F(z).
Σ
K
Bin (4) (o,, v)
20-1
==1
loga a'
log, o²
K
2
Bin (x, 2'-1 = K(aa' -1) ax,y
1=1
Theorem 10 follows immediately from Corollary 18 by taking az,y = w(x v) and a' 2 m'.
3.2 Fully Preserving k-NN
In this section, we prove Theorem which states the existence of an embedding with dimension = O(k10 log" n) that preserves the k-NN. Our approach can be summarized as follows: for each E V. the final embedding neighbors {x', y/} $ E' be at a larger distance than any neighbors {x.y} E E, i.c. for some large W holds that ó(ē; fj) + W < 8( g.). The goal of å order the distances of neighboring pairs {z, v} E E according to their rank, while still keeping non-neighbors further away than neighbors.
F(x) (2mă, &) (Figure 3). The goal of è is have all non-
We choose ((6) via a random process, so that for any two neighbors {ø,8) y) E we have 2(1) = g(و) with some probability P1 (and otherwise they have substantial distance), while for non-neighbors {z, y $ E, we have أ0ي أهوو with much smaller probability P2 < P1. Repeating this process, we get separation in distances between neighbors and non-neighbors
è guarantees that non-neighbors in G are far
à preserves the order between the edges
Structure of embedding for fully preserving k-NN. f guarantees that non-edges have very large distance, i.e. if (2,y)= E E and (x',y/} & E, then 8(2, & 8(1', ('). orders the edges.
Figure 3:
Choosing 3: The embedding è is comprised of L (r log' n) parts, i.e. ft (a(1)
(D))
We take each part g-U) to be vector from design [DKS12 large family of vectors which approximately equidistant.
Definition 19 ((a,, Re-den)g For integer R and value 0 < 1, (a,, Rt)design is family of sets T. such that (a) for each S; E T. S, S [R²], (b) for each S E T, |Sa| = R, and (c) for each two distinct sets S, S₁ T. |S, n Sy a.
Lemma 20 (Lemma 1, DKK112)). For any sufficiently large integer and any value < a 1, there exists an (a, design T of size at least 2 log, R
Let T be (a, Re-desi for R = log n) and a = O(log n/R), where r is arboricity of the constraint graph (constants specified below). We associate S T with binary vector I(S)
(0, x² as an indicator vector of the set i.e. for E [R²] we have T(S) [ = 1 iff e S. For each V, we choose unique sets Sz, Sy E T and denote L2- = I(S.), = (S)). By Lemma 20 the number of sets is 2 log, R = 20tlog n), exceeding 2n for appropriate choices of constants.
We choose each part a(0) independently of the rest as follows. For p = O(1 (r probability p. we choose x(i) = Ig. and otherwise choose a uniformly random í E [2r]. ? < IN (z)], set ((6) = Iy, where y E N ordering, and set a(1) I' otherwise. Let (1-p)r be the probability that and y choose Iy- 2r
(rlrrllogn)) logn)), with
~xx is the i'th point in N (x) according to some
Importantly, in this construction, neighbors are significantly more likely to sample the same vector compared with non-neighbors. Moreover, sampling the same vector contributes 0 to the distance be- tween embedding, while sampling different vectors contributes at least (2 - ax) R to the distance. For K defined as Definition 14 let max( TooK" ) a constant, and set a S 8rlogg and we justify these choices of parameters and show the following.
R llog n/a]. In Appendix
8

---

Lemma 21. With high probability. the following bounds hold.
(2,y) $ E, then ( 1) 2RL] - Flogg n 7RL
If (2,u) E E, then 6 () 2(1 - R) S Flogg RL.
That is, according to the embedding, the gap between neighbors' distances and non-neighbor' dis- tances is larger than the maximum difference between neighbors' distances.
The final dimension O log "0 n): L Ø(r* log" n) parts of dimension R² (( log" n). Since r = O(k) (Lemma 27). follows that the dimension is bounded by 1 1og'0 n).
Final Embedding Let ,1....,., &n be the embeddings from Corollary 18 with a' being the closest power of two from above of the expression Smacy Flog R.L. These embeddings have di- O62² log" n). For {x, y} E, let A(x, y)
mension most O(r² log" n logaa a') [2m (5(2; 0) 2 - 3x RT.) Set dr.y A(x, v) w(x, v). where wr(2,, y) is the ranking of edge {x, if the edges are sorted by the decreasing order of distances. By Lemma 21 we have 4mmy RL 4mey RL w.h.p.. and hence az,y rlog
0 < A (z. v) llg
d' Finally, F(z) (2mi, i))
Proof of Theorem
For each x E V, let F(z) (2må, .). It suffices show the following.
(a) For any {z, y E E and {/'.z/} E E. it holds that w(x y) < w(r' if and only ((F(z),F()) > FFF(2),F(y))
(b) For any (x,w} E E and {2', & E, it holds that 8(F(x), F(y)) < 8(F(z'),
By Corollary 18 for any (2. E E:
((F(c),F())) = K(d' - 1) - 2m (0 9) - 2 - 100) RL)] w(x, 2mm (+,
-
K(a'' - 1) + 4m (1-7- 100
RI. w(x 8) E2.9-
(1)
where Ex.y E [0, is the rounding error. Hence, property (a) holds: if w(x,8) v) < wol', then ((F(x), F(y)) 8 ((F(x'), F(/)), and vice versa, since the comparison defined by ranking. The property (b) holds since for any (a', v')
}e & E and {I, E E:
(P(x'),F(F'))
8(2mã' 2mm'') 4m (1 Y
RL
100 Y
2 K 1) + 4m 11-7 100
RL > 8(F((),
where the second inequality follows from Lemma 21 and the third inequality follows from K(a' 4
1) & 4ymRL, which holds: since a' <
r Flog RL, suffices to have K S 10c
10c
log n, which
indeed holds for our choice of e max( log
TOOK 100).
Experiments
We perform experiments on CIFAR-10 and CIFAR- 100 image datasets [KHO9] (we show additional experiments Appendix A We define the ground- truth distance between points as the distance between their embedding vectors produced by a pretrained ResNet-18 neural network. Let Q be contrastive triplets sampled uniformly random from all possible triplets of images, labeled based on the ground-truth distance. Then, we train different ResNet- 18 model from scratch, where we control the embedding dimension by replacing the last fully-connected layer with a fully-connected layer with the chosen output dimension. We train the model for 50 epochs single NVIDIA A100 GPU using triplet loss [SKP15b]: (p(x, y* our goal is to find an embedding of this set of queries, we evaluate the accuracy as the fraction of satisfied contrastive samples.
FF())) F(v)l F(x) F (2))l1++ 2 +1. Since
We present our results Figure In experiments, we vary the number of samples (Figures 4a and 4b) and the dimension (Figures 4c and 4d Figures 4a and 4b show that, while d 2 /m,

---

1D
m=10
30
of unsariiied samples,
Fraction of unsattfeed camples.
21
22
2*
24
20
30
50
10
20
40
50
Epoch
Epoch
(a) CIFAR-10: 10: the fraction of unsatisfied samples for various choices of the number of samples The
(b) CIFAR-100 100: the fraction of unsatisfied samples for various choices of the number of samples m. The embedding dimension is d 128.
embedding dimension is d= 128.
d=is
2-64
256
d 1024
25
1024
Fraction uncatieted samples,
Fraction of unssatieted samples.
22
% 12
22
24
10
30
40
50
10
20
30
40
50
Epoch
Epoch
(c) CIFAR-10: the fraction of unsatisfied samples for various choices of the embedding dimension d. The number of samples m = 10
(d) CIFAR-100: the fraction of unsatisfied samples for various choices of the embedding dimension d.
The number of samples m 10
Figure 4: Experiments CIFAR-10 10 (left) and CIFAR-100 (right). The data points show the average over 5 runs, and the shaded area shows the minimum and the maximum values over the runs
the resulting embedding is consistent with almost 2 99%) triplets. On the other hand, for m E {105, 10"}, d is substantially less than /m, and the number of satisfied samples sharply drops from 99% 93%. This is consistent with our theoretical results in Theorem 1
Not surprisingly, Figures/4c 4d show that, when the embedding dimension increases, so does the accuracy, i.c. the number of satisfied triplets. But the accuracy stops increasing when the dimension reaches approximately /m se 316 while there is 2% accuracy increase when the dimension changes from 64 to 256, there 1024. This again conforms with our result from Theorem
accuracy increase when the dimension changes from 256 to
5 Conclusion
In this paper, we provide bounds on the necessary and sufficient dimension to represent a collection of contrastive constraints of the form "distance from to is smaller than distance from x to This a fundamental question in machine learning theory, since educates the choice of deep learning architectures by providing guidance for the size of the embedding layer. Our experiments illustrate the predictive power of our theoretical findings in the context of deep learning. We also believe that it gives rise many interesting directions for future work depending the exact desiderata: approximate versions, different choices of normed spaces, bi-criteria algorithms, agnostic settings.
While the considered distance comparison settings play central role in contrastive learning and nearest neighbor search, so far there has been no theoretical studies of their embedding dimension. Our work is the first to present series of such upper and lower bounds in a variety of settings via novel connection to the notion of arboricity from graph theory. As a follow-up, one can consider an improved embedding construction for k-NN: in the upped bound from Section the dependence both log and can likely can improved. Another interesting direction is tighter data-dependent bounds dimension: while provide fine- grained bounds in terms of arboricity which potentially much stronger than bounds in terms of the number of edges - they don't 't necessary capture properties of dataset which lead to sharper bounds.
10

---

Acknowledgments and Disclosure of Funding
We would like thank Michael Barash for several very helpful suggestions. Work by Orr Fischer was partially supported by the Israel Science Foundation (grant No. 1042/22 and 800/22), Work by Vaggos Chatziafratis was partially supported by Hellman's fellowship and startup grant at UC Santa Cruz.
References
[AAE+24] Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer, and Grigory Yaroslavtsev. Optimal sample complexity of contrastive learning. In The Twelfth International Con- ference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024.
[ABD [0] Noga Alon, Mihai Bädoiu, Erik D Demaine, Martin Farach-Colton. Mohammad Taghi Hajiaghayi, and Anastasios Sidiropoulos. Ordinal embeddings of minimum relax- ation: general properties, trees, and ultrametrics. ACM Transactions on Algorithms (TALG), 4(4):1-21, 2008.
[ADK22] Pranjal Awasthi, Nishanth Dikkala, and Pritish Kamath. Do more negative samples necessarily hurt in contrastive learning? In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Con- ference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 1101-1116. PMLR, 2022.
[AGKM22] Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigat- ing the role of negatives in contrastive representation learning. In Gustau Camps- Valls, Francisco R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022. Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 7187-7209, PMLR, 2022.
[Ail12] Nir Ailon. An active learning algorithm for ranking from pairwise preferences with an almost optimal query complexity. Journal of Machine Learning Research, 13(1), 2012.
[AMR92] Noga Alon, Colin McDiarmid, and Bruce A. Reed. Star arboricity. Comb., 12(4):375- 380, 1992.
[BD++08] Mihai Bădoiu, Erik Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropou- los, and Morteza Zadimoghaddam. Ordinal embedding: Approximation algorithms and dimensionality reduction. International Workshop on Approximation Algo- rithms for Combinatorial Optimization, pages 21-34. Springer, 2008.
[BE13] Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory. Springer International Publishing, Cham, 2013.
[BHB19] Philip Bachman, R. Devon Hjelm, and William Buchwalter. Learning representa- tions by maximizing mutual information across views. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer. Florence d' Alché-Buce Buc, Emily B. Fox. and Roman Garnett, Advances in Neural Information Processing Systems 32: Annual Con- ference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14. 2019, Vancouver, BC, Canada, pages 15509-15519, 2019.
[BL05] Yonatan Bilu and Nati Linial. Monotone maps, sphericity and bounded second eigen- value. Journal of Combinatorial Theory, Series B, 95(2):283-299 2005.
[CH67] Cover and P. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1):21-27, 1967.
[CH21] Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In IEFE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pages 15750-15758. Computer Vision Foundation IEEE, 2021.
11

---

[CHX* 19] Fatih Cakir, Kun He, Xide Xia, Brian Kulis, and Stan Sclaroff. Deep metric learning rank. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 1861-1870, 2019.
[CI24] Vaggos Chatziafratis and Piotr Indyk. AimeensionAAccrace Tradeoffs in Contrastive Embeddings for Triplcts, Terminals & Top-k Nearest Neighbors. In 2024 Symposium on Simplicity in Algorithms (SOSA), Proceedings, pages 230-243. Society for Indus- trial and Applied Mathematics, January 2024.
[CKNH20] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A sim- ple framework for contrastive learning of visual representations. 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, pages 1597-1607. PMLR, 2020.
[CLL21] Ting Chen, Calvin Luo, and Lala Li. Intriguing properties of contrastive losses. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jen- nifer Wortman Vaughan, editors, Advances Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 11834-11845, 2021.
[CRL+20 20] Ching Yao Chuang, Joshua Robinson, Yen-Cher Lin, Antonio Torralba, and Stefanie Jegelka. Debiased contrastive learning. In Hugo Larochelle, Marc Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neu- ral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[CS74] James P Cunningham and Roger N Shepard. Monotone mapping of similarities into general metric space. Journal of Mathematical Psychology. 11(4):335-36 1974.
[DHS91] Alice Dean, Joan Hutchinson, and Edward Scheinerman. On the thickness and ar- boricity a graph. Journal of Combinatorial Theory, Series B, 52(1):147-151, 1991.
[DKS12] Anirban Dasgupta, Ravi Kumar, and D. Sivakumar. Sparse and lopsided set disjoint- ness via information theory. In Anupam Gupta, Klaus Jansen, José D. P. Rolim, and Rocco A. Servedio, editors, Approximation, Randomization. and Combinatorial Opti- mization. Algorithms and Techniques 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15- 17, 2012. Proceedings, volume 7408 of Lecture Notes in Computer Science, pages 517-528. Springer, 2012.
[DL97] Michel Marie Deza and Monique Laurent. Geometry of cuts and metrics, volume 15 of Algorithums and combinatorics. Springer, 1997.
[DSRB14] Alexey Dosovitskiy, Jost Tobias Springenberg, Martin A. Riedmiller, and Thomas Brox. Discriminative unsupervised feature learning with convolutional neural net- works. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 766-774,70 2014.
[FIM+20] Bohan Fan, Diego Ihara, Neshat Mohammadi, Francesco Sgherzi, Anastasios Sidiropoulos, and Mina Valizadeh. Learning lines with ordinal constraints. In Approxi- mation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Schloss Dagsuuh-Leiiniz--eentnn für Informatik, 2020.
[Fré10] M. Fréchet. Les dimensions d'un un ensemble abstrait. Mathematische Annalen, 68:145- 168, 1910.
[GCY19] Nikhil Ghosh, Yuxin Chen, and Yisong Yue. Landmark ordinal embedding. Advances in Neural Information Processing Systems, 32, 2019.
12

---

[GH10]
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new esti- mation principle for unnormalized statistical models. In Yee Whye Teh and D. Mike Titterington, editors, Proceedings of the Thirteenth International Conference on Arti- ficial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13-15, 2010, volume 9 of JMLR Proceedings, pages 297-304. JMLR.org, 2010.
[Goe06] Michel Goemans. Topics in tes: Embeddings of finite metric spaces, lecture 1, 2006.
[GPvL19] Debarghya Ghoshdastidar, Michaël Perrot, and Ulrike von Luxburg. Foundations of comparison-basee based hierarchical clustering. Advances in neural information processing systems, 32, 2019.
[GYC2I] Tianyu Gao, Xingcheng Yao, and Danqi Chen. Simcse: Simple contrastive learning of sentence embeddings. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021, pages 6894-6910 Association for Com- putational Linguistics, 2021.
[HFL*19] R. Devon Hjelm, Alex Fedorov, Samuel 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.
Karan Grewal, Philip
[HFW* 20] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick. Momentum contrast for unsupervised visual representation learning. In 2020 IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 1726-9735. Computer Vision Foundation / IEEE, 2020.
[HM23] Jeff Z. HaoChen and Tengyu Ma. theoretical study of inductive biases in con- trastive learning. In The Eleventh International Conference on Learning Representa- tions, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
[HWGM21] Jeff HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- suff-super deep learning with spectral contrastive loss. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 5000-5011, 2021.
[IMS1]] Piotr Indyk, Jivrí Matouvsek. and Anastasios Sidiropoulos. 8: low-distortion embed- dings of finite metric spaces. In Handbook of discrete and computational geometry, pages 1. Chapman and Hall/CRC, 2017.
[JN11a] Kevin G Jamieson and Robert Nowak. Active ranking using pairwise comparisons. Advances in neural information processing systems, 24, 2011.
[JN11b] Kevin G Jamieson and Robert D Nowak. Low-dimensional embedding using adap- tively selected ordinal data. In 2011 49th Annual Allerton Conference on Communi- cation, Control, and Computing (Allerton), pages 1077-1084. IEEE, 2011.
[KH09] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report, University of Toronto, 2009.
[KL14] Matthäus Kleindessner and Ulrike Luxburg. Uniqueness of ordinal embedding. In Conference on Learning Theory, pages 40-67. PMLR, 2014.
[Ku664a] Joseph B Kruskal. Multidimensional scaling by optimizing goodness of fit to a non- metric hypothesis. Psychometrika, 29(1):1-27, 1964.
[Kru64b] Joseph B Kruskal. Nonmetric multidimensional scaling: a numerical method. Psy- chometrika, 115-199, 1964.
13

---

[KVH16] Ramya Korlakai Vinayak and Babak Hassibi. Crowdsourced clustering: Querying edges vs triangles. Advances Neural Information Processing Systems, 29, 2016.
[LL18] Lajanugen Logeswaran and Honglak Lee. An efficient framework for learning sen- tence representations. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Pro- ceedings. OpenReview.net, 2018.
[Mat13] Jin Matouvsek. Lecture notes metric embeddings. Technical report, Technical report, ETH Zürich, 2013.
[MCCD13] Tomás Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. In Yoshua Bengio and Yann LeCun, editors, 1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 2013, Workshop Track Proceedings, 2013.
[ML09] Brian McFee and Gert Lanckriet. Partial order embedding with multiple kernels. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 721-728, 2009.
[MMW+11] Jovana Mitrovic, Brian McWilliams, Jacob C. Walker, Lars Holger Buesing, and Charles Blundell. Representation learning via invariant causal mechanisms. In 9th International Conference on Learming Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[NW61] C. St.. A. Mash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, s s1-36(1):445 450, 1961.
[NW64] C. St.. A. Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Sociery, s s1-39(1):12-12, 1964.
[OG08] Hua Ouyang and Alex Gray. Learning dissimilarities by ranking: from sdp to qp. In Proceedings of the 25th international conference on Machine learning, pages 728- 735, 2008
[Opa79] Jaroslav Opatrny. Total ordering problem. SIAM Journal on Computing, 8(1):111- 114, 1979.
[SAG+22] 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. Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, Interna- tional Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 19280-19286. PMLR, 2022.
[SE05] Noah A. Smith and Jason Eisner. Contrastive estimation: Training log-linear mod- els on unlabeled data. In Kevin Knight, Hwee Tou Ng. and Kemal Oflazer, editors, ACL 2005, 43rd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, 25-30 June 2005, University of Michigan, USA, pages 354-362. The Association for Computer Linguistics, 2005.
[She62] Roger N Shepard. The analysis of proximities: multidimensional scaling with an unknown distance function. Psychometrika, 2252); 1962.
[She74] Roger N Shepard. Representation of structure in similarity data: Problems and prospects. Psychometrika, 39(4):373 1974.
[SKP15a] Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embed- ding for face recognition and clustering. In IEEE Conference on Computer Vision and Puttern Recognition, CVPR 2015, Boston, MA, USA, June 7-12, 2015, pages 815-823. IEBE Computer Society, 2015.
14

---

[SKP15b]
Florian Schroff, Dmitry Kalenichenko, and James Philbin. FaceNet: A unified em- bedding for face recognition and clustering. In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 815-823, June 2015.
[SPA + 19] Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theoretical analysis of contrastive unsupervised representation learn- ing. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors. 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 Re- search, pages (628-5637. PMLR, 2019.
[TDR 20] 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. OpenReview.net, 2020.
[TJ06] MTCAJ Thomas and A Thomas Joy. Elements of information theory. Wiley- Interscience, 2006.
[TK221] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, ference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pages 1179-1206. PMLR, 2021.
editors, Algorithmic Learning Theory, 16-19 March 2021, Virtual Con-
[TKI20]
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Com- puter Vision ECCV 2020 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XI, volume 12356 of Lecture Notes in Computer Science, pages 776-794. Springer, 2020.
[TL14] Yoshikazu Terada and Ulrike Luxburg. Local ordinal embedding. In International Conference on Machine Learning, pages 847 855- PMLR, 2014.
11] Omer Tamuz, Ce Liu, Serge Belongie, Ohad Shamir, and Adam Tauman Kalai. Adap- tively learning the crowd kernel. Proceedings of the 28th International Conference on International Conference on Machine Learning, pages 673-680, 2011.
[Tor5]] Warren S Torgerson. Multidimensional scaling: I. theory and method. Psychometrika, 17(4):401-41, 1952.
[TWSM21] Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. Self-supervised learning from multi-view perspective. In 9th International Confer- ence on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[VD16] Sharad Vikram and Sanjoy Dasgupta. Interactive bayesian hierarchical clustering. In International Conference on Machine Learning, pages 2081 2001-20 PMLR, 2016.
[vdOLV18] Aäron den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with con- trastive predictive coding. CoRR, abs/1807 .000000078..220 2018
[vKSG+21] Julius von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmentations provably isolates content from style. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin. Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 16451-16467, 2021.
[War68] Hugh E. Warren. Lower bounds for approximation by nonlinear manifolds. Transac- tions of the American Mathematical Society, 133(1):167-178, 1968.
15

---

[WG15] Xiaolong Wang and Abhinav Gupta. Unsupervised learning of visual representations using videos. In 2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, pages 2794-2802. IEFR Computer So- ciety, 2015.
[WI20] Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on 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, pages 9939..
PMLR, 2020.
[WJJ13] Fabian Wauthier, Michael Jordan, and Nebojsa Jojic. Efficient ranking from pair- wise comparisons. In International Conference Machine Learning, pages 109-117. PMLR, 2013.
[WL21] Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self- supervised contrastive learning. In Marina Meila and Tong Zhang, editors, Proceed- ings of the 38th International Conference Machine Learning, ICML. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 11112-11122, PMLR, 2021.
[WXYL18] 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, pages 773--3742. Computer Vision Foundation IEEE Computer Soci- ety, 2018.
[ZSS+21] Roland S. Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel. Contrastive learning inverts the data generating process. CoRR, abs/2102.08850, 2021.
16

---

A Additional experiments
10a
10
10
10
10
10'
n 128
6,
32, 34
162, 169
256
256
256
n 256
6
20
135, 139
452, 464
512
512
n 512
4, 6
12
80, 82
508
1024
1024
n 1024
43,
363, 366
1453, 1473
2048
2048
4, 6
24, 25
202, 204
1479, 1488
39
Table Embedding dimension based on construction from Section For each pair of n and m, we show the minimum and the maximum dimensions obtained when the minimum and the maximum are equal).
10 runs (we show single number
8192
16384
32768
m 49152
Fraction of unsatisfied samples, %
12288
m= 24576
m 40960
25
24
23
2
21
2
10
20
30
40
50
Epoch
Figure 5: CIFAR-100: the fraction of unsatisfied samples for various choices of the number of samples m. The embedding dimension d 128.
In this section, we present additional experiments.
Contrastive Samples In Table 3 for various values of and m, show the dimensions of the embeddings constructed according to Section 2 We sample m random triplets from the CIFAR- 100 dataset, and label the triplets based ResNet18 network. Note that the embedding dimension is always at most 2n, which corresponds the case when the constraint graph is clique. Moreover, in agreement with theory, when m < n²? increasing decreases the required dimension: the constraint graph becomes more sparse, which decreases the arboricity.
ground-truth embedding generated using pretrained
In Figure 5 similarly to Figure 4b we show training accuracy on CIFAR-100 dataset for various values of m. In this figure, we focus the setting when is close to d = 16384. While for S d /2 the accuracy is close to perfect (99%), the accuracy decreases starting from this point. This supports theoretical result that d O(ym dimensions required to preserve the contrastive samples.
k-NN In Table present results for k-NN settings for d 128 and for various choices of n and k. We sample n points from the CIFAR- 10 dataset, and generate k-NN based on a ground-trum truth em- bedding generated using pretrained ResNet18 network. For each element let (x:,, ..., " (x) be the ordering of other elements according to the ground-truth embedding. For each and é E [A] and each j > i, we generate contrastive samples (x, (x)* (x)) and train the neural network on this set of samples similarly to Section
For each n and kt we report the loss function measuring the quality of preserving the k-NNs, defined as follows. For each vertex x and each [k), we compute the change of rank the i'th nearest neighbor of in the new embeddings. Formally, we find such that the i'th nearest neighbor of
17

---

k
==
k=
=
k 16
k 32
64
n 10
0.0, 1.8
0.05, 0.8
0.15, 0.8
0.22, 0.78
71 100
0.01, 0.07
0.21, 0.32
0.58, 0.7
1,
1.27
1.6, 1.8
2.16, 2.46
2.5, 2.9
1000
0.04, 0.07
0.34, 0.4
0.81, 0.93
1.47, 1.54
2.3, 2.4
3.36. 3.44
4.9
Table 4: Training loss for preserving k-NNs for various values of n and For each pair of n and k, we show the minimum and the maximum dimensions obtained over 10 runs (we show a single number when the minimum and the maximum are equal).
according to the ground-truth embedding is the j'th nearest neighbor according to the trained embedding, contributing j - jl to the loss. Finally, we define the final loss as the average loss over all V and E [k].
Table 4 shows that the loss increases with both A and n. However, dependence on n is much lower than dependence on k; supporting our theoretical result which shows polynomial dependence on k and only polylogarithmic dependence on n.
B Preliminaries
Definition 22 (Metric, semimetric). An metric space is an ordered pair (X, 8x) consisting of a set X and map 6x : X X + [0, oo] such that 8x satisfies:
1. 5x(x; v) = = x
(x(2) = 6x(y, x). all x, EX;
(x(22.) v) + (x, 2) S 8x (z, for all x, y, 2 X.
If 8x satisfies the last two properties but only 6x (x, x) = 0 for all x E X instead of the first one then it is called semimetric.
We note that the triangle inequality doesn't affect our results. Intuitively, our goal is to preserve the ranking of distances, and adding a sufficiently large constant to distances preserves the ranking while also satisfying the triangle inequality.
Definition 23 (lp norm, eg distance function, fo norm). Given vectors u, o E R and p 2 1, the distance between and of under the Ep norm is
1/P
d (v, = ΣMM - -(ip
-
where u|i] is the i'th coordinate of vector The distance between v and of under E, is
8eg(t, 2')
Σ ulo Eu 11
1=1
The distance between v and v' under the lox norm is
82 (v,
max[v[i] - 3' [i]]
sE(u!]
For 2 or co, the norm of v is defined as || = 5z, (u, v).
Fact 24 (Chernoff bound). Let XI....,X, X, E {0, 1} be mutually independent random variables.
Denote by и E Xi), the expectation of the sum of variables. Then for any Y 1
holds that
(-22
-224
7M
< 2exp
(-2
3
1=1
Additionally, for any o >> it holds that
72p
Σ x; x. (1+7)
5 exxp
2 2+7
18

---

B.1 Ordinal Embeddings
Fact 25 ((LO0)). Given set of non-contradictory inequalities among pairwise distances on V, there exists metric 8: V V + I2 which satisfies all the inequalities.
Proof. Consider graph whose vertices are V x V and create directed edge between two vertices if they participate in some inequality. Since the inequalities are non contraddicoory. there are no cycles in this graph. Consider any topological ordering of this graph and define Wij to be the index of each pair in the topological ordering. Let ò W Wij where W = IV]2. Note that å satisfies the triangle inequality.
B.2 Arboricity
In this subsection, present basic facts about arboricity, and analyze the arboricity of the constraint graph in our various settings.
For directed graph, we say that the out-degree of a vertex is R, for some integer R, if x has R incident edges oriented towards x.
Fact 26 ([MR92), Lemma 2.2). If the edges of G can be oriented such that each vertex has in- degree at most R for some integer R. then r S R
Lemma 27. The constraint graph in the k-NN setting has arboricity at most k + 1.
Proof. In the constraint graph of a k-NN instance, we have an edge for each pair (x, <;())) for 1 Sii k x E V. where N, the i'th nearest neighbor of z. If for each such pair, we orient the edge inwards to z, we obtain a directed graph with in-degree at most k. Therefore, by Fact 26 the constraint graph has arboricity at most & 1.
Finally, the following fact relates the number edges m and the arboricity of the graph.
Lemma 28 (DHS99 Theorem 2). Any graph G with edges has arboricity S [V mm/22)
C Missing Proofs From Sections 2 and 3
Proof of Lemma 77 Since |N (z)] < h for all x, it suffices to show that with probability 1, any subset C ( .......... ] of size |A| < is linearly independent. We prove by induction on |A]. and the base case |A| = 0 trivially holds.
For the induction step. let & be the last point in A. By the induction hypothesis, A {é) are linearly independent. Let H = Span(A) A) {.)), and let B the ball where é is sampled from. Since Vol(H) and VB >
we have P j E H] = O, meaning that A are linearly independent.
C.1 Proof of Lemma 21
In this section, 8(x, v) = ||a yl1. For other &p for +o0), the construction is the same by replacing each coordinate value with c//p.
Agreement sets
Before proving Lemma 21 we define the following sets:
Agr(z,y) {j [z]] أ00) -00)
Agrp y) = (i a()) = -100) = - or 266) = 91 = Lyb.
Agrn (z. (j 3z E (=)x)))))))) N- N (v) such that ((5) g(و) = Iz}.
The idea is to measure on which indices the points agree and to differentiate sources of agreements.
Agr(a, y) is the set of indices on which x and y agree, i.e. choose the same vector.
Agro (z. y) is the set of indices where and y choose the same vector by direct connection: chooses its own set Ig and y chooses r's set I (or reverse).
19

---

Agrn (z, y) is the set of indices where a and choose the same vector by an indirect connection: a and y share a common neighbor 2, and both choose z's Zz.
Note that Agr = Agtp U AgTN. When x and y are neighbors and and are not, we will show that Agr x. y) = (x, y) AAgr(r', y-)l
Choice of parameters
We next remind the choice of parameters.
Graph arboricity S 2k
The size of the design
R ( log n)
Probability that an element doesn't 't choose its own design vector
p = O lo
Probability that neighbors choose the same design vector
7 pfl pp) O
log
Fraction of intersecting elements between sets in the design
a O رم log n
The number of blocks corresponding to designs
L = O log" m2)
We next justify the choice of the parameters.
In the proof of Theorem 5 to counter the K = O(r log n) term from Section 3.1 for {a,y} E E
To achieve that, need to bound we need to bound the spread of |Agr] for neighbors as rlogn" the spread both |Agea| and Agrr))
|Agr
First, we need to guarantee that |AgeN| O ((
(grr))
Proposition 30 we require that
2r (z))² ín n This since 2r (1) bounds the probability that two points select the same common neighbor (which counts towards Agrn), while the probability that x will choose Iy for E N (x) (which counts towards Agrp). Since y= p(l-p) this bounds O(1/(r log n)) and (11((1")) log n)).
2r
To bound the spread of |Agrl, note that E [[Agr]] L]. To bound the spread Chernoff we must have 7 = log" n. meaning L - r log"
AAgrol by r log
Different sets from the design (Definition 19p intersect by at most R elements. When two points sample different sets, the distance between their embeddings increases by the number of elements outside of their intersection, which is at least 2 al. Note that the distance between neighbors will be approximately
(2R - -R)aa (Agrl)) 2RL 72 -0--00 -a))
Similarly to the above, we want bound the deviation due the a/2 term. and by the same logic ((1((r") log"n))
we choose O(7/(r(ogg)))
We need choose 2n sets from the design. Since by Lemma 20 the design has 20dt sets, to guarantee that this value is at least 2n, we take a and R so that all = 2(log n), meaning R (r² log" r2).
Proofs
The next statement shows concentration of AgrD for neighbors and non-neighbors. Proposition 29, For any x. y E V, if {a,, y} & E then [Agrn w)) = 0, and if (x, v) E, then eyL
[AgTD( v) - L S 4r log w.h.p.
Proof of Proposition 29 If [x, & E, then x & N N- and y & N- (x), i.e. for every j [Z]. we have 206) + L, and أا6ي) + In and hence AAgrn v)1 O.
If {a, 3) E E, assume w.l.o.g. that y E N- (xx). Therefore, j E Agro(a, y) if and only if we set (او I, and أ00) Ty- Recall that P (μ() = I,] =1 and P [+(0] I,] = (2r)..
Therefore,
P E AgrD v)] = p(1 p)
2r =,
i.c. E [[]AgrD(I, 2)1] LL Since L 12r n2), by Chernoff, w.h.p. we have
eyL
AAgro v)1 - - <
4r log
20

---

We next show concentration for AgTN. Note that AgtD for neighbors is much larger than AgnN for both neighbors and non-neighbors.
Proposition 30. For any x, E V, we have S Agr ()1 S
erL w.h.p.
4r log
Proof. We bound the expectation of [Arr v)]. Recall that j E Agrx(a, v) if and only if there exists point N (x) n (y) such that &6) a(U) 12 and (هt) T- are independent, each occurring with probability p/2r.
and (( I.. Moreover, the events
Since | (x) N (=)l < N (x)) < 2r, we have
P 2r
LI²
E Ag Ml - (N (z))
2r
Finally, we note that
Ly 2r
2(log n). and by Chernoff, w.h.p.:
4 3 T8 (1AgTN((, y)ll = 3 2r
4
Lp²
CYL 4r log n
Agnn(a, v\1 -
Proof of Lemma 21 Recall that Ó(ē, 0) Σラ 8($0), gol). For each j Agr(z, v), have 8(26), ((0) = 0, and for j & Agr(x,3) y). due to the property of the (a, de-dss, we have
18(2 g()) 2R| < 2aR.
Summing over all j & Agr(a, v). we get
((t,0) 2(L Agr(z, S 2aRL 4r log
CY
RL,
(2)
where we used S
cy 8r lng
Non-neighbors By Equation ( we have
If [f y) & E, then by Propositions and 30 we have < |Agr(z, v) <
CrL
Tr log
6(2, 0) (1
cy
2RL < RyRL
RL
<
R.
18(2,)) 9)
4r log
4r log
r log
Neighbors
If fxx y) E E, then by Propositions 29 and
207L 4r log n
||Agr(ı, 10) - 7 s
and by Equation 22 it follows that
20y
RL < CyRL log n1
10(2, 9) 211-7) RL| <
4r Ar
D Contrastive Queries in bp Norm
In this section, we show upper bounds for dimensions for embedding into space with l, -orms or loo -nrrm.
D.1 Contrastive Queries for Finite
In this section, we prove Theorem 3 which provides an upper bound of m on the embedding dimension in E, for integer 2 1.
We say that set S C V V is symmetric if (a, v) <> (y,z) 2:) S.
Due to the symmetry, with slight abuse of notation, we define the cardinality |.|] for symmetric sets to be equal to the number of distinct unordered pairs in S.
21

---

Definition 31 (Partial semimetric), An ordered triple (V. VVS.ós) consisting of a set V, symmetric set S S V V and map óg: - [0, oe) is a partial semimetric space if óg satisfies the following:
1. For all x E eV, if, x) E S then 85(x, x))
2. 65(2, v) 0s(y, for all (x.,)) E S,
3. 65(z, 1) + (5. =) 2 65(x, for all (x, v), (a, 2), (1) E.
Definition 32 (Partial embedding). We say that a partial semimetric (V. S, partially embeds into a metric space (Y, vr ) if there exists a map F; V + Y such that 65(2, y) = öy all (z, y) S.
for
The following lemma is an extension of the standard embedding result into lp (see e.g.
DL97
Lemma 33. Let S = (V, S, 6g) be a partial semimetric on V and let m = |S]. S partially embeds into an f7 space with finite dimension, then it embeds into (fp) em)m+
Proof. Let (1 y1) )" be the unordered pairs of S. We assign every partial semimetric (V,S, 8)) on S an m-dimennional vector vs, where vy [i] 6(2,, 31). We call vs the representation vector of (V, S. 8). Define NOR to be the set of representations of all partial semimetrics on S which can be partially embedded into eg. i..
NOR = {ws There exists d E N such that (V,5,)) partially embeds into (IR" (g)-
Note that NOR is cone:
1. os NOR then aus NOR for all a O.
2. If 0g, E NOR then es + ug E SORS.
An extreme ray is a point vs E NOR such that es = 18, + Un2 for U8y Ub2 E NOR then has to be that va, awt and Vsg- (1 a)us for some [0,
Next, we show that any extreme ray of NORS has a partial embedding into the one-dimensional space (R, fg). Indeed, let va be an extreme ray, and let be the minimum dimension for which (V,S,8) 8) partially embeds to (Rd, ; eg). If d = 1, then we are done; otherwise, assume by contra- diction that d >> 1. Let F : V + Rd such that 8(æ, v) (f)),x), F())) for all (x, E S. Let F1 TR, F2 V Rd-1 such that
F(x)(d)) i... Fi is the embedding F restricted to the first dimension, and F2 is F restricted to the remain- ing dimensions. We notice that for each (z,y) E V x V, (f((x,))) = (F + (F2,
Fz( = [())[1] and F2(x) =
Define Pl, P2 S RR such that (I (F(F(()) Fi and p2(x, y) F2(r)
Therefore, Ug Up1 + Up2-- Since Uy is an extreme ray, then there exists E [0, such that Vgg = 0'Upp In particular, 5 can be partially embedded into one dimension, by taking the embedding (z), contradicting minimality of d. We conclude that d 1.
Finally, let Uy be the representation vector of S. By Caratheodory's theorem, since es E NOR there exists m + extreme rays ohy,. V8,.. E NOR such that vs Em++1 U&g- We have shown that for each i E [m + 1], the partial semi-metric (X, S, 6.) has a partial embedding F(() V + R into the one dimensional space (RR (g). It follows that the embedding F = (P(1),.... F(,++)) is partial embedding of S into (Re=++1 ()) and the claim follows.
Proof of Theorem 3 If is set of non conorrttrrriitoryyyyyooo constraints, then we can embed it into &g using Theorem I We can then embed it isometrically into Ep (see Chapter 1.5 from [Mat13] and Theorem 5 from (ooc06)). By using the same points, the relationships between distances are also preserved in lg. Let be the set of all edges in the constraint graph G. Then we have a partial semimetric (V. 5g) which is partially embedded into eg. By Lemma 33 it partially embeds isometrically into 1St)1 For the same embedding, the relationships between distances are also preserved in 4p- D
22

---

D.2 Contrastive Queries in loo Norm
In this section, we prove Theorem 2 which states that dimension (mm2/3) suffices to satisfy any set of m non-contradictory contrastive queries Q in the lx norm.
Let G (V.E) be the constraint graph, where E is the edge set. We arbitrarily assign a unique identifier id( E [r]] for each a E V. Let Vhigh S V be the set of points with degree with at least m 1/3 in G. Let Vlow = V Vhigh.
Our embedding is concatenation of two embeddings Fi and F2, which intuitively "handle" Viow and Vhigh respectively. In the sub-embedding Fi, we use the fact that the graph induced by Viw has low degree to argue that it has a proper distance-2-edee coloring with (mm2/3) colors, i.c. we can color the edges of the graph such that no two edges at distance most share the same color. We use this coloring to obtain an embedding Fi: Vie + RO(m(()) which satisfies certain distance properties between any pair of neighbors in Vlow- We then extend F1
embedding F: V RO(m2/) which is consistent with Q. This extension draws inspiration from the seminal Fréchet embedding [Fr for each point in I; Vhigh we add a single distinct dimension in which we intuitively set this coordinate for each point x E V as distance from I; in F.. In actuality, we set these coordinates slightly differently, in order to combine correctly with the sub-embedding Fi, and obtain embedding which is consistent with Q. By Lemma 34, the size [highh Omm3/3), which implies that together the dimension of F is (mm2/3)
Lemma 34. Let Q be the set of contrastive queries. Let Vnigh be the set of points with degree at least m/ in the constraint graph. Then Vhigh! Omm2/3)
Proof. Recall that each query (t..t+== ) E Q is associated with two edges, {2,y}, {z, =} E E.
Hence, the total number of edges in G most 2/Q| = 2m. This implies
1/3 [Vighl m
S
Σ deg(x) xx) S Σ deg(z) 2|E| = 4m.
TrE Vnighh
By rearrangement, we obtain that [highh < 4m233
Since Q is non-contradictory, by Fact 25 there exists a metric 5 consistent with Q. Using the Frechét embedding [Fre10], any metric on n points may be isometrically embedded into Ra-1 under the foo norm.
Definition 35 (Scaled Frechét embedding F'). Let F'; V R be an embedding of 5 into the cube [0, 1 1/2 under the Eox norm, obtained by scaling and shifting (i.e. multiplying or adding some value to all coordinates, respectively) the Frechét embedding of 8.
We note that scaling and shifting do not affect whether a contrastive query is satisfied, therefore F is consistent with Q as well.
I Lemma 36. There is an embedding F1 of Vio into RO(m2/3)) such that the following hold:
(a) for each x E Viow and E N, it holds that (x E [0,
(b) for each w. y E Viow such that {2r E E, it holds that (1F(()) (1 = (1F())) F'ly)l
Proof. By definition, each œ E Viow has degree at most A = O(m²/3). Therefore, there is an edge E), in which (a) every vertex has most one incident
coloring C: E + [ + 2] of G edge of any color, and (b) any two adjacent vertices 2, y share exactly one edge color the one of their shared edge C(z, y). We remark that this coloring is called in the literature distance-2 -edge coloring. Such coloring can be found using a greedy approach, where we color the edges one by one, where for each edge (x. y we choose a color that is not taken by previous edges of x, y or by edges of any neighbor = E N(r) U N(y). In other words, let K( y) be the set of colors taken by any edge incident to any vertex {2,y) U N(x) U N(y). Since K (z. y) S 2 + 1, then we can always choose from (x. y) color different from all colors of K (z, v).
23

---

We define the embedding Fi as follows: assume the color of the edge of fa, y) is C(z,y) E + Let C(x, y) and assume w.l.o.g. that id(x) id(y). We define (x)
and (i (x) For any x E V, if a coordinate is not set in this process, we set (i 1 = 1/2. We note this is well-defined since the edge coloring is proper (i.e. no vertex has
1/2 + (z)
two edges of the same color), so no coordinate is set twice. This concludes the description of the embedding.
Next, we show that properties (a) and (b) hold. Recall that we consider distances over loo, hence for each pair z, y E Vlow there is a coordinate i(z. y) E N for which [I)' - F")y))o = (=)((() y)] - (')))
For property (a), we note that every coordinate is either set to Fty)[t] = 0, to F(y)
1/2 + (x)) F" (w))lo for some x E V. Since [x(x)) - F'(y) so E [0. 1/2,, and hence
[[F()) Pc = 1/2+ [IF =v) E [0. 1), property (a) follows.
Next, we show that property (b) holds. Denoting c C(r, for each edge (a.y) E E such that id(x) < id(y), it holds that (x) 0 and F"(v)lc] 1/2+ ((x) [()]lo.. Second, since æ,
share only one edge color, in each other coordinate j ش c, either [x = 11/2 or F, (y) - 1/2.
meaning that is the coordinate with the maximum difference, i.e. [1) Fi(w) 1/2 +
[IF((x)) F
The Overall Embedding:
Lemma 37. Let F1: Viow - RO(m2()) be the embedding described in Lemma
36 Then there exists
an embedding F: V + (R such that for any (zx22) E F. it holds that F [()) - F(=)]l>> = 1/2 + [I - (z)]loc.
FF)))>())))l
Proof. Let 0m32/3) be the dimension of F1 (i.e. Fr: Viw + RR,), and r [Viigh = O(m2/3). Let Vhigh = {yI.........................f{.. yr We define F(x) as follows: for yi E Vhigh. we set all coordinates for 1 S j S (d+i- F(y))[ 1/2, the (d+ th coordinate as (l 0, and set any coordinate ++++l1 For E Viow ++1 I S d + r, we define as F(x) = 1/2 + (z) - F')y))) This concludes the description of the embedding.
S d + r to F(y)]l = 1/2 + [.((()) - F (yr--))
set the first d coordinates to be in F1(.). The remaining r coordinates, i.e.
First, we show that for any xr 2 E Viow such that (ar E F, it holds that [F(xx) F(z)ll> = 1/2 + (z) - (x) This indeed holds by Lemma 36 and by the fact that in all the r last coordinates are set to a value in [1/2, 1]. i.c. the difference on any of these coordinates is at most 1/2.
Next, we show that for any x E Vlow and y E Vhigh such that {a. yr E E, it holds that F()) F(y))l の = 1/2+ Fz) - F* (xx))loc Indeed, in any coordinate j o (d+ i.+ ([) 2 1/2, and
hence F(y:) 1 - F(=) S 1/2. On the other hand, in the (d + 1)'th 'th coordinate [ (Fy:)(d d + i]
F(x)(d+ + = 1/2 || (z) - F (''(:))l > 1/2.
Finally, we consider the case where y/. Vy Vhigh such that {yr, E F. and < j. For the first d coordinates, both vectors are set to 1/2, in all coordinates between + 1, 1,..., .. + j 1 the vector YA set 1/2, and therefore they differ by at most 1/2 in these coordinates. For the (d + +)'"th
coordinate, yj is set to zero, and y/ is set to 1/2 + (v:) (1:)))) For higher coordinates, both yi, yj are set to values at least 1/2. Therefore, || F(ys)) (lo)) 1/2 | (y:) FF (lo)) O
Finally, we show that F is consistent with Q Lemma 38. The embedding F: V RO(m2()) 2/) is consistent with Q.
Proof. For any (x,v*,20 ) E Q, it holds that [[F((z)) - FF' < [FF(xx) F'(x) and therefore
[[F(x) - F(=)Il= = 1/2 FF (z) - (=)]l=> > 1/2 + [|F - F'(v) = [F(()) -P))))(())l--)
And since [[((x) - F(y)ll> < [1((x) - F(=)l the query (x, =-) satisfied.
Theorem 2 follows directly from Lemma 38
24

---

E Lower Bounds
In this section, we prove lower bounds for all our settings, Before presenting the main theorem of this section, formally introduce the notion of ordinally embedding metric ó into Ep space.
Recall that for x E V. we denote Ti (T) to be the points in V \ {x} ordered by their distance from ø.
Definition 39 (Ordinal Embedding). Given a metric 8, the fall ordinal sample Q(6) is the fol- lowing set of samples: Q(5) = {(x, n. (x), ( (x)) x V, E [n 2 We say that d can be ordinally embedded in lp space in dimension if its full ordinal sample set Q is consistent with some embedding in Ep space with dimension d.
Next, we present the main theorem of this section, from which we can obtain lower bounds for all our settings:
Theorem 40. For E N (oo), there exists a metric ō on n points which can only be ordinally embedded in fy-space using d = (i()) dimensions if p is a constant even inleger p 2 d (n/ log n) if is constant odd integer p 2 1 or 00.
We remark that the special case of p = was previously proven in C124 To prove Theorem 40 need several propositions.
For set of unlabeled triplets C. we say that a set of samples Q is a labeling of C' if Q has exactly one labeling for each unlabeled triplet of C' (and no other sample). We next show that there exists set of (nn²) triplets so that any its labeling is valid.
Lemma 41 ([AAE*22 24)). For V {xI,...,Tah, let C = {( unlabeled triplets, whose labeling compares distances between 2.) and (I1, Then for any labeling Q of C, there a metric de consistent with Q.
be the set of
Proof. Let Q be labeling of C. Fix anchor 2; and consider graph where we create directed edge Tj + 1++1 when (xi, 27. 3f41) E Q, and an edge Iz+1 + Ij when (Ii, o "f,, E Q. Note that for any Q this graph is acyclic (since the corresponding undirected edges form a path), and hence there exists topological sort p, 24+1,.... En. We define a metric 8 so that 6(z,, 8(1,, x2) = n + (z²,) for < j and 8(I,, x;)) = for all
Note that 5 is metric: by construction, 5 is symmetric and 5(x,x) = 0 for all and the triangle inequality satisfied since all distances are between n and 2n. Finally, note that 5 satisfies all samples from Q.
Next, we use a claim proven 24]+ showing that any sufficiently large set of unlabeled triplets has an labeling which does not have d-dimensional l, space embedding consistent with it (where the size of the unlabeled set is at least some function of n,, d,,,p).
Fact 42 ([AEE* 24), Reformulated), Let be an integer, V be a set of n points, and E 21, ..U {oo} } be constant. Then there exists constant Cp 0 such that for any sufficiently large the following hold.
If p is odd or p= oo, then for any set of triplets C of size at least log n on V, there exists a labeling of C which is not consistent with any d-dimensional Ep space.
If p even, then for any set of triplets of size at least epnd on V, there exists a labeling which is not consistent with any d-dimensional fy space.
We consider the case of even p cases of odd and infinite p are analogous. By Lemma 41 for some constant > 0 there exists a set of triplets C' of cardinality at least en so that any labeling of C realizable by some metric. On the other hand, by Fact 42 when |C| > n,ddd there exists labeling Q of C which is not consistent with any d-dimensional f, space metric. Solving for d, unless d nc/cp. there exists labeling which is not realizable in the d-dimensional lp space. Hence, d 2(n)) for even p.
Proof of Theorem 40
25

---

Next, we show lower bounds for our settings, namely for contrastive learning and k-NN, and for the extended settings of t-negatives and t-orderings, All lower bounds follow as immediate corollaries of Theorem 40
Theorem 43. Let p be a positive even integer.
1. (Contrastive triplets) There exists set of non-contradictory triplet samples Q of size [Q] = m for which any embedding in lgp space consistent with Q must have d [(mm).
(t-negatives) There exists set of non-contradictory t-negatives samples Q of size [Q] = m such that any embedding in lp space in d dimensions requires d = m)(mm).
3. (1-orderings) There exists a set of non-contralictory l-ordering samples Q size IQ] = m such that any embedding in lpp space in d dimensions requires d = m2(
4. (k-NN) There exists a metric ó on n points such that any embedding in lp space which preserves the k-NN ordering of 6 must have d = (2(k) dimensions.
When p is a positive odd integer or when p = -C, the lower bounds decrease by a logarithmic fuctor, that is the lower bounds are respectively (1/mm/ logm), Q1k/ log k), M0 log,), and O mt/ log(mt)).
Note that in the above statements, can be arbitrarily large: in the proofs below, we can choose subsets of required size inducing all the samples.
Proof. We consider the case of positive even p. The cases of positive odd or infinite p are analogous.
1. Choose an arbitrary set V of size /m. By Theorem 40 there exists a non-contradictory sample set Q of size ((m) on point set V such that any embedding into Ep space which is consistent with Q must have dimension 12( (.)m).
2. Let V be an arbitrary set of size vm + (t - 1). and V be an arbitrary subset of V of size v Vm. By the previous item, there exists non-contradictory sample set Q' of size O(m) set V that requires dimension (()m) dimensions. Let V V = { U1-1) For each s' = (x,yt,27) E Q', define s to be the + 1)-tull sample s = (z,y*, 27, U1 ..... 171)) Let Q be the set of all such (t + 1)-tuple samples.
Next, we prove that Q is con-contradictory. Since Q' is con-contradictory. there is a metric 8' on V' which is consistent with Q. Consider the following metric 5 on V: for 2r, y E V", we set 5(z, y) = d'(x, y). and otherwise 8(z,1) y) = D, where D = 2 maxx.yev 5(x, y). It is easy to see 8 satisfies triangle inequality, and is consistent with Q. Since every constraint in Q' is implied by some constraint in Q, embedding preserving Q must also preserve Q', requiring 2( dimension.
Choose an arbitrary set V of size /ml. By the first item, there exists a non-contradictory sample set Q' of size O(mt) on set V that requires dimension 2(vmt). It suffices show that there is a set of non-contradictory Q of size ((m) of (t + 1)-tuple samples that imply all inequalitics of Q'
Consider a metric 5 on V consistent with Q'. Denoting the j'th nearest neighbor of x according to 8 as Ty (z),, let
Q Usev ( (x),... TT (I)) T2. (()) (x)),...,
where the adjacent samples share one item. We note that Q is consistent with 8, hence non- contradictory. Finally, every inequality in Q' is implied by the inequalities of Q: this is due to the fact that is consistent with Q', and Q implies all ordinal constraints of 5 (as it implies the order of distances between each point and all its neighbors).
4. Choose an arbitrary set V of size k + 1. By Theorem 40 there exists a non-contradictory sample set Q on point set such that any embedding into fy space consistent with Q must have dimen- sion 2(k). Consider metric 5 on V consistent with Q. Since [V] = k + 1, k-NNs preserve all triplet comparisons of 6, and therefore, any embedding of V preserving the k-NN ordering has to be consistent with Q, hence requiring dimension 12(k).
D
26

---

F
Other Results
In this section, we first extend our results to contrastive queries with more than two candidates. Then, show that the problem of actually constructing the embedding consistent with given trastive samples is NP-hard. Finally, we consider an approximate setting for contrastive learning, in which we only need to satisfy an o-fraction of the constraints. We show that there exists instance for which satisfying a R 0.77 fraction of the constraints requires roughly the same number of di- mensions satisfying all constraints. On the other hand, show that for S 1/2, one dimension always suffices.
F. Upper Bound for t-Negatives and t-Ordering Samples in f2-norm
In this section, we consider two additional settings, in which each sample contains ordinal informa- tion about the distance between an anchor point and multiple (i.e. more than two other) points.
In the first setting (t-negatives), we are given a set Q of m samples, where each sample s is a (t + ttupee s (a, yt, 2 .T..,.()) We say sample s is satisfied by distance function ó if 8(z,y) > 6(x 2;) for all 1 sist.
In the second setting (t-ordering), we are given a set Q of m samples, where each sample s is I-tuple 8 (x,
V..........0 :/)), and we say sample is satisfied by distance function if 8(2, y1 <
5(1, < ... < 8(x,, wt) for all S S L.
Theorem 44 (l-orderings, (negatives). Lei Q be a set of m non-contrudictory l-ordering samples (resp. t-negative samples) set V. There is an embedding of V into E--sace ((ymm) which is consistent with Q.
Proof. For a set of (t + 2)-tue samples Q on of size m. we define the constraint graph G = EV as follows: for each sample (I14..., E Q, we add t-d+++1 edges (21,22),.... {01, Tz+23 to E (if they don't already exist).
First, we note that the constraint graph of t-orderings and t-negatives has arboricity O( O(vmt). In- deed, we add for each sample at most (t)) edges to G, hence the total number of edges is at most (mm)). By Fact 7 the arboricity of G is O(v By Theorem 9 there exists an embedding into fg-space with dimension = O( ((mt)) that satisfies the corresponding inequalities.
F.2 NP-Hardness for d d=
In this section, we show that, empirical risk minimization for embedding into an Ep space is NP- hard. Even in the realizable case and even for d = 1, finding an embedding satisfying constraints is NP-hard, by the reduction from the betweenness problem.
Definition 45 (Betweenness). You are given a set of items X of cardinality n and set of triplets for all The goal of the betweenness problem is to find an order of items on X so that for each i, by is located between and c,. That is, the goal is to find bijection r: [l....,n} so that for each either r(a,) < r(b.) < r(c,) or
f(a1. bi, 61), ........ (am dm, em)} }. such that a; by. C,
r(G)) < r((b)) < r(as) hold.
Opa79 shows that the decision version of the betweenness problem - i.e. checking whether such ordering exists is NP-hard.
Theorem 46. Unless P N., there no polynomial algorithm for finding embedding into l space for d = 1 in the realizable case.
Proof. Let A be an algorithm for finding an & embedding for d = 1, which accepts the set of contrastive queries as an input. For contradiction, assume that in the realizable case the algorithm finds an embedding in time at most T(n) = poly(n), where n is the number of points.
Let A' be the algorithm which executes A for most T(n) poly(n) iterations. This way, A' runs on all inputs in time at most 7 (nn) and outputs an embedding satisfying the input constraints iff such an embedding exists.
27

---

We complete the proof by reduction from the betweenness problem. Let (i,,b,,,....... (am bm, Cm) be the imput for the betweenness problem. Then, we can represent constraint "b, between a and of" using two contrastive constraints (at, b , and (c,,b,,00 0z ). For example, if r(b:) < r(a:) < r(ci), then the constraint (ci, bj a0; is violated; other cases are similar.
We execute A' on this set of contrastive constraints. Since the algorithm finds satisfying embedding iff such an embedding exists, we can check whether the contrastive constraints and hence the original betweenness constraints are satisfiable by checking the output of the algorithm. Hence, we can verify whether the set of betweenness constraints is satisfiable in the polynomial time, which contradicts NP-hardness of the problem and assumption that P + NP.
E.3 Satisfying a Fraction of Constraints
In this section, we consider the settings when the embedding doesn't have to satisfy all the con- straints. Instead, for some constant a, want to satisfy at least an a-fraction constraints. We show the following separation in the Ep case for any integer p.
Theorem 47. For the embedding into Ep space for p E (1,2.3.... ..., the following hold.
For any < 1/2, for any set of m constrainis, for any d 2 1 there exists an embedding with dimension d satisfying at least om constraints.
Let a" = 0.77 be the root of equation H H(x) = x, where H the binary entropy function. Then for any a > a", there exists set of m non-contradictory constraints so that satisfying at least am constraints requires dimension least 22( (m)) for even p and at least 1M log m) for odd p.
Notes The theorem shows that for a S 1/2, the problem trivializes, while for a > a², the problem is asymptotically as hard as in the case when we have to satisfy all constraints (up to log m factor for odd p). There gap between 1/2 and = 0.77, and we hypothesize that a* bound is the most likely one to be improved, due to the union bound used in the proof below.
Proof. The case a S 1/2 follows by the probabilistic argument, using the observation that a random one-dimensional embedding satisfies half of the constraints in the expectation. It remains to handle the case a > a". For that, we construct a set of m triplets, and, for a random labeling of m triplets, we look at the induced labeling of each subset of am triplets. For each individual subset, show the probability that its induced labeling is achievable is less than 1/( 1/(.))) By the union bound, the probability that any of the induced labelings is achievable is less than 1, implying that for at least one labeling, none of the induced labelings is achievable
will
le distance We first consider the fy-case, and below we describe how to handle f, distance for other integer p. By Lemma 41 there for any set V of items, there exists C of m = ("=2) unlabeled triplets such that any its labeling is realizable. For a sufficiently large n, assume that d < for some constant e (depending on a and to be specified later). We will show that for > a", there exists no subset of C' of size am so that every its labeling is realizable by some embedding into a d-dimensional space. For that, we will use the following fact.
Fact 48 (War668), ). Let m > 2 2 be integers, and let PI....,PP Pm be real polynomials on t variables of degree at most s. Let
U(Pr....,P...
EXER' + for all i E [m]]
be the set of points RR which are non-zero in all polynomials. Then the number of connected components in (P......PP. is at most (4esm/t)*.
Similarly to AAE 24), we apply this fact to the following polynomials: for each triplet (a. y, 2), for a fixed embedding function F, we define a polynomial
Pays = [F(x)) F(v) -I((== F(=)1} Σ (P(())-(()))
Σ (((()))((a))
1=1
28

---

Denoting V = f....... Inl, all Pa Pzys for (2, v.2) E C' are polynomials over nd variables Fi( Fi (=n).... Fa(xn))
Importantly, when satisfied by F, the polynomial is negative. Hence, different choices of labels of C must corre- spond to the different sign combinations of polynomials. Fact 488 shows that the number of sign combinations of the polynomials and hence the amount of possible labelings bounded by x²
-) is satisfied by F, the polynomial is negative, while, when (x, at, ,
(8em (Sem/nd)"tt & (den/d)" where we used m = (-22))
For any subset of am constraints, there are 2 possible induced labelings. On the other hand, as shown above, only (4en/d) (d)ndd)d of the labelings are achievable. Taking the ratio of these values, we get that the probability that an induced labeling is realizable is at most
(Aen/d)dd
2nd (tge
2am
As outlined above, since there are at most most 1/( mm By well-known fact [T066]
m am
subset of am constraints, we want this ratio to be at
gamy < 2H(mm where H is a binary entropy function.
m
Hence, the probability that any subset of am induced constraints is satisfiable most
(ten/d)m aam
(ondoor/tte//) = (4tHH())aa(((daaaaa)))) (ten(f))/)))
2a 12
Since m (n-1)//2, for sufficiently large n have nd/n /mmm 3d/n. n. Consider the case when d < en for some constant c. When e < 4, the last term (3d/n) (4gg(4en]))) monotonically increases in d, and hence we have
(a) a (nd/m) loga (4en/d) H(a) + Bclog2(4e/c)
When a > a., where a* = 0.77 satisfies a H(x"), we have 0 > H(a) Since f(c) 3e 3clog, (4e/c) is continuous and strictly monotone for e E [0, 4) and f(0) 0, there exists d' > such that (a)) - a + 3c' log, (4e/c) < O. Hence, when d < d'n, there exists labeling of m triplets, so that no subset am triplets is satisfiable.
lp distances for positive integer p odd, we encounter the issue that
When is even, the above argument doesn't 'tt change. When
d
[F(x)) - F(y) (1)(z) F(=))I
Σ F(((z) F(U Σ RR()) -((=))
not a polynomial. We address this issue similarly to AAE 24|: for each coordinate i, we guess the order of points with respect this coordinate. This introduces additional factor of (ml)d 20(dd in the number of possible sign combinations. The derivation is similar the above, but we instead want the following inequality:
H(a) - a + (nd/ m) logg(4en/ou d)) + O( log < 0,
which holds when cn/ log n for some constant c.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification:
The abstract and introduction clearly state all claims and contributions.
Guidelines:
The answer NA mcans that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation long as is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
All limitations of the work are discussed.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate' "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to viola- tions of these assumptions (e.g., independence assumptions, noiseless settings, model well- specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide elosed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address prob- lems privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't I acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
Justification: Paper contains full proofs for all claims.
Guidelines:
30

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- rooss-referecee...
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main exper- imental results of the paper the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes].
Justification: Paper discloses all information needed for reproducing the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided not.
the contribution dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways, For example, if the contribution is novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
new model (e.g., a large language model), then there should either
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the case of closed-soure, source models, may be that access to the model limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes].
Justification: code added to supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
31

---

Please see the NeurlPS code and data submission guidelines Sodeeeemisiinnnnn
for more details.
While we encourage the release code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to repro- duce the results. See the NeurIPS code and data submission guidelines (https://nips.... cc/ for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparame- ters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes].
Justification: Full information and code are available.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes].
Justification:
All experiments have error bars and other nessecary information.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eтrors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
32

---

8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the exper- iments?
Answer: [Yes].
Justification:
The paper provide full information on the resources used in the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
Code Of Ethics
Question:
Does the research conducted in the paper conform, every respect, with the NeurIPS hptp//eurriip....
Code of Ethics
Answer: [Yes].
Justification:
Paper fully conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper diseuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: The paper studies fundamentals of embedding theory, and it does not contain any subjects that might introduce any direct societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology being used intended and functioning correctly, harms that could arise when the technology is being used intended gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
33

---

If there are negative societal impacts, the authors could also discuss possible mitigation strate- gies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not re- quire this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes].
Justification: All datasets are properly cited and credited. We are not aware of any standard license mentioned the dataset's creator's paper website, but it does include guidelines how to properly use and cite their asset, which we followed.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset,
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpppapppphaaeoc thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the de- rived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes].
Justification:
The code used for experiments contained in the supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part their submis- sions via structured templates. This includes details about training, license, limitations, etc.
34

---

The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, applicable, as well as details about compensation (if any)?
Question:
Answer: [NA].
Justification:
The paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/revieww based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and lo- cations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if appli- cable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "E2bNrwKPOv", "reviewer": "Reviewer_x73K", "summary": "Paper studies the embedding dimension of contrastive learning and kNN problem.\nIn the first, we are given n points along with some constraints of the form (x,y, z1, z2, .., zm) which mean that x is closer to y and far from z1 z2  zm. Indeed, y is said to be positive label for x and z1, z2, zm are negative exmaples. It has been seen that such learning with + and - examples yield very good quality. \n\nSo the question studied in this work is if we were to embed the objects into vector space such that ||f(x) - f(y)|| < || f(x) - f(zi) || for all i, then what embedding dimension do we need?\n\nSimilarly, k-NN classifiers are used widely in ML. Here, we are given (x, y1 y2, .. yk) and want to preserve the ordering in the embedded space, i.e.,  ||f(x) - f(y_i)|| < ||f(x) - f(y_j)|| when i < j. In a generalization, we also require that y1.. yk are the kNNs in the embedded space also. \n\nMain results:\nAuthors show for l2 metrics, we can embed into sqrt(m) dims for contrastive learning\nThey show slightly weaker results for l_infty metric and l_p metrics for general p.\n\nMore interestingly, for k-NN embeddings, they show embeddability into poly(k) dims for lp norm and k dims for l2 norm!\n\nMain idea is to use arboricity as a key intermediate concept in showing embeddability. Indeed, a graph has arboricity r if it can be split as a union of r trees/ forests in general. Nice graph theoretic result states that graph with m edges has arboricity sqrt(m). \nThey then use this on the constraint graph resulting from the constraints placed by the embedding requirements (distances less than other distances). They show that if constraint graph has arboricity r, it can be embedded into l2 metric of dimension O(r). Moreover for kNN constraint graph they show that arboricity is O(k), so the result follows. Most relevant prior work [CI24] which gives some lower bounds.\n\nThey finally show some empirical results on CIFAR dataset showing that the obtained theoretical bounds can be met in practice.", "questions": "I have asked my qns in the weakness section.", "limitations": "Paper does not have explicit limitations/ future work section and would benefit from one.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "It is very interesting to study embedding dimension. Embeddings are the cornerstone of future ML and low-dimensional embeddings representative of data is crucial. Contrastive learning and kNN methods are important tools, so preserving their structure is useful. \n\nThe paper has clean ideas using arboricity as intermediate concept. Paper is also well written.", "weaknesses": "The experimental section seems slightly less convincing. Indeed, the embeddings you use to validate are not the ones you show theoretical bounds for right? Or am I misunderstanding. \n\nCan we show that such embeddings which preserve contrastive and kNN properties are as useful down the line as the original embeddings for various tasks? Some empirical study along these lines would be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your careful review. We’ve updated the experimental section to provide a more precise validation of the theoretical bounds (please the global response posted to all the reviewers above).\n\nRegarding the downstream applications of our embeddings, the answer to this question is two-fold:\n* k-NN embeddings themselves represent the main downstream task in their context. Such embeddings are used for recommendation systems, ranking, etc. Hence, preserving Top-k results in this context is exactly aligned with the objective of the downstream task.\n* The primary goal of our work is not to develop a scheme for computing embeddings better than the existing deep learning pipelines. It is our goal, however, to provide theoretical guidance for the choice of the embedding dimension in such architectures and do this in a theoretically rigorous fashion. Hence, we don’t expect the exact embedding constructions proposed in our theoretical bounds to perform better than the empirical embeddings which might be able to better capture the intrinsic structure of the data. It is only our goal to argue that the dimensionality used by these empirical constructions indeed suffices.\n\nRegarding conclusion/future work, please refer to the global response.\n\nPlease let us know whether our response addresses your concerns.", "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": "vRPw71BNp7", "reviewer": "Reviewer_ex1k", "summary": "The paper \"Embedding Dimension of Contrastive Learning and k-Nearest Neighbors\" investigates the minimum embedding dimension required for representing datasets labeled with distance relationships in l_p-spaces, focusing on contrastive learning and k-Nearest Neighbor (k-NN) settings. The main findings suggest that the arboricity of associated graphs significantly impacts the design of these embeddings, providing tight bounds for the popular l_2-space and sufficient or necessary dimensions for other l_p-spaces based on the size of data (m for contrastive learning and k for k-NN).", "questions": "1. Bound Tightness (Section 1.1, Line 61): The paper discusses tight bounds for embedding in l_2 spaces for both contrastive learning and k-NN settings. Could you clarify the specific conditions or dataset characteristics that lead to these bounds being tight, and whether similar tightness is achievable in other l_p spaces?\n\n2. Proof Complexity (Section 2, Lines 157-204): The proof of Theorem 8 relies on complex constructions involving vertex coloring and ordering by arboricity. Could you provide further intuition or simplified explanations to make this more accessible to readers without a deep background in graph theory?\n\n2. Experimental Results (Section 4, Lines 328-347): You mention experiments on CIFAR-10 and CIFAR-100 with various embedding dimensions. Could you elaborate on how these experiments were structured, particularly how the embedding dimensions were selected and their impact on the model performance?", "limitations": "The main limitations that come to my mind are the limited empirical support and the complexity of the theoretical concepts.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "One of the best papers that I read in a while! This paper is a standout piece, brilliantly blending strong theoretical insights with robust experimental validation. The authors have done an excellent job of presenting both lower and upper bounds, along with detailed experimental results, which really bring their work to life. It’s refreshing to see such a thorough demonstration in the field.\n\n- Theoretical Depth and Rigor: The paper provides a rigorous mathematical framework for determining the embedding dimensions necessary for accurately representing data in different l_p-spaces.\n\n- Practical Relevance: By exploring both contrastive learning and k-NN, the study addresses fundamental issues in machine learning that are highly relevant for practical applications, especially in areas like image recognition and nearest-neighbor classification.\n\n- Comprehensive Analysis: The analysis spans multiple norms (l_2, l_inf, and general l_p) and provides both upper and lower bounds, tight bound, making the results robust and versatile for different scenarios.", "weaknesses": "Complexity of Proofs: Some of the proofs, especially those involving graph arboricity and its relation to embedding dimensions, are quite intricate and may not be easily understandable to readers without a deep background in theoretical computer science. Proofs might benefit from additional clarification or simplification for better understandabelity to non technical users. I had hard time reading and understanding them. (Disclaimer: I still need more time to fully digest them)\n\nEmpirical Validation: While experimental results are mentioned, the paper could strengthen its claims by expanding on these results, particularly how they compare with theoretical predictions across different settings and data scales.\n\nApplication for non-expert audiences: The paper presents significant theoretical results that could impact practical machine learning applications, but the presentation style and technical jargon might be inaccessible to non-specialists in theoretical computer science, which limits its potential audience and applicability.\n\nThe presentation could benefit from some polishing and simplification of the notation, though this is more a matter of preference than a true weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your positive feedback, thoughtful review and the suggestions. \n\n### Complexity of Proofs\n\nThanks a lot for pointing this out, we’ve substantially updated the exposition by adding illustrations of the key concepts (you can find some examples in the *global response* to all reviewers), as well as illustrations for some of the most complicated parts in Sections 2 and 3.\nWe will also simplify the notation in the technical sections and add the intuitive explanations. To give an example, in Section 2, the arboricity $r$ implies that there exists an order of vertices so that each vertex has $O(r)$ preceding neighbors.\nWe use it when constructing both parts of the embedding:\n* First, during construction of $F_1$, we want to control the inner products between the vertex and its preceding neighbors.\nThis leads to at most $O(r)$ linear equations, and, by guaranteeing linear independence, it implies that $O(r)$ variables (that is, the embedding dimension of $O(r)$) is sufficient to guarantee the existence of the solution.\n* Second, during construction of $F_2$, for each vertex we update a single coordinate to normalize the vector. We want to avoid changes in the inner products between neighbors, and hence for each vertex we select the coordinate different from that of any preceding neighbor. Since there are at most $O(r)$ preceding neighbors, we require only $O(r)$ coordinates.\n\n### Empirical Validation\n\nAs per your suggestion, we added a major update to the experimental section by focusing on the various settings (you can find it in the *global response* above).\nIn particular, the response includes:\n* $\\ell_2$ construction based on Section 2;\n* k-NN experiments;\n* experiments on LLMs.\n\nPlease note that in Figures 3a) and 3b), we consider different values of $m$, which corresponds to a wide range of data scales, having as much as $10^6$ samples (in the *global response*, we consider up to $10^7$ samples).\n\n### Application for non-expert audiences\n\nWe clarified the technical sections to make them more accessible.\nWe have added a conclusion section (see a comment above) to summarize our main contribution, which we believe should be relevant to non-experts.\nIn particular, our results provide guidance for the choice of embedding dimension in contrastive learning and k-NN applications, which we believe can be understood without diving into the theoretical details.\n\n### Bound Tightness\n\nThe bounds are likely to be tight when the set of constraints is dense, i.e. when there exists a subset of $\\\\Omega(\\\\sqrt{m})$ elements so that the samples are focused on these elements.\n\nFor k-NNs, the lower bounds are likely to be tight in many cases, unless the dataset has some degeneracy.\nIt is likely that the upper bounds for k-NNs are not tight, and the dependence on $k$ can be improved substantially.\n\nPlease let us know if our response addresses your concerns.", "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": "7k0eYXCtF5", "reviewer": "Reviewer_wQgD", "summary": "This paper discusses the number of compressed dimensions that satisfy the triplet or kNN constraints. In particular, theoretical results are derived for various distance measures as well as $L_2$.", "questions": "See te weaknesses section.", "limitations": "Not discussed.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper obtains intuitive and useful results. To this end, it introduces the concept of arboricity and obtains theoretical results.", "weaknesses": "Although this paper is a theory paper, I am strongly interested in whether the embedding is actually obtained. Let's say we have 1,000,000 vectors, where the dimensionality of each vector is 1,000. Our task is to preserve the top-500 ranking for each vector. Here, there are no encoders. We have vectors only. Can we practically set the valid $h$ beforehand (without knowing the final validated result)? To compute $F$, what computation do we really need? Is it fast or slow? The current experimental section does not contain the details of such a process.", "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": "sILNLjX5S6", "reviewer": "Reviewer_AWx5", "summary": "This paper establishes various asymptotic upper (and some lower) bounds on the dimensionality required so that there is an embedding satisfying various types of ordinal constraints on the pairwise distances. The constraints are either triplet constraints or k-nearest neighbor relations. The paper considers different $\\ell_p$ embedding spaces for both types of constraints and derives bounds for each of them. The authors conduct experiments on CIFAR 10 / 100 that support their theoretically established bounds.", "questions": "- *Q1:* I did not get the Chernoff bound arguments in line 236 and 240. Could you please elaborate?\n\n- *Q2:* My understanding of the proof of Lemma 18 is that an embedding is constructed whose entries are indexed by $[L]$ (line 257), so that the embedding is of dimension $O(L) = O(r\\log n)$ by Def 15. But the statement of Lemma 18 claims the square of this as embedding dimensionality. What do I miss?\n\n- *Q3:* I understand the reason for line 264,265 to be that $|U(C_{j(y)}(x)| = O(log(n))$ (load property) is larger than $J=O(r)$ (line 256 and Fact 6). But why is $log(n) > r$?\n\n- *Q4:* In line 270, we seem to need $J=r$ rather than only $J=O(r)$ (see Q3 and W5).\n\n- *Q5:* Which basis of the logarithm is chosen in the proof of Cor 19? Since nothing is specified, I assume that it is the natural logarithm or to base 10. But since $m'$ is a power of 2, it seems it should be base 2 to make $log(m')$ an integer. Please clarify.\n\n- *Q6:* I do not get the computation in the proof of Cor 19: $r \\sum_{i=1}^{\\log(m')} 2^i = r * (2^{\\log(m')+1} -2) = 2r(m'-1) \\neq rm'$.\n\n- *Q7:* Line 294 speaks of $R=\\Theta(k^2log(n))$ and $\\alpha = \\Theta(k^{-2})$. But since $p= O(k^{-1})$ (line 300), we have $\\gamma = (1-p)p/k= O(k^{-2})$, $\\alpha = O(k^{-3})$, and $R=O(k^3log(n))$. Should it perhaps be $\\gamma = (1-p)p$?\n\n- *Q8:* Please repeat what $w(x,y)$ means in line 317. \n\n- *Q9:* I am a bit confused by the term \"non-contradictory\" in line 59 and Fact 51. In the triplet setting the distance constraint is phrased as $\\leq$ not $<$, so the constant embedding always satisfies all constraints. Should these be strict inequalities?", "limitations": "Limitations are not explicitly discussed. Possible limitations might be the asymptotic nature of the statements (for which m, k, n do they start to hold)? What are the constants hidden in the big-O notation? Perhaps also the fact that many triplets are generated by sampling at least the negatives, which might let the total number of constraints considered in a real world contrastive learning setting be as high as $m=O(n^2)$, so that the bound $\\sqrt{m}=n$ becomes very high.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality\n- I am not aware of any other work that tackles the question of required minimal dimensionality for ordinal distance constraints. This is despite both contrastive learning and k-nearest neighbor graphs being popular tools in machine larning. This makes the contribution of the paper relevant. \n\nQuality\n- While the paper is very formal, I think its numerous and general findings will be useful for many parts of the machine learning community, especially representation learning.\n\nClarity:\n- The paper is very theoretical and most of it consists of proofs. This makes is a fairly challenging read. But overall, the authors do a very good job of providing high-level intuitive sketches of each proof before conducing it formally or select to showcase a weaker, but more intuitive version of a stronger statement proved in the appendix. This makes the writing clear.\n\nSoundness:\n- The proofs in the main paper seem sound to me, see questions below. I did not check the proofs in the appendix.", "weaknesses": "- *W1 Missing conclusion / future work section:* The paper ends abruptly after the experiments section. Please use some space to summarize your findings, point out potential limitations, and discuss how to develop this work further.\n\n- *W2 Exact $d=\\sqrt{m}$ in experiments:* The authors comment on the qualitatively different behavior if $d>\\sqrt{m}$ or $d\\leq \\sqrt{m}$ in Fig 3. But they choose powers of 10 for m and powers of 2 for d, so that none of the runs is exactly at $d=\\sqrt{m}$. It might make sense to choose the same base for both the exponential range of $m$ and that of $d$. Or to resolve the area around $d=\\sqrt{m}$ more fine grained. The corresponding bound only states $d=O(\\sqrt{m})$, which can include a constant. Why would one expect the behavior to change exactly at $d=\\sqrt{m}$?\n\n- *W3 Discussion of bounds for the approximate setting:* Table 1 and 2 do a great job at providing an overview of the results in the paper (and field). For context, it would be very useful to also state some bounds for an approximate version of the problem from related work, in which, e.g., only a share of $(1-\\alpha)m$ of the constraints needs to be statisfied, or all constraints need to be satisfied up to an additive margin of $\\alpha$. This relaxed setting should allow much lower dimensionalities. I am not sure if there are such results. If so, please discuss them. If not, this might go to the conclusion paragraph.\n\n\n**Minor:**\n- *W4 Description of contrastive learning:* Lines 34-37 seem to imply that all forms of contrastive learning operate on ordinal distance constraints of a fixed set of points. This is not quite true: For instance, in self-supervised constrastive learning the constraints are not over a fixed set but a potentially infinite set of all possible augmentations of all data samples. Moreover, triples of (anchor, positive and negative sample) are not always strictly understood as hard constraints on the distance. Since the negative sample is often chosen uniformly, it might even happen to be equal to the positive sample or the anchor (although only rarely). Often, the triplet is rather to be understood as the pair (anchor, positive) coming from some data distribution that is to be modeled and the pair (anchor, negative) coming from some noise distribution, see Gutmann and Hyvärinen (2010, 2012). This is not an issue for the paper at large, but does require some more rephrasing.\n\n- *W5 Consistency between using big-O notation and not:* In several places, e.g., line 58 and footnote 1 the use of big-O notation is not very consistent. Line 58 speaks of $m\\leq n^2$ while the accompanying footnote 1 only of $m = O(n^2)$, which does not preclude $m> n^2$ and only makes an asymptotic statement.\n\n- *W6 Resolution of Figure 3:* is too low, especially for inspecting the small performance gaps between many of the runs.\n\n- *W7 Experimental validation for the k-NN setting:* I appreciate that the paper is predominantly theoretical. But a brief experiment on the k-NN setting would be nice (and might only appear in the appendix). This could also serve as using an even more toy setting than the experiment in Fig 3: For instance, simply sample some random points, compute the k-NN graph and directly optimize the embedding in some embedding space to reproduce the same k-NN graph (instead of optimizing a parametric embedding as in Fig 3).\n\n- *W8 Line 185:* Since the uniformly random choice in line 185 is the reason for the linear independence in Lemma 11 it would be nice to briefly mention this (without giving the proof) to build intuition about the proof sketch further. \n\n**Typo:**\nLine 269: \"for any $[J]...$\" --> \"for any $j\\in [J]...$\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your thoughtful, detailed, and precise comments. Please see our reply below:\n\n### W1 Missing conclusion / future work section\n\nThanks, please see the global response above for a proposed conclusion / future work section.\n\n### W2 Exact $d=\\\\sqrt{m}$ in experiments\n\nThank you! We first would like to clarify that the behavior changes around $\\\\sqrt{m}$ per our theory, not exactly at $\\\\sqrt{m}$. We changed the text to avoid confusion.\n\nWe expanded experiments which accurately capture the regime around the $d=\\\\sqrt{m}$ threshold. In particular, we consider $m = c \\\\cdot d^2$ for $c=0.5, 0.75, 1, 1.5, 2, 2.5, 3$. The corresponding mean accuracies are $99\\\\%, 99\\\\%, 98\\\\%, 97\\\\%, 96\\\\%, 95\\\\%, 95\\\\%$.\n\n### W3 Discussion of bounds for the approximate setting\n\nThanks, we’ve added a discussion of the approximate setting, in which we give a full characterization of your suggested setting. It exhibits a surprising behavior: for $\\\\alpha \\\\ge 1/2$, one dimension always suffices, and for constant $\\\\alpha < 1/2$ it becomes as hard as the “exact” setting. We will be happy to outline it during the discussion period if you are interested.\n\n### W4 Description of contrastive learning\n\nThank you, we clarified that in the paper we consider one of the most common forms of contrastive learning.\n\n### W5: Consistency between using big-O notation and not\n\nThank you, we replaced $O(n^2)$ with $n^2$ in the footnote. Generally in this paper, we are interested in the asymptotic behavior.\n\n### W6: Resolution of Figure 3\n\nThank you, we added figures with higher resolutions.\n\n### W7: Experimental validation for the k-NN setting\n\nWe first would like to note that our construction for the upper bound for k-NN is theoretical - even for $k=1$ and mild $n$, the dimension significantly exceeds a trivial bound of $n$. In the general response, we show the experiments for k-NN using the setup similar to that from the paper, with the objective of reconstructing the original k-NN.\n\n### W8: Adding a line of intuition for linear independence\n\nThank you, we added the intuition that random perturbation is used to preserve independence.\n\n### Limitations\n\nThank you, we discuss the limitations in the conclusion (please refer to our general response).\n\n### Constants in O-notation\n\nFor $\\\\ell_2$ construction, the constants in O-notation are within a factor of 4. For the k-NN construction, the hidden constants are very large, which makes it mainly of theoretical interest. We specified in the conclusion that the k-NN construction can likely be improved.\n\n### Quadratic number of constraints\n\nIt’s indeed the case that the dimension might be as high as $\\\\Theta(n)$. But note that this is unavoidable in the worst case: using contrastive samples, one might recover full comparison information, and [CI24] show that, to preserve this information, $n/2$ dimensions are required in the worst case.\n\n## Technical Questions\n\n> Q1. Chernoff bound in 236 and 240\n\nIn 240, we have $L$ independent indicator random variables $A^j(x,y)$, each occurring w.p. $\\\\Omega(1/r)$. Denote $X = \\\\sum_j A^j(x,y)$. The expectation $E[X]$ is at least $E[X] = \\\\sum_j E[A^j(x,y)] = \\\\Omega(\\\\log{n})$. (since $L = \\\\Theta(r\\\\log{n})$).\nBy Chernoff,\n$Pr[|X - E[X]| \\\\geq E[X]/2] < 2e^{-E[X]/12}$.\nIn particular, $Pr[X = 0] < 2e^{-E[X]/12}$. Taking $L$ to be with sufficiently large constant, we get $Pr[X = 0] < 1/poly(n)$.\n\nIn 236, Fix $x$. For $N^-(x) = \\\\{y_1,...,y_{O(r)}\\\\}$ we define $O(r)$ independent indicator variables $X_1,...,X_{O(r)}$, where $X_i = 1$ if $y_i$ and $x$ have the same color, and $X_i = 0$ otherwise. Denote $X = \\\\sum_i X_i$. Notice that $E[X] = O(1)$. By Chernoff, $Pr[X > c\\\\log{n}] \\\\leq Pr[X > (1+(c/E[X])\\\\log{n})E[X]] <  e^{-(c\\\\log{n}/2)} < 1/poly(n)$ (here $c$ is the constant of the load). Therefore, it holds for all $x$ w.h.p. by union bound.\n\n> Q2. Embedding dimension in Lemma 18\n\nIn the NCC embedding, we have $L = \\\\Theta(r \\\\log{n})$ blocks, where each block is a standard unit vector of dimension $\\\\Theta(r\\\\log{n})$. Intuitively, the reason each unit vector is taken from this dimension is that we need $\\\\Theta(r\\\\log{n})$ distinct standard unit vectors.\n\n> Q3.\n> Do you require $|U(C_{j(y)}(x))| > J$?\n\nThe only thing we require in those lines is that $|U(C_{j(y)}(x))| > 1$, because we only need to pick some vector distinct from that of $y$ (and since $j(y) \\\\in J$, we are guaranteed all other backwards neighbors choose a different vector for this block). \n\n> Q4,Q6,Q7.\n> In line 270, we seem to need $J=r$ rather than only $J=O(r)$. In Cor 19: $\\\\sum_{i=1}^{\\\\log{m'}} 2^i = 2(m'-1)$ and not $m'$. In Line 294, $\\\\gamma$ should be $\\\\gamma = (1-p)p$.\n\nThank you for pointing out these issues. These are typos arised due to refactoring the proofs. We fixed them, which did not affect correctness or the final result.\n* Q4: In Lem 18, the exact distance should be $L - 1$ or $L$ (not $r-1$ or $r$ as written) - each $i \\\\in [L] \\\\setminus \\\\{j(y)\\\\}$ contributes $1$ to the distance (see lines 257-262 and 263-265).\n* Q6: we fixed the sum.\n* Q7: $\\\\gamma$ should be indeed $\\\\gamma = p(1-p)$. We also changed $\\\\gamma$ to $\\\\gamma/k$ in a few expressions due to this typo. This doesn't affect dependence on $k$ in the final bound.\n\nQ4, Q6, Q7 are now fixed.\n\n> Q5. Basis of the log in Cor 19\n\nBy $\\\\log m'$ we denote the binary logarithm of $m'$ (i.e. $\\\\log_2$).\nWe added the base of the logarithm in this place in all equations.\n\n> Q8. Repeating what $w(x,y)$ means in line 317\n\nWe added a clarification that “$w(x,y)$ is the ranking of edge $\\\\{x, y\\\\}$ if the edges are sorted by the decreasing order of distances”\n\n> Q9. Should inequalities in line 59 and fact 51 be strict?\n\nThank you! The inequalities between distances in the paper are strict. $\\\\le$ is a typo, which we fixed.\n\nPlease let us know whether we addressed your concerns, and thank you again for your comprehensive review!", "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:
## Additional Figures

Based on the reviews, we decided to add figures to clarify the proofs. Please see the attached PDF.

## Conclusion

As suggested by the reviewers, we will use the extra space of the final version to include the following discussion of the future work and to reiterate our findings:

> In this paper, we provide bounds on the necessary and sufficient dimension to represent a collection of contrastive constraints of the form “distance $(a,b)$ is smaller than distance $(a,c)$". This is a fundamental question in machine learning theory. In particular, it helps educate the choice of deep learning architectures by providing guidance for the size of the embedding layer. Our experiments illustrate the predictive power of our theoretical findings in the context of deep learning. We also believe that it gives rise to many interesting directions for future work depending on the exact desiderata (e.g. approximate versions, different choices of normed spaces, bicriteria algorithms, agnostic settings, etc.). 

> While the distance comparison settings we consider play a central role in contrastive learning and nearest neighbor search, so far there has been no theoretical studies of their embedding dimension. Our work is the first to present a series of such upper and lower bounds in a variety of settings via a novel connection to the notion of arboricity from graph theory. As a follow-up, one can consider an improved embedding construction for k-NN: while the upped bound from Section 3 shows that dependence on $n$ is at most poly-logarithmic, the dependence on k can likely can be improved. Another interesting direction is tighter data-dependent bounds on dimension: while we provide fine-grained bounds in terms of arboricity - which are potentially much stronger than bounds in terms of the number of edges - they don’t necessary captures properties of dataset which can lead to sharper bounds.

## Additional Experiments

In this section, we present the experiments based on the reviewers' suggestions.  Please note that due to tight time constraints, the scale of the experiments below is limited. We will expand on these experiments in the camera-ready submissions.

### Our construction for $\\ell_2$-embeddings

In the table below, we show the dimension achieved by our construction from Section 2.
We consider these ranges of $n$ and $m$, since it allows $m$ to span from $m < n$ to $m > n^2$.

| | $m=10^2$ | $m=10^3$ | m=$10^4$ | m=$10^5$ | m=$10^6$ | m=$10^7$|
|---|---|---|---|---|---|---|
|$n=128$| 8 | 34 | 169 | 256 | 256 | 256 |
|$n=256$| 6 | 19 | 137 | 452 | 512 | 512 |
|$n=512$| 4 | 12 | 81 | 501 | 1024 | 1024 |
|$n=1024$| 4 | 8 | 43 | 362 | 1457 | 2048 |
|$n=2048$| 4 | 6 | 24 | 203 | 1488 | 3956 |

### Experiments for k-NNs

In the next table, we present results for k-NNs for $d=128$ and for various choices of $n$ and $k$.
We generate the k-NN using a ground-truth embeddings $e^*$.
For each element $u$, let $v_1^{(u)}(e^*), ..., v_{n-1}^{(u)}(e^*)$ be other elements, sorted by their distance to $u$ according to $e^*$.
For each $i \\in [k]$ and $j > i$, we generate contrastive samples $(u, v_i^{(u)}(e^*)^+, v_j^{(u)}(e^*)^-)$, and we train the neural network on this set of samples similarly to Section 4.
We denote the trained embeddings as $e$.

For each $n$ and $k$, we report the "accuracy" of preserving the k-NNs.
For each vertex $u \\in V$ and $i \\in [k]$, we compute the change of rank of the $i$'th neighbor w.r.t. $u$ in the new embeddings.
Formally, we find $j$ such that $v_{j}^{(u)}(e) = v_{i}^{(u)}(e^*)$, which contributes the loss $|i - j|$.
Finally, we define the accuracy as the average loss over all $u \\in V$  and $i \\in [k]$.

||k=1|k=2|k=4|k=8|k=16|k=32|
|---|---|---|---|---|---|---|
|n=10| 0.2 | 0 | 0.175 | 0.55 | - |-|
|n=100| 0.04 | 0.17 | 0.285 | 0.78 | 1.376 |2.316|
|n=1000| 0.007 | 0.367 | 0.882 | 1.5 | 2.2983|3.336|

The table shows that, as our theory predicts, dependence on $n$ is minor.

### Other experiments

1. We expanded experiments from Figure 3b) to accurately capture the regime around the $d=\\sqrt{m}$ threshold.
In particular, we consider $m = c \\cdot d^2$ for $c=0.5, 0.75, 1, 1.5, 2, 2.5, 3$.
The corresponding mean accuracies are $99\\%, 99\\%, 98\\%, 97\\%, 96\\%, 95\\%, 95\\%$.

2. We performed experiments similar to that from Figure 3b) on the Large Language Models tasks. We sampled $n=1000$ reviews from the Amazon sentiment dataset.
We get ground-truth embeddings using `paraphrase-MiniLM-L6-v2` model and train `stsb-roberta-base` model similarly to the settings from Figure 3.
We fix $d=128$ and consider $m = 10^3, 10^4, 10^5, 10^6$. The corresponding accuracies are $100\\%, 100\\%, 85\\%, 85\\%$, again showing the accuracy drop after $m$ significantly exceeds $d^2$.

Meta-review: All reviewers support the acceptance of the paper with one reviewer especially enthusiastic.

Pros:

- study the important topic of embedding dimensions with relevant motivating applications of contrastive learning and k-nearest neighbor.

- comprehensive set of results for different norms (l2, l_p, l_infinity) and both upper and lower bounds

Cons:

- the experiments concerning the k-NN setting are lacking
Decision: Accept (poster)