# Non-Adaptive Adaptive Sampling on Turnstile Streams

arXiv: https://arxiv.org/abs/2004.10969 · HTML: https://mlsanity.com/paper/2004.10969/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2020.

## Built on by (most cited first, 9 of 9)

- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [Lazy and Fast Greedy MAP Inference for Determinantal Point Process](https://mlsanity.com/paper/2206.05947/) (2022)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Single Pass Entrywise-Transformed Low Rank Approximation](https://mlsanity.com/paper/2107.07889/) (2021)
- [Adaptive Sketches for Robust Regression with Importance Sampling](https://mlsanity.com/paper/2207.07822/) (2022)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [One-pass additive-error subset selection for ℓp subspace approximation](https://mlsanity.com/paper/2204.12073/) (2022)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)

## Abstract (arXiv)

Adaptive sampling is a useful algorithmic tool for data summarization problems in the classical centralized setting, where the entire dataset is available to the single processor performing the computation. Adaptive sampling repeatedly selects rows of an underlying matrix A∈ℝn× d, where ngg d, with probabilities proportional to their distances to the subspace of the previously selected rows. Intuitively, adaptive sampling seems to be limited to trivial multi-pass algorithms in the streaming model of computation due to its inherently sequential nature of assigning sampling probabilities to each row only after the previous iteration is completed. Surprisingly, we show this is not the case by giving the first one-pass algorithms for adaptive sampling on turnstile streams and using space poly(d,k,log n), where k is the number of adaptive sampling rounds to be performed. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model. We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume maximization on turnstile streams that use space sublinear in n. We complement our volume maximization algorithmic results with lower bounds that are tight up to lower order terms, even for multi-pass algorithms. By a similar construction, we also obtain lower bounds for volume maximization in the row-arrival model, which we match with competitive upper bounds. See paper for full abstract.