The variable selection problem

A linear model relates a response \(\boldsymbol{y} \in \mathbb{R}^n\) to a design \(\boldsymbol{X} \in \mathbb{R}^{n \times p}\) with \(n\) observations and \(p\) variables,

\[\boldsymbol{y} = \boldsymbol{X} \boldsymbol{\beta} + \boldsymbol{\varepsilon},\]

and in the settings of these vignettes only a few coefficients of \(\boldsymbol{\beta}\) differ from zero. The variables with a non-zero coefficient form the active set \(\mathcal{A}\), the others are null variables. Variable selection returns an estimate \(\widehat{\mathcal{A}}\) of the active set. A null variable in \(\widehat{\mathcal{A}}\) is a false discovery, and an active variable missing from it is a missed discovery. Prediction is a different goal. A model can predict well with many null variables on board, while a selection with false discoveries sends a laboratory [1]–[4] or an investment team [5] after effects that are not there.

FDR and TPR

Let \(1 \vee a = \max\{1, a\}\). The false discovery rate (FDR) and the true positive rate (TPR) of a selection procedure are

\[\operatorname{FDR} = \mathbb{E}\left[\frac{|\widehat{\mathcal{A}} \setminus \mathcal{A}|} {1 \vee |\widehat{\mathcal{A}}|}\right], \qquad \operatorname{TPR} = \mathbb{E}\left[\frac{|\mathcal{A} \cap \widehat{\mathcal{A}}|} {1 \vee |\mathcal{A}|}\right].\]

The quantities inside the expectations are the false discovery proportion (FDP) and the true positive proportion (TPP) of one selection, which trex_fdp() and trex_tpp() compute when the true support is known, as in a simulation. Benjamini and Hochberg introduced the FDR as the error rate for multiple hypothesis testing [6], and Benjamini reviewed its origins and its first fifteen years in [7]. The older family-wise error rate asks for no false discovery at all and loses power as the number of hypotheses grows [8], while a target FDR of 0.1 says that among the selected variables at most ten percent are expected to be false, whether ten or ten thousand variables were screened. A good selection procedure keeps the FDR below the target and the TPR as high as possible.

Three regimes

What a procedure can do depends on the number of variables relative to the number of observations.

Low dimensionality, \(n \geq p\)

With at least as many observations as variables the least squares estimate exists, and every coefficient has a standard error, a test statistic and a p-value. Multiple testing is classical here. The Benjamini–Hochberg procedure on the \(p\) p-values controls the FDR under the assumptions of the model and the dependence conditions of the procedure [6], [9], and the T-Rex selector works here as well.

High dimensionality, \(p > n\)

With more variables than observations the least squares estimate does not exist, because \(\boldsymbol{X}^\top \boldsymbol{X}\) is singular, and the classical p-values go with it. Sparse path methods like the lasso [10] and least angle regression [11], and greedy pursuits like orthogonal matching pursuit, build a model one variable at a time and work for any \(p\), but their stopping rules are tuned for prediction error, so they select without controlling the FDR. The T-Rex selector wraps these solvers in its random experiments and supplies the FDR control they lack, in finite samples and without p-values [12], and for strongly dependent variables the dependency-aware variant T-Rex+DA restores the exchangeability its guarantee rests on [13].

Highest dimensionality, \(p \gg n\)

In genomics a design has hundreds of thousands or millions of variables and up to a hundred thousand observations, and the method is the same while the computation is not. Each random experiment enlarges the design by \(L \cdot p\) dummy columns, \(K\) experiments run, and the design itself may not fit in memory. Screen-T-Rex runs the random experiments once as a fast first pass [14], memory-mapped designs keep the data on disk [15], the seeded dummy strategies store no dummy matrices, the greedy solvers are cheaper per step [16], and the thread budgets of the package put the cores to work.

The regimes in one map

Figure 1: The three regimes in the plane of p and n.

The diagonal \(p = n\) separates low from high dimensionality, and the dashed line \(p = 1000\,n\) marks where the computation starts to dominate, a rule of thumb rather than a theorem. The markers show typical settings. The diagonal, not the size of \(p\) alone, decides the regime. A biobank with twenty thousand participants and a hundred variables is a low-dimensional problem, while a laboratory study with sixty samples and two thousand genes is a high-dimensional one. Large samples with many variables sit near the diagonal and belong to either side, which is why the map replaces the four quadrants of small and large samples with few and many variables.

The T-Rex selector across the regimes

The selector is defined for any \(n\) and \(p\). One data-generating process with five active variables of coefficient one at \(n = 100\) and three values of \(p\) walks through the regimes, ten trials per regime with ten random experiments each, every trial with its own data and dummies.

