Bandit Multiclass Linear Classification for the Group Linear Separable Case
This work addresses the problem of improving mistake bounds in bandit multiclass classification for researchers in online learning, but it is incremental as it builds on prior work by extending separability notions.
The paper tackles online multiclass linear classification with bandit feedback by refining weak linear separability to include class grouping, resulting in a mistake bound of K * 2^(tilde{O}(sqrt(1/γ) log L)), where L is the number of groups and L ≤ K.
We consider the online multiclass linear classification under the bandit feedback setting. Beygelzimer, Pál, Szörényi, Thiruvenkatachari, Wei, and Zhang [ICML'19] considered two notions of linear separability, weak and strong linear separability. When examples are strongly linearly separable with margin $γ$, they presented an algorithm based on Multiclass Perceptron with mistake bound $O(K/γ^2)$, where $K$ is the number of classes. They employed rational kernel to deal with examples under the weakly linearly separable condition, and obtained the mistake bound of $\min(K\cdot 2^{\tilde{O}(K\log^2(1/γ))},K\cdot 2^{\tilde{O}(\sqrt{1/γ}\log K)})$. In this paper, we refine the notion of weak linear separability to support the notion of class grouping, called group weak linear separable condition. This situation may arise from the fact that class structures contain inherent grouping. We show that under this condition, we can also use the rational kernel and obtain the mistake bound of $K\cdot 2^{\tilde{O}(\sqrt{1/γ}\log L)})$, where $L\leq K$ represents the number of groups.