# Label Embedding via Low-Coherence Matrices

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 64 references that are in the map.
- First posted on arXiv 31 May 2023.

## Builds on (most cited first, 20 of 20)

- [Distributed Representations of Sentences and Documents](https://mlsanity.com/paper/1405.4053/) (2014)
- [AttentionXML: Label Tree-based Attention-Aware Deep Model for High-Performance Extreme Multi-Label Text Classification](https://mlsanity.com/paper/1811.01727/) (2018)
- [DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification](https://mlsanity.com/paper/1609.02521/) (2016)
- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [Bonsai -- Diverse and Shallow Trees for Extreme Multi-label Classification](https://mlsanity.com/paper/1904.08249/) (2019)
- [LightXML: Transformer with Dynamic Negative Sampling for High-Performance Extreme Multi-label Text Classification](https://mlsanity.com/paper/2101.03305/) (2021)
- [Large-scale Multi-label Learning with Missing Labels](https://mlsanity.com/paper/1307.5101/) (2013)
- [PECOS: Prediction for Enormous and Correlated Output Spaces](https://mlsanity.com/paper/2010.05878/) (2020)
- [Beyond One-hot Encoding: lower dimensional target embedding](https://mlsanity.com/paper/1806.10805/) (2018)
- [DeepXML: A Deep Extreme Multi-Label Learning Framework Applied to Short Text Documents](https://mlsanity.com/paper/2111.06685/) (2021)
- [Extreme Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon Search with 50M Products](https://mlsanity.com/paper/1910.13830/) (2019)
- [LSHTC: A Benchmark for Large-Scale Text Classification](https://mlsanity.com/paper/1503.08581/) (2015)
- [ELIAS: End-to-End Learning to Index and Search in Large Output Spaces](https://mlsanity.com/paper/2210.08410/) (2022)
- [Simultaneous Learning of Trees and Representations for Extreme Classification and Density Estimation](https://mlsanity.com/paper/1610.04658/) (2016)
- [Logarithmic Time Online Multiclass prediction](https://mlsanity.com/paper/1406.1822/) (2014)
- [Efficient Loss-Based Decoding on Graphs For Extreme Classification](https://mlsanity.com/paper/1803.03319/) (2018)
- [A Survey on Extreme Multi-label Learning](https://mlsanity.com/paper/2210.03968/) (2022)
- [Optimistic bounds for multi-output prediction](https://mlsanity.com/paper/2002.09769/) (2020)
- [Optimized Projections for Compressed Sensing via Direct Mutual Coherence Minimization](https://mlsanity.com/paper/1508.03117/) (2015)
- [Deterministic compressed sensing matrices: Construction via Euler Squares and applications](https://mlsanity.com/paper/1501.06661/) (2015)

## Abstract (arXiv)

Label embedding is a framework for multiclass classification problems where each label is represented by a distinct vector of some fixed dimension, and training involves matching model output to the vector representing the correct label. While label embedding has been successfully applied in extreme classification and zero-shot learning, and offers both computational and statistical advantages, its theoretical foundations remain poorly understood. This work presents an analysis of label embedding in the context of extreme multiclass classification, where the number of classes C is very large. We present an excess risk bound that reveals a trade-off between computational and statistical efficiency, quantified via the coherence of the embedding matrix. We further show that under the Massart noise condition, the statistical penalty for label embedding vanishes with sufficiently low coherence. Our analysis supports an algorithm that is simple, scalable, and easily parallelizable, and experimental results demonstrate its effectiveness in large-scale applications.