An Efficient Projection for L1,infinity Regularization

Abstract

In recent years the l₁, _∞ norm has been proposed for joint regularization. In essence, this type of regularization aims at extending the l₁ framework for learning sparse models to a setting where the goal is to learn a set of jointly sparse models. In this paper we derive a simple and effective projected gradient method for optimization of l₁, _∞ regularized problems. The main challenge in developing such a method resides on being able to compute efficient projections to the l₁, _∞ ball. We present an algorithm that works in O(n log n) time and O(n) memory where n is the number of parameters. We test our algorithm in a multi-task image annotation problem. Our results show that l₁, _∞ leads to better performance than both l₂ and l₁ regularization and that it is is effective in discovering jointly sparse solutions.