mlsanityData to 14 Oct 2026

Simplex Random Features

arXiv 2301.13856 ↗First posted 31 Jan 2023stat.ML cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

We present Simplex Random Features (SimRFs), a new random feature (RF) mechanism for unbiased approximation of the softmax and Gaussian kernels by geometrical correlation of random projection vectors. We prove that SimRFs provide the smallest possible mean square error (MSE) on unbiased estimates of these kernels among the class of weight-independent geometrically-coupled positive random feature (PRF) mechanisms, substantially outperforming the previously most accurate Orthogonal Random Features at no observable extra cost. We present a more computationally expensive SimRFs+ variant, which we prove is asymptotically optimal in the broader family of weight-dependent geometrical coupling schemes (which permit correlations between random vector directions and norms). In extensive empirical studies, we show consistent gains provided by SimRFs in settings including pointwise kernel estimation, nonparametric classification and scalable Transformers.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 24 of its 54 references that are in the map. First posted on arXiv 31 Jan 2023.

Builds on

24 of 54 references.

References · 24

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  3. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  4. 2020Reformer: The Efficient Transformercited by 1,668
  5. 2020Rethinking Attention with Performerscited by 1,601
  6. 2021Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNetcited by 1,101
  7. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 700
  8. 2021Linear Transformers Are Secretly Fast Weight Programmerscited by 502
  9. 2020Efficient Content-Based Sparse Attention with Routing Transformerscited by 471
  10. 2020Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyondcited by 109
  11. 2016Orthogonal Random Featurescited by 91
  12. 2019Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizationscited by 76
12 more
  1. 2021Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encodingcited by 51
  2. 2017The Unreasonable Effectiveness of Structured Random Orthogonal Embeddingscited by 45
  3. 2014Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernelscited by 42
  4. 2021Relative Positional Encoding for Transformers with Linear Complexitycited by 37
  5. 2022Learning Model Predictive Controllers with Real-Time Attention for Real-World Navigationcited by 29
  6. 2022Chefs' Random Tables: Non-Trigonometric Random Featurescited by 21
  7. 2020Sub-Linear Memory: How to Make Performers SLiMcited by 18
  8. 2021On Learning the Transformer Kernelcited by 15
  9. 2020Demystifying Orthogonal Monte Carlo and Beyondcited by 8
  10. 2016Structured adaptive and random spinners for fast machine learning computationscited by 6
  11. 2021Translational Equivariance in Kernelizable Attentioncited by 5
  12. 2015On Binary Embedding using Circulant Matricescited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 4; 2025: 1; 2026: 1.

9 papers.

  1. 2023Towards Understanding How Transformers Learn In-context Through a Representation Learning Lenscited by 15
  2. 2023Quasi-Monte Carlo Graph Random Featurescited by 9
  3. 2024Linear Transformer Topological Masking with Graph Random Featurescited by 7
  4. 2023Repelling Random Walkscited by 6
  5. 2024Spectraformer: A Unified Random Feature Framework for Transformercited by 5
  6. 2024Variance-Reducing Couplings for Random Featurescited by 2
  7. 2024All Random Features Representations are Equivalentcited by 2
  8. 2025The kernel of graph indices for vector searchcited by 0
  9. 2026SWING: Unlocking Implicit Graph Representations for Graph Random Featurescited by 0