The Horseshoe+ Estimator of Ultra-Sparse Signals

Anindya Bhadra, Jyotishka Datta, Nicholas G. Polson, Brandon T. WillardBayesian 2016 · DOI

TL;DR

This paper introduces the "horseshoe+" prior, a novel Bayesian approach for identifying signals in datasets where most values are zero (ultra-sparse). It offers theoretical and empirical improvements over existing methods, particularly in accurately distinguishing true signals from noise, leading to better estimation and decision-making in high-dimensional settings.

What Problem Does This Paper Address?

In many real-world scenarios, especially in fields like genomics or signal processing, datasets are characterized by "ultra-sparsity." This means that while there might be a few important signals or effects, the vast majority of the data points are essentially zero or noise. Detecting these few true signals amidst a sea of noise is a significant challenge for statistical methods. Traditional approaches often struggle to distinguish between very small signals and pure noise, leading to either missed discoveries or false positives. The paper aims to develop a more robust statistical tool for this "needle in a haystack" problem.

Methods

The core contribution is the introduction of the horseshoe+ prior. This is a Bayesian statistical model that acts as a prior belief about the structure of the data. It's an extension of the existing "horseshoe" prior, which has shown promise in handling sparse data. The horseshoe+ prior is designed to:

  • Shrink noise towards zero: It encourages the model to assign very small values to most parameters, effectively treating them as noise.
  • Preserve true signals: Crucially, it allows important signals to escape this strong shrinkage, maintaining their values.
  • Heavier tails: A key innovation is the introduction of "heavier tails" in the prior distribution. This means the horseshoe+ prior assigns more probability mass to extreme values (both very close to zero and further away from zero) compared to the original horseshoe prior. This is theorized to improve the separation of true signals from noise, especially for signals that are not extremely close to zero but still distinct from pure noise.
  • Hierarchical structure: The prior is implemented using a hierarchical model, which is a common and powerful technique in Bayesian statistics for modeling complex relationships.

The paper also develops new theoretical techniques, specifically using Meijer-G functions, to analyze the properties of these "global-local" shrinkage priors.

Datasets

The paper uses simulated data for its primary experiments and a real-world prostate cancer gene expression dataset for illustration. The simulated data is designed to mimic ultra-sparse scenarios with varying proportions of true signals. The prostate cancer dataset is a benchmark for gene expression analysis, containing measurements for thousands of genes across normal and cancerous samples.

Key Insights and Ideas

  • The power of "heavier tails": The introduction of heavier tails in the horseshoe+ prior is not just a minor tweak; it fundamentally improves the ability to distinguish between weak signals and noise, especially in "nearly black" (ultra-sparse) scenarios.
  • Sharper theoretical guarantees: The horseshoe+ prior not only performs well in practice but also comes with stronger theoretical backing. It achieves faster convergence rates and lower error rates in estimation and testing compared to the original horseshoe prior.
  • Global vs. Local Shrinkage: The paper reinforces the idea that "global-local" shrinkage priors (like horseshoe and horseshoe+) are highly effective for sparse data. They balance a global tendency to shrink all parameters towards zero with local flexibility to preserve important signals.
  • The role of the global shrinkage parameter: The paper highlights that the effectiveness of these priors is sensitive to how a global shrinkage parameter is set, suggesting it needs to adapt to the underlying sparsity level of the data.

Key Results

  • Improved Estimation: In simulations, the horseshoe+ estimator consistently achieved lower average Sum of Squared Errors (SSE) compared to the horseshoe and Dirichlet-Laplace estimators, particularly when signals were present.
  • Better Signal Detection: The horseshoe+ prior demonstrated superior performance in misclassification probabilities for multiple testing, closely matching the theoretical "Bayes oracle" (the best possible performance).
  • Faster Convergence: Theoretically, the horseshoe+ estimator converges to the true density at a "super-efficient" rate, meaning it's faster than many other methods.
  • Lower Mean Squared Error (MSE): For large signal values, the horseshoe+ estimator has a lower MSE than the horseshoe estimator.

Limitations and Future Work

  • Computational Cost: While the horseshoe+ prior is computationally feasible, Bayesian methods, in general, can be computationally intensive, especially for very large datasets. The paper mentions using MCMC (Markov Chain Monte Carlo) methods for sampling.
  • Hyperparameter Tuning: The performance of the horseshoe+ prior can depend on the choice of certain hyperparameters, particularly the global shrinkage parameter τ. While the paper suggests optimal choices, further research into adaptive methods for setting these parameters could be beneficial.
  • Extension to other models: The authors suggest extending the horseshoe+ prior to more complex models, such as those involving higher-order products of Cauchy variables for even heavier tails, and exploring its application in other statistical problems. They also pose an open question about identifying necessary conditions for global-local shrinkage priors to guarantee desirable properties.

Summary updated

Abstract

We propose a new prior for ultra-sparse signal detection that we term the “horseshoe+ prior.” The horseshoe+ prior is a natural extension of the horseshoe prior that has achieved success in the estimation and detection of sparse signals and has been shown to possess a number of desirable theoretical properties while enjoying computational feasibility in high dimensions. The horseshoe+ prior builds upon these advantages. Our work proves that the horseshoe+ posterior concentrates at a rate faster than that of the horseshoe in the Kullback–Leibler (K-L) sense. We also establish theoretically that the proposed estimator has lower posterior mean squared error in estimating signals compared to the horseshoe and achieves the optimal Bayes risk in testing up to a constant. For one-group global–local scale mixture priors, we develop a new technique for analyzing the marginal sparse prior densities using the class of Meijer-G functions. In simulations, the horseshoe+ estimator demonstrates superior performance in a standard design setting against competing methods, including the horseshoe and Dirichlet–Laplace estimators. We conclude with an illustration on a prostate cancer data set and by pointing out some directions for future research.
BibTeX
@inproceedings{bhadra2016horseshoe,
  author = {Anindya Bhadra and Jyotishka Datta and Nicholas G. Polson and Brandon T. Willard},
  title = {{The Horseshoe+ Estimator of Ultra-Sparse Signals}},
  booktitle = {Bayesian},
  year = {2016},
  doi = {10.1214/16-ba1028},
}
Figure