A No-Free-Lunch Theorem for MultiTask Learning

By Steve Hanneke, Samory Kpotufe. 2020

45 citations recorded by the source corpus.

Multitask learning and related areas such as multi-source domain adaptation address modern settings where datasets from $N$ related distributions $\{P_t\}$ are to be combined towards improving performance on any single such distribution ${\cal D}$. A perplexing fact remains in the evolving theory on the subject: while we would hope for performance bounds that account for the contribution from multiple tasks, the vast majority of analyses result in bounds that improve at best in the number $n$ of samples per task, but most often do not improve in $N$. As such, it might seem at first that the distributional settings or aggregation procedures considered in such analyses might be somehow unfavorable; however, as we show, the picture happens to be more nuanced, with interestingly hard regimes that might appear otherwise favorable. In particular, we consider a seemingly favorable classification scenario where all tasks $P_t$ share a common optimal classifier $h^*,$ and which can be shown to admit a broad range of regimes with improved oracle rates in terms of $N$ and $n$. Some of our main results are as follows: $\bullet$ We show that, even though such regimes admit minimax rates accounting for both $n$ and $N$, no adaptive algorithm exists; that is, without access to distributional information, no algorithm can guarantee rates that improve with large $N$ for $n$ fixed. $\bullet$ With a bit of additional information, namely, a ranking of tasks $\{P_t\}$ according to their distance to a target ${\cal D}$, a simple rank-based procedure can achieve near optimal aggregations of tasks' datasets, despite a search space exponential in $N$. Interestingly, the optimal aggregation might exclude certain tasks, even though they all share the same $h^*$.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Model Zoo: A Growing Brain That Learns Continually (2021, methodology): “We build upon Hanneke and Kpotufe (2019; 2020) to construct the transfer exponent in §2; their work shows that even in very favorable settings, e.g., when all tasks have the same optimal classiﬁer, having access to a large number of tasks may not help.”
Provable and Efficient Continual Representation Learning (2022, background): “More recent works [30, 51, 39, 65, 85, 24, 26, 86, 18, 76, 75, 55, 3, 13, 72] consider variations beyond supervised learning, concrete settings or established more refined upper/lower performance bounds.”