A Unified Framework for Pattern Recovery in Penalized Estimation and its Geometry

Abstract

We consider the framework of penalized estimation where the penalty term is given by a polyhedral norm, or more generally, a polyhedral gauge, which encompasses methods such as LASSO (and many variants including 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 pattern 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. We also introduce the stronger noiseless recovery condition which can be shown to play exactly the same role as the well-known irrepresentability condition for the LASSO in that the probability of pattern recovery in our general framework is bounded by 1/2 if the condition is not satisfied. Finally, we prove that the noiseless recovery condition can indeed be relaxed when turning to so-called thresholded penalized estimation: in this setting, the accessibility condition is already sufficient (and necessary) for sure pattern recovery provided that the signal of the pattern is large enough. We demonstrate how our findings can be interpreted through a geometrical lens throughout the talk and illustrate our results for LASSO and SLOPE in particular.