# Distribution Compression in Near-linear Time

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 30 references that are in the map.
- First posted on arXiv 15 Nov 2021.

## Builds on (most cited first, 5 of 5)

- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Optimal Thinning of MCMC Output](https://mlsanity.com/paper/2005.03952/) (2020)
- [Statistically efficient thinning of a Markov chain sampler](https://mlsanity.com/paper/1510.07727/) (2015)

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

- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [Compress Then Test: Powerful Kernel Testing in Near-linear Time](https://mlsanity.com/paper/2301.05974/) (2023)
- [Counterfactual inference in sequential experiments](https://mlsanity.com/paper/2202.06891/) (2022)
- [Kernel quadrature with randomly pivoted Cholesky](https://mlsanity.com/paper/2306.03955/) (2023)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Low-Rank Thinning](https://mlsanity.com/paper/2502.12063/) (2025)
- [WildCat: Near-Linear Attention in Theory and Practice](https://mlsanity.com/paper/2602.10056/) (2026)
- [Estimating the Rate-Distortion Function by Wasserstein Gradient Descent](https://mlsanity.com/paper/2310.18908/) (2023)
- [Efficient and Accurate Explanation Estimation with Distribution Compression](https://mlsanity.com/paper/2406.18334/) (2024)
- [Supervised Kernel Thinning](https://mlsanity.com/paper/2410.13749/) (2024)
- [Learning Counterfactual Distributions via Kernel Nearest Neighbors](https://mlsanity.com/paper/2410.13381/) (2024)
- [Stationary MMD Points](https://mlsanity.com/paper/2505.20754/) (2025)
- [Policy Gradient with Kernel Quadrature](https://mlsanity.com/paper/2310.14768/) (2023)
- [Monte Carlo with kernel-based Gibbs measures: Guarantees for probabilistic herding](https://mlsanity.com/paper/2402.11736/) (2024)
- [Thinned Mean Field Langevin Dynamics](https://mlsanity.com/paper/2605.28589/) (2026)
- [Quenched large deviations for Monte Carlo integration with Coulomb gases](https://mlsanity.com/paper/2508.01392/) (2025)
- [Bilateral Distribution Compression: Reducing Both Data Size and Dimensionality](https://mlsanity.com/paper/2509.17543/) (2025)
- [Express Language Modeling](https://mlsanity.com/paper/2606.10944/) (2026)
- [Amortized quadrature for posterior expectations in inverse problems](https://mlsanity.com/paper/2606.15871/) (2026)

## Abstract (arXiv)

In distribution compression, one aims to accurately summarize a probability distribution mathbbP using a small number of representative points. Near-optimal thinning procedures achieve this goal by sampling n points from a Markov chain and identifying √n points with widetildeO(1/√n) discrepancy to mathbbP. Unfortunately, these algorithms suffer from quadratic or super-quadratic runtime in the sample size n. To address this deficiency, we introduce Compress++, a simple meta-procedure for speeding up any thinning algorithm while suffering at most a factor of 4 in error. When combined with the quadratic-time kernel halving and kernel thinning algorithms of Dwivedi and Mackey (2021), Compress++ delivers √n points with O(√log n/n) integration error and better-than-Monte-Carlo maximum mean discrepancy in O(n log3 n) time and O( √n log2 n ) space. Moreover, Compress++ enjoys the same near-linear runtime given any quadratic-time input and reduces the runtime of super-quadratic algorithms by a square-root factor. In our benchmarks with high-dimensional Monte Carlo samples and Markov chains targeting challenging differential equation posteriors, Compress++ matches or nearly matches the accuracy of its input algorithm in orders of magnitude less time.