Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper LearningResearch Paper
In binary classification, every PAC learnable class can be learned by a proper learner, one that always outputs a member of the class: empirical risk minimization does it, and learnability is characterized by the VC dimension. With many labels the picture changes. Daniely and Shalev-Shwartz introduced the DS dimension and conjectured that it characterizes…