Online Agnostic Multiclass Boosting
Boosting is a fundamental approach in machine learning that enjoys both
strong theoretical and practical guarantees. At a high-level, boosting
algorithms cleverly aggregate weak learners to generate predictions with
arbitrarily high accuracy. In this way, boosting algorithms convert weak
learners into strong ones. Recently, Brukhim et al. extended boosting to the
online agnostic binary classification setting. A key ingredient in their
approach is a clean and simple reduction to online convex optimization, one
that efficiently converts an arbitrary online convex optimizer to an agnostic
online booster. In this work, we extend this reduction to multiclass problems
and give the first boosting algorithm for online agnostic mutliclass
classification. Our reduction also enables the construction of algorithms for
statistical agnostic, online realizable, and statistical realizable multiclass
boosting.