Embedding Dimension of Contrastive Learning and k-Nearest Neighbors

Dmitrii Avdiukhin, Vaggos Chatziafratis, Orr Fischer, G. Yaroslavtsev
2/3/2026

No confident code implementation found for this paper. 2 possible matches can be shown below.

Abstract

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:

DOISemantic Scholar

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 2 weaker matches are hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Cite this paper

@article{avdiukhin2026embedding,
  title  = {Embedding Dimension of Contrastive Learning and k-Nearest Neighbors},
  author = {Dmitrii Avdiukhin and Vaggos Chatziafratis and Orr Fischer and G. Yaroslavtsev},
  year   = {2026},
  doi    = {10.52202/079017-1309},
  url    = {https://doi.org/10.52202/079017-1309},
  journal = {NEURIPS 2024 2024}
}

Discussion