Improved Regret Bounds for Online Kernel Selection under Bandit Feedback

Code

• github.com/junfli-tju/oks-bandit
  OfficialIn papernone★ 0

Abstract

In this paper, we improve the regret bound for online kernel selection under bandit feedback. Previous algorithm enjoys a O(( f^2_H_i+1)K^13T^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^23K^-13(^K_i=1L_T(f^_i))^23) expected bound where L_T(f^_i) is the cumulative losses of optimal hypothesis in H_i= _i: f_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(UKT^23T) 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(TK + f^2_H_i ,TR\) expected bound where R is the time budget. Finally, we empirically verify our algorithms on online regression and classification tasks.

Reproductions