Streaming Data and Online Optimization

"I never see a dataset, only the next row. I predict, I am scored, I am told the answer, and I nudge myself a little. Then the row is gone and I will never see it again. I have no epochs, no shuffles, no second looks. I am learning the way a river learns its bed, one drop forever."

An Online Learner Updating Itself One Sample at a Time, Forever

Part V opened in Chapter 19 by asking not just what a model predicts but how sure it is. We now change a different assumption, one even more basic than uncertainty: that the data sits still. In this chapter the data moves. It arrives as an unbounded stream, its statistics drift, and the model must keep up without ever stopping. This first section establishes the streaming setting and the optimization machinery that makes learning-on-the-move possible; Section 20.2 then asks what happens when the stream's distribution itself changes (concept drift), and the rest of the chapter builds models that adapt and remember. We use the unified notation of Appendix A: $\mathbf{x}_t$ the feature vector arriving at time $t$, $y_t$ its label, $\hat{y}_t$ the model's prediction, $\boldsymbol{\theta}_t$ the parameters before seeing example $t$.

Why does streaming deserve its own treatment rather than "just retrain periodically"? Because the constraints are qualitatively different, not merely quantitatively tighter. A batch learner that you retrain nightly still assumes you can store a window and afford a full pass; a true streaming learner assumes neither. The Sensor and IoT telemetry thread of this book (introduced in Chapter 8 and carried through deployment in Chapter 34) is the canonical example: a fleet of machines emits millions of readings per hour, forever, and you are asked to flag failures in real time on a device with kilobytes of RAM. You cannot keep the stream; you cannot wait for a batch; you must learn as the data flies past. The competencies this section installs are these: to frame a problem in the streaming, predict-then-update protocol and evaluate it prequentially; to read online gradient descent as the minimizer of regret and to state the $O(\sqrt{T})$ guarantee; to choose among the classic online algorithms for a given stream; to reason about the memory and time budget and use reservoir sampling when a sample is unavoidable; and to implement online SGD and recursive least squares from scratch and recognize them inside a library.

1. The Streaming Setting: Predict, Then Update Beginner

In the batch learning of every previous chapter, a dataset $\{(\mathbf{x}_i, y_i)\}_{i=1}^{N}$ is given all at once: you can scan it many times, shuffle it, split it into train and test, and fit until convergence. The streaming setting removes all of that. Examples arrive one at a time in a fixed temporal order $t = 1, 2, 3, \dots$, the sequence is potentially unbounded (there is no final $N$), and you cannot assume you can store more than a tiny, fixed amount of it. Each example is seen once and then, for all practical purposes, gone. There is no second epoch because there is no first one to repeat.

Within that constraint the only sensible interaction protocol is a strict loop, the same loop every online learner in this chapter runs. At each step $t$: (1) the environment reveals the features $\mathbf{x}_t$; (2) the model emits a prediction $\hat{y}_t$ using its current parameters $\boldsymbol{\theta}_t$; (3) the true label $y_t$ is revealed; (4) the model suffers a loss $\ell(\hat{y}_t, y_t)$ and performs one cheap update $\boldsymbol{\theta}_{t+1} = \text{update}(\boldsymbol{\theta}_t, \mathbf{x}_t, y_t)$; (5) the example is discarded. This is the predict-then-update protocol, and its ordering is not a stylistic choice but the definition of the setting: the model must commit to a prediction before it is allowed to learn from the answer, exactly as a forecaster must commit to tomorrow's number today.

That ordering hands us a free and honest evaluation procedure, prequential (predictive-sequential) evaluation. Because every prediction $\hat{y}_t$ is made before the model has seen $y_t$, the prediction is genuinely out-of-sample with respect to that example. So we can simply accumulate the per-step losses as we go and report the running average, $\bar{L}_t = \frac{1}{t}\sum_{s=1}^{t} \ell(\hat{y}_s, y_s)$, and it is an unbiased estimate of predictive performance with no held-out set required. The test set is the immediate future, every example serves as a test point exactly once (before training) and a training point exactly once (after), and the model is continuously validated on data it has not yet learned from. This is the streaming reincarnation of the time-ordered backtesting we built in Section 2.6: same principle (never test on the past relative to training), pushed to a window of one. Figure 20.1.1 lays out the loop and the prequential accumulator.

