Some sharp performance bounds for least squares regression with L1 regularization

By Tong Zhang. 2009

271 citations recorded by the source corpus.

We derive sharp performance bounds for least squares regression with L regularization from parameter estimation accuracy and feature selection quality perspectives. The main result proved for L 1 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 1 -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.

Subfields: Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/7ca8cf88e94390f48660e402b7dfadb90a319ee0

How researchers see this paper

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

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

ℓ1-penalization for mixture regression models (2010, background): “ Meinshausen and Bu¨hlmann,2006;Zhao and Yu, 2006;Bunea et al.,2007; Zhang and Huang, 2008; Meinshausen and Yu, 2009; Wainwright, 2009; Bickel et al., 2009; Cai et al., 2009b; Cand`es and Plan, 2009; Zhang, 2009) or the negative log-likelihood in a generalized linear model (van de Geer, 2008). We pr”
A Probabilistic and RIPless Theory of Compressed Sensing (2010, background): “This literature is, of course, extremely large and we cannot cite all contributions but a partial list would include [15], [21], [46], [13], [16], [5], [19], [50], [51], [3], [37], [29], [7], [2].”
Assumptionless consistency of the Lasso (2013, background): “[5, 6], Candès and Tao [7, 8], Zhang and Huang [32], Lounici [21], Bickel et. al.”
Sparse recovery under matrix uncertainty (2008, unknown): “The Annals of Statistics 2010, Vol. 38, No. 5, 2620–2651 DOI: 10.1214/10-AOS793 © Institute of Mathematical Statistics, 2010”
Group Regularized Estimation Under Structural Hierarchy (2014, background): “he result is of the type of Lounici (2008) and Ravikumar et al. (2010), but we do not have to assume the stringent irrepresentable conditions or mutual coherence conditions. For more discussions, see Zhang (2009). Assumption C(J e;J G;; 1; 2). Given J eˆ[p2], J Gˆ[p], 0, 1; 2 > 0, for any = [ b;”
Visual classification with multi-task joint sparse representation (2010, background): “Olshausen et al. [16] introduced a Bayesian framework to simulate the sparse coding mechanism of human vision system.”
Confidence intervals for low dimensional parameters in high dimensional linear models (2011, methodology): “…to verify condition (20) for various regularized estimators of β under different sets of conditions on X and β (Candès and Tao, 2007; Zhang and Huang, 2008; Bickel et al., 2009; van de Geer and Bühlmann, 2009; Zhang, 2009, 2010; Ye and Zhang, 2010; Sun and Zhang, 2012; Zhang and Zhang, 2012).”
Loss Minimization and Parameter Estimation with Heavy Tails (2013, methodology): “Standard analyses of sparse estimation with mean-zero noise assume light-tailed noise (Zhang, 2009; Bickel et al., 2009).”
Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models (2008, methodology): “The prediction performance of this method has been considered in [6, 2, 1, 9].”
A multi-task learning formulation for predicting disease progression (2011, methodology): “To resolve this problem, existing methods apply adaptive regularization [42], multiple thresholding procedures [41], or multistage methods [23, 40].”
A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem (2012, background): “2) achieves optimal error bound under stochastic noise model by picking λ of the order ‖AT z‖∞ [12, 46, 47, 6, 24, 42, 43].”
Asymptotic normality and optimalities in estimation of large Gaussian graphical models (2013, methodology): “Another ap- proach is to control the sparse ℓ2 norm of Z̃ to allow smaller penalty levels in the analysis; See Zhang (2009) and Ye and Zhang (2010) for analyses of the lasso and Sun and Zhang (2013) for an analysis of the scaled estimators (54) and (55).”
On the Consistency of Feature Selection using Greedy Least Squares Regression (2009, background): “The lnd factor (bias) is inherent to Lasso, which can be removed with two-stage procedures (e.g., Zhang, 2009).”
ℓ1-regularized linear regression: persistence and oracle inequalities (2011, background): “The first of these properties has been studied, for example, in [12, 39, 17, 4, 7, 21, 16] while the latter two are studied in [5, 41, 42, 26, 25, 23, 11, 7, 24, 21].”
Performance bounds for parameter estimates of high-dimensional linear models with correlated errors (2016, unknown): “See also [6, 28, 48, 49] for related conditions.”