Fast Projections onto ℓ1, Q -Norm Balls for Grouped Feature Selection

Abstract

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.