Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back

The fundamental theorem of statistical learning establishes that binary PAC learning is governed by a single parameter—the Vapnik-Chervonenkis (VC) dimension—which controls both learnability and sample complexity. Extending this characterization to multiclass classification has long been challenging, since the early work of Natarajan in the late 80’s that proposed the Natarajan dimension (Nat) as a natural analogue of the VC dimension. Daniely and Shalev-Shwartz (2014) introduced the DS dimension, later shown by Brukhim et al. (2022) to characterize multiclass learnability. Brukhim et al. (2022) also demonstrated that the Natarajan and DS dimensions can diverge arbitrarily, so that multiclass learning appears to be governed by DS rather than Nat. We show that the agnostic multiclass PAC sample complexity is in fact governed by two distinct dimensions. Specifically, we prove nearly tight agnostic sample complexity bounds that, up to logarithmic factors, take the form DS1.5 / є + Nat / є2   where є is the excess risk. This bound is tight up to a √DS factor in the first lower-order term, nearly matching known Nat/є2 and DS/є lower bounds. The first term reflects the DS-controlled regime, while the second reveals that the Natarajan dimension still dictates asymptotic behavior for small є. Thus, unlike in binary or online classification—where a single dimension (VC or Littlestone) controls both phenomena—multiclass learning inherently involves two structural parameters. Our technical approach departs significantly from traditional agnostic learning methods based on uniform convergence or reductions-to-realizable techniques. A key ingredient is a novel online procedure, based on a self-adaptive multiplicative-weights algorithm which performs a label-space reduction. This approach may be of independent interest and find further applications.