Variable Selection is Hard

The distribution of rademacher sums

S. J. Montgomery-Smith · 1990

Earlier work this paper cites.

Efficient probabilistic checkable proofs and applications to approximation

M. Bellare, S. Goldwasser, C. Lund, and A. Russell · 1994

Earlier work this paper cites.

The risk inflation criterion for multiple regression

D. P. Foster and E. I. George · 1994

Earlier work this paper cites.

On the hardness of approximating minimization problems

C. Lund and M. Yannakakis · 1994

Earlier work this paper cites.

Sparse approximate solutions to linear systems

B. K. Natarajan · 1995

Earlier work this paper cites.

A parallel repetition theorem

R. Raz · 1995

Earlier work this paper cites.

The hardness of approximate optima in lattices, codes, and systems of linear equations

S. Arora, L. Babai, J. Stern, and Z. Sweedyk · 1997

Cited alongside, same era.

Adaptive greedy approximations

G. Davis, S. Mallat, and M. Avellaneda · 1997

Cited alongside, same era.

Approximation Algorithms for NP-hard Problems

D. S. Hochbaum, editor · 1997

Cited alongside, same era.

On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems

E. Amaldi and V. Kann · 1998

Cited alongside, same era.

A threshold of ln n for approximating set cover

U. Feige · 1998

Cited alongside, same era.

Atomic decomposition by basis pursuit

S. S. Chen, D. L. Donoho, and M. A. Saunders · 2001

Cited alongside, same era.

On the difference between orthogonal matching pursuit and orthogonal least squares

T. Blumensath and M. E. Davies · 2007

Later among the works it cites.

Data stream algorithms

S. Muthukrishnan · 2009

Later among the works it cites.

The projection games conjecture and the np-hardness of ln n-approximating set-cover

D. Moshkovitz · 2012

Later among the works it cites.

A note on the hardness of sparse approximation

A. Çivril · 2013

Later among the works it cites.

Analytical approach to parallel repetition

I. Dinur and D. Steurer · 2014

Closest in time.

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

Original

Y. Zhang, M. J. Wainwright, and M. I. Jordan · 2014

Closest in time.