# One-vs-Each Approximation to Softmax for Scalable Estimation of Probabilities

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2016.

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

- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [The Devil in Linear Transformer](https://mlsanity.com/paper/2210.10340/) (2022)
- [Understanding Negative Samples in Instance Discriminative Self-supervised Representation Learning](https://mlsanity.com/paper/2102.06866/) (2021)
- [Convex Bounds on the Softmax Function with Applications to Robustness Verification](https://mlsanity.com/paper/2303.01713/) (2023)
- [Neural Architecture Search on Efficient Transformers and Beyond](https://mlsanity.com/paper/2207.13955/) (2022)
- [HETAL: Efficient Privacy-preserving Transfer Learning with Homomorphic Encryption](https://mlsanity.com/paper/2403.14111/) (2024)
- [Bayesian Principles Improve Prompt Learning In Vision-Language Models](https://mlsanity.com/paper/2504.14123/) (2025)
- [Improved Stochastic Optimization of LogSumExp](https://mlsanity.com/paper/2509.24894/) (2025)
- [On the inconsistency of separable losses for structured prediction](https://mlsanity.com/paper/2301.10810/) (2023)
- [Rethinking Approximate Gaussian Inference in Classification](https://mlsanity.com/paper/2502.03366/) (2025)
- [Enhancing Classifier Conservativeness and Robustness by Polynomiality](https://mlsanity.com/paper/2203.12693/) (2022)
- [Hyperbolic Cosine Transformer for LiDAR 3D Object Detection](https://mlsanity.com/paper/2211.05580/) (2022)
- [Accelerating Convergence in Bayesian Few-Shot Classification](https://mlsanity.com/paper/2405.01507/) (2024)
- [Softplus Attention with Re-weighting Boosts Length Extrapolation in Large Language Models](https://mlsanity.com/paper/2501.13428/) (2025)

## Abstract (arXiv)

The softmax representation of probabilities for categorical variables plays a prominent role in modern machine learning with numerous applications in areas such as large scale classification, neural language modeling and recommendation systems. However, softmax estimation is very expensive for large scale inference because of the high cost associated with computing the normalizing constant. Here, we introduce an efficient approximation to softmax probabilities which takes the form of a rigorous lower bound on the exact probability. This bound is expressed as a product over pairwise probabilities and it leads to scalable estimation based on stochastic optimization. It allows us to perform doubly stochastic estimation by subsampling both training instances and class labels. We show that the new bound has interesting theoretical properties and we demonstrate its use in classification problems.