# General bounds on the quality of Bayesian coresets

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 55 references that are in the map.
- First posted on arXiv 20 May 2024.

## Builds on (most cited first, 30 of 32)

- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Stochastic Gradient Hamiltonian Monte Carlo](https://mlsanity.com/paper/1402.4102/) (2014)
- [Advances in Variational Inference](https://mlsanity.com/paper/1711.05597/) (2017)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent](https://mlsanity.com/paper/1802.01737/) (2018)
- [Concentration of tempered posteriors and of their variational approximations](https://mlsanity.com/paper/1706.09293/) (2017)
- [Frequentist Consistency of Variational Bayes](https://mlsanity.com/paper/1705.03439/) (2017)
- [Stochastic gradient Markov chain Monte Carlo](https://mlsanity.com/paper/1907.06986/) (2019)
- [Automated Scalable Bayesian Inference via Hilbert Coresets](https://mlsanity.com/paper/1710.05053/) (2017)
- [On Markov chain Monte Carlo methods for tall data](https://mlsanity.com/paper/1505.02827/) (2015)
- [Introduction to Core-sets: an Updated Survey](https://mlsanity.com/paper/2011.09384/) (2020)
- [A Statistical Perspective on Algorithmic Leveraging](https://mlsanity.com/paper/1306.5362/) (2013)
- [Optimal Subsampling for Large Sample Logistic Regression](https://mlsanity.com/paper/1702.01166/) (2017)
- [Sparse Variational Inference: Bayesian Coresets from Scratch](https://mlsanity.com/paper/1906.03329/) (2019)
- [Control Variates for Stochastic Gradient MCMC](https://mlsanity.com/paper/1706.05439/) (2017)
- [Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget](https://mlsanity.com/paper/1304.5299/) (2013)
- [Firefly Monte Carlo: Exact MCMC with Subsets of Data](https://mlsanity.com/paper/1403.5693/) (2014)
- [Speeding Up MCMC by Efficient Data Subsampling](https://mlsanity.com/paper/1404.4178/) (2014)
- [Consistency of Variational Bayes Inference for Estimation and Model Selection in Mixtures](https://mlsanity.com/paper/1805.05054/) (2018)
- [Surrogate Likelihoods for Variational Annealed Importance Sampling](https://mlsanity.com/paper/2112.12194/) (2021)
- [Bayesian inference via sparse Hamiltonian flows](https://mlsanity.com/paper/2203.05723/) (2022)
- [The True Cost of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1706.02692/) (2017)
- [Optimal Subsampling Algorithms for Big Data Regressions](https://mlsanity.com/paper/1806.06761/) (2018)
- [Adaptive, delayed-acceptance MCMC for targets with expensive likelihoods](https://mlsanity.com/paper/1509.00172/) (2015)
- [Optimal subsampling for quantile regression in big data](https://mlsanity.com/paper/2001.10168/) (2020)
- [Fast Bayesian Coresets via Subsampling and Quasi-Newton Refinement](https://mlsanity.com/paper/2203.09675/) (2022)
- [The computational asymptotics of Gaussian variational inference and the Laplace approximation](https://mlsanity.com/paper/2104.05886/) (2021)
- [More Efficient Estimation for Logistic Regression with Optimal Subsample](https://mlsanity.com/paper/1802.02698/) (2018)
- [Subsampling MCMC - An introduction for the survey statistician](https://mlsanity.com/paper/1807.08409/) (2018)
- [Coreset Markov Chain Monte Carlo](https://mlsanity.com/paper/2310.17063/) (2023)

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

- [Tuning-Free Coreset Markov Chain Monte Carlo via Hot DoG](https://mlsanity.com/paper/2410.18973/) (2024)
- [Evaluation and Incident Prevention in an Enterprise AI Assistant](https://mlsanity.com/paper/2504.13924/) (2025)

## Abstract (arXiv)

Bayesian coresets speed up posterior inference in the large-scale data regime by approximating the full-data log-likelihood function with a surrogate log-likelihood based on a small, weighted subset of the data. But while Bayesian coresets and methods for construction are applicable in a wide range of models, existing theoretical analysis of the posterior inferential error incurred by coreset approximations only apply in restrictive settings -- i.e., exponential family models, or models with strong log-concavity and smoothness assumptions. This work presents general upper and lower bounds on the Kullback-Leibler (KL) divergence of coreset approximations that reflect the full range of applicability of Bayesian coresets. The lower bounds require only mild model assumptions typical of Bayesian asymptotic analyses, while the upper bounds require the log-likelihood functions to satisfy a generalized subexponentiality criterion that is weaker than conditions used in earlier work. The lower bounds are applied to obtain fundamental limitations on the quality of coreset approximations, and to provide a theoretical explanation for the previously-observed poor empirical performance of importance sampling-based construction methods. The upper bounds are used to analyze the performance of recent subsample-optimize methods. The flexibility of the theory is demonstrated in validation experiments involving multimodal, unidentifiable, heavy-tailed Bayesian posterior distributions.