Efficient transductive online learning via randomized rounding

DOI10.1007/978-3-642-41136-6_16MaRDI QIDQ5264100zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Nicolò Cesa-Bianchi, Ohad Shamir

Publication date 20 July 2015

Published in Empirical Inference (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

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

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

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)