The Group-Lasso for generalized linear models: uniqueness of solutions and efficient algorithms

ABSTRACT

The Group-Lasso method for finding important explanatory factors suffers from the potential non-uniqueness of solutions and also from high computational costs. We formulate conditions for the uniqueness of Group-Lasso solutions which lead to an easily implementable test procedure that allows us to identify all potentially active groups. These results are used to derive an efficient algorithm that can deal with input dimensions in the millions and can approximate the solution path efficiently. The derived methods are applied to large-scale learning problems where they exhibit excellent performance and where the testing procedure helps to avoid misinterpretations of the solutions.

REFERENCES

• 1: L. D. Brown, Fundamentals of statistical exponential families: with applications in statistical decision theory, Institute of Mathematical Statistics, Hayworth, CA, 1986
• 2: Crooks, G., Hon, G., Chandonia, J., & Brenner, S. (2004). Weblogo: A sequence logo generator. Genome Research, 14.
• 3: Dahinden, C., Parmigiani, G., Emerick, M., & Büühlmann, P. (2007). Penalized likelihood for sparse contingency tables with an application to full-length cDNA libraries. BMC Bioinformatics, 8, 476.
• 4: Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004). Least angle regression. Ann. Stat., 32, 407--499.
• 5: Kim, Y., Kim, J., & Kim, Y. (2006). Blockwise sparse regression. Statistica Sinica, 16, 375--390.
• 6: McCullaghand, P., & Nelder, J. (1983). Generalized linear models. Chapman & Hall.
• 7: Meier, L., van de Geer, S., & Büühlmann, P. (2008). The Group Lasso for Logistic Regression. J. Roy. Stat. Soc. B, 70, 53--71.
• 8: Roland Nilsson , José M. Peña , Johan Björkegren , Jesper Tegnér, Consistent Feature Selection for Pattern Recognition in Polynomial Time, The Journal of Machine Learning Research, 8, p.589-612, 5/1/2007
• 9: Osborne, M., Presnell, B., & Turlach, B. (2000). On the LASSO and its dual. J. Comp. and Graphical Statistics, 9, 319--337.
• 10: Shevade, K., & Keerthi, S. (2003). A simple and efficient algorithm for gene selection using sparse logistic regression. Bioinformatics, 19, 2246--2253.
• 11: Tibshirani, R. (1996). Regression shrinkage and selection via the Lasso. J. Roy. Stat. Soc. B, 58, 267--288.
• 12: Wainwright, M., Jaakkola, T., & Willsky, A. (2005). A new class of upper bounds on the log partition function. IEEE Trans. Information Theory, 51.
• 13: Wedderburn, R. W. M. (1973). On the existence and uniqueness of the maximum likelihood estimates for certain generalized linear models. Biometrika, 63, 27--32.
• 14: Yeo, G., & Burge, C. (2004). Maximum entropy modeling of short sequence motifs with applications to RNA splicing signals. J. Comp. Biology, 11, 377--394.
• 15: Yuan, M., & Lin, Y. (2006). Model selection and estimation in regression with grouped variables. J. Roy. Stat. Soc. B, 49--67.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory