Source-linked AI summary
Speeding Up MCMC by Efficient Data Subsampling
Matias Quiroz, Robert Kohn, Mattias Villani, Minh-Ngoc Tran
TL;DR
MCMC is costly for large datasets, so the paper asks whether likelihood computation can be reduced through data subsampling without excessive posterior error. It introduces control-variate-based Subsampling MCMC with pseudo-marginal sampling, and reports large speedups over full-data MCMC while outperforming other subsampling approaches.
Problem
MCMC remains time-consuming for large datasets, motivating scalable inference methods.
Method
Subsampling MCMC estimates the log-likelihood from a small random data fraction using control variates and uses the estimate in a pseudo-marginal sampling scheme.
Results
The method documents large speedups relative to MCMC using all data and outperforms other recent subsampling approaches.
Takeaways & Limitations
The perturbed posterior error is extremely small in the applications, including when using a small subsample.
Takeaways & Limitations
One compared approach is not an MCMC method, making credible regions infeasible to obtain in practice.
Abstract
from arXiv · showhide
We propose Subsampling MCMC, a Markov Chain Monte Carlo (MCMC) framework where the likelihood function for $n$ observations is estimated from a random subset of $m$ observations. We introduce a highly efficient unbiased estimator of the log-likelihood based on control variates, such that the computing cost is much smaller than that of the full log-likelihood in standard MCMC. The likelihood estimate is bias-corrected and used in two dependent pseudo-marginal algorithms to sample from a perturbed posterior, for which we derive the asymptotic error with respect to $n$ and $m$, respectively. We propose a practical estimator of the error and show that the error is negligible even for a very small $m$ in our applications. We demonstrate that Subsampling MCMC is substantially more efficient than standard MCMC in terms of sampling efficiency for a given computational budget, and that it outperforms other subsampling methods for MCMC proposed in the literature.
1. Introduction
MCMC remains time-consuming for large datasets, motivating scalable algorithms that reduce computation while preserving accurate posterior sampling. The paper develops subsampling methods using control variates and pseudo-marginal schemes, analyzes their perturbation error, and reports improved efficiency over full-data and other subsampling MCMC methods.
- Motivation: MCMC remains time-consuming, creating a need for scalable algorithms for inference with large datasets.
- Method: Subsampling MCMC uses a small random data fraction to estimate the log-likelihood unbiasedly within a pseudo-marginal sampling scheme.The likelihood estimate is bias-corrected before constructing the perturbed posterior.
- Method: The method combines parameter-expanded and data-expanded control variates to reduce variability in log-likelihood estimates.The approximations use Taylor expansions around a parameter-space reference value and the nearest data-space centroid.
- Error analysis: The perturbed posterior has total variation error O(n^-2) when the full-data MLE is available.
- Error analysis: The proportional posterior error is considerably smaller in regions of high posterior concentration, and feasible error estimators are extremely small in the examples.
- Results: The pseudo-marginal scheme produces large speedups over using all data and outperforms other recent subsampling approaches.The paper also describes the scheme as straightforward to implement and tune.
2. Sampling-based Log-likelihood Estimators
The paper estimates a decomposed log-likelihood from a subsample, using control variates to reduce variance and computational cost. It develops parameter- and data-expanded control variates, with their accuracy depending on data structure and dimension.
- Likelihood estimation: The log-likelihood is represented as a sum of observation-level contributions, making subsampling equivalent to estimating a finite-population total.The framework also applies when each term corresponds to all measurements from one subject or to time-series blocks.
- Sampling design: Simple random sampling can have high variance because observations contribute unequally, while probability-proportional-to-size sampling requires costly size measures.Control variates instead make population elements more homogeneous so simple random sampling becomes more efficient.
- Control variates: The proposed control variates reduce estimator cost to substantially less than O(n) by approximating each log-likelihood contribution.Their dependence on n arises because the approximations typically improve as more data become available.
- Variance and limitations: With control variates, the log-likelihood estimator can maintain bounded variance with a much smaller subsample than simple random sampling, whose optimal scaling can be m = O(n^2).The paper also warns that data-expanded control variates eventually suffer from the curse of dimensionality, while performance depends on proximity to a lower-dimensional manifold.
- Data-expanded control variates: Data-expanded control variates cluster observations and use local second-order Taylor expansions around fixed centroids, with K much smaller than n.The resulting approximation is quadratic in the data covariates and requires exact likelihood contributions only at the centroids.
- Control-variate types: Parameter-expanded control variates Taylor-expand contributions around a reference parameter, while data-expanded control variates expand with respect to the observations.The paper analyzes both approaches and notes that parameter-expanded covariates have better asymptotic properties under the stated assumptions.
3. Subsampling MCMC Methodology
Subsampling MCMC uses a bias-corrected subsampled likelihood within pseudo-marginal schemes, while correlated likelihood estimates and control variates control perturbation error. Theoretical rates characterize how error changes with subsample size and dataset size, but efficiency can conflict with accuracy in some regimes.
- Pseudo-marginal sampling: The method estimates the log-likelihood from a random subsample, approximately bias-corrects the estimate, and uses it in pseudo-marginal MCMC targeting a perturbed posterior.If the likelihood estimator is unbiased, the marginal invariant distribution is the true posterior; otherwise it is a perturbed posterior.
- Assumptions and limitations: The theory does not rely on normality of the difference estimator, although one variance estimate assumes knowledge that is impractical because it requires the entire dataset.This distinction separates the general theoretical result from a computationally unrealistic variance assumption.
- Variance control: Control variates reduce log-likelihood-estimator variance, while correlated pseudo-marginal schemes permit a larger variance in the estimated log-likelihood.The paper emphasizes that the combined use of both mechanisms makes the method scale well.
- Error analysis: The perturbation error is O(m^-2) for fixed n and can decrease rapidly with n under the theorem’s subsample-size choices.The results are derived under regularity conditions and include asymptotic bounds for perturbed quantities.
- Error analysis: For m = O(n^1/2), the stated example gives perturbation error of order O(n^-2).The theorem’s rates depend on how the subsample size scales with n.
- Practical tradeoffs: When control variates are based on a posterior mode, the optimal subsample size can decrease with n, creating a tradeoff between efficiency and accuracy.The paper suggests estimating the mode with stochastic-gradient methods or a fixed subsample to avoid handling all observations.
- Practical tradeoffs: If the reference subset has size e_n = n^κ and the target variance is O(1), the optimal subsample exponent is α = 2 − 3κ, with decreasing errors only when κ < 2/3.For κ ≥ 2/3, the optimal m decreases with n and the errors increase with n.
- Error estimation: The paper gives analytical and practical approaches for estimating proportional error in the perturbed likelihood and posterior.It reports that perturbed-posterior error can be much smaller than perturbed-likelihood error, while the practical variance assumption may require the full dataset.
4. Applications
The applications evaluate Subsampling MCMC across logistic-regression and AR-process examples, comparing pseudo-marginal variants with standard MCMC and competing subsampling methods. Correlated and block pseudo-marginal schemes achieve substantial computational advantages while maintaining accurate posterior approximations.
- Experimental design: The experiments compare proposed pseudo-marginal schemes with standard MH and competing subsampling methods across logistic-regression and AR-process models.The benchmark includes firm-bankruptcy, HIGGS, Cover Type, and two AR(1) models.
- Logistic regression: Correlated and block pseudo-marginal schemes significantly outperform independent PM and full-data MH in Relative Computational Time for the bankruptcy example.Relative Computational Time is defined as CT_MH/CT_A, while Relative Inefficiency is defined as IF_A/IF_MH.
- Logistic regression: The block-correlated and correlated PM samplers produce very small posterior bias, with proportional approximation error −0.01 for both methods and −0.0001 for standard PM.The corresponding marginal posterior density estimates are compared with the exact MH approach.
- AR-process comparison: Across the AR-process comparisons, many alternative subsampling approaches are no more efficient than full-data MH, whereas correlated PMs provide significant speedups.The proposed PM methods and the confidence sampler with proxies are identified as the only viable subsampling approaches in these experiments.
- AR-process comparison: The PM algorithms and confidence samplers provide excellent posterior approximations, with perturbation error less than 10^-6 for all methods in the AR examples.Firefly Monte Carlo is reported as highly inefficient in this example, and no effective sample was obtained for model M2.
5. Conclusions and Future Research
The paper develops Subsampling MCMC using unbiased, efficient log-likelihood estimates from a small data subset and shows that posterior perturbation can remain very small. Its experiments report substantial speedups over full-data MCMC and better performance than other subsampling approaches, while extensions support efficient gradient-based proposals.
- The framework estimates the log-likelihood unbiasedly and efficiently using only a small random fraction of the data, producing a pseudo-marginal scheme targeting a slightly perturbed posterior.Two correlated sampling schemes are used to improve Markov-chain mixing.
- The method provides feasible estimators of perturbed-posterior error, which is empirically extremely small in the examples.The error is assessed using statistics of absolute proportional error from draws of the perturbed posterior.
- Taking m = O(n) yields perturbed-posterior error O(n^-2) when the MLE is based on all data, with a corresponding result for an MLE based on a subset.The paper also reports that posterior perturbation is much smaller in high-concentration regions than the likelihood perturbation.
- The experiments document large speedups relative to full-data MCMC and show that Subsampling MCMC outperforms other recent subsampling approaches.Figure 5 summarizes relative computational time using minimum, median, and maximum values across parameters.
- A Metropolis-within-Gibbs variant provides exact derivatives of the estimated log-likelihood, enabling Gibbs-, Laplace-, and Langevin-based proposals that can scale with the number of unknowns.The paper also identifies applications where each data-unit density is expensive to compute, including models with latent-variable integrals.
S1.4. Computing the data expanded control variates for the GLM class. We now
The section develops control variates for generalized linear models and notes that the construction extends beyond GLMs under a twice-differentiability condition.
- Control variates are derived by expanding around z for generalized linear models.
- The method applies more widely whenever ℓ(z; θ) is twice differentiable with respect to z.
- Categorical responses and covariates are treated as continuous in the construction.
- The section illustrates the construction using a univariate GLM with an invertible link function.
- The approximation is typically straightforward to derive even for models with vector-valued Ψ outside the GLM class.
S2. Proofs
The proofs establish asymptotic results for the subsampling estimators and perturbed posterior, using moment bounds, concentration arguments, and exponential-moment decompositions.
- The central limit theorem yields asymptotic normality for the subsampling estimator of the difference quantity and the log-likelihood.
- The n-asymptotic analysis considers subsample sizes of the form m = Bn^α for constants B > 0 and α > 0.
- The proof of the assumptions and main theorem relies on posterior regularity, eigenvalue bounds, and moment-generating-function arguments.
- Lemma 6 combines exponential-moment expansions for three random variables, with the slowest-decaying error term controlling the result.
- The proof treats both normality-based and general cases, with the latter using Bernstein’s inequality rather than a normality assumption.
- The second error term dominates the first and determines the resulting order bound.
S3. Checking the assumptions for generalized linear models
The section verifies the required assumptions for generalized linear models and related likelihood forms under smoothness, convexity, and eigenvalue conditions.
- The assumptions are verified for generalized linear models using an approach related to Chen’s treatment of exponential families.
- The generalized likelihood setup assumes smooth B_i functions with positive semidefinite second derivatives and positive definite aggregate curvature.
- The same assumptions imply the stated regularity conditions for the posterior sequence.
- A lower bound on the minimum eigenvalue of B^(n)(θ) supports satisfaction of the relevant regularity condition.
- The verification extends to likelihoods proportional to −k_i(x^Tθ) when k_i has a continuous third derivative and nonnegative second derivative.