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

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 ℓ_1,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 ℓ_1,∞-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 ℓ_1,q- constrained convex regression problems. The most crucial component of our method is an algorithm for projecting onto ℓ_1,q-norm balls. We present several numerical results which show that our methods attain up to 30X speedups on large ℓ_1,∞-multitask lasso problems. Even more dramatic are the gains for just the ℓ_1,∞-projection subproblem: we observe almost three orders of magnitude speedups compared against the currently standard method.