FANOK: Knockoffs in Linear Time.

TITLE: FANOK: Knockoffs in Linear Time.

AUTHORS: Armin Askari, Quentin Rebjock, Alexandre d'Aspremont, Laurent El Ghaoui.

ABSTRACT: We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems. Identifying the knockoff distribution requires solving a large scale semidefinite program for which we derive several efficient methods. One handles generic covariance matrices, has a complexity scaling as O(p^3) where p is the ambient dimension, while another assumes a rank k factor model on the covariance matrix to reduce this complexity bound to O(pk^2). We also derive efficient procedures to both estimate factor models and sample knockoff covariates with complexity linear in the dimension. We test our methods on problems with p as large as 500,000.

STATUS: Preprint.

ArXiv PREPRINT: 2006.08790