Source-linked AI summary
Controlling the false discovery rate via knockoffs
Rina Foygel Barber, Emmanuel J. Candès
TL;DR
The paper asks how to select variables associated with a response while controlling the expected fraction of false discoveries in finite-sample linear regression. It constructs correlation-matched knockoff variables and uses exchangeable statistics to estimate false discoveries and set selection thresholds. The resulting procedures provide theoretical FDR guarantees and show effective control with high power in empirical comparisons, while their main theory is restricted to identifiable designs with invertible Σ.
Problem
The paper addresses finite-sample variable-selection accuracy when many candidate variables may include only a few true signals, while requiring control of the false discovery rate.
Method
The method constructs knockoff features that mimic the original design’s covariance structure, then uses statistics with exchangeability properties to estimate false discoveries and choose a data-dependent threshold.
Results
The knockoff and knockoff+ procedures theoretically control FDR-related quantities and empirically demonstrate effective FDR control and high power compared with BHq and permutation-based methods.
Takeaways & Limitations
The procedures provide a flexible route to selecting variables with finite-sample FDR guarantees under arbitrary feature correlations in the supported linear-regression setting.
Takeaways & Limitations
The analysis assumes an invertible Σ, restricting the main setting to identifiable designs and excluding the commonly encountered regime p > n.
Abstract
from arXiv · showhide
In many fields of science, we observe a response variable together with a large number of potential explanatory variables, and would like to be able to discover which variables are truly associated with the response. At the same time, we need to know that the false discovery rate (FDR) - the expected fraction of false discoveries among all discoveries - is not too high, in order to assure the scientist that most of the discoveries are indeed true and replicable. This paper introduces the knockoff filter, a new variable selection procedure controlling the FDR in the statistical linear model whenever there are at least as many observations as variables. This method achieves exact FDR control in finite sample settings no matter the design or covariates, the number of variables in the model, or the amplitudes of the unknown regression coefficients, and does not require any knowledge of the noise level. As the name suggests, the method operates by manufacturing knockoff variables that are cheap - their construction does not require any new data - and are designed to mimic the correlation structure found within the existing variables, in a way that allows for accurate FDR control, beyond what is possible with permutation-based methods. The method of knockoffs is very general and flexible, and can work with a broad class of test statistics. We test the method in combination with statistics from the Lasso for sparse regression, and obtain empirical results showing that the resulting method has far more power than existing selection rules when the proportion of null variables is high.
1. Introduction.
The paper develops knockoff procedures for finite-sample FDR control in linear regression, using constructed features that mimic the originals’ correlation structure. The procedures combine flexible statistics, including Lasso-based statistics, with data-dependent thresholds to select variables while retaining power.
- Motivation: The paper targets FDR-controlled variable selection in the classical linear model, particularly when few of many recorded variables have nonzero coefficients.The setting assumes n ≥ p and Gaussian noise, with an invertible Gram matrix for identifiability.
- Method: The procedure constructs knockoff features that imitate the original design’s covariance and cross-correlation structure without collecting new data.The construction uses the Gram matrix Σ and a nonnegative vector s satisfying diag{s} ⪯ 2Σ.
- Method: Statistics W_j compare each original feature with its knockoff, with large positive values indicating that the original enters the Lasso model earlier.The statistics can also be built from forward selection or other procedures satisfying sufficiency and antisymmetry.
- Method: The knockoff filter selects variables using a data-dependent threshold and estimates the false discovery proportion from positive and negative W_j values.The selected set and threshold depend on the target FDR level q.
- Guarantees: Theoretical results establish FDR control for knockoff+, while the original knockoff procedure controls a closely related modified FDR.The modified FDR is close to the ordinary FDR when many features are selected, whereas knockoff+ is more conservative and controls FDR exactly.
2. Knockoffs and FDR control.
The knockoff construction creates synthetic features with a controlled correlation structure, then pairs them with original features through statistics that support exact FDR control. The method extends to p<n<2p when noise is known or accurately estimated, and its power depends on how weakly each knockoff correlates with its original.
- Knockoff construction: Knockoff features are constructed with a Gram structure determined by s, requiring a positive-semidefinite condition and an orthogonal complement available when n≥2p.The construction uses an orthonormal matrix whose column space is orthogonal to X.
- Knockoff construction: Choosing larger s values makes original variables and knockoffs less correlated, which is associated with higher knockoff power.Equi-correlated and SDP knockoffs provide two choices for reducing original–knockoff correlations.
- Extension to p<n<2p: When p<n<2p, the method can augment the data with synthetic Gaussian observations using an estimated noise level, producing a 2p-observation problem.The augmented design permits applying the construction developed for n≥2p; the estimate is especially accurate when n−p is large.
- Test statistics: The statistic W can be built from Gram matrices and feature-response inner products, while antisymmetry requires swapping an original feature and its knockoff to reverse W_j’s sign.The paper illustrates this framework with Lasso and extends it to penalized likelihood methods, including SCAD.
- Exchangeability and FDR control: Under the knockoff symmetry, null W_j signs are i.i.d. random and independent of magnitudes and nonnull signs, enabling false-discovery estimation and FDR control.This symmetry makes the counts of null statistics below −t and above t identically distributed, so the estimated FDP reflects the true FDP.
3. Comparison with other variable selection techniques.
The comparisons show that permutation-based methods can lose FDR control when null features retain correlations with signals, whereas knockoff methods control FDR and generally achieve higher power than BHq across tested settings.
- 3.1. Comparing to a permutation method.: 45.61% FDR for the permutation method versus 12.29% for the knockoff method at a 20% target demonstrates the permutation method’s failure in the correlated-feature simulation.Null original features entered the Lasso path earlier than permuted features because only the originals remained correlated with the signals.
- 3.2. Comparing to BHq.: Under independence, BHq controls FDR, but without independent test statistics it has no general FDR guarantee.In regression, independence corresponds to an orthogonal design with diagonal X⊤X.
- 3.3.1. Comparing methods.: The SDP construction achieved slightly higher power than the equi-variant construction for both knockoff procedures.The authors consequently focused on SDP-based knockoff, SDP-based knockoff+, and BHq in subsequent comparisons.
- 3.3.2. Effect of sparsity level, signal amplitude and feature correlation.: Across sparsity, signal-amplitude, and correlation experiments, the methods generally controlled FDR at 20%, except knockoff reached 26.67% at correlation ρ = 0.9.Knockoff controlled FDR for ρ ≤ 0.8; knockoff and knockoff+ had a strong power advantage over BHq at low and moderate sparsity.
- 3.4. Orthogonal designs.: For orthogonal designs, BHq and knockoff both controlled FDR and achieved nearly identical power across signal amplitudes.BHq’s FDR was π0q, whereas knockoff’s FDR approached q when signal strength made power substantial.
4. Experiment on real data: HIV drug resistance.
The HIV drug-resistance analysis applies knockoff-based selection to mutation data and evaluates selected positions against independently created treatment-selected mutation panels. Across drug classes, knockoff methods generally show good agreement with these validation panels, while a challenging heavy-tailed simulation still exhibits approximate FDR control.
- Data and evaluation: The analysis models each drug separately, using log-fold-increase resistance as the response and mutation presence or absence as binary predictors.Mutations appearing fewer than three times are removed, and duplicated columns are excluded for identifiability.
- Results: Figures 7–9 compare knockoff methods and BHq for PI-, NRTI-, and NNRTI-type drugs using the corresponding treatment-selected mutation panels.The figures encode selected positions that appear in the panels separately from selected positions absent from them.
- Data and evaluation: Selected mutations are evaluated against treatment-selected mutation panels, which approximate ground truth but come from patient-treatment association studies rather than lab-tested resistance data.Because multiple mutations can occur at the same position, comparisons use mutation positions rather than individual mutations.
- Results: Across the three drug classes, both methods perform similarly for most drugs, with generally good agreement between selected mutation positions and treatment-selected mutation lists.The knockoff filter shows slightly better overall agreement than BHq, although outcomes vary across drugs.
- Robustness simulation: The knockoff, knockoff+, and BHq procedures each exhibit good FDR control and power in partially simulated data with sparse predictors and heavy-tailed, non-Gaussian noise.The simulation uses a design drawn from the NNRTI dataset and an empirical heavy-tailed noise distribution.
- Robustness simulation: Approximate FDR control persists in an especially challenging setting where sparse predictors and heavy-tailed noise invalidate a straightforward central-limit-theorem argument.Even with no signals, the marginal statistics can be highly non-Gaussian.
5. Sequential hypothesis testing.
The paper develops sequential hypothesis-testing procedures that estimate FDR while maximizing rejections, then connects the knockoff filter to one of these procedures. This connection provides the basis for the knockoff methods’ FDR-control guarantees.
- Sequential procedures: The section introduces sequential hypothesis-testing procedures and theoretical results used to prove the main FDR-control theorems for knockoff and knockoff+.The procedures operate under an independence property for null p-values.
- Sequential procedures: SeqStep and SeqStep+ reject an initial sequence of hypotheses using alternative threshold definitions, with SeqStep+ correcting SeqStep to guarantee FDR control.The procedures choose the largest admissible rejection count under a threshold constraint.
- Sequential procedures: Selective SeqStep rejects only hypotheses among the selected initial sequence that also satisfy a fixed p-value threshold.Its two variants differ in whether the numerator uses an added 0 or 1 term.
- Theoretical guarantees: SeqStep+ and Selective SeqStep+ control FDR, whereas SeqStep and Selective SeqStep control a modified FDR under the theorem’s stated null-p-value assumptions.The theorem defines V as false discoveries and R as total discoveries.
- Theoretical guarantees: The ordering of p-values must not depend on the p-values themselves; sorting them by magnitude would violate the condition required for FDR control.This restriction is explicit in the sequential-testing assumptions.
- Connection to knockoffs: The knockoff method becomes a special case of Selective SeqStep after ordering nonzero statistics by decreasing magnitude and encoding their signs as binary p-values.Setting c = 1/2 makes the sequential threshold equivalent to the knockoff or knockoff+ threshold.
- Connection to knockoffs: Applying the sequential-testing theorem to this representation yields FDR control for the knockoff procedures.Rejecting p-values at most 1/2 corresponds to selecting positive knockoff statistics.
6. Discussion.
The discussion identifies limitations involving one-bit knockoff statistics, unstudied theoretical false-negative control, and the invertibility assumption that excludes many p > n settings. It also outlines possible assumptions and screening strategies for addressing high-dimensional identifiability.
- One-bit p-values may make knockoff methods conservative when signal amplitudes are low.The paper suggests multiple knockoffs as a potential remedy and leaves this investigation to future work.
- The theoretical analysis controls FDR but does not study the false negative rate.Statistical power is demonstrated empirically, while theoretical analysis is deferred.
- The methods assume Σ = X⊤X is invertible, limiting direct application when p > n and Σ is noninvertible.Invertibility is required for each feature’s effect to be identifiable.
- Sparse dependence assumptions or sample splitting with a low-dimensional knockoff filter may help address high-dimensional identifiability.The paper presents these as possible approaches and notes that higher-power high-dimensional methodology remains future work.