TL;DR
This paper introduces a "two-stage Metropolis-Hastings" algorithm designed to make Markov Chain Monte Carlo (MCMC) methods computationally feasible for "tall data" (where the number of observations vastly exceeds the number of predictors). The core idea is to use a cheap, approximate likelihood to quickly filter out unlikely parameter proposals before resorting to expensive, exact likelihood calculations, significantly speeding up MCMC inference.
What Problem Does This Paper Address?
Bayesian inference, particularly using MCMC methods like Metropolis-Hastings (MH), is powerful for complex models. However, its computational cost scales poorly with dataset size. For "tall data" (n >> p), where n is the number of observations and p is the number of predictors, the repeated evaluation of the likelihood function over the entire dataset in each MCMC iteration becomes prohibitively expensive, rendering standard MCMC methods infeasible. Existing solutions like parallelization, subsampling, and consensus MCMC have their own limitations or complexities.
Methods
The paper proposes a Two-Stage Metropolis-Hastings (MH) algorithm. The key innovation is a two-stage proposal acceptance process:
- First Stage (Approximate Likelihood): A proposed parameter value is first evaluated using a computationally cheap approximate likelihood. This acts as a quick filter.
- Second Stage (Exact Likelihood): Only if the proposal passes the first stage (i.e., is deemed potentially acceptable by the approximate likelihood) is the full, exact likelihood computed. The proposal is then accepted or rejected based on the standard MH acceptance probability using the exact likelihood.
This approach aims to avoid expensive exact likelihood calculations for the vast majority of proposals that would be rejected anyway, thereby drastically reducing computational cost. The authors also discuss how this can be integrated into the Consensus Monte Carlo framework.
Datasets
The methods were applied to three datasets:
- Portuguese bank marketing data: Approximately 40,000 observations.
- Freddie Mac loan data: Approximately 2.3 million observations.
- Simulated dataset: A large dataset with 10^6 observations for a Bayesian multivariate adaptive regression splines (BMARS) model.
Key Insights and Ideas
- The "cheap filter" principle: The core insight is that most proposed MCMC steps are rejected. By using a fast, approximate likelihood to pre-screen proposals, we can avoid the computational bottleneck of the exact likelihood for most steps.
- Balancing speed and accuracy: The two-stage approach offers a trade-off. While the first stage uses an approximation, the final acceptance decision relies on the exact likelihood, ensuring the method still samples from the correct posterior distribution.
- Generality: The two-stage MH framework is presented as a general method applicable to any model where a computationally cheap likelihood approximation can be constructed.
- Subsampling effectiveness: The paper demonstrates that even small subsamples (e.g., 5-10% of data) can be effective for approximating the likelihood in the first stage, leading to significant speedups without sacrificing accuracy.
Key Results
- Speedup: The two-stage MH algorithm consistently demonstrated significant speed improvements over standard MH and other methods like subsampling and consensus MCMC across various applications. For example, in the Freddie Mac logistic regression, the two-stage method was faster than parallelized MH and consensus. In the BMARS application, it achieved a 30%-40% reduction in time.
- Accuracy: Posterior densities from the two-stage method were shown to be virtually indistinguishable from those obtained by standard MH, indicating no loss of inferential accuracy.
- Efficiency: Metrics like REDPM (Relative Effective Draws Per Minute) showed the two-stage method often outperformed consensus and standard MH, especially when thinning was applied.
- Robustness: The two-stage method showed robustness to subsample size in some applications, performing well even with very small percentages of data.
Limitations and Future Work
- Subsample Size Selection: The paper highlights that selecting the optimal subsample size for the approximate likelihood is a key question. Too small a subsample can lead to decreased acceptance rates, requiring adjustments to proposal variances, which can increase autocorrelation.
- Likelihood Approximation Quality: The effectiveness of the two-stage method depends on the availability of a computationally cheap and accurate likelihood approximation. Poor approximations can lead to proposals being rejected in the second stage even if they are good candidates, or vice-versa.
- Future Work: The authors suggest extending the method to handle more complicated likelihoods and exploring better, yet still computationally cheap, likelihood approximations. They also envision applying it to even larger datasets that might not fit into RAM.
Summary updated