# Online Multiclass Classification Based on Prediction Margin for Partial Feedback

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2019.

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

- [Class-Imbalanced Complementary-Label Learning via Weighted Loss](https://mlsanity.com/paper/2209.14189/) (2022)
- [Adversarial Training with Complementary Labels: On the Benefit of Gradually Informative Attacks](https://mlsanity.com/paper/2211.00269/) (2022)

## Abstract (arXiv)

We consider the problem of online multiclass classification with partial feedback, where an algorithm predicts a class for a new instance in each round and only receives its correctness. Although several methods have been developed for this problem, recent challenging real-world applications require further performance improvement. In this paper, we propose a novel online learning algorithm inspired by recent work on learning from complementary labels, where a complementary label indicates a class to which an instance does not belong. This allows us to handle partial feedback deterministically in a margin-based way, where the prediction margin has been recognized as a key to superior empirical performance. We provide a theoretical guarantee based on a cumulative loss bound and experimentally demonstrate that our method outperforms existing methods which are non-margin-based and stochastic.