Multiclass Online Learning and Uniform Convergence
This resolves a long-standing theoretical gap in online learning for multiclass settings, with implications for algorithm design in adversarial environments.
The paper solves the open problem of agnostic adversarial online learnability for multiclass classification by proving that a concept class is learnable if and only if its Littlestone dimension is finite, and demonstrates a separation between online learnability and uniform convergence with an unbounded sequential Rademacher complexity example.
We study multiclass classification in the agnostic adversarial online learning setting. As our main result, we prove that any multiclass concept class is agnostically learnable if and only if its Littlestone dimension is finite. This solves an open problem studied by Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011,2015) who handled the case when the number of classes (or labels) is bounded. We also prove a separation between online learnability and online uniform convergence by exhibiting an easy-to-learn class whose sequential Rademacher complexity is unbounded. Our learning algorithm uses the multiplicative weights algorithm, with a set of experts defined by executions of the Standard Optimal Algorithm on subsequences of size Littlestone dimension. We argue that the best expert has regret at most Littlestone dimension relative to the best concept in the class. This differs from the well-known covering technique of Ben-David, Pál, and Shalev-Shwartz (2009) for binary classification, where the best expert has regret zero.