  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.
