Bandit Multiclass Linear Classification for the Group Linear Separable
  Case
  We consider the online multiclass linear classification under the bandit
feedback setting. Beygelzimer, P\'{a}l, Sz\"{o}r\'{e}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 $\gamma$, they presented an algorithm based on Multiclass
Perceptron with mistake bound $O(K/\gamma^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/\gamma))},K\cdot 2^{\tilde{O}(\sqrt{1/\gamma}\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/\gamma}\log
L)})$, where $L\leq K$ represents the number of groups.
