Best subset selection, persistence in high-dimensional statistical learning and optimization under l1 constraint

By Eitan Greenshtein. 2006

113 citations recorded by the source corpus.

Let (Y, X 1 ,..., X m ) be a random vector. It is desired to predict Y based on (X 1 ,..., X m ). Examples of prediction methods are regression, classification using logistic regression or separating hyperplanes, and so on. We consider the problem of best subset selection, and study it in the context m = n α , a > 1, where n is the number of observations. We investigate procedures that are based on empirical risk minimization. It is shown, that in common cases, we should aim to find the best subset among those of size which is of order o(n/log(n)). It is also shown, that in some "asymptotic sense," when assuming a certain sparsity condition, there is no loss in letting m be much larger than n, for example, m = n α , a > 1. This is in comparison to starting with the "best" subset of size smaller than n and regardless of the value of a. We then study conditions under which empirical risk minimization subject to l 1 constraint yields nearly the best subset. These results extend some recent results obtained by Greenshtein and Ritov. Finally we present a high-dimensional simulation study of a "boosting type" classification procedure.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Best Subset Selection via a Modern Optimization Lens (2015, background): “Insightful statistical properties of problem (1.4) have been explored from a theoretical viewpoint in Greenshtein (2006), Greenshtein and Ritov (2004), Shen et al. (2013), Zhang and Zhang (2012), for example.”
Efficient Policy Learning (2017, background): “, support vector machines (Cortes and Vapnik, 1995), best-subset empirical risk minimization (Chen and Lee, 2016; Greenshtein, 2006), recursive partitioning (Breiman et al.”
Sparse Modeling for Image and Vision Processing (2014, background): “Given RIP-based assumptions on the dictionary D⋆ and number of non zero elements in the columns of A⋆, and the noise level, Gribonval et al. [2014] show that the cost function defined in Eq.”
Smoothly Clipped Absolute Deviation on High Dimensions (2008, background): “For LASSO, Meinshausen and Bühlmann (2006) and Zhao and Yu (2006) recently proved the model selection consistency in high-dimensional cases; that is, one can select only the relevant covariates by choosing the regularization parameter appropriately in LASSO.”
Elastic-net regularization in learning theory (2008, background): “Non-asymptotic bounds within the framework of statistical learning have been studied in several papers [25, 8, 28, 37, 24, 39, 44, 26].”
On the asymptotic properties of the group lasso estimator for linear models (2008, methodology): “…Bühlmann, 2006; Wainwright, 2006, 2007; Zhao and Yu, 2006), consistency and oracle properties (see, e.g. Meinshausen and Yu, 2006; Bickel et al., 2007; Bunea et al., 2007a,b; Zhang, 2007; Koltchinskii, 2005; Zhang and Huang, 2007), and persistence (Greenshtein and Ritov, 2006; Greenshtein, 2006).”
Supersparse Linear Integer Models for Interpretable Classification (2013, result): “There are similar asymptotic results in other works [28] which are theoretically interesting but not necessarily relevant to the kind of applied problems we consider in this paper.”
HIGH-DIMENSIONAL GENERALIZED LINEAR MODELS AND THE LASSO (2008, background): “Greenshtein (2006) studies general loss with ℓ1 constraint.”
High Dimensional Classification Using Features Annealed Independence Rules. (2007, methodology): “ propose the distance weighted discrimination to overcome the “data piling” of the support vector machine method; the concept of persistency is introduced and studied by Greenshtein and Ritov (2004), Greenshtein (2006) and Meinshausen (2005), which places more interests in misclassiﬁcation rates or ”
Confidence intervals for low dimensional parameters in high dimensional linear models (2011, methodology): “This includes l1 regularized methods (Tibshirani, 1996; Chen et al., 2001; Greenshtein and Ritov, 2004; Greenshtein, 2006; Meinshausen and Bühlmann, 2006; Tropp, 2006; Zhao and Yu, 2006; Candès and Tao, 2007; Zhang and Huang, 2008; Bickel et al., 2009; Koltchinskii, 2009; Meinshausen and Yu,…”
A Selective Overview of Variable Selection in High Dimensional Feature Space (2009, unknown): “The latter property is called persistence in Greenshtein and Ritov (2004) and Greenshtein (2006), and arises frequently in machine learning problems such as document classiﬁcation and computer vision.”
Sure independence screening for ultrahigh dimensional feature space (2006, background): “which along with (32), Conditions 2 and 4, and Bonferroni’s i nequality yields”
Approximation of Functions of Few Variables in High Dimensions (2011, background): “There are many impressive approaches (see [1, 4, 12, 8, 11, 13] as representative) which are being”
ℓ1-regularized linear regression: persistence and oracle inequalities (2011, background): “The first of these properties has been studied, for example, in [4,7,12, 16 ,17,21,39] while the latter two are studied in [5,7,11,21,23–26,41,42].”
Near-ideal model selection by ℓ1 minimization (2008, background): “In the last few years, there have been many beautiful works that attempt to understand the properties of the lasso and other minimum l1 algorithms, such as the Dantzig selector when the number of variables may be larger than the sample size [3, 5, 6, 10, 13, 15, 16, 20, 21, 29, 30].”