Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation

Dmitry B. Rokhlin; Georgiy A. Karapetyants

cs.LGApr 27, 2026

Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation

Authors: Dmitry B. Rokhlin, Georgiy A. Karapetyants

Organizations: Institute of Mathematics, Mechanics and Computer Sciences of the Southern Federal University

Abstract

We study online regression with the square loss in a reproducing kernel Hilbert space under a dynamic regret criterion. The learner is compared with a time-varying comparator sequence, and the bounds depend on its path length in the RKHS norm. The proposed method transfers the finite-dimensional discounted Vovk--Azoury--Warmuth approach of Jacobsen & Cutkosky (2024) to the RKHS setting by means of finite-dimensional subspace approximations. For a fixed subspace, we run a VAW-based ensemble of discounted VAW forecasters over a geometric grid of discount factors. The additional approximation error is controlled by the uniform projection error of kernel sections. We then introduce a general orthogonal truncation method: starting from a feature expansion of the kernel, we construct the associated RKHS by introducing an inner product that makes the feature functions orthonormal, and then use the spans of the first basis functions as finite-dimensional approximation spaces. The resulting subspace reduction is applied to several approximation schemes. Explicit feature expansions yield fast-regime bounds for Gaussian and analytic dot-product kernels. Mercer truncations provide a spectral approximation method and lead to dynamic regret bounds in fast and slow regimes, depending on the eigenvalue decay. Finally, we study subspaces spanned by kernel sections and apply this construction to Matérn kernels.

Explore similar work

Jun 19, 2026stat.ML

Subsampling for supervised learning in reproducing kernel Hilbert spaces

In the era of big data, subsampling became a common practice in statistical learning. By selecting a subgroup of individuals based on which the learner is trained, subsampling aims at reducing the computational cost and time of the estimation step, and ideally leads to a decrease of its energy consumption and carbon footprint. This work focuses on a nonparametric setting, in which the hypotheses set lies in a reproducing kernel Hilbert space, and the estimator is a minimizer of an empirical risk reweighted à la Horvitz-Thompson. By studying the asymptotic properties of this estimator, we reveal an optimal subsampling scheme (regarding the trace of the covariance operator) and show that it can be used via plug-in. A numerical study on synthetic and real-world datasets shows the practicability and the benefit of the proposed approach.

Eyal Vayness, Maxime Sangnier

Kernel Hilbert Spaces Subsampling Nonparametric Covariance Estimation Supervised Learning

Ask PDF

May 26, 2026cs.LG

Near-Optimal Regret in Adversarial Kernel Bandits

We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element of a reproducing kernel Hilbert space (RKHS). We propose an exponential-weights algorithm built on a regularized importance-weighted loss estimator, together with an explicit correction term that cancels the bias introduced by the regularization. Our main result bounds the regret by

\widetilde{O}\big(\sqrt{T\, d_*(λ)\,\log|{X}|}\big)

, where

d_*(λ)

is a widely-adopted notion of effective dimension that captures the complexity of the kernel. Up to logarithmic factors, this matches the known rate achieved in the related stochastic kernel bandit problem. A notable application is the Matérn

(ν,d)

kernel with smoothness parameter

ν

\mathbb{R}^d

, for which our bound specializes to

\widetilde{O}\big(T^{(ν+d)/(2ν+d)}\big)

, improving over the best-known prior rate of Chatterji et al. [2019] while simultaneously removing the rank-one adversary assumption required by their analysis. Moreover, this rate is the same as the known optimal rate for stochastic kernel bandits, and also matches a lower bound from concurrent work up to a

\log T

factor.

Yu-Jie Zhang, Hao Qiu, Jonathan Scarlett +1

Kernel Hilbert Spaces Regret Bandits Loss Function Prior Knowledge

Ask PDF

Jul 31, 2026stat.ML

Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs

We study expected improvement (EI) for minimizing a deterministic function

f

in the RKHS

\mathcal H_k

of a continuous positive-semidefinite kernel

k

on a nonempty compact set

\mathcal X\subset\mathbb R^d

. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance

σ^2k

σ>0

. A weak-EI policy queries a point whose EI is at least a fixed positive fraction of its maximum. We introduce a notion of sequential separation radius relating ranked selected-point innovation norms to Kolmogorov widths, drawing on greedy approximation. Standard power-function estimates from scattered-data approximation and a finite-budget regret argument yield the rates. After

N

post-initial queries, every weak-EI policy has simple regret

O(N^{-ν/d})

for isotropic Matérn kernels of smoothness

ν>0

and

O(\exp[-c_1\min\{N,N^{1/d}\log(eN)\}])

for the isotropic squared-exponential kernel, with

c_1>0

. For

d=1

, the sharper bound

O(\exp[-c_2N\log(eN)])

holds for exact EI, with

c_2>0

. These bounds are uniform over each fixed RKHS ball. If

\mathcal X

has nonempty interior and

B>0

, the exact EI policy is minimax-rate optimal over the RKHS ball of radius

B

for Matérn kernels, even among randomized strategies whose final recommendation need not be a query point. For the squared-exponential kernel, it is minimax-rate optimal up to constants in the exponent among deterministic methods whose final recommendation may be any point of

\mathcal X

Emmanuel Vazquez, Sébastien Petit

Kernel Hilbert Spaces Linear Regret Minimax Regret Objective Functions Improvement

Ask PDF