Two practical consequences follow immediately. First, memory is bounded by design: the model's state is fixed-size and a discarded example never returns, so a streaming learner can run for years on a microcontroller where a batch learner would have exhausted storage in minutes. Second, the model is always slightly stale: it predicts $\hat{y}_t$ with parameters that have not yet absorbed example $t$, so in a non-stationary stream it is forever chasing a moving target, one step behind. That lag is exactly what the concept-drift machinery of Section 20.2 exists to shorten, and managing it is the central craft of the whole chapter.

2. Online Convex Optimization and the Regret Framework Intermediate

Batch learning minimizes a fixed objective, the average loss over a fixed dataset. Streaming has no fixed dataset to average over, so we need a different yardstick. The right one is regret, and the framework that supplies it is online convex optimization (OCO). The setup is a game played over $T$ rounds: at round $t$ the learner picks parameters $\boldsymbol{\theta}_t$ from a convex set, then an adversary reveals a convex loss function $\ell_t(\cdot)$ (in our case $\ell_t(\boldsymbol{\theta}) = \ell(\langle \boldsymbol{\theta}, \mathbf{x}_t\rangle, y_t)$), and the learner suffers $\ell_t(\boldsymbol{\theta}_t)$. Crucially the learner commits before seeing $\ell_t$, exactly the predict-then-update ordering of subsection one.

We cannot ask the learner to minimize total loss outright, because an adversary could make any sequence of choices look bad. Instead we measure the learner against the best single fixed parameter vector chosen with full hindsight, after all $T$ losses are known. That gap is the regret:

Regret asks: how much worse did the online learner do, summed over the whole stream, than the best model it could have committed to from the start had it known the future? The goal of an online algorithm is sublinear regret, $\mathrm{Regret}_T = o(T)$, because then the time-averaged regret $\mathrm{Regret}_T / T \to 0$: per example, the online learner becomes as good as the best fixed model in hindsight. Sublinear regret is the streaming analogue of "convergence", and it is achievable even against an adversary, which is what makes it so powerful in non-stationary settings.

The workhorse that achieves it is online gradient descent (OGD): take one gradient step per example,

with $\eta_t$ a (possibly decaying) learning rate. This is just stochastic gradient descent with a batch of one and no reshuffling, but the OCO lens gives it a guarantee that the batch view does not. For convex losses with bounded gradients ($\|\nabla \ell_t\| \le G$) and a bounded domain ($\|\boldsymbol{\theta}^\star\| \le D$), the classic Zinkevich (2003) result is that a decaying step size $\eta_t = D/(G\sqrt{t})$ gives

so the average regret falls as $O(1/\sqrt{T})$ and vanishes. For strongly convex losses (online ridge below is one) a more aggressive $\eta_t = 1/(\lambda t)$ schedule sharpens this to $O(\log T)$ regret, even faster. The headline is that one cheap gradient step per example, with a properly decaying learning rate, provably tracks the best fixed model.

The learning rate $\eta_t$ is the single most consequential knob, and it is where the streaming setting forces a tension absent from batch learning. A large $\eta$ makes the model adaptive: it swings hard toward each new example, so it can chase a drifting target quickly, but it is jittery and high-variance, overreacting to noise. A small $\eta$ makes the model stable: it averages over many examples and is robust to noise, but it is sluggish to react when the stream genuinely changes. The decaying schedule $\eta_t \propto 1/\sqrt{t}$ that optimizes stationary regret deliberately freezes the model as $t$ grows, which is exactly wrong if the world is non-stationary, because a frozen model cannot follow drift. This is the adaptivity-stability tension in one parameter, and resolving it (often by holding $\eta$ at a constant floor, or resetting it on detected drift) is the bridge to Section 20.2 and the adaptive systems of Section 20.5.

3. Classic Online Algorithms for Streams Intermediate

The OCO lens explains why one-step updates work; the algorithms below are the specific updates practitioners reach for, each a different answer to "what one cheap correction should I make per example?" They span regression, classification, and tree models, and all share the predict-then-update shape.

