Online Multitask Learning with Long-Term Memory
This work addresses the challenge of efficient online learning with memory in multitask settings, offering incremental improvements by extending switching algorithms to non-parametric hypothesis classes.
The paper tackles the problem of online multitask learning where tasks are partitioned into unknown segments with associated hypotheses, aiming to exploit scenarios with many segments but fewer hypotheses. It provides algorithms with proven regret bounds for any segmentation and hypothesis association, achieving linear time per trial for finite hypothesis classes and cubic time for infinite classes in the single-task case.
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; 2003]. 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.