Necessary and Sufficient Conditions Toward Optimal Feature Selection and Parameter Estimation

• Activity Number: 483
• Type: Invited
• Date/Time: Wednesday, August 3, 2011 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Xiaotong Shen*+ and Wei Pan and Yunzhang Zhu
• Companies: University of Minnesota and University of Minnesota and University of Minnesota
• Keywords: High-dimensional regression ; Nonconvex regularization

Abstract

High-dimensional feature selection has become increasingly crucial for seeking parsimonious models in parameter estimation. For selection consistency, we derive one necessary and sufficient condition formulated on the notion of degree-of-separation. The minimal degree of separation is required for consistency, and consistency is achieved by constrained L0-regularization and its computational surrogate, at the degree of separation slightly exceeding the minimal level. This permits up to exponentially many features in the sample size, regardless of if a true model exists. In contrast, their unconstrained counterparts do so in presence of a true model, as in the parametric case. In this sense, L0-regularization and its surrogate are optimal in feature selection against any method. More importantly, sharper parameter estimation and prediction are resulted from such selection, which, otherwise, is impossible in absence of a good selection rule.