Online Learning Algorithms
The realizable case assumes that labels come from a hypothesis h⋆ in a known hypothesis class H.
The Online Learning Setting
An online learner receives examples one at a time. As each example arrives, the algorithm may make a mistake while it is learning. To evaluate the algorithm, we do not look only at one convenient sequence. We ask a worst-case question: across every allowed sequence of examples, how many mistakes could the algorithm make?
Online learning evaluates an algorithm by counting its mistakes as examples arrive and then considering how large that count can become over the allowed sequences.
Labels from One Hidden Hypothesis
The realizable case makes a consistency assumption about the labels. There is a known hypothesis class H, and a single hypothesis h⋆ in H generates the labels in the sequence. Thus, although the learner receives examples one at a time, the labels are assumed to come from one member of the known class rather than being arbitrary with respect to H.
Generated example: Suppose H contains several possible labeling rules, and one particular rule h⋆ in H supplies the labels for an incoming sequence. The learner still sees the examples one at a time; the realizable assumption concerns the source of the labels, not the order in which the examples arrive.
One Sequence versus Every Sequence
Let A be an online learning algorithm and let S be one particular sequence whose labels are generated by a hypothesis h⋆ in H. The number of mistakes A makes on this particular sequence is written M_A(S). It depends on which sequence was selected and on how A behaves on that sequence.
The worst-case quantity M_A(H) asks a different question. It considers all realizable sequences, meaning all allowed sequences whose labels are generated by a hypothesis in H. It captures the largest mistake count that must be considered when evaluating A over the whole allowed collection.
| Quantity | What it examines | What it tells you |
|---|---|---|
| M_A(S) | One particular realizable sequence S | How many mistakes A makes on that selected sequence |
| M_A(H) | All realizable sequences associated with H | The worst-case mistake quantity for A over the allowed sequences |
The two quantities answer different evaluation questions.
Separating the Two Counts
Generated example: Algorithm A is evaluated on one realizable sequence S and makes three mistakes. Across all realizable sequences allowed by H, the largest mistake count for A is seven.
Identify the selected sequence: The count on S concerns only the particular sequence that was chosen.
Name the particular-sequence quantity: For this generated example, M_A(S) is three because A made three mistakes on S.
Consider every allowed sequence: The worst-case quantity looks beyond S and considers all realizable sequences associated with H.
Name the worst-case quantity: For this generated example, M_A(H) is seven because seven is the largest mistake count among the allowed sequences.
M_A(S) describes performance on one sequence, whereas M_A(H) describes the worst case over all realizable sequences.
Reading a Mistake Bound
A mistake bound is a finite upper bound on M_A(H). It limits the worst-case number of mistakes that algorithm A can make over the realizable sequences considered for H.
The bound does not say that the algorithm makes no mistakes. The learner may make mistakes as examples arrive. Instead, the bound constrains the total worst-case number of mistakes across the sequence under consideration. It is therefore a statement about cumulative performance, not necessarily about every individual example.
Online Learnability of H
A hypothesis class H is online learnable when there is an online learning algorithm A whose worst-case mistake quantity M_A(H) has a finite upper bound. In other words, the class admits an algorithm whose mistakes remain bounded over the realizable sequences considered for H.
The key existence statement is: online learnability concerns whether some suitable online algorithm has a finite worst-case mistake bound for H.
Common Mistakes in Interpretation
Treating M_A(S) as the worst-case quantity.
The worst-case quantity considers all realizable sequences, not only S.
Fix:
Use M_A(S) for one sequence and M_A(H) for the worst case over the allowed realizable sequences.Assuming the realizable case means the learner never makes a mistake.
Realizability describes how the labels are generated; it does not state that the algorithm is immediately correct.
Fix:
Allow mistakes during the sequence, then evaluate their total using the relevant mistake quantity.Interpreting a mistake bound as zero mistakes on every example.
A finite bound can allow mistakes while still guaranteeing that their total remains limited.
Fix:
Read the bound as a cumulative worst-case limit.Forgetting the existence of an algorithm in the learnability condition.
Online learnability is not merely a property of observing one successful sequence.
Fix:
Check whether some online algorithm has a finite worst-case mistake bound for H.
Check Your Understanding
Generated practice: Explain the difference between M_A(S) and M_A(H) in your own words. Then state what must be true of M_A(H) for H to be online learnable.
Hints
- Start by identifying whether the notation refers to one sequence or all realizable sequences.
- A mistake bound is described using the word finite.
- Online learnability requires the existence of an online algorithm with the required bound.
What do you think happens?
Generated prediction: If an algorithm makes two mistakes on one realizable sequence, does that alone establish its worst-case mistake quantity for H?
Reveal answer
Answer: No, because the worst-case quantity considers all realizable sequences.
Two mistakes on one sequence describe M_A(S) for that sequence. The worst-case quantity M_A(H) requires considering the full collection of realizable sequences.
Key Takeaways
- In the realizable case, the labels in the sequence are generated by one hypothesis h⋆ from the known class H.
- M_A(S) is the number of mistakes made by algorithm A on one particular sequence S.
- M_A(H) is the worst-case mistake quantity over all realizable sequences associated with H.
- A finite upper bound on M_A(H) is called a mistake bound.
- H is online learnable when there exists an online algorithm with a finite worst-case mistake bound for H.
Key Takeaways
- The realizable assumption links every sequence label to one hypothesis h⋆ in H.
- A particular-sequence count M_A(S) and a worst-case quantity M_A(H) answer different questions.
- A mistake bound is a finite upper bound on the worst-case number of mistakes.
- A hypothesis class is online learnable when some online algorithm has a finite mistake bound for that class.