TY - GEN

T1 - Efficient projections onto the ℓ1-ball for learning in high dimensions

AU - Duchi, John

AU - Shalev-Shwartz, Shai

AU - Singer, Yoram

AU - Chandra, Tushar

PY - 2008/11/26

Y1 - 2008/11/26

N2 - We describe efficient algorithms for projecting a vector onto the ℓ1-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 ℓ1-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 ℓ1 projections outperform the exponentiated gradient algorithm while obtaining models with high degrees of sparsity.

AB - We describe efficient algorithms for projecting a vector onto the ℓ1-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 ℓ1-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 ℓ1 projections outperform the exponentiated gradient algorithm while obtaining models with high degrees of sparsity.

UR - http://www.scopus.com/inward/record.url?scp=56449092085&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=56449092085&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:56449092085

SN - 9781605582054

T3 - Proceedings of the 25th International Conference on Machine Learning

SP - 272

EP - 279

BT - Proceedings of the 25th International Conference on Machine Learning

T2 - 25th International Conference on Machine Learning

Y2 - 5 July 2008 through 9 July 2008

ER -