Exploiting the Surrogate Gap in Online Multiclass Classification

Dirk van der Hoeven

This summary provides an overview of the paper "Exploiting the Surrogate Gap in Online Multiclass Classification" by Dirk van der Hoeven, published at NeurIPS 2020.

TL;DR

The paper introduces GAPTRON, a randomized algorithm that achieves state-of-the-art performance in online multiclass classification. By cleverly exploiting the "gap" between the zero-one loss and convex surrogate losses, GAPTRON provides dimension-independent regret bounds and is the first linear-time algorithm to achieve $O(K\sqrt{T})$ regret in the challenging bandit feedback setting.

What Problem Does This Paper Address?

In online multiclass classification, a learner repeatedly receives a feature vector (like an image) and must predict its label (like "cat" or "dog"). The goal is to minimize the number of mistakes compared to the best possible fixed linear predictor.

There are two main flavors of this problem:

  1. Full Information: The learner sees the correct label after every prediction.
  2. Bandit Feedback: The learner only learns if their prediction was right or wrong—they don't see the true label if they guess incorrectly.

The core challenge is that the "true" error metric (zero-one loss) is non-convex and mathematically difficult to optimize. To solve this, researchers usually optimize a "surrogate loss" (like the hinge or logistic loss) that is convex and easier to handle. However, existing algorithms often suffer from regret bounds that grow with the dimension of the features ($d$) or require computationally expensive updates. GAPTRON aims to bridge this gap with an efficient, dimension-independent approach.

Methods

The authors introduce GAPTRON, a randomized first-order algorithm. Its mechanics are surprisingly elegant:

  • Weight Updates: It uses standard Online Gradient Descent (OGD) to update a weight matrix $W$ based on the gradient of a surrogate loss.
  • The "Gap Map": This is the paper's primary innovation. Instead of just picking the label with the highest score, GAPTRON uses a function $a(W, x)$ to create a probability distribution. This function is designed to exploit the surrogate gap—the mathematical difference between the zero-one loss and the surrogate loss.
Visualization of the surrogate gap between the zero-one loss and smooth hinge loss.
  • Randomized Prediction: The learner samples a label from this distribution. In the bandit setting, this includes a small amount of uniform exploration to ensure the learner keeps "trying" different labels to find the truth.

Unlike traditional proofs that rely on properties of the loss function itself (like exp-concavity), this paper’s proof technique focuses on how the surrogate loss relates to the zero-one loss, allowing for much tighter bounds.

Key Insights and Ideas

  • Dimension Independence: One of the most striking findings is that GAPTRON’s regret bounds do not depend on the dimension $d$ of the feature vector. This makes it theoretically superior for high-dimensional tasks where $d$ might be much larger than the number of classes $K$.
  • The Power of the Gap: The authors show that if you choose your prediction distribution carefully (via the gap map), the "extra" error introduced by the surrogate loss can actually cancel out the regret terms.
  • Efficiency: GAPTRON runs in $O(dK)$ time per round. In the bandit setting, it is the first algorithm to achieve the optimal $O(K\sqrt{T})$ regret while maintaining this linear time complexity. Previous algorithms with similar regret were often significantly slower (e.g., $O(d^2K^2)$ or worse).
  • Versatility: The framework works for multiple common losses, including logistic, hinge, and smooth hinge losses, simply by swapping out the specific "gap map" function.

Key Results

The paper provides several rigorous upper bounds on the expected number of mistakes ($M_T$):

Comparison of GAPTRON's regret bounds and time complexity against prior algorithms.
  • Full Information Setting: GAPTRON achieves $O(K)$ regret relative to the best linear predictor for logistic, hinge, and smooth hinge losses.
  • Bandit Setting: It achieves $O(KD\sqrt{T})$ expected regret (where $D$ is a bound on the norm of the comparator). This settles a long-standing open problem regarding the existence of a practical, linear-time algorithm with $O(\sqrt{T})$ regret in the bandit multiclass setting.
  • Comparison: As shown in the comparison table, GAPTRON matches or beats the regret of much more complex second-order methods (like ONS or Second-Order Perceptron) while being computationally cheaper.

Limitations and Future Work

  • Expected Regret: The current bounds hold "in expectation." The authors note that it would be valuable to prove that these bounds also hold with "high probability" (i.e., they aren't just true on average, but almost every time the algorithm runs).
  • Separable Case: In the "separable" setting (where a perfect predictor exists), GAPTRON is not yet optimal. Other specialized algorithms still perform better in that specific niche.
  • Deterministic vs. Randomized: GAPTRON is inherently randomized. In some industrial applications, deterministic behavior is preferred for reproducibility, which GAPTRON does not provide.
  • Empirical Validation: As a theory paper, it lacks "real-world" testing. Future work could involve benchmarking GAPTRON against standard libraries on large-scale multiclass datasets.

Summary updated

Abstract

We present \textproc{Gaptron}, a randomized first-order algorithm for online multiclass classification. In the full information setting we provide expected mistake bounds for \textproc{Gaptron} with respect to the logistic loss, hinge loss, and the smooth hinge loss with $O(K)$ regret, where the expectation is with respect to the learner's randomness and $K$ is the number of classes. In the bandit classification setting we show that \textproc{Gaptron} is the first linear time algorithm with $O(K\sqrt{T})$ expected regret. Additionally, the expected mistake bound of \textproc{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.
BibTeX
@inproceedings{hoeven2020exploiting,
  author = {Dirk van der Hoeven},
  title = {{Exploiting the Surrogate Gap in Online Multiclass Classification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=wEiHRRHeJ7K},
}
Figure