Online Machine Learning¶

Adapt a usable predictive or decision model during a sequence of arriving observations or feedback, rather than waiting for a completed fixed training set.

Version: v1 · 2026-10-04 · History
Domain-specific #: 13755
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Machine Learning, Online Learning → Computer Science & Software Engineering

Core Idea¶

Online machine learning is a regime in which a learner maintains a model or decision rule, encounters observations or feedback in sequence, and updates its state while the sequence is still unfolding. Unlike a learner trained once on a completed fixed data set, it can issue useful predictions or decisions at intermediate stages and adapt after additional information arrives. The persistent state may be parameters, a tree, accumulated statistics, a policy, or a mixture of these.^[1]^[2]

The regime is broader than one familiar “predict, receive true label, take one gradient step” loop. Some online learners receive labeled examples, others receive losses or only reward for the action taken; feedback can be delayed. Evaluation may use cumulative error, regret against a specified comparator, tracking of a changing environment, or resource cost. No single feedback type, memory cap, fixed-comparator theorem, batch-solution convergence guarantee or forgetting rule defines all online learning.^[1]^[3]^[4]^[5]

Structural Signature¶

Ordered encounter: information arrives or is revealed in a sequence, not necessarily as an independent identically distributed labeled batch.
Current state: the learner carries forward a model, parameters, statistics or policy that can affect its next output.^[2]
Interim output: the current state supports a prediction or decision before the eventual sequence is complete.
Feedback channel: a label, loss, gradient, reward or other update-relevant signal becomes available; it may be partial or delayed.^[3]^[4]
Update rule: new information revises the carried state so future outputs can differ from those under the earlier state.
Declared assessment: a setting-specific standard evaluates the sequence—predictive accuracy, regret against a chosen comparator, adaptation to drift, computational cost or a combination.^[1]^[5]

Condensed: streamed information → current usable state → output → available feedback → state revision → later output. The ordering and feedback can vary; immediate full supervision is a special case.

Sig role-phrases: ordered encounters → withhold future data; carried model state → shapes current prediction; interim output → is usable before stream completion; feedback channel → reveals update evidence; update rule → changes later state; comparator or metric → evaluates the sequence under stated assumptions.

What It Is Not¶

Not streaming inference alone. Serving a frozen model on live inputs produces outputs in sequence but does not update the learner.
Not necessarily one-example-at-a-time gradient descent. An online tree changes counts and splits; an online convex learner may make gradient-like updates; other algorithms use different state transitions.^[2]^[1]
Not necessarily zero replay or constant total memory. VFDT need not retain examples, yet its tree and associated statistics occupy space proportional to model size. Other online methods may use buffers or memory-dependent losses.^[2]^[5]
Not guaranteed to match a batch-trained model. VFDT has a specific asymptotic split-selection argument; that is not a theorem about every online learner or every drifting data stream.^[2]
Not universally fixed-comparator regret. A best fixed model in hindsight is one formal benchmark, while dynamic or policy regret is used under other assumptions.^[1]^[5]
Not continual learning by synonym alone. Continual-learning work may emphasize retention across tasks and avoiding catastrophic forgetting; online learning here emphasizes sequential within-stream updates. They can overlap.

Scope of Application¶

An incremental decision tree can update counts at current leaves and use a statistical criterion to decide when to split. Domingos and Hulten's original VFDT work demonstrates a model usable throughout a high-speed stream while retaining tree and sufficient-statistics state rather than storing all observations.^[2]

In online optimization, a learner chooses a decision, then receives loss information and revises its later decisions. Regret measures its cumulative loss relative to a precisely declared comparator; a small regret bound does not imply low absolute loss if the comparator itself performs poorly.^[1]

In delayed-feedback or bandit-feedback settings, the update signal may arrive later or reveal only the outcome of the chosen action. Those cases are still online because the learner acts during the sequence and adjusts to available feedback; forcing an immediate full true label into their definition would misclassify them.^[3]^[4]

Clarity¶

“Incremental” names the stepwise update aspect; “online” adds the temporal situation in which outputs may matter before future data are known. This separates the learning regime from a specific model representation. A tree, linear classifier or bandit policy can each participate in an online regime, yet a fixed tree used on streaming inputs is not itself learning online.

