# Logarithmic Time One-Against-Some

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

## Key facts

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

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

- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [A Survey on Extreme Multi-label Learning](https://mlsanity.com/paper/2210.03968/) (2022)
- [PINA: Leveraging Side Information in eXtreme Multi-label Classification via Predicted Instance Neighborhood Aggregation](https://mlsanity.com/paper/2305.12349/) (2023)
- [Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining](https://mlsanity.com/paper/2303.15311/) (2023)
- [Context-aware Tree-based Deep Model for Recommender Systems](https://mlsanity.com/paper/2109.10602/) (2021)
- [On Linear Separability under Linear Compression with Applications to Hard Support Vector Machine](https://mlsanity.com/paper/2202.01118/) (2022)

## Abstract (arXiv)

We create a new online reduction of multiclass classification to binary classification for which training and prediction time scale logarithmically with the number of classes. Compared to previous approaches, we obtain substantially better statistical performance for two reasons: First, we prove a tighter and more complete boosting theorem, and second we translate the results more directly into an algorithm. We show that several simple techniques give rise to an algorithm that can compete with one-against-all in both space and predictive power while offering exponential improvements in speed when the number of classes is large.