Super-Sampling with a Reservoir

Brooks Paige, Dino Sejdinovic, Frank Wood
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:801-810, 2016.

Abstract

We introduce an alternative to reservoir sampling, a classic and popular algorithm for drawing a fixed-size subsample from streaming data in a single pass. Rather than draw a random sample, our approach performs an online optimization which aims to select the subset that provides the best overall approximation to the full data set, as judged using a kernel two-sample test. This produces subsets which minimize the worst-case relative error when computing expectations of functions in a specified function class, using just the samples from the subset. Kernel functions are approximated using random Fourier features, and the subset of samples itself is stored in a random projection tree. The resulting algorithm runs in a single pass through the whole data set, and has a per-iteration computational complexity logarithmic in the size of the subset. These "super-samples" subsampled from the full data provide a concise summary, as demonstrated empirically on mixture models and the MNIST dataset.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-paige16a, title = {Super-Sampling with a Reservoir}, author = {Paige, Brooks and Sejdinovic, Dino and Wood, Frank}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {801--810}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/paige16a/paige16a.pdf}, url = {https://proceedings.mlr.press/r14/paige16a.html}, abstract = {We introduce an alternative to reservoir sampling, a classic and popular algorithm for drawing a fixed-size subsample from streaming data in a single pass. Rather than draw a random sample, our approach performs an online optimization which aims to select the subset that provides the best overall approximation to the full data set, as judged using a kernel two-sample test. This produces subsets which minimize the worst-case relative error when computing expectations of functions in a specified function class, using just the samples from the subset. Kernel functions are approximated using random Fourier features, and the subset of samples itself is stored in a random projection tree. The resulting algorithm runs in a single pass through the whole data set, and has a per-iteration computational complexity logarithmic in the size of the subset. These "super-samples" subsampled from the full data provide a concise summary, as demonstrated empirically on mixture models and the MNIST dataset.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Super-Sampling with a Reservoir %A Brooks Paige %A Dino Sejdinovic %A Frank Wood %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-paige16a %I PMLR %P 801--810 %U https://proceedings.mlr.press/r14/paige16a.html %V R14 %X We introduce an alternative to reservoir sampling, a classic and popular algorithm for drawing a fixed-size subsample from streaming data in a single pass. Rather than draw a random sample, our approach performs an online optimization which aims to select the subset that provides the best overall approximation to the full data set, as judged using a kernel two-sample test. This produces subsets which minimize the worst-case relative error when computing expectations of functions in a specified function class, using just the samples from the subset. Kernel functions are approximated using random Fourier features, and the subset of samples itself is stored in a random projection tree. The resulting algorithm runs in a single pass through the whole data set, and has a per-iteration computational complexity logarithmic in the size of the subset. These "super-samples" subsampled from the full data provide a concise summary, as demonstrated empirically on mixture models and the MNIST dataset. %Z Reissued by PMLR on 04 October 2026.
APA
Paige, B., Sejdinovic, D. & Wood, F.. (2016). Super-Sampling with a Reservoir. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:801-810 Available from https://proceedings.mlr.press/r14/paige16a.html. Reissued by PMLR on 04 October 2026.

Related Material