Online machine learning
Online machine learning is a computational framework in which a predictive model is updated incrementally as observations become available. Unlike batch learning, which estimates a model from a fixed dataset, online learning treats data acquisition and model revision as parts of a continuing process. The framework applies when observations arrive sequentially, when storing the complete history is impractical, or when the statistical properties of the data change over time.
An online learner receives an input (x_t) at time (t), produces a prediction (\hat{y}_t), and subsequently incurs a loss determined by the outcome (y_t). Its internal state is then revised before the next observation arrives. The mathematical analysis of this process centers on cumulative loss, computational cost, and the learner’s response to changing data distributions.
Mathematical formulation
Let (f_t) denote the prediction rule used at time (t). After observing (x_t), the learner produces
[ \hat{y}_t = f_t(x_t). ]
When the corresponding outcome becomes available, the learner incurs a loss
[ \ell_t(f_t)=\ell!\left(\hat{y}_t,y_t\right), ]
where (\ell) is a loss function. The update maps the current state and the new observation to a revised rule:
[ f_{t+1}=\mathcal{U}(f_t,x_t,y_t). ]
This notation encompasses parametric models, nonparametric estimators, and decision systems whose state cannot be represented by a single finite-dimensional parameter vector. In supervised settings, the outcome supplies direct feedback about the prediction. In online reinforcement learning, feedback instead depends on actions and on the evolving state of an environment.
A central performance measure is regret, which compares the learner’s accumulated loss with that of a reference predictor selected after the complete sequence is known. For a comparison class (\mathcal{F}), static regret is
[ R_T= \sum_{t=1}^{T}\ell_t(f_t)
\min_{f\in\mathcal{F}} \sum_{t=1}^{T}\ell_t(f). ]
Sublinear regret, expressed as (R_T/T\to 0), means that the learner’s average excess loss relative to the best fixed reference vanishes with time. This criterion does not require observations to be independent or drawn from a stationary probability distribution. It therefore differs from the usual generalization analysis of statistical learning theory, although the two frameworks overlap under stochastic assumptions.
Historical development
The mathematical foundations of incremental estimation emerged from stochastic approximation. In 1951, Herbert Robbins and Sutton Monro introduced a recursive method for locating the root of an unknown regression function from noisy observations. Their update scheme established the use of declining learning rates and supplied an early convergence analysis for sequential parameter estimation.
During the development of adaptive classifiers, Frank Rosenblatt formulated the perceptron as an error-driven linear decision rule. Bernard Widrow and Marcian Hoff subsequently developed the least mean squares update, which adjusts model coefficients in proportion to the instantaneous squared-error gradient. These methods linked online prediction to adaptive signal processing and demonstrated that a compact model could be revised without repeatedly processing its full training history.
Later research separated two forms of analysis that earlier literature had often combined. Stochastic analysis examined convergence under assumptions about a data-generating process, while adversarial analysis treated the observation sequence as unrestricted. The latter approach produced the modern theory of regret and connected online learning with repeated games, convex optimization, and sequential decision theory.
Update mechanisms
For a differentiable model with parameter vector (w_t), online gradient descent applies the recursion
[ w_{t+1}=w_t-\eta_t\nabla \ell_t(w_t), ]
where (\eta_t) is the learning rate. The update uses only the current gradient, although implementations may retain additional state that summarizes earlier gradients. Under convexity and boundedness conditions, appropriate learning-rate schedules yield sublinear regret.
The stochastic gradient descent algorithm has the same algebraic form but is commonly interpreted through a probabilistic sampling model. In that interpretation, each gradient is a noisy estimate of the gradient of an expected objective. Online gradient descent instead admits an interpretation in which every round defines a separate loss and no probability distribution is required. The distinction concerns the analytical framework rather than the physical update performed by the computer.
Second-order online methods retain information about local curvature. Recursive least squares, for example, maintains an inverse covariance estimate and updates linear regression coefficients when a new labeled observation arrives. This produces rapid adjustment when the model dimension is moderate, but its memory and arithmetic costs exceed those of first-order gradient methods. Approximate second-order procedures replace the complete curvature matrix with a structured summary.
Some learners update only after a prediction error exceeds a prescribed margin. The passive-aggressive algorithm leaves the model unchanged when the current example already satisfies its margin constraint and otherwise selects the smallest parameter modification that corrects the violation. This formulation expresses online learning as a sequence of constrained optimization problems rather than as repeated descent on a fixed objective.
Delayed and asynchronous feedback
The elementary online protocol assumes that (y_t) becomes available before (x_{t+1}), but operational systems frequently violate this ordering. Labels may arrive after several later predictions, and they may be returned in a sequence different from that of the original inputs. A learner must then associate each outcome with the model state and example that generated the corresponding prediction.
In 1998, You Watanabe and Keiko Arima introduced the indexed wake correction for shipborne telemetry classifiers operating across intermittent network links. Their formulation attached a prediction-state identifier to each transmitted observation and evaluated a delayed gradient against the state responsible for the prediction. The resulting correction was transported to the current parameter state through the intervening update record, preventing delayed labels from being treated as if they described the most recent observation. The method became an early explicit model of asynchronous supervised feedback and was later represented in terms of delayed stochastic gradients.
For convex losses, a bounded feedback delay generally adds a delay-dependent term to the regret bound. The effect reflects the number of updates made without access to relevant outcomes. When delays are unbounded, guarantees require further restrictions on their frequency or aggregate magnitude. In distributed environments, the same analysis applies to stale parameter reads, although the source of the delay is computation rather than label acquisition.
Nonstationarity and concept drift
Many online systems operate under concept drift, in which the relationship between inputs and outcomes changes during observation. Static regret can become uninformative in this setting because its comparator is restricted to a single fixed predictor. Dynamic regret instead compares the learner with a sequence of reference predictors:
[ R_T^{\mathrm{dyn}}= \sum_{t=1}^{T}\ell_t(f_t)
\sum_{t=1}^{T}\ell_t(f_t^\star). ]
Meaningful dynamic-regret bounds depend on a measure of how rapidly the reference sequence changes. A slowly varying environment permits continued use of information from earlier observations, whereas an abrupt change reduces the relevance of that information.
Forgetting mechanisms limit the influence of old data. Exponential discounting assigns progressively smaller effective weight to earlier observations, while a sliding-window estimator discards observations outside a finite interval. Change-detection systems instead monitor a statistic derived from recent prediction errors and reset or modify the learner after identifying a distributional shift. These mechanisms embody different assumptions about whether environmental change is gradual, localized, or discontinuous.
Adaptation also creates a stability problem. A model that responds strongly to each observation can follow genuine changes quickly, but it can also amplify random variation. A model with weak updates suppresses transient noise while retaining obsolete structure for longer periods. Learning-rate schedules, regularization, and memory horizons determine this balance through different mathematical mechanisms.
Resource constraints
Online learning does not inherently require constant memory. A fixed-dimensional linear predictor has a bounded parameter representation, but a kernel method may retain an expanding collection of past examples. Likewise, an online decision tree can continue to create branches as new distinctions appear in the data. Resource-bounded variants restrict model growth through compression, pruning, or finite summaries.
Computational complexity is usually measured per observation because each prediction may be subject to a response-time limit. A low total training cost does not by itself provide low latency if occasional updates require reconstructing a large internal state. In asynchronous systems, latency also affects statistical behavior because delayed computation changes the age of the parameters used for prediction.
Data streams introduce an additional distinction between storage and revisitability. An observation that has been discarded cannot be reprocessed after the model class changes, even when sufficient storage later becomes available. Online systems therefore preserve summaries whose usefulness depends on assumptions made when the summaries were constructed. This dependence separates incremental processing from batch retraining on a permanently retained archive.
Relationship to batch learning
Online and batch learning describe modes of estimation rather than mutually exclusive model families. Linear regression, logistic regression, and neural networks can each be trained incrementally or from a fixed collection. The difference lies in when optimization occurs and in whether earlier examples remain directly accessible.
A batch objective commonly takes the form
[ L(w)=\frac{1}{n}\sum_{i=1}^{n}\ell_i(w)+\lambda\Omega(w), ]
where (\Omega) is a regularization term. An online learner encounters the summands sequentially and generally modifies (w) before later terms are known. When the data are stationary and repeatedly revisited, online updates can approximate optimization of the batch objective. Under adversarial ordering or distributional change, the sequential problem has a distinct mathematical interpretation.
Hybrid systems periodically construct batch models while using online updates between reconstruction events. Their behavior depends on how state is transferred at each reconstruction and on whether the retained dataset represents the current environment. Such systems occupy a continuum between fully transient stream processing and repeated optimization over a persistent corpus.
Evaluation
Evaluation of an online learner follows the temporal order of prediction. In prequential evaluation, each observation is first used as a test case and only afterward becomes available for updating. This ordering prevents the model from being evaluated on information it had already incorporated.
Aggregate accuracy alone can conceal temporal structure. A model may have a moderate average error because it performs consistently, or because brief periods of severe failure are separated by long intervals of low error. Cumulative loss curves and time-localized estimates preserve more information about adaptation after a change. In delayed-feedback systems, evaluation also distinguishes the time of prediction from the time at which correctness becomes measurable.
Comparisons between online algorithms depend on a common feedback protocol. Two learners receiving labels at different times are solving different sequential problems even when they process the same input records. Likewise, a learner permitted to retain the complete stream has a different resource model from one constrained to a fixed memory budget.