Fast Exact Bayesian Inference for Sparse Signals in the Normal Sequence Model

Tim van Erven, Botond Szabó

Abstract

We consider exact algorithms for Bayesian inference with model selection priors (including spike-and-slab priors) in the sparse normal sequence model. Because the best existing exact algorithm becomes numerically unstable for sample sizes over $n=500$, there has been much attention for alternative approaches like approximate algorithms (Gibbs sampling, variational Bayes, etc.), shrinkage priors (e.g. the Horseshoe prior and the Spike-and-Slab LASSO) or empirical Bayesian methods. However, by introducing algorithmic ideas from online sequential prediction, we show that exact calculations are feasible for much larger sample sizes: for general model selection priors we reach $n=25,000$, and for certain spike-and-slab priors we can easily reach $n=100,000$. We further prove a de Finetti-like result for finite sample sizes that characterizes exactly which model selection priors can be expressed as spike-and-slab priors. The computational speed and numerical accuracy of the proposed methods are demonstrated in experiments on simulated data, on a differential gene expression data set, and to compare the effect of multiple hyper-parameter settings in the beta-binomial prior.

Introduction

In the sparse normal sequence model, we observe data $Y_i = \theta_i + \epsilon_i$ and aim to recover the signal $\theta$, assuming most components are zero. The "spike-and-slab" prior is considered the gold standard for this task because it explicitly models this sparsity by placing a point mass at zero (the spike) and a continuous distribution elsewhere (the slab).

However, Bayesian inference with these priors is notoriously difficult due to the combinatorial explosion of the model space; with $n$ variables, there are $2^n$ possible models. Previous exact algorithms were limited to $n \approx 500$ because they were computationally expensive ($O(n^3)$) and numerically unstable—floating-point errors would accumulate so quickly that the results became meaningless. Consequently, researchers have traditionally relied on approximations like Gibbs sampling or Variational Bayes, which can be slow to converge or provide biased results.

Methods

This research bridges the gap between Bayesian statistics and online sequential prediction to create two primary algorithms that achieve exact inference with high efficiency.

The Model Selection HMM

The authors observe that for many priors, the probability of a coordinate being non-zero depends only on the total number of non-zeros already observed, rather than their specific locations. This symmetry allows the prior to be represented as a Hidden Markov Model (HMM). By mapping the model selection process to an HMM, the authors can apply the standard Forward-Backward algorithm to compute marginal posterior probabilities efficiently, reducing complexity to $O(n^2)$.

Graphical representation of the Model Selection HMM. The hidden states $H_i$ track the cumulative number of non-zero signals, influencing the prior for $\theta_i$, which generates the observed data $Y_i$.

Discretized Spike-and-Slab

For the specific subclass of spike-and-slab priors, the authors introduce a discretization of the mixing parameter $\alpha$ (the prior probability of a signal being non-zero). By employing an arcsine transformation to ensure constant Fisher information, they demonstrate that a small number of discretization points ($k \approx \sqrt{n}$) is sufficient to achieve arbitrary precision, further reducing complexity to $O(n^{3/2})$.

Numerical Rigor

To address the historical issue of numerical instability, all calculations are performed in a logarithmic representation. Furthermore, the authors utilize interval arithmetic to provide guaranteed bounds on numerical error, ensuring the results are mathematically "exact" to a specified number of decimal places.

Results and Discussion

Computational Performance

The proposed methods offer massive speedups over previous state-of-the-art exact algorithms. For a sample size of $n=25,000$, the HMM method runs in under 15 minutes on a standard laptop—a task that would have previously taken approximately 20 days. The discretized version successfully handled $n=100,000$ within a 30-minute time limit. Crucially, these methods remained stable and accurate (providing 5–11 reliable decimal places) at scales where previous methods failed entirely.

Real-World Application: Gene Expression

The algorithms were tested on a differential gene expression dataset containing expression levels for 22,283 genes in patients with Ulcerative Colitis and Crohn’s disease. This high-dimensional test revealed that the choice of hyper-parameters in the beta-binomial prior significantly impacts the number of genes selected (ranging from 674 to 3,169). This highlights the importance of exact computation in understanding prior influence and ensuring reproducible results in sensitive biological applications.

Theoretical Contributions

The paper provides a new theoretical characterization of which model selection priors can be represented as spike-and-slab priors. They show that while binomial and Poisson priors work, heavy-tailed or sub-exponential priors cannot be simplified in this manner. Additionally, by having an "exact" benchmark, the authors reveal that standard MCMC and Variational Bayes often only provide 1 to 3 decimal places of accuracy.

Conclusion

While the current algorithms are optimized for the normal sequence model (where the design matrix is the identity), they represent a significant leap in the feasibility of exact Bayesian inference. Future work aims to extend these HMM-based approaches to general sparse linear regression where predictors are correlated, though this presents challenges as the hidden states may become fully connected, potentially increasing complexity.

Summary updated

Abstract

We consider exact algorithms for Bayesian inference with model selection priors (including spike-and-slab priors) in the sparse normal sequence model. Because the best existing exact algorithm becomes numerically unstable for sample sizes over n=500, there has been much attention for alternative approaches like approximate algorithms (Gibbs sampling, variational Bayes, etc.), shrinkage priors (e.g. the Horseshoe prior and the Spike-and-Slab LASSO) or empirical Bayesian methods. However, by introducing algorithmic ideas from online sequential prediction, we show that exact calculations are feasible for much larger sample sizes: for general model selection priors we reach n=25000, and for certain spike-and-slab priors we can easily reach n=100000. We further prove a de Finetti-like result for finite sample sizes that characterizes exactly which model selection priors can be expressed as spike-and-slab priors. The computational speed and numerical accuracy of the proposed methods are demonstrated in experiments on simulated data, on a differential gene expression data set, and to compare the effect of multiple hyper-parameter settings in the beta-binomial prior. In our experimental evaluation we compute guaranteed bounds on the numerical accuracy of all new algorithms, which shows that the proposed methods are numerically reliable whereas an alternative based on long division is not.
BibTeX
@inproceedings{erven2020fast,
  author = {Tim van Erven and Botond Szabó},
  title = {{Fast Exact Bayesian Inference for Sparse Signals in the Normal Sequence Model}},
  booktitle = {Bayesian},
  year = {2020},
  doi = {10.1214/20-ba1227},
}
Figure