Research map / Probabilistic and scientific modeling / Variational and generative sampling
General bounds on the quality of Bayesian coresets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives general large-data lower and upper bounds on the KL divergence of Bayesian coreset posterior approximations, and applies them to importance-weighted and subsample-optimize coreset methods on Cauchy location and logistic regression models.
Problem
Existing theoretical guarantees for Bayesian coreset posterior approximation error only hold for restrictive settings (exponential families, strongly log-concave smooth models), leaving general models without lower or general upper bounds on KL error.
Approach
Lower bounds on min of forward/reverse KL via a Hellinger/Vajda-type argument localized to a neighborhood of the posterior concentration point, requiring only mild asymptotic assumptions; upper bounds via a multivariate generalized subexponentiality condition on the log-likelihood moment generating function. These bounds are used to show importance-weighted coresets need M proportional to N and su
Key results
- Importance-weighted coresets have KL lower bounded by Omega_p(N/M), so M must scale proportionally to N for bounded error.
- Even with optimal post-hoc weight scaling, the KL lower bound is Omega_p(log(N/M)), so M proportional to N is still required.
- Subsample-optimize coresets of size M = O(polylog N) are shown to have bounded KL under the stated subexponentiality and alignment conditions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use importance-weighted subsampling with M = o(N) | Importance-weighted Bayesian coresets · General Bayesian models, data-asymptotic | minimum forward/reverse KL: \Omega_p\left(\frac{N}{M}\right) | Hurt |
| Apply optimal post-hoc scaling to importance-weighted coreset weights, with M = o(N) | Importance-weighted Bayesian coresets · General Bayesian models, data-asymptotic | minimum forward/reverse KL: \Omega_p\left(\log\frac{N}{M}\right) | Hurt |
| Restrict any coreset construction to a fixed size M < d | Any Bayesian coreset construction · General Bayesian models, data-asymptotic | minimum forward/reverse KL: \Omega_p\left(\log N\right) | Hurt |
| Subsample data points and optimize the selected points' weights, using M = O(\mathrm{polylog}(N)) | Subsample-optimize coreset · General Bayesian models satisfying the stated assumptions | maximum forward/reverse KL: O_p(1) | Helped |
| Use subsample-optimize construction with M \propto \log N | Subsample-optimize coreset · Cauchy location model and logistic regression model | maximum forward/reverse KL | Helped |
Surprising findings
- Importance-weighted coreset construction, even with post-hoc optimal scaling, cannot achieve bounded KL unless coreset size grows linearly with N.
Limitations
- The subexponentiality constant and alignment probability require case-by-case analysis.
- Upper bound for subsample-optimize relies on alignment conditions that are not generally verified.
Experimental setup
Metrics: forward KL reverse KL min of forward and reverse KL
Baselines: importance-weighted coresets scaled importance-weighted coresets
Builds on: Bayesian coresets Vajda's inequality Jensen's inequality
Closest papers by meaning
- Coresets for Scalable Bayesian Logistic Regression (NeurIPS 2016 · similarity 0.91)
- Fast Bayesian Coresets via Subsampling and Quasi-Newton Refinement (NeurIPS 2022 · similarity 0.91)
- Sparse Variational Inference: Bayesian Coresets from Scratch (NeurIPS 2019 · similarity 0.89)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.84)
- The Impact of Coreset Selection on Spurious Correlations and Group Robustness (NeurIPS 2025 · similarity 0.83)
- Asymptotically Log-Optimal Bayes-Assisted Confidence Sequences for Bounded Means (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.