mlsanityData to 7 Oct 2026

Hybrid Random Features

arXiv 2110.04367 ↗First posted 8 Oct 2021cs.LG stat.MLcited by 25

Not on the map. Why?

Abstract (arXiv)

We propose a new class of random feature methods for linearizing softmax and Gaussian kernels called hybrid random features (HRFs) that automatically adapt the quality of kernel estimation to provide most accurate approximation in the defined regions of interest. Special instantiations of HRFs lead to well-known methods such as trigonometric (Rahimi and Recht, 2007) or (recently introduced in the context of linear-attention Transformers) positive random features (Choromanski et al., 2021). By generalizing Bochner's Theorem for softmax/Gaussian kernels and leveraging random features for compositional kernels, the HRF-mechanism provides strong theoretical guarantees - unbiased approximation and strictly smaller worst-case relative errors than its counterparts. We conduct exhaustive empirical evaluation of HRF ranging from pointwise kernel estimation experiments, through tests on data admitting clustering structure to benchmarking implicit-attention Transformers (also for downstream Robotics applications), demonstrating its quality in a wide spectrum of machine learning problems.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 22 of its 36 references that are in the map. First posted on arXiv 8 Oct 2021.

Builds on

22 of 36 references.

References · 22

  1. 2018Representation Learning with Contrastive Predictive Codingcited by 7,662
  2. 2016Pointer Sentinel Mixture Modelscited by 2,992
  3. 2020Conformer: Convolution-augmented Transformer for Speech Recognitioncited by 1,838
  4. 2020Rethinking Attention with Performerscited by 1,584
  5. 2021Linear Transformers Are Secretly Fast Weight Programmerscited by 471
  6. 2021Random Feature Attentioncited by 350
  7. 2016Using the Output Embedding to Improve Language Modelscited by 266
  8. 2015On Wasserstein Two Sample Testing and Related Families of Nonparametric Testscited by 165
  9. 2020Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyondcited by 107
  10. 2015Less is More: Nystr"om Computational Regularizationcited by 89
  11. 2016Orthogonal Random Featurescited by 89
  12. 2016Tying Word Vectors and Word Classifiers: A Loss Framework for Language Modelingcited by 87
10 more
  1. 2021Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encodingcited by 50
  2. 2020Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformerscited by 49
  3. 2017The Unreasonable Effectiveness of Structured Random Orthogonal Embeddingscited by 43
  4. 2014Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernelscited by 41
  5. 2017Adaptive Sampled Softmax with Kernel Based Samplingcited by 38
  6. 2019Sampled Softmax with Random Fourier Featurescited by 33
  7. 2016Large-Scale Kernel Methods for Independence Testingcited by 32
  8. 2016Recycling Randomness with Structure for Sublinear time Kernel Expansionscited by 8
  9. 2017Random Features for Compositional Kernelscited by 5
  10. 2021Unlocking Pixels for Reinforcement Learning via Implicit Attentioncited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 7; 2023: 8; 2024: 4; 2025: 3; 2026: 2.

25 papers.

Sort:

By area:

  1. 2022Socratic Models: Composing Zero-Shot Multimodal Reasoning with Languagecited by 513
  2. 2024The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicrycited by 119
  3. 2023Efficient Attention via Control Variatescited by 23
  4. 2022Chefs' Random Tables: Non-Trigonometric Random Featurescited by 20
  5. 2024MetaLA: Unified Optimal Linear Approximation to Softmax Attention Mapcited by 20
  6. 2023Taming graph kernels with random featurescited by 17
  7. 2021On Learning the Transformer Kernelcited by 14
  8. 2025Scaling Linear Attention with Sparse State Expansioncited by 12
  9. 2022Attention-based Random Forest and Contamination Modelcited by 10
  10. 2023Learning a Fourier Transform for Linear Relative Positional Encodings in Transformerscited by 10
  11. 2023Random Fourier Signature Featurescited by 9
  12. 2025Selective Rotary Position Embeddingcited by 8
13 more
  1. 2024Linear Transformer Topological Masking with Graph Random Featurescited by 7
  2. 2025Collaborative Bayesian Optimization via Wasserstein Barycenterscited by 7
  3. 2023TRAMS: Training-free Memory Selection for Long-range Language Modelingcited by 5
  4. 2022Attention and Self-Attention in Random Forestscited by 4
  5. 2023FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Featurescited by 4
  6. 2026ZeroS: Zero-Sum Linear Attention for Efficient Transformerscited by 4
  7. 2022Implicit Two-Tower Policiescited by 3
  8. 2023Generalization Bound for Diffusion Models using Random Featurescited by 3
  9. 2023Hardness of Low Rank Approximation of Entrywise Transformed Matrix Productscited by 3
  10. 2024Spectraformer: A Unified Random Feature Framework for Transformercited by 3
  11. 2022Generalized Reference Kernel for One-class Classificationcited by 2
  12. 2026Manifold Random Featurescited by 1
  13. 2022LARF: Two-level Attention-based Random Forests with a Mixture of Contamination Modelscited by 0