Bolasso: model consistent Lasso estimation through the bootstrap

ABSTRACT

We consider the least-square linear regression problem with regularization by the l₁-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.
• 2: Francis R. Bach, Consistency of the Group Lasso and Multiple Kernel Learning, The Journal of Machine Learning Research, 9, p.1179-1225, 6/1/2008
• 3: Bentkus, V. (2003). On the dependence of the Berry--Esseen bound on dimension. Journal of Statistical Planning and Inference, 113, 385--402.
• 4: Boucheron, S., Lugosi, G., & Bousquet, O. (2004). Concentration inequalities. Advanced Lectures on Machine Learning. Springer.
• 5: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 6: Breiman, L. (1996b). Heuristics of instability and stabilization in model selection. Ann. Stat., 24, 2350--2383.
• 7: Breiman, L. (1998). Arcing classifier. Ann. Stat., 26, 801--849.
• 8: Bühlmann, P. (2006). Boosting for high-dimensional linear models. Ann. Stat., 34, 559--583.
• 9: Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004). Least angle regression. Ann. Stat., 32, 407.
• 10: Efron, B., & Tibshirani, R. J. (1998). An introduction to the bootstrap. Chapman & Hall.
• 11: Fu, W., & Knight, K. (2000). Asymptotics for Lasso-type estimators. Ann. Stat., 28, 1356--1378.
• 12: Lounici, K. (2008). Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators. Electronic Journal of Statistics, 2.
• 13: Meinshausen, N., & Yu, B. (2008). Lasso-type recovery of sparse representations for high-dimensional data. Ann. Stat., to appear.
• 14: Tibshirani, R. (1994). Regression shrinkage and selection via the Lasso. J. Roy. Stat. Soc. B, 58, 267--288.
• 15: Wainwright, M. J. (2006). Sharp thresholds for noisy and high-dimensional recovery of sparsity using l₁-constrained quadratic programming (Tech. report 709). Dpt. of Statistics, UC Berkeley.
• 16: Yuan, M., & Lin, Y. (2007). On the non-negative garrotte estimator. J. Roy. Stat. Soc. B, 69, 143--161.
• 17: Peng Zhao , Bin Yu, On Model Selection Consistency of Lasso, The Journal of Machine Learning Research, 7, p.2541-2563, 12/1/2006
• 18: Zou, H. (2006). The adaptive Lasso and its oracle properties. J. Am. Stat. Ass., 101, 1418--1429.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Least squares methods; Linear programming
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory