The Taub Faculty of Computer Science Events and Talks
Shahar Chen (CS, Tehcnion)
Sunday, 25.03.2012, 16:30
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
work, 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 on the results
of Blum and Burch (1997). 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.
Joint work with Niv Buchbinder, Seffi Naor, and Ohad Shamir.