Online Kernel Selection Via Adversarial Multi-armed Bandit Models

Online kernel selection is an important component of online kernel methods,which can be classified into the filter,the wrapper and the embedder three categories.Online kernel selection must face the “exploration-exploitation” dilemma,where we explore new kernels to find the best one and exploit the kernel that showed the best performance in the past.Existing online kernel selection work ignored the “exploration-exploitation”dilemma.To address the problem,we propose an adversarial multi-armed bandit model for online kernel selection,and give the wrapper and the embedder of online kernel selection simultaneously.The proposed wrapper and embedder aim at balancing the“exploration-exploitation”.Giving a set of candidate kernels,we correspond each kernel to an arm in the adversarial bandit model.At each round of online kernel selection,we randomly choose kernels according to a probability distribution,and update the probability distribution via the exponentially weighted average method.In this way,an online kernel selection problem is reduced to an adversarial bandit problem.We further give two wrappers and an embedder:1.Online kernel selection wrappers via adversarial bandit mode.We propose awrapper in oblivious and non-oblivious adversary setting separately,and furtherdefine a new regret concept of online kernel selection.We prove that the wrap-per proposed in oblivious adversary setting enjoys a sub-linear expected regretbound,and the wrapper proposed in non-oblivious adversary setting enjoys asub-linear weak expected regret bound.2.An online kernel selection embedder via adversarial bandit mode.We proposean embedder in non-oblivious adversary setting,and prove that the proposedembedder enjoys a sub-linear expected regret bound.Experimental results on benchmark datasets demonstrate the effectiveness of the proposed wrappers and embedder.