PaperlayerView exact revision on arXiv

Source-linked AI summary

Is the k-NN classifier in high dimensions affected by the curse of dimensionality?

Vladimir Pestov

arXiv:1110.4347v3stat.ML

TL;DR

The paper asks whether the curse affecting exact nearest-neighbor search also affects k-NN learning algorithms. The paper analyzes a k-approximate-nearest-neighbor classifier and a Borel-isomorphic reduction approach to dimensionality reduction. The k-ANN classifier is consistent under absolute continuity but requires exponentially many datapoints to maintain consistency in high dimensions; a Borel-isomorphic transport preserves k-NN consistency under the stated universal-consistency hypothesis.

  • Problem

    The paper asks whether the curse affecting exact nearest-neighbor search also affects k-NN learning algorithms.

    Source: §1 · p. 2

  • Method

    The paper analyzes a k-approximate-nearest-neighbor classifier and a Borel-isomorphic reduction approach to dimensionality reduction.

    Source: §1 · p. 3, §8 · p. 19

  • Results

    The k-ANN classifier is consistent under absolute continuity but requires exponentially many datapoints to maintain consistency in high dimensions; a Borel-isomorphic transport preserves k-NN consistency under the stated universal-consistency hypothesis.

    Source: §1 · pp. 3–4, §7.2 · p. 19

  • Takeaways & Limitations

    For data sampled randomly from high-dimensional distributions, switching to the ANN classifier does not lift the curse of dimensionality.

    Source: §1 · p. 4

    The k-ANN classifier has not been tested in practice, and its consistency result assumes absolute continuity of the data distribution.

    Source: §5.1 · p. 10, §6 · p. 14

Abstract

from arXiv · show

There is an increasing body of evidence suggesting that exact nearest neighbour search in high-dimensional spaces is affected by the curse of dimensionality at a fundamental level. Does it necessarily mean that the same is true for k nearest neighbours based learning algorithms such as the k-NN classifier? We analyse this question at a number of levels and show that the answer is different at each of them. As our first main observation, we show the consistency of a k approximate nearest neighbour classifier. However, the performance of the classifier in very high dimensions is provably unstable. As our second main observation, we point out that the existing model for statistical learning is oblivious of dimension of the domain and so every learning problem admits a universally consistent deterministic reduction to the one-dimensional case by means of a Borel isomorphism.

1. Introduction

The introduction asks whether the curse affecting exact nearest-neighbor search also applies to k-NN learning. It presents different answers across levels: approximate-neighbor classification is consistent, but high-dimensional performance is unstable, while Borel isomorphic reduction offers a separate theoretical route.

1. Introduction

  • If the curse-of-dimensionality conjecture holds, exact neighbor retrieval could make k-NN impractical for large, high-dimensional datasets.The conjecture concerns polynomial-time exact search without superpolynomial storage.Source: §1 · pp. 2–3
  • The proposed k-ANN classifier is consistent under the assumption that the data distribution is absolutely continuous.The authors describe this as a partial extension of Stone’s consistency theorem.Source: §1 · p. 3
  • In the high-dimensional limit, maintaining k-ANN consistency requires the number of datapoints to grow exponentially with dimension.The authors characterize this sample-size assumption as unrealistic and conclude that ANN does not lift the curse in this theoretical setting.Source: §1 · pp. 3–4
  • Borel isomorphisms between Euclidean or infinite-dimensional spaces and the real line can be managed algorithmically, despite possibly being discontinuous everywhere.The authors present this as an algorithmic data-analysis use of Borel structure.Source: §1 · p. 4
  • The practical significance of Borel reduction remains uncertain because it has been tested only on a few toy UCI datasets.The authors note encouraging results but leave the broader practical significance open.Source: §1 · p. 4

2. Stone’s theorem

This section states the statistical-learning model and recalls Stone’s consistency theorem for k-NN in Euclidean space. It also notes that the result does not extend to all metric spaces and describes related density-theorem results.

2. Stone’s theorem

  • The learning model treats observations as i.i.d. data-label pairs and defines consistency by convergence of learning error to Bayes error in probability.Almost-sure convergence is called strong consistency; consistency under every probability measure is universal consistency.Source: §2 · p. 5
  • Stone’s theorem gives universal consistency for k-NN in R^d when k tends to infinity and k/n tends to zero.The theorem is stated for Euclidean distance.Source: §2 · p. 6
  • Stone’s theorem fails in more general metric spaces, including ℓ2, where a deterministic concept can remain unlearned under a Gaussian distribution.The passage points to an example based on a construction of Preiss.Source: §2 · p. 6
  • Universal k-NN consistency is known in metric spaces satisfying the Lebesgue–Besikovitch density theorem, characterized as sigma-finite dimensional.The authors identify a formal equivalence between universal consistency and that density theorem as an open question.Source: §2 · p. 6

3. Exact similarity search

The section frames exact nearest-neighbour search as a similarity-workload problem and presents a conjectured lower bound for high-dimensional data structures. Existing lower bounds are established for some specific indexing schemes, but the general conjecture remains unproven.

3. Exact similarity search

  • A similarity workload consists of a metric space and dataset, with queries asking for nearby points; access methods answer these queries, often using indexing schemes.A k-nearest-neighbour query can be reduced by binary search to a sequence of ε-range queries.Source: §3 · pp. 6–7
  • The general conjecture remains open, although superpolynomial-in-d lower bounds have been proved for pivot-based schemes and metric trees.The best lower bound stated for polynomial-space data structures is Ω(d / log n).Source: §3 · p. 7
  • The curse-of-dimensionality conjecture says that, for specified intermediate growth of n relative to d, exact search with d^O(1) query time requires n^ω(1) space in the cell-probe model.The stated setting is the Hamming cube with Hamming distance.Source: §3 · p. 7

4. Approximate similarity search

Approximate nearest-neighbour search admits more efficient indexing schemes than exact search, and the section describes how to adapt such schemes to return one or k approximate neighbours. A random-binary-matrix scheme uses lower-dimensional hashing, with the k-neighbour variant taking O(dk poly log(dn)) query time.

4. Approximate similarity search

  • A (c, ε)-ANN query returns a point within (1 + c)ε of the query’s nearest-neighbour distance, when that distance is at most ε.Source: §4 · p. 7
  • Known approximate nearest-neighbour indexing schemes are more efficient than exact nearest-neighbour schemes.Source: §4 · p. 7
  • The (k, c)-ANN problem returns k datapoints within (1 + c) times the radius of the query’s kth nearest neighbour.Source: §4 · pp. 7–8
  • A random-binary-matrix scheme hashes points into a lower-dimensional Hamming cube, where nearest neighbours are retrieved; its k-ANN adaptation runs in O(dk poly log(dn)) time.The map preserves distances at a selected scale with constant confidence, and the k-ANN variant stores k neighbours per hash table entry.Source: §4 · pp. 8–9

5. The k approximate nearest neighbour classifier

This section extends Stone’s consistency result to a classifier that votes over k approximate nearest neighbours. Under absolute continuity and the stated growth conditions on k, the classifier is consistent, regardless of whether the ANN-query procedure is randomized or adversarially chosen.

5.1. Definition and statement of result

  • The (k, c)-ANN classifier predicts by majority vote among the k approximate neighbours returned by an indexing scheme.Source: §5 · p. 9, §5.1 · p. 9
  • With an absolutely continuous data distribution, the (k, c)-ANN classifier is consistent, even if an adversary aware of the distribution selects the approximate neighbours.Such a choice may slow the convergence rate; the authors do not know whether absolute continuity can be dropped or whether k must grow faster than log n.Source: §5.1 · p. 10

5.2. A variation on Stone’s theorem

  • A weighted-majority classification rule is consistent under absolute continuity when its nonnegative data-dependent weights sum to one and satisfy the theorem’s stated conditions.Source: §5.2 · pp. 10–11

5.3. Proof of Theorem 5.1

  • The proof applies the weighted theorem using equal weights on the returned k approximate neighbours and zero weights elsewhere.It uses shrinking k-neighbour radii and the Lebesgue differentiation theorem to verify the required conditions.Source: §5.3 · p. 12
  • A Stone-lemma bound controls how many query points can have a given sample point among their k approximate neighbours, supporting the proof’s weight control.Source: §5.3 · p. 13

