Online Learning

Definition

Online Learning

Online learning is a learning protocol in which examples are processed one round at a time and each prediction is made before its corresponding feedback is revealed.

Given a loss function $\ell$, at round $t=1,\dots ,T$ a learner with state $s_t$:

$$\begin{array}{rlrl}{x}_t& ⟼{\hat{y}}_t=h_t(x_t),& & \text{predict using the current hypothesis }{h}_t,\\ y_t& ⟼{\ell }_t=\ell ({\hat{y}}_t,y_t),& & \text{observe feedback and incur loss},\\ s_{t+1}& =U(s_t,x_t,y_t),& & \text{update before the next round}.\end{array}$$

Thus $h_t$ may depend on feedback from rounds $1,\dots ,t-1$, but not on the unrevealed label $y_t$.

Performance over a Sequence

The learner’s cumulative loss after $T$ rounds is

$$L_T=\sum _{t=1}^T\ell \left({\hat{y}}_t,y_t\right).$$

A common objective is low regret relative to the best fixed hypothesis in a comparison class $\mathcal{H}$:

$$R_T=\underset{\text{online learner}}{\underbrace{\sum _{t=1}^T\ell \left({\hat{y}}_t,y_t\right)}}-\underset{\text{best fixed hypothesis in hindsight}}{\underbrace{\underset{h\in \mathcal{H}}{\min }\sum _{t=1}^T\ell \left(h(x_t),y_t\right)}}.$$

If $R_T/T\to 0$, the learner’s average loss approaches that of this comparator, even though the learner had to predict each $y_t$ before seeing it.

Adaptation and Storage

Online learning is useful when data arrive continuously or when storing and repeatedly retraining on the full dataset is impractical. An incremental algorithm may retain only its current state rather than all past examples, although replay-based methods can still store previous data.

Sequential updates also make adaptation to a changing data distribution possible. They do not guarantee adaptation by themselves: when concept drift occurs, the update rule must give sufficient influence to recent observations rather than preserving old evidence indefinitely.

Unlike batch learning, which optimises over a fixed dataset, online learning couples prediction and learning within the same sequence of rounds. This can make individual updates more sensitive to noisy feedback, so learning rates, regularisation, averaging, or mini-batches are often used to stabilise them.