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

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.