# Variance-Reducing Couplings for Random Features

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 73 references that are in the map.
- First posted on arXiv 26 May 2024.

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

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Learning Mesh-Based Simulation with Graph Networks](https://mlsanity.com/paper/2010.03409/) (2020)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Mat'ern Gaussian Processes on Graphs](https://mlsanity.com/paper/2010.15538/) (2020)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [Quadrature-based features for kernel approximation](https://mlsanity.com/paper/1802.03832/) (2018)
- [Gaussian Processes on Graphs via Spectral Kernel Learning](https://mlsanity.com/paper/2006.07361/) (2020)
- [Gaussian Quadrature for Kernel Features](https://mlsanity.com/paper/1709.02605/) (2017)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [Tanimoto Random Features for Scalable Molecular Machine Learning](https://mlsanity.com/paper/2306.14809/) (2023)
- [General Graph Random Features](https://mlsanity.com/paper/2310.04859/) (2023)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Structured adaptive and random spinners for fast machine learning computations](https://mlsanity.com/paper/1610.06209/) (2016)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)
- [Leveraging History for Faster Sampling of Online Social Networks](https://mlsanity.com/paper/1505.00079/) (2015)

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

- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)

## Abstract (arXiv)

Random features (RFs) are a popular technique to scale up kernel methods in machine learning, replacing exact kernel evaluations with stochastic Monte Carlo estimates. They underpin models as diverse as efficient transformers (by approximating attention) to sparse spectrum Gaussian processes (by approximating the covariance function). Efficiency can be further improved by speeding up the convergence of these estimates: a variance reduction problem. We tackle this through the unifying lens of optimal transport, finding couplings to improve RFs defined on both Euclidean and discrete input spaces. They enjoy theoretical guarantees and sometimes provide strong downstream gains, including for scalable approximate inference on graphs. We reach surprising conclusions about the benefits and limitations of variance reduction as a paradigm, showing that other properties of the coupling should be optimised for attention estimation in efficient transformers.