In realizable learning, every label agrees with one target hypothesis. In agnostic learning, even the best hypothesis may make errors. To be nearly as good as that best hypothesis, a learner must detect small biases in the labels at many points. We construct a family of noisy distributions on a shattered set and show that too few samples leave a constant probability of excess risk. The proof permits randomized and improper learners.
The hard family
Definition 2.4.1
(Hard noisy family on a shattered set)
Let a binary hypothesis class shatter distinct points , with . Thus every sign vector is realized on those points by some hypothesis in . Fix . For each , define a distribution by drawing uniformly from the points and then drawing with
The labels are noisy, but is the pointwise Bayes labeling and a member of realizes it.
If a binary classifier disagrees with on of the points, then
Indeed, predicting makes conditional error , while predicting the opposite makes error . This identity also holds for an improper output, provided it predicts a binary label at each point.
Two tests cannot both be too accurate
We use the following finite-sample testing inequality. For distributions on a finite set, let and , with the usual endpoint conventions and natural logarithms. Then
This is Pinsker's inequality. For the finite setting here, it follows by choosing an event attaining total variation, applying the log-sum inequality to and its complement, and using for Bernoulli parameters, where . The latter follows because the second derivative in is and the value and first derivative vanish at ; boundary cases follow by limits.
For any test that guesses whether data came from or under equal prior probabilities, the average probability of a wrong guess is at least
If the test outputs “” on event , its average error is . The same inequality applies after averaging over an independent random seed used by the test.
One coordinate is hard to infer
Lemma 2.4.2
(Guessing one sign from noisy labels)
Fix an index and fix the signs for . Let be uniform on , and let a learner, possibly randomized with an independent seed, guess from i.i.d. examples of . Its probability of guessing incorrectly is at least
and the same holds when the other signs are not revealed.
Proof
(Pinsker's inequality applied to the product laws)
Fix an index and reveal all signs for to the learner as extra information. Let and denote the two distributions with and and all other signs fixed. Logarithms are natural. Their single-example KL divergence is
The factor is the probability of observing ; at every other input the two label laws agree. For independent samples, KL divergence is times this amount. Since ,
Pinsker and the binary-testing bound show that even with the other signs revealed, the probability of guessing incorrectly, averaged over a uniform , the sample and the independent seed with the other signs fixed, is at least
This bound may be negative for large , in which case it is merely uninformative. It is valid for a learner's prediction at , including one computed using independent internal randomness. Revealing extra information can only make the testing task easier, so the same lower bound applies when the learner is not given the other signs.
Averaging first, then fixing one hard distribution
Theorem 2.4.3
(A concrete agnostic sample lower bound)
Let and . For any measurable learner that outputs a binary classifier from labeled examples, using an independent random seed if randomized, if
then there is a fixed distribution from the family above for which, with probability at least over the sample and learner randomness,
Thus a distribution-free agnostic guarantee with failure probability strictly below requires whenever .
Proof
(Averaging over random signs)
Choose and let the signs be independent and uniform for the proof. The sample-size condition makes . Average the coordinate testing bound over the other signs and then sum over : by linearity, the expected fraction of sign mistakes over signs, samples and the independent learner seed is at least . The excess-risk identity therefore gives
Averaging over the finitely many sign vectors shows that at least one fixed has expected excess risk at least . For that distribution, the excess lies in . If , then
The hard is chosen after the algorithm is specified but before the sample and random seed are drawn. It does not change in response to the realized sample.
Proof X-ray
Random targets are a proof device
Shattering is used once, to make the Bayes labeling a member of , so that the best-in-class risk is and the excess risk is exactly . The sample-size condition is also used once, to make , which turns the coordinate bound into an error probability of at least per sign. The central move is to average over random signs, which treats all coordinates symmetrically and lets the lemma be applied coordinate by coordinate, and then to extract one fixed whose expected excess risk is at least .
The last step converts an expectation into a probability. It needs the excess to be bounded by , and that is where enters: . If the target were allowed to be chosen after seeing each sample, the statement would be different and weaker.
Worked example 2.4.4
(Excess risk in the hard family for )
Take , and . At the label is with probability and at it is with probability . The Bayes classifier has error at each point, so . The classifier is right at (error ) and wrong at (error ), so its risk is . Its excess risk is , in agreement with .
Worked example 2.4.5
(Applying the lower bound)
For , and , the stated condition holds with equality. Here ; the theorem guarantees a fixed noisy distribution on the shattered points for which excess risk exceeds with probability at least . The theorem does not identify that distribution without knowing the learner.
Worked example 2.4.6
(When the coordinate bound says nothing)
Take and . The single-example divergence is , so for samples the exact value is about and Pinsker gives total variation at most . The relaxed bound used in the text is , which gives total variation at most one, and the error bound is . This is the edge of the useful range: from onwards the relaxed lemma gives no information, although the exact divergence would still give a nonzero bound here. The theorem's condition keeps well inside the useful range.
Scope and a realizability warning
Counterexample mode
The hard family is not noiselessly realizable
When , both labels occur with positive probability at each point. No deterministic classifier can have zero risk on , even though the Bayes labeling is in . Applying a theorem that assumes noiseless realizability to this family would ignore the very label uncertainty responsible for the lower bound.
The constant is chosen for a transparent proof, not claimed optimal. We did not prove the dependence on an arbitrary confidence parameter , a computational lower bound, or a lower bound when the class does not shatter the specified points. The argument does not restrict the learner to output a member of .
Common mistake
(Holding the bias fixed while the accuracy target shrinks)
The excess risk in the hard family is , so the bias must scale with . With a fixed the same argument only forces about examples before the expected excess risk can fall below ; this is of order and does not grow as . The choice is what produces the dependence.
Common mistake
(Reading the probability as a confidence parameter)
The theorem shows failure with probability at least for one fixed constant. It says nothing about how the sample size must grow as the allowed failure probability tends to zero, and it does not exclude such growth. A distribution-free guarantee with failure probability strictly below needs ; no more is claimed.
Practice with solutions
Quick check
(If a classifier disagrees with on exactly one of points, what is its excess risk?)
Use the identity from the hard-family section.
Solution · Answer
.
Quick check
(What is the best-in-class risk in the hard family when ?)
It is the Bayes error at each point.
Solution · Answer
.
Quick check
(Why is a nonzero KL divergence incurred only when in the test of versus ?)
Compare the two distributions at an input with .
Solution · Answer
The candidates have identical input laws and identical conditional label laws at every other point. At the divergence is , multiplied by .
Quick check
(If and , what is the largest integer covered by the theorem's sufficient condition for a lower bound?)
Evaluate .
Solution · Answer
.
Quick check
(Why does the final theorem provide one fixed hard distribution even though its proof uses random signs?)
Think about what an average over finitely many distributions implies.
Solution · Answer
The finite-family average is at least , so some fixed member has at least that expectation. For that one distribution, gives .