Learning one prediction at a time
In a batch problem, a learner receives a labeled sample and then produces a classifier. In online learning, prediction and feedback alternate. At round , the learner sees , predicts a label, and only then sees . It may use the feedback to change its next prediction. This order prevents the learner from using the current label before predicting it.
A mistake bound controls the number of incorrect predictions on a sequence. Such a guarantee can be deterministic and hold for an adversarially chosen sequence; it is not automatically a probability bound on future examples. We first compare a finite set of binary experts, then state the extra i.i.d. assumption that connects the online and population viewpoints.
Halving a realizable version space
Let be a finite nonempty class of measurable classifiers on a measurable instance space. Initially let . At round , predict the majority label among , breaking a tie in favor of 1. After the true label is revealed, retain exactly the hypotheses that predicted it:
Definition 5.1.1
(Realizable sequence and version space)
A sequence is realizable by if one fixed labels every round correctly. The set of hypotheses consistent with all earlier labels is the version space at round .
Realizability ensures at every round, so the version space is never empty. The procedure need not know which member is .
Theorem 5.1.2
(Halving mistake bound)
On every finite sequence realizable by , the majority algorithm makes at most mistakes.
Proof
(Each mistake halves the version space)
On a mistaken round, at least half the current hypotheses predicted the learner's wrong majority label. This remains true in a tie. All those hypotheses are removed, so . On correct rounds the version space cannot grow. After mistakes, , because survives. Thus ; is an integer.
Proof X-ray
Where each hypothesis is used
Two separate facts drive the argument. The majority vote supplies the halving: it is used only on mistaken rounds, where the wrong label was held by at least half of , so at least half is deleted. Realizability supplies the survivor , which gives the floor and never enters the halving step. Dropping realizability keeps the halving but loses the floor, and may become empty, as the counterexample below shows. Correct rounds delete nothing that is needed and cost no mistake. The floor in comes only from being an integer.
Worked example 5.1.3
(Two mistakes with four thresholds)
Take and , where . On , two hypotheses vote 1 and two vote 0. The tie rule predicts 1. If , this is a mistake and only remain. On , they again tie; the learner predicts 1. If , it makes a second mistake and only remains. The sequence is realizable by , and the bound is attained.
The bound is sharp for some classes. On distinct points, let contain all binary functions. For any deterministic online learner, present each point once and choose its label opposite the learner's prediction. The resulting labels define a single target in , so the sequence is realizable and forces mistakes. This is a worst-case construction for that class, not a claim that every class of the same size forces that many mistakes.
Weighted majority when no expert is perfect
If the data are not realizable, eliminating an expert forever after one error can empty the version space. Weighted majority retains all experts but reduces the weight of those that err.
Definition 5.1.4
(Weighted majority with penalty factor)
Let , choose , and initially set for every . At each round predict the label with greater total weight, again breaking ties in favor of 1. After observing , update
All mistaken experts are updated on every round, including rounds on which the learner was correct. Let be the learner's number of mistakes and let be the number made by expert over the same rounds.
Theorem 5.1.5
(Weighted-majority mistake bound)
For every finite labeled sequence, without a realizability assumption,
The logarithms are natural. In particular, the bound holds with replaced by the number of mistakes of the best fixed expert in hindsight.
Proof
(A potential argument on the total weight)
Let ; initially . On any round, weights do not increase. When the learner makes a mistake, at least half the weight voted for the wrong label, including the tie case. Therefore
After mistakes, . On the other hand, a fixed expert with mistakes has final weight , so . Taking logarithms and rearranging gives the bound; the denominator is positive because .
Proof X-ray
Squeezing the total weight
The proof bounds one quantity, , from above and below. The upper bound uses only the learner's mistakes: on each mistaken round at least half the weight sat on the wrong label and shrinks by the factor , so falls by at least the fraction ; correct rounds can only lower , so ignoring them is safe. The lower bound uses a single expert, because is a sum of nonnegative terms and is therefore at least any one of them. Since is arbitrary, the conclusion holds for all experts at once, in particular for the best one. Nothing here requires realizability, independence of the experts or randomness in the labels.
Worked example 5.1.6
(Two constant experts)
Let two experts always predict 0 and 1, take , and use labels 0 then 1. Initially weights tie, so the learner predicts 1 and errs; the new weights are 1 and . Next it predicts 0 and errs; both weights become . Each expert made one mistake, and the bound gives , which holds for . The bound remains valid although no expert predicted both labels correctly.
Worked example 5.1.7
(A three-expert trace)
Take experts and . Round 1: predictions , label 1. The weight on 1 is and on 0 is , so the learner predicts 0 and errs; are halved to with . Round 2: predictions , label 0. The weight on 1 is and on 0 is , so the learner predicts 1 and errs; are halved to with . Round 3: predictions , label 0. The weight on 0 is and on 1 is , so the learner is correct, yet is halved to give and . Hence and . For the theorem gives : valid, but far from tight on so short a run. The final weight also checks the lower bound on .
Common mistake
(Penalizing experts only when the learner errs)
In weighted majority every expert that mispredicts is multiplied by on every round, including rounds on which the learner itself is correct, as the third round of the trace above shows. Updating only after the learner's own mistakes breaks the comparison , because counts all of the expert's errors.
This is a comparison with the best fixed expert. With a fixed , the coefficient multiplying is generally greater than one; the displayed result alone is not a sublinear-regret theorem. The halving proof treats separately: substituting zero into the logarithmic bound is not valid.
Counterexample mode
A version space can disappear
Take one instance , two constant experts 0 and 1, and labels 0 then 1. After the first label, halving retains only the constant-zero expert; after the second, none remains. The sequence is not realizable by a single expert, so the halving theorem does not apply. Weighted majority keeps positive weights and still has its best-expert comparison, but that comparison does not promise few absolute mistakes when every expert makes many errors.
From online mistakes to an expected-risk statement
Suppose now that are i.i.d. from a fixed distribution , , and the online rule at round defines a measurable classifier using only earlier examples, with a fixed deterministic tie rule. Let . After rounds choose uniformly from , independently of the sample, and output the stored classifier . Conditional on the past, is a fresh draw, so
The expectation is over both the sample and . If one fixed satisfies , the finite i.i.d. sequence is realizable almost surely. Halving then makes at most mistakes almost surely, yielding . This statement concerns a randomly selected stored predictor and expected risk. It is not automatically a high-probability guarantee, a guarantee for the last predictor, or a result for a non-i.i.d. sequence.
Common mistake
(Applying the expected-risk bound to the last predictor)
The identity averages over a uniform index . It does not bound or : an online rule may make its last mistake late, and a single late predictor can have large risk while the average over all stays small.
Practice with solutions
Quick check
(If a realizable class contains six hypotheses, what integer upper bound does halving give for its mistakes?)
Apply the theorem and round down.
Solution · Answer
. Three mistakes would leave at most hypotheses, impossible because survives.
Quick check
(For the four thresholds above, use the tie rule to trace the first prediction at and the surviving set after label 0.)
Evaluate for .
Solution · Answer
and . Two experts vote each way, so the tie predicts 1. The label 0 keeps exactly the hypotheses that predicted 0, which leaves .
Quick check
(In weighted majority with , , and a perfect expert, give the stated numerical upper bound on the learner's integer mistake count.)
A perfect expert has .
Solution · Answer
The theorem gives , hence because is an integer. This bound is weaker than the realizable halving bound in this example.
Quick check
(An i.i.d. problem with for one has . Run halving for rounds and output a stored with uniform and independent of the sample. Bound its population error in expectation over the sample and .)
Use and the halving bound.
Solution · Answer
Halving makes at most mistakes almost surely, so the expected error is at most . This does not say that every run, or the final online predictor, has error at most .