An online classifier sees one example at a time and predicts before receiving its label. A batch predictor must face new examples after training. When examples are independent draws from one fixed distribution, each online prediction is made on a fresh draw relative to the past. That observation lets us turn online performance into a population-risk statement. The precise output and the source of probability matter: a guarantee for the average risk of stored predictors is not automatically a guarantee for every stored predictor.
The online sequence and the batch mixture
Let be i.i.d. from , with . Before seeing , a deterministic online rule selects a measurable predictor using only ; all tie rules are fixed. Let the jointly measurable loss lie in , with predictors represented in a measurable space, and define
Assume the selections and risks are measurable. The stored predictors form a randomized batch rule, defined next.
Definition 5.4.1
(Mixture rule and its risk)
The mixture rule built from answers each future prediction as follows: draw a fresh test example from independently of the training sample, choose a fresh uniformly from independently of the sample and test example, then use . Conditional on the training sample, its expected test loss, including the random choice of , is
This is a Gibbs mixture, not necessarily one deterministic classifier. All logarithms below are natural except .
A general bounded-loss confidence bound
Theorem 5.4.2
(Sequential bounded-loss conversion)
For every , with probability at least over ,
No realizability assumption is needed. The probability here concerns the training sample; the random index is already averaged inside .
Proof
(An exponential-moment argument for the average)
Let , with trivial. Since is -measurable and is independent of with law , the conditional-expectation freezing lemma (from joint measurability and Fubini’s theorem) gives
Put . Conditional on the history it has mean zero and lies in an interval of length one. Hoeffding's lemma, applied conditionally, gives for . Iterated conditioning yields
Markov's inequality gives . Choosing gives ; set this equal to . The resulting event implies the displayed bound.
Proof X-ray
Fresh relative to the predictor
The argument does not treat as independent of the entire training set: later examples may affect later predictors. It uses only the fact that was fixed by the time is drawn. If the predictor may inspect before predicting, the conditional-expectation identity can fail.
A sharper bound for mistakes
For binary classification use zero-one loss and put . The next argument exploits the fact that a mistake indicator is Bernoulli conditional on the past. It can be much sharper when is small.
Theorem 5.4.3
(A fast-rate mistake conversion)
For any fixed and , with probability at least over the training sample,
The parameter is chosen before seeing the sample; selecting it from the data requires additional simultaneous control. This is a bound on the mixture risk and is valid for any measurable deterministic online rule under the i.i.d. assumption.
Proof
(An exponential supermartingale for mistakes)
Conditional on , let and let . Independence gives . With ,
using . Iterated conditioning shows . By Markov,
Rearranging on the complementary event proves the result.
If one fixed has and the finite class has members, the fixed target labels all examples correctly on a probability-one event, so it is never eliminated. Measurable halving with fixed ties then makes at most mistakes on that event. Taking gives, with probability at least ,
This uses a fixed target and i.i.d. realizability to apply the online mistake bound almost surely. The last inequality can exceed 1 for small ; risk is always at most 1, so the bound may be clipped at 1.
Worked example 5.4.4
(Halving on eight predictors)
For , , and , one has . The fast-rate bound is . The general bounded-loss bound gives at most . Both bound the same conditional mixture risk on their respective confidence events; neither says that every individual stored classifier has that risk.
Worked example 5.4.5
(A run with no mistakes)
Take , and . With the fast-rate bound is , whereas the general bound gives . When the fast-rate bound still decays like , while the general bound can never decay faster than ; this is the regime where the extra Bernoulli structure pays off.
Worked example 5.4.6
(A vacuous bound for tiny T)
Take , , , . The fast-rate expression equals , which exceeds ; since every risk is at most , the bound is clipped to and says nothing. The general bound with at most three mistakes still gives . Neither bound is uniformly better: the fast rate wins when is large and is small, the square-root bound can win when is very small.
Common mistake
(Choosing b after looking at M)
The fast-rate bound is proved for a value fixed before the sample is drawn. Picking the that minimizes the right-hand side for the observed is not covered by the theorem, because the exponential-moment argument controls for each fixed separately. A data-dependent choice needs simultaneous control, for example a union bound over a finite grid of values with divided among them.
Common mistake
(Treating online mistakes as a training error)
The indicators are losses of different predictors , each measured on the one example it had not yet seen. Their sum is not the training error of any single classifier, and the bounds above do not apply to a final predictor chosen after the last example. They apply to the average risk of the stored predictors .
What happens if one index is drawn only once?
Counterexample mode
An average can hide a bad stored predictor
Suppose the distribution always has label 0, and an online rule stores one classifier that always predicts 1 followed by nine that always predict 0. The ten risks are , so . If one index is sampled uniformly and then fixed as the deployed classifier, its population risk is 1 with probability and 0 otherwise. A bound on alone does not guarantee that the single selected has risk at most with certainty.
Drawing a fresh index for each prediction realizes the mixture loss. Drawing once yields a random classifier whose expected risk over , conditional on the sample, is the same average, but its realized risk can vary. For example, conditional on any training sample, Markov’s inequality gives for . Combining this with a sample event costs at most in total failure probability. A separate validation or selection procedure is another possibility.
Practice with solutions
Quick check
(An online binary learner makes at most two mistakes almost surely in i.i.d. rounds. Give the fast-rate mixture-risk bound at using .)
Substitute , and .
Solution · Answer
With probability at least , .
Quick check
(If all stored classifiers have population risk , what is the mixture risk? What is the risk of any one selected classifier?)
Average the ten, or , equal risks.
Solution · Answer
Both are : the mixture risk is the average of equal numbers, and every single classifier has risk by assumption. The two notions differ only when the stored risks differ.
Quick check
(Why does the general proof fail if is allowed to read the current label before predicting?)
Which step uses the order of events?
Solution · Answer
The current example is then no longer independent of the chosen predictor conditional on the past, so need not hold, and need not have conditional mean zero.
Quick check
(In the ten-classifier counterexample, what is ?)
Count the stored classifiers whose risk exceeds .
Solution · Answer
It is : exactly one stored classifier has risk , and the other nine have risk . The event has probability although exactly.