Parallelizing MCMC via Weierstrass Sampler

1 Introduction

• Large-scale MCMC is challenged by expensive likelihood calculations, latent-variable updates, and worsening mixing as posteriors concentrate.Source: §1 · p. 1
• Independent subset chains bypass communication costs until combination and can mix faster because smaller-subset posteriors are effectively annealed.Source: §1 · p. 2
• Existing averaging and kernel-smoothing approaches perform adequately only in specialized settings and poorly in cases including higher dimensionality.The cited passage also identifies settings where large-sample Gaussian approximations are inadequate.Source: §1 · p. 2
• The proposed Weierstrass method combines independent subset MCMC chains to approximate full-data posterior draws.It is based on the independent product equation.Source: §1 · p. 2

2 Motivation

• For conditionally independent observations partitioned into subsets, the full-data posterior is related to the product of subset posterior densities.The method uses the independent product equation as its starting point.Source: §2 · pp. 2–3
• Kernel density estimation can require sample sizes that grow exponentially with parameter dimension to maintain approximation accuracy.Source: §2 · p. 3
• Under the product form, small tail-area deviations among subset posterior approximations can yield poor full-posterior approximations.Source: §2 · p. 3
• For multimodal posteriors, averaging can collapse distinct modes and produce unreliable estimates.Source: §2 · p. 4
• The method is intended to perform well even when large-sample normality of the posterior does not hold.Source: §2 · p. 4
• The Weierstrass sampler applies a transform to subset densities and directly samples from transformed densities rather than estimating them from subset draws.The authors state that this avoids inheriting problems of kernel smoothing.Source: §2 · p. 4

3 Preliminaries

• Under the stated smoothness and finite-variance kernel conditions, the Weierstrass approximation is proper and its total-variation error has a bound controlled by the bandwidths.The result is stated for one dimension and extended to multivariate distributions, where kernel variances are replaced by covariance matrices.Source: §3 · pp. 5–6
• For multivariate posteriors, the error bound depends on the sum of the kernel covariance traces across subsets.The result applies under the stated multivariate smoothness and second-order kernel conditions.Source: §3 · p. 6
• The tuning parameters can be chosen independently of sample size because the error-bound constants converge in probability as sample size increases.The passage describes the constants as varying little with sample size and converging to constants in probability.Source: §3 · p. 6

4 Weierstrass refinement sampling

• The sampler treats subset parameters as latent variables and updates the full-posterior draw using their average.A rough full-posterior approximation is first sampled, then plugged into a one-step Gibbs refinement.Source: §4 · pp. 6–7
• One Gibbs refinement step yields geometric improvement over an initial rough approximation under the theorem’s stated conditions.The initial approximation may come from Laplace or variational methods, and the result is stated to apply to multivariate distributions as well.Source: §4 · p. 7
• The authors report good performance even when the true posterior is high-dimensional, multimodal, and very non-Gaussian.The large-sample approximation is used only as a rough starting point and is then refined.Source: §4 · p. 7
• Each refinement draw can be fully parallelized because the draws are independent operations.The sampler uses subset posterior draws as components of the Gibbs update.Source: §4 · p. 7
• The tuning parameter Hi controls each subset posterior’s approximation error; its trace apparently must decrease as the number of subsets m increases, while Hi also determines Gibbs-sampler efficiency.Source: §4 · pp. 7–8

5 Weierstrass rejection sampling

• The Weierstrass rejection sampler uses subset posterior draws directly rather than averaging, avoiding the mode-misspecification issue associated with averaging.The motivation is particularly relevant for multimodal posteriors, where averaging subset draws can cause mode misspecification.Source: §5 · p. 9
• For multivariate posteriors, the rejection sampler accepts a subset draw according to a threshold involving bounded kernels across the other subsets.The multivariate result assumes second-order kernels bounded by a positive constant and gives a total-variation approximation bound.Source: §5 · p. 9
• The rejection sampler’s acceptance rate suffers from dimensionality in both the number of subsets and parameters, requiring the posterior-sample count to grow exponentially with those quantities.The passage discusses the rate for adequately small common bandwidths.Source: §5 · p. 10

5.1 Sequential rejection sampling

• The sequential scheme builds the joint posterior by combining subset marginal distributions and then proceeding through conditional distributions parameter by parameter.The number of sequential updates is bounded by p, the number of parameters.Source: §5.1 · pp. 11–12
• The parameter-wise sequential rejection scheme decomposes the whole sampling procedure into p one-dimensional steps, reducing the dimensionality curse while keeping the required sequential-step count low at p.Source: §5.1 · p. 11

6 Numerical study

• The numerical study compares single-chain MCMC, simple and inverse-variance-weighted subset averaging, Weierstrass samplers, kernel smoothing, and Laplacian approximation across logistic, binomial, and Gaussian-mixture models.Kernel smoothing is described as sensitive to bandwidth and kernel covariance at higher dimensions, so the study considers marginal subset-density combinations.Source: §6 · p. 13

6.1.1 Refinement property

• The refinement sampler quickly moved from its initial approximation to the truth in just 10 steps, and 10 steps appeared adequate to obtain a reasonably good result.No posterior distribution from a full MCMC was plotted because the sample size was too large to run a full MCMC.Source: §6.1.1 · p. 14

6.1.2 Approximation accuracy

