Efficient Online Learning via Randomized Rounding

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

Bibtex »Metadata »Paper »Supplemental »


Nicolò Cesa-bianchi, Ohad Shamir


<p>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.</p>