Lower bounds on the performance of polynomial-time algorithms for sparse linear regression

By Yuchen Zhang, Martin J. Wainwright, Michael I. Jordan. 2014

135 citations recorded by the source corpus.

Under a standard assumption in complexity theory (NP 6⊂P/poly), we demonstrate a gap between the minimax prediction risk for sparse linear regression that can be achieved by polynomial-time algorithms, and that achieved by optimal algorithms. In particular, when the design matrix is ill-conditioned, the minimax prediction loss achievable by polynomial-time algorithms can be substantially greater than that of an optimal algorithm. This result is the first known gap between polynomial and optimal algorithms for sparse linear regression, and does not depend on conjectures in average-case complexity.

Subfields: Artificial Intelligence, Computational Mechanics, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Signal Processing

Citations in the corpus

On Bayes Risk Lower Bounds (2014, unknown): “We denote the chi-squared divergence by simply χ 2 ( P || Q ) as opposed to D f 2 ( P || Q ).”
Provable Meta-Learning of Linear Representations (2020, background): “Even in this setting, a gap remains with respect to condition number/eigenvalue factors of the data design matrix X, between existing upper and lower bounds (see Chen et al. (2016, Section 7), Raskutti et al. (2011, Theorem 1, Theorem 2) and Zhang et al. (2014) for example).”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, background): “A related line of work establishes statistical-computational tradeoffs for sparse PCA [BR13a, BR13b, MW15, WBS16], and sparse linear regression [ZWJ14] based on various hardness assumptions.”
Minimax rates for memory-bounded sparse linear regression (2015, background): “…polynomial-time procedures increases sample complexity for several problems, including sparse principal components analysis (Berthet and Rigollet, 2013) classification problems (Daniely et al., 2013, 2014), and, pertinent to this work, sparse linear regression (Zhang et al., 2014; Natarajan, 1995).”