# Generalization Guarantees for Sparse Kernel Approximation with Entropic Optimal Features

arXiv: https://arxiv.org/abs/2002.04195 · HTML: https://mlsanity.com/paper/2002.04195/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2020.

## Built on by (most cited first, 5 of 5)

- [Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process Regression with Mat'ern Correlations](https://mlsanity.com/paper/2203.03116/) (2022)
- [A Sparse Expansion For Deep Gaussian Processes](https://mlsanity.com/paper/2112.05888/) (2021)
- [Graph-Aided Online Multi-Kernel Learning](https://mlsanity.com/paper/2102.04690/) (2021)
- [High-Dimensional Simulation Optimization via Brownian Fields and Sparse Grids](https://mlsanity.com/paper/2107.08595/) (2021)
- [SIKA-GP: Accelerating Gaussian Process Inference with Sparse Inducing Kernel Approximations for Bayesian Deep Learning](https://mlsanity.com/paper/2605.26509/) (2026)

## Abstract (arXiv)

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^frac14) features (disregarding logarithmic factors), we can achieve the optimal statistical accuracy (i.e., O(1/√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.