Automated Scalable Bayesian Inference via Hilbert Coresets

1. Introduction

• Automated inference lets experts and nonexperts use sophisticated models, explore models faster, and improve experimental reproducibility.Black-box methods require only a basic model specification, reducing the need to develop and tune model-specific algorithms.Source: §1 · p. 2
• Standard MCMC, variational, and other scalable methods do not consistently combine large-data tractability, inferential guarantees, automation, and freedom from model-specific tuning.MCMC can scale at least linearly with dataset size, while scalable alternatives may lack guarantees or require extensive expert tuning.Source: §1 · p. 2
• Existing Bayesian coreset construction is difficult to automate, may require bounded parameter spaces, and improves over uniform subsampling by only a constant factor.Its i.i.d. sampling also cannot update point importance based on previously selected points.Source: §1 · p. 3
• Hilbert coresets replace the supremum norm with an inner-product-induced norm and use importance sampling or Frank–Wolfe construction, with guarantees relating approximation quality to coreset size.The proposed norms include a weighted L2 norm and one based on Fisher information distance; random finite-dimensional projections automate inner-product computation.Source: §1 · p. 3
• The experiments cover multivariate Gaussian inference, logistic and Poisson regression, and von Mises–Fisher mixture modeling on real and synthetic data.They report high-quality posterior approximations and significantly reduced inference computation compared with standard automated inference algorithms.Source: §1 · p. 3

2. Background

• A Bayesian coreset is a small weighted subset whose log-likelihood approximates that of the full dataset, and it can be passed to standard MCMC.Running MCMC on the reduced dataset can reduce computation while retaining MCMC's theoretical guarantees.Source: §2 · p. 4
• The standard coreset construction draws M independent observations with probabilities proportional to their sensitivities, producing a coreset of size at most M.The method first computes each data point's sensitivity.Source: §2 · p. 4
• Sensitivity-based sampling yields a weighted log-likelihood whose expectation equals the full-data log-likelihood.The cited results establish high-probability coreset approximation guarantees as the construction size increases.Source: §2 · p. 4

3. Coresets as sparse vector sum approximation

• The uniform norm treats coreset construction as sparse approximation of the total log-likelihood vector by a weighted subset of data log-likelihood vectors.The construction objective minimizes approximation error subject to a limit on the number of nonzero weights.Source: §3 · pp. 4–5
• Uniform-norm coreset construction uses importance sampling with probabilities proportional to the norms of the data log-likelihood vectors.The guarantee depends on problem scale, vector alignment, and an approximate dimension of the log-likelihood vectors.Source: §3 · p. 5
• The uniform norm can diverge on unbounded or infinite-dimensional parameter spaces, forcing artificial restrictions, and its optimization objective is typically nonconvex and difficult to automate.This excludes common unbounded settings, including logistic regression with full-support parameter space Θ = R^d.Source: §3 · p. 6
• The uniform norm lacks directionality, so its error bound does not scale properly with vector alignment and depends on approximate dimension.When vectors are aligned, η = 0, yet the bound does not approach zero as η approaches zero.Source: §3 · p. 6
• Importance sampling can favor large-norm vectors pointing away from the total log-likelihood, even when other vectors individually approximate it well.In the Gaussian-mean illustration, it tends to select data far from the posterior mean rather than nearby data whose likelihoods closely match the scaled posterior; expected error can be arbitrarily worse than the optimal size-M coreset.Source: §3 · pp. 6–7, Figure 1 · p. 6

4. Hilbert coresets

• Hilbert coreset guarantees can reflect log-likelihood alignment, while directionality lets selection account for residual approximation error.The section develops importance-sampling and Frank–Wolfe algorithms under an inner-product norm.Source: §4 · p. 7

4.1. Coreset construction via importance sampling.

• Importance probabilities proportional to sensitivity exactly minimize expected squared Hilbert coreset error, and the high-probability bound incorporates vector alignment.The bound also depends on η from the earlier analysis.Source: §4.1 · pp. 7–8

