# Fast Label Embeddings for Extremely Large Output Spaces

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2015.

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

- [NGAME: Negative Mining-aware Mini-batching for Extreme Classification](https://mlsanity.com/paper/2207.04452/) (2022)
- [Counterfactual Learning To Rank for Utility-Maximizing Query Autocompletion](https://mlsanity.com/paper/2204.10936/) (2022)
- [On Riemannian Approach for Constrained Optimization Model in Extreme Classification Problems](https://mlsanity.com/paper/2109.15021/) (2021)

## Abstract (arXiv)

Many modern multiclass and multilabel problems are characterized by increasingly large output spaces. For these problems, label embeddings have been shown to be a useful primitive that can improve computational and statistical efficiency. In this work we utilize a correspondence between rank constrained estimation and low dimensional label embeddings that uncovers a fast label embedding algorithm which works in both the multiclass and multilabel settings. The result is a randomized algorithm for partial least squares, whose running time is exponentially faster than naive algorithms. We demonstrate our techniques on two large-scale public datasets, from the Large Scale Hierarchical Text Challenge and the Open Directory Project, where we obtain state of the art results.