Title: Efficient Online Bandit Multiclass Learning with $\tilde{O}(\sqrt{T})$ Regret,
Abstract: We present an efficient second-order algorithm with
$\tilde{O}(\frac{1}{\eta}\sqrt{T})$ regret for the bandit online multiclass
problem. The regret bound holds simultaneously with respect to a family of loss
functions parameterized by $\eta$, for a range of $\eta$ restricted by the norm
of the competitor. The family of loss functions ranges from hinge loss
($\eta=0$) to squared hinge loss ($\eta=1$). This provides a solution to the
open problem of (J. Abernethy and A. Rakhlin. An efficient bandit algorithm for
$\sqrt{T}$-regret in online multiclass prediction? In COLT, 2009). We test our
algorithm experimentally, showing that it also performs favorably against
earlier algorithms.