Fast projections onto mixed-norm balls with applications
This work addresses a computational bottleneck for researchers and practitioners using mixed-norm sparse models, though it is incremental as it builds on existing methods.
The paper tackles the lack of scalable algorithms for constrained sparse models by developing batch and online optimization methods based on efficient projections onto mixed-norm balls, applying them to multitask lasso.
Joint sparsity offers powerful structural cues for feature selection, especially for variables that are expected to demonstrate a "grouped" behavior. Such behavior is commonly modeled via group-lasso, multitask lasso, and related methods where feature selection is effected via mixed-norms. Several mixed-norm based sparse models have received substantial attention, and for some cases efficient algorithms are also available. Surprisingly, several constrained sparse models seem to be lacking scalable algorithms. We address this deficiency by presenting batch and online (stochastic-gradient) optimization methods, both of which rely on efficient projections onto mixed-norm balls. We illustrate our methods by applying them to the multitask lasso. We conclude by mentioning some open problems.