4.2. Coreset construction via Frank–Wolfe.

• Frank–Wolfe incrementally selects log-likelihood vectors aligned with the residual error, adding at most one data point per iteration.The algorithm uses a polytope whose vertices each have a single nonzero component.Source: §4.2 · pp. 8–9
• With exact line search, the Frank–Wolfe guarantee captures logarithmic 1/M convergence for small M and a linear ν^M rate for large M.The stated alternative step size removes exact line-search computation but gives a weaker result.Source: §4.2 · p. 10

4.3. Distributed coreset construction.

• Running either algorithm for M iterations on each of C processors yields a merged coreset of size at most MC with a retained error guarantee.The merged coreset keeps the distributed weights unchanged.Source: §4.3 · p. 10

Norms

• The Fisher information norm measures expected squared differences between log-likelihood gradients under a weighting distribution ˆπ, ideally emphasizing regions of high posterior mass.The section also proposes a weighted L2 norm on log-likelihoods as another candidate.Source: §5 · p. 11
• The Fisher-gradient norm requires differentiable likelihoods; a weighted L2 norm on log-likelihoods is an alternative.The proposed norms are suggestions, and other Hilbert norms could also be used.Source: §5 · p. 11

Weighting distribution

• ˆπ may be chosen using a Laplace approximation, approximate sufficient statistics, subsample MCMC, the prior, or independent posterior conditionals; general-purpose selection is left for future work.The weighting distribution ideally matches the posterior, but obtaining it has significant computational cost.Source: §5 · pp. 11–12

Random projection

• Random finite-dimensional projections address intractable, model-specific inner products and make inner products with vector sums efficiently computable.The projections serve as approximations of the log-likelihood vectors used by the coreset algorithms.Source: §5 · p. 12
• Under the stated sub-Gaussian condition, the difference between true output error and projected output error shrinks as projection dimension J increases.The inner-product estimates used in the projections are unbiased.Source: §5 · pp. 12–13

6. Synthetic evaluation

• The 1,000-trial comparison tested random subsampling, uniform coresets, Hilbert importance sampling, and Hilbert Frank–Wolfe on 2D Gaussian-mean inference.The data comprised 1,000 observations, and both Hilbert constructions used the weighted Fisher information distance.Source: §6 · p. 13
• Using the true posterior as the Hilbert weighting distribution provided an ideal case in which that distribution well approximates the posterior.Under this choice, the Fisher information distance inner product was available in closed form.Source: §6 · p. 14

Results.

• Across coreset sizes, Frank–Wolfe produced higher-quality posterior approximations and needed fewer points than other methods to reach a reliable estimate.Figure 2 compares posterior predictive ellipses and plots KL-divergence against coreset iterations and projection dimension.Source: Results · p. 14, Figure 2 · p. 15
• Frank–Wolfe first selects a point near the center, then refines its estimate with distant points, while Hilbert and uniform coresets favor distant points.The near-center point’s scaled likelihood well approximates the true posterior.Source: Results · p. 14
• Figure 2e confirms linear convergence of Frank–Wolfe, while Figure 2f confirms projected Hilbert coreset posterior error converges toward that of the exact Hilbert coreset as projection dimension increases.The tests evaluate posterior approximation using the KL-divergence between approximate and true posteriors.Source: Results · p. 14, §6 · p. 14, Figure 2 · p. 15

7. Experiments

• Experiments compare logistic regression, Poisson regression, and directional clustering on real and synthetic data, using full-data MCMC as the benchmark.The evaluation focuses on Frank–Wolfe Hilbert coresets using the weighted Fisher information distance and uniform random subsampling.Source: §7 · p. 15

7.1. Models.

• The models cover binary-label prediction, count regression, and clustering unit-sphere data with a von Mises–Fisher mixture.The directional clustering model uses uniform priors on component modes and mixture weights and sets concentration τ = 50.Source: §7.1 · p. 16

