Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors

Authors: dmitrii  avdiukhin
vaggos  chatziafratis
orr  fischer
grigory  yaroslavtsev
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 18:43:14

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$.

Main paper: 
 introduction: 
 Embedding vectors play an important role in machine learning, with the embedding dimension being a key parameter of interest when choosing a deep learning architecture. In 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 k-NN.Contrastive Learning Contrastive learning [GH10] has recently become a popular technique for learning representations, see e.g. [SE05, MCCD13, DSRB14, SKP15a, WG15, WXYL18, LL18, HFL + 19, HFW + 20, TKI20, CKNH20, CH21, GYC21, CLL21]. Recent interest in theoretical foundations of contrastive learning has resulted in extensive research focusing on generalization [AAE + 24], design of specific loss functions [HWGM21] , transfer learning [SPA + 19, CRL + 20], multi-view redundancy [TKH21] , inductive biases [SAG + 22, HM23], the role of negative samples [AGKM22, ADK22] , mutual information [vdOLV18, HFL + 19, BHB19, TDR + 20], and other topics [WI20, TWSM21, ZSS + 21, vKSG + 21, MMW + 21, WL21].In on of the most common forms of contrastive learning, we are given m labeled data points {(x i , y + i , z - i )} m i=1 (or more generally, {(x i , y + i , z - i,1 , z - i,2 , . . . , z - i,t )} m i=1 ) over a dataset of size n. Each point represents the fact that the distance between the anchor x i and the positive example y i is smaller than the distance between x i and the negative example z i (or, more generally, t negative examples z i,1 , . . . , z i,t ). We study the problem of embedding such data into ℓ p -spaces, i.e., constructing an embedding F : V → R d such that ∥F (x i ) -F (y i )∥ p < ∥F (x i ) -F (z i )∥ p for all i (more generally, ∥F (x i ) -F (y i )∥ p < ∥F (x i ) -F (z i,j )∥ p for all i, j). In particular, we focus on the embedding dimension:Given a collection of m triplet comparisons of the form "x i is closer to y i than to z i ", what is the smallest dimension d of an ℓ p -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, we are given a set of n items and the information about the k-NN of each item {(x i , π 1 (x i ), . . . , π k (x i ))} n i=1 where π 1 (x i ), . . . , π k (x i ) are the k-NN of x i ordered by their distance from x i . Since k-NN classifiers are extremely popular in deep learning pipelines, understanding the embedding dimension required for preserving k-NN is a question of fundamental importance. In particular:Given n items and their k-NN, what is the smallest dimension d of an ℓ p -space in which the ordering of the k-NN can be preserved? What if the k-NN have to remain k-NN in the ℓ p -space?Let V be the set of n points. Our goal is to construct an embedding F : V → R d . For an integer n, we let [n] = {1, 2, . . . , n}. For a vector v ∈ R d , let v[i] be the i th coordinate of v. For vectors v 1 , v 2 , we denote their concatenation as (v 1 , v 2 ). In a graph, denote by N (x) the neighbors of vertex x. For standard definitions (e.g. metric and norm) and basic facts see Appendix B.Contrastive Learning For a set of samples Q = {(x 1 , y + 1 , z - 1 ), . . . , (x m , y + m , z - m )}, we call an embedding F consistent with Q if ∥F (x i ) -F (y i )∥ p < ∥F (x i ) -F (z i )∥ p for all i. W.l.o.g., we can assume1 that m ≤ n2 . We call a set of samples non-contradictory if one can't derive a contradiction from the inequalities between the distances. In particular, this implies the existence of a metric ρ 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 ℓ 2 ). Let Q be a set of m non-contradictory triplet samples on a set V . There is an embedding of V into ℓ 2 -space R O(m 1/2 ) which is consistent with Q. Theorem 2 (Embedding in ℓ ∞ ). Let Q be a set of m non-contradictory triplet samples on a set V . There is an embedding of V into ℓ ∞ -space R O(m 2/3 ) which is consistent with Q. Theorem 3 (Embedding in ℓ p ). Let Q be a set of m non-contradictory triplet samples on a set V . For any integer p ≥ 1, there is an embedding of V into ℓ p -space R O(m) which is consistent with Q.The lower bounds are shown in Appendix E and experimental results are in Section 4. Our results for the more general version of the problem with t negatives and the lower bounds are given in Table 1 .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 set of contrastive constraints, and results for an approximate setting in which we only need to satisfy a fraction of the constraints. -Ω(k), Theorem 43 k-NN In the k-NN setting, we are given the following information for each data point. Definition 4 (k-NN). For a distance function δ : V × V → R ≥0 , let π 1 (x), . . . , π n-1 (x) be an ordering of V \ {x} such that δ(x, π 1 (x)) < δ(x, π 2 (x)) < • • • < δ(x, π n-1 (x)). We define k-NN δ (x) = (π 1 (x), . . . , π k (x)) as the ordered set of k closest points to x.For a function F : V → R d , we denote by k-NN F the k-nearest neighbors in the ℓ p -space corresponding to the image of F . We prove the following theorem in Section 3. Theorem 5. Let δ : V × V → R ≥0 be a distance function, and let p ≥ 1 be a constant. There exists an embedding F : V → R d of V into an ℓ p -space of dimension d = O(k 10 log 10 n) such that k-NN δ (x) = k-NN F (x), i.e. the embedding F preserves the ordered set of k-nearest neighbors of any point x ∈ V under the distance function δ. 2We note that the above result is very surprising: k-NN graph in 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 1 provides only an O(n) upper bound on dimension for the ℓ 2 case. Nevertheless, we are able to exploit the structure of the 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 2 . Theorem 6. There is an embedding of V into ℓ 2 -space R O(k) that preserves the k-NN ordering.The key tool in our results is the notion of graph arboricity [NW61, NW64] applied to the associated constraint graph. Arboricity of an undirected graph is the minimum number of forests in which its edges can be partitioned. More intuitively, arboricity measures the "density" of the graph: sparse graphs have low arboricity, while graphs with dense subgraphs -such as cliques -have high arboricity. (a) There is an orderingx 1 , . . . , x n of V such that |N -(x i )| ≤ 2r -1 for each 1 ≤ i ≤ n, where N -(x i ) = {x j ∈ N (x i ) | j < i} is the set of neighbors of x i in G preceding x i 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, E) as follows: for each sample (x i , y + i , z - i ) ∈ Q, we add two edges {x i , y j } and {x i , z i } to E, unless they already exist. In the k-NN setting, for each x and its nearest neighbors π 1 (x), . . . , π k (x), we add edges {x, π i (x)} for 1 ≤ i ≤ k.Note that by Fact 7 the arboricity of the constraint graph resulting from m samples is at most √ m. The arboricity of the k-NN constraint graph is at most k + 1 (See Lemma 27). We show bounds on the embedding dimension in terms of arboricity, e.g. for ℓ 2 we prove the following in Section 2. Theorem 9. Given a set of non-contradictory inequalities among pairwise distances in V whose constraint graph has arboricity r, there exists an embedding of V into ℓ 2 -space R 4r which satisfies all these inequalities.Theorem 1 follows from Theorem 9 by using r ≤ ⌈ √ m/2⌉ (Fact 7). Moreover, since the arboricity of the constraint graph for k-NN at most k + 1 (Lemma 27), Theorem 9 shows that preserving the ordering of the k-NN in ℓ 2 requires O(k) dimension. Furthermore, the following theorem, proven in Section 3.1, implies that Õ(k 2 ) dimension suffices to preserve orderings of the k-NNs in ℓ p . Theorem 10. Given a set of non-contradictory inequalities among pairwise distances in V whose constraint graph has arboricity r, for any real p ≥ 1, there exists an embedding of V into ℓ p -space R O(r 2 log 3 n) which satisfies all these inequalities.While the above constructions suffice for the contrastive learning case and for preserving the ordering 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 a 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 ℓ ∞ , instead of arboricity, we use a related fact: by removing a set V high of O(m 2/3 ) high-degree vertices, we reduce the maximum degree of the remaining graph (i.e. V low = V \ V high ) to at most O(m 1/3 ). We handle each set differently (points in V low using graph colorings, and points in V high using a Frechét-like embedding). See Appendix D.2 for the details and the proof of Theorem 2.Understanding the underlying geometry of a given set of n points based only on comparisons between pairs of distances is a 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 [Tor52, She62, She74, CS74, Kru64a, Kru64b], and since then ordinal information and embeddings have been used in ranking [OG08, Ail12, WJJ13] , metric learning [CHX + 19], clustering [VD16, GPvL19, KVH16] , crowdsourcing [TLB + 11, JN11a, JN11b] and modeling human perception [ML09] . Note that the goal in ordinal embeddings is quite different from the vast literature on metric embeddings (e.g., see [Mat13, IMS17] ) 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 n points such that a 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 n regime, upon knowledge of the ordinal relationships, the set of points can be approximately recovered (up to certain transformations). This serves as further motivation for studying ordinal information 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 elusive. Most papers assume that all Θ(n 4 ) distance comparisons δ(x i , x j ) ≶ δ(x k , x l ) among the pairwise distances are known. In [BL05, ABD + 08, BDH + 08], for example, lower bounds are given for the dimension needed to preserve these comparisons. However, having access to such a 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.Contrastive learning has been studied for d = 1 (embedding on the line) by [FIM + 20] for dense instances, i.e. m = Θ(n 3 ). For higher dimensions, [CI24] gives an Ω (n) lower bound on the smallest dimension (only for ℓ 2 ) that preserves all Θ(n 3 ) triplet comparisons. Our Theorem 1 improves this bound for the general case when m triplet samples are given, without density assumptions. Then, x x x sets inner products according to edge ranksx makes norms of all vectors equal Figure 1: x is chosen so that if w(x, y) > w(x ′ , y ′ ), then ⟨x, ŷ⟩ < ⟨x ′ , ŷ′ ⟩. x ensures that all vectors have the same norm, i.e. ∥x∥ 2 2 = W for all x ∈ V .x 1 x 2 x 3 x 4 x 5 x 6 ⟨x 1 , x4 ⟩ = w(x 1 , x4 ) ⟨x 2 , x4 ⟩ = w(x 2 , x4 ) ⟨x 3 , x4 ⟩ = w(x 3 , x4 ) Figure 2: Example construction of x.The embedding x4 is computed based on the embeddings of its already processed neighbors x1 , x2 , x3 . We find the solution x4 to the linear system so that, for each edge to a preceding neighbor, the inner product equals the rank of the edge.our Theorems 2 and 3 go beyond ℓ 2 other ℓ p -norms. Our results can also be seen as the reverse direction of the recent work by [AAE + 24]. In [AAE + 24], the central question is quantifying the amount of data required for generalization in contrastive learning, assuming that the data can be embedded into an ℓ p -space of fixed dimension. Here we assume that the data is fixed instead and study the embedding dimension. Combined with [AAE + 24], this completes the picture of the relationship between the size of data, its embedding dimension and generalization.Our second setting (k-NNs) was also studied in [CI24] who showed a lower bound of d = Ω(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 ℓ p 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.There exists a set of non-contradictory triplet samples Q of size |Q| = m for which any embedding in ℓ p space consistent with Q must have d = Ω( √ m). 
