# Online nonparametric regression with Sobolev kernels

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 6 Feb 2021.

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

- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Optimal Rates For Regularization Of Statistical Inverse Learning Problems](https://mlsanity.com/paper/1604.04054/) (2016)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [A Chaining Algorithm for Online Nonparametric Regression](https://mlsanity.com/paper/1502.07697/) (2015)
- [Uniform regret bounds over Rd for the sequential linear regression problem with the square loss](https://mlsanity.com/paper/1805.11386/) (2018)
- [Efficient online learning with kernels for adversarial large scale problems](https://mlsanity.com/paper/1902.09917/) (2019)
- [Online Improper Learning with an Approximation Oracle](https://mlsanity.com/paper/1804.07837/) (2018)
- [Interpolation and Learning with Scale Dependent Kernels](https://mlsanity.com/paper/2006.09984/) (2020)

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

- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networks](https://mlsanity.com/paper/2212.13848/) (2022)
- [Structured Prediction in Online Learning](https://mlsanity.com/paper/2406.12366/) (2024)
- [Minimax Adaptive Online Nonparametric Regression over Besov Spaces](https://mlsanity.com/paper/2505.19741/) (2025)
- [Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation](https://mlsanity.com/paper/2604.25021/) (2026)

## Abstract (arXiv)

In this work we investigate the variation of the online kernelized ridge regression algorithm in the setting of d-dimensional adversarial nonparametric regression. We derive the regret upper bounds on the classes of Sobolev spaces Wpβ(X), p≥ 2, β>fracdp. The upper bounds are supported by the minimax regret analysis, which reveals that in the cases β> fracd2 or p=∞ these rates are (essentially) optimal. Finally, we compare the performance of the kernelized ridge regression forecaster to the known non-parametric forecasters in terms of the regret rates and their computational complexity as well as to the excess risk rates in the setting of statistical (i.i.d.) nonparametric regression.