Research map / Learning theory and algorithms / Sample complexity
Quantized Random Projections and Non-Linear Estimation of Cosine Similarity
Ping Li, Michael Mitzenmacher, Martin Slawski
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase bits per projection b beyond 1 at fixed bit budget | quantized RP MLE · similarity rho < 0.2 (Fisher information analysis) | b*I_b^-1(rho) | No clear effect |
| increase b as target similarity rho grows | quantized RP MLE · rho > 0.98 | optimal b at fixed bit budget | Improved |
| use one-parameter uniform quantizer with saturation T instead of Lloyd-Max thresholds (ablation) | quantized RP MLE · high similarity rho (Figure 2) | inverse Fisher information ratio | Improved |
| increase b to 5 or more when comparing Lloyd-Max and uniform thresholds (ablation) | quantizer choice · Fisher information | inverse information | No clear effect |
| replace Hamming-distance estimator with the MLE (ablation) | quantized RP nearest neighbour search · Farm Ads and RCV1, b=2 | fraction of K=10 neighbours retrieved | No clear effect |
| replace Hamming-distance estimator with the MLE (ablation) | quantized RP nearest neighbour search · Farm Ads and RCV1, b>=4 | fraction of K=10 neighbours retrieved | Improved |
| use 1-bit quantization instead of higher-bit quantization | quantized RP nearest neighbour search · synthetic, Farm Ads, RCV1 | fraction of neighbours retrieved | Hurt |
| MLE on quantized data versus full-precision data with k as for b=6 | quantized RP · nearest neighbour search | fraction retrieved | No clear effect |
| choose b=2 for linear classification at fixed bit budget | SVM on MLE-estimated Gram matrix · Farm Ads | test accuracy | Improved |
| choose b=3 or 4 for linear classification at fixed bit budget | SVM on MLE-estimated Gram matrix · Arcene | test accuracy | Improved |
| use b>=5 bits | SVM on MLE-estimated Gram matrix · Farm Ads and Arcene | test accuracy | Hurt |
Closest papers by meaning
- Random Projections with Asymmetric Quantization (NeurIPS 2019 · similarity 0.93)
- Simple strategies for recovering inner products from coarsely quantized random projections (NeurIPS 2017 · similarity 0.90)
- Sign-Full Random Projections (AAAI 2019 · similarity 0.87)
- Quantization Algorithms for Random Fourier Features (ICML 2021 · similarity 0.87)
- Node Similarities under Random Projections: Limits and Pathological Cases (ICLR 2025 · similarity 0.86)
- Optimization Can Learn Johnson Lindenstrauss Embeddings (NeurIPS 2024 · similarity 0.84)
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.
