# Improved Random Features for Dot Product Kernels

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 21 Jan 2022.

## Builds on (most cited first, 21 of 21)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Multimodal Compact Bilinear Pooling for Visual Question Answering and Visual Grounding](https://mlsanity.com/paper/1606.01847/) (2016)
- [Bilinear CNNs for Fine-grained Visual Recognition](https://mlsanity.com/paper/1504.07889/) (2015)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Compact Bilinear Pooling](https://mlsanity.com/paper/1511.06062/) (2015)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Variational Fourier features for Gaussian processes](https://mlsanity.com/paper/1611.06740/) (2016)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Dirichlet-based Gaussian Processes for Large-scale Calibrated Classification](https://mlsanity.com/paper/1805.10915/) (2018)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Deep Fried Convnets](https://mlsanity.com/paper/1412.7149/) (2014)
- [Compact Random Feature Maps](https://mlsanity.com/paper/1312.4626/) (2013)
- [Polynomial Networks and Factorization Machines: New Insights and Efficient Training Algorithms](https://mlsanity.com/paper/1607.08810/) (2016)
- [The Kernel Interaction Trick: Fast Bayesian Discovery of Pairwise Interactions in High Dimensions](https://mlsanity.com/paper/1905.06501/) (2019)
- [Complex-Valued Gaussian Processes for Regression](https://mlsanity.com/paper/1511.05710/) (2015)

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

- [Tanimoto Random Features for Scalable Molecular Machine Learning](https://mlsanity.com/paper/2306.14809/) (2023)
- [Scalable Neural Network Kernels](https://mlsanity.com/paper/2310.13225/) (2023)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [Local Random Feature Approximations of the Gaussian Kernel](https://mlsanity.com/paper/2204.05667/) (2022)
- [Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel](https://mlsanity.com/paper/2202.02031/) (2022)
- [EUGens: Efficient, Unified, and General Dense Layers](https://mlsanity.com/paper/2601.22563/) (2026)
- [Feature maps for the Laplacian kernel and its generalizations](https://mlsanity.com/paper/2502.15575/) (2025)
- [Residual-Mass Accounting for Partial-KV Decoding](https://mlsanity.com/paper/2604.05438/) (2026)
- [EUGens: Efficient, Unified, and General Dense Layers](https://mlsanity.com/paper/2410.09771/) (2024)
- [Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization](https://mlsanity.com/paper/2606.11255/) (2026)
- [Improving TensorSketch Using Complex Random Variables](https://mlsanity.com/paper/2608.10523/) (2026)
- [Rationally Linearized MLPs](https://mlsanity.com/paper/2610.13568/) (2026)

## Abstract (arXiv)

Dot product kernels, such as polynomial and exponential (softmax) kernels, are among the most widely used kernels in machine learning, as they enable modeling the interactions between input features, which is crucial in applications like computer vision, natural language processing, and recommender systems. We make several novel contributions for improving the efficiency of random feature approximations for dot product kernels, to make these kernels more useful in large scale learning. First, we present a generalization of existing random feature approximations for polynomial kernels, such as Rademacher and Gaussian sketches and TensorSRHT, using complex-valued random features. We show empirically that the use of complex features can significantly reduce the variances of these approximations. Second, we provide a theoretical analysis for understanding the factors affecting the efficiency of various random feature approximations, by deriving closed-form expressions for their variances. These variance formulas elucidate conditions under which certain approximations (e.g., TensorSRHT) achieve lower variances than others (e.g., Rademacher sketches), and conditions under which the use of complex features leads to lower variances than real features. Third, by using these variance formulas, which can be evaluated in practice, we develop a data-driven optimization approach to improve random feature approximations for general dot product kernels, which is also applicable to the Gaussian kernel. We describe the improvements brought by these contributions with extensive experiments on a variety of tasks and datasets.