Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing

DOI10.1109/TIT.2020.3025272MaRDI QIDQ5151728zbMATH OpenOpenAlexFDO

Authors Zhiqi Bu, Jason M. Klusowski, Cynthia Rush, Weijie J. Su

Publication date 22 February 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.07502

zbMATH Keywords

approximate message passing (AMP)convex optimization procedurehigh-dimensional linear regressionSLOPE

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Ridge regression; shrinkage estimators (Lasso) (62J07) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: SLOPE is a relatively new convex optimization procedure for high-dimensional linear regression via the sorted l1 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 l1 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.

Cited in

(13)

• Precise statistical analysis of classification accuracies for adversarial training
• Fundamental barriers to high-dimensional regression with convex penalties
• Approximate message passing algorithms for rotationally invariant matrices
• Proximal operator for the sorted \(\ell_1\) norm: application to testing procedures based on SLOPE
• A Unifying Tutorial on Approximate Message Passing
• Characterizing the SLOPE trade-off: a variational perspective and the Donoho-Tanner limit
• Debiasing convex regularized estimators and interval estimation in linear models
• Universality of approximate message passing algorithms and tensor networks
• Spectral estimators for structured generalized linear models via approximate message passing
• Entrywise dynamics and universality of general first order methods
• A leave-one-out approach to approximate message passing
• Unveiling low-dimensional patterns induced by convex non-differentiable regularizers
• A nonasymptotic distributional theory of approximate message passing for sparse and robust regression

This page was built for publication: Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5151728)