Lipschitz Continuity
1-NN is analyzed as a sample-dependent hypothesis h_S for binary classification.
A Prediction Begins with a Sample
Suppose a new input arrives and a classifier must assign it one of two labels. The 1-nearest-neighbor rule does not use a fixed prediction rule independent of the training data. Instead, it uses the labeled training sample: it finds the example closest to the new input and uses that example's label. This is why the analysis treats 1-NN as a sample-dependent hypothesis, written h_S, where S denotes the training sample.
Tracing the Nearest Example
Selecting the 1-NN Label
A training sample contains three labeled examples. For a new input x, the distances to the examples are 0.4, 0.1, and 0.3. Their labels are 0, 1, and 0, respectively. Which label does 1-NN predict?
Compare distances: The three distances are considered relative to the same new input x.
Select the closest example: The distance 0.1 is the smallest, so the second training example is the nearest neighbor.
Use its label: The selected training example has label 1, so the sample-dependent 1-NN hypothesis predicts label 1.
1-NN predicts label 1 for this new input.
The important point is the dependency on S. If the training sample changes, the closest example may change, and the prediction made by h_S may change as well. The rule is therefore different from a rule defined directly from the underlying data distribution.
Conditional Probability and the Bayes Benchmark
The conditional probability function η(x) describes the conditional label probability associated with an input x. The Bayes rule h* is defined from η(x). It serves as the optimal benchmark against which the sample-dependent 1-NN hypothesis can be studied. These rules have different sources of information: 1-NN uses the closest labeled example in the observed sample, while the Bayes rule is defined from the conditional probabilities at the input.
Two Different Sources of a Prediction
At a particular input x, imagine that the underlying conditional probability information favors label 1. A training sample has a closest labeled example whose label is 0. What is the conceptual difference between the two rules?
Apply 1-NN: The sample-dependent hypothesis h_S uses the label of the closest training example, so it predicts 0 in this situation.
Apply the Bayes benchmark: The Bayes rule h* is defined from η(x), so it uses the conditional label information at x rather than the label of one selected sample point.
Compare the rules: The predictions can differ because one rule depends on the observed nearest example and the other is defined from the conditional probability function.
1-NN is sample-dependent; the Bayes rule is the η(x)-based optimal benchmark.
Smooth Changes Across the Domain
The c-Lipschitz condition places a smoothness restriction on η(x). It connects Euclidean closeness between two inputs with the amount by which their conditional label probabilities can differ. When two inputs are close under the Euclidean distance ρ, the condition limits how quickly η can change between them. The constant c controls the allowed rate of change.
As a generated illustration, imagine two inputs that are very close in the domain. Under the c-Lipschitz assumption, their values of η cannot differ arbitrarily: the Euclidean distance between the inputs limits the permitted change. If the inputs are farther apart, the condition allows a larger change than it allows for the nearby pair. This is the smoothness idea used when relating a nearest training point to a new input.
Assumptions Behind the Error Analysis
The analysis studies binary classification with labels in Y = {0, 1}. The input domain is X = [0, 1]^d, the loss is the 0-1 loss, and distances are measured with the Euclidean distance ρ. A training sample supplies the examples used by h_S. The conditional probability function η and its c-Lipschitz condition provide the smoothness information needed to connect nearby inputs. Together, these choices establish the setting in which the true error of 1-NN can be studied beyond the observed sample.
| Part of the setting | Role in the analysis |
|---|---|
| Domain X = [0, 1]^d | Specifies the input space |
| Labels Y = {0, 1} | Specifies the binary classification labels |
| Euclidean distance ρ | Determines which training example is closest |
| Training sample S | Determines the sample-dependent hypothesis h_S |
| Conditional probability η(x) | Defines the Bayes rule h* |
| c-Lipschitz condition | Restricts how quickly η can change |
| 0-1 loss | Defines the classification loss used in the setting |
The assumptions work together rather than describing unrelated pieces.
Mistakes About 1-NN and Lipschitzness
Treating 1-NN as a fixed rule that does not depend on the training sample.
The hypothesis is written h_S because the selected neighbor, and therefore the prediction, depends on the sample S.
Fix:
Ask which labeled example is closest in the particular training sample being analyzed.Confusing the nearest neighbor's label with the Bayes rule's label.
1-NN uses a sampled neighbor, whereas h* is defined from the conditional probability function η(x).
Fix:
Keep h_S and h* separate: one is sample-dependent and the other is the η(x)-based optimal benchmark.Interpreting the c-Lipschitz condition as saying that η is constant.
The condition limits the amount of change in η according to Euclidean distance; it does not remove all change.
Fix:
Describe it as a restriction on the rate at which η changes.Ignoring the distance function when explaining 1-NN.
1-NN selects the closest example using the specified Euclidean distance.
Fix:
Compare distances from the new input to the training examples before transferring a label.
Practice the Distinction
Explain, in your own words, why a change to the training sample can change h_S while leaving the Bayes rule h* conceptually defined by the same conditional probability function η(x). Then explain what the c-Lipschitz condition contributes to the analysis.
Hints
- Begin by identifying the information used by h_S.
- Contrast the nearest sampled label with the rule defined from η(x).
- Describe the c-Lipschitz condition as a limit on how quickly η can change with Euclidean distance.
What do you think happens?
A new input has one closest training example. If that example's label changes while all distances remain the same, does the 1-NN prediction change?
Reveal answer
Answer: Yes
1-NN uses the label of the closest training example. Changing that label changes the label supplied to the sample-dependent prediction.
Key Takeaways
- The 1-NN hypothesis h_S is sample-dependent: it selects the closest labeled training example and uses its label.
- The conditional probability function η(x) defines the Bayes rule h*, which serves as the optimal benchmark.
- The c-Lipschitz condition limits how quickly η can change as inputs move under Euclidean distance.
- The analysis combines the domain X = [0, 1]^d, binary labels Y = {0, 1}, Euclidean distance, the training sample, η, smoothness, and 0-1 loss.
- Understanding 1-NN error requires keeping the observed-neighbor rule h_S distinct from the η(x)-based Bayes rule h*.
Key Takeaways
- 1-NN makes a prediction from the closest labeled example in a particular training sample.
- The Bayes rule h* is defined from η(x) and provides the optimal benchmark.
- The c-Lipschitz condition restricts the rate at which η can change between inputs.
- The domain, binary labels, Euclidean distance, sample, conditional probability, smoothness condition, and 0-1 loss form the setting for analyzing 1-NN error.
- The central distinction is between the sample-dependent rule h_S and the η(x)-based rule h*.