Worst-case Regret Analysis of Computationally Budgeted Online Kernel Selection

Junfan Li (Tianjin University); Shizhong Liao (Tianjin University)*


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 attainable by any online kernel selection algorithm that operates on a subset of the observed examples, and develop algorithms achieving matching 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, a problem of prediction with expert advice and a multi-armed bandit problem with an additional observation. Our algorithms contain some new techniques, such as memory sharing, hypothesis space discretization and decoupled exploration-exploitation scheme. Numerical experiments are conducted to verify our theoretical results.