NeurIPS 2020
### Online Multitask Learning with Long-Term Memory

### Meta Review

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).
There were, however, several issues raised by the reviewers. It seems to me that most of them are related to a somewhat poor presentation of the results: unclear motivation, missing discussion on the prior knowledge the algorithm requires on the number of switches, time horizon, etc., writing which was difficult to follow at various places, and problems with evaluation of the technical part due to a long (50 pages) supplementary materials.
In my view, the negative reviews seem to be too critical of the paper contribution, while the positive one looks overly optimistic. I agree with the reviewers that the paper could have been written more clearly.
I also think, however, that issues raised by Reviewer #4 regarding the RKHS were properly addressed in the rebuttal.
I have asked the Senior Area Chair to take a closer look at this paper and discuss it further with other Senior Area Chairs.
After the discussion, the decision is that the paper is acceptable; hoping that the presentation will be improved for the final version.