Online Learning Algorithms
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.
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.
- 1Identify the selected sequence
The count on S concerns only the particular sequence that was chosen.
- 2Name the particular-sequence quantity
For this generated example, M_A(S) is three because A made three mistakes on S.
- 3Consider every allowed sequence
The worst-case quantity looks beyond S and considers all realizable sequences associated with H.
- 4Name 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.
M_A(H) can grow without a finite upper bound.
No finite worst-case mistake guarantee is available for the class.
There exists an algorithm A with a finite upper bound on M_A(H).
The class satisfies the online learnability condition.
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
Common mistake Treating M_A(S) as the worst-case quantity.
What it looks likeM_A(S) counts mistakes on one particular sequence S.
Why it failsThe worst-case quantity considers all realizable sequences, not only S.
Do this insteadUse M_A(S) for one sequence and M_A(H) for the worst case over the allowed realizable sequences.
Common mistake Assuming the realizable case means the learner never makes a mistake.
What it looks likeThe labels come from h⋆ in H, but A may still make mistakes while learning.
Why it failsRealizability describes how the labels are generated; it does not state that the algorithm is immediately correct.
Do this insteadAllow mistakes during the sequence, then evaluate their total using the relevant mistake quantity.
Common mistake Interpreting a mistake bound as zero mistakes on every example.
What it looks likeA finite upper bound limits the total worst-case mistakes over a sequence.
Why it failsA finite bound can allow mistakes while still guaranteeing that their total remains limited.
Do this insteadRead the bound as a cumulative worst-case limit.
Common mistake Forgetting the existence of an algorithm in the learnability condition.
What it looks likeThe question is whether there is an online algorithm A with finite M_A(H).
Why it failsOnline learnability is not merely a property of observing one successful sequence.
Do this insteadCheck 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
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
- 1In the realizable case, the labels in the sequence are generated by one hypothesis h⋆ from the known class H.
- 2M_A(S) is the number of mistakes made by algorithm A on one particular sequence S.
- 3M_A(H) is the worst-case mistake quantity over all realizable sequences associated with H.
- 4A finite upper bound on M_A(H) is called a mistake bound.
- 5H is online learnable when there exists an online algorithm with a finite worst-case mistake bound for H.
At a glance
- 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.