Improved Regret Bounds for Online Kernel Selection under Bandit Feedback

In this paper, we improve the regret bound for online kernel selection under bandit feedback. Previous algorithm enjoys a O((Vert fVert2Hi+1)K^frac13T^frac23) expected bound for Lipschitz loss functions. We prove two types of regret bounds improving the previous bound. For smooth loss functions, we propose an algorithm with a O(U^frac23K^-frac13(sumKi=1LT(f^asti))^frac23) expected bound where LT(f^asti) is the cumulative losses of optimal hypothesis in mathbbHi=f∈Hi:Vert fVertHi≤ U. The data-dependent bound keeps the previous worst-case bound and is smaller if most of candidate kernels match well with the data. For Lipschitz loss functions, we propose an algorithm with a O(U√KTln^frac23T) expected bound asymptotically improving the previous bound. We apply the two algorithms to online kernel selection with time constraint and prove new regret bounds matching or improving the previous O(√TlnK +Vert fVert2Himax√T,fracT√R) expected bound where R is the time budget. Finally, we empirically verify our algorithms on online regression and classification tasks.