论文标题
改进的内核对齐遗憾绑定到在线内核学习
Improved Kernel Alignment Regret Bound for Online Kernel Learning
论文作者
论文摘要
在本文中，我们改善了铰链损失功能政权中的在线内核学习的内核对齐遗憾。以前的算法在计算复杂度（空间和每一时间）$ o（\ sqrt {\ sqrt {\ sqrt {$ ntercal {$ ntercal {$ ntercal} $ \ MATHCAL {a} _t $称为\ textit {kernel Alignment}。我们提出了一种算法，其遗憾和计算复杂性比以前的结果更好。我们的结果取决于核基质的特征值的衰减率。如果呈核心矩阵衰减的特征值，那么我们的算法对$ O（\ sqrt {\ sqrt {\ sqrt {a} _t}）$感到遗憾，以$ o（\ ln^2 {t}）的计算复杂性处于计算上的复杂性。否则，我们的算法对$ o感到遗憾（（（\ Mathcal {a} _tt）^{\ frac {1} {4}}}）$在$ o（\ sqrt {\ sqrt {\ mathcal {a}} _tt}）的计算复杂性上。我们将算法扩展到批处理学习，并获得$ O（\ frac {1} {t} \ sqrt {\ Mathbb {e} [\ Mathcal {\ Mathcal {a} _t]}）$多余的风险绑定，从而改善了先前的$ O（1/\ \ sqrt {t} t}）$。
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.
