CHARACTERIZING THE SLOPE TRADE-OFF: A VARIATIONAL PERSPECTIVE AND THE DONOHO-TANNER LIMIT

• 成果类型: Article
• 署名作者: Bu, Zhiqi; Klusowski, Jason M.; Rush, Cynthia; Su, Weijie J.
• 署名单位: University of Pennsylvania; Princeton University; Columbia University; University of Pennsylvania
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/22-AOS2194
• 发表日期: 2023
• 页码: 33-61
• 关键词: optimization problems; unknown sparsity; Lasso; polytopes; selection

摘要

Sorted l(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 rel-atively new regularization technique improves variable selection by charac-terizing 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 work-ing under Gaussian random designs, we obtain an upper bound on the op-timal 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 l(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 l(1) regulariza-tion in optimally trading the FDP off for the TPP. Finally, we show that on any problem instance, SLOPE with a certain regularization sequence out-performs the Lasso, in the sense of having a smaller FDP, larger TPP and smaller l(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 ap-proximate message passing theory.