Ulrike
Schneider
Universität Wien
A Unified Framework for Pattern Recovery in Penalized Estimation
Abstract.
We consider the framework of least-squares 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 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 novel and 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 with positive probability, the so-called accessibility condition. We make the connection to estimation uniqueness by showing that uniqueness holds if and only if no pattern with complexity exceeding the rank of the X-matrix is accessible. Subsequently, we introduce the noiseless recovery condition which is a stronger requirement than accessibility and 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 is bounded by 1/2 if the condition is not satisfied. Through this, we unify and extend the irrepresentability condition to a broad class of penalized estimators using an interpretable criterion. We also look at the gap between accessibility and the noiseless recovery condition and discuss that our criteria show that it is more pronounced for simple patterns. 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 the Lasso as well as other estimation procedures.