Boosting for high-dimensional linear models

Abstract

We prove that boosting with the squared error loss, $L_2$Boosting, is consistent for very high-dimensional linear models, where the number of predictor variables is allowed to grow essentially as fast as $O$(exp(sample size)), assuming that the true underlying regression function is sparse in terms of the ${\ell }_1$-norm of the regression coefficients. In the language of signal processing, this means consistency for de-noising using a strongly overcomplete dictionary if the underlying signal is sparse in terms of the ${\ell }_1$-norm. We also propose here an $AIC$-based method for tuning, namely for choosing the number of boosting iterations. This makes $L_2$Boosting computationally attractive since it is not required to run the algorithm multiple times for cross-validation as commonly used so far. We demonstrate $L_2$Boosting for simulated data, in particular where the predictor dimension is large in comparison to sample size, and for a difficult tumor-classification problem with gene expression microarray data.

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

References in corpus (12)

• 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
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Boosting with early stopping: Convergence and consistency
• Complexity regularization via localized random penalties

Cited by in corpus (20)

• On asymptotically optimal confidence regions and tests for high-dimensional models
• Boosting Algorithms: Regularization, Prediction and Model Fitting
• Asymptotic properties of bridge estimators in sparse high-dimensional regression models
• The Evolution of Boosting Algorithms - From Machine Learning to Statistical Modelling
• High-dimensional variable selection
• Statistical significance in high-dimensional linear models
• Boosting the concordance index for survival data - a unified framework to derive and evaluate biomarker combinations
• Conditional Transformation Models
• Boosting algorithms in energy research: A systematic review
• Bayesian variable selection for high dimensional generalized linear models: convergence rates of the fitted densities
• Extending Statistical Boosting - An Overview of Recent Methodological Developments
• Discussion: A tale of three cousins: Lasso, L2Boosting and Dantzig
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• Non-asymptotic Oracle Inequalities for the High-Dimensional Cox Regression via Lasso
• Fast Linear Model Trees by PILOT
• Greedy algorithms for prediction
• Characterizing $L_2$Boosting
• Two-stage Sampling, Prediction and Adaptive Regression via Correlation Screening (SPARCS)
• A Forward Backward Greedy approach for Sparse Multiscale Learning
• Forward-Selected Panel Data Approach for Program Evaluation