Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Safe rules for the identification of zeros in the solution of the SLOPE problem

Clément Elvira 1 Cédric Herzet 2 
2 SIMSMART - SIMulation pARTiculaire de Modèles Stochastiques
Inria Rennes – Bretagne Atlantique , IRMAR - Institut de Recherche Mathématique de Rennes
Abstract : In this paper we propose a methodology to accelerate the resolution of the socalled "Sorted LOne Penalized Estimation" (SLOPE) problem. Our method leverages the concept of "safe screening", well-studied in the literature for group-separable sparsity-inducing norms, and aims at identifying the zeros in the solution of SLOPE. More specifically, we introduce a family of n! safe screening rules for this problem, where n is the dimension of the primal variable, and propose a tractable procedure to verify if one of these tests is passed. Our procedure has a complexity O(n log n+LT) where T ≤ n is a problem-dependent constant and L is the number of zeros identified by the tests. We assess the performance of our proposed method on a numerical benchmark and emphasize that it leads to significant computational savings in many setups.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03400322
Contributor : Clément Elvira Connect in order to contact the contributor
Submitted on : Friday, April 15, 2022 - 5:00:00 PM
Last modification on : Saturday, May 21, 2022 - 3:47:55 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03400322, version 2

Citation

Clément Elvira, Cédric Herzet. Safe rules for the identification of zeros in the solution of the SLOPE problem. 2022. ⟨hal-03400322v2⟩

Share

Metrics

Record views

100

Files downloads

26