Analysis of 1-NN Rule

Higher dimension creates an exponential, not merely proportional, demand for training data in this analysis.

Programming

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.

What happens to the required number of training examples as the Euclidean dimension increases?

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.

How does increasing dimension change the coverage needed for reliable nearest-neighbor prediction?

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.

How do the Lipschitz coefficient and dimension combine to affect the 1-NN error bound?

Formula, step by step

1
c appears in the base, so a larger Lipschitz coefficient increases the required sample size.
2
√d appears in the base, so dimension also increases the base.
3
The exponent is d + 1, so increasing dimension changes the exponent as well as the base.
4
The condition is given for the last term in Theorem 19.3's bound to be smaller than ε.

Reading the Exponent

Worked example

Inspecting the Sample-Size Condition

Suppose c and ε are held fixed while the dimension d increases. What parts of the condition m ≥ (4c√d/ε)^{^d+1} change?

1
Inspect the base
The factor √d increases as d increases, so the base becomes larger.
2
Inspect the exponent
The exponent is d + 1, so it also increases with dimension.
3
Combine the effects
Dimension therefore affects both the base and the exponent. The exponent is the especially important source of rapid growth.

Result

Even with c and ε fixed, increasing d produces exponential growth in the stated sample-size requirement.

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.

What minimum limitation does Theorem 19.4 establish when the training sample is below its exponential threshold?

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.

What is the difference between output behavior constrained by a Lipschitz condition and behavior with no such smoothness restriction?

Situation	What is controlled	What it does not imply
c-Lipschitz η	How rapidly output behavior may vary with input	That Bayes error must be positive
Bayes error 0	The best possible classifier can have zero error	That a small training sample is sufficient
No Lipschitz condition in the analysis	No smoothness control supplied by that condition	A specific output pattern or error value

Smoothness, Bayes error, and training-data difficulty are related but distinct ideas.

Common Misreadings

Common mistake
Treating the dimensional effect as merely proportional.
What it looks like
Assuming that adding dimensions only requires adding a comparable number of training examples.
Why it fails
The analysis states that the requirement can grow exponentially with d, and d appears in the exponent d + 1 of the sample-size condition.
Do this instead
Look for both appearances of d: it changes the base through √d and the exponent through d + 1.
Common mistake
Assuming that a Lipschitz condition means the classification problem is noisy.
What it looks like
Concluding that c-Lipschitz η must have nonzero Bayes error.
Why it fails
The source explicitly allows a c-Lipschitz η with Bayes error 0.
Do this instead
Interpret Lipschitz continuity as control over output variation, not as a claim about unavoidable classification mistakes.
Common mistake
Reading Theorem 19.4 as a statement only about 1-NN.
What it looks like
Saying that the theorem proves only that the nearest-neighbor rule fails with too few examples.
Why it fails
The theorem quantifies over every learning rule L and gives a distribution for which the lower bound applies.
Do this instead
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.
Common mistake
Concluding that zero Bayes error makes learning easy with any sample size.
What it looks like
Assuming a perfectly classifiable distribution can always be learned from a small sample.
Why it fails
The source separates Bayes error from the amount of data needed to discover the target behavior in a high-dimensional space.
Do this instead
Keep the two claims separate: Bayes error can be 0 while insufficient data still causes a large true error.

Check Your Understanding

MEDIUM

Explain, in your own words, why increasing d can make the training-set requirement grow exponentially even when c and ε are fixed. Then state the exact sample-size threshold and true-error conclusion supplied by Theorem 19.4.

Hints

Identify where d appears in m ≥ (4c√d/ε)^{^d+1}.
Mention both the base and the exponent.
For Theorem 19.4, include the conditions c > 1 and m ≤ (c + 1)^{^d} / 2.
Include the conclusion that the true error is greater than 1/4 for the distribution guaranteed by the theorem.

Your attempt (not saved)

What do you think happens?

If Bayes error is 0, does that by itself guarantee that a small training sample will let a learning rule achieve small true error in this analysis?

Reveal answer

Answer:

Theorem 19.4 describes distributions with Bayes error 0 for which every learning rule has true error greater than 1/4 when the sample size is no larger than (c + 1)^{^d} / 2.

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.

At a glance

Higher dimension creates an exponential, not merely proportional, demand for training data in this analysis.
The Lipschitz coefficient controls output variation, while dimension controls the severity of sample-size growth.
The 1-NN error-bound calculation contains dimension in both the base and the exponent.
Theorem 19.4 shows that for some distributions, every learning rule faces true error greater than 1/4 below an exponential sample-size threshold.
Zero Bayes error does not prevent learning from being difficult when the training sample is too small.

More concepts starting with A