2023/03/09 by Junfan Li, Li, Junfan, Shizhong Liao +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2303.05018
openalex publication_date 2023/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we improve the regret bound for online kernel selection under bandit feedback. Previous algorithm enjoys a O((\Vert f\Vert2Hi+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)(∑Ki=1LT(f^∗i))(2)/(3)) expected bound where LT(f^∗i) is the cumulative losses of optimal hypothesis in ℍi=\f\inHi:\Vert f\VertHi≤ 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 +\Vert f\Vert2Himax\√(T),(T)/(√(R))\) expected bound where R is the time budget. Finally, we empirically verify our algorithms on online regression and classification tasks.