Research map / Learning theory and algorithms / Prediction and decision losses
Online Consistency of the Nearest Neighbor Rule
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.
Proves online consistency of the 1-nearest neighbor rule for all measurable labelings in upper doubling metric measure spaces when instances come from uniformly absolutely continuous (uniformly dominated) processes, and for negligible-boundary labelings under ergodically dominated processes.
Problem
Online classification with the nearest neighbor rule is known to be consistent only under i.i.d. instances or uniform class separation; the question is when it stays online consistent for non-i.i.d. instance streams and general label functions.
Approach
Shows that mutually-labeling balls cover almost all of the space for negligible-boundary labels, giving monotone progress; introduces ergodically dominated and uniformly dominated processes; in upper doubling spaces, proves nearest-neighbor processes inherit ergodic domination via a cover-tree decomposition, yielding universal consistency.
Key results
- Nearest neighbor rule is online consistent for all measurable labelings on upper doubling spaces when instances are uniformly dominated (Universal consistency theorem).
- Nearest neighbor processes are ergodically dominated at rate O(epsilon(delta) log(1/delta)) when the instance process is uniformly dominated in an upper doubling space.
- For negligible-boundary label functions, the nearest neighbor rule is online consistent under ergodically dominated processes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require ergodic domination of the instance process and a label function with negligible boundary | 1-nearest neighbor · Realizable online classification | asymptotic mistake rate: 0 | Helped |
| Require a uniformly dominated instance process and an upper doubling metric measure space | 1-nearest neighbor · Realizable online classification, any measurable label function | asymptotic mistake rate: 0 | Helped |
| Use an arbitrary instance sequence when classes have no positive separation | 1-nearest neighbor · Worst-case online classification | asymptotic mistake rate: ≥ 1/2 | Hurt |
Surprising findings
- Ergodic domination alone is insufficient for universal consistency; a known counterexample on [0,1] shows the nearest neighbor rule can fail even with ergodically dominated processes and small-boundary labels.
Limitations
- Universal consistency result requires upper doubling metric measure space and uniform domination assumptions.
- Rates of convergence given only for smoothed processes in doubling spaces and under stronger assumptions.
Experimental setup
Metrics: asymptotic mistake rate
Builds on: Cover trees Smoothed online learning Optimistic universal learning Lebesgue differentiation theorem
Closest papers by meaning
- Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning (NeurIPS 2025 · similarity 0.82)
- Computable universal online learning (NeurIPS 2025 · similarity 0.82)
- Multiclass Transductive Online Learning (NeurIPS 2024 · similarity 0.82)
- Online Bernstein-von Mises theorem (NeurIPS 2026 · similarity 0.82)
- Online Classification with Predictions (NeurIPS 2024 · similarity 0.81)
- Optimal Mistake Bounds for Transductive Online Learning (NeurIPS 2025 · similarity 0.81)
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.