Online Classification
An online convex optimization problem is defined by a convex hypothesis class, a domain, and a loss function convex in its first argument.
One Round at a Time
Online classification can be understood as a repeated prediction problem. The learner does not make one prediction and finish. Instead, the process repeats across time steps: the learner chooses a vector from a hypothesis class, the environment provides a domain element, and the learner suffers a loss determined by the chosen vector and that element.
What do you think happens?
What is the order of events in one online round?
Reveal answer
Answer: Prediction, then environment response, then loss
The learner first chooses a vector. The environment then provides a domain element, and the resulting interaction determines the loss suffered by the learner.
Tracing a Repeated Problem
A Three-Round Symbolic Trace
Trace the roles of the learner, the environment, and the loss across three online rounds.
Round 1: The learner chooses a prediction vector from the hypothesis class. The environment provides a domain element. The learner then incurs the loss determined by that vector and element.
Round 2: The same order repeats. The learner makes another prediction, the environment supplies another domain element, and a loss is incurred.
Round 3: The learner again predicts, the environment responds, and the resulting loss becomes another term in the learner's cumulative loss.
After the rounds: The learner's performance is considered across the repeated sequence, not only by inspecting one isolated round.
An online problem is a sequence of prediction, environment response, and loss events. Repeating this sequence produces cumulative losses that can later be compared.
The important point in this trace is the dependency between the events. A loss is not described as an independent quantity appearing before prediction. It is incurred after the learner has chosen a vector and the environment has provided a domain element. Across rounds, these individual losses form the cumulative loss used in regret analysis.
Why Convexity Matters
An online convex optimization problem has two convexity requirements. First, the hypothesis class is convex. This means the available hypotheses form a convex set. Second, the loss function is convex in its first argument, which is the learner's predicted vector. These conditions describe the mathematical setting in which the repeated prediction problem is studied.
Learner and Comparator
The learner's prediction vector and the competing vector play different roles. At each time step, the learner chooses a vector from the hypothesis class. Regret analysis then evaluates the learner relative to a competing vector, written as w⋆, that belongs to the same hypothesis class. The learner's chosen vector can be associated with the individual prediction at a particular round, while w⋆ is the reference used for the comparison.
| Role | What it represents | How it is used |
|---|---|---|
| Learner's prediction vector | The vector chosen by the learner at a time step | Determines the learner's loss for that round together with the environment's domain element |
| Competing vector w⋆ | A vector in the hypothesis class used as a reference | Provides the competing cumulative loss in regret analysis |
Cumulative Loss and Regret
Regret is a cumulative comparison. It is the difference between the learner's cumulative loss and the cumulative loss of a competing vector w⋆. Therefore, regret is not determined by looking only at the loss from one round. The comparison gathers the learner's losses across the repeated prediction problem and compares them with the losses associated with the competing vector across that same sequence.
Reading a Regret Comparison
Suppose an online process has several rounds. For each round, consider both the loss incurred by the learner's prediction vector and the loss associated with the competing vector w⋆.
Collect learner losses: Record the loss incurred after each learner prediction and environment response. These terms together form the learner's cumulative loss.
Collect competing losses: For the same sequence of rounds, consider the losses associated with w⋆. These terms together form the competing cumulative loss.
Compare the totals: Regret is the difference between the learner's cumulative loss and the competing vector's cumulative loss.
A one-round loss is only one part of the analysis. Regret comes from comparing the two cumulative quantities over the repeated sequence.
Mistakes in Interpretation
Reversing the order of events
The stated sequence is prediction, environment response, and then incurred loss.
Fix:
Read each round as a three-stage process: learner prediction, environment response, loss.Treating the competing vector as the learner's current prediction
The learner's vector is chosen at a time step, while w⋆ is the competing vector used as a reference in regret analysis.
Fix:
Keep the learner's prediction vector and the competing vector as separate roles.Using only one round to define regret
Regret is evaluated using cumulative losses over the repeated prediction problem.
Fix:
Accumulate both sides across the sequence before making the comparison.Confusing the two convexity assumptions
The framework requires both a convex hypothesis class and a loss function convex in its first argument.
Fix:
Check the structure of the hypothesis class and the convexity of the loss in the learner's predicted vector separately.
Practice the Framework
Describe one online round in the correct order, then explain how the losses from several rounds would be used to evaluate regret relative to a competing vector w⋆.
Hints
- Begin with the vector chosen by the learner.
- Identify what the environment provides next.
- Explain that regret compares cumulative learner loss with cumulative competing-vector loss.
A proposed online convex optimization problem has a hypothesis class and a loss function. List the two convexity checks you would make before describing it as an online convex optimization problem.
Hints
- Check whether the hypothesis class is convex.
- Check whether the loss function is convex in its first argument, the learner's predicted vector.
Key Takeaways
- Each online round follows the order: learner prediction, environment response, and incurred loss.
- The hypothesis class must be convex, and the loss function must be convex in its first argument, the learner's predicted vector.
- The learner's prediction vector is the round-by-round choice; w⋆ is a competing vector in the hypothesis class used for comparison.
- Regret compares cumulative learner loss with cumulative loss associated with the competing vector, not merely one round's loss.
Key Takeaways
- Online classification in this framework is a repeated prediction problem.
- Every round moves from prediction to environment response to loss.
- Convexity applies both to the hypothesis class and to the loss function in the learner's predicted vector.
- Regret is a cumulative comparison between the learner and a competing vector w⋆.