contrastive learning in ℓ norm: 
 In this section, we prove Theorem 9 -that contrastive queries with the constraint graph G = (V, E) (Definition 8) of arboricity r are preserved when the points are embedded into ℓ 2 space of dimension 4r -from which Theorem 1 and Theorem 6 follow. Fix a distance function δ : V × V → R ≥0 that satisfies the given set of inequalities (such a function exists by Fact 25). We order all pairs of neighboring vertices by the distance function δ in descending order, and let w(x, y) = i if {x, y} is the i-th pair in the ranking. Recall that ∥F (x) -F (y)∥ 2 = ∥F (x)∥ 2 + ∥F (y)∥ 2 -2 ⟨F (x), 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 → R 4r into two parts, i.e. for a point x let F (x) = (x, x), where x ∈ R 2r and x ∈ R 2r . For neighboring points x and y, our choices of x and ŷ ensure that ⟨x, ŷ⟩ ≈ w(x, y). We embed the points one by one into R h in the arboricity ordering x 1 , . . . , x n , which by Fact 7 ensures that for every vertex, the number of neighbors with smaller indices is at most h. When embedding x i , we make sure that for any neighbor x j ∈ N -(x i ) (i.e. a neighbor x j of x i such that j < i) it holds that ⟨x i , xj ⟩ ≈ w(x i , x j ). This requires solving a linear system over xi with at most h equations, and hence with h variables, with slight perturbations, the solution always exists.The choices of xi 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 h colors using Fact 7 and assigning each color to a unique basis vector, which is scaled to equalize the norms. Since these basis vectors are orthogonal, the inner product between any two neighboring points x i and x j is ⟨x i , xj ⟩.Construction of xi Assume x1 , . . . , xi-1 have already been chosen. Let N -(x i ) = {x j ∈ N (x i ) | j < i} be the set of preceding neighbors of x i in G. For each x j ∈ N -(x i ), let a linear equation P (i, j) be ⟨x i , xj ⟩ = w(x i , x j ), where we consider the coordinates of xi as variables (recall that xj is already set for all x j ∈ N -(x i )). In Appendix C we show the following. Lemma 11. The set of vectors {x j | x j ∈ N -(x i )} is linearly independent.By Lemma 11, the system of linear equations P i = {P (i, j) | x j ∈ N -(x i )} has a solution v ∈ R 2r . Let B(v) be a ball centered at v with sufficiently small radius such that for any v ′ ∈ B(v) it holds that | ⟨v ′ , xj ⟩ -w(x i , x j )| < 1/3 for all x j ∈ N -(x i ). Choose a point v ′ uniformly at random from B(v), and set xi = v ′ : this random perturbation guarantees that, with probability 1, Lemma 11 holds in future iterations. By construction, the following property holds. Proposition 12. For any x and any y ∈ N -(x), we have | ⟨x, ŷ⟩ -w(x, y)| < 1/3. Construction of xi Let W = 2 max x∈V ∥x∥ 2 2 . By Fact 7, there exists vertex coloringC : V → [h] of G, such that C(x) ̸ = C(y) for any pair {x, y} ∈ E. Set x = α x e C(x), where e C(x) is the standard basis vector in the C(x)-th coordinate, and α x is chosen so that ∥F (x)∥ 2 2 = ∥x∥ 2 2 + ∥x∥ 2 2 = W (note that α x exists because ∥x∥ 2 2 ≤ W ). By construction, the following property holds. Proposition 13. For any edge {x, y} ∈ E, we have ⟨x, ẙ⟩ = 0.Proof of Theorem 9 (sufficient dimension for ℓ 2 embeddings). For any edge {u, v} ∈ E it holds that∥F (u) -F (v)∥ 2 2 = ∥F (u)∥ 2 2 + ∥F (v)∥ 2 2 -2 ⟨û, v⟩ -2 ⟨ů,v⟩. By the choice of ů and v, we have ∥F (u)∥ 2 2 = ∥F (v)∥ 2 2 = W . By Proposition 13, ⟨ů,v⟩ = 0, and hence the distance depends only on ⟨û, v⟩. For any (x, y+ , z -) ∈ Q, we have ∥F (x) -F (y)∥ 2 2 < ∥F (x) -F (z)∥ 22 iff ⟨x, ŷ⟩ > ⟨x, ẑ⟩. By Proposition 12, for any edge {x, y} in G it holds that | ⟨x, ŷ⟩ -w(x, y)| < 1/3. Since the function w assigns only integer values, it holds that ⟨x, ŷ⟩ > ⟨x, ẑ⟩ if and only if w(x, y) < w(x, z), hence preserving the ranking of the edges.There exists a set of non-contradictory t-negatives samples Q of size |Q| = m such that any embedding in ℓ p space in d dimensions requires d = Ω( √ m). 
