  Model-X knockoffs is a wrapper that transforms essentially any feature
importance measure into a variable selection algorithm, which discovers true
effects while rigorously controlling the expected fraction of false positives.
A frequently discussed challenge to apply this method is to construct knockoff
variables, which are synthetic variables obeying a crucial exchangeability
property with the explanatory variables under study. This paper introduces
techniques for knockoff generation in great generality: we provide a sequential
characterization of all possible knockoff distributions, which leads to a
Metropolis-Hastingsformulation of an exact knockoff sampler. We further show
how to use conditional independence structure to speed up computations.
Combining these two threads, we introduce an explicit set of sequential
algorithms and empirically demonstrate their effectiveness. Our theoretical
analysis proves that our algorithms achieve near-optimal computational
complexity in certain cases. The techniques we develop are sufficiently rich to
enable knockoff sampling in challenging models including cases where the
covariates are continuous and heavy-tailed, and follow a graphical model such
as the Ising model.
