Some sharp performance bounds for least squares regression with L1 regularization
The Annals of StatisticsPublished 15 July 2009Open access
Tong Zhang
Citations108
SJR quartileQ1
SJR score4.77
SNIP3.13
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We derive sharp performance bounds for least squares regression with L<sub>1</sub> regularization from parameter estimation accuracy and feature selection quality perspectives. The main result proved for L<sub>1</sub> regularization extends a similar result in [Ann. Statist. 35 (2007) 2313–2351] for the Dantzig selector. It gives an affirmative answer to an open question in [Ann. Statist. 35 (2007) 2358–2364]. Moreover, the result leads to an extended view of feature selection that allows less restrictive conditions than some recent work. Based on the theoretical insights, a novel two-stage L<sub>1</sub>-regularization procedure with selective penalization is analyzed. It is shown that if the target parameter vector can be decomposed as the sum of a sparse parameter vector with large coefficients and another less sparse vector with relatively small coefficients, then the two-stage procedure can lead to improved performance.
Keywords
MathematicsEngineering
IEEE Transactions on Information TheoryDecoding by Linear Programming
7,181 Citations2005Emmanuel J. Candès, Terence Tao
F can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program) and numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted.
Communications on Pure and Applied MathematicsStable signal recovery from incomplete and inaccurate measurements
7,170 Citations2006Emmanuel J. Candès, Justin Romberg +1 more
It is shown that it is possible to recover x0 accurately based on the data y from incomplete and contaminated observations.
The Annals of StatisticsSimultaneous analysis of Lasso and Dantzig selector
2,536 Citations2009Peter J. Bickel, Ya’acov Ritov +1 more
It is shown that, under a sparsity scenario, the Lasso estimator and the Dantzig selector exhibit similar behavior and derive, in parallel, oracle inequalities for the prediction risk in the general nonparametric regression model as well as bounds on the l p estimation loss in the linear model.
The Annals of StatisticsHigh-dimensional graphs and variable selection with the Lasso
2,406 Citations2006Nicolai Meinshausen, Peter Bühlmann
It is shown that neighborhood selection with the Lasso is a computationally attractive alternative to standard covariance selection for sparse high-dimensional graphs and is hence equivalent to variable selection for Gaussian linear models.
IEEE Transactions on Information TheoryStable recovery of sparse overcomplete representations in the presence of noise
2,209 Citations2005David L. Donoho, Michael Elad +1 more
This paper establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system and shows that similar stability is also available using the basis and the matching pursuit algorithms.
arXiv (Cornell University)The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
1,725 Citations2005Candes, Emmanuel, Tao, Terence
Is it possible to estimate β reliably based on the noisy data y?
The Annals of StatisticsThe sparsity and bias of the Lasso selection in high-dimensional linear regression
494 Citations2008Cun-Hui Zhang, Jian Huang
It is proved that the sum of error squares for the mean response and the l α -loss for the regression coefficients converge at the best possible rates under the given conditions, and the logarithm of the number of variables can be of the same order as the sample size for certain random dependent designs.
The Annals of StatisticsLasso-type recovery of sparse representations for high-dimensional data
479 Citations2009Nicolai Meinshausen, Bin Yu
Even though the Lasso cannot recover the correct sparsity pattern, the estimator is still consistent in the ‘2-norm sense for fixed designs under conditions on (a) the number sn of non-zero components of the vector n and (b) the minimal singular values of the design matrices that are induced by selecting of order sn variables.
Computational Statistics & Data AnalysisRelaxed Lasso
462 Citations2006Nicolai Meinshausen
It is shown that the contradicting demands of an efficient computational procedure and fast convergence rates of the `2-loss can be overcome by a two-stage procedure, termed the relaxed Lasso.
The Annals of StatisticsHigh-dimensional generalized linear models and the lasso
396 Citations2008Sara A. van de Geer
A nonasymptotic oracle inequality is proved for the empirical risk minimizer with Lasso penalty for high-dimensional generalized linear models with Lipschitz loss functions, and the penalty is based on the coefficients in the linear predictor, after normalization with the empirical norm.
The Annals of StatisticsNear-ideal model selection by ℓ1 minimization
291 Citations2009Emmanuel J. Candès, Yaniv Plan
It is proved that solving a simple quadratic program achieves a squared error within a logarithmic factor of the ideal mean squared error that one would achieve with an oracle supplying perfect information about which variables should and should not be included in the model.
Electronic Journal of StatisticsSparsity oracle inequalities for the Lasso
240 Citations2007Florentina Bunea, Alexandre Tsybakov +1 more
It is shown that the penalized least squares estimator satisfies sparsity oracle inequalities, i.e., bounds in terms of the number of non-zero components of the oracle vector, in nonparametric regression setting with random design.
The Annals of StatisticsAggregation for Gaussian regression
172 Citations2007Florentina Bunea, Alexandre B. Tsybakov +1 more
arXiv (Cornell University)Sharp thresholds for high-dimensional and noisy recovery of sparsity
152 Citations2006Martin J. Wainwright
This work analyzes the behavior of $\ell_1$-constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern and establishes a sharp relation between the problem dimension $\mdim$ and the number of observations that are required for reliable recovery.
Annales de l Institut Henri Poincaré Probabilités et StatistiquesSparsity in penalized empirical risk minimization
130 Citations2009Vladimir Koltchinskii
BernoulliThe Dantzig selector and sparsity oracle inequalities
122 Citations2009Vladimir Koltchinskii
The Annals of StatisticsDiscussion: The Dantzig selector: Statistical estimation when p is much larger than n
76 Citations2007Bradley Efron, Trevor Hastie +1 more
There are tantalizing similarities between the Dantzig Selector (DS) and the LARS methods, but they are not the same and produce somewhat different models.
BiometrikaA generalized Dantzig selector with shrinkage tuning
69 Citations2009Gareth James, Peter Radchenko
The Dantzig selector is extended to fit generalized linear models while eliminating overshrinkage of the coefficient estimates, and a computationally efficient algorithm is developed to compute the entire path of coefficient estimates.