Most traditional online learning algorithms 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, tailored for transductive settings, which combines "random playout" and randomized rounding of loss subgradients. As an application of our approach, we present 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.
Efficient transductive online learning via randomized rounding / N. Cesa-Bianchi, O. Shamir - In: Empirical inference : festschrift in honor of Vladimir N. Vapnik / [a cura di] B. Schölkopf, Z. Luo, V. Vovk. - Berlin : Springer, 2013. - ISBN 9783642411366. - pp. 177-194 [10.1007/978-3-642-41136-6_16]
Efficient transductive online learning via randomized rounding
N. Cesa-Bianchi;
2013
Abstract
Most traditional online learning algorithms 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, tailored for transductive settings, which combines "random playout" and randomized rounding of loss subgradients. As an application of our approach, we present 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.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
