Skip to yearly menu bar Skip to main content


Poster

Efficient Online Learning via Randomized Rounding

Nicolò Cesa-Bianchi · Ohad Shamir


Abstract:

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.

Live content is unavailable. Log in and register to view live content