Material Detail

Fast projections onto l1,q-norm balls for grouped feature selection

Fast projections onto l1,q-norm balls for grouped feature selection

This video was recorded at European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), Athens 2011. Joint sparsity is widely acknowledged as a powerful structural cue for performing feature selection in setups where variables are expected to demonstrate "grouped" behavior. Such grouped behavior is commonly modeled by Group-Lasso or Multitask Lasso-type problems, where feature selection is effected via l1,q-mixed-norms. Several particular formulations for modeling groupwise sparsity have received substantial attention in the literature; and in some cases, efficient algorithms are also available. Surprisingly, for constrained formulations of fundamental importance (e.g., regression with an l1,∞-norm constraint), highly scalable methods seem to be missing. We address this deficiency by presenting a method based on spectral projected-gradient (SPG) that can tackle l1,q- constrained convex regression problems. The most crucial component of our method is an algorithm for projecting onto l1,q-norm balls. We present several numerical results which show that our methods attain up to 30X speedups on large l1,∞-multitask lasso problems. Even more dramatic are the gains for just the l1,∞-projection subproblem: we observe almost three orders of magnitude speedups compared against the currently standard method.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.