[2510.08382] Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions

Computer Science > Machine Learning arXiv:2510.08382 (cs) [Submitted on 9 Oct 2025 (v1), last revised 3 Mar 2026 (this version, v3)] Title:Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions Authors:Jacob Trauger, Tyson Trauger, Ambuj Tewari View a PDF of the paper titled Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions, by Jacob Trauger and 2 other authors View PDF Abstract: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. Comments: Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML) Cite as: arXiv:2510.08382 [cs.LG]   (or arXiv:2510.08382v3 [cs.LG] for this version)   https://doi.org/10.48550/arXiv.2510.08382 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Jacob Trauger [view email] [v1] Thu, 9 Oct 2025 16:07:55 UTC (15 KB) [v2] Fri, 10 Oct 2025 15:45:42 UTC (15 KB) [v3] Tue, 3 Mar 2026 18:31:08 UTC (26 KB) Full-text links: Access Paper:...