CMP.7:5.2 - Construct an online learner and derive its mistake bound

Let H be a finite family of binary prediction rules and suppose one fixed rule in H gives every true label that will arrive. Retain the set V of rules consistent with all labels seen so far. On a new input, predict the majority label among rules in V, using a fixed tie rule. After receiving the true label, remove the rules that predicted otherwise.

On each mistaken prediction, at least half of V is removed. The true rule remains, so after M mistakes 1≤|H|/2^M, giving M≤log2|H|. This establishes a bound on mistakes for an arbitrary input sequence under the stable-realizable-target assumption. It does not require independent random examples. Evaluating all survivors on each input costs up to |H| rule evaluations; the mistake guarantee alone does not make an enormous family affordable.

For a concrete instance, let inputs be integers 0 through 4 and let H contain six threshold rules h_t(x)=1 if x≥t else 0, for t=0,...,5. Break ties by predicting 1. At input 2, three rules predict each label, so predict 1. If the true label is 0, retain thresholds 3, 4 and 5. At input 3, the majority now predicts 0; if the true label is 1, retain only threshold 3. The two mistakes are within floor(log2 6)=2; subsequent predictions follow h_3 correctly as long as the assumed target remains h_3.

Changed feedback: a later example gives label 1 at input 2. It contradicts the previously received label at 2. Eliminating the last rule would leave an empty set. The stable noiseless-target premise has failed: retain the discrepancy and choose a treatment for noise or change, such as weighting errors or using a recent-data learner. The earlier mistake proof cannot be carried through that change unchanged.