We introduce MTLAB, a new algorithm for learning multiple related tasks with strong theoretical guarantees. Its key idea is to perform learning sequentially over the data of all tasks, without interruptions or restarts at task boundaries. Predictors for individual tasks are derived from this process by an additional online-to-batch conversion step.

 By learning across task boundaries, MTLAB achieves a sublinear regret of true risks in the number of tasks. In the lifelong learning setting, this leads to an improved generalization bound that converges with the total number of samples across all observed tasks, instead of the number of examples per tasks or the number of tasks independently. At the same time, it is widely applicable: it can handle finite sets of tasks, as common in multi-task learning, as well as stochastic task sequences, as studied in lifelong learning. In recent years, machine learning has become a core technology in many commercially relevant applications. One observation in this context was that real-world learning tasks often do not occur in isolation, but rather as collections or temporal sequences of many, often highly related tasks. Examples include click-through rate prediction for online ads, personalized voice recognition for smart devices, or handwriting recognition of different languages.Multi-task learning BID3 has been developed exactly to handle such situations. It is based on an intuitive idea that sharing information between tasks should help the learning process and therefore lead to improved prediction quality. In practice, however, this is not guaranteed and multi-task learning can even lead to a reduction of prediction quality, so called negative transfer. The question when negative transfer occurs and how it can be avoided has triggered a surge of research interest to better understanding the theoretical properties of multi-task learning, as well as related research areas, such as lifelong learning BID1 BID9 , where more and more tasks occur sequentially, and task curriculum learning , where the order in which to learn tasks needs to be determined.In this work, we describe a new approach to multi-task learning that has strong theoretical guarantees, in particular improving the rate of convergence over some previous work. Our core idea is to decouple the process of predictor learning from the task structure. This is also the main difference of our approach to previous work, which typically learned one predictor for each task. We treat the available data for all tasks as parts of a single large online-learning problem, in which individual tasks simply correspond to subsets of the data stream that is processed. To obtain predictors for the individual tasks, we make use of online-to-batch conversion methods. We name the method MTLAB (multi-task learning across boundaries).Our main contribution is a sublinear bound on the task regret of MTLAB with true risks. As a corollary, we show that MTLAB improves the existing convergence rates in the case of lifelong learning. From the regret-type bounds, we derive high probability bounds on the expected risk of each task, which constitutes a second main contribution of our work.For real-world problems, not all tasks might be related to all previous ones. Our third contribution is a theoretically well-founded, yet practical, mechanism to avoid negative transfer in this case: we show that by splitting the set of tasks into homogeneous groups and using MTLAB to learn individual predictors on each of the resulting subsequences of samples, one obtains the same strong guarantees for each of the learned predictors while avoiding negative transfer. We introduced a new and widely applicable algorithm for sequentially learning of multiple tasks. By performing learning across tasks boundaries it is able to achieve a sublinear regret bound and improves the convergence rates in the lifelong learning scenario. MTLAB's way of not interrupting or restarting the learning process at task boundaries results in faster convergence rates than what can be achieved by learning individual predictors for each task: in particular, the generalization error decreases with the product of the number of tasks and the number of samples per task, instead of separately in each of these quantities. We also introduced a mechanism for the situation when the tasks to be learned are not all related to each other. We show that by constructing suitable subsequences of task, the convergence properties can hold even in this case.
A new algorithm for online multi-task learning that learns without restarts at the task borders
{"src": "scitldr-AIC_train", "paper_id": "HkllV5Bs24"}