# Logarithmic Time Online Multiclass prediction

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

## Key facts

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

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

- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [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)
- [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)
- [Federated Multiple Label Hashing (FedMLH): Communication Efficient Federated Learning on Extreme Classification Tasks](https://mlsanity.com/paper/2110.12292/) (2021)
- [Label Embedding via Low-Coherence Matrices](https://mlsanity.com/paper/2305.19470/) (2023)

## Abstract (arXiv)

We study the problem of multiclass classification with an extremely large number of classes (k), with the goal of obtaining train and test time complexity logarithmic in the number of classes. We develop top-down tree construction approaches for constructing logarithmic depth trees. On the theoretical front, we formulate a new objective function, which is optimized at each node of the tree and creates dynamic partitions of the data which are both pure (in terms of class labels) and balanced. We demonstrate that under favorable conditions, we can construct logarithmic depth trees that have leaves with low label entropy. However, the objective function at the nodes is challenging to optimize computationally. We address the empirical problem with a new online decision tree construction procedure. Experiments demonstrate that this online algorithm quickly achieves improvement in test error compared to more common logarithmic training time approaches, which makes it a plausible method in computationally constrained large-k applications.