Random sampling with a reservoir

By Jeffrey Scott Vitter. 1985

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

A Comprehensive Survey of Continual Learning: Theory, Method and Application (2023, background): “For example, Reservoir Sampling [66], [360], [419] randomly stores a fixed amount”
Practical Black-Box Attacks against Machine Learning (2016, methodology): “l value for the period ˝. We also experimented with a decreasing grid step amplitude , but did not ﬁnd that it yielded substantial improvements. Reducing Oracle Querying: We apply reservoir sampling [16] as a mean to reduce the number of queries made to the oracle. This is useful when learning subst”
Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples (2016, methodology): “We also introduce the use of reservoir sampling [23] as a mean to reduce the number of queries made to the oracle.”
Memory Efficient Experience Replay for Streaming Learning (2018, methodology): “pling [68] and 2) a first-in, first-out queue.”
The Ideal Continual Learner: An Agent That Never Forgets (2023, methodology): “Based on prior works (Vitter, 1985; Lopez-Paz & Ranzato, 2017; Rebuffi et al., 2017; Riemer et al., 2019), Chaudhry et al.”
Task-Aware Information Routing from Common Representation Space in Lifelong Learning (2023, methodology): “To preserve knowledge of previous tasks, we seek to approximate previous data distributions Dt∈{t:1≤i Tc} through a memory buffer Dm with reservoir sampling (Vitter, 1985).”
Task-Free Continual Learning via Online Discrepancy Distance Learning (2022, neutral): “We compare with several baselines including: finetune that directly trains a classifier on the data stream, GSS [1], Dynamic-OCM [54], MIR [2], Gradient Episodic Memory (GEM) [27], Incremental Classifier and Representation Learning (iCARL) [39], Reservoir [45], CURL, CNDPM, CoPE, ER + GMED and ERa +”
On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning (2022, neutral): “If not specified, all methods use reservoir sampling [78] to update the memory buffer.”
Repeated Augmented Rehearsal: A Simple but Strong Baseline for Online Continual Learning (2022, methodology): “A simple but strong baseline approach to sampling in ER is reservoir sampling Vitter [1985].”
Meta-Learning with Less Forgetting on Large-Scale Non-Stationary Task Distributions (2022, positive): “The memory is updated by online reservoir sampling (RS) [58], at each time step t , RS operates on task unit level.”
Online Continual Learning with Contrastive Vision Transformer (2022, methodology): “After updating the whole CVT model on a mini-batch B, the memory buffer M will be updated with B by Reservoir sampling [77,9].”
Transfer without Forgetting (2022, neutral): “We thus equip the continual learner with a small memory buffer B (populated with examples from the input stream via reservoir sampling [65]) and adopt the simple labels and logits replay strategy proposed in [8]:”
Information-theoretic Online Memory Selection for Continual Learning (2022, neutral): “A selection method compatible with GCL is reservoir sampling (RS) (Vitter, 1985).”
Memory Efficient Continual Learning with Transformers (2022, methodology): “While several different data sources can be used to populate the buffer, such as using auxiliary external data [69] or generating synthetic data [9], in this work we populate the buffer using covariates from previous tasks selected with Reservoir Sampling [58].”
Learning Fast, Learning Slow: A General Continual Learning Method based on Complementary Learning System (2022, methodology): “Finally, Reservoir sampling (Vitter, 1985) is employed to maintain a small episodic memory M .”
GCR: Gradient Coreset based Replay Buffer Selection for Continual Learning (2021, neutral): “As shown in the pseudocode, we employ reservoir sampling [46] for selecting the candidate pool.”
Online Continual Learning on Class Incremental Blurry Task Configuration with Anytime Inference (2021, methodology): “For the memory management policy, we use reservoir sampling (Vitter, 1985) and for memory usage, we we use experience replay (ER).”
Continual Learning on Noisy Data Streams via Self-Purified Replay (2021, methodology): “We include all of GDumb [68] combinations and the single best performing combination of PRS [37] and CRS [86] for each dataset.”
Recent Advances of Continual Learning in Computer Vision: An Overview (2021, positive): “However, reservoir sampling [87] works well if each of the tasks has a similar number of instances, and it could lose information from the tasks that have significantly fewer instances than the others.”