Lipschitz Continuity

Lipschitz continuity is a restriction on change, not a statement that η has the same value everywhere.

Programming

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.

How does a labeled training sample determine which training point is selected and what label 1-NN predicts for a new input?

Tracing the Nearest Example

Worked 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?

1
Compare distances
The three distances are considered relative to the same new input x.
2
Select the closest example
The distance 0.1 is the smallest, so the second training example is the nearest neighbor.
3
Use its label
The selected training example has label 1, so the sample-dependent 1-NN hypothesis predicts label 1.

Result

1-NN predicts label 1 for this new input.

How does 1-NN compare distances from a new point to the sample and identify the single training example whose label will be used?

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.

How does the value of η(x) determine the Bayes-optimal binary label at each point x?

Worked example

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?

1
Apply 1-NN
The sample-dependent hypothesis h_S uses the label of the closest training example, so it predicts 0 in this situation.
2
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.
3
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.

Result

1-NN is sample-dependent; the Bayes rule is the η(x)-based optimal benchmark.

What is the difference between the label chosen from the nearest sampled point and the label chosen from the larger conditional probabilities at x?

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.

How does the Lipschitz condition restrict the amount by which η(x) can change between two points as their distance changes?

In the real world

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.

How do the domain, binary labels, distance function, and conditional probability function fit together to support the analysis of 1-NN error?

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

Common mistake
Treating 1-NN as a fixed rule that does not depend on the training sample.
What it looks like
Assuming every training set must produce the same prediction for a given input.
Why it fails
The hypothesis is written h_S because the selected neighbor, and therefore the prediction, depends on the sample S.
Do this instead
Ask which labeled example is closest in the particular training sample being analyzed.
Common mistake
Confusing the nearest neighbor's label with the Bayes rule's label.
What it looks like
Calling the label of the closest sampled point the Bayes-optimal prediction.
Why it fails
1-NN uses a sampled neighbor, whereas h* is defined from the conditional probability function η(x).
Do this instead
Keep h_S and h* separate: one is sample-dependent and the other is the η(x)-based optimal benchmark.
Common mistake
Interpreting the c-Lipschitz condition as saying that η is constant.
What it looks like
Concluding that two different inputs must have exactly the same conditional probability.
Why it fails
The condition limits the amount of change in η according to Euclidean distance; it does not remove all change.
Do this instead
Describe it as a restriction on the rate at which η changes.
Common mistake
Ignoring the distance function when explaining 1-NN.
What it looks like
Choosing a training example because it appears first in the sample rather than because it is closest.
Why it fails
1-NN selects the closest example using the specified Euclidean distance.
Do this instead
Compare distances from the new input to the training examples before transferring a label.

Practice the Distinction

MEDIUM

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.

Your attempt (not saved)

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

1
The 1-NN hypothesis h_S is sample-dependent: it selects the closest labeled training example and uses its label.
2
The conditional probability function η(x) defines the Bayes rule h*, which serves as the optimal benchmark.
3
The c-Lipschitz condition limits how quickly η can change as inputs move under Euclidean distance.
4
The analysis combines the domain X = [0, 1]^d, binary labels Y = {0, 1}, Euclidean distance, the training sample, η, smoothness, and 0-1 loss.
5
Understanding 1-NN error requires keeping the observed-neighbor rule h_S distinct from the η(x)-based Bayes rule h*.

At a glance

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*.

Related concepts

More concepts starting with L