Online Multiclass Classification Based on Prediction Margin for Partial Feedback
This work addresses the problem of improving performance in online multiclass classification for applications with limited feedback, representing an incremental advancement over prior methods.
The paper tackles online multiclass classification with partial feedback by proposing a novel margin-based algorithm inspired by complementary labels, which deterministically handles feedback and achieves superior performance, as demonstrated through theoretical guarantees and experimental results showing it outperforms existing non-margin-based and stochastic methods.
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.