k-NN Regression Adapts to Local Intrinsic Dimension

By Samory Kpotufe. 2011

141 citations recorded by the source corpus.

Many nonparametric regressors were recently shown to converge at rates that depend only on the intrinsic dimension of data. These regressors thus escape the curse of dimension when high-dimensional data has low intrinsic dimension (e.g. a manifold). We show that k-NN regression is also adaptive to intrinsic dimension. In particular our rates are local to a query x and depend only on the way masses of balls centered at x vary with radius. Furthermore, we show a simple way to choose k = k(x) locally at any x so as to nearly achieve the minimax rate at x in terms of the unknown intrinsic dimension in the vicinity of x. We also establish that the minimax rate does not depend on a particular choice of metric space or distribution, but rather that this minimax rate holds for any metric space and doubling measure.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “…of research employs kernel density estimation (KDE) to perform regression on distributions with consistency guarantee (under the assumption that the true regressor is Hölder continuous, and the meta distribution have finite doubling dimension (Kpotufe 2011)) (Póczos et al. 2013, Oliva et al. 2014).”
Distribution-Free Distribution Regression (2013, background): “Following Kpotufe [2011], we say that P is a doubling measure with effective dimension d if, for every r > 0 and 0 < < 1, P(B(s, r)) P(B(s, r)) ≤ (c )d , ∀s.”
Gradient Weights help Nonparametric Regressors (2012, unknown): “The first two datasets describe the dynamics of 7 degrees of freedom of robotic arms, Barrett WAM and SARCOS [9, 10].”
Nonparametric Conditional Density Estimation in a High-Dimensional Regression Setting (2016, unknown): “Indeed, our empirical experiments indicate that spectral series (with approximate eigenvectors) perform better or as well as the nearest neighbor method which is minimax optimal in regression (Kpotufe 2011).”
Distribution to Distribution Regression (2013, methodology): “Following (Kpotufe, 2011), we look to control the effective dimension through the doubling dimension.”
Converting High-Dimensional Regression to High-Dimensional Conditional Density Estimation (2017, methodology): “For example, in a setting with submanifold structure, our estimator adapts to the intrinsic dimensionality of the data with a suitably chosen regression method; such as, nearest neighbors, local linear, tree-based or spectral series regression [4, 33, 34, 36].”
Toward enhanced understanding and projections of climate extremes using physics-guided data mining techniques (2014, background): “Dimensionality reduction techniques that utilize manifold, atomic, and topological structures derived directly from physical laws (Kpotufe, 2009, 2011; Balakrishnan et al., 2013a, b; Kpotufe and Garg, 2013; Lum et al., 2013; Wang et al., 2014) at once could make the prediction problem both more…”
Two-stage sampled learning theory on distributions (2014, methodology): “Using the classical bias-variance decomposition analysis for kernel regressors, they show the consistency of the constructed kernel regressor, and provide a polynomial upper bound on the rates, assuming the true regressor to be Hölder continuous, and the meta distribution that generates the covariat”