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 ``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.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningCollaborative FilteringOpen-Ended Question AnsweringSimilar Papers 제목 키워드 기반
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 …
Collaborative FilteringOpen-Ended Question AnsweringNo-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…
DiversityRetrievalUniversal Algorithm for Online Trading Based on the Method of Calibration
We present a universal algorithm for online trading in Stock Market which performs asymptotically at least as good as any stationary trading strategy that computes the investment at each step using a fixed function of th…
Online Weighted Paging with Unknown Weights
Online paging is a fundamental problem in the field of online algorithms, in which one maintains a cache of $k$ slots as requests for fetching pages arrive online. In the weighted variant of this problem, each page has i…
Online Multi-Class Selection with Group Fairness Guarantee
We study the online multi-class selection problem with group fairness guarantees, where limited resources must be allocated to sequentially arriving agents. Our work addresses two key limitations in the existing literatu…