AI Paper Atlas

Research map / Learning theory and algorithms / Sample complexity

Quantized Random Projections and Non-Linear Estimation of Cosine Similarity

Ping Li, Michael Mitzenmacher, Martin Slawski

NeurIPS 2016 · Learning theory and algorithms › Sample complexity · approach: Density and property estimation

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 changedWhereMeasuredEffect
increase bits per projection b beyond 1 at fixed bit budgetquantized RP MLE · similarity rho < 0.2 (Fisher information analysis)b*I_b^-1(rho)No clear effect
increase b as target similarity rho growsquantized RP MLE · rho > 0.98optimal b at fixed bit budgetImproved
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 ratioImproved
increase b to 5 or more when comparing Lloyd-Max and uniform thresholds (ablation)quantizer choice · Fisher informationinverse informationNo clear effect
replace Hamming-distance estimator with the MLE (ablation)quantized RP nearest neighbour search · Farm Ads and RCV1, b=2fraction of K=10 neighbours retrievedNo clear effect
replace Hamming-distance estimator with the MLE (ablation)quantized RP nearest neighbour search · Farm Ads and RCV1, b>=4fraction of K=10 neighbours retrievedImproved
use 1-bit quantization instead of higher-bit quantizationquantized RP nearest neighbour search · synthetic, Farm Ads, RCV1fraction of neighbours retrievedHurt
MLE on quantized data versus full-precision data with k as for b=6quantized RP · nearest neighbour searchfraction retrievedNo clear effect
choose b=2 for linear classification at fixed bit budgetSVM on MLE-estimated Gram matrix · Farm Adstest accuracyImproved
choose b=3 or 4 for linear classification at fixed bit budgetSVM on MLE-estimated Gram matrix · Arcenetest accuracyImproved
use b>=5 bitsSVM on MLE-estimated Gram matrix · Farm Ads and Arcenetest accuracyHurt

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy