Density Sketches for Sampling and Estimation

Aditya Desai, Benjamin Coleman, Anshumali Shrivastava

TL;DR

This paper introduces Density Sketches (DS), a novel streaming data structure that creates a compact summary of data distributions. DS allows for efficient sampling of synthetic data that asymptotically converges to the true underlying distribution, offering a practical alternative to storing massive datasets for machine learning tasks.

What Problem Does This Paper Address?

The explosion of data generated worldwide presents a significant challenge for machine learning pipelines. Storing and processing this data is often infeasible due to its sheer volume. While existing methods like histograms and Kernel Density Estimators (KDEs) can approximate distributions, they often suffer from high memory requirements or lack theoretical guarantees. Generative models can produce synthetic data but don't offer statistical guarantees on the distribution. This paper addresses the need for a data-efficient, streaming approach that can summarize data distributions, enable on-the-fly sampling, and provide theoretical guarantees on the quality of the generated samples.

Methods

The core of Density Sketches (DS) lies in its connection between LSH-based partitioning and count sketches. The authors propose using LSH functions to partition the data space into bins. A count sketch (CS) is then employed to store a compressed representation of the counts within these bins, rather than the raw data. To facilitate efficient sampling, a min-heap is used to maintain the "heavy" partitions (those with the most data points).

The process involves:

  1. LSH-based Partitioning: Randomly generated LSH functions partition the data space into bins.
  2. Count Sketching: A count sketch (M) is used to store approximate counts of data points falling into each bin in a streaming fashion.
  3. Heavy Partition Tracking: An augmented min-heap (H) keeps track of the top H partitions with the highest counts.
  4. Sampling: To generate a synthetic data point, a partition is first chosen probabilistically from the heap (weighted by its count), and then a random point is sampled uniformly from within that chosen partition.

This approach allows for a compressed representation of the density, enabling sampling without storing the original data, and offering a tunable accuracy-storage trade-off.

Datasets

The paper evaluates its approach on the following datasets:

  • Multi-Gaussian distribution: Used for initial sanity checks of density capture.
  • MNIST dataset: Used to visualize samples from DS.
  • Higgs dataset: A large dataset (10M samples, 28 dimensions) used for classification tasks.
  • Susy dataset: Another large dataset (5M samples, 18 dimensions) used for classification tasks.

The authors note that large datasets with dimensions less than 100 and more than 1,000 samples per class are suitable for DS.

Key Insights and Ideas

  • Bridging KDE and Histograms: The paper establishes a crucial connection: LSH-based randomized histograms have an expected value equal to KDE estimates. This insight allows the authors to leverage the strengths of both approaches.
  • Count Sketch for Compression: Using count sketches to compress histogram bins is key to achieving memory efficiency, especially in high dimensions where traditional histograms become intractable.
  • Heap for Efficient Sampling: Maintaining a min-heap of "heavy" partitions is an ingenious way to enable efficient sampling from the compressed distribution. It prioritizes the most informative parts of the data.
  • Theoretical Guarantees: Unlike many generative models, DS provides theoretical guarantees that the sampling distribution asymptotically converges to the true underlying density.
  • Streaming and Online Updates: The DS construction is inherently streaming, allowing for efficient online updates as new data arrives, making it suitable for dynamic data environments.

Key Results

  • Density Capture: Visualizations show that DS successfully captures the density information of the original data, producing samples that are visually indistinguishable from those drawn from the true distribution (e.g., multi-Gaussian example).
  • Compression Ratios: For large datasets like Higgs (2.5GB original), DS achieved a 50x compression, reaching near-original data accuracy on downstream classification tasks with only 50MB of sketch size. Similar compression was observed for the Susy dataset (100x compression).
  • Performance: DS consistently outperformed random samples and Liberty coresets in downstream classification tasks across various memory sizes.
  • Parameter Sensitivity: The performance of DS is sensitive to the choice of bin width (B), with an optimal value existing for best performance. The parameters K and R (count sketch parameters) showed stable performance for a reasonable budget.

Limitations and Future Work

  • Curse of Dimensionality: DS inherits the curse of dimensionality from histograms, meaning the number of samples needed can still grow exponentially with dimension. However, the paper argues that DS handles this better than traditional histograms by discarding empty bins.
  • Data Space Limitations: DS may not perform well on data types where standard distance metrics do not imply conceptual similarity (e.g., images). The authors suggest learning a transformation for such data, though this might sacrifice theoretical guarantees.
  • Future Work: The paper suggests exploring differential privacy for density sketches, which they demonstrate by adding noise to the count sketch. They also mention the potential for further theoretical analysis and applications in various machine learning tasks.

Summary updated

Abstract

There has been an exponential increase in the data generated worldwide. Insights into this data led by machine learning (ML) have given rise to exciting applications such as recommendation engines, conversational agents, and so on. Often, data for these applications is generated at a rate faster than ML pipelines can consume it. In this paper, we propose Density Sketches(DS) - a cheap and practical approach to reducing data redundancy in a streaming fashion. DS creates a succinct online summary of data distribution. While DS does not store the samples from the stream, we can sample unseen data on the fly from DS to use for downstream learning tasks. In this sense, DS can replace actual data in many machine learning pipelines analogous to generative models. Importantly, unlike generative models, which do not have statistical guarantees, the sampling distribution of DS asymptotically converges to underlying unknown density distribution.
BibTeX
@inproceedings{desai2023density,
  author = {Aditya Desai and Benjamin Coleman and Anshumali Shrivastava},
  title = {{Density Sketches for Sampling and Estimation}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=SdXv2C2-tnj},
}
Figure