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 (( (cid:107) f (cid:107) 2 H i + 1) K 13 T 23 ) 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 23 K − 13 ( (cid:80) Ki =1 L T ( f ∗ i )) 23 ) expected bound where L T ( f ∗ i ) is the cumulative losses of optimal hy- pothesis in H i = { f ∈ H i : (cid:107) f (cid:107) H i ≤ 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 √ KT ln 23 T ) 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 ( √ T ln K + (cid:107) f (cid:107) 2 H i max {√ T, T √R } ) expected bound where R is the time budget. Finally, we empirically verify our algorithms on online regression and classiﬁcation tasks.