Universal Rates for Multiclass Learning
Steve Hanneke Shay Moran Qian Zhang
We study universal rates for multiclass classification, establishing the
optimal rates (up to log factors) for all hypothesis classes. This generalizes
previous results on binary classification (Bousquet, Hanneke, Moran, van
Handel, and Yehudayoff, 2021), and resolves an open question studied by
Kalavasis, Velegkas, and Karbasi (2022) who handled the multiclass setting with
a bounded number of class labels. In contrast, our result applies for any
countable label space. Even for finite label space, our proofs provide a more
precise bounds on the learning curves, as they do not depend on the number of
labels. Specifically, we show that any class admits exponential rates if and
only if it has no infinite Littlestone tree, and admits (near-)linear rates if
and only if it has no infinite Daniely-Shalev-Shwartz-Littleston (DSL) tree,
and otherwise requires arbitrarily slow rates. DSL trees are a new structure we
define in this work, in which each node of the tree is given by a pseudo-cube
of possible classifications of a given set of points. Pseudo-cubes are a
structure, rooted in the work of Daniely and Shalev-Shwartz (2014), and
recently shown by Brukhim, Carmon, Dinur, Moran, and Yehudayoff (2022) to
characterize PAC learnability (i.e., uniform rates) for multiclass
classification. We also resolve an open question of Kalavasis, Velegkas, and
Karbasi (2022) regarding the equivalence of classes having infinite
Graph-Littlestone (GL) trees versus infinite Natarajan-Littlestone (NL) trees,
showing that they are indeed equivalent.