Generalization Guarantees for Sparse Kernel Approximation with Entropic Optimal Features

Abstract

Despite their success, kernel methods suffer from a massive computational cost in practice. In this paper, in lieu of commonly used kernel expansion with respect to $N$ inputs, we develop a novel optimal design maximizing the entropy among kernel features. This procedure results in a kernel expansion with respect to entropic optimal features (EOF), improving the data representation dramatically due to features dissimilarity. Under mild technical assumptions, our generalization bound shows that with only $O(N^{\frac{1}{4}})$ features (disregarding logarithmic factors), we can achieve the optimal statistical accuracy (i.e., $O(1/\sqrt{N})$). The salient feature of our design is its sparsity that significantly reduces the time and space cost. Our numerical experiments on benchmark datasets verify the superiority of EOF over the state-of-the-art in kernel approximation.

References in corpus (12)

• Generalization Properties of Learning with Random Features
• Orthogonal Random Features
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
• Bayesian Nonparametric Kernel-Learning
• Compact Nonlinear Maps and Circulant Extensions
• A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe
• Data-dependent compression of random features for large-scale kernel approximation
• Scalable Learning in Reproducing Kernel Krein Spaces
• BdryGP: a new Gaussian process model for incorporating boundary information
• Learning Bounds for Greedy Approximation with Explicit Feature Maps from Multiple Kernels
• Scalable Stochastic Kriging with Markovian Covariances

Cited by in corpus (1)

• High-Dimensional Simulation Optimization via Brownian Fields and Sparse Grids