PaperlayerView exact revision on arXiv

Source-linked AI summary

Panning for Gold: Model-X Knockoffs for High-dimensional Controlled Variable Selection

Emmanuel Candes, Yingying Fan, Lucas Janson, Jinchi Lv

arXiv:1610.02351v4stat.MEmath.STstat.AP

TL;DR

High-dimensional nonlinear variable selection needs reliable false-discovery control, but conditional inference is difficult when the response model is unknown. The paper introduces model-X knockoffs, which construct knockoff variables probabilistically and enable finite-sample inference; the method doubles discoveries in a Crohn’s disease analysis.

  • Problem

    High-dimensional variable selection requires identifying outcome-relevant covariates while controlling false discoveries, but estimating conditional relationships from finite samples is generally impossible without restrictive models.

  • Method

    Model-X knockoffs construct variables probabilistically and use data-dependent thresholds whose estimated false-discovery proportion supports false discovery rate control without constructing p-values.

  • Results

    18 discoveries on average versus 9 for WTCCC (2007), doubling the power in the Crohn’s disease analysis.

  • Takeaways & Limitations

    The framework selects important variables in high-dimensional nonlinear models, including GLMs, while guaranteeing Type I error control and avoiding p-values.

  • Takeaways & Limitations

    Under dependent marginal p-values, BHq does not control FDR exactly and may produce highly variable FDP.

Abstract

from arXiv · show

Many contemporary large-scale applications involve building interpretable models linking a large set of potential covariates to a response in a nonlinear fashion, such as when the response is binary. Although this modeling problem has been extensively studied, it remains unclear how to effectively control the fraction of false discoveries even in high-dimensional logistic regression, not to mention general high-dimensional nonlinear models. To address such a practical problem, we propose a new framework of $model$-$X$ knockoffs, which reads from a different perspective the knockoff procedure (Barber and Candès, 2015) originally designed for controlling the false discovery rate in linear models. Whereas the knockoffs procedure is constrained to homoscedastic linear models with $n\ge p$, the key innovation here is that model-X knockoffs provide valid inference from finite samples in settings in which the conditional distribution of the response is arbitrary and completely unknown. Furthermore, this holds no matter the number of covariates. Correct inference in such a broad setting is achieved by constructing knockoff variables probabilistically instead of geometrically. To do this, our approach requires the covariates be random (independent and identically distributed rows) with a distribution that is known, although we provide preliminary experimental evidence that our procedure is robust to unknown/estimated distributions. To our knowledge, no other procedure solves the $controlled$ variable selection problem in such generality, but in the restricted settings where competitors exist, we demonstrate the superior power of knockoffs through simulations. Finally, we apply our procedure to data from a case-control study of Crohn's disease in the United Kingdom, making twice as many discoveries as the original analysis of the same data.

1 Introduction

The paper formulates high-dimensional variable selection as identifying predictors that conditionally determine an outcome, then introduces model-X knockoffs for finite-sample FDR control without modeling the response. The framework assumes i.i.d. observations and a known covariate distribution, and is applied to Crohn’s disease data with twice as many discoveries as the original analysis.

  • 1 Introduction: The selection target is the smallest covariate subset that makes the outcome independent of all remaining variables.This subset is the Markov blanket or Markov boundary for the outcome.
  • 1 Introduction: The framework permits arbitrary relationships between covariates and outcomes while controlling FDR in finite samples.It places no restriction on dimensionality or the conditional distribution of the outcome given covariates.
  • 1 Introduction: Model-X knockoffs construct control variables for random covariates, shifting modeling assumptions from the response to the covariate distribution.The observations are i.i.d.; the joint covariate distribution is assumed known, while the conditional response distribution is not.
  • 1 Introduction: The method applies beyond linear models to nonlinear regression, classification, survival analysis, and generalized linear models.The framework accommodates arbitrary nonlinearities and heteroscedasticity, including settings common in machine learning.
  • 1 Introduction: Marginal testing can lose power, test the wrong hypotheses for correlated covariates, and yield unstable FDP under dependent p-values.These limitations motivate conditional selection procedures in high-dimensional settings.

2 Problem statement

The paper defines controlled variable selection as finding variables conditionally relevant to the response while controlling the false discovery rate. In GLMs, conditional relevance corresponds to nonzero coefficients when covariates are not perfectly predictable from the others.

  • The target is the Markov blanket: the smallest subset of covariates on which the conditional distribution of Y depends.
  • A variable is null when Y is conditionally independent of it given all other covariates; otherwise it is relevant.
  • The selection goal is to discover as many relevant variables as possible while keeping the false discovery rate under control.
  • In GLMs, conditional independence between Y and Xj is equivalent to βj = 0 under broad conditions.
  • Perfectly predictable covariates can make coefficient-based relevance disagree with conditional dependence, so the covariate assumption is necessary.For example, a variable can have a nonzero coefficient while remaining conditionally independent of Y given another covariate.

