Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent

By Trevor Campbell, Tamara Broderick. 2018

151 citations recorded by the source corpus.

Coherent uncertainty quantification is a key strength of Bayesian methods. But modern algorithms for approximate Bayesian posterior inference often sacrifice accurate posterior uncertainty estimation in the pursuit of scalability. This work shows that previous Bayesian coreset construction algorithms---which build a small, weighted subset of the data that approximates the full dataset---are no exception. We demonstrate that these algorithms scale the coreset log-likelihood suboptimally, resulting in underestimated posterior uncertainty. To address this shortcoming, we develop greedy iterative geodesic ascent (GIGA), a novel algorithm for Bayesian coreset construction that scales the coreset log-likelihood optimally. GIGA provides geometric decay in posterior approximation error as a function of coreset size, and maintains the fast running time of its predecessors. The paper concludes with validation of GIGA on both synthetic and real datasets, demonstrating that it reduces posterior approximation error by orders of magnitude compared with previous coreset constructions.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

GCR: Gradient Coreset based Replay Buffer Selection for Continual Learning (2021, neutral): “Coresets enable efﬁcient and scalable Bayesian inference [30, 31, 32, 33, 34] by approximating the model logit sum of the entire data.”
Facilitating Bayesian Continual Learning by Natural Gradients and Stein Gradients (2019, methodology): “There are some existing approaches to Bayesian coreset construction for scalable machine learning [7, 8], the idea is to find a sparse weighted subset of data to approximate the likelihood over the whole dataset.”
Coresets for Data-efficient Training of Machine Learning Models (2019, methodology): “…nearest-neighbors (Wei et al., 2015), mixture models (Lucic et al., 2017), low rank approximation (Cohen et al., 2017), spectral approximation (Agarwal et al., 2004; Li et al., 2013), Nystrom methods (Agarwal et al., 2004; Musco & Musco, 2017), and Bayesian inference (Campbell & Broderick, 2018).”
Sparse Variational Inference: Bayesian Coresets from Scratch (2019, methodology): “5, Appendix C shows that SparseVI is signiﬁcantly slower than Hilbert coreset construction via GIGA [32], primarily due to the expensive gradient descent weight update.”
Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective (2021, methodology): “The experiment was proposed by Campbell & Broderick (2019), and is used in (Campbell & Broderick, 2018) (GIGA) and (Campbell & Beronov, 2019) (SparseVI).”
RETRIEVE: Coreset Selection for Efficient and Robust Semi-Supervised Learning (2021, methodology): “Figure 5 shows the results comparing the BAYESIANCORESET method [6], adapted to the SSL setting with RETRIEVE using the VAT algorithm for 20% and 30% CIFAR10 subsets.”
Selection Via Proxy: Efficient Data Selection For Deep Learning (2019, background): “…selection attempts to ﬁnd a representative subset of points to speed up learning or clustering; such as k -means and k -medians [Har-Peled and Kushal, 2007], SVM [Tsang et al., 2005], Bayesian logistic regression [Huggins et al., 2016], and Bayesian inference [Campbell and Broderick, 2017, 2018].”
GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning (2020, methodology): “Coreset algorithms have been used for several problems including k-means clustering (Har-Peled and Mazumdar 2004), SVMs (Clarkson 2010) and Bayesian inference (Campbell and Broderick 2018).”
GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training (2021, methodology): “Coreset algorithms have been used for several problems including k-means and k-median clustering (Har-Peled & Mazumdar, 2004), SVMs (Clarkson, 2010) and Bayesian inference (Campbell & Broderick, 2018).”