# Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing

arXiv: https://arxiv.org/abs/1907.07502 · HTML: https://mlsanity.com/paper/1907.07502/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jul 2019.

## Built on by (most cited first, 14 of 14)

- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Minimum ℓ1-norm interpolators: Precise asymptotics and multiple descent](https://mlsanity.com/paper/2110.09502/) (2021)
- [Safe rules for the identification of zeros in the solutions of the SLOPE problem](https://mlsanity.com/paper/2110.11784/) (2021)
- [A New Central Limit Theorem for the Augmented IPW Estimator: Variance Inflation, Cross-Fit Covariance and Beyond](https://mlsanity.com/paper/2205.10198/) (2022)
- [Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings](https://mlsanity.com/paper/2402.08543/) (2024)
- [Characterizing the SLOPE Trade-off: A Variational Perspective and the Donoho-Tanner Limit](https://mlsanity.com/paper/2105.13302/) (2021)
- [Unifying AMP Algorithms for Rotationally-Invariant Models](https://mlsanity.com/paper/2412.01574/) (2024)
- [Efficient Designs of SLOPE Penalty Sequences in Finite Dimension](https://mlsanity.com/paper/2102.07211/) (2021)
- [Bayes optimal learning in high-dimensional linear regression with network side information](https://mlsanity.com/paper/2306.05679/) (2023)
- [Understanding Optimal Feature Transfer via a Fine-Grained Bias-Variance Analysis](https://mlsanity.com/paper/2404.12481/) (2024)
- [Optimal Implicit Bias in Linear Regression](https://mlsanity.com/paper/2506.17187/) (2025)
- [Towards Designing Optimal Sensing Matrices for Generalized Linear Inverse Problems](https://mlsanity.com/paper/2111.03237/) (2021)
- [Sharp Trade-Offs in High-Dimensional Inference via 2-Level SLOPE](https://mlsanity.com/paper/2507.09110/) (2025)

## Abstract (arXiv)

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.