KL-BSS: Rethinking optimality for neighbourhood selection in structural equation models

Abstract

We introduce a new method for neighbourhood selection in linear structural equation models that improves over classical methods such as best subset selection (BSS) and the Lasso. Our method, called KL-BSS, takes advantage of the existence of underlying structure in SEM -- even when this structure is unknown -- and is easily implemented using existing solvers. Under weaker eigenvalue conditions compared to BSS and the Lasso, KL-BSS can provably recover the support of linear models with fewer samples. We establish both the pointwise and minimax sample complexity for support recovery, which KL-BSS obtains. Extensive experiments on both real and simulated data confirm the improvements offered by KL-BSS. While it is well-known that the Lasso encounters difficulties under structured dependencies, it is less well-known that even BSS runs into trouble as well, and can be substantially improved. These results have implications for structure learning in graphical models, which often relies on neighbourhood selection as a subroutine.

References in corpus (15)

• Nearly unbiased variable selection under minimax concave penalty
• High-dimensional graphs and variable selection with the Lasso
• On the conditions used to prove oracle results for the Lasso
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• Lasso-type recovery of sparse representations for high-dimensional data
• High-dimensional variable selection
• Necessary and Sufficient Conditions on Sparsity Pattern Recovery
• CAM: Causal additive models, high-dimensional order search and penalized regression
• Geometry of the faithfulness assumption in causal inference
• Information theoretic bounds for Compressed Sensing
• Variable selection in high-dimensional linear models: partially faithful distributions and the PC-simple algorithm
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• UPS delivers optimal phase diagram in high-dimensional variable selection
• On Causal Discovery with Equal Variance Assumption
• Sparse Signal Processing with Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach