# Extreme Classification via Adversarial Softmax Approximation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2020.

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

- [Neural Transformation Learning for Deep Anomaly Detection Beyond Images](https://mlsanity.com/paper/2103.16440/) (2021)
- [Disentangling Sampling and Labeling Bias for Learning in Large-Output Spaces](https://mlsanity.com/paper/2105.05736/) (2021)
- [S-Rocket: Selective Random Convolution Kernels for Time Series Classification](https://mlsanity.com/paper/2203.03445/) (2022)
- [A Survey on Extreme Multi-label Learning](https://mlsanity.com/paper/2210.03968/) (2022)
- [Noise Contrastive Estimation-based Matching Framework for Low-Resource Security Attack Pattern Recognition](https://mlsanity.com/paper/2401.10337/) (2024)
- [Prototype Memory for Large-scale Face Representation Learning](https://mlsanity.com/paper/2105.02103/) (2021)
- [Learning distributed representations with efficient SoftMax normalization](https://mlsanity.com/paper/2303.17475/) (2023)
- [iACOS: Advancing Implicit Sentiment Extraction with Informative and Adaptive Negative Examples](https://mlsanity.com/paper/2311.03896/) (2023)
- [D-HAN: Dynamic News Recommendation with Hierarchical Attention Network](https://mlsanity.com/paper/2112.10085/) (2021)
- [Revisiting lp-constrained Softmax Loss: A Comprehensive Study](https://mlsanity.com/paper/2206.09616/) (2022)

## Abstract (arXiv)

Training a classifier over a large number of classes, known as 'extreme classification', has become a topic of major interest with applications in technology, science, and e-commerce. Traditional softmax regression induces a gradient cost proportional to the number of classes C, which often is prohibitively expensive. A popular scalable softmax approximation relies on uniform negative sampling, which suffers from slow convergence due a poor signal-to-noise ratio. In this paper, we propose a simple training method for drastically enhancing the gradient signal by drawing negative samples from an adversarial model that mimics the data distribution. Our contributions are three-fold: (i) an adversarial sampling mechanism that produces negative samples at a cost only logarithmic in C, thus still resulting in cheap gradient updates; (ii) a mathematical proof that this adversarial sampling minimizes the gradient variance while any bias due to non-uniform sampling can be removed; (iii) experimental results on large scale data sets that show a reduction of the training time by an order of magnitude relative to several competitive baselines.