Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning
This work addresses the problem of efficient online learning in reproducing kernel Hilbert spaces for machine learning practitioners, offering an incremental improvement over prior multi-kernel algorithms.
The paper tackles online multi-kernel learning for least squares regression by introducing VAW^2, a two-level algorithm using random Fourier features and the Vovk-Azoury-Warmuth method, which achieves a regret bound of O(T^{1/2} ln T) and demonstrates superior performance on benchmark datasets compared to existing methods like Raker and OMKL-GF.
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}\ln 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.