论文标题
在线多类分类中利用替代差距
Exploiting the Surrogate Gap in Online Multiclass Classification
论文作者
论文摘要
我们提出Gaptron，这是一种用于在线多类分类的随机一阶算法。在完整的信息设置中，我们显示了有关后勤损失，铰链损失和平稳铰链损失的预期错误界限，并持续遗憾，而在学习者的随机性方面的期望是在这种情况下。在Bandit分类设置中，我们表明Gaptron是第一个具有$ O（K \ sqrt {t}）$的线性时间算法预期的遗憾，其中$ k $是类的数量。此外，Gaptron的预期错误不取决于特征向量的维度，与以前具有$ O（K \ sqrt {t}）$的先前算法相反，在强盗分类设置中遗憾。我们提出了一种新的证明技术，该技术利用了零损失和替代损失之间的差距，而不是利用诸如Exp-Concavity或Mixability之类的特性，这些属性传统上被用来证明对数或持续的后悔界限。
We present Gaptron, a randomized first-order algorithm for online multiclass classification. In the full information setting we show expected mistake bounds with respect to the logistic loss, hinge loss, and the smooth hinge loss with constant regret, where the expectation is with respect to the learner's randomness. In the bandit classification setting we show that Gaptron is the first linear time algorithm with $O(K\sqrt{T})$ expected regret, where $K$ is the number of classes. Additionally, the expected mistake bound of Gaptron does not depend on the dimension of the feature vector, contrary to previous algorithms with $O(K\sqrt{T})$ regret in the bandit classification setting. We present a new proof technique that exploits the gap between the zero-one loss and surrogate losses rather than exploiting properties such as exp-concavity or mixability, which are traditionally used to prove logarithmic or constant regret bounds.