6. Query instability in high dimensions

The k-ANN classifier has not been tested in practice, and its high-dimensional performance can be unstable in theory. Under certain high-dimensional distribution assumptions, maintaining consistency requires exponentially growing datasets, while expanded neighbor balls can contain far more than k points.

6. Query instability in high dimensions

  • In the high-dimensional limit, maintaining k-ANN classifier consistency requires the number of datapoints to grow exponentially with dimension.The paper links this to the expanded ball containing far more than k points, so the oracle's selected labels could be highly biased.Source: §6 · p. 14
  • For k = 20 and c = 0.5, the expanded ball contains an average of 60 Segment datapoints versus 1,742 for Gaussian data in dimension 14.The paper characterizes Segment as relatively low intrinsic dimension and the Gaussian data as medium intrinsic dimension.Source: §6 · pp. 14–15
  • A query is c-unstable when its ball of radius (1 + c)εNN(q) contains at least half of all datapoints.Figure 5 is identified as depicting query instability.Source: §6 · p. 15, Figure 5 · p. 15
  • With subexponential dataset growth and an intrinsic high-dimensionality assumption, most queries become (1 + c)-unstable, and the k-ANN classifier can become meaningless as Bayes error approaches 1/2.The paper says the exponential dataset-size growth needed in some theoretical settings is unrealistic.Source: §6 · p. 15

7. Borel dimensionality reduction

The section uses Borel structure to motivate dimension reduction for statistical learning. Because Borel isomorphisms preserve that structure, a learning problem can be transported to a one-dimensional setting while retaining universal consistency under the stated conditions.

7. Borel dimensionality reduction

  • Descriptive set theory provides a route to dimensionality reduction in non-parametric classification by focusing on the Borel structure of the domain.The section re-examines the standard statistical classification setting for this purpose.Source: §7 · p. 16

7.1. Borel sets, mappings, and isomorphisms

  • A Borel isomorphism is a bijective Borel mapping with a Borel inverse; complete metric spaces of the same cardinality, including Euclidean spaces and separable Hilbert space, are Borel isomorphic.The interval and square example interlaces the binary expansions of their coordinates.Source: §7.1 · pp. 16–17

7.2. Borel isomorphic dimension reduction

  • Transporting the metric through a Borel isomorphism to a space where k-NN is universally consistent yields a universally consistent k-NN rule on the original standard Borel space.The paper states that such a reduction is always possible from Rd to d = 1 and also applies to arbitrary separable metric spaces, including functional data settings.Source: §7.2 · pp. 17–19

8. Discussion

The discussion revisits the two proposed dimensionality-reduction approaches, their preliminary practical reach, and the question of what dimension should mean in statistical learning.

8. Discussion

  • The proposed Borel reduction differs from random-projection approaches, since projections are not Borel isomorphisms.The paper identifies a combination of k-NN and random projections as the closest literature counterpart.Source: §8 · pp. 19–20
  • The Borel reduction is easy to implement, but high-dimensional input may require floating-point arithmetic; an implemented and tested approximate-classifier account is forthcoming.The authors invite readers to try the Borel reduction.Source: §8 · p. 20
  • The UCI experiments show that Borel reduction succeeds for some datasets and fails for others.The table compares k-NN classification before and after reduction using k=1–20 and 10-fold cross-validation.Source: §8 · p. 20, Table 1 · p. 20
  • The authors suggest reducing dimension by grouping coordinates and applying a Borel isomorphism from each group to R, while seeking optimal reductions through a capacity theory.They frame this as a realistic possibility rather than a panacea for the curse of dimensionality.Source: §8 · p. 20
  • The discussion asks whether statistical learning needs a satisfactory theory of intrinsic data dimension.It raises this as an open question for explaining the curse of dimensionality.Source: §8 · pp. 20–21
  • A useful notion of dimension should reflect target-classifier complexity, including the isoperimetric behavior of the target concept, rather than domain dimension alone.A fast-growing isoperimetric function reflects high margin complexity and difficulty finding a classifier.Source: §8 · p. 21
Loading 1110.4347v3…