# Exploiting the Surrogate Gap in Online Multiclass Classification

arXiv: https://arxiv.org/abs/2007.12618 · HTML: https://mlsanity.com/paper/2007.12618/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2020.

## Built on by (most cited first, 9 of 9)

- [FedSpeed: Larger Local Interval, Less Communication Round, and Higher Generalization Accuracy](https://mlsanity.com/paper/2302.10429/) (2023)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [Efficient Methods for Online Multiclass Logistic Regression](https://mlsanity.com/paper/2110.03020/) (2021)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts](https://mlsanity.com/paper/2307.00836/) (2023)
- [Bandit and Delayed Feedback in Online Structured Prediction](https://mlsanity.com/paper/2502.18709/) (2025)
- [Online Learning-to-Defer with Varying Experts](https://mlsanity.com/paper/2605.12340/) (2026)
- [Non-Stationary Online Structured Prediction with Surrogate Losses](https://mlsanity.com/paper/2510.07086/) (2025)

## Abstract (arXiv)

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√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√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.