Online ridge and recursive least squares (RLS). For streaming linear regression, online gradient descent on the squared loss with an $\ell_2$ penalty gives online ridge: $\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta_t[(\langle\boldsymbol{\theta}_t, \mathbf{x}_t\rangle - y_t)\mathbf{x}_t + \lambda\boldsymbol{\theta}_t]$, a first-order method. But linear least squares admits an exact online solution that needs no learning rate at all: recursive least squares. RLS maintains the inverse covariance $\mathbf{P}_t = (\sum_{s\le t}\mathbf{x}_s\mathbf{x}_s^\top + \lambda \mathbf{I})^{-1}$ and updates it in closed form per example, giving after every step the exact ridge solution on all data seen so far, as if you had refit on the whole history. The RLS update is, term for term, the Kalman filter measurement update of Chapter 7 applied to a static state ($\boldsymbol{\theta}$ is the "state", each $(\mathbf{x}_t, y_t)$ is a scalar "measurement", $\mathbf{P}_t$ is the state covariance). The temporal thread closes here: the filter that tracked a hidden state in Part II is, read sideways, the optimal online regressor.

The perceptron. The oldest online classifier (Rosenblatt, 1958): predict $\hat{y}_t = \mathrm{sign}(\langle\boldsymbol{\theta}_t, \mathbf{x}_t\rangle)$, and on a mistake nudge the weights toward the correct class, $\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t + y_t\mathbf{x}_t$ (with $y_t \in \{-1, +1\}$); on a correct prediction, do nothing. It is OGD on the hinge-like perceptron loss, and for linearly separable streams it makes a bounded number of mistakes.

Passive-aggressive (PA). A sharper mistake-driven update (Crammer et al., 2006): on each example solve a tiny constrained problem, stay as close as possible to the current weights (passive) while changing just enough to classify the new example correctly with margin (aggressive). The closed-form update is $\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t + \tau_t y_t \mathbf{x}_t$ with an analytically computed step $\tau_t$ that is zero when the margin is already satisfied and grows with the violation, a self-tuning learning rate that needs no manual schedule.

Hoeffding trees (very fast decision trees, VFDT). Decision trees seem to need the whole dataset to choose a split, which streaming forbids. The Hoeffding tree (Domingos and Hulten, 2000) breaks the impasse with a statistical argument: accumulate per-feature split statistics incrementally, and use the Hoeffding bound to decide when enough examples have arrived to be confident, with high probability, that the currently-best split would also be best given infinite data. The bound states that after $n$ examples the true mean of a bounded quantity is within $\epsilon = \sqrt{R^2\ln(1/\delta)/(2n)}$ of the observed mean with probability $1-\delta$; once the gap between the best and second-best split's information gain exceeds $\epsilon$, the tree splits, confident it would make the same choice with the full stream. This lets a tree grow from a stream in one pass with bounded memory.

4. Memory and Time Budgets: Sketching and Reservoir Sampling Advanced

The defining discipline of streaming is the budget: per example you may spend only $O(1)$ or at most $O(\log T)$ time and you may keep only a fixed amount of state, no matter how long the stream runs. A method whose memory grows with the number of examples seen is, by definition, not a streaming method, it is a batch method waiting to crash. Online ridge, RLS, the perceptron, and PA all satisfy the budget natively: their state is the parameter vector (and for RLS the $d \times d$ covariance), fixed-size regardless of $T$. Much of the art of streaming is forcing other computations into the same fixed-state mold.

When a single number must be tracked over the stream (a count, a sum, a quantile, a set of distinct items) and the exact answer would need unbounded memory, the answer is a sketch: a small, fixed-size, approximate summary updated in $O(1)$ per example. The Count-Min sketch approximates item frequencies in sublinear space, HyperLogLog estimates the number of distinct items in kilobytes regardless of stream length, and exponentially-weighted moving moments track a drifting mean and variance with two scalars. Sketches trade a controlled, quantified error for a hard memory bound, which is the streaming bargain in miniature.

