Research map / Learning theory and algorithms / Prediction and decision losses
Weighted distance nearest neighbor condensing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces weighted distance nearest neighbor (WNN) condensing, where condensed-set points carry weights that scale distances, proving it can condense far better than NN, giving near-NN generalization bounds, a greedy heuristic with Bayes consistency, and small empirical gains.
Problem
Nearest neighbor condensing: finding a small subset of a labeled sample that correctly classifies all sample points under the nearest neighbor rule, which is NP-hard and whose condensing limits are constrained by the unweighted rule.
Approach
Assign each condensed point a weight and define weighted distance as distance divided by the product of weights, so high-weight points gain influence on labeling; this yields circular/ball decision boundaries that allow far smaller consistent condensed sets than unweighted NN, with a greedy ball-cover-style heuristic.
Key results
- On circle, banana and iris the WNN heuristic yields condensed sets of 12, 35 and 4 points versus 52, 74 and 11 for MSS (and 45, 66, 9 for RSS), though the exact IP gives 7, 32 and 2.
- On notMNIST (UMAP to 3D), the greedy WNN heuristic achieves essentially the same test error as 1-NN while compressing the data by about 80%.
- Theory shows a family of instances where unweighted NN condensing needs Theta(n) points but WNN condenses to 2 points.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the WNN greedy heuristic instead of MSS | Condensing heuristic · Circle | condensed set size: 52 -> 12 | Helped |
| Use the WNN greedy heuristic instead of RSS | Condensing heuristic · Circle | condensed set size: 45 -> 12 | Helped |
| Use the WNN greedy heuristic instead of IP | Condensing heuristic · Circle | condensed set size: 7 -> 12 | Hurt |
| Use the WNN greedy heuristic instead of MSS | Condensing heuristic · Banana | condensed set size: 74 -> 35 | Helped |
| Use the WNN greedy heuristic instead of RSS | Condensing heuristic · Banana | condensed set size: 66 -> 35 | Helped |
| Use the WNN greedy heuristic instead of IP | Condensing heuristic · Banana | condensed set size: 32 -> 35 | Hurt |
| Use the WNN greedy heuristic instead of MSS | Condensing heuristic · Iris (Setosa and Versicolour) | condensed set size: 11 -> 4 | Helped |
| Use the WNN greedy heuristic instead of RSS | Condensing heuristic · Iris (Setosa and Versicolour) | condensed set size: 9 -> 4 | Helped |
| Use the WNN greedy heuristic instead of IP | Condensing heuristic · Iris (Setosa and Versicolour) | condensed set size: 2 -> 4 | Hurt |
| Use greedy WNN instead of standard 1-NN | notMNIST classifier · notMNIST test set | test error | No clear effect |
| Use greedy WNN instead of MSS | notMNIST classifier · notMNIST test set | test error | Helped |
| Use greedy WNN condensing | notMNIST classifier · notMNIST | compression ratio: approximately 80% | Helped |
Surprising findings
- The greedy WNN heuristic is slightly worse than the optimal unweighted IP solution on the small datasets, although it beats MSS and RSS on circle and banana in the sense of set size only for RSS/MSS comparisons (WNN is larger than RSS on circle and banana).
Limitations
- Empirical evaluation limited to small synthetic/iris datasets and one reduced-dimension notMNIST setting.
- Weighted distance may violate the triangle inequality, so standard metric search structures need modification.
- Bayes consistency of the greedy heuristic requires additional tail assumptions on the distribution.
Experimental setup
Datasets: banana circle iris notMNIST
Benchmarks: banana circle iris notMNIST
Metrics: condensed set size compression ratio test error
Baselines: MSS RSS integer program for NN condensing 1-NN
Builds on: navigating nets NET algorithm OptiNet MSS RSS
Closest papers by meaning
- An algorithm for L1 nearest neighbor search via monotonic embedding (NeurIPS 2016 · similarity 0.87)
- k*-Nearest Neighbors: From Global to Local (NeurIPS 2016 · similarity 0.87)
- Graph-based Nearest Neighbor Search: From Practice to Theory (ICML 2020 · similarity 0.86)
- An adaptive nearest neighbor rule for classification (NeurIPS 2019 · similarity 0.85)
- Learning Space Partitions for Nearest Neighbor Search (ICLR 2020 · similarity 0.85)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · 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.