Efficient Designs of SLOPE Penalty Sequences in Finite Dimension
This work addresses a computational bottleneck for researchers and practitioners using SLOPE in regression, offering incremental improvements in efficiency.
The paper tackles the computational expense of designing penalty sequences for SLOPE in linear regression by proposing two efficient algorithms: a first-order Projected Gradient Descent for Gaussian data and a zero-th order Coordinate Descent for general data, achieving a trade-off between accuracy and speed in experiments.
In linear regression, SLOPE is a new convex analysis method that generalizes the Lasso via the sorted L1 penalty: larger fitted coefficients are penalized more heavily. This magnitude-dependent regularization requires an input of penalty sequence $λ$, instead of a scalar penalty as in the Lasso case, thus making the design extremely expensive in computation. In this paper, we propose two efficient algorithms to design the possibly high-dimensional SLOPE penalty, in order to minimize the mean squared error. For Gaussian data matrices, we propose a first order Projected Gradient Descent (PGD) under the Approximate Message Passing regime. For general data matrices, we present a zero-th order Coordinate Descent (CD) to design a sub-class of SLOPE, referred to as the k-level SLOPE. Our CD allows a useful trade-off between the accuracy and the computation speed. We demonstrate the performance of SLOPE with our designs via extensive experiments on synthetic data and real-world datasets.