Title
Efficient projections onto the l1-ball for learning in high dimensions
Abstract
We describe efficient algorithms for projecting a vector onto the l1-ball. We present two methods for projection. The first performs exact projection in O(n) expected time, where n is the dimension of the space. The second 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 learning tasks. We show that variants of stochastic gradient projection methods augmented with our efficient projection procedures outperform interior point methods, which are considered state-of-the-art optimization techniques. We also show that in online settings gradient updates with l1 projections outperform the exponentiated gradient algorithm while obtaining models with high degrees of sparsity.
Year
DOI
Venue
2008
10.1145/1390156.1390191
ICML
Keywords
DocType
Citations 
online setting,l1 projection,exact projection,exponentiated gradient algorithm,expected time,online learning,high dimension,stochastic gradient projection method,efficient projection procedure,efficient algorithm,gradient updates
Conference
101
PageRank 
References 
Authors
7.02
8
4
Search Limit
100101
Name
Order
Citations
PageRank
John C. Duchi1164898.77
Shai Shalev-Shwartz23681276.32
Y Singer3134551559.02
Tushar Deepak Chandra45163388.99