3 Methodology

Model-X knockoffs construct response-independent copies of covariates whose joint distribution is invariant to swapping originals and copies. This exchangeability makes null statistics behave like independent sign flips, enabling finite-sample FDR control.

  • Model-X knockoffs are constructed to be pairwise exchangeable with the original covariates and conditionally independent of the response given X.The response-independence property is guaranteed when knockoffs are constructed without using Y.
  • Swapping any subset of null covariates with their knockoffs leaves the joint distribution of covariates and knockoffs conditional on Y unchanged.
  • Feature statistics Wj are designed so swapping Xj with its knockoff reverses Wj's sign, while leaving the other statistics unchanged.
  • The Lasso coefficient-difference statistic compares importance assigned to each original variable and its knockoff.
  • Conditional on absolute statistics, null Wj signs are independent fair coin flips, even conditionally on the response.
  • The resulting thresholding procedure rigorously controls FDR in finite samples regardless of the dependence between response and covariates.The method's power depends on how knockoffs and statistics are constructed.

4 The conditional randomization test

The conditional randomization test generates null covariates from their conditional distribution given the others, then compares feature statistics across randomized samples. It provides valid conditional-independence p-values but can be computationally expensive at large p.

  • The procedure computes one-sided p-values by repeatedly generating randomized covariate columns and recalculating the feature statistic.
  • The test assesses whether Xj and Y are conditionally independent by resampling Xj from L(Xj|X-j) while holding the other covariates fixed.
  • Under the null, the resampled and observed feature statistics are identically distributed conditional on Y and the other covariates.This permits Monte Carlo estimation of the conditional null distribution and p-values.
  • Conditional null quantiles yield valid p-values because the null statistic is no larger than its corresponding conditional quantile with the stated tail probability.
  • The method is closely related to propensity-score inference but applies beyond binary Xj, whereas residual permutation methods rely on accurately estimated response models.
  • The main limitation is computational cost: obtaining high-resolution p-values for many covariates can require Ω(p) feature-statistic computations.Knockoffs need the analogous feature-importance computation only once; conditional randomization can become prohibitive when p reaches hundreds of thousands or millions.
  • Unlike BHq applied to arbitrarily dependent p-values, model-X knockoffs provide guaranteed FDR control.

5 Numerical simulations

The simulations examine logistic-regression p-value validity, adaptive knockoff statistics, and comparisons with alternative procedures across linear, nonlinear, low-dimensional, and high-dimensional settings. They show that adaptive and model-X knockoff methods can retain FDR control while offering strong or substantially greater power, with conditional randomization incurring extreme computational cost.

  • 5.1 Logistic regression p-values: Null logistic-regression p-values can be highly non-uniform, with their distribution depending on unknown coefficient sequences and remaining distorted as sample size and dimension increase proportionally.In one setting, P{p-value ≤ 0.1%} exceeded its nominal value by more than 20 times.
  • 5.2 Alternative knockoff statistics: Model-X knockoffs permit a broad choice of feature statistics, including GLM coefficients, random-forest importances, and sensitivity measures, while retaining rigorous variable-selection error control.The framework can wrap essentially any data-fitting or prediction algorithm, provided the statistic construction respects the knockoff requirements.
  • 5.2.1 Adaptive knockoff statistics: LCD was uniformly more powerful than LSM across simulations spanning model class, covariate dependence, effect size, sparsity, sample size, and dimension, particularly under covariate dependence.LCD uses cross-validation to tune the Lasso penalty; using the one-standard-error rule can make it underpowered in low-power settings.
  • 5.3 Comparisons with alternative procedures: Conditional randomization testing achieved somewhat higher power with similar FDR control, but required roughly 5000 times more computation than MX knockoffs.The reported Figure 4 computation took roughly three years of serial time versus about six hours for MX knockoffs, preventing its inclusion in larger simulations.
  • 5.3 Comparisons with alternative procedures: MX knockoffs were the most powerful method in the Gaussian linear comparison, achieving as much as 10% higher power than the nearest alternative while all methods controlled FDR.When p = 6000, maximum-likelihood p-values and fixed-X knockoffs could not be computed, whereas MX knockoffs remained applicable and outperformed BHq on marginal p-values.
  • 5.3 Comparisons with alternative procedures: In binomial models, MX knockoffs continued to have the highest power among FDR-controlling procedures, while BHq applied to asymptotic maximum-likelihood p-values exceeded 50% FDR.The inflated FDR made the competing method’s high power uninformative in that comparison.

6 Robustness