The seed's promise that memory and per-example work remain bounded independently of stream length is unsound as a general statement. VFDT illustrates the distinction: it can process each example efficiently without storing all examples, but the growing tree and statistics still require space proportional to their own size.^[2]

Manages Complexity¶

Carrying forward sufficient state lets a learner respond to a long or unbounded stream without retraining an entire model from scratch after each arrival. In VFDT, leaf statistics summarize what has passed through a leaf and support later split choices. In gradient-style online updates, parameters summarize the effect of earlier losses. These are different compression mechanisms; neither proves universal constant memory or convergence to the same final model.^[2]^[1]

An online formulation also makes information availability explicit. A hindsight batch optimizer can see future examples; an online learner cannot use information not yet revealed. Delayed or partial feedback further constrains what it can learn at each step.^[3]^[4]

Abstract Reasoning¶

To decide whether a method is online, ask: when is its output used, what information has arrived by then, what state persists, and what update follows available feedback? Then ask which comparator and assumptions justify any performance claim. Fixed-comparator regret, dynamic regret and statistical convergence answer different questions.^[1]^[5]

For drift, a learner may discount older information, detect distribution changes, or compare against a changing sequence of reference decisions. None of those strategies is mandatory for the broad identity. The correct diagnostic is whether the update rule and assessment match the expected drift and feedback schedule.^[5]

Knowledge Transfer¶

The stream/state/update skeleton transfers between a Hoeffding tree and a gradient-based learner even though one grows a discrete tree and the other adjusts continuous parameters. It also transfers to partial-feedback decision policies if the feedback channel is retyped explicitly. The transfer fails if one imports a VFDT-specific memory claim or an online-convex-optimization regret bound into a different learner without proving its assumptions.^[2]^[1]^[4]

The broader prime Learning captures durable experience-driven state change. Online machine learning adds the domain-specific computational regime of ordered inputs, interim outputs, feedback and sequential model revision.

Examples¶

Constructed unsplit leaf of a streaming tree¶

A newly created, unsplit VFDT-style leaf predicts the majority class recorded in its leaf counters, breaking an initial tie in favor of \(0\). In a constructed three-event prefix, \((x=\text{red},y=1)\) arrives: the leaf predicts \(0\), then updates counts from \((n_0,n_1)=(0,0)\) to \((0,1)\). Next \((\text{blue},0)\) arrives: it predicts \(1\), then counts become \((1,1)\), so the tie rule would predict \(0\) next. Third, \((\text{red},1)\) arrives: it predicts \(0\), then counts become \((1,2)\) and the next prediction is \(1\). The point is the before/after usable state, not a claim that three events suffice for a Hoeffding split. Actual VFDT also maintains attribute-value statistics for candidate splits; both these statistics and the tree can grow even though past examples need not all be stored.^[2]

Mapped back: ordered labeled events = three red/blue arrivals; current state = leaf counters; interim outputs = \(0,1,0\); feedback = labels \(1,0,1\); updates = \((0,0)\to(0,1)\to(1,1)\to(1,2)\); later model output = majority-class \(1\); storage claim = no fixed total-memory bound.

Constructed two-action online decision learner¶

Let the action set be \(\{A,B\}\). A toy full-information rule starts with \(A\), then on each later round chooses whichever action had lower loss in the previous round. Before each decision it has not seen that round's losses. For three rounds let the revealed loss vectors \((\ell(A),\ell(B))\) be \((1,0)\), \((0,1)\), \((0,1)\). The rule chooses \(A,B,A\), incurs \(1+1+0=2\), and updates its next choice after each revealed vector. Fixed \(A\) would incur \(1+0+0=1\), fixed \(B\) would incur \(0+1+1=2\); regret to the best fixed action in hindsight is \(2-1=1\). This is an author-constructed arithmetic example of the online-decision protocol, not a performance guarantee for the toy rule or a result reported by the MIT notes.^[1]

Mapped back: ordered rounds = three; carried state = previous round's lower-loss action; interim actions = \(A,B,A\); feedback = complete two-action loss vector after each action; update = choose previous winner; assessment = cumulative learner loss \(2\) versus best fixed comparator \(A\) loss \(1\), regret \(1\).

Fixed model on a live feed¶

A pre-trained classifier scores new transactions indefinitely, but its parameters never change. The application processes a stream; the model does not learn online. The missing role is state revision from newly available information.

Structural Tensions¶