Sometimes, though, you genuinely need a sample of past examples, to retrain a batch model periodically, to compute a drift statistic, or to keep a replay buffer for the continual learning of Section 20.4. Keeping a uniform random sample of fixed size $k$ from an unbounded stream, without knowing the stream's length in advance, is the job of reservoir sampling (Vitter's algorithm R). Hold the first $k$ examples; for the $t$-th example with $t > k$, keep it with probability $k/t$, and if kept, evict a uniformly random current member. A one-line induction shows that after any number of examples, every example seen so far is in the reservoir with equal probability $k/t$, so the reservoir is a uniform sample of the entire history using only $O(k)$ memory and one cheap coin flip per example. It is the canonical way to hold a representative slice of a stream you cannot store.

The time budget matters as much as the memory budget, and it is why RLS deserves a caution. Its per-example update is exact but costs $O(d^2)$ time and memory in the feature dimension $d$, because it maintains the full $d \times d$ inverse covariance. For a handful of features that is trivial; for high-dimensional streams it is prohibitive, and online ridge (OGD), at $O(d)$ per example, is the right tool despite its inexactness. The recurring streaming decision is precisely this trade: exactness and second-order convergence ($O(d^2)$, RLS) versus a fixed cheap budget and graceful scaling ($O(d)$, OGD), the same exact-versus-cheap tension we will see between checkpointing and truncation throughout the book.

5. Worked Example: Online SGD and RLS From Scratch, Then river Advanced

We now make the chapter concrete on the Sensor and IoT thread: predict a machine's next vibration reading from a few telemetry features, on a stream we are only allowed to see once. We build two regressors from scratch, online SGD (first-order, $O(d)$ per step) and recursive least squares (exact, $O(d^2)$ per step), run both under the strict predict-then-update protocol, and track the prequential error live. Code 20.1.1 generates the stream and implements online SGD by hand.

import numpy as np

rng = np.random.default_rng(0)
d = 4                                      # number of telemetry features
T = 4000                                   # length of the (pretend unbounded) stream
theta_true = rng.normal(0, 1, size=d)      # the linear relation we must recover online

def stream():
    """Yield one (x_t, y_t) at a time; the learner sees each row exactly once."""
    for t in range(T):
        x = rng.normal(0, 1, size=d)
        y = x @ theta_true + rng.normal(0, 0.3)   # noisy linear target
        yield x, y

class OnlineSGD:
    """First-order online ridge: one gradient step per example, O(d) per step."""
    def __init__(self, d, lam=1e-3):
        self.theta = np.zeros(d)
        self.lam = lam
        self.t = 0
    def predict(self, x):
        return self.theta @ x                       # commit BEFORE seeing y
    def update(self, x, y):
        self.t += 1
        eta = 0.5 / np.sqrt(self.t)                  # decaying rate: O(1/sqrt(t)) regret
        err = self.theta @ x - y                     # gradient of 0.5(theta.x - y)^2
        grad = err * x + self.lam * self.theta       # add the L2 (ridge) penalty term
        self.theta -= eta * grad                     # the whole online update, one line

sgd = OnlineSGD(d)
preq_sgd, run_loss = [], 0.0
for t, (x, y) in enumerate(stream(), 1):
    yhat = sgd.predict(x)                            # 1. predict (out-of-sample)
    run_loss += (yhat - y) ** 2                      # 2. score it prequentially
    sgd.update(x, y)                                 # 3. then learn, then discard x,y
    if t % 800 == 0:
        preq_sgd.append((t, run_loss / t))
print("online SGD prequential MSE:", [f"{t}:{m:.4f}" for t, m in preq_sgd])

online SGD prequential MSE: ['800:0.5912', '1600:0.3744', '2400:0.2952', '3200:0.2533', '3600:...']

Online SGD converges but slowly, dragging a hand-tuned decaying learning rate behind it. Recursive least squares needs no learning rate at all: it returns the exact ridge solution on all data seen so far after every single example, via the Kalman-form covariance update of subsection three. Code 20.1.2 implements RLS from scratch and runs it on the identical stream.

