# Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 14 Jun 2023.

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

- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [Adaptive Regret of Convex and Smooth Functions](https://mlsanity.com/paper/1904.11681/) (2019)
- [A Closer Look at Small-loss Bounds for Bandits with Graph Feedback](https://mlsanity.com/paper/2002.00315/) (2020)
- [Small-loss bounds for online learning with partial information](https://mlsanity.com/paper/1711.03639/) (2017)
- [Second-Order Kernel Online Convex Optimization with Adaptive Sketching](https://mlsanity.com/paper/1706.04892/) (2017)
- [Efficient online learning with kernels for adversarial large scale problems](https://mlsanity.com/paper/1902.09917/) (2019)
- [Universal Online Convex Optimization Meets Second-order Bounds](https://mlsanity.com/paper/2105.03681/) (2021)
- [Improved Kernel Alignment Regret Bound for Online Kernel Learning](https://mlsanity.com/paper/2212.12989/) (2022)

## Abstract (arXiv)

The trade-off between regret and computational cost is a fundamental problem for online kernel regression, and previous algorithms worked on the trade-off can not keep optimal regret bounds at a sublinear computational complexity. In this paper, we propose two new algorithms, AOGD-ALD and NONS-ALD, which can keep nearly optimal regret bounds at a sublinear computational complexity, and give sufficient conditions under which our algorithms work. Both algorithms dynamically maintain a group of nearly orthogonal basis used to approximate the kernel mapping, and keep nearly optimal regret bounds by controlling the approximate error. The number of basis depends on the approximate error and the decay rate of eigenvalues of the kernel matrix. If the eigenvalues decay exponentially, then AOGD-ALD and NONS-ALD separately achieves a regret of O(√L(f)) and O(deff(μ)lnT) at a computational complexity in O(ln2T). If the eigenvalues decay polynomially with degree p≥ 1, then our algorithms keep the same regret bounds at a computational complexity in o(T) in the case of p>4 and p≥ 10, respectively. L(f) is the cumulative losses of f and deff(μ) is the effective dimension of the problem. The two regret bounds are nearly optimal and are not comparable.