Papers โบ Improved Kernel Alignment Regret Bound for Online Kernel Learning
Improved Kernel Alignment Regret Bound for Online Kernel Learning
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((๐_TTlnT)^(1/4)) at a computational complexity (space and per-round time) of O(โ(๐_TTlnT)), where ๐_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(โ(๐_T)) at a computational complexity of O(lnยฒT). Otherwise, our algorithm enjoys a regret of O((๐_TT)^(1/4)) at a computational complexity of O(โ(๐_TT)). We extend our algorithm to batch learning and obtain a O(1/Tโ(๐ผ[๐_T])) excess risk bound which improves the previous O(1/โ(T)) bound.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change ยท a person checks every report against the paper or source before anything changes; decisions are listed on /corrections