home · mobile · calendar · colloquia · 2007-2008 · 

Colloquium - Singer

Efficient Projections Algorithms onto the L1 Ball for Learning Sparse Representations from High Dimension Data
Google, Inc.

We describe efficient algorithms for projecting a vector onto the L1-ball. We present two projection methods. The first method performs exact projection in O(n) time, where n is the dimension of the space. The second method works on vectors k of whose elements are perturbed outside the L1-ball, projecting in O(k log(n)) time. This setting is especially useful for online learning in sparse feature spaces, such as text categorization applications. We demonstrate the merits and effectiveness of our algorithms in numerous batch and online statistical learning tasks. We show that variants of gradient projection methods augmented with our efficient projection procedures outperform interior point methods, which are considered state-of-the-art optimization techniques. For least squares problems we show that the algorithm is competitive with a coordinate descent algorithm that was tailored to the problem. We also show that in online settings gradient updates with L1 projections outperform the entropic descent and exponentiated gradient algorithms while obtaining models with high degrees of sparsity.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)