# Multitask Learning via Shared Features: Algorithms and Hardness

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 7 Sep 2022.

## Builds on (most cited first, 11 of 11)

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Revisiting Unreasonable Effectiveness of Data in Deep Learning Era](https://mlsanity.com/paper/1707.02968/) (2017)
- [Rapid Learning or Feature Reuse? Towards Understanding the Effectiveness of MAML](https://mlsanity.com/paper/1909.09157/) (2019)
- [How to train your MAML](https://mlsanity.com/paper/1810.09502/) (2018)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [The Benefit of Multitask Representation Learning](https://mlsanity.com/paper/1505.06279/) (2015)
- [On the Theory of Transfer Learning: The Importance of Task Diversity](https://mlsanity.com/paper/2006.11650/) (2020)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [MAML and ANIL Provably Learn Representations](https://mlsanity.com/paper/2202.03483/) (2022)
- [Sample Efficient Linear Meta-Learning by Alternating Minimization](https://mlsanity.com/paper/2105.08306/) (2021)
- [Efficient Representations for Life-Long Learning and Autoencoding](https://mlsanity.com/paper/1411.1490/) (2014)

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

- [Metalearning with Very Few Samples Per Task](https://mlsanity.com/paper/2312.13978/) (2023)
- [Few-shot Multi-Task Learning of Linear Invariant Features with Meta Subspace Pursuit](https://mlsanity.com/paper/2409.02708/) (2024)
- [Prompt and Parameter Co-Optimization for Large Language Models](https://mlsanity.com/paper/2509.24245/) (2025)
- [Transformers are almost optimal metalearners for linear classification](https://mlsanity.com/paper/2510.19797/) (2025)
- [When More Data Doesn't Help: Limits of Adaptation in Multitask Learning](https://mlsanity.com/paper/2601.20774/) (2026)

## Abstract (arXiv)

We investigate the computational efficiency of multitask learning of Boolean functions over the d-dimensional hypercube, that are related by means of a feature representation of size k ll d shared across all tasks. We present a polynomial time multitask learning algorithm for the concept class of halfspaces with margin γ, which is based on a simultaneous boosting technique and requires only textrmpoly(k/γ) samples-per-task and textrmpoly(klog(d)/γ) samples in total. In addition, we prove a computational separation, showing that assuming there exists a concept class that cannot be learned in the attribute-efficient model, we can construct another concept class such that can be learned in the attribute-efficient model, but cannot be multitask learned efficiently -- multitask learning this concept class either requires super-polynomial time complexity or a much larger total number of samples.