Worst-case regret analysis of computationally budgeted online kernel selection

摘要

We study the problem of online kernel selection under computational constraints, where the memory or time of kernel selection and online prediction procedures is restricted to a fixed budget. In this paper, we analyze the worst-case lower bounds on the regret of online kernel selection algorithm with a subset of the observed examples, and design algorithms enjoying corresponding upper bounds. We also identify the condition under which online kernel selection with time constraints is different from that with memory constraints. To design algorithms, we reduce the problems to two sequential decision problems, that is, the problem of prediction with expert advice and the multi-armed bandit problem with an additional observation. Our algorithms invent some new techniques, such as memory sharing, hypothesis space discretization and decoupled exploration-exploitation scheme. Numerical experiments on online regression and classification are conducted to verify our theoretical results.