Variance-Optimal Offline and Streaming Stratified Random Sampling

Trong Duc Nguyen, Ming-Hung Shih, Divesh Srivastava, Srikanta Tirthapura, Bojian XuarXiv 2018 · OpenReview

TL;DR

This paper introduces VOILA, an offline algorithm for stratified random sampling (SRS) that optimizes sample allocation even when some data strata are "bounded" (have fewer data points than needed for optimal allocation). They also present S-VOILA, a streaming SRS algorithm that adapts to data changes and achieves near-optimal variance, outperforming traditional methods like Neyman allocation, especially in dynamic or bounded-strata scenarios.

What Problem Does This Paper Address?

Traditional methods for stratified random sampling (SRS), like Neyman allocation, aim to minimize the variance of estimates from a sample. However, these methods often assume that each data stratum is "abundant," meaning it has a large enough number of data points to satisfy its allocated sample size. This assumption breaks down in real-world scenarios where some strata might be "bounded" – having fewer data points than theoretically optimal. This leads to suboptimal sample allocations and increased variance in estimates. Furthermore, existing SRS methods are predominantly offline, requiring all data to be available beforehand, which is impractical for continuously arriving data streams. This paper addresses both the bounded strata problem in offline SRS and the challenge of maintaining variance-optimal SRS in a streaming setting.

Methods

The paper introduces two main algorithmic contributions:

  • VOILA (Variance-OptImaL Allocation): An offline algorithm for variance-optimal SRS that explicitly handles bounded strata. It achieves this by first framing the problem as "sample size reduction" from a hypothetical full data sample (zero variance) to the target memory budget. VOILA leverages an efficient algorithm called FastSSR (a fast, iterative implementation of sample size reduction) to determine the optimal allocation of sample sizes across strata, minimizing the increase in variance. It generalizes Neyman allocation, reducing to it when all strata are abundant.
  • S-VOILA: A practical streaming algorithm for SRS. It maintains a stratified random sample by making "locally optimal" decisions as new data arrives. When a minibatch of data arrives, S-VOILA updates stratum statistics and selects elements based on random keys. If the sample size exceeds the memory budget, it uses variance-optimal sample size reduction techniques (specifically, SingleSSR for reducing by one element, and FastSSR for larger reductions) to evict elements, thereby minimizing the increase in variance. S-VOILA is designed to adapt to changing data characteristics and stratum sizes in a streaming fashion.

The paper also establishes a theoretical lower bound for streaming SRS algorithms, showing that in the worst case, their variance can be Ω(r) times that of the optimal offline algorithm, where 'r' is the number of strata.

Datasets

  • OpenAQ dataset: A real-world dataset containing over 31 million air quality measurements from 2016. It was used to stratify data by country and measurement type, resulting in 177 strata. This dataset exhibits dynamic changes in stratum characteristics over time.
  • Synthetic dataset: A dataset created to have more control over data characteristics. It features 20 strata with initially equal frequencies. A specific experiment involved increasing the standard deviation of one stratum significantly to observe how algorithms adapt.

Key Insights and Ideas

  • Bounded strata are a critical issue: Traditional methods like Neyman allocation perform poorly when strata are bounded, highlighting the need for algorithms that explicitly account for this.
  • Sample size reduction is a unifying concept: Both offline and streaming SRS can be viewed as problems of reducing a larger sample (or the entire dataset) to a target memory budget while minimizing variance increase.
  • Streaming algorithms face inherent limitations: A theoretical lower bound shows that streaming SRS algorithms, due to their inability to revisit past data and potentially increase sample sizes quickly, will always have a worst-case variance at least Ω(r) times worse than optimal offline methods.
  • Local optimality can lead to good global performance: S-VOILA's strategy of making locally optimal decisions for sample eviction and selection, especially with larger minibatches, allows it to closely track the performance of the offline optimal algorithm.
  • Minibatch processing significantly improves streaming SRS: Using minibatches in S-VOILA leads to more stable and near-optimal variance compared to processing elements one by one, as it allows for better informed eviction decisions.

Key Results

  • VOILA vs. Neyman: VOILA achieved significantly smaller variances than Neyman allocation (1.4x to 50x smaller) on real-world data, demonstrating its effectiveness with bounded strata.
  • S-VOILA vs. VOILA: The streaming algorithm S-VOILA (especially with minibatch processing) achieved variances very close to the optimal offline algorithm VOILA.
  • Streaming Lower Bound: A theoretical lower bound of Ω(r) was established for the worst-case variance of streaming SRS algorithms compared to optimal offline methods.
  • Minibatch Impact: For S-VOILA, increasing the minibatch size (e.g., to 100 elements) significantly reduced variance, bringing it close to optimal.
  • Query Performance: S-VOILA and VOILA showed better query accuracy than Reservoir and Uniform sampling, even with smaller sample sizes.

Limitations and Future Work

  • Streaming adaptation speed: While S-VOILA adapts to changes, it may lag behind offline methods like VOILA when significant changes occur in strata characteristics, especially with single-element processing. The paper suggests that larger minibatches help mitigate this.
  • Future Work: The authors suggest several directions:
  • Restratification in a streaming manner: Dynamically changing the strata definitions as data arrives.
  • Time-decay into sampling: Giving more recent elements a higher probability of being sampled.
  • Stratified random sampling on distributed data: Extending these methods to distributed environments.

Summary updated

Abstract

Stratified random sampling (SRS) is a fundamental sampling technique that provides accurate estimates for aggregate queries using a small size sample, and has been used widely for approximate query processing. A key question in SRS is how to partition a target sample size among different strata. While Neyman allocation provides a solution that minimizes the variance of an estimate using this sample, it works under the assumption that each stratum is abundant, i.e., has a large number of data points to choose from. This assumption may not hold in general: one or more strata may be bounded, and may not contain a large number of data points, even though the total data size may be large. We first present VOILA, an offline method for allocating sample sizes to strata in a variance-optimal manner, even for the case when one or more strata may be bounded. We next consider SRS on streaming data that are continuously arriving. We show a lower bound, that any streaming algorithm for SRS must have (in the worst case) a variance that is {\Omega}(r) factor away from the optimal, where r is the number of strata. We present S-VOILA, a practical streaming algorithm for SRS that is locally variance-optimal in its allocation of sample sizes to different strata. Our result from experiments on real and synthetic data show that VOILA can have significantly (1.4 to 50.0 times) smaller variance than Neyman allocation. The streaming algorithm S-VOILA results in a variance that is typically close to VOILA, which was given the entire input beforehand.
BibTeX
@misc{nguyen2018variance,
  author = {Trong Duc Nguyen and Ming-Hung Shih and Divesh Srivastava and Srikanta Tirthapura and Bojian Xu},
  title = {{Variance-Optimal Offline and Streaming Stratified Random Sampling}},
  year = {2018},
  eprint = {1801.09039},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1801.09039},
}

Loading related content...

Figure