Nearest Neighbors I
summary
K‑nearest neighbors is universally consistent when K → ∞ and K/N → 0, and regression rates scale like N^{-2/(2+D)} with the optimal K ≈ N^{2/(2+D)}, exposing the curse of dimensionality. One‑NN converges to 2η(1−η) (not Bayes); growing K recovers Bayes risk. A finite‑sample bound gives Risk ≤ R + μ(boundary_{P,Δ}) + δ with P ≈ K/N and Δ ≈ √(log(1/δ)/K). Analysis swaps geometric smoothness for a probability‑mass smoothness* tied to balls of mass ≈ K/N.
AI-written summary · about
chapters (28)
- 0:00Intro
- 1:20Talk Outline
- 2:14k Nearest Neighbors
- 3:46The Metric Space
- 5:19Tutorial Outline
- 5:39NN Regression Setting
- 7:27Universality
- 8:18More Formally...
- 9:15Intuition: Universal Consistency
- 13:56Convergence Rates
- 19:08k-NN Distances
- 21:34From Distances to Rates
- 21:44Bias-Variance Decomposition
- 23:02Bounding Bias and Variance
- 24:36Integrating across the space
- 26:54Nearest Neighbor Classification
- 27:29The Statistical Learning Framework
- 29:32The Bayes Optimal Classifier
- 31:33Consistency of I-NN
- 34:27Consistency under Continuity
- 35:16Proof Intuition
- 37:39Universal Consistency in Metric Spaces
- 39:08Main Idea in Prior Analysis
- 39:49A Motivating Example
- 43:01Effective Interiors and Boundaries
- 45:25Convergence Rate Theorem
- 55:18A Better Smoothness Condition
- 57:18Smoothness Bounds
related talks
40mFast NN Prediction with No Statistical Tradeoff
42mDistribution-Specific Analysis of Nearest Neighbor Search and Classification
48mSmooth Sensitivity for k-Nearest Neighbor
43mSpectral Approaches to Nearest Neighbor Search
01h 01mNearest Neighbor Methods II
01h 05mNearest Neighbor Methods I
46mSpectral Partitioning for Metrics (And NNs Too)
40mEfficient Reductions for k-Nearest Neighbor Search