# Graph-Aided Online Multi-Kernel Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 42 references that are in the map.
- First posted on arXiv 9 Feb 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Random Feature-based Online Multi-kernel Learning in Environments with Unknown Dynamics](https://mlsanity.com/paper/1712.09983/) (2017)
- [Online Learning with Feedback Graphs Without the Graphs](https://mlsanity.com/paper/1605.07018/) (2016)
- [Online Distributed Learning Over Networks in RKH Spaces Using Random Fourier Features](https://mlsanity.com/paper/1703.08131/) (2017)
- [Generalization Guarantees for Sparse Kernel Approximation with Entropic Optimal Features](https://mlsanity.com/paper/2002.04195/) (2020)
- [Learning Bounds for Greedy Approximation with Explicit Feature Maps from Multiple Kernels](https://mlsanity.com/paper/1810.03817/) (2018)

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

- [Budgeted Online Model Selection and Fine-Tuning via Federated Learning](https://mlsanity.com/paper/2401.10478/) (2024)
- [Random feature-based double Vovk-Azoury-Warmuth algorithm for online multi-kernel learning](https://mlsanity.com/paper/2503.20087/) (2025)

## Abstract (arXiv)

Multi-kernel learning (MKL) has been widely used in function approximation tasks. The key problem of MKL is to combine kernels in a prescribed dictionary. Inclusion of irrelevant kernels in the dictionary can deteriorate accuracy of MKL, and increase the computational complexity. To improve the accuracy of function approximation and reduce the computational complexity, the present paper studies data-driven selection of kernels from the dictionary that provide satisfactory function approximations. Specifically, based on the similarities among kernels, the novel framework constructs and refines a graph to assist choosing a subset of kernels. In addition, random feature approximation is utilized to enable online implementation for sequentially obtained data. Theoretical analysis shows that our proposed algorithms enjoy tighter sub-linear regret bound compared with state-of-art graph-based online MKL alternatives. Experiments on a number of real datasets also showcase the advantages of our novel graph-aided framework.