Fetching the paper…

Reading the bibliography…

2011

Fast-rate and optimistic-rate error bounds for L1-regularized regression

Foygel, Rina, Srebro, Nathan

Original
PDF
Post on X

Understand

We consider the prediction error of linear regression with L1 regularization when the number of covariates p is large relative to the sample size n.

When the model is k-sparse and well-specified, and restricted isometry or similar conditions hold, the excess squared-error in prediction can be bounded on the order of sigma^2*(k*log(p)/n), where sigma^2 is the noise variance.
Although these conditions are close to necessary for accurate recovery of the true coefficient vector, it is possible to guarantee good predictive accuracy under much milder conditions, avoiding the restricted isometry condition, but only ensuring an excess error bound of order (k*log(p)/n)+sigma*\surd(k*log(p)/n).
Here we show that this is indeed the best bound possible (up to logarithmic factors) without introducing stronger assumptions similar to restricted isometry.

Fast-rate and optimistic-rate error bounds for L1-regularized regression · Around

Built on

Regression shrinkage and selection via the lasso
Original
R. Tibshirani · 1996
Earlier work this paper cites.
Adaptive estimation of a quadratic functional by model selection
B. Laurent and P. Massart · 2000
Earlier work this paper cites.
Boosting as a regularized path to a maximum margin classifier
S. Rosset, J. Zhu, and T. Hastie · 2004
Earlier work this paper cites.
Decoding by linear programming
E.J. Candes and T. Tao · 2005
Earlier work this paper cites.

Similar

Simultaneous analysis of Lasso and Dantzig selector
P.J. Bickel, Y. Ritov, and A.B. Tsybakov · 2009
Cited alongside, same era.
On recovery of sparse signals via ℓ 1 \ell_{1} minimization
T.T. Cai, G. Xu, and J. Zhang · 2009
Cited alongside, same era.
The Dantzig selector and sparsity oracle inequalities
V. Koltchinskii · 2009
Cited alongside, same era.

Then

Extended Bayesian information criteria for Gaussian graphical models
R. Foygel and M. Drton · 2010
Later among the works it cites.
Matrix completion from noisy entries
R.H. Keshavan, A. Montanari, and S. Oh · 2010
Later among the works it cites.
Smoothness, low noise and fast rates
N. Srebro, K. Sridharan, and A. Tewari · 2010
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…