cs.LGOct 30, 2026

On k-nearest-neighbor regression in metric spaces

Authors: László Györfi, Vladimir G. Pestov, Harro Walk, Roi Weiss

Abstract

We study mean squared consistency of k-nearest-neighbor regression for metric space valued features. For a fixed feature distribution mu with atomless distance distributions, we describe how neighbor selection redistributes probability through the density of a uniformly chosen neighbor of an independent query. This gives separate conditions for the approximation error and the conditional response variance, and weakens Stone's domination condition when stronger response moments are available. In particular, when k_n tends to infinity and k_n/n tends to zero, a uniform L2(mu) bound on the selection densities suffices under a finite fourth response moment. We give a corresponding condition in terms of neighborhoods of fixed population mass and recover the Euclidean density bound. Finite global Nagata dimension gives Stone's domination. While sigma-finite Nagata dimensionality is known to ensure universal consistency of k-NN classification in complete separable spaces, we show that this is not the case for mean squared consistency with unbounded responses: we construct a space in this class on which one fixed noiseless response with all finite moments has diverging mean squared error.

Explore similar work

Mar 18, 2026

Consistency of the kk-Nearest Neighbor Regressor under Complex Survey Designs

We study the consistency of the kk-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 kk-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.
Jul 21, 2025

Conformal and kNN Predictive Uncertainty Quantification Algorithms in Metric Spaces

This paper introduces a framework for uncertainty quantification in regression models defined on metric spaces. Using a proposed notion of homoscedasticity, we define a conformal prediction algorithm that provides finite-sample marginal coverage guarantees and fast convergence rates to the oracle prediction region. For heteroscedastic settings, we introduce a kNN procedure that yields locally adaptive prediction radii in general metric spaces. Although this procedure does not provide the same finite-sample guarantees as the conformal algorithm, it is designed to improve local coverage calibration without imposing smoothing assumptions. Both procedures are compatible with a broad range of regression algorithms and scale to large datasets, allowing practitioners to use their preferred models and incorporate domain-specific knowledge. Building on the heteroscedastic kkNN approach, we also develop a flexible sequential extension for metric-space-valued time series based on nearest-neighbor expert aggregation. We establish the consistency of the proposed estimators under minimal conditions. Finally, we illustrate the practical utility of our framework in personalized medicine applications involving random objects such as probability distributions and graph Laplacians.
Nov 1, 2026

Convex Regression at Scale: Geometry-Preserving Constraint Sparsification

Convex regression provides a flexible nonparametric estimation framework while incorporating appropriate shape information. However, its standard least-squares formulation has O(n2)O(n^2) supporting-hyperplane constraints creating a computational bottleneck as the sample size nn increases. We study a KK-nearest-neighbor (KNN) localized relaxation for convex regression where we for each sample, we only maintain the KK nearest hyperplane constraints. Under mild regularity conditions, we establish statistical guarantees for our modified estimator in every fixed dimension d≥2d\ge2. In particular, for d>4d>4, the population risk of our modified problem can be shown to have equivalent convergence rates as the original least square convex regression estimator of O~(n−2/d)\widetilde O(n^{-2/d}) using neighborhoods sizes (i.e. K=KnK=K_n) of order O~(n2(d−1)/(2d−1))\widetilde O(n^{2(d-1)/(2d-1)}) for general convex functions and O~(n(d+1)/(d+2))\widetilde O(n^{(d+1)/(d+2)}) for strongly convex functions. To corroborate our theory, we implement iterative optimization methods to compare the prediction accuracy of the KNN relaxation with those of the full estimator across synthetic convex benchmarks. Our experiments demonstrate that KNN prediction risk approaches the full-estimator prediction risk at neighborhood sizes matching the theoretical scale.