# Improved Kernel Alignment Regret Bound for Online Kernel Learning

arXiv: https://arxiv.org/abs/2212.12989 · HTML: https://mlsanity.com/paper/2212.12989/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 25 references that are in the map.
- First posted on arXiv 26 Dec 2022.

## Builds on (most cited first, 3 of 3)

- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Combining Online Learning Guarantees](https://mlsanity.com/paper/1902.09003/) (2019)
- [Second-Order Kernel Online Convex Optimization with Adaptive Sketching](https://mlsanity.com/paper/1706.04892/) (2017)

## Built on by (most cited first, 2 of 2)

- [Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression](https://mlsanity.com/paper/2306.08320/) (2023)
- [Learnability in Online Kernel Selection with Memory Constraint via Data-dependent Regret Analysis](https://mlsanity.com/paper/2407.00916/) (2024)

## Abstract (arXiv)

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((ATTlnT)^frac14) at a computational complexity (space and per-round time) of O(√ATTlnT), where AT is called textitkernel 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(√AT) at a computational complexity of O(ln2T). Otherwise, our algorithm enjoys a regret of O((ATT)^frac14) at a computational complexity of O(√ATT). We extend our algorithm to batch learning and obtain a O(frac1T√mathbbE[AT]) excess risk bound which improves the previous O(1/√T) bound.