On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes
This work addresses foundational challenges in machine learning for researchers and practitioners using kernel methods, though it appears incremental as it builds on existing kernel theory with new structural insights.
The paper tackles the problem of understanding the expressive power of kernel methods and the feasibility of learning kernels efficiently, focusing on a broad class called Euclidean kernels that includes polynomial and radial basis functions. It proves limitations on expressivity and develops efficient algorithms for kernel learning over domains like the hypercube.
We study the expressive power of kernel methods and the algorithmic feasibility of multiple kernel learning for a special rich class of kernels. Specifically, we define \emph{Euclidean kernels}, a diverse class that includes most, if not all, families of kernels studied in literature such as polynomial kernels and radial basis functions. We then describe the geometric and spectral structure of this family of kernels over the hypercube (and to some extent for any compact domain). Our structural results allow us to prove meaningful limitations on the expressive power of the class as well as derive several efficient algorithms for learning kernels over different domains.