Unified Algorithms for Online Learning and Competitive Analysis
成果类型：
Article
署名作者：
Buchbinder, Niv; Chen, Shahar; Naor, Joseph (Seffi); Shamir, Ohad
署名单位：
Tel Aviv University; Technion Israel Institute of Technology; Weizmann Institute of Science
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2015.0742
发表日期：
2016
页码：
612-625
关键词：
摘要：
Online learning and competitive analysis are two widely studied frameworks for online decision-making settings. Despite the frequent similarity of the problems they study, there are significant differences in their assumptions, goals, and techniques, hindering a unified analysis and richer interplay between the two. In this paper, we provide several contributions in this direction. We provide a single unified algorithm, which, by parameter tuning, interpolates between optimal regret for learning from experts (in online learning) and optimal competitive ratio for the metrical task systems problem (MTS) (in competitive analysis), improving upon previous results. The algorithm also allows us to obtain new regret bounds against drifting experts, which might be of independent interest. Moreover, our approach allows us to go beyond experts/MTS, obtaining similar unifying results for structured action sets and combinatorial experts, whenever the setting has a certain matroid structure.
来源URL：