Efficient Online Learning via Randomized Rounding
Nicolò Cesa-Bianchi · Ohad Shamir

Wed Dec 14th 12:00 -- 12:20 PM @ None

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.

Author Information

Nicolò Cesa-Bianchi (Università degli Studi di Milano, Italy)
Ohad Shamir (Weizmann Institute of Science)

More from the Same Authors