PAC Learning Model

Online learning has no separate training phase followed by a separate prediction phase.

Programming

The Timing Problem

Imagine that a learner must make a decision before knowing whether the decision is correct. Only afterward does the learner obtain the true answer and use it to make later decisions better. This timing pattern is the central idea of online learning. Learning and prediction are not placed in two separate stages; they are interwoven over a sequence of rounds.

One Online Round

An online learning round has four main events. First, the learner receives an instance. Second, the learner must make a prediction for that instance. Third, the correct label is revealed. Fourth, the learner uses that label to support future predictions. The next round then begins with another instance, so the process continues through consecutive rounds.

What happens first, when does the learner predict, when is the true label revealed, and when can the label support later predictions?

Key point

The learner predicts before seeing the correct label. The label becomes available only afterward and can then support predictions in later rounds.

Rounds in Sequence

Online learning is not one isolated prediction. It is a sequence of consecutive learning rounds. In each round, the learner receives an instance, predicts, obtains the correct label, and uses that label to support future predictions. The result is a repeated predict-and-learn schedule rather than a single training event followed by all later predictions.

How does one online learning round lead into the next, and how does information from earlier rounds support later predictions?

Best practice

When analyzing an online learning process, write the events in time order. Ask what the learner knows before the prediction, then identify what becomes available after the correct label is revealed.

From Test to Training

In the real world

Consider the papaya setting. In an online round, a learner receives one papaya and must predict its taste before obtaining the correct label. At that moment, the papaya is functioning as a test example because the learner is being asked to make a prediction about it. After the correct taste label is revealed, the same papaya can contribute to future predictions. It has now also served a training role.

How can the learner predict on an example before seeing its label, and then use that same labeled example to learn?

The important point is the change in role. The example is not permanently a test example or permanently a training example. Before its correct label is known, it is used for prediction. After the label is obtained, it can support future learning and prediction.

PAC and Online Schedules

The PAC learning model separates learning from prediction. The learner first receives a batch of training examples, learns a hypothesis from that batch, and then applies the learned hypothesis to new examples. Online learning uses a different schedule: the learner predicts each current instance before obtaining its correct label, and that labeled instance can then contribute to future predictions.

PAC learning model	Online learning
Starts with a batch of training examples	Processes examples through consecutive rounds
Learning happens before prediction on new examples	Prediction happens before the current correct label is obtained
A learned hypothesis is applied to new examples	The obtained label can support future predictions
Training and prediction are separate stages	Learning and prediction are interwoven

The central difference is the schedule of training, prediction, and label access.

What is the difference between a separate training phase followed by prediction in PAC learning and the interleaved predict-and-learn process of online learning?

Common Mistakes

Common mistake
Treating online learning as if it had one separate training phase followed by one separate prediction phase.
What it looks like
The learner trains on all available examples first and only later begins making predictions.
Why it fails
That schedule describes the separation emphasized in the PAC learning model, not the interleaved schedule of online learning.
Do this instead
Place prediction before the current correct label is revealed, then allow that label to support future predictions.
Common mistake
Assuming an example is only a test example.
What it looks like
The learner predicts the label and stops using the example once the answer is revealed.
Why it fails
In online learning, the same example can move from a test role to a training role after its correct label is obtained.
Do this instead
Track the example across time: it is first used for prediction and later can contribute to future predictions.
Common mistake
Putting the correct label before the prediction.
What it looks like
The learner sees the answer and then predicts the label for the current instance.
Why it fails
The online round requires a prediction before the correct label is revealed.
Do this instead
Use the order instance, prediction, correct label, and support for future predictions.

Check Your Understanding

EASY

A learner receives an instance, predicts its label, receives the correct label, and then uses that information when handling later instances. Is this schedule closer to PAC learning or online learning? Explain which event must happen before the correct label is available.

Hints

Recall whether training and prediction are separate or interwoven.
List the four events in an online learning round in order.

Your attempt (not saved)

Worked example

Identifying the Learning Schedule

A learner first receives a batch of training examples, learns a hypothesis, and then applies that hypothesis to new examples.

1
Identify the training arrangement
The learner receives a batch before making predictions on new examples.
2
Identify the prediction arrangement
Prediction occurs after the separate training stage.
3
Compare with the models
A batch training stage followed by a prediction stage matches the PAC learning model rather than the online schedule.

Result

This is the PAC learning model. Online learning would require the learner to predict each current instance before obtaining its correct label, then use that label to support future predictions.

Key Takeaways

1
Online learning proceeds through consecutive learning rounds.
2
Each round contains four events: receive an instance, make a prediction, obtain the correct label, and use that label to support future predictions.
3
An example can first serve as a test example and later serve as a training example after its correct label is obtained.
4
PAC learning separates a batch training stage from a later prediction stage.
5
Online learning interweaves prediction and learning across rounds.

At a glance

Online learning is organized as consecutive rounds rather than separate training and prediction phases.
The learner predicts before seeing the current instance's correct label.
Once revealed, the label can support predictions in later rounds.
The same example can move from a test role to a training role.
PAC learning uses a batch training stage followed by a prediction stage, unlike online learning.

More concepts starting with P