set.seed(7)
n <- 100
num_act <- 5
trials <- 10
true_support <- seq_len(num_act)
for (p in c(50, 200, 1000)) {
  fdr <- 0
  tpr <- 0
  for (trial in seq_len(trials)) {
    X <- matrix(rnorm(n * p), n, p)
    beta <- c(rep(1, num_act), rep(0, p - num_act))
    y <- as.vector(X %*% beta + rnorm(n))
    ctrl <- trex_control(K = 10)
    sel <- TRexSelector$new(X, y, tFDR = 0.1, seed = 6 + trial, verbose = FALSE, control = ctrl)
    sel$select()
    fdr <- fdr + trex_fdp(sel$selected_indices, true_support) / trials
    tpr <- tpr + trex_tpp(sel$selected_indices, true_support) / trials
  }
  cat(sprintf("p = %4d  n/p = %5.2f  FDR = %.2f  TPR = %.2f\n", p, n / p, fdr, tpr))
}
#> p =   50  n/p =  2.00  FDR = 0.03  TPR = 1.00
#> p =  200  n/p =  0.50  FDR = 0.04  TPR = 0.98
#> p = 1000  n/p =  0.10  FDR = 0.05  TPR = 0.86

The estimated FDR stays below the target in every regime, while the TPR falls as \(p\) grows relative to \(n\). Dimensionality costs power, not the control of the false discoveries. In the low-dimensional case the classical route exists next to the selector, and in the two others it does not.

Bibliography

[1]

J. P. A. Ioannidis, “Why most published research findings are false,” PLoS Med., vol. 2, no. 8, 2005, doi: 10.1371/journal.pmed.0020124.

[2]

D. MacArthur, “Face up to false positives,” Nature, vol. 487, no. 7408, pp. 427–428, 2012, doi: 10.1038/487427a.

[3]

E. Uffelmann et al., “Genome-wide association studies,” Nat. Rev. Methods Primers, vol. 1, 2021, doi: 10.1038/s43586-021-00056-9.

[4]

S. Tandy-Connor et al., “False-positive results released by direct-to-consumer genetic tests highlight the importance of clinical confirmation testing for appropriate patient care,” Genet. Med., vol. 20, no. 12, pp. 1515–1521, 2018, doi: 10.1038/gim.2018.38.

[5]

C. R. Harvey, Y. Liu, and H. Zhu, “… and the cross-section of expected returns,” Rev. Financ. Stud., vol. 29, no. 1, pp. 5–68, 2016, doi: 10.1093/rfs/hhv059.

[6]

Y. Benjamini and Y. Hochberg, “Controlling the false discovery rate: A practical and powerful approach to multiple testing,” J. R. Stat. Soc. Ser. B Stat. Methodol., vol. 57, no. 1, pp. 289–300, 1995, doi: 10.1111/j.2517-6161.1995.tb02031.x.

[7]

Y. Benjamini, “Discovering the false discovery rate,” J. R. Stat. Soc. Ser. B Stat. Methodol., vol. 72, no. 4, pp. 405–416, 2010, doi: 10.1111/j.1467-9868.2010.00746.x.

[8]

S. Holm, “A simple sequentially rejective multiple test procedure,” Scand. J. Stat., vol. 6, no. 2, pp. 65–70, 1979, Available: https://www.jstor.org/stable/4615733

[9]

Y. Benjamini and D. Yekutieli, “The control of the false discovery rate in multiple testing under dependency,” Ann. Stat., vol. 29, no. 4, pp. 1165–1188, 2001, doi: 10.1214/aos/1013699998.

[10]

R. Tibshirani, “Regression shrinkage and selection via the lasso,” J. R. Stat. Soc. Ser. B Stat. Methodol., vol. 58, no. 1, pp. 267–288, 1996, doi: 10.1111/j.2517-6161.1996.tb02080.x.

[11]

B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, “Least angle regression,” Ann. Statist., vol. 32, no. 2, pp. 407–499, 2004, doi: 10.1214/009053604000000067.

[12]

J. Machkour, M. Muma, and D. P. Palomar, “The terminating-random experiments selector: Fast high-dimensional variable selection with false discovery rate control,” Signal Process., vol. 231, 2025, doi: 10.1016/j.sigpro.2025.109894.

[13]

J. Machkour, M. Muma, and D. P. Palomar, “High-dimensional false discovery rate control for dependent variables,” Signal Process., vol. 234, 2025, doi: 10.1016/j.sigpro.2025.109990.

[14]

J. Machkour, M. Muma, and D. P. Palomar, “False discovery rate control for fast screening of large-scale genomics biobanks,” in Proc. 22nd IEEE statist. Signal process. Workshop (SSP), 2023, pp. 666–670. doi: 10.1109/SSP53291.2023.10207957.

[15]

F. Scheidt, J. Machkour, and M. Muma, “Solving FDR-controlled sparse regression problems with five million variables on a laptop,” in Proc. IEEE 9th int. Workshop comput. Adv. Multi-sensor adapt. Process. (CAMSAP), 2023, pp. 116–120. doi: 10.1109/CAMSAP58249.2023.10403478.

[16]

F. Scheidt and M. Muma, “Terminating greedy pursuits for high-dimensional false discovery rate control,” in Proc. Eur. Signal process. Conf. (EUSIPCO), 2026, pp. 2511–2515.

Data dimensionality and FDR control