Mistake Bounds
SOA begins with V_1 = H and maintains the hypotheses consistent with observed labels.
Why Mistakes Need a Bound
An online learner receives examples one at a time and predicts a label before seeing the true label. Some predictions may be wrong. The important evaluation question is not only how many mistakes occur on one particular sequence, but how many mistakes the algorithm could make over every allowed sequence. Mistake bounds give a precise way to express that worst-case guarantee.
The realizable case assumes that the labels in the online sequence come from a hypothesis h⋆ in a known hypothesis class H. The Standard Optimal Algorithm, or SOA, uses the hypotheses in H that remain consistent with the labels observed so far.
Realizable means that the observed labels do not contradict the assumption that at least one hypothesis in the original class H generated them.
The SOA State at Each Round
SOA begins with V_1 = H. At round t, V_t is the current version space: the hypotheses that agree with all labels observed before the current example. When the input x_t arrives, SOA divides V_t according to the label that each hypothesis assigns to x_t. The two candidate classes are V_t^(0) and V_t^(1).
Keep prediction and update as separate events. SOA first chooses p_t from the two candidate classes. Only after the true label y_t arrives does it construct V_(t+1).
Choosing a Label with Ldim
SOA compares the Ldim of V_t^(0) and V_t^(1). It predicts the label whose candidate class has the larger Ldim. In this procedure, Ldim determines which side is selected for the prediction, while the true observed label determines which hypotheses survive the update.
Selecting Between Two Candidate Classes
Suppose the current split has Ldim(V_t^(0)) = 2 and Ldim(V_t^(1)) = 4.
Compare: The candidate class associated with label 1 has the larger Ldim.
Predict: SOA predicts p_t = 1.
Update: After the true label y_t arrives, SOA keeps only the hypotheses in V_t that agree with y_t. It does not automatically keep the hypotheses supporting the prediction.
The prediction is selected from Ldim, but the next version space is selected from the true label.
Tracing a Mistake Correctly
What do you think happens?
SOA predicts p_t = 1 because V_t^(1) has the larger Ldim. The true label is y_t = 0. Which hypotheses form V_(t+1)?
Reveal answer
Answer: The hypotheses in V_t^(0), because they agree with the true label.
The update uses y_t, not p_t. A wrong prediction does not cause SOA to preserve the hypotheses that supported that prediction.
A prediction trace diverges from SOA when it updates with the prediction instead of the true label. If p_t is wrong, this error is especially visible: SOA discards the hypotheses that disagree with y_t, even though those hypotheses may have supported p_t. An incorrect update changes the next version space and can therefore change every later prediction.
Updating with p_t instead of y_t
The next version space must contain hypotheses that agree with the true observed label.
Fix:
Use y_t to form V_(t+1), whether the prediction was correct or incorrect.Choosing the smaller Ldim
SOA predicts using the candidate class with larger Ldim.
Fix:
Compare both values and choose label 0 in this example.Ignoring an Ldim tie
SOA has a specified tie-breaking rule.
Fix:
Predict 1 when the two Ldim values are equal.
Counting Mistakes at Two Scales
Let S be one particular realizable sequence. M_A(S) is the number of mistakes made by algorithm A on that sequence. This count depends on the chosen examples and labels. The worst-case quantity M_A(H) considers all realizable sequences allowed by H, so it asks for the largest number of mistakes the algorithm could make across those sequences.
| Quantity | What it measures | Scope |
|---|---|---|
| M_A(S) | The mistakes made by A | One particular realizable sequence S |
| M_A(H) | The worst-case mistake count | All realizable sequences associated with H |
| Mistake bound | A finite upper bound on the worst-case count | The algorithm's guaranteed maximum over allowed sequences |
Mistake counts become worst-case guarantees when the scope expands from one sequence to all allowed realizable sequences.
A mistake bound is a finite upper bound on M_A(H), the worst-case number of mistakes made by an online algorithm over all realizable sequences considered for H.
The SOA Guarantee
The Standard Optimal Algorithm makes at most Ldim(H) mistakes on hypothesis class H. Thus, Ldim has two roles in the SOA analysis: it selects the predicted label at each round, and it supplies the stated upper bound on the total number of mistakes.
The guarantee is a worst-case statement. It does not claim that SOA makes exactly Ldim(H) mistakes on every sequence. A particular realizable sequence may produce fewer mistakes. The bound says that, across the allowed realizable sequences, the number of mistakes does not exceed Ldim(H).
Practice the Procedure
A round begins with current class V_t. The two candidate classes have Ldim(V_t^(0)) = 3 and Ldim(V_t^(1)) = 3. SOA receives the true label y_t = 0. State the prediction and describe the next version space.
Hints
- Use the specified tie-breaking rule.
- The update uses the true label rather than the prediction.
Practice Solution
The candidate classes have equal Ldim, and the true label is 0.
Prediction: The Ldim values are tied, so SOA predicts 1.
Mistake status: Because y_t = 0, the prediction is incorrect.
Update: The next version space contains the hypotheses in V_t^(0), because those hypotheses agree with the true label.
SOA predicts 1, then updates to the hypotheses consistent with y_t = 0.
Key Takeaways
- SOA starts with V_1 = H and maintains the hypotheses consistent with observed true labels.
- At each round, SOA splits V_t into V_t^(0) and V_t^(1), then predicts using the side with larger Ldim.
- If the two Ldim values are equal, SOA predicts 1.
- The update uses y_t, the true label, not p_t, the prediction.
- SOA makes at most Ldim(H) mistakes; a finite worst-case bound provides the online learning guarantee.
Key Takeaways
- SOA predicts from the candidate class with larger Ldim and resolves ties by predicting 1.
- The version space is updated with the true label, even when the prediction is wrong.
- M_A(S) counts mistakes on one sequence, while M_A(H) is the worst-case count over all allowed realizable sequences.
- A mistake bound is a finite upper bound on the worst-case number of mistakes.
- For SOA, the stated bound is Ldim(H), so a finite Ldim gives a finite online mistake guarantee.