A VC dimension counts possible label patterns, but it does not by itself tell us how to find a classifier. Axis-aligned boxes provide an algorithm that is easy to implement and an elementary distribution-free proof. The main idea is geometric: if the learner misses substantial positive probability, then a substantial boundary region of the target must have escaped the sample.
Model and learner
Fix an integer . A target box is , where all endpoints are finite and . It is unknown. Draw independent examples from an arbitrary distribution on , with noiseless labels . No density or absence of atoms is assumed. The population error of a box is
Definition 1.3.1
(Tightest enclosing box)
If at least one positive example is observed, output the smallest closed axis-aligned box containing all positive examples:
If there are no positive examples, output the empty set.
The hypothesis class therefore includes the empty set. The rule uses coordinate comparisons and stored endpoints in a real-comparison model; bit complexity depends on how inputs are encoded.
Lemma 1.3.2
(No false positives and consistency)
Under the noiseless model, for every sample. Consequently contains every observed positive and no observed negative, so it is consistent with the sample.
Proof
(Minimum and maximum stay inside the target)
Every positive sample is inside . Each coordinate minimum and maximum lies in the corresponding target interval, so ; this also holds when is empty. Thus all observed positives are inside , while every observed negative lies outside and hence outside .
The learner can make false negatives but no false positives. A consistent box need not be the target box.
Boundary bands, even with atoms
Theorem 1.3.3
(Distribution-free sample bound for boxes)
Let . If
then . The guarantee holds for every distribution and every target box above; logarithms are natural.
Proof
(Boundary bands and a union bound)
Put and . If , then for every sample, since the learner has no false positives. Otherwise . For each coordinate choose thresholds satisfying
Such thresholds exist even with atoms. For example, is the infimum of for which ; it is finite because , the target coordinates are bounded, and makes the defining set nonempty. Right-continuity gives the first inequality; for every , and continuity from below as gives the second. The upper threshold follows by the same argument applied to . A threshold need not split an atom, and the inequalities need not be equalities.
Call the events and the boundary bands. If the sample hits every band, it contains at least one positive point, so is nonempty. It has a positive point with coordinate at most and another with coordinate at least . Consequently, a target-positive point missed by must satisfy or for some . By (3) and the union bound, its probability is at most ; because , this is the entire classification risk. This argument remains valid even if .
Each band has probability at least , so the probability that independent draws miss a fixed band is at most . A union bound over bands gives
The bands can overlap and their missing events need not be independent. Independence is used across draws when bounding the chance that one fixed band is missed.
Proof X-ray
Why use weak and strict inequalities together?
The weak boundary bands have enough probability to be sampled, even if an atom lies at a threshold. Once a sample hits a band, only points strictly beyond that threshold can be missed on that side; those strict tails have probability at most . We never ask an atom to be divided into a prescribed probability mass.
Example and two mistakes to avoid
Worked example 1.3.4
(A misleading sample)
In two dimensions let be uniform on the four points and let . Suppose and the two observed positives are and . The output is the degenerate box , which fits the sample but misses the other two points. Its risk is . This sample occurs with positive probability; a PAC guarantee controls how often such misleading samples occur, not whether they can occur.
Worked example 1.3.5
(A three-dimensional run and its sample size)
Let and observe the positives , , . Taking coordinatewise minima and maxima gives . For and , inequality (2) requires , so suffices. If the sample had contained no positive point, the output would be the empty set, whose risk equals . Under (2) this happens with probability at most unless , in which case the risk is below anyway.
Worked example 1.3.6
(Rare positives: the case below the threshold)
Let , , , so , and suppose only of the mass lies in . Since , the proof stops at its first step: whatever the sample, even if the output is the empty set, , because the learner makes no false positives. No sample-size condition is needed in this case.
Common mistake
(Expecting the learner to recover the boundary)
The learner does not identify the exact target from arbitrary . If is concentrated at the origin, every target box containing the origin generates identical labeled data; their boundaries can differ, yet any box agreeing at the origin has zero risk. PAC error is distribution-dependent and is not geometric boundary reconstruction.
Common mistake
(Assuming a band has probability exactly )
With a density one could choose thresholds whose bands have probability exactly . With atoms this is generally impossible: a single atom at the threshold can carry mass larger than . That is why (3) uses a weak inequality for the band and a strict inequality for the tail, instead of asking for equality.
The proof also uses noiseless labels, and the next example shows concretely that the sample bound is not robust to label noise.
Counterexample mode
Label noise breaks the no-false-positive invariant
Take , , and with mass at and mass at . Suppose each example at is mislabeled as positive with probability , independently, while the labels at are correct. With , inequality (2) asks for , so take . Each draw is a noisy positive at with probability , so with probability the sample contains one. Then contains , which lies outside , and the risk against the true target is at least . The claimed failure probability is exceeded by a wide margin. The no-false-positive invariant is what the proof relies on; arbitrary label noise requires a different analysis.
Practice with solutions
Quick check
(If the positives in are and , what box is returned?)
Take coordinatewise minima and maxima.
Solution · Answer
The first coordinates are and the second coordinates are , so the box is .
Quick check
(With , , , give the sufficient integer sample size in (2).)
Evaluate with .
Solution · Answer
, so suffices.
Quick check
(Why can a negative training example never lie in the returned box under the model?)
Compare the returned box with the target box.
Solution · Answer
The returned box is a subset of , while every negative point lies outside .
Quick check
(In (3), why is the lower band's weak inequality not interchangeable with the strict tail inequality when there are atoms?)
Think of an atom sitting exactly at the threshold.
Solution · Answer
A threshold can carry positive mass: including its atom may be necessary to make the band have mass at least , while excluding it keeps the tail mass at most . For example, if an atom of mass lies at and no positive mass lies below it, the weak band has mass and the strict tail has mass zero. No arbitrary fraction of an atom is required.