Papers › Improved Regret Bounds for Online Kernel Selection under Bandit Feedback
Improved Regret Bounds for Online Kernel Selection under Bandit Feedback
Junfan Li, Shizhong Liao
In this paper, we improve the regret bound for online kernel selection under bandit feedback. Previous algorithm enjoys a O((‖f‖²_(ℋᵢ)+1)K^(1/3)T^(2/3)) 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^(2/3)K^(-1/3)(∑ᴷᵢ₌₁L_T(f^∗ᵢ))^(2/3)) expected bound where L_T(f^∗ᵢ) is the cumulative losses of optimal hypothesis in ℍᵢ={f∈ℋᵢ:‖f‖_(ℋᵢ)≤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^(2/3)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(√(TlnK) +‖f‖²_(ℋᵢ)max{√(T),T/(√(ℛ))}) expected bound where ℛ is the time budget. Finally, we empirically verify our algorithms on online regression and classification tasks.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections