# All Random Features Representations are Equivalent

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 11 references that are in the map.
- First posted on arXiv 27 Jun 2024.

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

- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [On Data-Dependent Random Features for Improved Generalization in Supervised Learning](https://mlsanity.com/paper/1712.07102/) (2017)
- [FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Features](https://mlsanity.com/paper/2302.00787/) (2023)

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

- [The kernel of graph indices for vector search](https://mlsanity.com/paper/2506.20584/) (2025)
- [Data-Aware Random Feature Kernel for Transformers](https://mlsanity.com/paper/2603.04127/) (2026)

## Abstract (arXiv)

Random features are a powerful technique for rewriting positive-definite kernels as linear products. They bring linear tools to bear in important nonlinear domains like KNNs and attention. Unfortunately, practical implementations require approximating an expectation, usually via sampling. This has led to the development of increasingly elaborate representations with ever lower sample error. We resolve this arms race by deriving an optimal sampling policy. Under this policy all random features representations have the same approximation error, which we show is the lowest possible. This means that we are free to choose whatever representation we please, provided we sample optimally.