Online Learning is the machine learning paradigm where the model is updated incrementally as each new data point (or small batch) arrives, rather than training on the entire dataset at once — essential for streaming data scenarios (real-time fraud detection, recommendation systems, sensor monitoring) where data arrives continuously, distributions shift over time (concept drift), and the model must adapt without storing or reprocessing the full history, making online learning the operational reality for most production ML systems.

Online vs. Batch Learning

• Batch: Collect all data → train model → deploy. Retrain periodically (daily/weekly). Stale between retrains. Requires storing all data.
• Online: Process one example at a time → update model → discard example. Always up-to-date. Bounded memory. Natural for streaming data.

Online Optimization Algorithms

Online Gradient Descent (OGD): For each example (x_t, y_t): compute loss L(w, x_t, y_t), update w ← w - η × ∇L. The regret (cumulative loss vs. best fixed model in hindsight) of OGD is O(√T) for convex losses — sublinear, meaning per-step regret → 0 as T → ∞.

Follow-the-Regularized-Leader (FTRL): w_t = argmin Σᵢ₌₁^t ∇L_i^T w + R(w). With L1 regularization R(w) = λ||w||₁, FTRL produces sparse models — exactly zero weights for irrelevant features. Used at Google scale for online ad click prediction with billions of features.

Adaptive Learning Rates: AdaGrad, Adam, etc., adapt per-parameter learning rates based on gradient history. Early large gradients for a feature → lower learning rate (avoid overshooting). Rare features → higher learning rate (learn quickly from sparse signals). Critical for online learning where feature frequencies vary enormously.

Concept Drift

The fundamental challenge of online learning — the data distribution changes over time:

• Sudden Drift: Distribution changes abruptly (new product launch changes user behavior).
• Gradual Drift: Distribution shifts slowly (seasonal trends, evolving fraud tactics).
• Recurring Drift: Distribution cycles (holiday shopping patterns repeat annually).

Drift Detection Methods:

• DDM (Drift Detection Method): Monitor the model's error rate. If error rate increases beyond a threshold (mean + 3σ), declare drift and retrain/reset.
• ADWIN (Adaptive Windowing): Maintains a variable-length window of recent observations. Automatically shrinks the window when drift is detected (old data is discarded) and grows it during stable periods.
• Page-Hinkley Test: Monitors cumulative deviation of a metric from its running mean. Signals drift when cumulative deviation exceeds a threshold.

Production Online Learning

• Feature Hashing: Hash high-dimensional features (URLs, user IDs, n-grams) into a fixed-size vector. Bounded memory regardless of feature cardinality. Small hash collisions reduce accuracy slightly.
• Reservoir Sampling: Maintain a representative sample of past data for evaluation, calibration, and replay during drift recovery.
• A/B Testing with Online Models: Deploy the new online model alongside the old batch model. Monitor live metrics. Automated rollback if performance degrades.

Online Learning is the deployment paradigm that keeps ML models synchronized with reality — the continuous adaptation mechanism that handles the non-stationarity, scale, and freshness requirements that batch retraining cannot satisfy for real-time production systems.