Sparsistency of \ell_1-Regularized M-Estimators

[edit]

Yen-Huan Li, Jonathan Scarlett, Pradeep Ravikumar, Volkan Cevher ;
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:644-652, 2015.

Abstract

We consider the model selection consistency or sparsistency of a broad set of \ell_1-regularized M-estimators for linear and non-linear statistical models in a unified fashion. For this purpose, we propose the local structured smoothness condition (LSSC) on the loss function. We provide a general result giving deterministic sufficient conditions for sparsistency in terms of the regularization parameter, ambient dimension, sparsity level, and number of measurements. We show that several important statistical models have M-estimators that indeed satisfy the LSSC, and as a result, the sparsistency guarantees for the corresponding \ell_1-regularized M-estimators can be derived as simple applications of our main theorem.

Related Material