Online, Streaming, and Active Learning

Online learning formalizes a repeated-decision protocol distinct from ordinary batch supervised learning. At each round, the learner makes a prediction, the true outcome or loss is then revealed, and the learner updates before the next round begins; unlike batch learning, there is no fixed training set collected in advance, and examples may arrive too quickly or in too great a volume to store in full. This setting is a natural fit for streaming applications, where the underlying data distribution may also be shifting over time rather than remaining fixed, a possibility standard i.i.d.-based supervised learning theory does not accommodate. It is also the natural framework for problems where data genuinely accrues one observation at a time, such as a recommendation system reacting to each new click or a trading algorithm reacting to each new market tick, since retraining a full batch model after every single new observation would be both wasteful and, for large models, computationally infeasible.

The central performance measure in this framework is regret, defined as the online learner's cumulative loss over a sequence of rounds compared to the cumulative loss the single best fixed hypothesis in some comparison class would have achieved in hindsight over the same sequence. A learner with low, typically sublinear, regret performs almost as well as the best fixed strategy, even though it had to commit to each prediction before that round's outcome was known and even without any assumption that the sequence of examples was generated i.i.d. or non-adversarially. Online gradient descent is the workhorse algorithm in this framework: at each round it updates its parameters by taking a step in the negative subgradient direction of the loss incurred that round, an update rule structurally identical to the stochastic gradient descent used to train most modern machine learning models, but here justified and analyzed through worst-case regret bounds rather than through convergence to a fixed population risk minimizer.

Convexity of the loss function plays a central structural role: it is what makes efficient, provably low-regret algorithms possible for online convex optimization, since a convex loss guarantees that local gradient information reliably points toward better solutions even though the learner never sees the full loss landscape at once. Classification losses are not convex in general, but surrogate convex losses and randomized prediction strategies extend the framework's guarantees to classification and other originally non-convex settings. The framework also generalizes to bandit settings, where the learner only observes the loss of the action it actually took rather than the loss it would have incurred under every possible action, a much more limited feedback signal relevant whenever full supervision is unavailable at prediction time, such as an online advertising system that only learns whether the ad it actually showed was clicked, never what would have happened had it shown a different ad.

Streaming learning shares online learning's one-example-at-a-time protocol but emphasizes additional practical constraints: the stream may be effectively unbounded, arrive at high velocity, and require the learner to operate within strict, bounded memory and per-example processing time, ruling out any strategy that assumes the whole history of the stream can be revisited on demand. A defining challenge specific to long-running streaming deployments, one that a purely online-learning framing does not directly address, is concept drift, a change over time in the statistical relationship the model is trying to capture. Gama and colleagues' survey distinguishes real concept drift, a change in the conditional relationship between inputs and target, p(y given X), which genuinely requires the model's decision boundary to change, from virtual drift, a change only in the input distribution p(X) with the underlying p(y given X) left intact, meaning an existing model may in fact still be correct even though the incoming data now looks different. Telling these apart matters in practice, since reacting to virtual drift as though it were real drift wastes retraining effort on a model that did not actually need to change.

The survey organizes adaptive learning systems around four modular components that can be combined in different ways. Memory management determines which historical data is retained for training or monitoring, commonly via a sliding window of fixed or adaptively varying size, or via gradual forgetting mechanisms that downweight older examples rather than discarding them outright. Change detection identifies when drift has occurred, using techniques ranging from statistical process control and sequential hypothesis testing to direct monitoring of feature or error-rate distributions. The learning component itself then updates the model, either through blind, continuous adaptation applied regardless of detected drift, or informed, trigger-based retraining launched specifically when drift is detected. Loss estimation tracks ongoing model performance to inform both of the previous components.

In practice, drift manifests in qualitatively different patterns worth distinguishing: sudden drift, an abrupt regime change occurring within a short window; gradual drift, a slow transition during which examples from both the old and new concept are intermixed for a time; incremental drift, a steady, continuous evolution without any single sharp transition point; and recurring concepts, where a previously seen pattern reappears after some time away, such as seasonal purchasing behavior that returns each year. Evaluating drift-handling systems is itself complicated by the fact that true labels for streaming examples are frequently delayed or costly to obtain, so a change-detection mechanism watching the error rate directly may only learn of a problem well after it began. This motivates combining streaming methods with the active learning strategies covered in the next lesson, using selective labeling both to control labeling cost and to give the drift detector timelier feedback about which arriving examples are worth the expense of confirming.

Active learning starts from the observation that in many domains, unlabeled data is abundant but labels are the scarce and costly resource, requiring expert time, laboratory work, or expensive human judgment. Settles' survey frames the central idea plainly: letting the learner itself choose which examples get labeled next, rather than labeling a randomly sampled batch, can reach a target accuracy using substantially fewer total labels. The survey distinguishes several scenarios by how examples become available for querying: pool-based active learning selects the single most informative example from a large, already-collected pool of unlabeled data; stream-based active learning must decide, for each example as it arrives in sequence, whether to request its label immediately, without the benefit of comparing it to a full assembled pool; and membership query synthesis allows the learner to construct entirely new query instances rather than selecting among existing ones.

The simplest and most widely used family of query strategies is uncertainty sampling, which selects the unlabeled example the current model is least confident about, measured variously as the least-confident predicted class probability, the smallest margin between the top two predicted class probabilities, or the highest entropy across the full predicted class distribution. Query-by-committee instead trains multiple models, or hypotheses, consistent with the labels collected so far, and queries the example on which committee members disagree most, framed theoretically as an attempt to most efficiently shrink the version space of hypotheses still consistent with the data. More computationally demanding strategies, including expected model change and expected error reduction, more directly target the actual training objective by estimating how much labeling a candidate example would shift model parameters or reduce future error, at the cost of requiring repeated retraining or simulation to evaluate candidates.

A known failure mode of pure uncertainty sampling is that it can repeatedly select rare, unrepresentative outliers sitting near the decision boundary rather than examples that are genuinely informative about the broader data distribution. Density-weighted methods correct for this by combining an informativeness score with a representativeness score derived from an example's similarity to the overall data distribution, so isolated points far from where most of the probability mass lies are downweighted even if the model is technically uncertain about them. In deployed systems, active learning is frequently combined with the online and streaming techniques from earlier in this module: a system might learn incrementally from a live data stream while simultaneously and selectively requesting labels only for the examples it finds most uncertain or most likely to reveal concept drift.