Analysis of 1-NN Rule

The Data Requirement Surprise

Adding dimensions to a data point may sound like adding only a few more measurements. In the analysis of the 1-NN rule, however, each additional dimension affects how many training examples are needed. The required sample size can grow exponentially with the Euclidean dimension d, not merely proportionally. This is the curse of dimensionality: the learning problem can become difficult because the data space has gained dimensions, even though the learning rule itself has not changed.

Coverage in Higher Dimensions

The 1-NN rule predicts using a nearby training example. Therefore, reliable prediction depends on having training examples that provide adequate coverage of the data space. In this analysis, increasing d changes the sample-size requirement exponentially. The key issue is not simply that there are a few extra measurements. The geometry of the higher-dimensional space makes the number of examples needed to control the relevant error term grow much more rapidly.

The Error-Bound Ingredients

The NN-rule analysis uses two key quantities: a Lipschitz coefficient c and the Euclidean dimension d. The coefficient c controls how rapidly the function's output may vary when the input changes. A larger c permits more rapid output variation relative to changes in the input. The dimension d controls the severity of the sample-size growth. Thus, the coefficient describes the smoothness burden, while dimension determines how strongly the required training size escalates.

m ≥ (4c√d/ε)^(d+1)

Reading the Exponent

This condition should not be treated as a numerical recipe that applies with exactly the same constants to every learning problem. Its instructional purpose is to expose the mechanism of the curse of dimensionality. Dimension does more than add a factor to the calculation: it appears in the base through √d and in the exponent through d + 1.

The Lower-Bound Barrier

The exponential requirement is not presented only as a potentially loose upper-bound calculation for the 1-NN rule. Theorem 19.4 gives a lower-bound result. For any c greater than 1 and every learning rule L, there is a distribution over [0,1]^d × {0,1} whose η is c-Lipschitz and whose Bayes error is 0, yet whenever m ≤ (c + 1)^d / 2, the true error of L is greater than 1/4.

The result is especially significant because the distribution can have Bayes error 0. The difficulty is therefore not attributed to unavoidable classification noise. It comes from having too little training data for the dimensional setting described by the theorem.

Smoothness Is Not Noise

A c-Lipschitz condition controls how the target behavior changes as the input changes. It says that output variation is constrained by input variation and the coefficient c. This is a smoothness assumption used to analyze learning difficulty; it does not say that the classification problem must contain noise.

Common Misreadings

• Treating the dimensional effect as merely proportional.

  The analysis states that the requirement can grow exponentially with d, and d appears in the exponent d + 1 of the sample-size condition.

  Fix: Look for both appearances of d: it changes the base through √d and the exponent through d + 1.

• Assuming that a Lipschitz condition means the classification problem is noisy.

  The source explicitly allows a c-Lipschitz η with Bayes error 0.

  Fix: Interpret Lipschitz continuity as control over output variation, not as a claim about unavoidable classification mistakes.

• Reading Theorem 19.4 as a statement only about 1-NN.

  The theorem quantifies over every learning rule L and gives a distribution for which the lower bound applies.

  Fix: State the stronger implication: for some distributions, every learning rule has true error greater than 1/4 when m is no larger than the stated threshold.

• Concluding that zero Bayes error makes learning easy with any sample size.

  The source separates Bayes error from the amount of data needed to discover the target behavior in a high-dimensional space.

  Fix: Keep the two claims separate: Bayes error can be 0 while insufficient data still causes a large true error.

Check Your Understanding

Key Takeaways

1. In the 1-NN analysis, the training-data requirement can grow exponentially with the Euclidean dimension d.
2. The Lipschitz coefficient c controls output variation, while d controls the severity of the dimensional sample-size growth.
3. The condition m ≥ (4c√d/ε)^(d+1) shows that d affects both the base and the exponent of the requirement.
4. Theorem 19.4 gives a lower-bound result for every learning rule on some distributions: when c > 1 and m ≤ (c + 1)^d / 2, the true error is greater than 1/4.
5. A c-Lipschitz target can still have Bayes error 0, so smoothness and unavoidable classification noise are different concepts.