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.
Introduction
In online multiclass classification, a learner iteratively receives a feature vector, predicts a label, and receives feedback. This problem is typically studied in two settings: Full Information, where the true label is revealed regardless of the prediction, and the Bandit setting, where the learner only learns if their specific prediction was correct or incorrect.
The primary metric for performance is the zero-one loss, which simply tracks whether a prediction was correct. However, because this loss is non-convex and computationally difficult to optimize directly, researchers rely on convex surrogate losses (such as logistic or hinge loss). Historically, the challenge has been to develop algorithms that are both computationally efficient (linear time) and provide tight regret bounds—measuring how much worse the learner performs compared to the best fixed predictor in hindsight.
The Gaptron Algorithm
Gaptron is a randomized, first-order algorithm that builds upon Online Gradient Descent (OGD) but introduces a novel mechanism called the Gap Map ($a$). Instead of a deterministic prediction, Gaptron generates a probability distribution over labels. It mixes the label with the highest predicted score with a uniform distribution over all possible labels.
The mixing weight is determined by the gap map, which is specifically engineered to exploit the mathematical relationship between the zero-one loss and the chosen surrogate loss. This approach allows Gaptron to be versatile, supporting major loss functions including logistic loss, hinge loss, and smooth hinge loss.
Exploiting the Surrogate Gap
Traditional regret analysis often relies on specific properties of the surrogate loss, such as exp-concavity or mixability. Gaptron shifts this paradigm by focusing on the "surrogate gap"—the difference between the expected zero-one loss and the surrogate loss.
By ensuring this gap remains non-positive through the gap map, the algorithm achieves superior regret bounds without requiring the complex second-order calculations typically needed for logarithmic or constant regret. This technique simplifies the underlying proofs and results in better constants within the regret bounds.
Key Results and Complexity
Gaptron achieves state-of-the-art performance across both information settings while maintaining high computational efficiency. Notably, its regret bounds are dimension-independent, meaning they do not grow with the size of the feature vector ($d$). This is a significant advantage for high-dimensional datasets where previous $O(K\sqrt{T})$ bandit algorithms were constrained by the dimensionality.
As summarized in the comparison table, Gaptron matches or exceeds the regret performance of complex second-order methods like Online Newton Step (ONS) or Vovk’s Aggregating Algorithm, while remaining as fast as the simple Perceptron ($O(dK)$ per round). It is the first algorithm to achieve the optimal $O(K\sqrt{T})$ bandit regret with linear time complexity.
Discussion and Future Work
While Gaptron provides a significant leap in efficiency and regret performance, several avenues for future research remain. Currently, the regret bounds hold "in expectation," meaning they describe average performance; establishing high-probability bounds is an ongoing challenge. Additionally, in the "separable" bandit setting (where a perfect predictor exists), Gaptron still suffers $\sqrt{T}$ regret, whereas more complex algorithms can achieve $O(K)$ regret. Bridging the gap between the efficiency of Gaptron and the performance of these specialized algorithms in separable or stochastic settings remains an open problem.
Summary updated