Papageorgiou et al. prove fundamental limits of distributed multiclass classifiers

A new theoretical paper by Papageorgiou, Nomula, Ganesh, Jaggi, and Parag tackles the practical question: can you build a high-quality multiclass classifier by combining a small number of simple binary classifiers? Specifically, they consider using only O(log K) hyperplane-based binary classifiers to distinguish among K classes. This is a natural distributed computing paradigm—each agent only needs to solve a simple binary task—but the emergent performance limits were not well understood.

The authors study a stylized Gaussian mixture where K class centers are independent Gaussian points in ℝᵈ, and observations are corrupted by Gaussian noise. They derive explicit performance bounds for several decoding strategies (e.g., one-vs-one, one-vs-all, and error-correcting output codes) across different dimensional regimes. The results reveal sharp tradeoffs between the number of binary classifiers, the dimensionality, and the achievable classification accuracy. Extensive simulations confirm the theoretical predictions. For practitioners, this work provides a rigorous framework for deciding when a distributed committee of simple classifiers can approach the accuracy of a single, more complex multiclass model—and when it cannot.