NIPS Proceedingsβ

Efficient Online Learning via Randomized Rounding

Part of: Advances in Neural Information Processing Systems 24 (NIPS 2011)

[PDF] [BibTeX] [Supplemental]



Most online algorithms used in machine learning today are based on variants of mirror descent or follow-the-leader. In this paper, we present an online algorithm based on a completely different approach, which combines ``random playout'' and randomized rounding of loss subgradients. As an application of our approach, we provide the first computationally efficient online algorithm for collaborative filtering with trace-norm constrained matrices. As a second application, we solve an open question linking batch learning and transductive online learning.