  Online learning with multiple kernels has gained increasing interests in
recent years and found many applications. For classification tasks, Online
Multiple Kernel Classification (OMKC), which learns a kernel based classifier
by seeking the optimal linear combination of a pool of single kernel
classifiers in an online fashion, achieves superior accuracy and enjoys great
flexibility compared with traditional single-kernel classifiers. Despite being
studied extensively, existing OMKC algorithms suffer from high computational
cost due to their unbounded numbers of support vectors. To overcome this
drawback, we present a novel framework of Budget Online Multiple Kernel
Learning (BOMKL) and propose a new Sparse Passive Aggressive learning to
perform effective budget online learning. Specifically, we adopt a simple yet
effective Bernoulli sampling to decide if an incoming instance should be added
to the current set of support vectors. By limiting the number of support
vectors, our method can significantly accelerate OMKC while maintaining
satisfactory accuracy that is comparable to that of the existing OMKC
algorithms. We theoretically prove that our new method achieves an optimal
regret bound in expectation, and empirically found that the proposed algorithm
outperforms various OMKC algorithms and can easily scale up to large-scale
datasets.
