Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions
Not on the map. Why?
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 12 of its 25 references that are in the map. First posted on arXiv 9 Oct 2025.
Builds on
12 of 25 references.
References · 12
- 2022A Characterization of Multiclass Learnabilitycited by 66
- 2014Optimal Learners for Multiclass Problemscited by 65
- 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
- 2021Realizable Learning is All You Needcited by 25
- 2022A Characterization of List Learnabilitycited by 22
- 2022Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classescited by 14
- 2022Molecule Generation for Drug Design: a Graph Learning Perspectivecited by 13
- 2016On statistical learning via the lens of compressioncited by 10
- 2024List Sample Compression and Uniform Convergencecited by 10
- 2023Online Learning with Set-Valued Feedbackcited by 7
- 2023A Characterization of Multioutput Learnabilitycited by 2
- 2023On the Learnability of Multilabel Rankingcited by 2
Built on by
Not cited yet.