On the Computational Complexity of High-Dimensional Bayesian Variable Selection

Yun Yang; Martin J. Wainwright; Michael I. Jordan

Source-linked AI summary

On the Computational Complexity of High-Dimensional Bayesian Variable Selection

Yun Yang, Martin J. Wainwright, Michael I. Jordan

arXiv:1505.07925v1May 29, 2015math.STcs.LGstat.COstat.MEstat.ML

TL;DR

The paper asks whether statistically consistent Bayesian variable selection is also computationally tractable in high-dimensional regression. It analyzes a Metropolis-Hastings sampler, introduces a truncated sparsity prior, and proves conditions yielding both variable-selection consistency and rapid mixing. The result is a mixing time linear in the number of covariates up to a logarithmic factor, while posterior consistency alone need not imply rapid mixing.

Problem
The paper examines whether posterior concentration and variable-selection consistency are sufficient to guarantee efficient MCMC sampling in high-dimensional Bayesian regression.
Method
The paper analyzes a Zellner g-prior model with a truncated sparsity prior and a local Metropolis-Hastings random walk using spectral-gap and canonical-path arguments.
Results
The conditions guarantee Bayesian variable-selection consistency and rapid mixing, with mixing time linear in p up to a logarithmic factor.
Takeaways & Limitations
Posterior concentration can aid rapid-mixing guarantees, but computational efficiency requires stronger conditions than posterior consistency alone.
Takeaways & Limitations
Posterior consistency can coexist with exponentially slow Metropolis-Hastings mixing, and the discussion identifies intermediate-SNR behavior and extensions beyond linear regression as open directions.

Abstract

from arXiv · show

We study the computational complexity of Markov chain Monte Carlo (MCMC) methods for high-dimensional Bayesian linear regression under sparsity constraints. We first show that a Bayesian approach can achieve variable-selection consistency under relatively mild conditions on the design matrix. We then demonstrate that the statistical criterion of posterior concentration need not imply the computational desideratum of rapid mixing of the MCMC algorithm. By introducing a truncated sparsity prior for variable selection, we provide a set of conditions that guarantee both variable-selection consistency and rapid mixing of a particular Metropolis-Hastings algorithm. The mixing time is linear in the number of covariates up to a logarithmic factor. Our proof controls the spectral gap of the Markov chain by constructing a canonical path ensemble that is inspired by the steps taken by greedy algorithms for variable selection.

1 Introduction

The paper studies when Bayesian variable-selection posteriors in high-dimensional regression are statistically consistent and when the associated MCMC algorithms mix rapidly. It shows that posterior consistency alone may not ensure rapid mixing, while stronger conditions and a truncated sparsity prior can support both.

High-dimensional regression addresses p ≫ n by assuming that the response depends on only a small subset of covariates.
MCMC analysis focuses on mixing time, the iterations needed to approach stationarity, and distinguishes polynomially growing rapid mixing from exponentially growing slow mixing.
The paper studies a hierarchical Bayesian sparse-regression model with a Zellner g-prior and a local Metropolis-Hastings random walk motivated by shotgun stochastic search.
Truncating the prior support to exclude unrealistically large models yields conditions for posterior consistency and rapid mixing, with mixing time linear in p up to a logarithmic factor.
The analysis addresses computational complexity through spectral-gap arguments and canonical paths, while simulations illustrate the theory.
Posterior concentration can provide algorithmic benefits, but posterior consistency alone is not sufficient for rapid mixing.

2 Background and problem formulation

This section formulates Bayesian variable selection over binary model indicators and introduces the local Metropolis-Hastings chains used to sample model space. It then defines mixing-time efficiency through convergence to stationarity and its dependence on p and n.

