{"id":"arxiv/2607.19334","url":"https://arxiv.org/abs/2607.19334","tags":["stat.ML","cs.IT","cs.LG","math.ST"],"score":0,"title":"Fundamental limits of distributed multiclass classification from simple binary decisions","domain":"stat.ML","source":"arxiv","authors":["Ioannis Papageorgiou","Srinivas Nomula","Ayalvadi Ganesh","Sidharth Jaggi","Parimal Parag"],"reviews":0,"subject":"stat.ML","summary":"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 R^d$ and the observations are corrupted by Gaussian noise, we derive explicit performance…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-07-21","reactions":{}}