The Horseshoe at Scale — Selection when p ≫ n

Python · R · Part 8 of the variable-selection arc — global-local shrinkage

Overview

Part 8 of the variable-selection arc: selection when p≫np\gg n. Every dataset so far had a handful of predictors; real variable selection often looks the opposite — thousands of candidate predictors, tens of samples. Genomics is the canonical case, and exactly where the earlier machinery breaks down: enumeration would need 240882^{4088} models, and discrete spike-and-slab mixes painfully with 4,088 indicators. The tool built for this regime is the continuous global-local shrinkage prior — above all the horseshoe (Carvalho–Polson–Scott 2010). The benchmark is the riboflavin dataset (Bühlmann–Kalisch–Meier 2014): n=71n=71 Bacillus subtilis cultures, p=4088p=4088 gene-expression measurements, and a continuous response — the log vitamin-B2 production rate. The question: which handful of genes drives production? Fit from scratch, cross-checked against PyMC (same prior, NUTS) and R (glmnet, the lasso — the frequentist workhorse for p≫np\gg n).

βj∣λj,τ,σ∼N(0, λj2τ2σ2),λj∼C+(0,1),τ∼C+(0,1);κj=11+λj2τ2\beta_j\mid\lambda_j,\tau,\sigma \sim \mathcal N(0,\ \lambda_j^2\tau^2\sigma^2), \quad \lambda_j\sim C^+(0,1), \quad \tau\sim C^+(0,1); \qquad \kappa_j = \frac{1}{1+\lambda_j^2\tau^2}

Global-local shrinkage, and the sampler that makes it scale

The horseshoe gives each coefficient its own local scale on top of a global one: βj∼N(0,λj2τ2σ2)\beta_j\sim\mathcal N(0,\lambda_j^2\tau^2\sigma^2), with λj∼C+(0,1)\lambda_j\sim C^+(0,1) and τ∼C+(0,1)\tau\sim C^+(0,1). The global τ\tau pulls everything toward zero (essential when p≫np\gg n); the heavy-tailed local λj\lambda_j lets a few coefficients escape. It is essentially parameter-free — the half-Cauchys need no tuning — and its action is summarised by the shrinkage weight κj=1/(1+λj2τ2)∈[0,1]\kappa_j=1/(1+\lambda_j^2\tau^2)\in[0,1] (κj≈1\kappa_j\approx1: shrunk to zero; κj≈0\kappa_j\approx0: kept). Two ingredients make it tractable. (1) Makalic–Schmidt (2016) auxiliary variables turn each half-Cauchy into a pair of conjugate inverse-gamma draws, so the whole sampler is Gibbs. (2) The Bhattacharya–Chakraborty–Mallick (2016) sampler for the coefficient block: the naive draw needs the p×pp\times p precision — O(p3)=O(40883)O(p^3)=O(4088^3), hopeless — but their exact algorithm never forms it, solving an n×nn\times n system instead at O(n2p)O(n^2p) cost. With n=71n=71 that turns an impossible step into a millisecond one — the entire run is under 10 seconds (9.89.8 s for 6,000 iterations at p=4088p=4088). There are no free hyperparameters (all half-Cauchy scales are 1, the standard horseshoe). Engine: a self-contained hshd.py.

Results

A needle in 4,088 haystacks. The horseshoe drives essentially every coefficient to zero — the median shrinkage weight is 0.998 — and lets just a couple escape: YOAB and YXLE stand out sharply (κ≈0.25,0.29\kappa\approx 0.25, 0.29), with a weaker second tier (ARGB, YISU). This is what selection must look like when p≫np\gg n: aggressive global shrinkage, a few local exceptions — and the signals are biologically sensible (the YXL-region genes and YOAB recur across analyses of this benchmark), recovered without any pre-screening. Both Bayesian engines agree on what is real, not on what is noise: with priors matched, the from-scratch Gibbs and PyMC's NUTS pick the same dominant gene (YOAB; YXLE the runner-up in the from-scratch Gibbs) and R's lasso puts YOAB first too — but across all 4,088 coefficients the two samplers correlate only r≈0.80r\approx 0.80. That is the posterior being honest: the ~4,086 near-zero coefficients are ≈0\approx 0 with large uncertainty, so their exact values are not meant to be reproduced — the reliable outputs of a p≫np\gg n fit are the shrinkage weights and the top-gene ranking, not individual near-zero estimates. The sampler matters enormously at scale: the specialised Gibbs finishes in ~10 seconds; general-purpose NUTS takes ~2.7 minutes (~16× longer) and still mixes poorly against the horseshoe funnel in 4,088 dimensions. When p≫np\gg n, the algorithm, not just the prior, is the enabling idea. The horseshoe answers the same question as SSVS — but by shrinking rather than switching: no 2p2^p model space, no binary indicators, just a heavy-tailed prior that lets a few coefficients through, which is why global-local priors dominate the p≫np\gg n regime.

Notebooks

Downloads

References