Review for NeurIPS paper: Online Multitask Learning with Long-Term Memory

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).