On the Expressive Power of Kernel Methods and the Efficiency of Kernel\n Learning by Association Schemes

2019/02/13 by Pravesh K. Kothari, Kothari, Pravesh K., Roi Livni +1
Computer Science · Engineering · #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1902.04782

openalex publication_date 2019/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the expressive power of kernel methods and the algorithmic\nfeasibility of multiple kernel learning for a special rich class of kernels.\n Specifically, we define \Euclidean kernels, a diverse class that\nincludes most, if not all, families of kernels studied in literature such as\npolynomial kernels and radial basis functions. We then describe the geometric\nand spectral structure of this family of kernels over the hypercube (and to\nsome extent for any compact domain). Our structural results allow us to prove\nmeaningful limitations on the expressive power of the class as well as derive\nseveral efficient algorithms for learning kernels over different domains.\n

Citations

• Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning

Related

• A Geometric Algorithm for Scalable Multiple Kernel Learning
• Learning the Kernel for Classification and Regression
• Scalable Learning in Reproducing Kernel Krein Spaces
• New Generalization Bounds for Learning Kernels
• Dual-to-kernel learning with ideals