# Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 25 references that are in the map.
- First posted on arXiv 9 Oct 2025.

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

- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [Molecule Generation for Drug Design: a Graph Learning Perspective](https://mlsanity.com/paper/2202.09212/) (2022)
- [On statistical learning via the lens of compression](https://mlsanity.com/paper/1610.03592/) (2016)
- [List Sample Compression and Uniform Convergence](https://mlsanity.com/paper/2403.10889/) (2024)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)
- [A Characterization of Multioutput Learnability](https://mlsanity.com/paper/2301.02729/) (2023)
- [On the Learnability of Multilabel Ranking](https://mlsanity.com/paper/2304.03337/) (2023)

## Abstract (arXiv)

In this paper we will give a characterization of the learnability of forgiving 0-1 loss functions in the multiclass setting with effectively finite cardinality of the output and label space. To do this, we create a new combinatorial dimension that is based off of the Natarajan Dimension and we show that a hypothesis class is learnable in our setting if and only if this Generalized Natarajan Dimension is finite. We also show how this dimension characterizes other known learning settings such as a vast amount of instantiations of learning with set-valued feedback and a modified version of list learning.