Abstract
Bayesian coresets have emerged as a promising approach for implementing scalable Bayesian inference. The Bayesian coreset problem involves selecting a (weighted) subset of the data samples, such that the posterior inference using the selected subset closely approximates the posterior inference using the full dataset. This manuscript revisits Bayesian coresets through the lens of sparsity constrained optimization. Leveraging recent advances in accelerated optimization methods, we propose and analyze a novel algorithm for coreset selection. We provide explicit convergence rate guarantees and present an empirical evaluation on a variety of benchmark datasets to highlight our proposed algorithm’s superior performance compared to state-of-the-art on speed and accuracy.
Introduction
Bayesian inference provides a robust framework for uncertainty quantification, yet its computational cost often becomes prohibitive as dataset sizes ($n$) grow. Standard techniques like Markov Chain Monte Carlo (MCMC) and Variational Inference (VI) typically scale linearly with $n$, making them impractical for massive datasets.
Bayesian coresets address this challenge by replacing the full dataset with a small, weighted subset of $k$ points ($k \ll n$) that yields a posterior distribution nearly identical to the original. However, identifying the optimal $k$ points is a difficult combinatorial problem. Existing methods generally rely on convex relaxations (e.g., Frank-Wolfe), which can be slow and less accurate, or greedy approaches (e.g., GIGA, SparseVI) that are often "short-sighted" and computationally expensive as $k$ increases.
The A-IHT Framework
This work re-envisions coreset selection as a sparse regression problem within a Hilbert space. Rather than relaxing the sparsity constraint, the authors propose Automated Accelerated Iterative Hard Thresholding (A-IHT), an algorithm that directly optimizes the nonconvex objective.
A-IHT introduces several critical enhancements over standard IHT:
- Nesterov-style Acceleration: Incorporates momentum to accelerate convergence.
- Adaptive Step Sizes: Utilizes an exact line search to automatically determine optimal step sizes and momentum weights, eliminating the need for manual hyperparameter tuning.
- De-biasing (A-IHT II): An advanced variant that includes an additional gradient step in the sparsified space to further minimize approximation error.
Unlike greedy methods that add points sequentially and scale as $O(nk)$, A-IHT updates the entire set of $k$ points simultaneously with a per-iteration complexity of $O(n \log k)$. This allows the algorithm to "correct" suboptimal choices made in earlier iterations, leading to more robust coresets.
Experimental Evaluation
The proposed algorithms were evaluated across several benchmarks, including synthetic Gaussian posteriors, Bayesian Radial Basis Function (RBF) regression (using UK housing price data), and Logistic/Poisson regression (using the Phishing dataset).
Accuracy and Convergence
In Gaussian and RBF regression tasks, A-IHT and A-IHT II consistently achieved lower Kullback–Leibler (KL) divergence than state-of-the-art greedy methods like GIGA and SparseVI. The algorithm demonstrates linear convergence under the Restricted Isometry Property (RIP), providing a strong theoretical foundation for its empirical success.
Computational Efficiency
A-IHT demonstrates significant computational advantages, particularly as the coreset size $k$ increases. While greedy methods like GIGA see a linear increase in time cost, A-IHT's cost remains relatively flat. Furthermore, while SparseVI can achieve high accuracy, it is often orders of magnitude slower than A-IHT.
Discussion and Future Work
By embracing the nonconvex nature of sparsity constraints rather than avoiding them, A-IHT provides a path toward more efficient and accurate Bayesian coreset selection. The use of full gradients ensures that the algorithm has comprehensive information about the optimal support set at each step.
Future research could explore extending this framework to more complex constraints, such as group or structured sparsity, which are relevant for hierarchical Bayesian models. Additionally, while the algorithm performs well in practice, further investigation into relaxing the RIP assumption for theoretical guarantees remains an open area of interest.
Summary updated