Abstract
We derive high-probability finite-sample uniform rates of consistency for $k$-NN regression that are optimal up to logarithmic factors under mild assumptions. We moreover show that $k$-NN regression adapts to an unknown lower intrinsic dimension automatically. We then apply the $k$-NN regression rates to establish new results about estimating the level sets and global maxima of a function from noisy observations.
Introduction
While $k$-nearest neighbor ($k$-NN) regression is a cornerstone of nonparametric statistics, theoretical understanding of its performance has historically been bifurcated. Most existing consistency results focus on "average" error metrics, such as Mean Squared Error, or describe asymptotic behavior as the sample size $n$ approaches infinity. However, these perspectives often fail to characterize the "worst-case" error across a specific, finite dataset—a critical requirement for high-stakes applications like level set estimation or global optimization.
This paper addresses this gap by providing the first finite-sample, high-probability uniform (sup-norm) consistency rates for $k$-NN regression. Crucially, the analysis demonstrates that $k$-NN automatically adapts to the intrinsic dimension of the data, circumventing the "curse of dimensionality" when data resides on a lower-dimensional manifold.
Theoretical Framework
The paper establishes new upper bounds for the error $|f_k(x) - f(x)|$ that hold uniformly across the entire input space. The derivation relies on several key technical components:
- VC-type Concentration Bounds: These are employed to demonstrate that the $k$-NN radius remains within a predictable, stable range across the entire dataset.
- Bias-Variance Decomposition: The total error is decomposed into a "bias" term (representing the variation of the underlying function within the $k$-NN radius) and a "variance" term (representing the impact of noise in the observations).
- Geometric Partitioning: To achieve uniform results, the author utilizes a partitioning strategy that divides the space into regions where the set of $k$-nearest neighbors remains constant.
- Manifold Regularity: By incorporating standard manifold learning assumptions (such as condition numbers and reach), the analysis proves that the algorithm effectively "sees" the lower-dimensional structure of the data without explicit dimensionality reduction.
Key Insights and Results
Sup-Norm Optimality
The derived rates match the "minimax optimal" rate—the theoretical best possible rate any algorithm could achieve—up to logarithmic factors. This confirms that $k$-NN is a near-optimal tool for uniform function estimation.
Automatic Adaptation to Intrinsic Dimension
A significant finding is that $k$-NN does not require prior knowledge of the intrinsic dimension $d$ to exploit it. The algorithm naturally adjusts its neighborhood size based on local density, effectively collapsing the problem from the ambient dimension $D$ to the intrinsic dimension $d$.
Specifically:
- For an $\alpha$-Hölder continuous function in $D$ dimensions, the error is bounded by $\tilde{O}(n^{-\alpha/(2\alpha+D)})$.
- If the data lies on a $d$-dimensional manifold, the rate improves to $\tilde{O}(n^{-\alpha/(2\alpha+d)})$.
Plug-and-Play Applications
Because the paper provides a strong uniform bound on the function estimate, these results can be directly applied to other statistical tasks:
- Level Set Estimation: The paper provides a finite-sample rate for the Hausdorff distance between true level sets and their estimates, which is vital for identifying regions where a function exceeds a specific threshold.
- Global Maxima Estimation: The error in estimating a global maximum $x_0$ is shown to be approximately $O(n^{-1/(4+D)})$, matching known minimax rates for mode estimation.
Discussion and Limitations
While this work provides robust theoretical guarantees, certain practical considerations remain. The results assume "sub-Gaussian" noise; while this covers many standard scenarios, it may not account for heavy-tailed outliers. Additionally, while the statistical rates are optimal, the computational cost of $k$-NN in high dimensions remains a challenge, often requiring specialized data structures for efficiency. Finally, the current analysis assumes a fixed $k$ across the space; future research may explore whether locally varying $k$ based on density could further refine these uniform rates.
Summary updated