Variable Selection is Hard

Abstract

Variable selection for sparse linear regression is the problem of finding, given an m x p matrix B and a target vector y, a sparse vector x such that Bx approximately equals y. Assuming a standard complexity hypothesis, we show that no polynomial-time algorithm can find a k'-sparse x with ||Bx-y||^2<=h(m,p), where k'=k*2^{log^{1-delta} p} and h(m,p)<=p^(C_1)*m^(1-C_2), where delta>0, C_1>0,C_2>0 are arbitrary. This is true even under the promise that there is an unknown k-sparse vector x^* satisfying Bx^*=y. We prove a similar result for a statistical version of the problem in which the data are corrupted by noise. To the authors' knowledge, these are the first hardness results for sparse regression that apply when the algorithm simultaneously has k'>k and h(m,p)>0.

References in corpus (2)

• On the conditions used to prove oracle results for the Lasso
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression

Cited by in corpus (8)

• Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions
• Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
• Best subset selection is robust against design dependence
• Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP
• Approximate Guarantees for Dictionary Learning
• Optimal Sketching Bounds for Sparse Linear Regression
• Online Sparse Linear Regression
• Local Search Algorithms for Rank-Constrained Convex Optimization