Technical Report PHD-2015-07

Title: Online Learning and Competitive Analysis: a Unified Approach
Authors: Shahar Chen
Supervisors: Seffi Naor, Niv Buchbinder
Abstract: 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 research we provide several contributions in this direction.

First, 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.

A complementary direction of our research tries to ``borrow'' various learning techniques, specifically focusing on the online convex optimization domain, in order to obtain new results in the competitive analysis framework. We show how \emph{regularization}, a fundamental method in machine learning and particularly in the field of online learning, can be applied to obtain new results in the area of competitive analysis. We also show how \emph{convex conjugacy} and \emph{Fenchel duality}, other powerful techniques used in online convex optimization and learning, can be used in the competitive analysis setting, allowing us to cope with a richer world of online optimization problems.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2015
To the main CS technical reports page

Computer science department, Technion