On the sign recovery by LASSO, thresholded LASSO and thresholded Basis Pursuit Denoising

Basis Pursuit (BP), Basis Pursuit DeNoising (BPDN), and LASSO are popular methods for identifyingimportant predictors in the high-dimensional linear regression model Y = Xβ + ε. By definition, whenε = 0, BP uniquely recovers β when Xβ = Xb and β different than b implies L1 norm of β is smaller than the L1 norm of b (identifiability condition). Furthermore, LASSO can recover the sign of β only under a much stronger irrepresentability condition. Meanwhile, it is known that the model selection properties of LASSO can be improved by hard-thresholdingits estimates. This article supports these findings by proving that thresholded LASSO, thresholded BPDNand thresholded BP recover the sign of β in …

The Geometry of Uniqueness, Sparsity and Clustering in Penalized Estimation

We provide a necessary and sufficient condition for the uniqueness of penalized least-squares estimators whose penalty term is given by a norm with a polytope unit ball, covering a wide range of methods including SLOPE, PACS, fused, clustered and classical LASSO as well as the related method of basis pursuit. We consider a strong type of uniqueness that is relevant for statistical problems. The uniqueness condition is geometric and involves how the row span of the design matrix intersects the faces of the dual norm unit ball, which for SLOPE is given by the signed permutahedron. Further considerations based this condition also allow to derive results on sparsity and clustering features. In …

Comment on the subdifferential formula given in the article "Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing"

Subdifferential formula for the sorted 1 norm attracted lot of attention recently to derive screening procedures for SLOPE [5, 7], clustering and sparsity properties for SLOPE [1, 10] and explicit expressions for the proximal operator of the sorted 1 norm [4, 11]. In this note, we discuss the formula for the subdifferential of the sorted 1 norm given in the article of Bu et al., [3]. We believe that expressing the sorted 1 norm as the maximum of linear functions, as suggested by the authors, is an appropriate approach to derive its subdifferential. However the formula provided in this article contains many flaws and we hope that authors would take into account this note in order to rewrite …

The Solution Path of SLOPE

The SLOPE estimator has the particularity of having null components (sparsity) and components that are equal in absolute value (clustering). The number of clusters depends on the regularization parameter of the estimator. This parameter can be chosen as a trade-off between interpretability (with a small number of clusters) and accuracy (with a small mean squared error or a small prediction error). Finding such a compromise requires to compute the solution path, that is the function mapping the regularization parameter to the estimator. We provide in this article an algorithm to compute the solution path of SLOPE.

On sparsity and clustering properties

La symphonie des cercles circonscrits

Pattern Recovery in Penalized and Thresholded Estimation and its Geometry

We consider the framework of penalized estimation where the penalty term is given by a real-valued polyhedral gauge, which encompasses methods such as LASSO (and many variants thereof such as the generalized LASSO), SLOPE, OSCAR, PACS and others. Each of these estimators can uncover a different structure or ``pattern'' of the unknown parameter vector. We define a general notion of patterns based on subdifferentials and formalize an approach to measure their complexity. For pattern recovery, we provide a minimal condition for a particular pattern to be detected by the procedure with positive probability, the so-called accessibility condition. Using our approach, we also introduce the stronge…

La Géométrie pour l'Unicité, la Parcimonie et l'Appariement des Estimateurs Pénalisés

During the talk we will give a necessary and sufficient condition for the uniqueness of a penalized least squares estimator whose penalty term is a polyhedral norm. Our results cover many methods including the OSCAR, SLOPE and LASSO estimators as well as the related method of basis pursuit. The geometrical condition for uniqueness involves how the row span of the design matrix intersects the faces of the dual normunit ball. Theoretical results on sparsity by LASSO and basis pursuit estimators are deduced from this condition via the characterization of accessible sign vectors for these two methods.