# Fundamental limits of distributed multiclass classification from simple binary decisions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 31 references that are in the map.
- First posted on arXiv 21 Jul 2026.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Contrastive ECOC: Learning Output Codes for Adversarial Defense](https://mlsanity.com/paper/2508.10491/) (2025)

## Abstract (arXiv)

We consider the problem of constructing a K-class classifier from the combination of O(log K) simple binary classifiers -- this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task. We study the fundamental performance limits of such a classifier when the corresponding binary classifiers are hyperplanes. For a stylized Gaussian setting where the K class centers are independent Gaussian points in mathbb Rd and the observations are corrupted by Gaussian noise, we derive explicit performance bounds across several decoding and dimensional regimes. Extensive simulation experiments provide strong empirical validation of the presented theoretical results.