When More Data Doesn't Help: Limits of Adaptation in Multitask Learning

Multitask learning and related frameworks have achieved tremendous success in modern applications. In multitask learning problem, we are given a set of heterogeneous datasets collected from related source tasks and hope to enhance the performance above what we could hope to achieve by solving each of them individually. The recent work of Hanneke & Kpotufe (2022) has showed that, without access to distributional information, no algorithm based on aggregating samples alone can guarantee optimal risk as long as the sample size per task is bounded. In this paper, we focus on understanding the statistical limits of multitask learning. We go beyond the no-free-lunch theorem in Hanneke & Kpotufe (2022) by establishing a stronger impossibility result of adaptation that holds for arbitrarily large sample size per task. This improvement conveys an important message that the hardness of multitask learning cannot be overcame by having abundant data per task. We also discuss the notion of optimal adaptivity that may be of future interests.

For multitask learning, can we design adaptive algorithms, i.e., algorithms that can automatically identify the optimal aggregation of datasets without access to distributional information? Previous work has answered this question negatively under a significant constraint that sample size per task is bounded in terms of noise level. We want to understand whether adaptivity is possible when local sample size is large. The main contribution of our paper is the surprising result that even with arbitrarily large sample size per task, adaptivity is still impossible. This is surprising since having more samples per task is commonly believed to yield some advantages from having multiple tasks as suggested by the classical no-free-lunch theorem. In addition, we propose the question of what is the optimal adaptive multitask learner and take the first step towards answering this question by proving that pooling all datasets is not always the best adaptive algorithm. Our results reveal the following practical implication - for scientists who hope to design better multitask learners, they need to somehow leverage additional information such as which datasets are less contaminated or which sources are more relevant to the target environment, rather than merely rely on data.