Efficient Transductive Online Learning via Randomized Rounding
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
Code (0)
등록된 구현이 없습니다.
Tasks
Collaborative FilteringOpen-Ended Question AnsweringSimilar Papers 제목 키워드 기반
Efficient Online Learning via Randomized Rounding
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 `…
BIG-bench Machine LearningCollaborative FilteringOpen-Ended Question AnsweringTradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
We study online and transductive online learning when the learner interacts with the concept class only via Empirical Risk Minimization (ERM) or weak consistency oracles on arbitrary instance subsets. This contrasts with…
2kNo-Regret Caching via Online Mirror Descent
We study an online caching problem in which requests can be served by a local cache to avoid retrieval costs from a remote server. The cache can update its state after a batch of requests and store an arbitrarily small f…
DiversityRetrievalTransductive and Learning-Augmented Online Regression
Motivated by the predictable nature of real-life in data streams, we study online regression when the learner has access to predictions about future examples. In the extreme case, called transductive online learning, the…
Optimal Mistake Bounds for Transductive Online Learning
We resolve a 30-year-old open problem concerning the power of unlabeled data in online learning by tightly quantifying the gap between transductive and standard online learning. In the standard setting, the optimal mista…