Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing

SLOPE is a relatively new convex optimization procedure for high-dimensional linear regression via the sorted \ell _{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 t...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2021-01, Vol.67 (1), p.506-537
Main Authors: Bu, Zhiqi, Klusowski, Jason M., Rush, Cynthia, Su, Weijie J.
Format: Article
Language:English
Subjects:
Algorithms
Approximate message passing (AMP)
Approximation algorithms
Asymptotic properties
Computational geometry
Convergence
Convexity
Electronic mail
Estimation
Fines & penalties
high-dimensional regression
Message passing
Optimization
Regression analysis
sorted <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">ℓ ₁ regression
state evolution
Statistical analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:SLOPE is a relatively new convex optimization procedure for high-dimensional linear regression via the sorted \ell _{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 \ell _{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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2020.3025272