Efficient Projections onto the L1-Ball for Learning in High Dimensions

author: Yoram Singer, The Hebrew University of Jerusalem
published: Aug. 29, 2008,   recorded: July 2008,   views: 7715


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


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) 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 state-of-the-art optimization techniques such as interior point methods. We also show that in online settings gradient updates with L1 projections outperform the EG algorithm while obtaining models with high degrees of sparsity.

Disclaimer: VideoLectures.NET emphasizes that this talk was not recorded in its full duration but due to its content value was published.

See Also:

Download slides icon Download slides: icml08_singer_ep_01.pdf (5.3┬áMB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 jk, August 30, 2008 at 5:57 p.m.:

Why is not the whole video available?
(video stops much before the talk finishes)

Write your own review or comment:

make sure you have javascript enabled or clear this field: