Adaptive random neighbourhood informed Markov chain Monte Carlo for high-dimensional Bayesian variable selection

Xitong Liang, Samuel Livingstone, Jim E. Griffin

TL;DR

This paper introduces a new, efficient Markov Chain Monte Carlo (MCMC) algorithm called PARNI for high-dimensional Bayesian variable selection. PARNI significantly improves upon existing methods by intelligently combining adaptive neighbourhood construction with informed proposal strategies, leading to faster and more reliable inferences, especially when dealing with a massive number of potential predictors.

What Problem Does This Paper Address?

In statistical modeling, especially with large datasets, identifying the most relevant predictor variables (variable selection) is crucial for building accurate and interpretable models. Bayesian Variable Selection (BVS) offers a principled way to do this by quantifying uncertainty in model selection. However, traditional BVS methods using Markov Chain Monte Carlo (MCMC) can become computationally very expensive and slow to converge when the number of potential predictors ($p$) is large (high-dimensional settings). Existing advanced MCMC techniques, while improving on basic methods, still face challenges with mixing time and computational cost. This paper aims to develop a more efficient and robust MCMC framework that can handle these high-dimensional BVS problems effectively.

Methods

The authors propose a novel framework for constructing MCMC algorithms for high-dimensional discrete distributions, specifically for BVS. They unify existing methods like Zanella's locally informed sampler and Griffin et al.'s Adaptively Scaled Individual Adaptation (ASI) sampler within this framework. Their core contribution is the Adaptive Random Neighbourhood Informed (ARNI) sampler, which combines the strengths of ASI (efficient neighbourhood construction) and locally informed samplers (intelligent proposal within a neighbourhood).

To address computational costs, they introduce the Point-wise Adaptive Random Neighbourhood Informed (PARNI) sampler. PARNI implements ARNI by sequentially proposing changes to individual variables within a neighbourhood, drastically reducing the computational burden compared to block-wise proposals. Key aspects include:

  • Adaptive Random Neighbourhood Construction: Similar to ASI, it intelligently builds neighbourhoods that are likely to contain good models.
  • Locally Informed Proposals: Within these neighbourhoods, it uses informed proposals (based on local posterior information) to guide the search, improving efficiency in correlated settings.
  • Point-wise Implementation (PARNI): This crucial step breaks down the neighbourhood proposal into a sequence of single-variable changes, making it computationally tractable even for very large $p$.
  • Adaptation Schemes: PARNI employs adaptive tuning of parameters (like the thinning parameter $\omega$) using Robbins-Monro (RM) and Kiefer-Wolfowitz (KW) schemes to ensure efficient convergence.

Datasets

The paper evaluates their proposed methods on both simulated and real datasets.

  • Simulated Data: Data is generated from a linear model with varying signal-to-noise ratios (SNR = 0.5, 1, 2, 3), sample sizes ($n$ = 500, 1000), and numbers of covariates ($p$ = 500, 5000, 50000). This setup is based on previous work by Yang et al. (2016).
  • Real Data: They use eight real datasets:
  • Tecator, Concrete, Boston Housing, Protein (moderate $p$).
  • PCR1, PCR2, PCR3 (from Lan et al., 2006, with $p$ = 22,575).
  • SNP (from Carbonetto et al., 2017, with $p$ = 79,748).

Key Insights and Ideas

  • Unifying Framework: The paper demonstrates that several advanced MCMC samplers for BVS can be viewed as special cases of a more general "random neighbourhood sampler" framework, providing a unified perspective.
  • Synergy of Neighbourhood Construction and Informed Proposals: The ARNI sampler shows that combining intelligent neighbourhood selection (like ASI) with informed proposals within those neighbourhoods is a powerful strategy for efficient exploration of the posterior.
  • Computational Efficiency via Point-wise Updates: The PARNI sampler's key innovation is its point-wise implementation, which dramatically reduces computational cost without sacrificing exploration ability, making it suitable for extremely high-dimensional problems.
  • Adaptation is Crucial: The effectiveness of PARNI relies heavily on its adaptive tuning mechanisms (RM and KW) for parameters like $\omega$, which help it converge to optimal settings.
  • High-Dimensional Performance: The PARNI samplers consistently outperform existing methods like Add-Delete-Swap and ASI in terms of mixing speed and accuracy, especially as the number of predictors ($p$) increases.

Key Results

  • Improved Performance: The PARNI sampler (both RM and KW versions) demonstrates significantly faster mixing and better convergence compared to Add-Delete-Swap and ASI, particularly in high-dimensional settings ($p$ = 50,000 and 79,748).
  • Accuracy: For large $p$ datasets, PARNI achieves substantially lower mean squared errors for estimating posterior inclusion probabilities, sometimes by orders of magnitude compared to Add-Delete-Swap.
  • Computational Efficiency: While informed proposals can be computationally expensive, the point-wise implementation of PARNI makes it efficient enough for practical use in very large $p$ scenarios.
  • Robustness of Adaptation: The Kiefer-Wolfowitz adaptation scheme for $\omega$ is shown to be robust, converging to optimal values across various datasets and initial settings.

Limitations and Future Work

  • Isolated Modes: The authors acknowledge that PARNI, like other sequential samplers, might still struggle to move across very low probability regions or highly isolated modes in the posterior. The original ARNI scheme, with its larger jumps, might be better for exploring such scenarios, albeit at a higher computational cost.
  • Future Directions:
    • Investigating ways to improve mode-jumping capabilities, possibly by constructing larger blocks or using techniques from sequential Monte Carlo methods.
  • Extending the framework to generalized linear models and other flexible Bayesian variable selection models.
  • Exploring the application of random neighbourhood samplers beyond variable selection.
  • Developing more efficient methods for handling the computational costs associated with informed proposals, potentially by leveraging gradient information.

Summary updated

Abstract

We introduce a framework for efficient Markov chain Monte Carlo algorithms targeting discrete-valued high-dimensional distributions, such as posterior distributions in Bayesian variable selection problems. We show that many recently introduced algorithms, such as the locally informed sampler of Zanella (J Am Stat Assoc 115(530):852–865, 2020), the locally informed with thresholded proposal of Zhou et al. (Dimension-free mixing for high-dimensional Bayesian variable selection, 2021) and the adaptively scaled individual adaptation sampler of Griffin et al. (Biometrika 108(1):53–69, 2021), can be viewed as particular cases within the framework. We then describe a novel algorithm, the adaptive random neighbourhood informed sampler, which combines ideas from these existing approaches. We show using several examples of both real and simulated data-sets that a computationally efficient point-wise implementation (PARNI) provides more reliable inferences on a range of variable selection problems, particularly in the very large p setting.
BibTeX
@article{liang2022adaptive,
  author = {Xitong Liang and Samuel Livingstone and Jim E. Griffin},
  title = {{Adaptive random neighbourhood informed Markov chain Monte Carlo for high-dimensional Bayesian variable selection}},
  journal = {Stat. Comput.},
  year = {2022},
  doi = {10.1007/s11222-022-10137-8},
}
Figure