preserving k nearest neighbors: 
 In this section, we focus on k nearest neighbors, and namely we prove Theorems 5 and 10. Let G = (V, E) be the constraint graph (Definition 8) 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.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 c should be replaced with c 1/p . In this section, let δ(u, v) = δ ℓ1 (u, v). For a non-contradictory set of samples Q, by Fact 25 there exists a metric δ ′ consistent with Q. We order all pairs of neighboring vertices by the value of δ ′ in descending order, and let w(x, y) = t if (x, y) is the t-th pair in the ranking. Given an embedding F , let αF be a re-scaling of the embedding by a factor of α, i.e. multiplying each coordinate by α.In this section, we 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-Collection Coloring. Let x 1 , . . . , x n be the arboricity ordering (Fact 7) and N -(x i ) = {x j | {x i , x j } ∈ E, j < i} be the set of neighbors of x i preceding x i in the ordering. Definition 14 (NCC Scheme). A neighbor-collection coloring scheme is a set of K = Θ(r log n) vertex colorings C (1) , . . . , C (K) , where C (j)x ∈ [r] for any x ∈ V and j ∈ [K], such that for any x ∈ V the following holds:• (Collection) for any y ∈ N -(x), there exists a coloring j ∈ [K] such that C (j) x = C (j)y , andC (j) z ̸ = C (j)x for any z ∈ N -(x) \ {y}.• (Load) for any j ∈ [K], the number of prior neighbors with j-th color being the same as C j)x is small:|{y ∈ N -(x) | C (j) x = C (j) y }| = O(log n).Intuitively, each coloring corresponds to a part of the embedding. When the colors C (j)x , C (j) y are different, the j'th part of the embedding always contributes 2 to 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 ∈ N -(x) such a part exists. The load property guarantees that for each part we always have enough choices to get distance 2. Finally, we represent w(x, y) in binary format for all x, y, and, using an NCC scheme, we recover w(x, y) bit-by-bit.Lemma 15. There exists an NCC scheme for the constraint graph G.Proof. For each x ∈ V and j ∈ [K], we choose C (j)x i.i.d. uniformly at random from [r]. First, note that the load property holds: for any j ∈ [K] and y ∈ N -(x), we have P C x occurs no more than O(log n) times in N -(x) w.h.p. By the union bound, the load property holds w.h.p. for all j.Next, for any fixed x ∈ V , y ∈ N -(x), and j ∈ [K], let A (j) (x, y) be the event that y is the only point inN -(x) such that C (j) x = C (j)y . Since the colorings are selected uniformly at random, we have P A (j) (x, y) = Ω(1/r). Since K = O(r log n), by Chernoff, w.h.p. there exists j ∈ [K] such that A (j) (x, y) occurs. By the union bound, the collection property holds w.h.p.Definition 16 (NCC-Embedding). Given a graph G and an NCC scheme, an NCC-embedding is an embedding of dimension O(r 2 log 2 n) of the following form. Associate each color i ∈ [r] with M = O(log n) unique basis vectors B(i) = {e (i-1)M +1 , e (i-1)M +2 , . . . , e iM }. The embedding of point x is comprised of K parts x(1) , . . . , x(K) , where each part is a basis vector x(j) ∈ B(C(j)x ), i.e. x(j) is one of the basis vectors associated with color C (j)x . Lemma 17. Let D : E → {0, 1} be a mapping of each edge, with 1 meaning "close" and 0 meaning "far". For each x ∈ V there exists embedding x into O(r 2 log 2 n) dimensions such that for any {x, y} ∈ E, it holds that δ(x, ẙ) = K -D(x, y).Proof. Let (C (1) , . . . , C (K) ) be an NCC scheme of G. We embed the points one by one according to the arboricity ordering x 1 , . . . , x n as in Fact 7. We assume by induction that all nodes x 1 , . . . , x i-1 are embedded using an NCC-embedding. For each y ∈ N -(x), fix one index j(y) such that under C (j(y)) the points x, y have the same color, which is different from colors of other points from N -(x) (such j(y) exists by the collection property). Let J = {j(y) | y ∈ N -(x)}, and, since for any two points inN -(x) the chosen index is distinct, |J| = |N -(x)|.For each part j ∈ [K]\[J], we choose x (j) to be a basis vector from B(C(j)x ) that is different from all basis vectors {ẙ (j) | y ∈ N -(x)}. This can be done, since, on the one hand, for each C (j)x ̸ = C (j)y , all basis vectors of B(C(j)x ) are different from ẙ(j) , and, on the other hand, by the load property there are less thanO(log n) points y ∈ N -(x) such that C (j) x = C (j)y . Therefore, we can choose a basis vector that is different from any taken by these O(log n) points.For each part j(y) ∈ [J], we select the basis vector based on D. If D(x, y) = 1, then we take x(j(y)) = ẙ(j(y)) . Otherwise, we pick a basis vector x(j(y)) ∈ B(C(j(y)) x) such that x(j(y)) ̸ = ẙ(j(y)) .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 {x, y} ∈ E such that y ∈ N -(x). Let I (j) (x, y) = 1 if x(j) ̸ = ẙ(j) , and I (j) (x, y) = 0 otherwise. Since each part is a basis vector, δ(x, ẙ) = 2 j∈[K] I (j) (x, y). By construction, for any j ∈ [J]\{j(y)} it holds that I (j) (x, y) = 1. For j(y) we have I (j(y)) (x, y) = 1 -D(x, y), i.e. δ(x, ẙ) = 2(K -D(x, y)). Rescaling the embedding vectors by a factor of 1/2 completes the proof.Corollary 18. Let a ′ be a power of 2 such that for all {x, y} ∈ E we have a x,y ∈ {0, . . . , a ′ }. Then there exists an embedding F of V into O(r 2 log 2 n log a ′ ) dimensions such that for any {x, y} ∈ E, we have δ(F (x), F (y)) = K(a ′ -1) -a x,y . Proof. Let Bin (i) (x, y) be the i'th bit of the binary encoding of a x,y using a string of size log 2 a ′ bits. Let F 1 , . . . , F log 2 a ′ be embeddings as in Lemma 17, where for each F i we chooseD i = Bin (i) (x, y). For embedding F (x) = (F 1 (x), 2F 2 (x), . . . , 2 i F i (x), . . . , (a ′ /2)F log 2 a ′ (x)) we have δ(F (x), F (y)) = log 2 a ′ i=1 K -Bin (i) (x, y) • 2 i-1 = K log 2 a ′ i=1 2 i-1 - log 2 a ′ i=1 Bin (i) (x, y) • 2 i-1 = K(a ′ -1) -a x,y .Theorem 10 follows immediately from Corollary 18 by taking a x,y = w(x, y) and a ′ ≥ m ′ .In this section, we prove Theorem 5, which states the existence of an embedding with dimension d = O(k 10 log 10 n) that preserves the k-NN. Our approach can be summarized as follows: for each x ∈ V , the final embedding is F (x) = (2mx, x) (Figure 3 ). The goal of x is to have all nonneighbors {x ′ , y ′ } /∈ E be at a larger distance than any neighbors {x, y} ∈ E, i.e. for some large W it holds that δ(x, ŷ) + W < δ(x ′ , ŷ′ ). The goal of x is to order the distances of neighboring pairs {x, y} ∈ E according to their rank, while still keeping non-neighbors further away than neighbors.We choose x(j) via a random process, so that for any two neighbors {x, y} ∈ E we have x(j) = ŷ(j) with some probability p 1 (and otherwise they have substantial distance), while for non-neighbors {x, y} / ∈ E, we have x(j) = ŷ(j) with much smaller probability p 2 ≪ p 1 . Repeating this process, we get a separation in distances between neighbors and non-neighbors.x xx guarantees that non-neighbors in G are far x preserves the order between the edges Figure 3 : Structure of embedding for fully preserving k-NN. x guarantees that non-edges have very large distance, i.e. if {x, y} ∈ E and {x ′ , y ′ } / ∈ E, then δ(x, ŷ) ≪ δ(x ′ , ŷ′ ). x orders the edges.Choosing x: The embedding x is comprised of L = Θ(r 4 log 4 n) parts, i.e. x = (x (1) , . . . , x(L) ).We take each part x(j) to be a vector from a design [DKS12] -a large family of vectors which are approximately equidistant. Definition 19 ((α, R)-design). For integer R and value 0 < α < 1, an (α, R)-design is a family of sets T , such that (a) for eachS i ∈ T , S i ⊆ [R 2 ], (b) for each S i ∈ T , |S i | = R, and (c) for each two distinct sets S i , S j ∈ T , |S i ∩ S j | ≤ αR.Lemma 20 (Lemma 1, [DKS12] ). For any sufficiently large integer R and any value 0 < α < 1, there exists an (α, R)-design T of size at least 2 αR log 2 R .Let T be a (α, R)-design for R = Θ(r 3 log 3 n) and α = Θ(log n/R), where r is arboricity of the constraint graph (constants specified below). We associate S ∈ T with a binary vector I(S) ∈ {0, 1} R 2 as an indicator vector of the set S, i.e. for i∈ [R 2 ] we have I(S)[i] = 1 iff i ∈ S.For each x ∈ V , we choose unique sets S x , S ′x ∈ T and denoteI x = I(S x ), I ′ x = I(S ′ x ). By Lemma 20, the number of sets is 2 αR log 2 R = 2 Ω(log n) , exceeding 2n for appropriate choices of constants.We choose each part x(j) independently of the rest as follows. For p = O(1/(r log n)), with probability 1 -p, we choose x(j) = I x , and otherwise choose a uniformly random i ∈[2r]. If i ≤ |N -(x)|, set x(j) = I y , where y ∈ N -(x) is the i'th point in N -(x)according to some ordering, and set x(j) = I ′x otherwise. Let γ = (1-p)p 2r be the probability that x and y choose I y .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 between embedding, while sampling different vectors contributes at least (2 -α)R to the distance. For K is defined as in Definition 14, let c = max( r log n 100K , 1 100 ) be a constant, and set α ≤ cγ 8r log 2 n and R = ⌈log 2 n/α⌉. In Appendix C.1 we justify these choices of parameters and show the following.Lemma 21. With high probability, the following bounds hold.• If {x, y} / ∈ E, then |δ(x, ŷ) -2RL| ≤ c r log 2 n γRL • If {x, y} ∈ E, then |δ(x, ŷ) -2(1 -γ)RL| ≤ c r log 2 n γRL.That is, according to the embedding, the gap between neighbors' distances and non-neighbor' distances is larger than the maximum difference between neighbors' distances.The final dimension is O(r 10 log 10 n): L = Θ(r 4 log 4 n) parts of dimension R 2 = Θ(r 6 log 6 n). Since r = O(k) (Lemma 27), it follows that the dimension is bounded by O(k 10 log 10 n).Final Embedding Let x1 , . . . , xn be the embeddings from Corollary 18 with a ′ being the closest power of two from above of the expression 5mcγ r log n RL. These embeddings have di-mension at most O(r 2 log 2 n log a ′ ) = O(r 2 log 3 n). For {x, y} ∈ E, let ∆(x, y) = 2m δ(x, ŷ) -2 1 -γ -γ100 RL . Set a x,y = ∆(x, y)+w(x, y), where w(x, y) is the ranking of edge {x, y} if the edges are sorted by the decreasing order of distances. By Lemma 21, we have 0 ≤ ∆(x, y) ≤ 4mcγ r log n RL w.h.p., and hence a x,y ≤ 4mcγr log n RL + m ≤ a ′ . Finally, F (x) = (2mx, x).Proof of Theorem 5. For each x ∈ V , let F (x) = (2mx, x). It suffices to show the following.(a) For any {x, y} ∈ E and {x ′ , y ′ } ∈ E, it holds that w(x, y) < w(x ′ , y ′ ) if and only ifδ(F (x), F (y)) > δ(F (x ′ ), F (y ′ )). (b) For any {x, y} ∈ E and {x ′ , y ′ } / ∈ E, it holds that δ(F (x), F (y)) < δ(F (x ′ ), F (y ′ )).By Corollary 18, for any {x, y} ∈ E:EQUATIONwhere ε x,y ∈ [0, 1) is the rounding error. Hence, property (a) holds: if w(x, y) < w(x ′ , y ′ ) then δ(F (x), F (y)) > δ(F (x ′ ), F (y ′ )), and vice versa, since the comparison is defined by ranking. The property (b) holds since for any {x ′ , y ′ } / ∈ E and {x, y} ∈ E:δ(F (x ′ ), F (y ′ )) ≥ δ(2mx ′ , 2mŷ ′ ) ≥ 4m 1 - γ 100 RL ≥ K(a ′ -1) + 4m 1 -γ - γ 100 RL > δ(F (x), F (y)),where the second inequality follows from Lemma 21, and the third inequality follows from K(a ′ -1) ≤ 4γmRL, which holds: since a ′ -1 ≤ 10c r log n γmRL, it suffices to have K ≤ 4 10c r log n, which indeed holds for our choice of c = max( r log n 100K , 1 100 ).There exists a set of non-contradictory t-ordering samples Q of size |Q| = m such that any embedding in ℓ p space in d dimensions requires d = Ω( √ mt). 
experiments: 
 We perform experiments on CIFAR-10 and CIFAR-100 image datasets [KH09] (we show additional experiments in 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 at random from all possible triplets of images, labeled based on the ground-truth distance. Then, we train a 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 on a single NVIDIA A100 GPU using triplet loss [SKP15b] :L F (x, y + , z -) = ∥F (x) -F (y)∥ 2 -∥F (x) -F (z)∥ 2 +1. Since our goal is to find an embedding of this set of queries, we evaluate the accuracy as the fraction of satisfied contrastive samples.We present our results in Figure 4 . 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 ≥ √ m, Not surprisingly, Figures 4c and 4d show that, when the embedding dimension increases, so does the accuracy, i.e. the number of satisfied triplets. But the accuracy stops increasing when the dimension reaches approximately √ m ≈ 316 -while there is a 2% accuracy increase when the dimension changes from 64 to 256, there is no accuracy increase when the dimension changes from 256 to 1024. This again conforms with our result from Theorem 1.There exists a metric δ on n points such that any embedding in ℓ p space which preserves the k-NN ordering of δ must have d = Ω(k) dimensions.When p is a positive odd integer or when p = ∞, the lower bounds decrease by a logarithmic factor, that is the lower bounds are respectively Ω( √ m/ log m), Ω(k/ log k), Ω( √ m/ log m), and Ω( √ mt/ log(mt)).Note that in the above statements, V 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 ℓ p space which is consistent with Q must have dimension Ω( √ m).2. Let V be an arbitrary set of size √ m + (t -1), and V ′ be an arbitrary subset of V of size √ m. By the previous item, there exists a non-contradictory sample setQ ′ of size Θ(m) on a set V ′ that requires dimension Ω( √ m) dimensions. Let V \ V ′ = {v 1 , . . . , v t-1 }.For each s ′ = (x, y + , z -) ∈ Q ′ , define s to be the (t + 1)-tuple sample s = (x, y + , z -, v - 1 , . . . , v - t-1 ). Let Q be the set of all such (t + 1)-tuple samples.Next, we prove that Q is non-contradictory. Since Q ′ is non-contradictory, there is a metric δ ′ on V ′ which is consistent with Q. Consider the following metric δ on V : for x, y ∈ V ′ , we set δ(x, y) = δ ′ (x, y), and otherwise δ(x, y) = D, where D = 2 max x,y∈V ′ δ(x, y). It is easy to see δ 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 Ω( √ m) dimension.3. Choose an arbitrary set V of size √ mt. By the first item, there exists a non-contradictory sample set Q ′ of size O(mt) on a set V that requires dimension Ω( √ mt). It suffices to show that there is a set of non-contradictory Q of size O(m) of (t + 1)-tuple samples that imply all inequalities of Q ′ . Consider a metric δ on V consistent with Q ′ . Denoting the j'th nearest neighbor of x according to δ as π j (x), letQ = ∪ x∈V {(x, π 1 (x), . . . , π t (x)), (x, π t (x), . . . , π 2t-1 (x)), . . .},where the adjacent samples share one item. We note that Q is consistent with δ, hence is noncontradictory. 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 δ (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 V such that any embedding into ℓ p space consistent with Q must have dimension Ω(k). Consider a metric δ on V consistent with Q. Since |V | = k + 1, k-NNs preserve all triplet comparisons of δ, and therefore, any embedding of V preserving the k-NN ordering has to be consistent with Q, hence requiring dimension Ω(k).Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?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, a 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 are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to 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 a 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) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either 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). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is 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. 
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 x to y is smaller than distance from x to z". This is a fundamental question in machine learning theory, since it 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 to many interesting directions for future work depending on the exact desiderata: approximate versions, different choices of normed spaces, bi-criteria algorithms, agnostic settings.While the considered distance comparison settings 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: in the upped bound from Section 3, the dependence on both log n and 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 capture properties of dataset which can lead to sharper bounds. 3 : Embedding dimension based on construction from Section 2. For each pair of n and m, 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). In this section, we present additional experiments.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.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is 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 reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on 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 a 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 to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 a 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. Guidelines:• The answer NA means that the paper does not include experiments. • The authors should answer "Yes" if 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, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is 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). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.• The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, 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 applicable), such as the institution conducting the review. 
 
 Appendix: Contrastive Samples In Table 3 , for various values of n and m, we 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 on a ground-truth embedding generated using a pretrained ResNet18 network. Note that the embedding dimension is always at most 2n, which corresponds to the case when the constraint graph is a clique. Moreover, in agreement with our theory, when m < n 2 , increasing n decreases the required dimension: the constraint graph becomes more sparse, which decreases the arboricity.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 on the setting when m is close to d 2 = 16384. While for m ≤ d 2 /2 the accuracy is close to perfect (99%), the accuracy decreases starting from this point. This supports our theoretical result that d = Θ( √ m) dimensions are required to preserve the contrastive samples.k-NN In Table 4 , we 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-truth embedding generated using a pretrained ResNet18 network. For each element x, let π * 1 (x), ..., π * n-1 (x) be the ordering of other elements according to the ground-truth embedding. For each and i ∈ [k] and each j > i, we generate contrastive samples (x, π * i (x) + , π * j (x) -), and we train the neural network on this set of samples similarly to Section 4.For each n and k, we report the loss function measuring the quality of preserving the k-NNs, defined as follows. For each vertex x and each i ∈ [k], we compute the change of rank of the i'th nearest neighbor of x in the new embeddings. Formally, we find j such that the i'th nearest neighbor ofk = 1 k = 2 k = 4 k = 8 k = 16 k = 32 k = 64 n = 100.0, 1.8 0.05, 0.8 0.15, 0.8 0.22, 0.78 n = 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 n = 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.7, 4.9 Table 4 : Training loss for preserving k-NNs for various values of n and k. 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).x according to the ground-truth embedding is the j'th nearest neighbor according to the trained embedding, contributing |i -j| to the loss. Finally, we define the final loss as the average loss over all x ∈ V and i ∈[k].Table 4 shows that the loss increases with both k 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.Definition 22 (Metric, semimetric). An metric space is an ordered pair (X, δ X ) consisting of a set X and a map δ X : X × X → [0, ∞] such that δ X satisfies:1. δ X (x, y) = 0 ⇐⇒ x = y; 2. δ X (x, y) = δ X (y, x), for all x, y ∈ X; 3. δ X (x, y) + δ X (y, z) ≤ δ X (x, z), for all x, y, z ∈ X.If δ X satisfies the last two properties but only δ X (x, x) = 0 for all x ∈ X instead of the first one then it is called a 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 (ℓ p norm, ℓ p p distance function, ℓ ∞ norm). Given vectors v, v ′ ∈ R d and p ≥ 1, the distance between v and v ′ under the ℓ p norm isδ ℓp (v, v ′ ) = d i=1 v[i] -v ′ [i] p 1/p, where v[i] is the i'th coordinate of vector v. The distance between v and v ′ under ℓ p p isδ ℓ p p (v, v ′ ) = d i=1 v[i] -v ′ [i] p .The distance between v and v ′ under the ℓ ∞ norm isδ ℓ∞ (v, v ′ ) = max i∈[d] v[i] -v ′ [i] .For p ≥ 1 or p = ∞, the norm of v is defined as ∥v∥ p = δ ℓp (v, v).Fact 24 (Chernoff bound). Let X 1 , . . . , X r ∈ {0, 1} be mutually independent random variables.Denote by µ = E [ r i=1 X i ], the expectation of the sum of variables. Then for any 0 < γ < 1 it holds thatP r i=1 X i -µ ≥ γµ ≤ 2 exp - γ 2 µ 3 .Additionally, for any γ > 0 it holds that P r i=1X i ≥ (1 + γ)µ ≤ exp - γ 2 µ 2 + γ .• Agr N (x, y) is the set of indices where x and y choose the same vector by an indirect connection:x and y share a common neighbor z, and both choose z's set I z .Note that Agr = Agr D ∪ Agr N . When x and y are neighbors and x ′ and y are not, we will show that |Agr(x, y)| ≈ |Agr D (x, y)| ≫ |Agr(x ′ , y ′ )|.We next remind the choice of parameters.Graph arboricity r ≤ 2k The size of the design R = Θ(r 3 log 3 n) Probability that an element doesn't choose its own design vector p = O(1/(r log n))Probability that neighbors choose the same design vector γ = p(1-p) • Different sets from the design (Definition 19) 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 2R -αR. Note that the distance between neighbors will be approximately(2R -αR)(L -|Agr D |) ≈ 2RL(1 - α 2 -γ(2 -α))Similarly to the above, we want to bound the deviation due to the α/2 term, and by the same logic we choose α = O(γ/(r log n)) = O(1/(r 3 log 2 n)).• We need to choose 2n sets from the design. Since by Lemma 20 the design has 2 αR log R sets, to guarantee that this value is at least 2n, we take α and R so that αR = Ω(log n), meaning R = Θ(r 3 log 3 n). If {x, y} ∈ E, assume w.l.o.g. that y ∈ N -(x). Therefore, j ∈ Agr D (x, y) if and only if we set ŷ(j) = I y and x(j) = I y . Recall that P ŷ(j) = I y = 1 -p and P x(j) = I y = p/(2r). We next show concentration for Agr N . Note that Agr D for neighbors is much larger than Agr N for both neighbors and non-neighbors.Proposition 30. For any x, y ∈ V , we have 0 ≤ |Agr N (x, y)| ≤ cγL 4r log n w.h.p.Proof. We bound the expectation of |Agr N (x, y)|. Recall that j ∈ Agr N (x, y) if and only if there exists a point z ∈ N -(x) ∩ N -(y) such that x(j) = I z and ŷ(j) = I z . Moreover, the events x(j) = I z and ŷ(j) = I z are independent, each occurring with probability p/2r.Since |N -(x) ∩ N -(y)| ≤ |N -(x)| ≤ 2r, we have E [|Agr N (x, y)|] ≤ |N -(x)| • L p 2r 2 = Lp 2 2r .Finally, we note that Lp 2 2r = Ω(log n), and by Chernoff, w.h.p.:|Agr N (x, y)| ≤ 4 3 E [|Agr N (x, y)|] = 4 3 • Lp 2 2r ≤ cγL 4r log nProof of Lemma 21. Recall that δ(x, ŷ) = L j=1 δ(x (j) , ŷ(j) ). For each j ∈ Agr(x, y), we have δ(x (j) , ŷ(j) ) = 0, and for j / ∈ Agr(x, y), due to the property of the (α, R)-design, we have|δ(x (j) , ŷ(j) ) -2R| ≤ 2αR.Summing over all j / ∈ Agr(x, y), we getEQUATIONwhere we used α ≤ cγ 8r log n . In this section, we show upper bounds for dimensions for embedding into space with ℓ p -norms or ℓ ∞ -norm.In this section, we prove Theorem 3, which provides an upper bound of m + 1 on the embedding dimension in ℓ p for integer p ≥ 1.We say that a set S ⊆ V × V is symmetric if (x, y) ∈ S ⇔ (y, x) ∈ S.Due to the symmetry, with a slight abuse of notation, we define the cardinality |S| for symmetric sets to be equal to the number of distinct unordered pairs in S.Definition 31 (Partial semimetric). An ordered triple (V, S, δ S ) consisting of a set V , a symmetric set S ⊆ V × V and a map δ S : S → [0, ∞) is a partial semimetric space if δ S satisfies the following:1. For all x ∈ V , if (x, x) ∈ S then δ S (x, x) = 0.2. δ S (x, y) = δ S (y, x) for all (x, y) ∈ S, 3. δ S (x, y) + δ S (y, z) ≤ δ S (x, z) for all (x, y), (x, z), (y, z) ∈ S. Definition 32 (Partial embedding). We say that a partial semimetric (V, S, δ S ) partially embeds into a metric space (Y, δ Y ) if there exists a map F : V → Y such that δ S (x, y) = δ Y (F (x), F (y)) for all (x, y) ∈ S.The following lemma is an extension of the standard embedding result into ℓ p (see e.g. [DL97] ). Lemma 33. Let S = (V, S, δ S ) be a partial semimetric on V and let m = |S|. If S partially embeds into an ℓ p p -space with finite dimension, then it embeds into (ℓ p p ) m+1 .Proof. Let {{x i , y i }} m i=1 be the unordered pairs of S. We assign every partial semimetric (V, S, δ) on S an m-dimensional vector v δ , where v δ [i] = δ(x i , y i ). We call v δ the representation vector of (V, S, δ). Define NOR S to be the set of representations of all partial semimetrics on S which can be partially embedded into ℓ p p , i.e. NOR S = {v δ | There exists d ∈ N such that (V, S, δ) partially embeds into (R d , ℓ p p )}.Note that NOR S is a cone:1. If v δ ∈ NOR S then αv δ ∈ NOR S for all α ≥ 0. 2. If v δ , v δ ′ ∈ NOR S then v δ + v δ ′ ∈ NOR S .An extreme ray is a pointv δ ∈ NOR S such that if v δ = v δ1 + v δ2 for v δ1 , v δ2 ∈ NOR S then it has to be that v δ1 = αv δ and v δ2 = (1 -α)v δ for some α ∈ [0, 1].Next, we show that any extreme ray of NOR S has a partial embedding into the one-dimensional space (R, ℓ p p ). Indeed, let v δ be an extreme ray, and let d be the minimum dimension for which (V, S, δ) partially embeds to (R d , ℓ p p ). If d = 1, then we are done; otherwise, assume by contradiction that d > 1. Let F : V → R d such that δ(x, y) = δ p p (F (x), F (y)) for all (x, y) ∈ S. LetF 1 : V → R, F 2 : V → R d-1 such that F 1 (x) = F (x)[1] and F 2 (x) = (F (x)[2], . . . , F (x)[d]), i.e. F 1 is the embedding F restricted to the first dimension, and F 2 is F restricted to the remaining d -1 dimensions. We notice that for each (x, y)∈ V × V , δ p p (F (x, y)) = δ p p (F 1 (x, y)) + δ p p (F 2 (x, y)). Define ρ 1 , ρ 2 : S → R such that ρ 1 (x, y) = δ p p (F 1 (x), F 1 (y)), and ρ 2 (x, y) = δ p p (F 2 (x), F 2 (y)). Therefore, v δ = v ρ1 + v ρ2 .Since v δ is an extreme ray, then there exists α ∈ [0, 1] such that v δ = αv ρ1 . In particular, δ can be partially embedded into one dimension, by taking the embedding αF 1 (x), contradicting minimality of d. We conclude that d = 1.Finally, let v S be the representation vector of S. By Caratheodory's theorem, since v S ∈ NOR S , there exists m + 1 extreme rays v δ1 , . . . , v δm+1 ∈ NOR S such that v S = m+1 i=1 v δi . We have shown that for each i ∈ [m + 1], the partial semi-metric (X, S, δ i ) has a partial embedding F (i) : V → R into the one dimensional space (R, ℓ p p ). It follows that the embedding F = (F (1) , . . . , F (m+1) ) is a partial embedding of S into (R m+1 , ℓ p p ), and the claim follows.Proof of Theorem 3. If Q is a set of non-contradictory constraints, then we can embed it into ℓ 2 using Theorem 1. We can then embed it isometrically into ℓ p (see Chapter 1.5 from [Mat13] and Theorem 5 from [Goe06] ). By using the same points, the relationships between distances are also preserved in ℓ p p . Let S be the set of all edges in the constraint graph G. Then we have a partial semimetric (V, S, δ S ) which is partially embedded into ℓ p p . By Lemma 33 it partially embeds isometrically into (ℓ p p ) |S|+1 . For the same embedding, the relationships between distances are also preserved in ℓ p .In this section, we prove Theorem 2, which states that dimension O(m 2/3 ) suffices to satisfy any set of m non-contradictory contrastive queries Q in the ℓ ∞ norm.Let G = (V, E) be the constraint graph, where E is the edge set. We arbitrarily assign a unique identifier id(x) ∈ [n] for each x ∈ V . Let V high ⊆ V be the set of points with degree with at leastm 1/3 in G. Let V low = V \ V high .Our embedding is a concatenation of two embeddings F 1 and F 2 , which intuitively "handle" V low and V high respectively. In the sub-embedding F 1 , we use the fact that the graph induced by V low has low degree to argue that it has a proper distance-2-edge coloring with O(m 2/3 ) colors, i.e. we can color the edges of the graph such that no two edges at distance at most 2 share the same color.We use this coloring to obtain an embeddingF 1 : V low → R O(m 2/3) which satisfies certain distance properties between any pair of neighbors in V low . We then extend F 1 to an embeddingF : V → R O(m 2/3) which is consistent with Q. This extension draws inspiration from the seminal Fréchet embedding [Fré10] : for each point in x i ∈ V high we add a single distinct dimension i, in which we intuitively set this coordinate for each point x ∈ V as distance from x i in F ′ . In actuality, we set these coordinates slightly differently, in order to combine correctly with the sub-embedding F 1 , and obtain an embedding which is consistent with Q. By Lemma 34, the size |V high | = O(m 2/3 ), which implies that together the dimension of F is O(m 2/3 ).Lemma 34. Let Q be the set of m contrastive queries. Let V high be the set of points with degree at least m 1/3 in the constraint graph. Then |V high | = O(m 2/3 ).Proof. Recall that each query (x, y + , z -) ∈ Q is associated with two edges, {x, y}, {x, z} ∈ E. Hence, the total number of edges in G is at most 2|Q| = 2m. This impliesm 1/3 |V high | ≤ x∈V high deg(x) ≤ x∈V deg(x) = 2|E| = 4m.By rearrangement, we obtain that |V high | ≤ 4m 2/3 .Since Q is non-contradictory, by Fact 25 there exists a metric δ consistent with Q. Using the Frechét embedding [Fré10] , any metric on n points may be isometrically embedded into R n-1 under the ℓ ∞ norm.Definition 35 (Scaled Frechét embedding F ′ ). Let F ′ : V → R n-1 be an embedding of δ into the cube [0, 1/2] n-1 under the ℓ ∞ norm, obtained by scaling and shifting (i.e. multiplying or adding some value to all coordinates, respectively) the Frechét embedding of δ.We note that scaling and shifting do not affect whether a contrastive query is satisfied, therefore F ′ is consistent with Q as well.Lemma 36. There is an embeddingF 1 of V low into R O(m 2/3) such that the following hold:(a) for each x ∈ V low and i ∈ N, it holds thatF 1 (x)[i] ∈ [0, 1]; (b) for each x, y ∈ V low such that {x, y} ∈ E, it holds that ∥F 1 (x) -F 1 (y)∥ ∞ = 1/2 + ∥F ′ (x) - F ′ (y)∥ ∞ .Proof. By definition, each x ∈ V low has degree at most ∆ = O(m 1/3 ). Therefore, there is an edge coloringC : E → [∆ 2 + 2] of G = (V, E), in which (a) every vertex has at most one incident edge of any color, and (b) any two adjacent vertices x, y share exactly one edge color -the one of their shared edge C(x, y). We remark that this coloring is called in the literature distance-2-edge coloring. Such a 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 z ∈ N (x) ∪ N (y). In other words, let K(x, y) be the set of colors taken by any edge incident to any vertex in {x, y} ∪ N (x) ∪ N (y). Since |K(x, y)| ≤ 2∆ 2 + 1, then we can always choose from {x, y} a color different from all colors of K(x, y).We define the embedding F 1 as follows: assume the color of the edge of {x, y} is C(x, y) ∈ [∆ 2 +2].Let c = C(x, y) and assume w.l.o.g. that id(x) < id(y). We defineF 1 (x)[c] = 0 and F 1 (y)[c] = 1/2 + ∥F ′ (x) -F ′ (y)∥ ∞ .For any x ∈ V , if a coordinate i is not set in this process, we set F 1 (x)[i] = 1/2. We note this is well-defined since the edge coloring is proper (i.e. no vertex has 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 ℓ ∞ , hence for each pair x, y ∈ V low there is a coordinate i(x, y) ∈ N for which∥F ′ (x) -F ′ (y)∥ ∞ = ∥F ′ (x)[i(x, y)] -F ′ (y)[i(x, y)]∥.For property (a), we note that every coordinate i is either set to F (y)[i] = 0, or to F (yEQUATIONNext, we show that property (b) holds. Denoting c = C(x, y), for each edge {x, y} ∈ E such that id(x) < id(y), it holds thatF ′ (x)[c] = 0 and F ′ (y)[c] = 1/2+∥F (x)-F (y)∥ ∞ . Second, since x, y share only one edge color, in each other coordinate j ̸ = c, either F 1 (x)[j] = 1/2 or F 1 (y)[j] = 1/2, meaning that c is the coordinate with the maximum difference, i.e. ∥F 1 (x) -F 1 (y)∥ ∞ = 1/2 + ∥F ′ (x) -F ′ (y)∥ ∞ .The Overall Embedding:Lemma 37. Let F 1 : V low → R O(m 2/3) be the embedding described in Lemma 36. Then there exists an embeddingF : V → R O(m 2/3 ) such that for any {x, z} ∈ E it holds that ∥F (x) -F (z)∥ ∞ = 1/2 + ∥F ′ (x) -F ′ (z)∥ ∞ . Proof. Let d = O(m 2/3 ) be the dimension of F 1 (i.e. F 1 : V low → R d ), and r = |V high | = O(m 2/3). Let V high = {y 1 , . . . , y r }. We define F (x) as follows: fory i ∈ V high , we set all coordinates for 1 ≤ j ≤ (d + i -1) to F (y i )[j] = 1/2, the (d + i)'th coordinate as F (y i )[d + i] = 0,and set any coordinated + i + 1 ≤ j ≤ d + r to F (y i )[j] = 1/2 + ∥F ′ (y i ) -F ′ (y j-d )∥ ∞ .For x ∈ V low , we set the first d coordinates to be as in F 1 (x). The remaining r coordinates, i.e. d + 1 ≤ j ≤ d + r, we define as F (x)[j] = 1/2 + ∥F ′ (x) -F ′ (y j )∥ ∞ . This concludes the description of the embedding.First, we show that for any x, z ∈ V low such that {x, z} ∈ E, it holds that ∥F (x) -F (z)∥ ∞ = 1/2 + ∥F ′ (x) -F ′ (z)∥ ∞ .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.e. the difference on any of these coordinates is at most 1/2.Next, we show that for any x ∈ V low and y i ∈ V high such that {x,y i } ∈ E, it holds that ∥F (x) - F (y i )∥ ∞ = 1/2 + ∥F ′ (x) -F ′ (y i )∥ ∞ . Indeed, in any coordinate j ̸ = (d + i), F (y i )[j] ≥ 1/2, and hence |F (y i )[j] -F (x)[j]| ≤ 1/2. On the other hand, in the (d + i)'th coordinate |F (y i )[d + i] - F (x)[d + i]| = 1/2 + ∥F ′ (x) -F ′ (y i )∥ ∞ > 1/2.Finally, we consider the case where y i , y j ∈ V high such that {y i , y j } ∈ E and i < j. For the first d coordinates, both vectors are set to 1/2, in all coordinates between d + 1, . . . , d + j -1 the vector y j is set to 1/2, and therefore they differ by at most 1/2 in these coordinates. For the (d + j)'th coordinate, y j is set to zero, and y i is set to 1/2 + ∥F ′ (y i ) -F ′ (y j )∥ ∞ . For higher coordinates, both y i , y j are set to values at least 1/2. Therefore,∥F (y i )-F (y j )∥ ∞ = 1/2+∥F ′ (y i )-F ′ (y j )∥ ∞ .Finally, we show that F is consistent with Q.Lemma 38. The embeddingEQUATION∥F (x) -F (z)∥ ∞ = 1/2 + ∥F ′ (x) -F ′ (z)∥ ∞ > 1/2 + ∥F ′ (x) -F ′ (y)∥ ∞ = ∥F (x) -F (y)∥ ∞ .And since ∥F (x) -F (y)∥ ∞ < ∥F (x) -F (z)∥ ∞ , the query (x, y + , z -) is satisfied.Theorem 2 follows directly from Lemma 38.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.In this section, we first extend our results to contrastive queries with more than two candidates. Then, we show that the problem of actually constructing the embedding consistent with given contrastive samples is NP-hard. Finally, we consider an approximate setting for contrastive learning, in which we only need to satisfy an α-fraction of the constraints. We show that there exists an instance for which satisfying α ≈ 0.77 fraction of the constraints requires roughly the same number of dimensions as satisfying all constraints. On the other hand, we show that for α ≤ 1/2, one dimension always suffices.F.1 Upper Bound for t-Negatives and t-Ordering Samples in ℓ 2 -normIn this section, we consider two additional settings, in which each sample contains ordinal information 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 + 2)-tuple s = (x, y + , z - 1 , . . . , z - t ). We say sample s is satisfied by distance function δ if δ(x, y) > δ(x, z i ) for all 1 ≤ i ≤ t.In the second setting (t-ordering), we are given a set Q of m samples, where each sample s is a t-tuple s = (x, y 1 , . . . , y t ), and we say sample s is satisfied by distance function δ if δ(x, y 1 ) < δ(x, y 2 ) < • • • < δ(x, y t ) for all 1 ≤ i ≤ t.Theorem 44 (t-orderings, t-negatives). Let Q be a set of m non-contradictory t-ordering samples (resp. t-negative samples) on a set V . There is an embedding of V into ℓ 2 -space R O( √ mt) which is consistent with Q.Proof. For a set of (t + 2)-tuple samples Q on V of size m, we define the constraint graph G = (V, E) as follows: for each sample (x 1 , . . . , x t+2 ) ∈ Q, we add t+1 edges {x 1 , x 2 }, . . . , {x 1 , x t+2 } to E (if they don't already exist).First, we note that the constraint graph of t-orderings and t-negatives has arboricity O( √ mt). Indeed, we add for each sample at most O(t) edges to G, hence the total number of edges is at most O(mt). By Fact 7, the arboricity of G is r = O( √ mt). By Theorem 9 there exists an embedding into ℓ 2 -space with dimension r = O( √ mt) that satisfies the corresponding inequalities.In this section, we show that, empirical risk minimization for embedding into an ℓ p space is NPhard. 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 a set of triplets {(a 1 , b 1 , c 1 ), . . . , (a m , b m , c m )}, such that a i , b i , c i ∈ X for all i. The goal of the betweenness problem is to find an order of items on X so that for each i, b i is located between a i and c i . That is, the goal is to find a bijection r : X → {1, . . . , n} so that for each i either r(a i ) < r(b i ) < r(c i ) or r(c i ) < r(b i ) < r(a i ) hold.[Opa79] shows that the decision version of the betweenness problem -i.e. checking whether such an ordering exists -is NP-hard.Theorem 46. Unless P = N P , there is no polynomial algorithm for finding an embedding into ℓ 2 space for d = 1 in the realizable case.Proof. Let A be an algorithm for finding an ℓ 2 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 at most T (n) = poly(n) iterations. This way, A ′ runs on all inputs in time at most T (n) and outputs an embedding satisfying the input constraints iff such an embedding exists.We complete the proof by reduction from the betweenness problem.Let {(a 1 , b 1 , c 1 ), . . . , (a m , b m , c m )} be the input for the betweenness problem. Then, we can represent constraint "b i is between a i and c i " using two contrastive constraints (a i , b + i , c - i ) and (c i , b + i , a - i ). For example, if r(b i ) < r(a i ) < r(c i ), then the constraint (c i , b + i , a - i ) is violated; other cases are similar.We execute A ′ on this set of contrastive constraints. Since the algorithm finds a 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 ̸ = N P .In this section, we consider the settings when the embedding doesn't have to satisfy all the constraints. Instead, for some constant α, we want to satisfy at least an α-fraction constraints. We show the following separation in the ℓ p case for any integer p. Theorem 47. For the embedding into ℓ p space for p ∈ {1, 2, 3, . . .}, the following hold.• For any α ≤ 1/2, for any set of m constraints, for any d ≥ 1 there exists an embedding with dimension d satisfying at least αm constraints.• Let α * ≈ 0.77 be the root of equation H(x) = x, where H is the binary entropy function. Then for any α > α * , there exists a set of m non-contradictory constraints so that satisfying at least αm constraints requires dimension at least Ω( √ m) for even p and at least Ω( √ m/ log m) for odd p.The theorem shows that for α ≤ 1/2, the problem trivializes, while for α > α * , 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 is a gap between 1/2 and α * ≈ 0.77, and we hypothesize that α * bound is the most likely one to be improved, due to the union bound used in the proof below.Proof. The case α ≤ 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 α > α * . 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 αm triplets. For each individual subset, we will show the probability that its induced labeling is achievable is less than 1/ m αm . 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 ℓ 2 distance We first consider the ℓ 2 -case, and below we describe how to handle ℓ p distance for other integer p. By Lemma 41, there for any set V of items, there exists a set C of m = n-1 2 unlabeled triplets such that any its labeling is realizable. For a sufficiently large n, assume that d < cn for some constant c (depending on α and to be specified later). We will show that for α > α * , there exists no subset of C of size αm so that every its labeling is realizable by some embedding into a d-dimensional space. For that, we will use the following fact.). Let m ≥ t ≥ 2 be integers, and let P 1 , . . . , P m be real polynomials on t variables of degree at most s. LetU (P 1 , . . . , P m ) = x ∈ R t | P i (x) ̸ = 0 for all i ∈ [m]be the set of points x ∈ R t which are non-zero in all polynomials. Then the number of connected components in U (P 1 , . . . , P m ) is at most (4esm/t) t .Similarly to [AAE + 24], we apply this fact to the following polynomials: for each triplet (x, y, z), for a fixed embedding function F , we define a polynomialP xyz = ∥F (x) -F (y)∥ 2 2 -∥F (x) -F (z)∥ 2 2 = d i=1 (F i (x) -F i (y)) 2 - d i=1 (F i (x) -F i (z)) 2Denoting V = {x 1 , . . . , x n }, all P xyz for (x, y, z) ∈ C are polynomials over nd variables F 1 (x 1 ), . . . , F d (x 1 ), . . . , F 1 (x n ), . . . , F d (x n ).Importantly, when (x, y + , z -) is satisfied by F , the polynomial is negative, while, when (x, z + , y -) is satisfied by F , the polynomial is negative. Hence, different choices of labels of C must correspond to the different sign combinations of polynomials. Fact 48 shows that the number of sign combinations of the polynomials -and hence the amount of possible labelings -is bounded by (8em/nd) nd ≤ (4en/d) nd , where we used m = n-1 2 < n 2 2 . For any subset of αm constraints, there are 2 αm possible induced labelings. On the other hand, as shown above, only (4en/d) nd 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(4en/d) nd 2 αm = 2 nd log 2 (4en/d)-αmAs outlined above, since there are at most m αm subset of αm constraints, we want this ratio to be at most 1/ m αm . By a well-known fact [TJ06], m αm ≤ 2 H(α)m , where H is a binary entropy function. Hence, the probability that any subset of αm induced constraints is satisfiable is at most(4en/d) nd m αm 2 α(n-1) 2 /2 ≤ 2 nd log 2 (4en/d)-αm+H(α)m = 2 m(H(α)-α+(nd/m) log 2 (4en/d))Since m ≥ (n -1) 2 /2, for a sufficiently large n we have nd/m < 3d/n. Consider the case when d < cn for some constant c. When c < 4, the last term (3d/n) log 2 (4en/d) monotonically increases in d, and hence we haveH(α) -α + (nd/m) log 2 (4en/d) < H(α) -α + 3c log 2 (4e/c) When α > α * , where α * ≈ 0.77 satisfies α * = H(α * ), we have 0 > H(α) -α. Since f (c) = 3c log 2 (4e/c) is continuous and strictly monotone for c ∈ [0, 4] and f (0) = 0, there exists c ′ > 0 such that H(α) -α + 3c ′ log 2 (4e/c ′ ) < 0. Hence, when d < c ′ n, there exists a labeling of m triplets, so that no subset of αm triplets is satisfiable. ℓ p distances for positive integer p When p is even, the above argument doesn't change. When p is odd, we encounter the issue that∥F (x) -F (y)∥ p p -∥F (x) -F (z)∥ p p = d i=1 |F i (x) -F i (y)| p - d i=1 |F i (x) -F i (z)| pis not a polynomial. We address this issue similarly to [AAE + 24]: for each coordinate i, we guess the order of points with respect to this coordinate. This introduces an additional factor of (n!) d = 2 O(nd log n) in the number of possible sign combinations. The derivation is similar to the above, but we instead want the following inequality:H(α) -α + (nd/m) log 2 (4en/d) + O((nd/m) log n) < 0,which holds when d < cn/ log n for some constant c.• 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-referenced.• 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 are 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).This is since ntriplet 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 a set of at most n 2 samples which is also embeddable and at least as restrictive as Q.In subsequent versions of our paper, we have improved the analysis to show a dimension bound of O(k). 


