Abstract: 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.