Research map / Learning theory and algorithms / Prediction and decision losses
Euclidean distance compression via deep random features
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.
Constructs random nonlinear maps as ℓ-fold compositions of random sign-feature maps that sketch point sets directly into the discrete cube, recovering squared distances up to (1±ε) error with fewer bits than Johnson-Lindenstrauss sketches in some regimes.
Problem
Compressing point sets into as few bits as possible while preserving pairwise squared distances up to multiplicative (1±ε) error, where standard random projection (Johnson-Lindenstrauss) produces real-valued sketches that need an extra quantization step.
Approach
Compose random sign-feature maps (random Gaussian hyperplane sign features) ℓ times; the expected inner product is iterated arcsine kernel f_ℓ, whose inverse g_ℓ has derivative vanishing near 1, so choosing ℓ ~ log log(1/m) yields multiplicative distance recovery with a sketch that lives directly in the discrete cube.
Key results
- Theorem gives sketch size N = Θ((log n/ε²)(log 1/m)^{2log2(π/√2)}) bits total Θ(n log n/ε² (log 1/m)^{2log2(π/√2)}), which beats JL's Θ(ε^{-2} n log n log(1/m²ε)) when (log 1/m)^{2log2(π/√2)} = o(log(1/ε)).
- Success probability at least (1-2/n)^ℓ with ℓ = O(log log d) under the stated assumptions, approaching one for useful parameters.
- Extension to the unit ball adds n log(1/(ρm²ε)) bits for storing norms and recovers squared distances with (1±ε) multiplicative error.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the deep random-feature map φℓ instead of Johnson–Lindenstrauss with epsilon-net encoding | Point-set distance sketches on the unit sphere · Unit-sphere point sets | sketch bits | Helped |
| Compose ℓ random sign-feature maps and store the approximate norms | Point-set distance sketches on the unit ball · Unit-ball point sets | squared-distance recovery | Helped |
| Increase the composition depth ℓ | Deep random-feature distance recovery · Point pairs with very small distance | approximation error | Helped |
| Increase the composition depth ℓ | Deep random-feature distance recovery · Point pairs with inner product close to zero | approximation accuracy | Hurt |
Surprising findings
- The sketch's bit count is within a power of log(1/m) of the known one-way communication lower bound, but the power 2log2(π/√2) is not optimal.
Limitations
- Purely theoretical with no experiments.
- Bit count has a power of log(1/m) above the communication lower bound.
- Requires ε < min(1-|<x,y>|) and only holds for point-by-point compression.
Experimental setup
Baselines: Johnson-Lindenstrauss random projection epsilon-net quantization
Builds on: Johnson-Lindenstrauss lemma random features
Closest papers by meaning
- Practical Data-Dependent Metric Compression with Provable Guarantees (NeurIPS 2017 · similarity 0.86)
- Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization (NeurIPS 2024 · similarity 0.84)
- Manifold Random Features (NeurIPS 2026 · similarity 0.83)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.83)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.83)
- Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry (NeurIPS 2025 · similarity 0.82)
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.