@inproceedings{shetty2022distribution,
author = {Shetty, Abhishek and Dwivedi, Raaz and Mackey, Lester},
title = {Distribution Compression in Near-Linear Time},
booktitle = {ICLR 2022},
year = {2022},
month = {April},
abstract = {In distribution compression, one aims to accurately summarize a probability distribution  using a small number of representative points. Near-optimal thinning procedures achieve this goal by sampling  points from a Markov chain and identifying  points with  discrepancy to . Unfortunately, these algorithms suffer from quadratic or super-quadratic runtime in the sample size . 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  points with  integration error and better-than-Monte-Carlo maximum mean discrepancy in  time and  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.},
url = {http://approjects.co.za/?big=en-us/research/publication/distribution-compression-in-near-linear-time/},
}