Consistency of the $k$-Nearest Neighbor Regressor under Complex Survey Designs

Caren Hasler

stat.MLMar 18, 2026

Consistency of the $k$ -Nearest Neighbor Regressor under Complex Survey Designs

Authors: Caren Hasler

Abstract

We study the consistency of the $k$ -nearest neighbor regressor under complex survey designs. While consistency results for this algorithm are well established for independent and identically distributed data, corresponding results for complex survey data are lacking. We show that the $k$ -nearest neighbor regressor is consistent under regularity conditions on the sampling design and the distribution of the data. We derive lower bounds for the rate of convergence and show that these bounds exhibit the curse of dimensionality, as in the independent and identically distributed setting. Empirical studies based on simulated and real data illustrate our theoretical findings.

Figures & tables

Panel of Figure 1 — Figure 1: Left panel: 15 population units (filled and empty dots), six sample units (filled dots), closed ball of radius $\rho_{4U}({\mathbf{x}})$ centered at ${\mathbf{x}}$ ( $B\left({\mathbf{x}},\rho_{4U}({\mathbf{x}})\right)$ , solid circle), and closed ball of radius $\rho_{4S}({\mathbf{x}})$ centered at ${\mathbf{x}}$ ( $B\left({\mathbf{x}},\rho_{4S}({\mathbf{x}})\right)$ , dashed circle). Right panel: six sample units (filled dots), partition of $\mathbb{R}^{2}$ obtained from the 4-nearest neighbors applied to sample units (polygons), labels of four nearest sample units of any point in a polygon (four-figure numbers within the polygons).

Panel of Figure 2 — Figure 2: Simulated data: maximum value of the ratio of the overall sampling fraction $f$ to the sampling fraction $f(x^{o}_{i})$ in the ball of radius $\rho_{k_{n}S}(x^{o}_{i})$ centered at $x^{o}_{i}$ over a sequence of values ${\mathbf{x}}^{o}$ in the support of the covariate. Different population sizes $N$ and sampling designs are considered. The sampling designs are proportional to size sampling (pps), simple random sampling without replacement (srswor), and stratified sampling (stratified).

Panel of Figure 3 — Figure 3: Simulated data: average value of $|r_{ij}|$ for different population sizes N.

Panel of Figure 4 — Figure 4: Simulated data: boxplots of the value of the MSE of the sample $k_{n}$ -nearest neighbors estimator $\widehat{m}_{n}(x^{o}_{i})$ , $i=1,\ldots,10$ for nine populations of respective size N. The dashed line is the value of $\frac{1}{k_{n}}+\frac{k_{n}}{n}$ for the nine populations (multiplied by 2.2 for graphical reasons).

Panel of Figure 5 — Figure 5: White Wine data: boxplots of the value of the MSE of the sample $k_{n}$ -nearest neighbors estimator $\widehat{m}_{n}({\mathbf{x}}^{o}_{i})$ , $i=1,\ldots,100$ for five populations of respective size N. The dashed line is the value of $\frac{1}{k_{n}}+\left(\frac{k_{n}}{n}\right)^{2/10}$ for the five populations (multiplied by 4.5 for graphical reasons).

k-Nearest Neighbors

k-Nearest Neighbors (k-NN) predicts or retrieves from nearby data points using local similarity for classification, regression, clustering, and uncertainty.

See all 32 papers

Nearest-Neighbor Radii under Dependent Sampling
May 14, 2026Yuanyuan Gao, Yilong Hou, Zhexiao Link-Nearest Neighbors
Department of Statistics, University of California, Berkeley, CA 94720, USA · Department of Biostatistics, University of California, Berkeley, CA 94720, USA
Conformal and kNN Predictive Uncertainty Quantification Algorithms in Metric Spaces
Jul 21, 2025Gábor Lugosi, Marcos MatabuenaConformal Prediction k-Nearest Neighbors
Department of Economics and Business, Pompeu Fabra University, Barcelona, Spain · ICREA, Pg. Lluís Companys 23, 08010 Barcelona, Spain · Barcelona Graduate School of Economics +3
Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees
Aug 26, 2026Caixing Wang, Zhibo Chen, Yue WangRandom Feature Methods Kernel Ridge Regression
School of Statistics and Data Science, Southeast University · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China

May 14, 2026J/K move · Enter open · S save

Nearest-Neighbor Radii under Dependent Sampling

Yuanyuan Gao, Yilong Hou, Zhexiao Lin

Department of Statistics, University of California, Berkeley, CA 94720, USA · Department of Biostatistics, University of California, Berkeley, CA 94720, USA

k-Nearest Neighbors

Open paper AskPDF arXiv

Nearest-neighbor methods are fundamental to classical and modern machine learning, yet their geometric properties are typically analyzed under independent sampling. In this paper, we study the nearest-neighbor radii under dependent sampling. We consider strong mixing dependent observations and ask whether dependence changes the scale of nearest-neighbor neighborhoods. We establish distribution-free almost sure convergence under polynomial mixing and sharp non-asymptotic moment bounds under geometric mixing. The moment bounds depend on the local intrinsic dimension rather than the ambient dimension, making the results applicable to high-dimensional data concentrated near lower-dimensional manifolds. Synthetic experiments and real-world time-series benchmarks support the theory, showing that nearest-neighbor geometry remains informative under dependence sampling.

Abstract

k-Nearest Neighbors

Explore similar work

Nearest-Neighbor Radii under Dependent Sampling

Conformal and kNN Predictive Uncertainty Quantification Algorithms in Metric Spaces

Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees