Sparse Learning of Parsimonious Reproducing Kernel Hilbert Space Models

Abstract

Reproducing kernel ilbert spaces (RKHSs) have been at the core of successful non-parametric tools in signal processing, statistics, and machine learning. Despite their success, the computational complexity of these models often hinders their use in practice. Indeed, fitting RKHS models typically relies on representer theorems to express the solution space as a combination of kernels evaluated at the training samples. Thus, the computational cost of evaluating these models is proportional to the number of training samples, which in many applications is prohibitively high. This issue is often addressed by sparsifying the coefficients of the kernel expansion, despite the fact that classical representer theorems no longer hold in the presence of sparsity penalties. In this work, we propose to directly tackle sparse learning over RKHSs by posing it as a functional problem. In other words, by formulating the RKHS model as a sparse, continuous combination of atoms from an overparametrized, continuous dictionary containing the value of the kernel evaluated at every point of the function domain. We show that despite the infinite dimensionality and non-convexity of the underlying optimization problem, these models can be fit exactly and efficiently using duality. We illustrate the performance of this technique in numerical experiments.