Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions

Classification is one of the most common tasks in machine learning. Within classification, there is normally a split between binary classification (only two possible outputs) and multiclass classification (more than two possible outputs). The theoretical analysis of these settings shares the same split. Under the P AC-learning model, binary classification learnability under the 0-1 loss is known to be characterized by the VC-dimension [V apnik and Chervonenkis, 1974, Shalev-Shwartz and Ben-David, 2014]. For multiclass classification, there has also been a further split between finite and infinite label cases.