FANOK: knockoffs in linear time

DOI10.1137/20M1363698MaRDI QIDQ5154638zbMATH OpenOpenAlexFDO

Authors

Publication date 5 October 2021

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.08790

zbMATH Keywords

convex optimizationcoordinate descentfalse discovery rateFast Knockoffs (FANOK)semidefinite programming

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Parametric hypothesis testing (62F03) Statistical ranking and selection procedures (62F07) Semidefinite programming (90C22) Convex programming (90C25)

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(p{k}^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$.

Recommendations

• Controlling the false discovery rate via knockoffs
• Robust inference with knockoffs
• Powerful knockoffs via minimizing reconstructability
• Relaxing the assumptions of knockoffs by conditioning
• Metropolized Knockoff Sampling

Cites work

• A knockoff filter for high-dimensional selective inference
• A Note on the Stability of Solving a Rank-p Modification of a Linear System by the Sherman–Morrison–Woodbury Formula
• A well-conditioned estimator for large-dimensional covariance matrices
• An Interior-Point Method for Semidefinite Programming
• Block coordinate descent methods for semidefinite programming
• Conic optimization via operator splitting and homogeneous self-dual embedding
• Controlling the false discovery rate via knockoffs
• CVXPY: a Python-embedded modeling language for convex optimization
• Exact post-selection inference, with application to the Lasso
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• First-Order Methods for Sparse Covariance Selection
• Hierarchical clustering schemes
• scientific article; zbMATH DE number 720689 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Inferential Theory for Factor Models of Large Dimensions
• Panning for Gold: ‘Model-X’ Knockoffs for High Dimensional Controlled Variable Selection
• Practical sketching algorithms for low-rank matrix approximation
• Scikit-learn: machine learning in Python
• Valid post-selection inference
• Why Are Big Data Matrices Approximately Low Rank?

Cited in

(4)

• Powerful knockoffs via minimizing reconstructability
• RANK: Large-Scale Inference With Graphical Nonlinear Knockoffs
• IPAD: stable interpretable forecasting with knockoffs inference
• Controlling the false discovery rate via knockoffs

Describes a project that uses

Uses Software

• Scikit
• CVXPY
• FANOK
• SCS

This page was built for publication: FANOK: knockoffs in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5154638)