Online Learning Algorithms
Batch learning's blind spot
Most ML pipelines assume you have a fixed dataset, train once, and deploy. Online learning flips this: the model sees examples one at a time (or in small mini-batches) in a continuous stream, and updates its parameters after each one — before the next example even arrives. This matters whenever data is too large to hold in memory, arrives continuously (clickstreams, sensor feeds, ad impressions), or when the underlying distribution drifts over time and a model trained once goes stale.
Online gradient descent and regret
The canonical online learning algorithm is Online Gradient Descent (OGD): for each incoming example $x_t$, predict, observe the true label, compute the loss $\ell_t(w_t)$, and update $w_{t+1} = w_t - \eta_t \nabla \ell_t(w_t)$. Theoretical guarantees are framed in terms of regret — the cumulative loss of the online learner compared to the best fixed model in hindsight: $R_T = \sum_{t=1}^{T} \ell_t(w_t) - \min_{w} \sum_{t=1}^{T} \ell_t(w)$. For convex losses with an appropriately decaying learning rate ($\eta_t \propto 1/\sqrt{t}$), OGD achieves sublinear regret $O(\sqrt{T})$, meaning average per-step regret vanishes as $T \to \infty$ — the online learner asymptotically matches the best fixed hindsight model.
Follow-the-Regularized-Leader and adaptive variants
FTRL (Follow-the-Regularized-Leader), popularized by Google's ad-click prediction systems, generalizes OGD by choosing, at each step, the weight vector that minimizes cumulative loss over all past examples plus a regularization term. FTRL-Proximal with L1 regularization produces sparse models online — critical when feature spaces have millions of dimensions (hashed categorical interactions) but only a handful matter per model. AdaGrad and its online cousins adapt the per-coordinate learning rate based on the historical sum of squared gradients, giving rare features larger effective updates than frequent ones.
| Algorithm | Update rule focus | Best for |
|---|---|---|
| OGD | Fixed/decaying learning rate gradient step | Simple streaming regression/classification |
| FTRL-Proximal | Cumulative loss + L1/L2 regularization | Sparse, high-dimensional online models (ad CTR) |
| AdaGrad (online) | Per-coordinate adaptive learning rate | Sparse features with very different frequencies |
| Passive-Aggressive | Update only if margin violated, bounded step | Streaming classification needing fast convergence |
import numpy as np
class OnlineLogisticRegression:
def __init__(self, n_features, lr=0.1, l2=1e-4):
self.w = np.zeros(n_features)
self.b = 0.0
self.lr = lr
self.l2 = l2
self.t = 0
def predict_proba(self, x):
z = np.dot(self.w, x) + self.b
return 1 / (1 + np.exp(-z))
def partial_fit(self, x, y):
self.t += 1
eta = self.lr / np.sqrt(self.t) # decaying step size for sublinear regret
p = self.predict_proba(x)
grad_w = (p - y) * x + self.l2 * self.w
grad_b = (p - y)
self.w -= eta * grad_w
self.b -= eta * grad_b
return -(y * np.log(p + 1e-12) + (1 - y) * np.log(1 - p + 1e-12))
# Stream simulation: one example at a time, model updates immediately
model = OnlineLogisticRegression(n_features=10)
for x, y in stream_of_examples(): # generator yielding (feature_vector, label)
loss = model.partial_fit(x, y)Concept drift: the real reason online learning matters
The deeper motivation for online learning isn't just memory efficiency — it's concept drift, where $P(y \mid x)$ changes over time (user preferences shift, fraud patterns evolve, seasonal effects kick in). A batch model trained last month silently degrades. Online learners that keep updating on fresh data adapt continuously. Detecting drift explicitly (via tools like the ADWIN algorithm, which maintains an adaptive window and drops stale data when a statistical test detects a distribution change, or the DDM/EDDM drift detectors that monitor error-rate trends) lets you decide when to reset the learning rate, widen the window, or trigger a full retrain rather than relying on gradual adaptation alone.
Online learning is not free of catastrophic forgetting
Online learning as the backbone of production ML
What's Next?
Online learning naturally raises the question of what happens when new tasks — not just new data from the same task — arrive sequentially, and how a model can learn them without forgetting earlier ones entirely.
I build these systems professionally.
Whether it's a RAG pipeline, analytics migration, or AI workflow — let's talk.