# Sampled Softmax with Random Fourier Features

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2019.

## Built on by (most cited first, 30 of 33)

- [FEDformer: Frequency Enhanced Decomposed Transformer for Long-term Series Forecasting](https://mlsanity.com/paper/2201.12740/) (2022)
- [Socratic Models: Composing Zero-Shot Multimodal Reasoning with Language](https://mlsanity.com/paper/2204.00598/) (2022)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Choose a Transformer: Fourier or Galerkin](https://mlsanity.com/paper/2105.14995/) (2021)
- [Parameter-Efficient Fine-Tuning with Discrete Fourier Transform](https://mlsanity.com/paper/2405.03003/) (2024)
- [EGformer: Equirectangular Geometry-biased Transformer for 360 Depth Estimation](https://mlsanity.com/paper/2304.07803/) (2023)
- [Understanding Hard Negatives in Noise Contrastive Estimation](https://mlsanity.com/paper/2104.06245/) (2021)
- [DeepXML: A Deep Extreme Multi-Label Learning Framework Applied to Short Text Documents](https://mlsanity.com/paper/2111.06685/) (2021)
- [Visual Attention Methods in Deep Learning: An In-Depth Survey](https://mlsanity.com/paper/2204.07756/) (2022)
- [FMMformer: Efficient and Flexible Transformer via Decomposed Near-field and Far-field Attention](https://mlsanity.com/paper/2108.02347/) (2021)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Item Recommendation from Implicit Feedback](https://mlsanity.com/paper/2101.08769/) (2021)
- [How Does Momentum Benefit Deep Neural Networks Architecture Design? A Few Case Studies](https://mlsanity.com/paper/2110.07034/) (2021)
- [A Call for Clarity in Beam Search: How It Works and When It Stops](https://mlsanity.com/paper/2204.05424/) (2022)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [Disentangling Sampling and Labeling Bias for Learning in Large-Output Spaces](https://mlsanity.com/paper/2105.05736/) (2021)
- [Generalization for multiclass classification with overparameterized linear models](https://mlsanity.com/paper/2206.01399/) (2022)
- [Dual-Encoders for Extreme Multi-Label Classification](https://mlsanity.com/paper/2310.10636/) (2023)
- [Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining](https://mlsanity.com/paper/2303.15311/) (2023)
- [Momentum Transformer: Closing the Performance Gap Between Self-attention and Its Linearization](https://mlsanity.com/paper/2208.00579/) (2022)
- [Fast Offline Policy Optimization for Large Scale Recommendation](https://mlsanity.com/paper/2208.05327/) (2022)
- [Prototype Memory for Large-scale Face Representation Learning](https://mlsanity.com/paper/2105.02103/) (2021)
- [Implicit Two-Tower Policies](https://mlsanity.com/paper/2208.01191/) (2022)
- [FlashSampling: Fast and Memory-Efficient Exact Sampling](https://mlsanity.com/paper/2603.15854/) (2026)
- [Efficient Image Representation Learning with Federated Sampled Softmax](https://mlsanity.com/paper/2203.04888/) (2022)
- [Learning distributed representations with efficient SoftMax normalization](https://mlsanity.com/paper/2303.17475/) (2023)
- [EMC2: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence](https://mlsanity.com/paper/2404.10575/) (2024)
- [From Algorithm to Hardware: A Survey on Efficient and Safe Deployment of Deep Neural Networks](https://mlsanity.com/paper/2405.06038/) (2024)
- [A Fresh Take on Stale Embeddings: Improving Dense Retriever Training with Corrector Networks](https://mlsanity.com/paper/2409.01890/) (2024)

## Abstract (arXiv)

The computational cost of training with softmax cross entropy loss grows linearly with the number of classes. For the settings where a large number of classes are involved, a common method to speed up training is to sample a subset of classes and utilize an estimate of the loss gradient based on these classes, known as the sampled softmax method. However, the sampled softmax provides a biased estimate of the gradient unless the samples are drawn from the exact softmax distribution, which is again expensive to compute. Therefore, a widely employed practical approach involves sampling from a simpler distribution in the hope of approximating the exact softmax distribution. In this paper, we develop the first theoretical understanding of the role that different sampling distributions play in determining the quality of sampled softmax. Motivated by our analysis and the work on kernel-based sampling, we propose the Random Fourier Softmax (RF-softmax) method that utilizes the powerful Random Fourier Features to enable more efficient and accurate sampling from an approximate softmax distribution. We show that RF-softmax leads to low bias in estimation in terms of both the full softmax distribution and the full softmax gradient. Furthermore, the cost of RF-softmax scales only logarithmically with the number of classes.