Predictive Coresets

Bernardo Flores · 2025

Read Predictive Coresets by Bernardo Flores (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-05725.txt.

Introduction

Large datasets make standard statistical inference slow, so analysts often pick a small weighted subset, called a coreset, that stands in for the whole. The usual way to build one compares how likely the data look under the full set versus the subset, but that breaks down for flexible models whose likelihood cannot be written down. Bernardo Flores offers a different route that works with predictions instead of likelihoods.

The method uses randomized posteriors and picks weights so that the forecasts made from the small subset match the forecasts made from all the data. An algorithm based on step-by-step predictive updating carries this out, and it fits flexible models with no fixed form. Tests cover problems such as random partitions of data and estimating smooth density curves, where the new coresets kept the accuracy of full-data analysis at a fraction of the cost.

Catalog record

CREATORBernardo Flores
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-05725

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Predictive Coresets Bernardo Flores Abstract Modern data analysis often involves massive datasets with hundreds of thousands of observations, making traditional inference algorithms computationally prohibitive. Coresets are selection methods designed to choose a smaller subset of observations while maintaining similar learning performance. Conventional coreset approaches determine these weights by minimizing the Kullback-Leibler (KL) divergence between the likelihood functions of the full and weighted datasets; as a result, this makes them ill-posed for nonparametric models, where the likelihood is often intractable. We propose an alternative variational method which employs randomized posteriors and finds weights to match the unknown posterior predictive distributions conditioned on the full and reduced datasets. Our approach provides a general algorithm based on predictive recursions suitable for nonparametric priors. We evaluate the performance of the proposed coreset construction on diverse problems, including random partitions and density estimation. Keywords: coresets, predictive inference, Dirichlet process, optimal transport. 1 Introduction We propose a construction of coresets based on a predictive view of Bayesian posterior inference ( Fong et al., 2024 , Fortini and Petrone, 2012 ) . The main attraction of the approach is the model-agnostic nature - the method is valid with any inference model and independent of the specific inference goals, making it highly adaptable for a wide range of applications. Such adaptability is particularly valuable in the context of large-scale datasets, now commonplace in fields like genomics and astronomy. While this explosion of data offers incredible opportunities for discoveries, it also brings significant computational challenges. Tasks that were once straightforward, such as evaluating likelihoods several times have become increasingly difficult, making traditional data processing methods impractical. These obstacles have frequently pushed practitioners toward simpler statistical models that might not capture the full complexity of the data, disregarding expressiveness and flexibility that rich hierarchical and nonparametric models can offer. Typically, scaling Bayesian inference for massive data involves tweaking specific algorithms like Markov Chain Monte Carlo (MCMC) or variational Bayes to handle data distributed across systems or streaming in real-time. Techniques such as mini-batches and streaming for variational Bayes ( Hoffman et al., 2013 ) ( Broderick et al., 2013a ) , subsampling methods for MCMC ( Quiroz et al., 2018 ) , and distributed methods for MCMC ( Scott et al., 2016 ) are prominent examples. However, these existing methods have their drawbacks. In practice, subsampling MCMC methods often need to examine a significant portion of the data each time to be able to reach stationarity, which limits their efficiency gains ( Johndrow et al., 2020 ) . More scalable approaches like consensus MCMC and streaming variational Bayes improve computational efficiency but often lack rigorous theoretical backing and come with no guarantees for the quality of the proposed inference. A key observation in handling large datasets is that much of the data is redundant, while a smaller portion contains unique information. For instance, in a clustering setting, data points at the border of the cluster carry more discrimination power than the ones on the inside; moreover, adding two points close to each other does not add more structural information than just incorporating one of them. Similarly, in genome-wide association studies, only a small proportion of genes actually are correlated to the target, which requires a careful control of the false discovery rate ( Sesia et al., 2021 ) . Building upon these observations, a recent trend has been to focus on modifying the dataset itself rather than altering the inference algorithms. Specifically, to introduce a preprocessing step that constructs a coreset, a small, weighted subset of the original data that effectively approximates the inference with the full dataset. This coreset can be used with standard inference procedures to produce posterior approximations with guaranteed accuracy ( Huggins et al., 2016 ) . Coresets originated in computational geometry ( Feldman, 2020 ) . In the Bayesian context several algorithms have been developed with strong theoretical backings; see Campbell and Broderick (2019) , Huggins et al. (2016) , Manousakas et al. (2020) ; yet the nature of these approaches using likelihoods has limited the applications for deep hierarchical models and likelihood-free settings like non-Euclidean and simulator-based models ( Winter et al., 2023 ) . In this paper we extend the concept of coresets by focusing on the posterior predictive distributions, rather than on the likelihoods; as well as using distances between probability measures instead of data points. This change of strategy allows us to include prior structure and to accommodate non-standard applications with data in non-Euclidean spaces. In Section 2, we review existing coreset approaches. Section 3 introduces our novel coreset construction alongside a detailed algorithm. In Sections 4 and 5, we demonstrate the versatility of our method through three applications—parametric logistic regression, random partitions and density estimation. Section 6 establishes theoretical guarantees by analyzing posterior contraction rates. Finally, Section 7 outlines an extension of the algorithm from Section 3 that facilitates faster hyperparameter exploration, and we conclude with some final comments. 2 Coresets Coresets are data summarizing methods designed to, given a data set and a learning algorithm, reduce the size of the dataset while retaining a similar learning performance ( Campbell and Broderick, 2019 ) . Typically one wishes to approximate a density \pi^{N} comprised of N potentials \{f_{n}(\theta)\}_{n=1}^{N} and a base density \pi , \pi^{N}(\theta)=\frac{1}{Z}\exp\left(\sum_{n=1}^{N}f_{n}(y_{n},\theta)\right)\pi(\theta). In a Bayesian context, \pi is the prior distribution, f_{n} is the log-likelihood of the n th data point, and hence \pi^{N} is the posterior density. The approximation is formulated by defining a set of sparse weights w=(w_{n})_{1}^{N} such that only at most M weights are non-zero, where M<<N , and then running the estimation algorithm on the weighted likelihood p_{\theta}(w\odot y_{1:N})=\frac{1}{Z(w)}\exp\left(\sum_{n=1}^{N}w_{n}f_{n}(y_{n},\theta)\right), where the operator \odot denotes the weighting by w . We denote the posteriors obtained under weights w as \pi^{N}_{w} . Whenever no weights are used—that is, when all weights are set to 1—we denote the coreset by \pi_{1}^{N} and refer to it as the unit coreset. Finding the set of optimal weights w^{*} can be done in a variational way by minimizing the Kullback-Leibler (KL) divergence between the weighted posterior \pi^{N}_{w} and \pi^{N}_{1} , defined as D_{KL}\left(\pi_{w}^{N}\mid\pi_{1}^{N}\right)=\int\pi_{w}^{N}\log\frac{\pi_{w}^{N}}{\pi_{1}^{N}} Thus w^{*} is the solution of the optimization program w^{*}:=\argmin_{w\in\mathbb{R}^{N}}\;D_{KL}\left(\pi_{w}^{N}\mid\pi_{1}^{N}\right)\quad\text{s.t.}\quad w\geq 0,\,\|w\|_{0}\leq M, where \|w\|_{0}:=\sum_{n}\mathbb{I}(w_{n}>0) . Many algorithms in this direction have been proposed; yet an open question remains; how to extend them to non-parametric settings. The difficulty arises from the fact that the normalizing constants are not available in a general functional form without integrating out some of the randomness and performing truncations. Claici et al. (2020) proposed an alternative, variational view of coresets exploiting the machinery behind optimal transport theory ( Villani, 2003 ) . Recall that the p -Wasserstein distance between two probability measures \mu and \nu is defined as W_{p}(\mu,\nu)=\inf_{\gamma\in\Pi(\mu,\nu)}\int\|x-y\|_{p}^{1/p}\,\gamma(\mathrm{d}x,\mathrm{d}y), the infimum being taken over the set of couplings \Pi(\mu,\nu) betweeen \mu and \nu . The idea is to introduce a variational family \Pi_{\theta} and to find a measure p_{\theta}\in\Pi_{\theta} that minimizes the p-Wasserstein distance with the likelihood p under the full data set, i.e. \min_{p_{\theta}\in\Pi_{\theta}}W_{p}\left(p_{\theta},\,p\right). (1) This was achieved by parametrizing the problem as finding a Lipschitz map T , so that given data y_{1},\dots,y_{N} and a subsample of it y^{*}_{1},\dots,y^{*}_{n} , T is obtained by solving \min_{T}W_{p}\left\{\widehat{p}\left[T(y^{*}_{1:n})\right],\,\widehat{p}\left(y_{1:N}\right)\right\}, where \widehat{p}

Read the complete text