Advertisement
Published in:
2023 | OriginalPaper | Chapter
Improved Regret Bounds for Online Kernel Selection Under Bandit Feedback
Authors : Junfan Li, Shizhong Liao
Published in: Machine Learning and Knowledge Discovery in Databases
Publisher: Springer Nature Switzerland
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this paper, we improve the regret bound for online kernel selection under bandit feedback. Previous algorithm enjoys a \(O((\Vert f\Vert ^2_{\mathcal {H}_i}+1)K^{\frac{1}{3}}T^{\frac{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^{\frac{2}{3}}K^{-\frac{1}{3}}(\sum ^K_{i=1}L_T(f^*_i))^{\frac{2}{3}})\) expected bound where \(L_T(f^*_i)\) is the cumulative losses of optimal hypothesis in \(\mathbb {H}_{i} =\{f\in \mathcal {H}_i:\Vert f\Vert _{\mathcal {H}_i}\le 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\sqrt{KT}\ln ^{\frac{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(\sqrt{T\ln {K}} +\Vert f\Vert ^2_{\mathcal {H}_i}\max \{\sqrt{T},\frac{T}{\sqrt{\mathcal {R}}}\})\) expected bound where \(\mathcal {R}\) is the time budget. Finally, we empirically verify our algorithms on online regression and classification tasks.