期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 67, 期 1, 页码 506-537出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2020.3025272
关键词
Approximate message passing (AMP); sorted l(1) regression; high-dimensional regression; state evolution
资金
- NSF DMS [1915932]
- NSF CCF [1849883]
- CAREER DMS [1847415]
- Wharton Dean's Research Fund
- NSF TRIPODS DATA-INSPIRE CCF [1934924]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1849883] Funding Source: National Science Foundation
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [1915932] Funding Source: National Science Foundation
This paper characterizes the SLOPE solution under Gaussian random designs through solving the problem using AMP, showing that the AMP iterates converge to the SLOPE solution asymptotically. The research provides a novel technique that offers both asymptotically sharp analysis and an algorithmic, flexible approach to understanding the SLOPE problem.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据