• The simulation varies predictor correlation (ρ = 0 and 0.3) and sample size (n = 10,000 or 30,000), with p = 50 predictors, m = 20 subsets, and 50 synthetic data sets per (ρ,n) pair.Source: §6.1.2 · pp. 15–16

6.2 Weierstrass rejection sampling

• The rejection sampler uses draws from subsets directly rather than averaging, which may help preserve posterior modes; the study investigates this property.The passage motivates this potential advantage by noting that averaging might disrupt modes.Source: §6.2 · p. 17
• The binomial comparison assesses rejection sampling against other methods for marginal and joint-density approximation accuracy, including Weierstrass refinement and uncorrected rejection sampling.The section also presents posterior densities for independent predictors at ρ = 0 and ρ = 0.3, each with n = 30,000.Source: §6.2 · p. 17, Table 1 · p. 18, Figure 5 · p. 18

6.2.1 Mode exploration

• Weierstrass sequential rejection sampling correctly recognized posterior modes, while one false mode was also selected by single-chain MCMC.The comparison used a normal mixture model without label-switching moves to mimic settings without a specific multimodality solution.Source: §6.2.1 · p. 19, Figure 7 · p. 19

6.2.2 Approximation accuracy

• For moderate information (p = 0.1), all methods work fine; for inadequately informed data (p = 0.001), only kernel smoothing and Weierstrass rejection sampling perform appropriately.To match the posterior-density scale, the rejection sampler adopts an acceptance rate of 0.1%.Source: §6.2.2 · p. 20

6.3 Computation efficiency

• The computation-efficiency study examines how runtime varies with sample size and parameter or component count in logistic regression and mixture models, with 20 subsets.The text states that reducing sample size reduces computational time in most cases.Source: §6.3 · p. 20, Figure 9 · p. 21, Figure 10 · p. 21

7 Real data analysis

• The data contain around 200,000 observations and 40 attributes recoded into 176 predictors for predicting income above $50,000.The data are weighted census data from the 1994 and 1995 Current Population Surveys; the positive class is rare in the training set.Source: §7 · p. 22
• Because the sample is too large for usual MCMC software and the model is high-dimensional, the analysis illustrates parallelized algorithms and Laplacian approximation.It also limits kernel smoothing because of its sensitivity in the high-dimensional model.Source: §7 · p. 22
• The marginal Weierstrass rejection sampler is omitted from reported results because its performance is very similar to the marginal kernel combining algorithm.Prediction is assessed on two test sets, with positive predictions assigned when logit−1(E[xiβ]) exceeds 0.5.Source: §7 · p. 22
• For posterior inference, data were partitioned into 20 subsets, with 20,000 samples drawn per subset after 50,000 burn-in; the Weierstrass refinement sampler used 10 steps on 2,000 initial draws.Each step used 50 iterations to propose refined draws.Source: §7 · p. 22
• For the rare-positive training setting, Laplacian approximation may overfit and a non-Gaussian posterior can lead to low accuracy in predicting positive cases for most methods.The analysis also reports that all methods perform well on Test Set 2, which mimics the training-set ratio.Source: §7 · pp. 22–23

• The Weierstrass sampler contains two algorithms designed for different situations.Source: §8 · p. 23
• Compared with other methods in the same direction, the Weierstrass sampler has better approximation accuracy and chain mixing, with potentially faster speed.Source: §8 · p. 23
• The sampler seeks a balance between approximation accuracy and computational efficiency while facing the dimensionality curse.Source: §8 · p. 23
• The rejection sampler approximates the original MCMC and improves posterior-mode exploration in the numerical study.Source: §8 · p. 23
• In simulation, the sampler identifies all mixture components, removing problems of the original Gibbs sampler.Source: §8 · p. 23
• Future work includes asymptotic justification for marginal combining, which could help address dimensionality concerns for kernel density estimation and Weierstrass rejection sampling.Source: §8 · p. 23
• The authors propose exploring parallel tempering with multiple h values, since small h favors accuracy while large h supports exploration.Source: §8 · p. 23

• Theorem 1 is a special case of the more general result when α ≥ 2 and k = 2.Source: Proofs for preliminaries and Theorem 3 · pp. 26, 28
• Under the stated smoothness and kernel conditions, Theorem 1 establishes propriety and bounds the variation distance between the posterior and its approximation.Source: Proofs for preliminaries and Theorem 3 · pp. 26, 28
• For the asymptotic discussion, local asymptotic normality supports replacing subset posteriors with normal approximations, yielding a rough approximation for MCk/Ck+1.Source: Proofs for preliminaries and Theorem 3 · p. 28
• Theorem 3's proof rewrites g_i using the subset density and kernel-smoothed factors, then applies the same argument as Theorem 1 because the expression differs only at the ith term.Source: Proofs for preliminaries and Theorem 3 · p. 29

• For continuous density functions f and f0, Lemma 3 provides a bounded measurable set D for any p0 in (0, 1).Source: Proof of Theorem 2 · p. 29
• Lemma 5 establishes a minorization condition on bounded D when the kernel is fully supported on R; under condition (6), D can be R.Source: Proof of Theorem 2 · pp. 32–33
• Theorem 2 follows by combining the lemmas' set and transition-kernel results with Lemma 4.Source: Proof of Theorem 2 · p. 34