skip to main content
10.1145/1390156.1390161acmotherconferencesArticle/Chapter ViewAbstractPublication PagesicmlConference Proceedingsconference-collections
research-article

Bolasso: model consistent Lasso estimation through the bootstrap

Authors Info & Claims
Published:05 July 2008Publication History

ABSTRACT

We consider the least-square linear regression problem with regularization by the l1-norm, a problem usually referred to as the Lasso. In this paper, we present a detailed asymptotic analysis of model consistency of the Lasso. For various decays of the regularization parameter, we compute asymptotic equivalents of the probability of correct model selection (i.e., variable selection). For a specific rate decay, we show that the Lasso selects all the variables that should enter the model with probability tending to one exponentially fast, while it selects all other variables with strictly positive probability. We show that this property implies that if we run the Lasso for several bootstrapped replications of a given sample, then intersecting the supports of the Lasso bootstrap estimates leads to consistent model selection. This novel variable selection algorithm, referred to as the Bolasso, is compared favorably to other linear regression methods on synthetic data and datasets from the UCI machine learning repository.

References

  1. Asuncion, A., & Newman, D. (2007). UCI machine learning repository.Google ScholarGoogle Scholar
  2. Bach, F. R. (2008). Consistency of the group Lasso and multiple kernel learning. J. Mac. Learn. Res., to appear. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Bentkus, V. (2003). On the dependence of the Berry--Esseen bound on dimension. Journal of Statistical Planning and Inference, 113, 385--402.Google ScholarGoogle ScholarCross RefCross Ref
  4. Boucheron, S., Lugosi, G., & Bousquet, O. (2004). Concentration inequalities. Advanced Lectures on Machine Learning. Springer.Google ScholarGoogle Scholar
  5. Breiman, L. (1996a). Bagging predictors. Machine Learning, 24, 123--140. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Breiman, L. (1996b). Heuristics of instability and stabilization in model selection. Ann. Stat., 24, 2350--2383.Google ScholarGoogle ScholarCross RefCross Ref
  7. Breiman, L. (1998). Arcing classifier. Ann. Stat., 26, 801--849.Google ScholarGoogle ScholarCross RefCross Ref
  8. Bühlmann, P. (2006). Boosting for high-dimensional linear models. Ann. Stat., 34, 559--583.Google ScholarGoogle ScholarCross RefCross Ref
  9. Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004). Least angle regression. Ann. Stat., 32, 407.Google ScholarGoogle ScholarCross RefCross Ref
  10. Efron, B., & Tibshirani, R. J. (1998). An introduction to the bootstrap. Chapman & Hall.Google ScholarGoogle Scholar
  11. Fu, W., & Knight, K. (2000). Asymptotics for Lasso-type estimators. Ann. Stat., 28, 1356--1378.Google ScholarGoogle ScholarCross RefCross Ref
  12. Lounici, K. (2008). Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators. Electronic Journal of Statistics, 2.Google ScholarGoogle Scholar
  13. Meinshausen, N., & Yu, B. (2008). Lasso-type recovery of sparse representations for high-dimensional data. Ann. Stat., to appear.Google ScholarGoogle Scholar
  14. Tibshirani, R. (1994). Regression shrinkage and selection via the Lasso. J. Roy. Stat. Soc. B, 58, 267--288.Google ScholarGoogle Scholar
  15. Wainwright, M. J. (2006). Sharp thresholds for noisy and high-dimensional recovery of sparsity using l 1-constrained quadratic programming (Tech. report 709). Dpt. of Statistics, UC Berkeley.Google ScholarGoogle Scholar
  16. Yuan, M., & Lin, Y. (2007). On the non-negative garrotte estimator. J. Roy. Stat. Soc. B, 69, 143--161.Google ScholarGoogle ScholarCross RefCross Ref
  17. Zhao, P., & Yu, B. (2006). On model selection consistency of Lasso. J. Mac. Learn. Res., 7, 2541--2563. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Zou, H. (2006). The adaptive Lasso and its oracle properties. J. Am. Stat. Ass., 101, 1418--1429.Google ScholarGoogle ScholarCross RefCross Ref

Index Terms

  1. Bolasso: model consistent Lasso estimation through the bootstrap

                  Recommendations

                  Comments

                  Login options

                  Check if you have access through your login credentials or your institution to get full access on this article.

                  Sign in
                  • Published in

                    cover image ACM Other conferences
                    ICML '08: Proceedings of the 25th international conference on Machine learning
                    July 2008
                    1310 pages
                    ISBN:9781605582054
                    DOI:10.1145/1390156

                    Copyright © 2008 ACM

                    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

                    Publisher

                    Association for Computing Machinery

                    New York, NY, United States

                    Publication History

                    • Published: 5 July 2008

                    Permissions

                    Request permissions about this article.

                    Request Permissions

                    Check for updates

                    Qualifiers

                    • research-article

                    Acceptance Rates

                    Overall Acceptance Rate140of548submissions,26%

                  PDF Format

                  View or Download as a PDF file.

                  PDF

                  eReader

                  View online with eReader.

                  eReader