# A Characterization of Multioutput Learnability

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 42 references that are in the map.
- First posted on arXiv 6 Jan 2023.

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

- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [The price of bandit information in multiclass online classification](https://mlsanity.com/paper/1302.1043/) (2013)
- [Multi-Label Learning with Deep Forest](https://mlsanity.com/paper/1911.06557/) (2019)

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

- [On the Learnability of Multilabel Ranking](https://mlsanity.com/paper/2304.03337/) (2023)
- [Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions](https://mlsanity.com/paper/2510.08382/) (2025)

## Abstract (arXiv)

We consider the problem of learning multioutput function classes in the batch and online settings. In both settings, we show that a multioutput function class is learnable if and only if each single-output restriction of the function class is learnable. This provides a complete characterization of the learnability of multilabel classification and multioutput regression in both batch and online settings. As an extension, we also consider multilabel learnability in the bandit feedback setting and show a similar characterization as in the full-feedback setting.