Learnability in Online Kernel Selection with Memory Constraint via Data-Dependent Regret Analysis  

作　　者：Jun-Fan Li Shi-Zhong Liao 李峻樊;廖士中

机构地区：[1]College of Intelligence and Computing,Tianjin University,Tianjin 300350,China

出　　处：《Journal of Computer Science & Technology》2025年第1期73-84,共12页计算机科学技术学报(英文版)

基　　金：supported by the National Natural Science Foundation of China under Grant No.62076181.

摘　　要：Online kernel selection is a fundamental problem of online kernel methods.In this paper,we study online kernel selection with memory constraint in which the memory of kernel selection and online prediction procedures is limited to a fixed budget.An essential question is what is the intrinsic relationship among online learnability,memory constraint,and data complexity.To answer the question,it is necessary to show the trade-offs between regret and memory budget.Previous work gives a worst-case lower bound depending on the data size,and shows learning is impossible within a small memory budget.In contrast,we present distinct results by offering data-dependent upper bounds that rely on two data complexities:kernel alignment and the cumulative losses of competitive hypothesis.We propose an algorithmic framework giving data-dependent upper bounds for two types of loss functions.For the hinge loss function,our algorithm achieves an expected upper bound depending on kernel alignment.For the smooth loss functions,our algorithm achieves a high-probability upper bound depending on the cumulative losses of competitive hypothesis.We also prove a matching lower bound for smooth loss functions.Our results show that if the two data complexities are sub-linear,then learning is possible within a small memory budget.Our algorithmic framework depends on a new buffer maintaining framework and a reduction from online kernel selection to prediction with expert advice.Finally,we empirically verify the prediction performance of our algorithms on benchmark datasets.

关 键 词：model selection online kernel learning memory constraint LEARNABILITY 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]