The robustness experiments examine MX knockoffs when the covariate distribution is estimated rather than known, using simulated Gaussian designs and real GWAS covariates. Across these settings, FDR remains controlled, while covariance overfitting can reduce power and increase conservativeness.

  • Covariate-distribution estimation: The experiments test robustness to errors in the joint covariate distribution, including overfitting toward the empirical covariance and estimation from real GWAS data.The simulated study varies covariance estimates from the true AR(1) covariance to graphical-lasso and convex-combination estimates; further studies use high-dimensional GWAS covariates.
  • Simulated covariance robustness: 10% FDR is never violated even when the covariance estimate is very far from the truth.This result concerns the simulated covariance-robustness experiment and uses the nominal 10% FDR target.
  • Simulated covariance robustness: Almost 100% relative covariance-estimation error reduces MX knockoff power by about 20% relative to using the known covariance.Greater overfitting makes the procedure more conservative, although substantial power remains under large estimation error.
  • Real-data robustness: The GWAS robustness studies use high-dimensional genotype covariates with strong spatial structure and an in-sample covariance estimator tailored to GWAS data.They assess second-order model-X knockoffs constructed by ASDP under an artificial conditional response model.

7 Genetic analysis of Crohn’s disease

The Crohn’s disease analysis applied model-X knockoffs to highly correlated, high-dimensional SNP data and found substantially more discoveries than the original marginal analysis. Robustness checks supported using the estimated covariate distribution, while clustering and approximate knockoff construction addressed computational and correlation challenges.

  • Data and setup: The analysis covered 377,749 SNPs across 4,913 subjects, with p much larger than n.The subjects included 1,917 Crohn’s disease patients and 2,996 healthy controls.
  • Data and setup: Clustering reduced the SNP representation to 71,145 representatives and bounded pairwise representative correlations by 0.5.The representatives were selected from correlation-based clusters using held-out observations for marginal t-tests.
  • Method: The procedure used an approximate SDP knockoff construction based on block-diagonal covariance approximations to make computation tractable.Blocks were formed by single-linkage clustering and constrained to a maximum size of 999; chromosome-level parallelization reduced computation time.
  • Validation: Robustness simulations evaluated realized FDP under estimated covariate distributions before applying knockoffs to real Crohn’s disease outcomes.The simulations split the design matrix into 10 datasets and ran knockoffs 10 times for each conditional model.
  • Interpretation: Overlapping discovered clusters may reflect multiple important nearby SNPs, omitted intermediate SNPs, false discoveries, or errors in the estimated covariate distribution.The authors considered the estimation-error explanation unlikely for the highlighted chromosome 1 and 5 pairs.
  • Results: 18 discoveries on average versus 9 for WTCCC (2007), doubling the reported power.Knockoffs were run repeatedly at a nominal FDR level of 10%.
  • Results: Several knockoff discoveries were absent from both earlier analyses, including candidates whose nearby genes had independent links to Crohn’s disease.Examples included rs6601764 near KLF6 and rs4692386 near RBP-J.

8 Discussion

The discussion presents model-X knockoffs as a general variable-selection framework with finite-sample Type I error control in high-dimensional nonlinear models. It also identifies unresolved challenges in knockoff construction, feature-statistic power, correlated settings, and computational cost.

  • Contributions: The framework selects important variables in general non-parametric models while guaranteeing Type I error control without constructing p-values.The authors describe this as a rethinking of the earlier knockoff filter.
  • Limitations: Highly correlated covariates may lack enough resolution to determine which individual variable the response depends on, making SNP-level FDR less meaningful.The discussion points to co-located SNPs in the Crohn’s disease analysis as an example.
  • Open questions: Constructing model-X knockoffs for practical non-Gaussian feature distributions remains an open problem.The paper presents a general strategy but gives concrete construction details mainly for Gaussian covariates.
  • Open questions: Choosing the dependence between original and knockoff variables remains unresolved even for Gaussian covariates.The authors discuss marginal correlations, partial correlations, and mutual information as possible criteria.
  • Limitations: Theoretical guarantees rely on knowing the joint covariate distribution, although preliminary experiments found robustness when it was estimated.The authors call for theoretical understanding of this robustness.
  • Open questions: The choice of feature-importance statistic remains important because the knockoff framework delegates power to the statistician’s W_j.The discussion calls for statistics with higher power.
  • Limitations: Conditional randomization testing offers an alternative FDR-control method but is currently computationally prohibitive for large problems.Suggested improvements include importance sampling, faster statistics, and computation reuse.
  • Conclusion: The paper concludes that reliable feature selection in high-dimensional nonlinear models remains a fundamental problem with substantial work still ahead.The authors emphasize that much remains to be done.

