Source-linked AI summary
Firefly Monte Carlo: Exact MCMC with Subsets of Data
Dougal Maclaurin, Ryan P. Adams
TL;DR
Large datasets make MCMC costly because evaluating every likelihood at every iteration is prohibitive. FlyMC uses auxiliary brightness variables and data subsets while preserving the exact full-data posterior, and experiments show substantial speedups over regular MCMC.
Problem
MCMC on large datasets is hindered by the repeated cost of evaluating all likelihood terms during iterative posterior updates.
Method
FlyMC introduces binary latent variables that mark data as bright or dark, allowing subset-based MCMC updates while preserving the true full-data posterior.
Results
FlyMC’s MAP-tuned algorithm queried 207 of 12,2214 likelihoods per iteration on average and achieved a speedup of more than 20 after burn-in.
Takeaways & Limitations
FlyMC provides an exact subset-based MCMC approach whose efficiency depends on obtaining likelihood lower bounds that collapse efficiently.
Takeaways & Limitations
Useful likelihood lower bounds can be difficult to obtain, and explicit resampling cannot mix faster than 1/α when each data point is visited only a fraction α of iterations.
Abstract
from arXiv · showhide
Markov chain Monte Carlo (MCMC) is a popular and successful general-purpose tool for Bayesian inference. However, MCMC cannot be practically applied to large data sets because of the prohibitive cost of evaluating every likelihood term at every iteration. Here we present Firefly Monte Carlo (FlyMC) an auxiliary variable MCMC algorithm that only queries the likelihoods of a potentially small subset of the data at each iteration yet simulates from the exact posterior distribution, in contrast to recent proposals that are approximate even in the asymptotic limit. FlyMC is compatible with a wide variety of modern MCMC algorithms, and only requires a lower bound on the per-datum likelihood factors. In experiments, we find that FlyMC generates samples from the posterior more than an order of magnitude faster than regular MCMC, opening up MCMC methods to larger datasets than were previously considered feasible.
1. INTRODUCTION.
Bayesian inference offers principled uncertainty and model control, but iterative inference methods often require repeated computations involving all data points. FlyMC addresses this challenge with an MCMC algorithm that exploits data subsets while preserving the exact full-data posterior.
- Motivation: Iterative Bayesian inference can require examining all data to evaluate parameter or latent-variable updates.Metropolis–Hastings evaluates posterior factors for each datum, while variational procedures may construct local approximations for each datum repeatedly.
- Related work: Recent subset-based variational methods provide approximation guarantees, whereas subset-based MCMC proposals approximate the ideal transition operator.The paper identifies a less settled situation for MCMC than for stochastic and online variational procedures.
- Contribution: FlyMC is an MCMC algorithm that exploits subsets of data to construct transition operators.It is introduced as a method aligned with efforts to reduce data usage in MCMC.
- Contribution: FlyMC leaves the true full-data posterior invariant by introducing Bernoulli latent variables that turn individual likelihood terms on or off.The latent variables alter computation without changing the marginal distribution of the parameters of interest.
- Contribution: FlyMC requires a collapsible lower bound for each likelihood term and can improve MCMC performance in wallclock time.The method’s practical requirement is stated alongside its potential computational benefit.
2. FIREFLY MONTE CARLO.
Firefly Monte Carlo augments the posterior with binary variables that turn individual likelihood terms on or off while preserving the exact marginal posterior over parameters. By using lower bounds and evaluating only active terms, it can make MCMC updates cheaper when most data points are dark.
- Motivation and scope: The method targets the bottleneck in conventional MCMC, where evaluating all N likelihoods at every iteration becomes costly for large datasets.The practical setting assumes likelihood evaluation over the full dataset is the computational bottleneck and that the data can remain in memory.
- Auxiliary-variable construction: FlyMC introduces one binary auxiliary variable z_n per datum and a strictly positive lower bound B_n(θ) satisfying 0 < B_n(θ) ≤ L_n(θ).The variables are conditioned on the parameters through Bernoulli distributions.
- Auxiliary-variable construction: The augmented joint distribution preserves the original marginal distribution over θ after the auxiliary variables are marginalized out.This is the basis for using the augmented Markov chain without changing the target posterior.
- Sparse likelihood evaluation: For a fixed configuration of {z_n}, only likelihood terms with z_n = 1 need to be evaluated; terms with z_n = 0 contribute their lower bounds.The factor for each datum uses L_n(θ) − B_n(θ) when z_n = 1 and B_n(θ) when z_n = 0.
- Sparse likelihood evaluation: When most z_n = 0, parameter updates use a minibatch-like subset of the data and avoid computing most true likelihoods.The resulting parameter transitions are cheaper, although all lower bounds must still be evaluated at each iteration.
- Efficient implementation: Convenient lower bounds, such as scaled Gaussian or other exponential-family forms, allow their full product to be computed efficiently using precomputed sufficient statistics.The bound product can be evaluated in O(1) time for each new θ when the sufficient statistics are available.
- Efficient implementation: FlyMC alternates conventional MCMC updates of θ conditional on the auxiliary variables with updates of the variables conditional on θ.Dark data can become bright through auxiliary-variable updates, after which their likelihoods are included in subsequent iterations.
3. IMPLEMENTATION CONSIDERATIONS.
FlyMC reduces likelihood evaluations by maintaining bright and dark data points while preserving valid MCMC updates. Its efficiency depends on tight, cheaply summarized lower bounds and resampling strategies that limit auxiliary-variable overhead.
- Choosing lower bounds: Tight lower bounds reduce the number of bright data points, lowering the cost of evaluating the joint posterior.Bounds should be tight where the posterior has most of its mass.
- Choosing lower bounds: The product of exponential-family lower bounds can be computed independently of N after precomputing sufficient statistics.For logistic regression, the bound product costs O(D2) per parameter value after a one-time setup.
- Algorithmic implementation: FlyMC’s joint-posterior calculation evaluates the prior and bound product, then applies bound-corrected likelihood factors only to bright data points.The implementation loops over data with z_n = 1 rather than evaluating every likelihood factor.
- Choosing lower bounds: With ξ = 1.5, fewer than 0.02 of data points are bright where 0.1 < L_n(θ) < 0.9.Bounds can be tightened further near an approximate MAP estimate.
- Sampling brightness variables: Explicit resampling updates a random fixed-size subset of brightness variables, but its mixing time cannot be faster than 1/α when the sampled fraction is α.It remains practical because mixing is usually limited by exploration of θ rather than z_n.
- Sampling brightness variables: Implicit resampling proposes brightness changes with tunable Bernoulli probabilities and evaluates likelihoods only for points proposed to change state.Reusing likelihoods for bright points permits setting q_b→d = 1 and tuning q_d→b near M/N.
- Data structures: Efficient storage of brightness variables must support Brighten, Darken, and indexed bright or dark-point retrieval in O(1) time.The structure also tracks the number of bright points.
4. EXPERIMENTS.
Across three datasets, models, and MCMC operators, FlyMC was evaluated against regular MCMC using untuned and MAP-tuned likelihood bounds. MAP-tuned FlyMC substantially improved computational efficiency, including 20-fold and 11-fold speedups in the reported experiments.
- Experimental setup: Three experiments compared regular MCMC with untuned and MAP-tuned FlyMC across logistic regression, softmax classification, and robust regression.The evaluations used MNIST, CIFAR-10, and organic photovoltaic molecular data with different parameter-update operators.
- Logistic regression: MAP-tuned FlyMC queried 207 of 12,2214 likelihoods per iteration on average after burn-in, yielding a speedup of more than 20 over regular MCMC.FlyMC mixed and burned in more slowly per iteration, but the reduction in likelihood evaluations produced the larger overall speedup.
- Experimental setup: Figure 4 compared convergence traces and average likelihood evaluations per iteration for tuned FlyMC, untuned FlyMC, and full-data MCMC across all three experiments.The comparisons used five runs per method and displayed one standard deviation around the mean.
- Robust sparse linear regression: The robust molecular regression experiment used slice sampling and found that MAP-tuned FlyMC substantially outperformed regular MCMC.The dataset contained 1.8 million molecules with 57 cheminformatic features each, and the likelihood used a Student-t distribution with ν = 4.
5. DISCUSSION.
FlyMC preserves the full-data posterior while reducing computation through auxiliary bright/dark data indicators and efficiently collapsing lower bounds. The main limitation is that useful lower bounds can be difficult to obtain, although empirical gains can offset slower mixing from the enlarged state space.
- Discussion: FlyMC introduces binary latent variables that mark data as bright or dark while preserving the true posterior after marginalization.Bright data contribute likelihood terms to parameter updates, whereas dark data are omitted from those updates.
- Discussion: Efficient FlyMC requires likelihood lower bounds that collapse in a computationally convenient way.The method can otherwise shift computational work from evaluating likelihoods to evaluating all bounds.
- Limitations and future work: Useful lower bounds may be difficult to obtain for many problems, motivating future work on automatically constructing them for a wider class of models.The authors connect this direction to developments in black-box variational methods.
- Limitations and future work: Although auxiliary variables enlarge the state space and can slow mixing, experiments showed that faster per-transition computation more than offset this effect.The authors identify efficient data structures and improved latent-variable update schemes as additional future-work directions.