# Efficient online learning with kernels for adversarial large scale problems

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2019.

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

- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Mixability made efficient: Fast online multiclass logistic regression](https://mlsanity.com/paper/2110.03960/) (2021)
- [Online nonparametric regression with Sobolev kernels](https://mlsanity.com/paper/2102.03594/) (2021)
- [Dynamic Regret Reduces to Kernelized Static Regret](https://mlsanity.com/paper/2507.05478/) (2025)
- [Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR](https://mlsanity.com/paper/2111.11550/) (2021)
- [Provably Efficient Kernelized Q-Learning](https://mlsanity.com/paper/2204.10349/) (2022)
- [Efficient Kernel UCB for Contextual Bandits](https://mlsanity.com/paper/2202.05638/) (2022)
- [Minimax Adaptive Online Nonparametric Regression over Besov Spaces](https://mlsanity.com/paper/2505.19741/) (2025)
- [A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHS](https://mlsanity.com/paper/2506.22631/) (2025)
- [Efficient Inference after Directionally Stable Adaptive Experiments](https://mlsanity.com/paper/2602.21478/) (2026)
- [Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression](https://mlsanity.com/paper/2306.08320/) (2023)
- [Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation](https://mlsanity.com/paper/2604.25021/) (2026)

## Abstract (arXiv)

We are interested in a framework of online learning with kernels for low-dimensional but large-scale and potentially adversarial datasets. We study the computational and theoretical performance of online variations of kernel Ridge regression. Despite its simplicity, the algorithm we study is the first to achieve the optimal regret for a wide range of kernels with a per-round complexity of order nα with α < 2. The algorithm we consider is based on approximating the kernel with the linear span of basis functions. Our contributions is two-fold: 1) For the Gaussian kernel, we propose to build the basis beforehand (independently of the data) through Taylor expansion. For d-dimensional inputs, we provide a (close to) optimal regret of order O((log n)d+1) with per-round time complexity and space complexity O((log n)2d). This makes the algorithm a suitable choice as soon as n gg ed which is likely to happen in a scenario with small dimensional and large-scale dataset; 2) For general kernels with low effective dimension, the basis functions are updated sequentially in a data-adaptive fashion by sampling Nystr"om points. In this case, our algorithm improves the computational trade-off known for online kernel regression.