Fast NN Prediction with No Statistical Tradeoff

on YouTube ↗40m

" summary

Claims that K nearest-neighbor accuracy (with optimal K ~ sqrt(n)) is attainable in O(log n) prediction time by reducing the dataset via quantization or subsampling and applying a simple variance correction that replaces each stored label by a local average (a denoising precompute). Quantization matches accuracy but can cost up to N^2 to build; subsampling (many m-sized bags, empirically m ≈ 10% of n) with denoising gives near-KNN risk while yielding measured speedups of about 2–8×, all via a variance correction on stored labels.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 3:22Statistical Performance
3. 6:18Prediction with No Tradeoff
4. 8:15Outline
5. 12:50Intuition
6. 18:40Guarantees
7. 23:45Subsampling
8. 29:10Variance correction

" related talks

• 01h 08mNearest Neighbors IKamalika Chaudhuri · Deep Learning Boot Camp 2019
• 01h 05mNearest Neighbors IIKamalika Chaudhuri · Deep Learning Boot Camp 2019
• 42mDistribution-Specific Analysis of Nearest Neighbor Search and ClassificationSanjoy Dasgupta · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 43mSpectral Approaches to Nearest Neighbor SearchRobert Krauthgamer · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 48mSmooth Sensitivity for k-Nearest NeighborChristopher Clifton · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)
• 40mTools and Tricks from a Pragmatic Data ScientistLucas Javier Bernardi · PyData Amsterdam 2016
• 49mSpectral Approaches to Nearest Neighbor SearchAlexandr Andoni · Spectral Algorithms: From Theory to Practice 2014
• 01h 22mGeneralization IVPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019