Decision: 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

Reviews: review: paper_summary: paper_summary: Paper studies the embedding dimension of contrastive learning and kNN problem.
In 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. 

So 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?

Similarly, 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. 

Main results:
Authors show for l2 metrics, we can embed into sqrt(m) dims for contrastive learning
They show slightly weaker results for l_infty metric and l_p metrics for general p.

More interestingly, for k-NN embeddings, they show embeddability into poly(k) dims for lp norm and k dims for l2 norm!

Main 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). 
They 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.

They finally show some empirical results on CIFAR dataset showing that the obtained theoretical bounds can be met in practice.
strength_weakness: strength_weakness: 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. 

Can 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.
questions: questions: I have asked my qns in the weakness section.
limitations: limitations: Paper does not have explicit limitations/ future work section and would benefit from one.
paper_summary: paper_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).
strength_weakness: strength_weakness: 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)

Empirical 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.

Application 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.

The presentation could benefit from some polishing and simplification of the notation, though this is more a matter of preference than a true weakness.
questions: 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?

2. 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?

2. 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: limitations: The main limitations that come to my mind are the limited empirical support and the complexity of the theoretical concepts.
paper_summary: paper_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$.
strength_weakness: strength_weakness: 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.
questions: questions: See te weaknesses section.
limitations: limitations: Not discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: - *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.

