Regret Bounds for Online Kernel Selection in Continuous Kernel Space

Authors

  • Xiao Zhang Gaoling School of Artificial Intelligence, Renmin University of China Beijing Key Laboratory of Big Data Management and Analysis Methods
  • Shizhong Liao College of Intelligence and Computing, Tianjin University
  • Jun Xu Gaoling School of Artificial Intelligence, Renmin University of China Beijing Key Laboratory of Big Data Management and Analysis Methods
  • Ji-Rong Wen Gaoling School of Artificial Intelligence, Renmin University of China Beijing Key Laboratory of Big Data Management and Analysis Methods

Keywords:

Online Learning & Bandits

Abstract

Regret bounds of online kernel selection in a finite kernel set have been well studied, having at least an order O( √ NT) of magnitude after T rounds, where N is the number of candidate kernels. But it is still an unsolved problem to achieve sublinear regret bounds of online kernel selection in a continuous kernel space under different learning frameworks. In this paper, to represent different learning frameworks of online kernel selection, we divide online kernel selection approaches in a continuous kernel space into two categories according to the order of selection and training at each round. Then we construct a surrogate hypothesis space that contains all the candidate kernels with bounded norms and inner products, representing the continuously varying hypothesis space. Finally, we decompose the regrets of the proposed online kernel selection categories into different types of instantaneous regrets in the surrogate hypothesis space, and derive optimal regret bounds of order O( √ T) of magnitude under mild assumptions, independent of the cardinality of the continuous kernel space. Empirical studies verified the correctness of the theoretical regret analyses.

Downloads

Published

2021-05-18

How to Cite

Zhang, X., Liao, S., Xu, J., & Wen, J.-R. (2021). Regret Bounds for Online Kernel Selection in Continuous Kernel Space. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12), 10931-10938. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17305

Issue

Section

AAAI Technical Track on Machine Learning V