A Characterization of Multiclass Learnability

A seminal result in learning theory characterizes the PAC learnability of binary classes through the VC dimension. Extending this characterization to the general multiclass setting has been open since the late 1980s.

We resolve this problem by characterizing multiclass PAC learnability through the DS dimension, a combinatorial dimension defined by Daniely and Shalev-Shwartz (2014).

The classical characterization of the binary case boils down to empirical risk minimization. In contrast, our characterization of the multiclass case involves a variety of algorithmic ideas; these include a natural setting we call list PAC learning. In the list learning setting, instead of predicting the label of a given unseen input, the goal is to provide a short list of labels which contains the correct one with high probability.

Our second main result concerns the Natarajan dimension, which has been a central candidate for characterizing multiclass learnability. This dimension was introduced by Natarajan (1988) as a barrier for PAC learning. Whether the Natarajan dimension characterizes PAC learnability in general has been posed as an open question in several papers since. We provide a negative answer: we construct a non-learnable class with Natarajan dimension one.

For the construction, we identify a fundamental connection between concept classes and topology. We crucially rely on a deep and involved geometric-group-theoretic construction by Januszkiewicz and Swiatkowski. This proof provides another demonstration of the fruitful links learning theory has with different areas in mathematics.

Joint work with Daniel Carmon, Irit Dinur, Shay Moran and Amir Yehudayoff.