  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.
