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

Abstract

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^{\alpha }$, $\alpha >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^{\alpha },\alpha >1$. This is in comparison to starting with the ``best'' subset of size smaller than $n$ and regardless of the value of $\alpha$. 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.

Published at http://dx.doi.org/10.1214/009053606000000768 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (12)

• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• High-dimensional graphs and variable selection with the Lasso
• Nonconcave penalized likelihood with a diverging number of parameters

Cited by in corpus (16)

• High-dimensional classification using features annealed independence rules
• High-dimensional generalized linear models and the lasso
• Near-ideal model selection by ${\ell }_1$ minimization
• Properties and refinements of the fused lasso
• Learning physical descriptors for materials science by compressed sensing
• Gibbs posterior for variable selection in high-dimensional classification and data mining
• Honest variable selection in linear and logistic regression models via ${\ell }_1$ and ${\ell }_1+{\ell }_2$ penalization
• Variable selection and updating in model-based discriminant analysis for high dimensional data with food authenticity applications
• Bayesian variable selection for high dimensional generalized linear models: convergence rates of the fitted densities
• Kullback-Leibler aggregation and misspecified generalized linear models
• The log-linear group-lasso estimator and its asymptotic properties
• Exact Localization and Superresolution with Noisy Data and Random Illumination
• On the Sensitivity of the Lasso to the Number of Predictor Variables
• Greedy algorithms for prediction
• Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
• Model Selection in Utility-Maximizing Binary Prediction