Fetching the paper…
Reading the bibliography…
Under a standard assumption in complexity theory (NP not in 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.
Sparse approximate solutions to linear systems
B. K. Natarajan · 1995
Earlier work this paper cites.
Regression shrinkage and selection via the Lasso
R. Tibshirani · 1996
Earlier work this paper cites.
Atomic decomposition by basis pursuit
S. S. Chen, D. L. Donoho, and M. A. Saunders · 1998
Earlier work this paper cites.
Aggregation for Gaussian regression
F. Bunea, A. Tsybakov, and M. Wegkamp · 2007
Earlier work this paper cites.
The Dantzig selector: statistical estimation when p p is much larger than n n
E. Candes and T. Tao · 2007
Earlier work this paper cites.
High-dimensional analysis of semidefinite relaxations for sparse principal component analysis
A. A. Amini and M. J. Wainwright · 2009
Earlier work this paper cites.
Computational Complexity: A Modern Approach
S. Arora and B. Barak · 2009
Earlier work this paper cites.
Simultaneous analysis of Lasso and Dantzig selector
P. J. Bickel, Y. Ritov, and A. B. Tsybakov · 2009
Cited alongside, same era.
Lasso-type recovery of sparse representations for high-dimensional data
N. Meinshausen and B. Yu · 2009
Cited alongside, same era.
On the conditions used to prove oracle results for the Lasso
S. A. Van De Geer and P. Bühlmann · 2009
Cited alongside, same era.
Restricted eigenvalue properties for correlated Gaussian designs
G. Raskutti, M. J. Wainwright, and B. Yu · 2010
Cited alongside, same era.
Non-asymptotic theory of random matrices: extreme singular values
M. Rudelson and R. Vershynin · 2010
Cited alongside, same era.
Fast rate and optimistic rate for ℓ 1 \ell_{1} -regularized regression
R. Foygel and N. Srebro · 2011
Optimal detection of sparse principal components in high dimensions
Q. Berthet and P. Rigollet · 2012
Later among the works it cites.
The convex geometry of linear inverse problems
V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky · 2012
Later among the works it cites.
A unified framework for high-dimensional analysis of M M -estimators with decomposable regularizers
S. Negahban, P. Ravikumar, M. J. Wainwright, and B. Yu · 2012
Later among the works it cites.
Simultaneously structured models with applications to sparse and low-rank matrices
S. Oymak, A. Jalali, M. Fazel, Y. C. Eldar, and B. Hassibi · 2012
Later among the works it cites.
Computational lower bounds for sparse PCA
Q. Berthet and P. Rigollet · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Minimax rates of estimation for high-dimensional linear regression over ℓ q \ell_{q} -balls
G. Raskutti, M. J. Wainwright, and B. Yu · 2011
Cited alongside, same era.
R. Krauthgamer, B. Nadler, and D. Vilenchik · 2013
Later among the works it cites.
Computational barriers in minimax submatrix detection
Z. Ma and Y. Wu · 2013
Later among the works it cites.