Sorted l1 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 l1-based method, can achieve even with arbitrarily strong effect sizes. Next, we derive a tight lower bound that delineates the fundamental limit of sorted l1 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 l2 estimation risk simultaneously. Our proofs are based on a novel technique that reduces a variational calculus problem to a class of infinite-dimensional convex optimization problems and a very recent result from approximate message passing theory.
翻译:在本文中,我们研究了这一相对较新的正规化技术如何通过将虚假发现比例(FDP)与真实正比(TPP)之间的最佳 SLOPE 权衡(TPP),或相当于第一类误差和强力等量之间的最佳 SLOPE 权衡(TPP),从而改进了变量选择。我们假设了线性宽度制度,并在高斯随机设计下工作,我们获得了关于SLOPE最佳交易的上限,展示了它打破多诺-丹纳电限的能力。在本文中,我们研究这一相对较新的正规化技术如何通过描述虚假发现比例(FDP)与真实正比(TPP)之间的最佳权衡(SLOPE)之间的最佳权衡(SLOPE ), 展示了它打破多诺- 坦纳电限的能力。要将其引入视角,这一限制是拉索(可能是最受欢迎的 L1 ), 甚至最受欢迎的方法(TP) 能够以任意强大的效果大小的比值实现。我们FPPA 的更小的精确度估计, 将一个小的比值降低了我们LASOLOUULI 的理论, 将降低了我们FDP 的比值。