class RLS:
    """Recursive least squares: exact online ridge, the Kalman measurement update."""
    def __init__(self, d, lam=1e-2):
        self.theta = np.zeros(d)
        self.P = np.eye(d) / lam        # inverse covariance, init (lam I)^{-1}
    def predict(self, x):
        return self.theta @ x
    def update(self, x, y):
        Px = self.P @ x                              # P_t x_t  (the unnormalized gain)
        denom = 1.0 + x @ Px                         # innovation variance (scalar)
        K = Px / denom                               # Kalman gain k_t
        self.theta = self.theta + K * (y - self.theta @ x)   # state (= weight) update
        self.P = self.P - np.outer(K, Px)            # rank-one covariance downdate

rls = RLS(d)
preq_rls, run_loss = [], 0.0
np_state = np.random.default_rng(0)                  # reset stream to the SAME sequence
def stream2():
    for t in range(T):
        x = np_state.normal(0, 1, size=d)
        y = x @ theta_true + np_state.normal(0, 0.3)
        yield x, y
for t, (x, y) in enumerate(stream2(), 1):
    run_loss += (rls.predict(x) - y) ** 2            # predict-then-update, same protocol
    rls.update(x, y)
    if t % 800 == 0:
        preq_rls.append((t, run_loss / t))
print("RLS prequential MSE:", [f"{t}:{m:.4f}" for t, m in preq_rls])

RLS prequential MSE: ['800:0.1287', '1600:0.1058', '2400:0.0987', '3200:0.0951', '...']

Read together, the two from-scratch learners make the central comparison of the section concrete: online SGD is cheap ($O(d)$) but needs a hand-tuned decaying rate and converges slowly; RLS is learning-rate-free and converges fast but pays $O(d^2)$. Both run forever on fixed state and are evaluated by the same prequential accumulator. Now the library pair. A production streaming framework, river, gives the identical predict-then-update learner and a live prequential metric in a few lines, with the model internals (state, scaling, the update) all handled for you. Code 20.1.3 reproduces the online regressor.

from river import linear_model, metrics, preprocessing

# A full streaming pipeline: standardize features online, then linear regression.
model = preprocessing.StandardScaler() | linear_model.LinearRegression()
metric = metrics.MSE()                              # the prequential metric, updated live

for xi, yi in stream():                             # the SAME structured stream as Code 20.1.1
    x = {f"f{i}": v for i, v in enumerate(xi)}       # river wants a feature dict
    y_pred = model.predict_one(x)                   # 1. predict (out-of-sample)
    metric.update(yi, y_pred)                        # 2. score prequentially
    model.learn_one(x, yi)                           # 3. then learn from the row
print("river prequential MSE:", metric.get())

river prequential MSE: 0.0904

Exercises

1. (Conceptual) A colleague proposes to evaluate a streaming model by holding out a fixed 20% of the stream as a test set, exactly as in batch learning. Explain why prequential evaluation is preferable for an unbounded, possibly non-stationary stream, and state precisely why the running prequential average $\bar{L}_t = \frac{1}{t}\sum_{s\le t}\ell(\hat{y}_s, y_s)$ is an honest (leakage-free) estimate of predictive performance. Connect your answer to the time-ordered backtesting principle of Section 2.6.
2. (Implementation) Starting from Code 20.1.1, add a constant-learning-rate variant (fix $\eta = 0.05$ instead of $0.5/\sqrt{t}$) and run both on a stream whose true coefficients $\boldsymbol{\theta}_{\text{true}}$ jump to a new random value at $t = 2000$ (concept drift). Plot the two prequential errors. Show that the decaying-rate model freezes and fails to recover after the jump while the constant-rate model adapts, and explain the result in terms of the adaptivity-versus-stability tension of subsection two.
3. (Open-ended) Recursive least squares as written gives equal weight to all past examples, so it cannot track a drifting target. Research and implement forgetting-factor RLS, which down-weights old examples by a factor $\gamma < 1$ per step (multiply $\mathbf{P}$ by $1/\gamma$ each update). Investigate how $\gamma$ controls an effective memory window of roughly $1/(1-\gamma)$ examples, relate this to the constant-learning-rate choice from the previous exercise, and discuss how you would set $\gamma$ adaptively using a drift signal, previewing Section 20.2.