Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators

By Karim Lounici. 2008

252 citations recorded by the source corpus.

We derive the l! convergence rate simultaneously for Lasso and Dantzig estimators in a high-dimensional linear regression model under a mutual coherence assumption on the Gram matrix of the design and two di! erent assumptions on the noise: Gaussian noise and general noise with finite variance. Then we prove that simultaneously the thresholded Lasso and Dantzig estimators with a proper choice of the threshold enjoy a sign concentration property provided that the non-zero components of the target vector are not too small.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/3a5d83dece45016f7b7d701b31d4ada3b5246054

How researchers see this paper

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

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Minimax risks for sparse regressions: Ultra-high-dimensional phenomenons (2010, unknown): “The l1 penalization methods have also been analyzed for the inverse problem (P3) [8] and for support estimation (P4) [36, 49].”
Massachusetts Institute of Technology Department of Economics Working Paper Series Sparse Models and Methods for Optimal Instruments with an Application to Eminent Domain Sparse Models and Methods for Optimal Instruments with an Application to Eminent Domain (unknown): “For theoretical and simulation evidence regarding LASSO's performance see, for example, [8], [12], [13], [29], [11], [14], [32], [33], [34], [35], [41], [43], [45], [46], [47], and [4], among many others; for analogous results on Post-LASSO see [4]. is the number of instruments and n is the sample…”
Oracle Inequalities and Optimal Inference under Group Sparsity (2010, methodology): “Closest to our study is the paper [4], which relies upon a Restricted Eigenvalue (RE ) assumption as well as [21], which considered the problem of selection of sparsity pattern.”
A Selective Overview of Variable Selection in High Dimensional Feature Space (2009, unknown): “Lounici (2008) derives the L ∞ convergence rate and studies a sign concentration property simultaneously for the LASSO estimator and the Dantzig selector under a mutual coherence condition.”
Robust machine learning by median-of-means: Theory and practice (2017, result): “This was shown for example, in [14, 58, 93, 94, 65, 72, 90] for estimation and sparse oracle inequalities, in [64, 99, 6] for support recovery results; more results and references on LASSO can be found in the books [19, 44].”
High-dimensional covariance matrix estimation with missing observations (2012, background): “This recent paradigm where high-dimensional objects of interest admit in fact a small intrinsic dimension has produced spectacular results in several fields, such as compressed sensing where it is possible to recover s-sparse vectors of dimension p with only n = O (s log(ep/s)) measurements provided”
Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise (2011, methodology): “The MIP condition used in Lounici (2008) is µ 13 k for the Dantzig selector and µ 15 k for the LASSO.”
Rate Minimaxity of the Lasso and Dantzig Selector for the lq Loss in lr Balls (2010, background): “Lounici (2008) considered thresholding either the Lasso or the Dantzigselector under the stronger condition maxj 6=k |(Σ) jk| ≤ 1/{α(1+2ξ)|J”
Taking Advantage of Sparsity in Multi-Task Learning (2009, methodology): “Similar assumptions are standard in the literature on sign consistency (see, for example, [19] for more details and references).”
Sparse Models and Methods for Optimal Instruments With an Application to Eminent Domain (2012, background): “…Bunea, Tsybakov, and Wegkamp (2006, 2007a, 2007b), Candes and Tao (2007), Huang, Horowitz, and Wei (2010), Knight (2008), Koltchinskii (2009), Lounici (2008), Lounici, Pontil, Tsybakov, and van de Geer (2010), Meinshausen and Yu (2009), Rosenbaum and Tsybakov (2008), Tibshirani (1996), van…”
Asymptotic Properties of Lasso+mLS and Lasso+Ridge in Sparse High-dimensional Linear Regression (2013, background): “In addition, thresholded Lasso and Dantzig estimators were introduced in [31] and the authors proved their model selection consistency under less restrictive conditions on the decay rates of the nonzero regression coefficients.”
Structured sparsity through convex optimization (2011, background): “, Lv and Fan, 2009) – Fixing the Lasso: adaptive Lasso (Zou, 2006), relaxed Lasso (Meinshausen, 2008), thresholding (Lounici, 2008), Bolasso (Bach, 2008a), stability selection (Meinshausen and Bühlmann, 2008), Wasserman and Roeder (2009)”
ROBUST EMPIRICAL MEAN ESTIMATORS (2011, methodology): “We study the Lasso estimator of [31], which is a famous aggregation procedure extensively studied over the last few years (see for example [7, 11, 15, 17, 19, 24, 28, 34–36] and the references therein), using ℓ 1 -penalties.”