Research map / Learning theory and algorithms / Sample complexity
Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies the smallest ℓp embedding dimension for contrastive triplet constraints and k-nearest-neighbor orderings, giving upper and lower bounds via graph arboricity, with tight Θ(√m) bounds in ℓ2 and experiments on CIFAR.
Problem
Given distance-comparison data (contrastive triplets or k-NN orderings over n points), determine the smallest dimension d of an ℓp space that can represent all the comparisons.
Approach
Relates the embedding dimension to the arboricity of the constraint graph: sparse constraint graphs (low arboricity) admit low-dimensional embeddings, and the k-NN constraint graph has arboricity at most k+1, yielding O(k) dimension in ℓ2 and polynomial-in-k bounds in ℓp, including a construction that preserves the k-NN sets themselves.
Key results
- In ℓ2, the constructed embedding has dimension O(√m) and the paper proves a matching Ω(√m) lower bound for contrastive constraints.
- Experiments with ResNet-18 on CIFAR-10 show ≥99% of triplets satisfied when d ≥ √m, dropping to about 93% for m in {10^5, 10^6} with d well below √m.
- For k-NN ordering preservation in ℓ2 the paper gives a tight Θ(k) bound; in ℓp the bound is Õ(k^2) for ordering and Õ(poly(k)) for full k-NN preservation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase embedding dimension from 64 to 256 | ResNet-18 trained on contrastive samples · CIFAR-10 and CIFAR-100 | accuracy: 2% accuracy increase | Helped |
| increase embedding dimension from 256 to 1024 | ResNet-18 trained on contrastive samples · CIFAR-10 and CIFAR-100 | accuracy | No clear effect |
| increase the number of contrastive samples to m ∈ {105, 106} while using d = 128 | ResNet-18 trained with triplet loss · CIFAR-10 and CIFAR-100 | satisfied samples: 99% to 93% | Hurt |
Surprising findings
- Preserving the full k-NN sets in ℓp needs only polylogarithmic dependence on n (poly(k) dimension), despite the k-NN constraints corresponding to n(n-1) triplets.
Limitations
- Upper bounds for k-NN in ℓp carry large polylogarithmic and polynomial-in-k factors (Õ(k^10) in the original version, later improved to Õ(k^3)).
- Experiments use a single dataset pair (CIFAR-10/100) with ResNet-18 and synthetic labels from a pretrained network, so they only loosely test the theory.
- Data-dependent bounds beyond arboricity are not captured.
Experimental setup
Datasets: CIFAR-10 CIFAR-100
Benchmarks: CIFAR-10 contrastive triplets CIFAR-100 contrastive triplets CIFAR k-NN preservation
Metrics: fraction of satisfied contrastive triplets k-NN rank-change loss
Baselines: Chen and Indyk 2024 (CI24) lower bound Fischer et al. 2020 (FIM+20)
Builds on: triplet loss Frechet embedding design-based random construction (DKS12) Fact on graph arboricity (Nash-Williams)
Closest papers by meaning
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.89)
- On the Similarities of Embeddings in Contrastive Learning (ICML 2025 · similarity 0.87)
- The Complexity of Finding Local Optima in Contrastive Learning (NeurIPS 2025 · similarity 0.87)
- Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings (ICML 2025 · similarity 0.86)
- Sparse Dimensionality Reduction Revisited (ICML 2024 · similarity 0.85)
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.