- *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}$?

- *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.


**Minor:**
- *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.

- *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.

- *W6 Resolution of Figure 3:* is too low, especially for inspecting the small performance gaps between many of the runs.

- *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).

- *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. 

**Typo:**
Line 269: "for any $[J]...$" --> "for any $j\in [J]...$"
questions: questions: - *Q1:* I did not get the Chernoff bound arguments in line 236 and 240. Could you please elaborate?

- *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?

- *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$?

- *Q4:* In line 270, we seem to need $J=r$ rather than only $J=O(r)$ (see Q3 and W5).

- *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.

- *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'$.

- *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$?

- *Q8:* Please repeat what $w(x,y)$ means in line 317. 

- *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: 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.

Comments: title: Happy authors
Happy reviewer
Rebuttal
More on W3 and W7
Reply: Other Questions
Reply: W3
comment: Thanks a lot, very excited to hear that this is one of the best papers you've read in a while and your concerns have been fully addressed! :)
Thanks for your hard work, your responses fully addressed my comments. Good luck!
Thank you for reconsidering the score and for your valuable comments!
Thank you for your comments.

> ... Whether the embedding is actually obtained ...
> To compute $F$, what computation do we really need?

Yes, all embedding constructions are explicit. The construction for $\\ell_2$ is in Section 2, and the construction for k-NN embeddings is in Section 3.

