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

DOI10.1214/009053606000000768MaRDI QIDQ869974zbMATHOpenAlexWikidataFDO

Authors Eitan Greenshtein

Publication date 12 March 2007

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0702684

zbMATH Keywords

Lasso procedure

Mathematics Subject Classification ID

Statistical ranking and selection procedures (62F07) Statistical decision theory (62C99)

Abstract: Let $(Y,X_1,\mathrm{...},X_m)$ be a random vector. It is desired to predict $Y$ based on $(X_1,\mathrm{...},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.

Recommendations

• Persistene in high-dimensional linear predictor-selection and the virtue of overparametrization
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Prediction when fitting simple models to high-dimensional data
• Better subset regression
• Boosting for high-dimensional linear models

Cites work

• scientific article; zbMATH DE number 5769866 (Why is no real title available?)
• scientific article; zbMATH DE number 3772326 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• Asymptotic behavior of M-estimators for the linear model
• Asymptotic behavior of M-estimators of p regression parameters when \(p^ 2/n\) is large. I. Consistency
• Atomic decomposition by basis pursuit
• DNA microarray experiments: biological and technological aspects
• Discussion on boosting papers.
• Discussion on boosting papers.
• Efficient agnostic learning of neural networks with bounded fan-in
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• Functional aggregation for nonparametric regression.
• High-dimensional graphs and variable selection with the Lasso
• Least angle regression. (With discussion)
• Nonconcave penalized likelihood with a diverging number of parameters.
• On the Bayes-risk consistency of regularized boosting methods.
• Persistene in high-dimensional linear predictor-selection and the virtue of overparametrization
• Population theory for boosting ensembles.
• Robust regression: Asymptotics, conjectures and Monte Carlo
• Some theory for Fisher's linear discriminant function, `naive Bayes', and some alternatives when there are many more variables than observations
• Statistical modeling: The two cultures. (With comments and a rejoinder).
• The elements of statistical learning. Data mining, inference, and prediction
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties

Cited in

(47)

• Risk minimization for time series binary choice with variable selection
• Prediction when fitting simple models to high-dimensional data
• Honest variable selection in linear and logistic regression models via \(\ell _{1}\) and \(\ell _{1}+\ell _{2}\) penalization
• On the asymptotic properties of the group lasso estimator for linear models
• Near-ideal model selection by \(\ell _{1}\) minimization
• Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low
• Sure independence screening for ultrahigh dimensional feature space. With discussion and authors' reply
• Confidence intervals for low dimensional parameters in high dimensional linear models
• Sharp support recovery from noisy random measurements by \(\ell_1\)-minimization
• Constrained optimization for stratified treatment rules in reducing hospital readmission rates of diabetic patients
• Properties and refinements of the fused Lasso
• Variable selection and updating in model-based discriminant analysis for high dimensional data with food authenticity applications
• Gene selection and prediction for cancer classification using support vector machines with a reject option
• Nonparametric time series forecasting with dynamic updating
• Fast best subset selection: coordinate descent and local combinatorial optimization algorithms
• Best subset selection via a modern optimization lens
• Overview of debiased Lasso in high-dimensional linear model
• Model selection in utility-maximizing binary prediction
• Best subset binary prediction
• Approximation of functions of few variables in high dimensions
• Regularization in statistics
• Complexity of approximation of functions of few variables in high dimensions
• Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
• Kullback-Leibler aggregation and misspecified generalized linear models
• Graphical-model based high dimensional generalized linear models
• High-dimensional generalized linear models and the lasso
• The statistical rate for support matrix machines under low rankness and row (column) sparsity
• Better subset regression
• Persistene in high-dimensional linear predictor-selection and the virtue of overparametrization
• An error bound for \(L_1\)-norm support vector machine coefficients in ultra-high dimension
• Mathematical programming for simultaneous feature selection and outlier detection under l1 norm
• Sparse regression at scale: branch-and-bound rooted in first-order optimization
• scientific article; zbMATH DE number 7415078 (Why is no real title available?)
• High-dimensional classification using features annealed independence rules
• On the sensitivity of the Lasso to the number of predictor variables
• On two continuum armed bandit problems in high dimensions
• Forecasting functional time series
• Greedy algorithms for prediction
• Difference-of-convex learning: directional stationarity, optimality, and sparsity
• Elastic-net regularization in learning theory
• Learning without concentration
• Gibbs posterior for variable selection in high-dimensional classification and data mining
• Genetic algorithm in the wavelet domain for large \(p\) small \(n\) regression
• OR forum: An algorithmic approach to linear regression
• Bayesian variable selection for high dimensional generalized linear models: convergence rates of the fitted densities
• \(\ell _{1}\)-regularized linear regression: persistence and oracle inequalities
• The log-linear group-lasso estimator and its asymptotic properties

Describes a project that uses

Uses Software

• PDCO

This page was built for publication: Best subset selection, persistence in high-dimensional statistical learning and optimization under \(l_1\) constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q869974)