# Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 24 references that are in the map.
- First posted on arXiv 25 Mar 2025.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Online Learning: A Comprehensive Survey](https://mlsanity.com/paper/1802.02871/) (2018)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Optimal learning with Bernstein Online Aggregation](https://mlsanity.com/paper/1404.1356/) (2014)
- [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)
- [Graph-Aided Online Multi-Kernel Learning](https://mlsanity.com/paper/2102.04690/) (2021)

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

- [A hierarchical Vovk-Azoury-Warmuth forecaster with discounting for online regression in RKHS](https://mlsanity.com/paper/2506.22631/) (2025)

## Abstract (arXiv)

We introduce a novel multi-kernel learning algorithm, VAW2, for online least squares regression in reproducing kernel Hilbert spaces (RKHS). VAW2 leverages random Fourier feature-based functional approximation and the Vovk-Azoury-Warmuth (VAW) method in a two-level procedure: VAW is used to construct expert strategies from random features generated for each kernel at the first level, and then again to combine their predictions at the second level. A theoretical analysis yields a regret bound of O(T1/2ln T) in expectation with respect to artificial randomness, when the number of random features scales as T1/2. Empirical results on some benchmark datasets demonstrate that VAW2 achieves superior performance compared to the existing online multi-kernel learning algorithms: Raker and OMKL-GF, and to other theoretically grounded method methods involving convex combination of expert predictions at the second level.