> Here, there are no encoders.

We would appreciate it if you could please clarify what you mean by encoders here. 

> Can we practically set the valid $h$ beforehand


We are not exactly sure we understand this question. By $h$, we assume you mean the size parameter in the construction for $\\ell_2$. We don’t use this parameter in the k-NN construction, which your questions seems to be about.
Thanks for clarifying the argument further!

Overall, I am happy with the rebuttal and have raised my score to 6.
Thank you again for your comments!

> W3. Could you please comment on why you can choose $m$ (or $c$) to make (*) true while maintaining $m \\le n^2$, so that the triplets are not contradictory? I also do not get the last bit on choosing $n = \\sqrt{m}$. 

Let us present the construction in a slightly different way, which hopefully answers both of your questions.

**Construction.**
Consider a set of $n$ points.
On this set of $n$ points, according to Lemma 41, there exists a set of $m = {n - 1 \\choose 2} \\approx n^2 / 2$ triplets $C$, such that for every labeling of $C$ there exists a metric consistent with this labeling.

We will show that, in general, $d = \\Omega(n)$ is required so that for any labeling of $C$ there exists an embedding into a $d$-dimensional $\\ell_2$-space.
Since for this construction $n = \\Theta(\\sqrt{m})$, this implies that $d = \\Omega(\\sqrt{m})$ is required in general to embed a set of $m$ non-contradictory constraints.

**Proof.**
For the sake of contradiction, assume that there is a sufficiently large $n$ such that every labeling of the above set of triplets can be embedded using dimension $d < c n$ for some constant $c < 1$ (to be specified later).
As mentioned in the previous reply, the amount of possible labelings consistent with an embedding of dimension $d$ is at most $(8 em / (nd))^{nd} \\approx (4e n / d)^{nd}$, where $\\approx$ ignores low-order terms in the exponent.

As we showed in the previous reply, not all labelings are embeddable as long as the above expression is less than
$$2^{\\alpha m} \\cdot {m \\choose \\alpha m} \\approx 2^{m(\\alpha - H(\\alpha))} \\approx 2^{n^2 (\\alpha - H(\\alpha)) / 2}$$

When $d < cn$, we have
$$(4e n / d)^{nd} < (4e / c)^{c n^2} = 2^{n^2 c \\log_2 (4e/c)}$$

for a sufficiently large $n$.

Then, if $c \\log_2 (4e/c) < (\\alpha - H(\\alpha)) / 2$ (such $c$ exists), we have that $(4e n / d)^{nd} < 2^{\\alpha m} \\cdot {m \\choose \\alpha m}$ for a sufficiently large $n$, implying that not all labelings of $C$ are embeddable.
This proves that $d = \\Omega(n)$ is required.

Since in this construction $n = \\Theta(\\sqrt{m})$, this means that $d = \\Omega(\\sqrt{m})$ is required in general.

> W7. Thanks for stating the constant! I do not mind the result being largely theoretical, especially with the additional discussion on why the poly-logarithmic dependence is surprising. Nevertheless, I encourage you to state the constant and the $n$-regime in which your bound becomes practically useful in the revision.

Thank you, we will specify the constants and add a short discussion about the constants and the practical regime at the conclusion of the paper.
Thanks for your reply!

**W3:** Could you please comment on why you can choose $m$ (or $c$) to make (*) true while maintaining $m \leq n^2$, so that the triplets are not contradictory? I also do not get the last bit on choosing $n=\sqrt{m}$. 

**W7:** Thanks for stating the constant! I do not mind the result being largely theoretical, especially with the additional discussion on why the poly-logarithmic dependence is surprising. Nevertheless, I encourage you to state the constant and the $n$-regime in which your bound becomes practically useful in the revision.
> W7: Can you give a rough guidance on the $(n,k)$ regime in which your kNN bound would be an improvement over the trivial bound of $n$? I.e. how large is the constant in the big-O notation?
I appreciate the additional experiments on the $k$-NN graph. Perhaps a table showing the required dimension like you provide in the general comment for $\\ell_2$ embeddings would be useful.

