# Proximal Operators of Sorted Nonconvex Penalties

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 50 references that are in the map.
- First posted on arXiv 18 Jun 2025.

## Builds on (most cited first, 13 of 13)

- [SLOPE - Adaptive variable selection via convex optimization](https://mlsanity.com/paper/1407.3824/) (2014)
- [False Discoveries Occur Early on the Lasso Path](https://mlsanity.com/paper/1511.01957/) (2015)
- [Beyond L1: Faster and Better Sparse Models with skglm](https://mlsanity.com/paper/2204.07826/) (2022)
- [The Geometry of Uniqueness, Sparsity and Clustering in Penalized Estimation](https://mlsanity.com/paper/2004.09106/) (2020)
- [The Strong Screening Rule for SLOPE](https://mlsanity.com/paper/2005.03730/) (2020)
- [On the Convergence of the Iterative Shrinkage/Thresholding Algorithm With a Weakly Convex Penalty](https://mlsanity.com/paper/1510.07821/) (2015)
- [Safe rules for the identification of zeros in the solutions of the SLOPE problem](https://mlsanity.com/paper/2110.11784/) (2021)
- [CLEAR: Covariant LEAst-square Re-fitting with applications to image restoration](https://mlsanity.com/paper/1606.05158/) (2016)
- [Coordinate Descent for SLOPE](https://mlsanity.com/paper/2210.14780/) (2022)
- [Sparse Signal Estimation by Maximally Sparse Convex Optimization](https://mlsanity.com/paper/1302.5729/) (2013)
- [Sparse Estimation with Strongly Correlated Variables using Ordered Weighted L1 Regularization](https://mlsanity.com/paper/1409.4005/) (2014)
- [An Exact Solution Path Algorithm for SLOPE and Quasi-Spherical OSCAR](https://mlsanity.com/paper/2010.15511/) (2020)
- [The Proximity Operator of the Log-Sum Penalty](https://mlsanity.com/paper/2103.02681/) (2021)

## Abstract (arXiv)

This work studies the problem of sparse signal recovery with automatic grouping of variables. To this end, we investigate sorted nonsmooth penalties as a regularization approach for generalized linear models. We focus on a family of sorted nonconvex penalties which generalizes the Sorted L1 Norm (SLOPE). These penalties are designed to promote clustering of variables due to their sorted nature, while the nonconvexity reduces the shrinkage of coefficients. Our goal is to provide efficient ways to compute their proximal operator, enabling the use of popular proximal algorithms to solve composite optimization problems with this choice of sorted penalties. We distinguish between two classes of problems: the weakly convex case where computing the proximal operator remains a convex problem, and the nonconvex case where computing the proximal operator becomes a challenging nonconvex combinatorial problem. For the weakly convex case (e.g. sorted MCP and SCAD), we explain how the Pool Adjacent Violators (PAV) algorithm can exactly compute the proximal operator. For the nonconvex case (e.g. sorted Lq with q in ]0,1[), we show that a slight modification of this algorithm turns out to be remarkably efficient to tackle the computation of the proximal operator. We also present new theoretical insights on the minimizers of the nonconvex proximal problem. We demonstrate the practical interest of using such penalties on several experiments.