The Realizable Case in Online Classification
The realizable case assumes that labels come from a hypothesis h⋆ in a known hypothesis class H.
A Consistent Source of Labels
In online classification, an algorithm receives examples one at a time and predicts as it goes. The realizable case is the setting in which the labels are not arbitrary: they come from one fixed target hypothesis h⋆ that belongs to a known hypothesis class H. The learner may not know which hypothesis in H is the target, but the sequence is assumed to be consistent with that target.
The essential assumption is consistency: one fixed h⋆ in H generates the labels throughout the sequence.
Following One Sequence
Consider one particular realizable sequence S. The online algorithm A sees the examples in that sequence one at a time and may make some incorrect predictions. The number of mistakes made on this particular sequence is written as M_A(S). This is a sequence-specific quantity: it depends on which sequence was presented and on how the algorithm behaved on it.
Counting Mistakes on One Sequence
An online algorithm processes one realizable sequence S. It makes mistakes on rounds 2 and 5 and is correct on the other rounds shown. What does M_A(S) represent?
Identify the sequence: The count concerns this particular sequence S, not every possible sequence.
Count the errors: There are two rounds on which the algorithm's prediction is incorrect.
Name the quantity: The sequence-specific mistake count is M_A(S), so in this example M_A(S) is 2.
M_A(S) = 2 for this particular sequence.
From One Sequence to the Worst Case
A learner's performance on one sequence does not by itself give a worst-case guarantee. To evaluate the algorithm more strongly, consider every sequence whose labels are generated by a hypothesis h⋆ in H. The quantity M_A(H) represents the worst-case mistake count across those realizable sequences. It asks how many mistakes the algorithm could make on the most difficult allowed sequence.
| Quantity | What it considers | Meaning |
|---|---|---|
| M_A(S) | One particular realizable sequence S | The mistakes A makes on that sequence |
| M_A(H) | All realizable sequences associated with H | The worst-case mistake count for A over the allowed sequences |
Reading a Mistake Bound
A finite upper bound on M_A(H) is called a mistake bound. If an algorithm has a mistake bound M, the bound says that its worst-case number of mistakes over the allowed realizable sequences does not exceed M. The statement is therefore stronger than reporting the mistakes on one selected sequence: it applies across the entire collection of realizable sequences considered for H.
Interpreting a Bound
Suppose an online algorithm has a mistake bound M for a hypothesis class H. What does this tell you about any realizable sequence considered under H?
Start with the scope: The claim concerns every allowed realizable sequence, not just one selected sequence.
Use the bound: For each such sequence, the algorithm's mistake count is no greater than M.
Separate actual and guaranteed counts: A particular sequence may produce fewer than M mistakes. M is the worst-case ceiling supplied by the guarantee.
The algorithm makes at most M mistakes on every allowed realizable sequence.
When H Is Online Learnable
A hypothesis class H is online learnable when there exists an online learning algorithm A with a finite worst-case mistake bound on every realizable sequence associated with H. In the notation used here, the condition is that M_A(H) has a finite upper bound for some online algorithm A.
Whenever you see a claim about online learnability, check its quantifiers: there must be one online algorithm with a finite worst-case mistake bound across all realizable sequences under consideration.
Common Reasoning Errors
Treating one sequence's mistake count as the worst-case guarantee.
M_A(S) describes one particular sequence. The worst-case quantity must consider all realizable sequences.
Fix:
Use M_A(H) for the worst-case count over the allowed realizable sequences.Assuming realizability means the learner already knows h⋆.
The realizable-case assumption says that a target h⋆ in H generates the labels; it does not say that the learner has identified that target.
Fix:
Keep the target hypothesis as the source of the labels while evaluating how the online algorithm learns from examples.Interpreting a mistake bound as the exact number of mistakes on every sequence.
A bound is an upper limit. Individual sequences can have different mistake counts.
Fix:
Read M as a worst-case ceiling: each allowed sequence has a mistake count no greater than M.
Check Your Understanding
An online algorithm makes three mistakes on one realizable sequence S. Explain why this fact alone does not establish that the algorithm has a mistake bound of three for H. Then state what additional kind of statement would establish such a bound.
Hints
- Identify whether the count refers to M_A(S) or M_A(H).
- A mistake bound must cover every allowed realizable sequence.
- Look for a finite upper bound on the worst-case quantity.
A complete answer should say that three mistakes on S describe only M_A(S). To establish a mistake bound of three, one would need the worst-case quantity M_A(H) to be at most three across all realizable sequences associated with H.
Key Takeaways
- The realizable case assumes that one fixed target hypothesis h⋆ in H generates the labels.
- M_A(S) counts an algorithm's mistakes on one particular realizable sequence.
- M_A(H) refers to the worst-case mistake count across all realizable sequences associated with H.
- A finite upper bound on M_A(H) is a mistake bound.
- A hypothesis class is online learnable when some online algorithm has a finite worst-case mistake bound on every realizable sequence.