{"ID":2858259,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.08382","arxiv_id":"2510.08382","title":"Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions","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.","short_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 cl...","url_abs":"https://arxiv.org/abs/2510.08382","url_pdf":"https://arxiv.org/pdf/2510.08382v3","authors":"[\"Jacob Trauger\",\"Tyson Trauger\",\"Ambuj Tewari\"]","published":"2025-10-09T16:07:55Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}