7.2. Datasets.

• The datasets include synthetic and applied examples: phishing-site and chemical-reactivity classification, bike-trip and airport-delay counts, and synthetic directional clusters.The experiments vary coreset size and use 50 trials; logistic and Poisson regression use a random projection dimension of 500.Source: §7.2 · pp. 16–18, §7.3 · p. 18

7.3. Methods.

• Posterior quality is assessed by held-out negative log-likelihood and 1-Wasserstein distance to full-data MCMC samples, alongside computation time.The metrics are normalized to make results across datasets coherent.Source: §7.3 · pp. 18–19

7.4. Results and discussion.

• Across all models and datasets considered, Frank–Wolfe Hilbert coresets reduce both error metrics by orders of magnitude at a given computation-time budget and match full-data negative test log-likelihood in roughly one-tenth the time.The comparison uses the full-data MCMC posterior as a benchmark.Source: §7.4 · p. 21, Figure 6 · p. 21
• For any construction size M, both Hilbert algorithms improve posterior approximation over uniform random subsampling with comparable computation time; Frank–Wolfe can also be faster at fixed M.Frank–Wolfe may select the same point repeatedly, so its coreset can be much smaller than M, reducing inference cost.Source: §7.4 · pp. 21–22
• Hilbert importance sampling performs comparably to uniform coresets and random subsampling, while Frank–Wolfe typically outperforms random subsampling; weighted 2-norm and Fisher information norm perform similarly in tested cases.Detailed comparisons are deferred to Appendix B.Source: §7.4 · p. 22

8. Conclusion

• Hilbert coresets offer a fully automated, scalable, theoretically sound Bayesian inference framework that provides high-quality posterior approximations at a fraction of full-data inference cost.The authors state that the framework supports sophisticated modeling and exploratory analysis at scale.Source: §8 · p. 22
• Future work includes high-dimensional models, alternate Hilbert norms and weighting functions, tighter random-projection bounds, and Frank–Wolfe variants with stronger convergence guarantees.The authors also propose relating their norms to more familiar measures of posterior discrepancy.Source: §8 · p. 22

Appendix A. Technical results and proofs

• The appendix develops technical lemmas for the proofs, including Azuma’s inequality, a martingale Bennett inequality, and geometric results used in the Frank–Wolfe error bound.It also gives a bound on logistic recursion iterates.Source: Appendix A · pp. 22–23
• A geometric lemma relates the alignment constants used in the paper under a Hilbert norm.Source: Appendix A · p. 26
• The Frank–Wolfe proof concludes with a coreset of size at most M and derives the stated error bound from the iteration analysis.The proof notes that it computes M − 1 iterations after initialization.Source: Appendix A · p. 28

• Frank–Wolfe constructions outperform subsampling techniques across all models and datasets considered.Source: Appendix B · p. 29
• Hilbert importance sampling performs comparably to uniform coresets and uniformly random subsampling across the evaluated models and datasets.Hilbert coresets are often the best of the three subsampling techniques.Source: Appendix B · p. 29, Figure 7 · p. 30
• Weighted 2-norm and Fisher information norm constructions perform similarly in the importance-sampling and Frank–Wolfe cases considered.Source: Appendix B · p. 29, Figure 8 · p. 31, Figure 9 · p. 32

• The derivation targets the sensitivity of observation y_n used in Bayesian coreset construction, ignoring constants.Source: Appendix C · p. 33
• Varying mu over a fixed-radius ball centered at the data mean keeps the denominator constant.Source: Appendix C · p. 33
• The numerator is maximized when mu lies on the one-dimensional affine line between the data mean and y_n.Source: Appendix C · p. 33
• Reparameterizing mu along that line as lambda times the data mean plus (1 minus lambda) times y_n yields the optimization.Source: Appendix C · p. 33