We note that the constants in the proof (including multiple 100's) were chosen for the sake of simplicity of the calculations, leading to very large total constant.
We believe that the constants can be decreased so that the final constant is approximately $10^4$. In this case, the final dependency would be $10^4 k^7 \\log^3 n$ which for very small $k$ might make it applicable for $n$ of order $10^8$-$10^9$. With some further work, one might be able to improve the constant event further but we believe that the more important (and closely related) question is improving the dependence on $k$.

Overall, we would like to emphasize that the main contribution for the k-NN settings is theoretical, showing that the dependence on $n$ is at most poly-logarithmic.
This is very surprising, since, intuitively, k-NN still requires $n^2$ contrastive constraints: in particular, you need to compare the closest neighbor with all other neighbors.
In general, as our paper shows, $n^2$ constraints might require $\\Omega(n)$ dimension, but we show that these constraints have a sufficiently good structure to avoid linear dependence on $n$.

We don't claim that the $k$-NN construction is practical as is, and it's very likely that the dependence on all parameters can be improved substantially, which we leave as a future work.
In particular, one of the main reason for the large dimension is due to randomized sampling scheme used to get Lemma 22.
It is likely that a simpler deterministic scheme exists (which potentially might not require $\\alpha$-designs, further simplifying the construction), which would probably give better dependency both on $k$ and constants.


> Q1 Chernoff bounds I got the argument for line 240. Unfortunately, I am not very familiar with Chernoff bounds and for line 236, I only found the statement $P[X \\geq (1+\\delta)E[X]]\\leq e^{-\\delta^2 E[X]/(2+\\delta)}$ online which looks similar to what you use, but is not quite the same. Could you please state the version of the Chernoff bound that you are using and a reference?


We'be been aiming to simplify the presentation, which in result omitted some details.
We use the standard Chernoff bound $P[X \\geq (1+\\delta)E[X]] \\leq e^{-\\delta^2 E[X]/(2+\\delta)}$, and below we show the complete derivation.

We have
\\begin{align*}
    P[X > c \\ln n] 
    &= P[X > \\frac{c}{E[X]} \\ln n \\cdot E[X]] \\\\
    &= P[X > (1 + (\\frac{c}{E[X]} \\ln n - 1)) \\cdot E[X]]
\\end{align*}

Next, we use the referenced Chernoff bound with $\\delta = (\\frac{c}{E[X]} \\ln n - 1)$.
Note that for $n \\ge e$ and $c \\ge 3 E[X]$, we have $\\delta \\ge (\\frac{3 E[X]}{E[X]} \\ln e - 1) \\ge 2$ and hence $2 + \\delta \\le 2 \\delta$ and $\\delta^2 / (2 + \\delta) \\ge \\delta / 2$.
Finally, by the Chernoff bound, we have
\\begin{align*}
    P[X > c \\ln n] 
    &\\le e^{-\\delta E[X] / 2} \\\\
    &\\le e^{-(\\frac{c}{E[X]} \\ln n - 1) E[X] / 2} \\\\
    &= n^{-c/2} \\cdot e^{E[X] / 2}
\\end{align*}

Since $E[X] = O(1)$ (as a sum of $O(r)$ i.i.d. random variables with expectation $1/r$),
the error probability is $O(n^{-c/2})$, which can be made arbitrarily small by the appropriate choice of constant $c$.


> General comment on $\\ell_2$ embeddings: I am surprised that the required dimension decreases with $n$ for certain $m$-values. Could you please give some intuition why this happens?

Great question! Recall that the dimension is $O(r)$, where $r$ is the arboricity.
Arboricity is the measure of density of the graph (see also figures in the global reply).
For a fixed $m$, with the increase of $n$, the density of the graph naturally decreases, which leads to smaller arboricity, and hence smaller dimension. We'll elaborate on this in the experiment.
Thank you for the fast reply! We are happy to elaborate on these points. Please let us know if you have any questions remaining. If we addressed all your questions, we would be grateful if you could reconsider the score.

## W3: This dependence on $\\alpha \\le 0.5$ sounds intriguing! I'd be interested in a reference and suggest to add this for context to the background section of the paper.

In the following, for simplicity, we changed the meaning of $\\alpha$ compared your review: we are interested in satisfying $\\alpha$-fraction of constraints, instead of $(1-\\alpha)$-fraction.
Here is what we can say quickly (we belive this can be improved with more work):

* For any set of $m$ triplet constraints, a random one-dimensional $\\ell_p$ embedding satisfies at $m / 2$ constraints in expectation, hence there exists an embedding which satisfies at least $m/2$.
* Let $\\alpha^* \\approx 0.77$ be the root of equation $H(x) = x$, where $H$ is the binary entropy function. Let $\\alpha$ be a constant greater than $\\alpha^*$. Then for any $m$, there exists a set of $m$ constraints so that satisfying at least $\\alpha m$ constraints in $\\ell_2$ embedding requires dimension at least $\\Omega(\\sqrt{m})$.

**Satisfying $\\alpha m$ constraints for constant** $\\alpha > \\alpha^*$

We use the following fact (see Section 3 of [AAE+24] for more details):

**Fact.** Consider a set of $m$ triplets $\\{(x_i, y_i, z_i)\\}_{i=1}^m$. Then the number of sets $T \\subseteq S$ such that there exists an embedding satisfying the following conditions is at most $(8 e m / (nd))^{nd}$.
* The embedding lies in the $d$-dimensional $\\ell_2$ space.
* For each triplet $(x_i, y_i, z_i)$ from $T$, the correct constraint according to the embedding is $(x_i, y_i^+, z_i^-)$.
* For each triplet $(x_i, y_i, z_i)$ from $S \\setminus T$, the correct constraint according to the embedding is $(x_i, z_i^+, y_i^-)$.

In other words, for fixed $n$ and $d$, the number of different labelings (i.e. choices of triplets for which the first candidate is the closest to the anchor) *we can achieve* depends on $m$ polynomially, not exponentially.
This means that, when $m$ sufficiently large, the number of achievable labelings is less than $2^m$.
Hence, some of the labelings are not achievable, which is used by [AAE+24].

Our idea is similar. This is the outline:
* For each subset of triplets of size $\\alpha m$, there are at most $(8 e \\alpha m / (nd))^{nd}$ possible labelings.
Meaning, if we choose a random labeling, the probability that this labeling is achievable is at most $(8 e m / (nd))^{nd} / 2^{\\alpha m}$.
We choose $m$ so that the probability is less than $1 / {m \\choose \\alpha m}$.
* Let's choose a random labeling of $m$ triplets, and look at the induced labeling of each subset of $\\alpha m$ triplets. For each individual subset, the probability that the labeling is achievable is less than $1 / {m \\choose \\alpha m}$. By the union bound, the probability that any of the induced labelings is achieavable is less than $1$.
* Hence, by the probabilistic argument, there exists at least one labeling of $m$ triplets so that none of the induced labelings of any subset of $\\alpha m$ triplets is achievable.
In other words, if we choose constraints according to this labeling, then for any embedding, there is no subset of $\\alpha m$ satisfied constraints.

It remains to show that for $\\alpha > \\alpha^*$, there exists $m$ such that
$$
(8 e \\alpha m / (nd))^{nd} / 2^{\\alpha m} < 1 / {m \\choose \\alpha m} \\iff (8 e m / (nd))^{nd} < 2^{\\alpha m} \\cdot {m \\choose \\alpha m},
\qquad(*)
$$

and for that we want the right-hand side to grow exponentially in $m$.
We use a well-known fact that
$${m \\choose \\alpha m} = 2^{m H(\\alpha)} \\cdot poly(...),$$

where $H$ is the binary entropy function.
Since we want $2^{\\alpha m} \\cdot 2^{m H(\\alpha)}$ to grow exponentially in $m$, we need to guarantee that $\\alpha > H(\\alpha)$, which holds for $\\alpha > \\alpha^*$.
For $m = cnd / (\\alpha - H(\\alpha))$ for some constant $c$, we have
$$(8 em / (nd))^{nd} = (8ec \\alpha / (\\alpha - H(\\alpha)))^{nd}$$

and
$$2^{\\alpha m} \\cdot {m \\choose \\alpha m} = 2^{cnd} \\cdot poly(...),$$

and the desired inequality $(*)$ is satisfied for some constant $c$ (depending on $\\alpha$).

Finally, similarly to the paper, by choosing $n = \\sqrt{m}$, we get $\\Omega(\\sqrt{m})$ on dimension.


**Notes.** There is a gap between $1/2$ and $\\alpha^* \\approx 0.77$.
Most likely, one can improve the $\\alpha^*$ bound since the union bound is too coarse.
Thank you very much for your detailed response, which clarified many of my issues. I have a few remaining follow-up questions / comments.

**W3:** This dependence on $\alpha \leq 0.5$ sounds intriguing! I'd be interested in a reference and suggest to add this for context to the background section of the paper.

**W7:** Can you give a rough guidance on the (n,k) regime in which your kNN bound would be an improvement over the trivial bound of $n$? I.e. how large is the constant in the big-O notation? I appreciate the additional experiments on the $k$-NN graph. Perhaps a table showing the required dimension like you provide in the general comment for $\ell_2$ embeddings would be useful.

**Q1 Chernoff bounds** I got the argument for line 240. Unfortunately, I am not very familiar with Chernoff bounds and for line 236, I only found the statement $P(X \geq (1+\delta)E(x))\leq e^{-\delta^2E(X)/(2+\delta)}$ online which looks similar to what you use, but is not quite the same. Could you please state the version of the Chernoff bound that you are using and a reference?

**General comment on $\ell_2$ embeddings:** I am surprised that the required dimension decreases with $n$ for certain $m$-values. Could you please give some intuition why this happens?