A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHS
This work provides an incremental improvement for machine learning researchers by extending a finite-dimensional method to non-parametric online regression with adaptive parameter tuning.
The authors tackled online regression in RKHS by proposing a hierarchical algorithm that adaptively learns discount factors and random features, achieving an expected dynamic regret of O(T^{2/3}P_T^{1/3} + √T ln T) with per-iteration complexity O(T ln T).
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.