Exploiting the Surrogate Gap in Online Multiclass Classification

Abstract

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.

arXiv comment23 pages

References in corpus (5)

• Logistic Regression: Tight Bounds for Stochastic and Online Optimization
• Logistic Regression: The Importance of Being Improper
• Contextual bandits with surrogate losses: Margin bounds and efficient algorithms
• Fast Rates for Online Prediction with Abstention
• Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case

Cited by in corpus (1)

• Efficient Methods for Online Multiclass Logistic Regression