Reservoir Sampling

The core property of reservoir sampling is its single-pass operation. The algorithm processes each element of the stream exactly once, without the need to store the entire stream or revisit previous elements. This makes it memory-efficient and suitable for online learning and streaming data scenarios where data arrives continuously and cannot be stored in full.

• Mechanism: It maintains a 'reservoir' of size k. For the first k elements, it fills the reservoir. For each subsequent element i (where i > k), it includes the element with probability k/i, replacing a randomly chosen existing reservoir element.

The defining statistical guarantee: after processing n elements, every subset of size k from the n elements has an equal probability of being the final reservoir. Each individual element has a probability of exactly k/n of being in the sample. This property holds regardless of the order of the stream.

• Proof Sketch: For element i, the probability it enters the reservoir is k/i. The probability it survives all subsequent replacement attempts (for elements j from i+1 to n) is Π (1 - k/(j * k)) = i/n. Multiplying these gives k/n.
• Implication for Continual Learning: This ensures the replay buffer is an unbiased statistical sample of the entire data stream, preventing distributional skew in rehearsal.

Algorithm R is the foundational, simple reservoir sampling algorithm. It is straightforward to implement and provides the uniform sampling guarantee.

Pseudocode:

codeCopy
Initialize reservoir R with first k elements.
for i = k+1 to n:
    j = random integer in [1, i]
    if j <= k:
        R[j] = element i

• Complexity: O(n) time, O(k) space.
• Drawback: It requires generating a random number for every element in the stream after the first k, which can be a computational bottleneck for extremely high-speed streams.

Algorithm L is an optimized version that reduces the number of random number generations. Instead of checking every element, it uses skip intervals calculated from a geometric distribution.

• Mechanism: It calculates how many elements to skip before the next candidate for replacement, based on the current reservoir size and a random variable. This dramatically reduces the number of iterations in the main loop.
• Advantage: While maintaining the uniform sampling property, it runs in O(k(1 + log(n/k))) expected time, which is significantly faster than Algorithm R for large n.
• Use Case: Preferred in high-throughput streaming applications or when the sampling operation itself is a performance-critical path.

In Continual Learning, reservoir sampling is the standard algorithm for buffer management in rehearsal-based methods like Experience Replay.

• Process: As new task data streams in, the algorithm decides which new samples to insert into the fixed-size replay buffer and which old ones to evict.
• Why it works: It ensures the buffer always contains a uniform random sample of all data seen so far. This provides a statistically sound basis for interleaving old and new data during training, which is crucial for mitigating catastrophic forgetting.
• Contrast with Heuristics: Unlike FIFO (First-In-First-Out) or other deterministic strategies, reservoir sampling prevents bias towards recent data, promoting better long-term knowledge retention.

A powerful generalization where each stream element i has an associated weight w_i. The algorithm selects a sample where the probability of an element being chosen is proportional to its weight.

• Use Case in ML: Extremely relevant for importance sampling and non-uniform buffer management. For example, samples with higher loss or gradient magnitude can be given higher weight to be retained in the buffer, as they may be more informative for rehearsal.
• Algorithm: Variants like Algorithm A-Chao or Algorithm A-Res extend the core idea to handle weights, maintaining O(k) memory but with more complex per-element operations.
• Connection: This bridges simple random sampling to more sophisticated, curriculum-based or hard example mining strategies within continual learning frameworks.

A foundational continual learning technique that mitigates catastrophic forgetting by storing a subset of past training data (or their feature representations) and interleaving them with new data during training. This rehearsal of old tasks helps maintain performance. Reservoir Sampling is the standard probabilistic algorithm for managing the fixed-size memory buffer in online scenarios where the data stream is potentially infinite.

The fixed-capacity memory storage used in rehearsal-based continual learning. Its management is critical for performance. Key strategies include:

• Reservoir Sampling: Maintains a uniform random sample.
• Core-set Selection: Chooses representative prototypes to maximize coverage.
• Ring Buffer: FIFO replacement, simple but non-random.
• Gradient-based Selection: Prioritizes samples that maximize loss if forgotten. Effective Buffer Management directly influences the stability-plasticity trade-off.

The strictest and most realistic variant of continual learning, where the model receives a single, non-repeating pass through a stream of data, often one sample or a small mini-batch at a time. This scenario prohibits multiple epochs over past data, making efficient buffer algorithms like Reservoir Sampling essential for feasible rehearsal. It closely mimics real-world edge deployment where data arrives sequentially and cannot be stored indefinitely.

A rehearsal-based algorithm that stores past data in an episodic memory. Its core innovation is to constrain the gradient update for a new task so that it does not increase the loss on the memory examples. This is formulated as a quadratic programming problem. While GEM defines how to use the buffer, Reservoir Sampling or other strategies define what goes into the buffer, making them complementary components of the system.

The fundamental trade-off in all continual learning systems. Stability refers to a model's ability to retain knowledge from previous tasks. Plasticity is its capacity to learn new information efficiently. Rehearsal-based methods using a buffer directly address this: the buffer size and management policy (e.g., Reservoir Sampling) are hyperparameters that control the balance. A larger buffer favors stability but may reduce plasticity for new patterns.

The practical domain of deploying continual learning on resource-constrained edge devices (e.g., smartphones, IoT sensors). Key constraints are memory, compute, and energy. Reservoir Sampling is highly suitable for Edge-CL because it is computationally lightweight (O(1) per sample decision), requires minimal memory overhead (only the buffer itself), and operates in a single pass, making it ideal for on-device, online data streams.