Abstract 
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 singletask setting this is equivalent to switching with longterm memory in the sense of [1]. 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 singletask special case this is the first example of an efficient regretbounded switching algorithm with longterm memory for a nonparametric hypothesis class. 
Authors 
 Mark Herbster (UCL)
 Stephen Pasteris (UCL)
 Lisa Tse (UCL)

Date 
Dec2020 
Venue 
Neural Information Processing Systems Online Conference 2020 [link] 
