改进的在线核学习核对齐遗憾界本文改进了在线核学习中在Hinge损失函数的情形下的核对齐遗憾界。之前的算法在计算复杂度（空间和每轮时间）为$O(\sqrt{\mathcal{A}_TT\ln{T}})$的情况下，实现了遗憾界$O((\mathcal{A}_TT\ln{T})^{\frac{1}{4}})$，其中 $\mathcal{A}_T$ 被称为 \textit{核对齐度}。我们提出了一种算法，其遗憾界和计算复杂度均优于以前的结果。我们的结果取决于核矩阵的特征值的衰减速率。如果核矩阵的特征值指数衰减，那么我们的算法在计算复杂度为$O(\ln^2{T})$的情况下会得到$O(\sqrt{\mathcal{A}_T})$的遗憾界。否则，我们的算法在计算复杂度为$O(\sqrt{\mathcal{A}_TT})$的情况下获得$O((\mathcal{A}_TT)^{\frac{1}{4}})$的遗憾界。我们将我们的算法扩展到批量学习中，并获得了$O(\frac{1}{T}\sqrt{\mathbb{E}[\mathcal{A}_T]})$的超额风险界，该界优于以前的$O(1/\sqrt{T})$界。 (Improved Kernel Alignment Regret Bound for Online Kernel Learning)

翻译：改进的在线核学习核对齐遗憾界本文改进了在线核学习中在Hinge损失函数的情形下的核对齐遗憾界。之前的算法在计算复杂度（空间和每轮时间）为$O(\sqrt{\mathcal{A}_TT\ln{T}})$的情况下，实现了遗憾界$O((\mathcal{A}_TT\ln{T})^{\frac{1}{4}})$，其中 $\mathcal{A}_T$ 被称为 \textit{核对齐度}。我们提出了一种算法，其遗憾界和计算复杂度均优于以前的结果。我们的结果取决于核矩阵的特征值的衰减速率。如果核矩阵的特征值指数衰减，那么我们的算法在计算复杂度为$O(\ln^2{T})$的情况下会得到$O(\sqrt{\mathcal{A}_T})$的遗憾界。否则，我们的算法在计算复杂度为$O(\sqrt{\mathcal{A}_TT})$的情况下获得$O((\mathcal{A}_TT)^{\frac{1}{4}})$的遗憾界。我们将我们的算法扩展到批量学习中，并获得了$O(\frac{1}{T}\sqrt{\mathbb{E}[\mathcal{A}_T]})$的超额风险界，该界优于以前的$O(1/\sqrt{T})$界。

Junfan Li,Shizhong Liao

In this paper, we improve the kernel alignment regret bound for online kernel learning in the regime of the Hinge loss function. Previous algorithm achieves a regret of $O((\mathcal{A}_TT\ln{T})^{\frac{1}{4}})$ at a computational complexity (space and per-round time) of $O(\sqrt{\mathcal{A}_TT\ln{T}})$, where $\mathcal{A}_T$ is called \textit{kernel alignment}. We propose an algorithm whose regret bound and computational complexity are better than previous results. Our results depend on the decay rate of eigenvalues of the kernel matrix. If the eigenvalues of the kernel matrix decay exponentially, then our algorithm enjoys a regret of $O(\sqrt{\mathcal{A}_T})$ at a computational complexity of $O(\ln^2{T})$. Otherwise, our algorithm enjoys a regret of $O((\mathcal{A}_TT)^{\frac{1}{4}})$ at a computational complexity of $O(\sqrt{\mathcal{A}_TT})$. We extend our algorithm to batch learning and obtain a $O(\frac{1}{T}\sqrt{\mathbb{E}[\mathcal{A}_T]})$ excess risk bound which improves the previous $O(1/\sqrt{T})$ bound.

翻译：改进的在线核学习核对齐遗憾界本文改进了在线核学习中在Hinge损失函数的情形下的核对齐遗憾界。之前的算法在计算复杂度（空间和每轮时间）为$O(\sqrt{\mathcal{A}_TT\ln{T}})$的情况下，实现了遗憾界$O((\mathcal{A}_TT\ln{T})^{\frac{1}{4}})$，其中 $\mathcal{A}_T$ 被称为核对齐度。我们提出了一种算法，其遗憾界和计算复杂度均优于以前的结果。我们的结果取决于核矩阵的特征值的衰减速率。如果核矩阵的特征值指数衰减，那么我们的算法在计算复杂度为 $O(\ln^2{T})$ 的情况下会得到 $O(\sqrt{\mathcal{A}_T})$ 的遗憾界。否则，我们的算法在计算复杂度为 $O(\sqrt{\mathcal{A}_TT})$ 的情况下获得 $O((\mathcal{A}_TT)^{\frac{1}{4}})$ 的遗憾界。我们将我们的算法扩展到批量学习中，并获得了 $O(\frac{1}{T}\sqrt{\mathbb{E}[\mathcal{A}_T]})$ 的超额风险界，该界优于以前的 $O(1/\sqrt{T})$ 界。