2.1 Variable selection in the Bayesian setting: Variable selection seeks the support of the unknown regression vector, or covariates whose absolute coefficients exceed a specified threshold.
2.1 Variable selection in the Bayesian setting: A Bayesian approach places a prior on binary inclusion vectors and uses the induced posterior to assess models and covariate inclusion probabilities.
2.1 Variable selection in the Bayesian setting: Each inclusion vector γ is also treated as a subset, with |γ| counting active covariates and set operations describing model comparisons.
2.2 MCMC algorithms for Bayesian variable selection: Metropolis-Hastings updates are local procedures that propose neighboring models and accept or reject moves using posterior and proposal probabilities.
2.2 MCMC algorithms for Bayesian variable selection: The analyzed neighborhood combines single-component flips with exchanges that remove one selected covariate and add one unselected covariate.
2.2 MCMC algorithms for Bayesian variable selection: The transition matrix assigns proposal-acceptance probabilities to neighboring states, zero probability to non-neighbors, and remaining probability to staying put.
2.3 Background on mixing times: For reversible chains, states form a weighted graph whose edge weights are π(γ)P(γ,γ′), supporting analysis through transition structure.
2.3 Background on mixing times: Mixing time measures iterations to reach an ε-distance from stationarity; rapid mixing is polynomial in p and n, whereas slow mixing is exponential.

3 Main results and their consequences

The paper separates posterior concentration from computational efficiency: consistency can coexist with exponentially slow MCMC mixing, while a truncated sparsity prior yields conditions for both consistency and rapid mixing.

Prior and assumptions: The truncated sparsity prior constrains model size to enable rapid MCMC mixing, although that constraint is unnecessary for Bayesian variable-selection consistency.The prior imposes |γ| ≤ s0 to rule out overly large models.
Posterior consistency: Under the stated assumptions and βmin-condition, the posterior concentrates on the true model with probability at least 1 − c2 p^−c3.The βmin-condition requires influential covariates to have sufficiently large signal magnitudes.
Posterior consistency: In high-SNR settings the posterior favors the true model, whereas in low-SNR settings it favors the null model.These regimes are characterized by distinct signal-to-noise conditions and posterior concentration targets.
Posterior versus computation: Posterior consistency does not guarantee rapid mixing: an example satisfies consistency while the Metropolis-Hastings mixing time grows exponentially in p.The paper attributes the slow mixing to posterior multimodality.
Rapid mixing: Under high- or low-SNR conditions, the Metropolis-Hastings chain has an upper-bounded mixing time, and after the corresponding burn-in it outputs the true model with high probability.The worst-case bound includes a logarithmic factor in p; a good initialization removes the n term from the upper bound.
Empirical consequences: Empirically, chains converge within 20p iterations in favorable settings, but correlated designs can produce poor convergence in the intermediate SNR regime.The correlated-design results indicate a slowly mixing regime characterized by n, p, and SNR.
Open question: The unresolved question is whether the slowly mixing regime reflects a fundamental limit on computationally efficient variable selection.The paper leaves this issue for future work.

4 Proofs

The proofs establish rapid mixing through spectral-gap bounds built from canonical paths, then use the same machinery for posterior consistency. The paths are constructed via a memoryless transition function that moves models toward the true model using greedy-style variable-selection steps.

Rapid mixing: The proof reduces rapid mixing to a lower bound on the spectral gap of a lazy Metropolis-Hastings chain.The lazy chain has nonnegative smallest eigenvalue, so mixing is controlled by its second-largest eigenvalue and spectral gap.
Rapid mixing: The proof combines canonical-path congestion bounds with posterior-ratio controls to complete the rapid-mixing theorem.The argument uses high-probability bounds and concludes with Gap(P) ≥ 1/(4c_p s0^2) as stated in the proof.
Canonical paths: The canonical path construction is inspired by greedy stepwise variable-selection procedures.The transition function directs models toward the true model using deletion or addition moves resembling backward and forward selection.
Canonical paths: A memoryless path ensemble assigns each state a unique route toward the central state through a transition function G.The next move from an intermediate state depends only on that state, and a strictly decreasing Hamming distance guarantees validity.
Transition function: Overfitted states remove uninfluential covariates, while underfitted states add influential covariates or use double flips when saturated.Each transition strictly decreases Hamming distance to the true model, by one for overfitted or unsaturated underfitted states and by two for saturated underfitted states.
Canonical paths: Paths between arbitrary model states are formed by joining their nonoverlapping routes to the central state, reversing one branch.The resulting ensemble has maximal path length at most 2s0 and yields a spectral-gap lower bound through congestion control.

