Bayesian inference on large datasets is slow because every step of a Markov chain Monte Carlo (MCMC) sampler, the standard tool for drawing samples from a posterior distribution, has to evaluate the likelihood of every data point. A coreset avoids this by replacing the full dataset with a small weighted subset of $M$ points, so each step costs $O(M)$ instead of $O(N)$. Current methods split the job into two stages, the way engineers split network resource allocation into a discrete stage and a continuous stage. First they choose which points to keep, usually uniformly at random. Then they tune the points' weights continuously. The weakness is the same in both fields: the first stage never learns what the second stage discovers. When a few unusual, influential points are missing from the random subset, no amount of weight tuning recovers them.
We propose to close that loop with a cheap feedback signal. The MCMC draws used to tune weights in Coreset Markov chain Monte Carlo can also estimate, for any point outside the coreset, how much the posterior approximation would improve if that point were given a small weight. Operations researchers call this kind of quantity a "price" or reduced cost. The sampler periodically prices a small random pool of outside points. It inserts the best-priced points at weight zero and evicts points whose weights have been driven to zero. Because points enter and leave only at zero weight, the sampler's target distribution never jumps.
Core Claim
Discrete coreset membership can be updated during sampling, at a cost of a few likelihood evaluations per candidate. The update uses the same covariance estimate that already drives the continuous weight updates. On models where uniformly chosen points are a poor basis for the likelihood, this should reach a given posterior accuracy with a markedly smaller coreset and fewer total likelihood evaluations than static Coreset MCMC. On simple low-dimensional models it should give no gain, and we will report that honestly.
The pricing rule follows from the KL-gradient identity that Coreset MCMC uses. Write $\ell_n(\theta) = \log p(x_n \mid \theta)$ for the log-likelihood of point $n$, $w$ for the coreset weights, $S$ for the current coreset, and $p_w$ for the coreset posterior. The gradient of the divergence $D_{\text{KL}}(p_w \| p)$ with respect to weight $w_n$, evaluated at $w_n = 0$ for a point not in $S$, is
$$ g_n \;=\; \mathrm{Cov}_{p_w}\!\Big(\ell_n(\theta),\; \textstyle\sum_{m \in S} w_m \ell_m(\theta) - \sum_{i=1}^{N} \ell_i(\theta)\Big). $$
A strongly negative $g_n$ means the current coreset badly underexplains the variation in point $n$'s likelihood across the posterior, so adding point $n$ helps. Estimating $g_n$ needs only $\ell_n$ at the $K$ current chain states. The full-data residual term is already estimated from a subsample in Coreset MCMC, so it can be reused.
Research Program
The algorithm keeps Coreset MCMC's structure: $K$ parallel chains target $p_w$, and ADAM updates $w$ using the covariance identity. Every $T$ iterations we add a pricing step. We draw $C$ candidate indices uniformly from outside $S$, compute $\ell_n$ at the $K$ chain states for each candidate, and form $\hat g_n$. Candidates whose $\hat g_n$ is below a threshold enter $S$ at weight zero. ADAM is then free to raise their weights. Points whose projected weight has stayed at zero for a window of updates are evicted to keep $|S| \le M$. The pricing step costs $CK$ likelihood evaluations, and every one of them is counted against the method's budget.
The two-stage-optimization lens supplies the design, not the analogy alone. The mm-wave access network method in Joint Optimization of User Association and Resource Allocation for Millimeter-Wave Integrated Backhaul and Access Network and the edge-computing method in Joint Offloading and Charge Cost Minimization in Mobile Edge Computing both fix discrete assignments and then optimize continuous variables. The second of these adds a crude feedback step: it assumes everything is offloaded, then reverts unprofitable tasks. Our eviction rule is the sampling counterpart of that revert step. Our insertion rule adds what those methods lack, a price for discrete choices computed from the continuous stage's current state. Neur2SP uses a learned surrogate of the second stage to steer the first. We need no surrogate, because the second-stage sensitivity is available exactly, in expectation, from the chains.
The analysis has three parts. The first concerns stability. Inserting and removing points at zero weight means the sequence of targets $p_w$ changes only through the continuous weights, which matters given the learning-rate sensitivity already reported for Coreset MCMC. We will check empirically that chain diagnostics do not degrade around swap times. The second concerns estimator quality. With $K$ draws, $\hat g_n$ has variance of order $1/K$, the usual rate for a sample covariance. We will measure how well the ranking by $\hat g_n$ agrees with an oracle ranking obtained by refitting with each candidate added. The third concerns budget scaling: how total evaluations to reach a target accuracy depend on $C$, $T$, and $M$.
Baselines
The naive reference point is uniform-subset Coreset MCMC with a larger coreset. We give static Coreset MCMC a coreset size $M'$ chosen so that its total likelihood evaluations match ours, pricing cost included. This tests the obvious objection that the pricing budget would be better spent on more random points. Beating it means lower posterior error at equal total evaluations, across at least the two harder benchmarks.
The strongest existing method is Coreset Markov chain Monte Carlo itself, run with the authors' configuration, the same kernel (slice sampling or HMC), the same $K$, and the same ADAM schedule tuned on an identical grid for both methods. The paper reports that it trains coreset weights 2 to 10 times faster than QNC on the Flight Delay benchmark and improves ESS per second over standard subsampling MCMC by roughly two orders of magnitude. No reported numerical KL or moment-error result was found on Lacuna for Coreset MCMC on Bikeshare or sparse regression, so we will produce those reference numbers ourselves.
We also compare against Fast Bayesian Coresets via Subsampling and Quasi-Newton Refinement (QNC). QNC is the cleanest example of selection fully decoupled from refinement, and its authors report that RBF regression needs much larger coresets. On a synthetic Gaussian location model they report finishing in seconds while sparse variational inference took over an hour. We include Control variates for stochastic gradient MCMC (SGLD-CV) as the strongest non-coreset scalable sampler at the same evaluation budget. No reported numerical result was found on Lacuna for its Covertype log-predictive density.
The key ablation is random swaps. It uses the same insertion and eviction schedule and the same $C$ and $T$, but inserts candidates chosen at random instead of by price. This isolates whether the price, rather than mere membership churn, produces any gain. A second ablation uses eviction only, with no insertion.
Why not just…?
Why not just use a bigger random coreset? This is the real threat. QNC proves that uniform subsets of size proportional to $d \log N$ suffice for common exponential families, so on low-dimensional GLMs we expect priced swaps to tie this baseline. The question is settled by the matched-budget comparison above. If static Coreset MCMC with $M'$ matches us on RBF and sparse regression too, the idea has failed and we will say so.
Why not choose points once, up front, by an importance score such as leverage at the MAP estimate? This is cheap and plausible. Its weakness is that a single-mode score inherits the fragility that SGLD-CV and Firefly Monte Carlo concede for multimodal or heavy-tailed posteriors, where MAP-centred quantities stop being representative. No reported result was found on Lacuna for MAP-based coreset selection on these benchmarks. We therefore run it as an additional baseline, including on the heavy-tailed Cauchy-prior logistic regression from QNC. There, posterior-averaged prices should beat mode-based scores if they are going to beat them anywhere.
Why not learn inclusion probabilities with policy gradients, as in Probabilistic Bilevel Coreset Selection? That method relaxes membership to Bernoulli probabilities over all $N$ points. It updates them with a forward-only gradient estimator, and each update requires training to near-convergence. It was built for deterministic deep learning and never interfaced with a sampler. In our setting, the covariance identity gives a direct, lower-variance estimate of the same marginal benefit, with no inner retraining and no length-$N$ probability vector. We will include a policy-gradient variant at matched budget on the Bikeshare benchmark ($N \approx 15{,}000$), where it is affordable.
Proposed Experiments
The benchmarks follow the cited work. From Coreset MCMC we use Flight Delay ($N \approx 98{,}000$), Bikeshare, and synthetic sparse regression. From QNC we use RBF regression and heavy-tailed Cauchy-prior logistic regression. Covertype ($N = 581{,}012$), used for SGLD-CV, is our largest test. For each benchmark we build a reference posterior once with long full-data MCMC. The metrics are relative error of the posterior mean and covariance against the reference, a two-moment Gaussian KL estimate, and ESS per second. The headline measure is total likelihood evaluations needed to reach a fixed error, swept over $M$.
Three checks are decisive. First, on RBF and sparse regression at matched total evaluations, priced swaps must beat both static Coreset MCMC with $M'$ and the random-swap ablation. Second, the estimated prices must rank candidates in rough agreement with oracle refits, measured by rank correlation. If they do not, any gain is accidental. Third, on low-dimensional GLMs such as Flight Delay, we predict a tie, and a large win there would make us suspect a bookkeeping error in the budget. Finally, we will check chain stability around swap events using split-chain convergence diagnostics in windows before and after each swap.
References
- Coreset Markov chain Monte Carlo
- Joint Optimization of User Association and Resource Allocation for Millimeter-Wave Integrated Backhaul and Access Network
- Joint Offloading and Charge Cost Minimization in Mobile Edge Computing
- Neur2SP: Neural Two-Stage Stochastic Programming
- Fast Bayesian Coresets via Subsampling and Quasi-Newton Refinement
- Control variates for stochastic gradient MCMC
- Firefly Monte Carlo: Exact MCMC with Subsets of Data
- Probabilistic Bilevel Coreset Selection