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?
- 1Identify the sequence
The count concerns this particular sequence S, not every possible sequence.
- 2Count the errors
There are two rounds on which the algorithm's prediction is incorrect.
- 3Name 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 |
Sequence-specific performance and worst-case performance answer different questions.
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?
- 1Start with the scope
The claim concerns every allowed realizable sequence, not just one selected sequence.
- 2Use the bound
For each such sequence, the algorithm's mistake count is no greater than M.
- 3Separate 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
Common mistake Treating one sequence's mistake count as the worst-case guarantee.
What it looks likeThe algorithm makes two mistakes on S, so its mistake bound is two.
Why it failsM_A(S) describes one particular sequence. The worst-case quantity must consider all realizable sequences.
Do this insteadUse M_A(H) for the worst-case count over the allowed realizable sequences.
Common mistake Assuming realizability means the learner already knows h⋆.
What it looks likeBecause the labels come from h⋆, the learner can use h⋆ immediately.
Why it failsThe realizable-case assumption says that a target h⋆ in H generates the labels; it does not say that the learner has identified that target.
Do this insteadKeep the target hypothesis as the source of the labels while evaluating how the online algorithm learns from examples.
Common mistake Interpreting a mistake bound as the exact number of mistakes on every sequence.
What it looks likeIf the bound is M, every sequence produces exactly M mistakes.
Why it failsA bound is an upper limit. Individual sequences can have different mistake counts.
Do this insteadRead 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.