5 Discussion

The paper connects Bayesian variable-selection consistency with computational efficiency for sparse high-dimensional regression. It also identifies slow mixing under failed selection and leaves broader models and sharpness of the mixing bound for future study.

Main implications: Under conditions guaranteeing Bayesian variable-selection consistency, the corresponding MCMC algorithm achieves rapid mixing.The discussion presents posterior contraction as having both statistical and algorithmic benefits for sampling from the posterior.
Open questions: The paper leaves the mixing behavior unresolved when Bayesian variable selection fails.Slow mixing is observed empirically in an intermediate SNR regime, but its theoretical explanation remains open.
Open questions: Future work includes extending the analysis beyond linear regression and determining whether the Theorem 2 mixing-time upper bound is sharp up to constants.The proposed extensions include high-dimensional nonparametric additive regression.

A Further details on Metropolis-Hastings

The appendix relates the Bayesian variable-selection formulation to penalized optimization and specifies the posterior under Zellner’s g-prior. Its penalty combines prior complexity control with an Occam penalty from integrating model parameters.

Bayesian–optimization connection: The MAP solution of the Bayesian variable-selection problem is equivalent to an ℓ0-penalized optimization problem.The equivalence is established under the specified Bayesian model.
Penalty structure: The hyperparameter κ controls the trade-off between including uninfluential covariates and requiring sufficient signal for influential covariates.Small κ can admit noise variables, whereas large κ requires stronger signal for posterior selection.
Posterior specification: Integrating out βγ and φ yields a closed-form marginal likelihood and posterior over the model indicator γ.The model space is restricted to models with |γ| ≤ s0, and the posterior is expressed up to a normalization constant.
Bayesian–optimization connection: The Bayesian penalty correspondence also links choices of λ to AIC, BIC, and high-dimensional BIC regimes.The stated correspondences are λ = 1 for AIC, λ = log n/2 for BIC, and λ = α log p for high-dimensional BIC.

A.2 Example of slow mixing

The slow-mixing example shows that an untruncated prior can produce exponentially slow Metropolis-Hastings mixing even when the statistical consistency conditions hold. The proof uses a conductance upper bound based on the isolated full model.

Counterexample: The untruncated prior yields mixing time exponential in n with probability at least 1/2 in the specified null-model example.The example sets p = n, g = p^(2α), and Y ∼ N(0, I_n), while satisfying the conditions of Theorem 1.
Conductance argument: The slow-mixing proof upper-bounds the spectral gap through the conductance of a reversible Markov chain.The argument uses 1 − λ2 ≤ 2ΦC and selects the full model as the relevant set.
Conductance argument: Under the single-flip transition rule, the full model has only its one-variable deletions as neighboring states.This restricted neighborhood limits the flow out of the full-model state used in the conductance bound.
Counterexample: The example completes the claimed slow-mixing result by combining posterior and transition-probability bounds.The preceding χ2 tail and exponential inequalities control the relevant posterior terms before the conductance conclusion.

B Proof of inequality (23a) in Lemma 4

Because γ differs from γ∗, the transition γ′ = G(γ) also differs from γ. The proof therefore separates into three disjoint cases, beginning with underfitted saturated models.

The transition function satisfies γ′ = G(γ) ≠ γ because γ ≠ γ∗.
The first case concerns models γ that are both underfitted and saturated.

B.1 Case γ is overfitted

In the overfitted case, the transition removes an uninfluential covariate while retaining all influential covariates. Posterior-ratio bounds are then obtained using projection properties, norm assumptions, and the chosen hyperparameter scaling.