Timely adaptation versus feedback limits. A learner that acts promptly on a partial or delayed signal can produce decisions before later evidence arrives, but those decisions may be based on stale state; waiting for fuller labels improves information quality but forfeits timely intervention. In bandit feedback, observing only the chosen action's outcome saves the requirement to reveal all alternatives but makes counterfactual losses harder to estimate. These are protocol-dependent pressures, not a promise that any delay policy is optimal. Diagnostic: what could the learner actually know at each update, and what decision opportunity is lost by waiting?^[3]^[4]

Historical information versus resource control. Retaining detailed past information can support later split decisions or adaptation to recurring patterns, but consumes storage and update work; compressing history into leaf counts or parameters limits stored examples while possibly discarding distinctions a future task would need. VFDT's sufficient statistics illustrate compression, not constant total memory as leaves and their statistics grow. Diagnostic: does a claimed memory bound cover retained examples, total model size, or computation per round—and what information is lost?^[2]^[5]

Structural–Framed Character¶

The stream/state/feedback/update order is structural, but the entry sits in a protocol-framed region of the spectrum because the designer determines when labels arrive, which losses are visible and how success is scored. The evaluative weight of a regret of \(1\), for example, depends on the chosen fixed comparator and horizon; it is not an intrinsic goodness score. Human and institutional practice shapes the stream: sensors, web services and annotation pipelines determine observation order, latency and memory budgets. Machine-learning research made “online” a technical contrast with a fixed completed training set, while the term also circulates colloquially as mere internet connectivity. It travels literally from trees to two-action decision rules when usable interim state and feedback-driven revision remain; applying it to a static model served over the internet imports the word without the learning mechanism. Its character: a sequential model-revision regime with a stable temporal skeleton and task-dependent feedback, resource and evaluation frames.

Structural Core vs. Domain Accent¶

The portable skeleton is learning from experience while action and evidence alternate; that broad relation belongs under Learning. The domain-bound mechanism is a computationally maintained predictive or decision state, an information-arrival protocol, an update rule, and a declared sequential assessment such as cumulative loss. The named entry fails the prime bar because ordinary skill learning, organizational learning or biological adaptation need not expose a formal prediction/loss stream or model state, while a static inference service exposes a stream without revision. Only the broad Learning skeleton transfers automatically; any VFDT statistics, regret comparator or memory bound must be re-established in the receiving regime.

This entry is a kind of Learning.

Learning is the accepted strict genus: online machine learning persistently revises predictive or decision state as information arrives. Incrementalism is a related pattern, not a genus; an incremental decision tree is one possible model implementation of this regime. Static streaming inference without model revision is outside this child, and no universal convergence or regret guarantee follows.

Relationships to Other Abstractions¶

Current abstraction Online Machine Learning Domain-specific

Parents (1) — more general patterns this builds on

Online Machine Learning is a kind of Learning Prime

Sequential revision of a persistent predictive or decision state from arriving observations or feedback is specialized experience-driven learning.

Hierarchy paths (2) — routes to 2 parentless roots

Online Machine Learning → Learning → Adaptation

Show alternative path (1)

Neighborhood in Abstraction Space¶

Online Machine Learning sits in a sparse region of the domain-specific corpus (94^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

Model-Free Reinforcement Learning — 0.79
Reinforcement learning — 0.78
Self-Organizing List — 0.78
N-Back Task — 0.78
Reactive Programming — 0.78

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Online learning may process one case at a time, but it is not defined by one optimizer, no replay, fixed memory or one regret criterion. “Incremental decision tree” is a member family. Delayed labels and bandit feedback are valid variants. A continuously serving but frozen model is the decisive negative case.^[2]^[3]^[4]

References¶

[1] MIT 9.520, Online Learning, lecture 9 (2008), sequential comparison and regret. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j

[2] Domingos and Hulten, “Mining High-Speed Data Streams” (KDD 2000), original VFDT paper. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l

[3] Joulani, György and Szepesvári, “Online Learning under Delayed Feedback” (ICML 2013), original paper. registry ↩a ↩b ↩c ↩d ↩e ↩f

[4] MIT 6.7980, “Learning with bandit feedback”, institutional lecture. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g

[5] Zhao, Wang and Zhou, “Non-stationary Online Learning with Memory and Non-stochastic Control” (AISTATS 2022), original dynamic-policy-regret study. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g