TY - JOUR
T1 - CHARACTERIZING THE SLOPE TRADE-OFF
T2 - A VARIATIONAL PERSPECTIVE AND THE DONOHO–TANNER LIMIT
AU - Bu, Zhiqi
AU - Klusowski, Jason M.
AU - Rush, Cynthia
AU - Su, Weijie J.
N1 - Funding Information:
Funding. Weijie Su was supported in part by NSF through CAREER DMS-1847415 and CCF-1934876, an Alfred Sloan Research Fellowship, and the Wharton Dean’s Research Fund. Cynthia Rush was supported by NSF through CCF-1849883 and this work was done in part while the author was visiting the Simons Institute for the Theory of Computing. Jason M. Klusowski was supported in part by NSF through DMS-2054808 and HDR TRIPODS DATA-INSPIRE DCCF-1934924.
Publisher Copyright:
© Institute of Mathematical Statistics, 2023.
PY - 2023/2
Y1 - 2023/2
N2 - Sorted ℓ1 regularization has been incorporated into many methods for solving high-dimensional statistical estimation problems, including the SLOPE estimator in linear regression. In this paper, we study how this relatively new regularization technique improves variable selection by characterizing the optimal SLOPE trade-off between the false discovery proportion (FDP) and true positive proportion (TPP) or, equivalently, between measures of type I error and power. Assuming a regime of linear sparsity and working under Gaussian random designs, we obtain an upper bound on the optimal trade-off for SLOPE, showing its capability of breaking the Donoho–Tanner power limit. To put it into perspective, this limit is the highest possible power that the Lasso, which is perhaps the most popular ℓ1-based method, can achieve even with arbitrarily strong effect sizes. Next, we derive a tight lower bound that delineates the fundamental limit of sorted ℓ1 regularization in optimally trading the FDP off for the TPP. Finally, we show that on any problem instance, SLOPE with a certain regularization sequence outperforms the Lasso, in the sense of having a smaller FDP, larger TPP and smaller ℓ2 estimation risk simultaneously. Our proofs are based on a novel technique that reduces a calculus of variations problem to a class of infinite-dimensional convex optimization problems and a very recent result from approximate message passing theory.
AB - Sorted ℓ1 regularization has been incorporated into many methods for solving high-dimensional statistical estimation problems, including the SLOPE estimator in linear regression. In this paper, we study how this relatively new regularization technique improves variable selection by characterizing the optimal SLOPE trade-off between the false discovery proportion (FDP) and true positive proportion (TPP) or, equivalently, between measures of type I error and power. Assuming a regime of linear sparsity and working under Gaussian random designs, we obtain an upper bound on the optimal trade-off for SLOPE, showing its capability of breaking the Donoho–Tanner power limit. To put it into perspective, this limit is the highest possible power that the Lasso, which is perhaps the most popular ℓ1-based method, can achieve even with arbitrarily strong effect sizes. Next, we derive a tight lower bound that delineates the fundamental limit of sorted ℓ1 regularization in optimally trading the FDP off for the TPP. Finally, we show that on any problem instance, SLOPE with a certain regularization sequence outperforms the Lasso, in the sense of having a smaller FDP, larger TPP and smaller ℓ2 estimation risk simultaneously. Our proofs are based on a novel technique that reduces a calculus of variations problem to a class of infinite-dimensional convex optimization problems and a very recent result from approximate message passing theory.
KW - SLOPE
KW - approximate message passing
KW - false discovery rate
KW - phase transition
KW - sorted ℓ regularization
KW - true positive rate
UR - http://www.scopus.com/inward/record.url?scp=85151069966&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85151069966&partnerID=8YFLogxK
U2 - 10.1214/22-AOS2194
DO - 10.1214/22-AOS2194
M3 - Article
AN - SCOPUS:85151069966
SN - 0090-5364
VL - 51
SP - 33
EP - 61
JO - Annals of Statistics
JF - Annals of Statistics
IS - 1
ER -