Blockwise coordinate descent procedures for the multi-task lasso, with applications to neural semantic basis discovery

ABSTRACT

We develop a cyclical blockwise coordinate descent algorithm for the multi-task Lasso that efficiently solves problems with thousands of features and tasks. The main result shows that a closed-form Winsorization operator can be obtained for the sup-norm penalized least squares regression. This allows the algorithm to find solutions to very large-scale problems far more efficiently than existing methods. This result complements the pioneering work of Friedman, et al. (2007) for the single-task Lasso. As a case study, we use the multi-task Lasso as a variable selector to discover a semantic basis for predicting human neural activation. The learned solution outperforms the standard basis for this task on the majority of test participants, while requiring far fewer assumptions about cognitive neuroscience. We demonstrate how this learned basis can yield insights into how the brain represents the meanings of words.

REFERENCES

• 1: Andreas Argyriou , Theodoros Evgeniou , Massimiliano Pontil, Convex multi-task feature learning, Machine Learning, v.73 n.3, p.243-272, December 2008 [doi>10.1007/s10994-007-5040-8]
• 2: Massimo Fornasier , Holger Rauhut, Recovery Algorithms for Vector-Valued Data with Joint Sparsity Constraints, SIAM Journal on Numerical Analysis, v.46 n.2, p.577-613, March 2008 [doi>10.1137/0606668909]
• 3: Friedman, J., Hastie, T., Hüdotofling, H., & Tibshirani, R. (2007). Pathwise coordinate optimization. The Annals of Applied Statistics, 1, 302--332.
• 4: Friedman, J. H., Hastie, T., & Tibshirani, R. (2008). Regularized paths for generalized linear models via coordinate descent. Technical report, Stanford University.
• 5: Fu, W. J. (1998). Penalized regressions: The bridge versus the lasso. Journal of Computational and Graphical Statistics, 7, 397--416.
• 6: Hastie, T., Tibshirani, R., & Friedman, J. H. (2001). The elements of statistical learning: Data mining, inference, and prediction. Springer-Verlag.
• 7: Mallows, C. L. (Ed.). (1990). The collected works of john w. tukey. volume vi: More mathematical, 1938--1984. Wadsworth & Brooks/Cole.
• 8: Mitchell, T., et al. (2008). Predicting human brain activity associated with the meanings of nouns. Science, 320, 1191--1195.
• 9: Rockafellar, R. T., & Wets, R. J.-B. (1998). Variational analysis. Springer-Verlag Inc.
• 10: P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, Journal of Optimization Theory and Applications, v.109 n.3, p.475-494, June 2001 [doi>10.1023/A:1017501703105]
• 11: Turlach, B., Venables, W. N., & Wright, S. J. (2005). Simultaneous variable selection. Technometrics, 27, 349--363.
• 12: Wu, T. T., & Lange, K. (2008). Coordinate descent algorithms for lasso penalized regression. The Annals of Applied Statistics, 2, 224--244.
• 13: Zhang, J. (2006). A probabilistic framework for multitask learning (Technical Report CMU-LTI-06-006). Ph.D. thesis, Carnegie Mellon University.
• 14: Zhao, P., Rocha, G., & Yu, B. (2009). The grouped and hierarchical model selection through composite absolute penalties. The Annals of Statistics (to appear).

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; Classifier design and evaluation
  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