Slope meets lasso: Improved oracle bounds and optimality

TY - JOUR

T1 - Slope meets lasso

T2 - Improved oracle bounds and optimality

AU - Bellec, Pierre C.

AU - Lecué, Guillaume

AU - Tsybakov, Alexandre B.

N1 - Funding Information: Supported by GENES and by the French National Research Agency (ANR) under the Grants IPANEMA (ANR-13-BSH1-0004-02) and Labex Ecodec (ANR-11-LABEX-0047). It was also supported by the “Chaire Economie et Gestion des Nouvelles Données,” under the auspices of Institut Louis Bachelier, Havas-Media and Paris-Dauphine. Funding Information: Received May 2016; revised May 2017. 1Supported by GENES and by the French National Research Agency (ANR) under the Grants IPANEMA (ANR-13-BSH1-0004-02) and Labex Ecodec (ANR-11-LABEX-0047). It was also supported by the “Chaire Economie et Gestion des Nouvelles Données,” under the auspices of Institut Louis Bachelier, Havas-Media and Paris-Dauphine. MSC2010 subject classifications. Primary 60K35, 62G08; secondary 62C20, 62G05, 62G20. Key words and phrases. Sparse linear regression, minimax rates, high-dimensional statistics, Slope, Lasso. Publisher Copyright: © Institute of Mathematical Statistics, 2018.

PY - 2018

Y1 - 2018

N2 - We show that two polynomial time methods, a Lasso estimator with adaptively chosen tuning parameter and a Slope estimator, adaptively achieve the minimax prediction and2 estimation rate (s/n)log(p/s) in high-dimensional linear regression on the class of s-sparse vectors in Rp. 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 theq estimation errors with 1 ≤ q ≤ 2 when the model is well specified. The results are nonasymptotic, 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 2-norms of regressors are uniformly bounded.

AB - We show that two polynomial time methods, a Lasso estimator with adaptively chosen tuning parameter and a Slope estimator, adaptively achieve the minimax prediction and2 estimation rate (s/n)log(p/s) in high-dimensional linear regression on the class of s-sparse vectors in Rp. 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 theq estimation errors with 1 ≤ q ≤ 2 when the model is well specified. The results are nonasymptotic, 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 2-norms of regressors are uniformly bounded.

KW - High-dimensional statistics

KW - Lasso

KW - Minimax rates

KW - Slope

KW - Sparse linear regression

UR - http://www.scopus.com/inward/record.url?scp=85054152682&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054152682&partnerID=8YFLogxK

U2 - https://doi.org/10.1214/17-AOS1670

DO - https://doi.org/10.1214/17-AOS1670

M3 - Article

SN - 0090-5364

VL - 46

SP - 3603

EP - 3642

JO - Annals of Statistics

JF - Annals of Statistics

IS - 6B

ER -