The transition removes an uninfluential covariate ℓγ from γ, producing γ′ = γ \ {ℓγ}.
All influential covariates remain included in both Mγ and Mγ′.
The posterior probability ratio is bounded through Cauchy-Schwarz, non-expansiveness of projections, and the stated norm assumption.
The proof uses γ′ ⊂ γ together with bounds on R2 and the condition 4r s0 log p ≤ n.
The resulting posterior-ratio bound contains the factor 1/(p^κ√g).
Choosing √g ≍ p^α with α ≥ 8(L + ˜L) + 1 − κ completes the overfitted-case proof.

B.2 Case γ is underfitted and unsaturated

In the underfitted unsaturated case, the transition adds the influential covariate that maximizes the explained true-signal contribution. The βmin condition and related assumptions yield a favorable posterior-ratio bound.

The transition adds jγ ∈ γ∗ \ γ, selected to maximize the explained true-signal contribution.
This case is considered only when s∗ ≥ 1, with additional bounds applied under event Cn.
Adding jγ produces a projection-operator difference Φγ′ − Φγ.
The βmin condition implies that adding Xjγ explains at least ν^2Cβσ0^2 log p of the true signal.
The argument applies under the event An and uses n sufficiently large so that νpCβ ≥ 2(L + ˜L).
For sufficiently large Cβ, the posterior probability ratio is controlled using Assumption A and the βmin condition.

B.3 Case γ is underfitted and saturated

In the underfitted saturated case, the transition replaces an unimportant covariate with an influential one. The proof compares the resulting signal-explanation gain against cross-term and residual bounds to control the posterior ratio.

The transition replaces kγ with jγ, yielding γ′ = γ ∪ {jγ} \ {kγ}.
Replacing the unimportant covariate increases the proportion of the true signal explained by the current model.
The proof expands the relevant quadratic expression using v1, ˜w, and the projection difference.
Cauchy-Schwarz bounds the two cross terms in the expansion.
Under the βmin condition and ν^2Cβ ≥ 32(L + ˜L), the resulting bound holds on event An.
Combining the intermediate inequalities gives the final posterior-ratio bound when ν^2Cβ ≥ 192 under An ∩ Cn ∩ Dn.

B.4 Lemma 8 and its proof

Lemma 8 establishes inequalities showing that an influential covariate can replace an unimportant one with controlled loss in explained variation. The proof combines projection identities, least-squares optimality, and design assumptions.

Adding jγ to γ can explain γ∗, while removing kγ after the addition incurs explained-variation loss at most nω(X)∥β∗∥²/(s0−s∗).
If s0 ≥ (2ν−2ω(X)+1)s∗, replacing kγ with jγ is favorable in the current model.
Lemma 8 states the result under the conditions and notation of Lemma 4.
The proof derives the first inequality by summing projection-based bounds over missing influential covariates and using the maximizing definition of jγ.
The second inequality follows from least-squares optimality, normalization, the minimizing definition of kγ, and Assumption D.
Combining the preceding bounds completes the proof of the second claimed inequality.

C Proof of Lemma 7

The proof of Lemma 7 bounds posterior probability ratios separately for overfitted and underfitted models. It uses the model-size penalty, assumptions on signal and design quantities, and separate high-probability events.

The proof divides into overfitted and underfitted cases.
Overfitted case: For overfitted γ, k=|γ\γ∗| counts unimportant selected covariates, and the posterior ratio is expressed relative to a reduced model.
Overfitted case: When all influential covariates are included, projection non-expansiveness and bounds on R1 and R2 control the posterior ratio under An∩Bn∩Cn.
Underfitted case: The underfitted analysis uses α≥8(L+L̃)+2−κ and sufficiently large c0 to establish the required bounds under the stated events.
Underfitted case: For underfitted γ, the enlarged model eγ=γ∪γ∗ has |eγ|=k+ℓ≤(K+1)s∗, and the posterior ratio is analyzed through this completion.
Underfitted case: Combining the intermediate bounds under An∩Bn∩Cn∩Dn yields the final posterior-ratio control.