Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing
Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing
复制标题
DOI：
10.1109/tit.2020.3025272
复制
发表时间：
2021-01-01
影响因子：
2.5
通讯作者：
Su, Weijie J.
中科院分区：
文献类型：
--
作者：
Bu, Zhiqi;Klusowski, Jason M.;Su, Weijie J.
SLOPE是一个相对较新的凸优化过程，用于高维线性回归，通过排序的l（1）惩罚：拟合系数的秩越大，惩罚越大。这种不可分离的惩罚使得许多现有技术在分析SLOPE解决方案时无效或不确定。在本文中，我们通过使用近似消息传递（AMP）解决SLOPE问题，在高斯随机设计下的SLOPE解的渐近精确的特征。这种算法方法使我们能够通过更可靠的AMP迭代来近似SLOPE解决方案。解释，我们的AMP迭代的渐近动力学的特征依赖于最近开发的状态演化分析不可分离的处罚，从而克服了排序的l（1）处罚所造成的困难。此外，我们证明了AMP迭代收敛到SLOPE解的渐近意义下，数值模拟表明，收敛速度是惊人的快。我们的证明依赖于一种专门利用SLOPE问题的新技术。与以前的文献相比，我们的工作不仅产生了一个渐进尖锐的分析，但也提供了一个算法，灵活，建设性的方法来理解的斜坡问题。
SLOPE is a relatively new convex optimization procedure for high- dimensional linear regression via the sorted l(1) penalty: the larger the rank of the fitted coefficient, the larger the penalty. This non-separable penalty renders many existing techniques invalid or inconclusive in analyzing the SLOPE solution. In this paper, we develop an asymptotically exact characterization of the SLOPE solution under Gaussian random designs through solving the SLOPE problem using approximate message passing (AMP). This algorithmic approach allows us to approximate the SLOPE solution via the much more amenable AMP iterates. Explicitly, we characterize the asymptotic dynamics of the AMP iterates relying on a recently developed state evolution analysis for non-separable penalties, thereby overcoming the difficulty caused by the sorted l(1) penalty. Moreover, we prove that the AMP iterates converge to the SLOPE solution in an asymptotic sense, and numerical simulations show that the convergence is surprisingly fast. Our proof rests on a novel technique that specifically leverages the SLOPE problem. In contrast to prior literature, our work not only yields an asymptotically sharp analysis but also offers an algorithmic, flexible, and constructive approach to understanding the SLOPE problem.