mlsanityData to 14 Oct 2026

Chefs' Random Tables: Non-Trigonometric Random Features

arXiv 2205.15317 ↗First posted 30 May 2022cs.LG cs.AIcited by 21

Not on the map. Why?

Abstract (arXiv)

We introduce chefs' random tables (CRTs), a new class of non-trigonometric random features (RFs) to approximate Gaussian and softmax kernels. CRTs are an alternative to standard random kitchen sink (RKS) methods, which inherently rely on the trigonometric maps. We present variants of CRTs where RFs are positive, a key requirement for applications in recent low-rank Transformers. Further variance reduction is possible by leveraging statistics which are simple to compute. One instantiation of CRTs, the optimal positive random features (OPRFs), is to our knowledge the first RF method for unbiased softmax kernel estimation with positive and bounded RFs, resulting in exponentially small tails and much lower variance than its counterparts. As we show, orthogonal random features applied in OPRFs provide additional variance reduction for any dimensionality d (not only asymptotically for sufficiently large d, as for RKS). We test CRTs on many tasks ranging from non-parametric classification to training Transformers for text, speech and image data, obtaining new state-of-the-art results for low-rank text Transformers, while providing linear space and time complexity.

Key facts. Cited by 21 papers in the map (data through 14 Oct 2026). Builds on 34 of its 73 references that are in the map. First posted on arXiv 30 May 2022.

Builds on

34 of 73 references.

References · 34

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  4. 2021Masked Autoencoders Are Scalable Vision Learnerscited by 7,403
  5. 2018GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understandingcited by 4,899
  6. 2020Extracting Training Data from Large Language Modelscited by 2,189
  7. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  8. 2020Conformer: Convolution-augmented Transformer for Speech Recognitioncited by 1,863
  9. 2020Big Bird: Transformers for Longer Sequencescited by 1,684
  10. 2020Reformer: The Efficient Transformercited by 1,668
  11. 2020Rethinking Attention with Performerscited by 1,601
  12. 2019Generating Long Sequences with Sparse Transformerscited by 1,546
22 more
  1. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  2. 2019Energy and Policy Considerations for Deep Learning in NLPcited by 1,254
  3. 2015Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Bookscited by 1,043
  4. 2021Ethical and social risks of harm from Language Modelscited by 966
  5. 2018Image Transformercited by 772
  6. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 700
  7. 2020Sparse Sinkhorn Attentioncited by 251
  8. 2020Synthesizer: Rethinking Self-Attention in Transformer Modelscited by 205
  9. 2015On the Error of Random Fourier Featurescited by 76
  10. 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
  11. 2020Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformerscited by 49
  12. 2017The Unreasonable Effectiveness of Structured Random Orthogonal Embeddingscited by 45
  13. 2015Optimal Rates for Random Fourier Featurescited by 38
  14. 2021Random feature neural networks learn Black-Scholes type PDEs without curse of dimensionalitycited by 34
  15. 2018But How Does It Work in Theory? Linear SVM with Random Featurescited by 28
  16. 2021Hybrid Random Featurescited by 25
  17. 2016Operator-Valued Bochner Theorem, Fourier Feature Maps for Operator-Valued Kernels, and Vector-Valued Learningcited by 15
  18. 2021On Learning the Transformer Kernelcited by 15
  19. 2021Nonparametric adaptive control and prediction: theory and randomized algorithmscited by 8
  20. 2014Fast Function to Function Regressioncited by 7
  21. 2019Deep Kernel Learning via Random Fourier Featurescited by 7
  22. 2021Random Features for the Neural Tangent Kernelcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 10; 2024: 6; 2025: 0; 2026: 4.

21 papers.

Sort:

  1. 2023Efficient Attention via Control Variatescited by 23
  2. 2023SARA-RT: Scaling up Robotics Transformers with Self-Adaptive Robust Attentioncited by 20
  3. 2023Taming graph kernels with random featurescited by 17
  4. 2023Learning a Fourier Transform for Linear Relative Positional Encodings in Transformerscited by 10
  5. 2023Simplex Random Featurescited by 9
  6. 2023Mnemosyne: Learning to Train Transformers with Transformerscited by 9
  7. 2023Scalable Neural Network Kernelscited by 9
  8. 2024Spectraformer: A Unified Random Feature Framework for Transformercited by 5
  9. 2023FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Featurescited by 4
  10. 2023Hardness of Low Rank Approximation of Entrywise Transformed Matrix Productscited by 3
  11. 2024SeTformer is What You Need for Vision and Languagecited by 3
  12. 2024Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphscited by 3
9 more
  1. 2024Variance-Reducing Couplings for Random Featurescited by 2
  2. 2024All Random Features Representations are Equivalentcited by 2
  3. 2026EUGens: Efficient, Unified, and General Dense Layerscited by 2
  4. 2023Orthogonal Random Features: Explicit Forms and Sharp Inequalitiescited by 1
  5. 2026Manifold Random Featurescited by 1
  6. 2026SLAY: Geometry-Aware Spherical Linearized Attention with Yat-Kernelcited by 1
  7. 2022Multiple View Performers for Shape Completioncited by 0
  8. 2024EUGens: Efficient, Unified, and General Dense Layerscited by 0
  9. 2026Rationally Linearized MLPscited by 0