Slope meets Lasso: Improved oracle bounds and optimality

By Pierre C. Bellec, Guillaume Lecué, Alexandre B. Tsybakov. Annals of Statistics, 2016

201 citations recorded by the source corpus.

We show that two polynomial time methods, a Lasso estimator with adaptively chosen tuning parameter and a Slope estimator, adaptively achieve the exact minimax prediction and $\ell_2$ estimation rate $(s/n)\log (p/s)$ in high-dimensional linear regression on the class of $s$-sparse target vectors in $\mathbb R^p$. This is done under the Restricted Eigenvalue (RE) condition for the Lasso and under a slightly more constraining assumption on the design for the Slope. The main results have the form of sharp oracle inequalities accounting for the model misspecification error. The minimax optimal bounds are also obtained for the $\ell_q$ estimation errors with $1\le q\le 2$ when the model is well-specified. The results are non-asymptotic, and hold both in probability and in expectation. The assumptions that we impose on the design are satisfied with high probability for a large class of random matrices with independent and possibly anisotropically distributed rows. We give a comparative analysis of conditions, under which oracle bounds for the Lasso and Slope estimators can be obtained. In particular, we show that several known conditions, such as the RE condition and the sparse eigenvalue condition are equivalent if the $\ell_2$-norms of regressors are uniformly bounded.

Subfields: Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/fbcb62a2c9f3f06c62dea5eab209aa5e83e2fbd1

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

Learning from MOM’s principles: Le Cam’s approach (2017, background): “• Estimation rates achieved by MOM-LASSO are the actual minimax rates s log( ed/s ) /N , see Bellec et al. (2016), while classical LASSO estimators achieve the rate s log( ed ) /N .”
The Spike-and-Slab LASSO (2018, methodology): “Although our current proving technique did not allow us to obtain exact minimax rates even when q is known, different approaches may prove fruitful in this regard, see, for example, Su and Candes (2016) and Bellec, Lecue, and Tsybakov (2016).”
Regularization, sparse recovery, and median-of-means tournaments (2017, methodology): “The analysis of the lasso and slope procedures of [7] was extended and generalized by Bellec, Lecu´e, and Tsybakov [2].”
Adaptive Huber Regression (2017, background): “As pointed out by a reviewer, if one pursues a sparsity-adaptive approach, such as the SLOPE (Bogdan et al. 2015; Bellec, Lecué, and Tsybakov 2018), the upper bound on (cid:5) 2 -error can be improved from (cid:25) s log ( d )/ n to (cid:25) s log ( ed / s )/ n .”
Robust machine learning by median-of-means: Theory and practice (2017, background): “Theoretical properties of MOM LASSO (cf. Theorem 5) outperform those of LASSO (cf. Theorem 3) in several ways: • Estimation rates achieved by MOM-LASSO are the actual minimax rates s log( ed/s ) /N , see [13], while classical LASSO estimators achieve the rate s log( ed ) /N .”
Penalized Estimation in Additive Regression with High-Dimensional Data (2017, methodology): “wing maximal inequality can be obtained from van de Geer (2000, Corollary 8.3), or directly derived using Dudley’s inequality for sub-gaussian variables and Chernoﬀ’s tail bound (see Proposition 9.2, Bellec et al. 2016). Lemma 12. For δ>0, let F1 be a functional class such that supf 1∈F1 kf1kn ≤ ”