Pattern Recovery in Penalized Estimation and its Geometry

Abstract

For many penalized estimators such as LASSO, SLOPE, OSCAR, PACS, fused, clustered and generalized LASSO, the penalty term is a real-valued polyhedral gauge. We focus on pattern recovery at β with respect to such a penalty term, where β is the unknown parameter of regression coefficients. For LASSO, the pattern of β only depends on the sign of β and sign recovery by LASSO is a well known topic in the literature. We introduce the notion of patterns and pattern recovery in the broad framework of gauge-penalized least-squares estimation and illustrate the patterns different polyhedral gauges. We also provide theoretical guarantees for pattern recovery, in particular the “noiseless recovery condition” is necessary for a probability of recovery larger than 1/2 and can be viewed as a generalization of the LASSO’s irrepresentability condition. This condition may be relaxed using thresholded penalized least squares estimators, a class of estimators generalizing the thresholded LASSO. Indeed, we show that the “accessibility condition”, a weaker condition than the “noiseless recovery condition”, is necessary and asymptotically sufficient for pattern recovery in thresholded penalized estimation. We also provide a geometric interpretation of our approach to pattern recovery and the accessibility condition.