A Hierarchical Vovk–Azoury–Warmuth Forecaster with Discounting for Online Regression in RKHS

We study the problem of online regression with the unconstrained quadratic loss against a time-varying sequence of functions from a Reproducing Kernel Hilbert Space (RKHS). Recently, Jacobsen and Cutkosky (2024) introduced a discounted Vovk–Azoury–Warmuth (DVAW) forecaster that achieves optimal dynamic regret in the finite-dimensional case. In this work, we lift their approach to the non-parametric domain by synthesizing the DVAW framework with a random feature approximation. We propose a fully adaptive, hierarchical algorithm, which we call H-VAW-D (Hierarchical Vovk–Azoury–Warmuth with Discounting), that learns both the discount factor and the number of random features. We prove that this algorithm, which has a per-iteration computational complexity of $$O(T\ln T)$$ , achieves an expected dynamic regret of $$O(T^{2/3}P_{T}^{1/3}+\sqrt{T}\ln T)$$ , where $$P_{T}$$ is the functional path length of a comparator sequence.