We introduce a novel online multitask setting. In this setting each task is partitioned into a sequence of segments that is unknown to the learner. Associated with each segment is a hypothesis from some hypothesis class. We give algorithms that are designed to exploit the scenario where there are many such segments but significantly fewer associated hypotheses. We prove regret bounds that hold for any segmentation of the tasks and any association of hypotheses to the segments. In the single-task setting this is equivalent to switching with long-term memory in the sense of [Bousquet and Warmuth 2011]. We provide an algorithm that predicts on each trial in time linear in the number of hypotheses when the hypothesis class is finite. We also consider infinite hypothesis classes from reproducing kernel Hilbert spaces for which we give an algorithm whose per trial time complexity is cubic in the number of cumulative trials. In the single-task special case this is the first example of an efficient regret-bounded switching algorithm with long-term memory for a non-parametric hypothesis class.

Weaknesses: Unfortunately, the paper has several major weaknesses: * In the online multitask expert setting (Section 3), the authors claim that their framework is more general than the related work [1,3,4,7], by allowing switches between hypotheses for each class. Yet, the number m of modes is known in advance. So, for each task i \in [s], we know that there are at most m best hypotheses. Thus, unless I missed something, we can simply replace the s tasks by m \times s ones (i.e. each task in [s] consists of m different subtasks), and just apply the results obtained by [1] for the shifting multitask problem with expert advice (Corollary 1 in [1]) in order to get a bound that is essentially similar to (3). Still, I am aware that there are some differences between [1] and the present paper.

The paper concerns a multi-task version of a well-known online learning problem of switching with long-term memory. It considers two two types of the hypothesis spaces: a finite space, and an RKHS space of functions. In both cases, the authors first provide a regret bound for an exponential-time algorithm based on a reduction to a single-task problem using the idea of „meta-experts". These algorithms are then followed by their efficient (polynomial-time) versions, which achieve the same bound up to a small overhead. The paper received a very mixed set of scores, ranging from „reject" to „to 15% of accepted papers". The main strength of the paper is a novel, efficient long-term memory algorithms for a multi-task version of the prediction with expert advice problem, as well as kernel linear classification (with hinge loss, but written in terms of 0/1 loss by only considering interpolants on an instance sequence). In particular, the second part seems a significant extension of the „switching with long-term memory" framework to an infinite hypothesis space (even leaving the multitask extension aside).

We introduce a novel online multitask setting. In this setting each task is partitioned into a sequence of segments that is unknown to the learner. Associated with each segment is a hypothesis from some hypothesis class. We give algorithms that are designed to exploit the scenario where there are many such segments but significantly fewer associated hypotheses. We prove regret bounds that hold for any segmentation of the tasks and any association of hypotheses to the segments.