Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back

Alon Cohen, Liad Erez, Steve Hanneke +4

The fundamental theorem of statistical learning states that binary PAC learning is governed by a single parameter -- the Vapnik-Chervonenkis (VC) dimension -- which determines both…