# A No-Free-Lunch Theorem for MultiTask Learning

arXiv: https://arxiv.org/abs/2006.15785 · HTML: https://mlsanity.com/paper/2006.15785/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2020.

## Built on by (most cited first, 28 of 28)

- [Transfer Learning under High-dimensional Generalized Linear Models](https://mlsanity.com/paper/2105.14328/) (2021)
- [Model Zoo: A Growing "Brain" That Learns Continually](https://mlsanity.com/paper/2106.03027/) (2021)
- [How Fine-Tuning Allows for Effective Meta-Learning](https://mlsanity.com/paper/2105.02221/) (2021)
- [Adaptive and Robust Multi-Task Learning](https://mlsanity.com/paper/2202.05250/) (2022)
- [Provable and Efficient Continual Representation Learning](https://mlsanity.com/paper/2203.02026/) (2022)
- [Multitask Learning and Bandits via Robust Statistics](https://mlsanity.com/paper/2112.14233/) (2021)
- [Metalearning with Very Few Samples Per Task](https://mlsanity.com/paper/2312.13978/) (2023)
- [Limits of Model Selection under Transfer Learning](https://mlsanity.com/paper/2305.00152/) (2023)
- [On the Generalization Ability of Unsupervised Pretraining](https://mlsanity.com/paper/2403.06871/) (2024)
- [A picture of the space of typical learnable tasks](https://mlsanity.com/paper/2210.17011/) (2022)
- [FedGKD: Unleashing the Power of Collaboration in Federated Graph Neural Networks](https://mlsanity.com/paper/2309.09517/) (2023)
- [Distributed Personalized Empirical Risk Minimization](https://mlsanity.com/paper/2310.17761/) (2023)
- [Help Me Help You: The Aggregate Value of Source and Target Data in Transfer Learning](https://mlsanity.com/paper/2408.16189/) (2024)
- [Provable Pathways: Learning Multiple Tasks over Multiple Paths](https://mlsanity.com/paper/2303.04338/) (2023)
- [Tight Rates in Supervised Outlier Transfer Learning](https://mlsanity.com/paper/2310.04686/) (2023)
- [Understanding Server-Assisted Federated Learning in the Presence of Incomplete Client Participation](https://mlsanity.com/paper/2405.02745/) (2024)
- [Transfer Learning for Latent Variable Network Models](https://mlsanity.com/paper/2406.03437/) (2024)
- [Collaborative Learning with Different Labeling Functions](https://mlsanity.com/paper/2402.10445/) (2024)
- [Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples](https://mlsanity.com/paper/2410.11227/) (2024)
- [Trans-Glasso: A Transfer Learning Approach to Precision Matrix Estimation](https://mlsanity.com/paper/2411.15624/) (2024)
- [The ART of Transfer Learning: An Adaptive and Robust Pipeline](https://mlsanity.com/paper/2305.00520/) (2023)
- [Mixture Weight Estimation and Model Prediction in Multi-source Multi-target Domain Adaptation](https://mlsanity.com/paper/2309.10736/) (2023)
- [When More Data Doesn't Help: Limits of Adaptation in Multitask Learning](https://mlsanity.com/paper/2601.20774/) (2026)
- [FLEA: Provably Robust Fair Multisource Learning from Unreliable Training Data](https://mlsanity.com/paper/2106.11732/) (2021)
- [Sample Complexity of Transfer Learning: An Optimal Transport Approach](https://mlsanity.com/paper/2605.20545/) (2026)
- [Capacity and Redundancy Trade-offs in Multi-Task Learning](https://mlsanity.com/paper/2607.16554/) (2026)
- [Optimal Learning Under Tsybakov Noise](https://mlsanity.com/paper/2608.08416/) (2026)
- [Grounding Time-Series Foundation Models in Digital Twin Topology for Predictive Maintenance](https://mlsanity.com/paper/2609.40071/) (2026)

## Abstract (arXiv)

Multitask learning and related areas such as multi-source domain adaptation address modern settings where datasets from N related distributions Pt 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 Pt 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 Pt 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^*.