Online Learning

A Decision Before the Answer

Imagine a learner that must decide whether a current instance belongs to one class or another before it knows the correct answer. After making the prediction, the learner receives the true label and can use that information to improve later predictions. This timing pattern is the central idea of online learning: prediction and learning are interwoven instead of being separated into two large phases.

Four Events in Every Round

An online learning run consists of consecutive rounds. In round t, the algorithm has a current hypothesis h_t. It receives an instance, uses h_t to make a prediction, observes the correct label, and then uses that label to support future predictions. These four events occur in order: receive the instance, predict, reveal the label, and update the learner's later behavior.

• The learner receives the current instance.
• The learner predicts before seeing the correct label.
• The correct label is revealed.
• The learner uses the revealed label to support future predictions.

From Test to Training

An example has two roles at different moments of the same round. Before its label is revealed, it tests the learner's current hypothesis because the learner must predict its label without knowing the answer. After the correct label is revealed, that same example can contribute to future learning. This is why online learning repeatedly combines prediction and training within each round.

Building a PAC Learner from the Run

The online-to-PAC conversion runs the online algorithm on T independently sampled examples. Suppose examples come from a distribution D over an instance domain X, and their labels are supplied by a true hypothesis h⋆ in H. At round t, the online algorithm uses h_t to predict the label of the tth example. After all T rounds, the run has produced the sequence h_1 through h_T. The converted PAC learner chooses a uniformly random member h_r of that sequence as its output.

1. Draw T examples independently from D.
2. Process them in order through the online learner.
3. Record the current hypothesis h_t associated with each round.
4. Choose an index r uniformly from the T rounds.
5. Return h_r as the PAC learner's hypothesis.

Why the Mistake Bound Matters

Assume the online algorithm has a finite mistake bound M_A(H). This bound limits the total number of prediction mistakes the algorithm can make across the online sequence. Because the selected hypothesis h_r comes from that sequence, the total mistakes constrain the average error represented across the hypotheses. The resulting expected risk of the uniformly selected hypothesis is bounded by M_A(H) divided by T.

Choosing a Hypothesis from the Sequence

The converted learner does not invent a separate hypothesis by applying a new selection rule outside the online process. The online run itself creates h_1, h_2, and so on through h_T. A random index r identifies which member is returned. The expected guarantee accounts for both sources of randomness: the independently sampled examples and the random choice of r.

The selection works because the online mistakes are distributed over the sequence of rounds. If the sequence contains only a bounded total number of mistakes, then choosing a member of the sequence uniformly cannot have an uncontrolled expected risk under the conversion's assumptions. The guarantee is therefore an average expected guarantee over the sampled examples and the random index.

Online and PAC Learning Compared

Common Reasoning Mistakes

• Treating online learning as a batch training phase followed by a separate prediction phase.

  Online learning interweaves prediction and learning across consecutive rounds.

  Fix: Remember the order within each round: instance, prediction, revealed label, and support for future predictions.

• Assuming the label is available before the online prediction.

  The defining timing pattern is that the prediction occurs before the correct label is revealed.

  Fix: Treat the current example as a test example first and as a training example afterward.

• Selecting a hypothesis that was not produced during the online run.

  The described conversion selects a uniformly random h_r from h_1 through h_T.

  Fix: Track the hypotheses created at the rounds and choose one of those members.

• Ignoring the mistake bound.

  The conversion assumes a finite mistake bound M_A(H), which limits total mistakes.

  Fix: Connect the guarantee to both quantities: the mistake bound M_A(H) and the number of rounds T.

• Thinking that increasing T changes the algorithm's mistake bound.

  The source describes M_A(H) as the algorithm's contribution and T as the amount of online data in the bound.

  Fix: Keep the roles separate: M_A(H) limits total mistakes, while T determines how those mistakes affect the expected-risk bound.

Check Your Understanding

Key Takeaways

1. Online learning is a sequence of rounds in which the learner receives an instance, predicts, observes the correct label, and uses that label for future predictions.
2. The same example is first a test of the current hypothesis and then a source of training information.
3. Running an online learner on T independently sampled examples creates hypotheses h_1 through h_T.
4. The converted PAC learner chooses a uniformly random h_r from that sequence.
5. A finite mistake bound M_A(H) limits total online mistakes, producing an expected-risk bound of M_A(H) divided by T.