Efficient transductive online learning via randomized rounding

DOI10.1007/978-3-642-41136-6_16zbMATH Open1330.68247DBLPconf/birthday/Cesa-BianchiS13arXiv1106.2429OpenAlexW2962826158WikidataQ59538559 ScholiaQ59538559MaRDI QIDQ5264100FDOQ5264100

Authors: Nicolò Cesa-Bianchi, Ohad Shamir 

Publication date: 20 July 2015

Published in: Empirical Inference (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1106.2429

Recommendations

• Near-optimal algorithms for online matrix prediction
• Online learning and online convex optimization
• Efficient algorithms for online decision problems.
• Sparse online learning via truncated gradient
• On the efficiency of a randomized mirror descent algorithm in online optimization problems

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Minimax procedures in statistical decision theory (62C20)

Cited In (1)

• Near-optimal algorithms for online matrix prediction

This page was built for publication: Efficient transductive online learning via randomized rounding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5264100)