# A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHS

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 27 Jun 2025.

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

- [Online Learning: A Comprehensive Survey](https://mlsanity.com/paper/1802.02871/) (2018)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Random Feature-based Online Multi-kernel Learning in Environments with Unknown Dynamics](https://mlsanity.com/paper/1712.09983/) (2017)
- [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 Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning](https://mlsanity.com/paper/2503.20087/) (2025)

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

- [Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation](https://mlsanity.com/paper/2604.25021/) (2026)

## Abstract (arXiv)

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(Tln T), achieves an expected dynamic regret of O(T2/3PT1/3 + √Tln T), where PT is the functional path length of a comparator sequence.