skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · events · colloquia · 2007-2008 · 

Colloquium - Singer

ECCR 265

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.

The Department holds colloquia throughout the Fall and Spring semesters. These colloquia, open to the public, are typically held on Thursday afternoons, but sometimes occur at other times as well. If you would like to receive email notification of upcoming colloquia, subscribe to our Colloquia Mailing List. If you would like to schedule a colloquium, see Colloquium Scheduling.

Sign language interpreters are available upon request. Please contact Stephanie Morris at least five days prior to the colloquium.

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:29)