2021/02/06 by Oleksandr Zadorozhnyi, Pierre Gaillard, Zadorozhnyi, Oleksandr +4 · 1 citation
Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2102.03594
openalex publication_date 2021/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, β>(d)/(p). The upper bounds are supported by the minimax regret analysis, which reveals that in the cases β> (d)/(2) 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.