Research map / Learning theory and algorithms / Prediction and decision losses
Rates of Convergence for Large-scale Nearest Neighbor Classification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Divide the training data into partitions and aggregate local kNN predictions by majority vote | kNN classification · Binary classification under smoothness and margin assumptions | excess risk convergence rate: N^{-α(β+1)/(2α+1)} | No clear effect |
| Use bigNN instead of centralized oracle kNN | kNN classification · Simulation 1 | prediction time | Helped |
| Increase the partitioning rate to γ≥0.4 | bigNN · Credit | risk | Hurt |
| Pre-train labels using bigNN and predict with 1-NN on smaller subsamples | bigNN · Simulation 3 | prediction time | Helped |
| Use small prediction subsamples for denoised bigNN | denoised bigNN · Simulation 3 | regret | Hurt |
| Fix the neighbor count at k=5 instead of scaling it with sample size and partitions (ablation) | bigNN · Simulation 2 | regret convergence rate: O(N^{-γ(1+β)/2}) | Mixed |
| Vary the number of prediction subsampling repeats I (ablation) | denoised bigNN · Simulation 3 | regret | No clear effect |
Closest papers by meaning
- Statistical Guarantees of Distributed Nearest Neighbor Classification (NeurIPS 2020 · similarity 0.91)
- An adaptive nearest neighbor rule for classification (NeurIPS 2019 · similarity 0.89)
- On Convergence of Nearest Neighbor Classifiers over Feature Transformations (NeurIPS 2020 · similarity 0.89)
- Doubly Approximate Nearest Neighbor Classification (AAAI 2018 · similarity 0.88)
- k*-Nearest Neighbors: From Global to Local (NeurIPS 2016 · similarity 0.87)
- DNNR: Differential Nearest Neighbors Regression (ICML 2022 · similarity 0.87)
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.