Embedding Dimension of Contrastive Learning and k-Nearest Neighbors

We study the embedding dimension of distance comparison data in two settings: contrastive learning and k-nearest neighbors (k-NN). Our goal is to find the smallest dimension d of an ℓ 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. For the most popular ℓ 2 -space, we get tight bounds in both settings. In contrastive learning, we are given m labeled samples (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 also give results for t negatives). For representing such dataset in:

• ℓ 2 : d = Θ( √ m) is necessary and sufficient, consistent with our experiments.

• ℓ p for p ≥ 1: d = O(m) is sufficient and d = Ω( √ m) is necessary.

• ℓ ∞ : d = O(m 2/3 ) is sufficient and d = Ω( √ m) is necessary. In k-NN, for each of the n data points we are given an ordered set of the closest k points. We show that for preserving the ordering of the k-NN for every point in:

• ℓ 2 : d = Θ(k) is necessary and sufficient.

• ℓ p for p ≥ 1: d = Õ(k 2 ) is sufficient and d = Ω(k) is necessary.

• ℓ ∞ : d = Ω(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 = Õ(poly(k)) suffices in ℓ p for p ≥ 1.