Reservoir Sampling

The defining characteristic of reservoir sampling is its single-pass nature. It processes each item in the stream exactly once, requiring only O(k) memory to hold the reservoir of size k. This makes it impossible to store the entire stream, which is essential for applications like:

• Maintaining a replay buffer for continual learning.
• Sampling from live network traffic or sensor feeds.
• Log sampling in high-throughput distributed systems.

The algorithm's core guarantee is that every item seen in the stream has an identical probability of being in the final sample. For a stream of length n and reservoir size k, the probability for any item is exactly k/n. This property holds even though n is unknown when processing begins. It ensures a statistically unbiased simple random sample, which is critical for:

• Creating representative training datasets from non-stationary streams.
• Fairly selecting experiences for reinforcement learning replay.
• Providing valid inputs for downstream statistical tests.

Algorithm R is the foundational, straightforward implementation.

• Initialization: Fill the reservoir with the first k items from the stream.
• Inductive Step: For each incoming item i (where i > k), generate a random integer j uniformly from 1 to i. If j ≤ k, replace the j-th item in the reservoir with the new item.
• Complexity: The time complexity is O(n), and it requires k random numbers to be generated. While simple, it can be inefficient for very large n due to the random number generation for every item.

Algorithm L introduces a key optimization to reduce the number of random number generations. Instead of checking every item, it uses skip intervals.

• It calculates how many items to skip before the next replacement, based on a geometric distribution.
• This reduces the number of random variate generations from O(n) to O(k log(n/k)) on average.
• It is the algorithm of choice for extremely long streams (e.g., sampling from petabytes of log data) where the cost of random number generation becomes a bottleneck.

A crucial extension where each item i has an associated weight w_i. The goal is to sample such that the probability of selecting an item is proportional to its weight. Common algorithms include:

• Algorithm A-Res: Uses a key u_i^(1/w_i) for each item, where u_i is a uniform random number. It maintains the k items with the largest keys.
• Algorithm A-ExpJ: An optimized version that reduces computational cost.
• Use Case: Essential for importance sampling in online learning, where recent or high-loss data points should be sampled with higher probability for replay.

Reservoir sampling can be scaled to parallel and distributed streams.

• Parallel/Distributed Sampling: Each node (or thread) maintains its own reservoir of size k from its local stream. The final reservoir is created by performing a second round of reservoir sampling on the merged outputs from all nodes.
• Use Case: Sampling from sharded databases, distributed log aggregators (like Apache Kafka topics), or federated learning nodes where data cannot be centralized. This preserves the equal-probability guarantee across the entire global dataset.

Online learning is the core machine learning paradigm where a model updates its parameters sequentially, processing one data point or a small mini-batch at a time without revisiting past data. This makes it essential for:

• Streaming data applications like financial tickers or IoT sensor feeds.
• Real-time adaptation where model predictions must reflect the most recent information.
• Large-scale datasets where storing the entire history is computationally infeasible. The primary challenge is balancing immediate learning with long-term stability, often analyzed through the framework of regret minimization.

An experience replay buffer is a fixed-size memory store used in reinforcement learning and continual learning to cache past experiences (e.g., state-action-reward transitions). Its core functions are:

• Breaking temporal correlations by randomly sampling past data in mini-batches.
• Mitigating catastrophic forgetting by allowing the model to revisit and rehearse old tasks.
• Improving sample efficiency by reusing valuable experiences. Reservoir sampling is the canonical algorithm for maintaining a uniform random sample within this buffer when the stream length is unknown, ensuring every past experience has an equal probability of being retained.

Concept drift detection refers to algorithms that automatically identify when the underlying statistical properties of a target variable change over time relative to the input data. In streaming contexts, this is critical because:

• A model's performance will degrade silently if the data distribution shifts.
• Detection triggers model adaptation, retraining, or alerting. Common algorithms include ADWIN (Adaptive Windowing) and CUSUM. These methods often work in tandem with sampling techniques like reservoir sampling, which provides a representative recent history of data to analyze for statistical change.

Stochastic Gradient Descent is the fundamental optimization algorithm for online learning. It updates model parameters using the gradient computed from a single data point or a small, randomly sampled mini-batch.

• Core Mechanism: θ = θ - η * ∇J(θ; x_i, y_i), where η is the learning rate.
• Connection to Streaming: SGD processes data in the order it arrives, making it inherently online.
• Asynchronous Variants: Asynchronous SGD allows parallel workers to update shared parameters without tight synchronization, crucial for high-throughput streaming systems. While reservoir sampling manages which data is stored, SGD defines how the model learns from each new piece of data.

Regret minimization is the primary theoretical framework for analyzing and designing online learning algorithms. Regret is defined as the cumulative difference between the losses incurred by the online algorithm and the losses of the best fixed decision in hindsight.

• Goal: Design algorithms with sublinear regret, meaning the average regret per round goes to zero.
• Application: This framework provides performance guarantees for algorithms dealing with adversarial data streams, where patterns can change arbitrarily. While practical algorithms like reservoir sampling are heuristic, their effectiveness in maintaining a representative buffer supports the overall goal of minimizing regret in continual learning systems.

A multi-armed bandit is a sequential decision-making framework that formalizes the explore-exploit tradeoff. An agent chooses from a set of actions (arms) with unknown reward distributions to maximize cumulative reward over time.

• Exploration: Gathering information about unknown arms.
• Exploitation: Choosing the arm with the highest known reward. Key solving algorithms include Thompson Sampling (Bayesian) and Upper Confidence Bound (UCB). Bandits represent a specialized form of online learning where feedback is limited to the chosen action. Reservoir sampling can be used in contextual bandits to maintain a sample of past contexts for more efficient off-policy evaluation.