# Stochastic Negative Mining for Learning with Large Output Spaces

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2018.

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

- [Gemini Embedding: Generalizable Embeddings from Gemini](https://mlsanity.com/paper/2503.07891/) (2025)
- [NGAME: Negative Mining-aware Mini-batching for Extreme Classification](https://mlsanity.com/paper/2207.04452/) (2022)
- [Extreme Multi-label Learning for Semantic Matching in Product Search](https://mlsanity.com/paper/2106.12657/) (2021)
- [Max-Margin Contrastive Learning](https://mlsanity.com/paper/2112.11450/) (2021)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [sigmoidF1: A Smooth F1 Score Surrogate Loss for Multilabel Classification](https://mlsanity.com/paper/2108.10566/) (2021)
- [Cardinality-Aware Set Prediction and Top-k Classification](https://mlsanity.com/paper/2407.07140/) (2024)
- [Extreme Zero-Shot Learning for Extreme Text Classification](https://mlsanity.com/paper/2112.08652/) (2021)
- [An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates](https://mlsanity.com/paper/2206.14707/) (2022)
- [Neural Collapse in Multi-label Learning with Pick-all-label Loss](https://mlsanity.com/paper/2310.15903/) (2023)
- [CascadeXML: Rethinking Transformers for End-to-end Multi-resolution Training in Extreme Multi-label Classification](https://mlsanity.com/paper/2211.00640/) (2022)
- [Disentangling Sampling and Labeling Bias for Learning in Large-Output Spaces](https://mlsanity.com/paper/2105.05736/) (2021)
- [Consistent Polyhedral Surrogates for Top-k Classification and Variants](https://mlsanity.com/paper/2207.08873/) (2022)
- [Label Disentanglement in Partition-based Extreme Multilabel Classification](https://mlsanity.com/paper/2106.12751/) (2021)
- [A Survey on Extreme Multi-label Learning](https://mlsanity.com/paper/2210.03968/) (2022)
- [Dual-Encoders for Extreme Multi-Label Classification](https://mlsanity.com/paper/2310.10636/) (2023)
- [Towards Memory-Efficient Training for Extremely Large Output Spaces -- Learning with 500k Labels on a Single Commodity GPU](https://mlsanity.com/paper/2306.03725/) (2023)
- [Fine-grained Generalization Analysis of Vector-valued Learning](https://mlsanity.com/paper/2104.14173/) (2021)
- [Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining](https://mlsanity.com/paper/2303.15311/) (2023)
- [Top-k Classification and Cardinality-Aware Prediction](https://mlsanity.com/paper/2403.19625/) (2024)
- [Prototype Memory for Large-scale Face Representation Learning](https://mlsanity.com/paper/2105.02103/) (2021)
- [Speeding-up One-vs-All Training for Extreme Classification via Smart Initialization](https://mlsanity.com/paper/2109.13122/) (2021)
- [Large Language Model as a Teacher for Zero-shot Tagging at Extreme Scales](https://mlsanity.com/paper/2406.09288/) (2024)
- [Graph Regularized Encoder Training for Extreme Classification](https://mlsanity.com/paper/2402.18434/) (2024)
- [Federated Learning with Only Positive Labels by Exploring Label Correlations](https://mlsanity.com/paper/2404.15598/) (2024)
- [UniDEC : Unified Dual Encoder and Classifier Training for Extreme Multi-Label Classification](https://mlsanity.com/paper/2405.03714/) (2024)
- [On the Necessity of World Knowledge for Mitigating Missing Labels in Extreme Classification](https://mlsanity.com/paper/2408.09585/) (2024)
- [A Fresh Take on Stale Embeddings: Improving Dense Retriever Training with Corrector Networks](https://mlsanity.com/paper/2409.01890/) (2024)
- [ASTRA: Accurate and Scalable ANNS-based Training of Extreme Classifiers](https://mlsanity.com/paper/2409.20156/) (2024)

## Abstract (arXiv)

We consider the problem of retrieving the most relevant labels for a given input when the size of the output space is very large. Retrieval methods are modeled as set-valued classifiers which output a small set of classes for each input, and a mistake is made if the label is not in the output set. Despite its practical importance, a statistically principled, yet practical solution to this problem is largely missing. To this end, we first define a family of surrogate losses and show that they are calibrated and convex under certain conditions on the loss parameters and data distribution, thereby establishing a statistical and analytical basis for using these losses. Furthermore, we identify a particularly intuitive class of loss functions in the aforementioned family and show that they are amenable to practical implementation in the large output space setting (i.e. computation is possible without evaluating scores of all labels) by developing a technique called Stochastic Negative Mining. We also provide generalization error bounds for the losses in the family. Finally, we conduct experiments which demonstrate that Stochastic Negative Mining yields benefits over commonly used negative sampling approaches.