Exploiting the Surrogate Gap in Online Multiclass Classification
This work addresses efficient online learning for multiclass classification, particularly in bandit settings, by offering a linear-time algorithm with improved regret bounds, though it is incremental in advancing existing methods.
The paper tackles online multiclass classification by introducing Gaptron, a randomized first-order algorithm that achieves expected mistake bounds with constant regret in full information settings and O(K√T) expected regret in bandit settings, with results independent of feature vector dimension.
We present Gaptron, a randomized first-order algorithm for online multiclass classification. In the full information setting we show expected mistake bounds with respect to the logistic loss, hinge loss, and the smooth hinge loss with constant regret, where the expectation is with respect to the learner's randomness. In the bandit classification setting we show that Gaptron is the first linear time algorithm with $O(K\sqrt{T})$ expected regret, where $K$ is the number of classes. Additionally, the expected mistake bound of Gaptron does not depend on the dimension of the feature vector, contrary to previous algorithms with $O(K\sqrt{T})$ regret in the bandit classification setting. We present a new proof technique that exploits the gap between the zero-one loss and surrogate losses rather than exploiting properties such as exp-concavity or mixability, which are traditionally used to prove logarithmic or constant regret bounds.