| Online kernel selection determines the reproducing kernel Hilbert space where the hypothesis sequence belongs to,which is critical to the theory and application of online kernel methods.Existing online kernel methods typically choose the kernel functions beforehand using some prior knowledge or offline kernel selection approaches,which require multiple passes over the whole data,have high computational complexities,and do not offer any theoretical guarantee.To address these issues,we propose the randomized sketching theory and approach to online kernel selection,which construct and maintain hypothesis space sketches incrementally,develop a sound online kernel selection theory,give theoretically guaranteed online kernel selection criteria and computationally efficient online kernel selection algorithms.The details are as follows:1.The formulation of randomized sketching.We formulate two types of hypothesis space sketches using randomized sketching.We first propose a local dynamic sketching approach,which maintains a basis function vector of a hypothesis space sketch using dynamic maintenances.Then we present a novel incremental randomized sketching approach.The proposed incremental randomized sketching approach constructs incremental randomized sketches for the kernel matrix approximation and a time-varying explicit feature mapping for online kernel learning,enjoying the incremental maintenance property and approximation property.2.The establishment of online kernel selection theory.We first define a surrogate hypothesis space and bound the norms.Then,for a discrete kernel set,we analyze the upper bounds of regrets and the consistency of the online kernel selection with a single hypothesis sequence or multiple hypothesis sequences.Finally,we divide online kernel selection in a continuous kernel space into two categories according to the order of selection and training at each round,and give the conditions that guarantee the optimal regret bounds and the consistency of the online kernel selection in a continuous kernel space.3.The formulation of online kernel selection criteria and algorithms.Based on the online kernel selection theory,we present online kernel selection criteria both for discrete kernel sets and for continuous kernel spaces.We further design efficient online kernel selection algorithms and analyze the computational complexities of the proposed algorithms.In summary,we construct the hypothesis space sketches incrementally using the randomized sketching,in which we study the consistency and unbiasedness of online kernel selection and demonstrate the optimal regret bounds of online kernel selection,for establishing a sound online kernel selection theory.We further propose theoretically guaranteed online kernel selection criteria and design online kernel selection algorithms with constant per-round computational complexities,which lays a foundation for the theory and application of online model selection and online learning. |