A Relationship with the knockoffs of Barber and Cand`es

Model-X knockoffs replace the fixed-design covariance perspective of Barber and Candès with a population-distribution perspective for random covariates. Consequently, their exchangeability requirement concerns the population covariance rather than the sample covariance.

  • Comparison: Barber and Candès treat the design matrix as fixed and set Σ = X⊤X when constructing knockoffs.Their construction uses the sample covariance of the observed design.
  • Comparison: Model-X knockoffs require invariance of the population covariance, so their knockoffs generally do not satisfy the same X⊤X relationship.The distinction follows from treating covariates as random rather than fixed.

B Sequential conditional independent pairs algorithm

The sequential algorithm constructs knockoff variables one coordinate at a time and proves exchangeability inductively. Symmetry of the conditional construction preserves exchangeability for the current and previously generated pairs.

  • Algorithm: Algorithm 1 constructs knockoffs sequentially and proves the exchangeability property by induction on j.The proof is presented first for discrete covariates and extended to general distributions using Radon–Nikodym derivatives.
  • Proof invariant: After j steps, each pair X_k, X̃_k for k = 1, …, j is exchangeable in the joint distribution.This is the induction hypothesis used by the proof.
  • Proof: The base case holds because X_1 and X̃_1 have the same marginal distribution and are conditionally independent.This implies conditional exchangeability for the first pair.
  • Proof: The joint distribution after adding X̃_j is formed by multiplying its conditional PMF by the joint PMF from the previous step.The resulting expression is symmetric in the relevant original-knockoff pair.
  • Proof: Symmetry in X_j and X̃_j establishes exchangeability for the new pair, while symmetry of the previous joint PMF preserves earlier pairs.Thus the induction hypothesis continues after each sequential step.

C Bayesian knockoff statistics

The Bayesian variable-selection knockoff statistic is computed from posterior inclusion probabilities obtained with a Gibbs sampler under a model treating original and knockoff covariates as fixed.

  • A Gibbs sampler computes posterior probabilities for each original variable and its knockoff counterpart.The procedure treats X1, ..., Xp and their knockoffs as fixed.
  • The model requires only a very slight modification of the procedure in George and McCulloch (1997).
  • The Bayesian knockoff statistic is the difference between the posterior probabilities for the original and knockoff variables.For variable j, W_j = δ̂_j − δ̃̂_j.
  • The computation uses 500 Gibbs samples after 50 burn-in samples.

D Conditional randomization speedups

The conditional-randomization calculations use several shortcuts because the unmodified computation is extremely expensive. These shortcuts reduce work through fixed tuning, early stopping, and skipping unnecessary p-value calculations.

  • Roughly three years of serial computation time was required for Figure 4 even after speed-ups and shortcuts.
  • A fixed Lasso penalty replaced cross-validation after repeated simulations from the known amplitude-30 model made cross-validation too expensive.
  • Statistics equal to zero receive conditional-randomization p-values of one without further computation when their distribution has a point mass at its minimum.
  • The procedure used roughly 10,000 randomizations to achieve the p-value resolution suggested by the anticipated BHq cutoff.Randomizations were concentrated on only a few covariates, with early stopping for covariates unlikely to pass the cutoff.

E Robustness Simulations

The robustness simulations compare knockoffs using covariance estimates that combine or replace the true covariance matrix with empirical or graphical-Lasso estimates.

  • Figure 8 evaluates knockoffs using convex combinations of the true and empirical covariance matrices.
  • The Graph. Lasso condition uses a covariance estimate based on an inverse covariance fitted by graphical Lasso.Its penalty parameter is selected by 2-fold cross-validation on the log-likelihood.

F Genetic analysis of Crohn’s disease

The Crohn’s disease genetic analysis preprocesses SNP-array data by filtering variants and subjects, then mean-imputing remaining missing SNP values. Population structure was not adjusted for, following the original analysis.

  • SNPs were removed for low minor allele frequency, Hardy–Weinberg disequilibrium, excessive missingness, duplicate positions, or absent genetic-map positions.The thresholds were MAF < 1%, Hardy–Weinberg p-value < 0.01%, and more than 5% missing values.
  • Subjects missing more than 5% of values were removed.
  • Remaining missing values were replaced by the mean of the nonmissing values for each SNP.
  • The analysis did not adjust for population structure, following the original WTCCC analysis.

G Knockoffs with selection

This section verifies the knockoff exchangeability condition for a two-part construction used in Section 7. The verification relies on classical knockoffs for one independent sample set and identity knockoffs for the other.

  • Knockoff construction: Knockoffs for the second sample set use the ASDP construction, while the first sample set uses identity knockoffs, ˜ X(1) = X(1).This differs slightly from the knockoff construction described elsewhere in the paper.
  • Data split: The Section 7 data are split into two independent sample sets, with dimensions 983 × 71,145 and 3930 × 71,145.The first set selects cluster representatives; the second is used for the remaining construction.
  • Verification: The required exchangeability property holds for both sample sets: by construction for the second, and with exact equality for the first.For the identity knockoffs, exchangeability is immediate, and conditional independence from the response follows because X(1) determines ˜ X(1).
Loading 1610.02351v4…