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

Code

• github.com/O-Gurt/VAW2
  Officialnone★ 0

Abstract

We introduce a novel multi-kernel learning algorithm, VAW^2, for online least squares regression in reproducing kernel Hilbert spaces (RKHS). VAW^2 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(T^1/2 T) in expectation with respect to artificial randomness, when the number of random features scales as T^1/2. Empirical results on some benchmark datasets demonstrate that VAW^2 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.

Reproductions