[论文] Fundamental limits of distributed multiclass classification from simpl...

论文概要

研究领域: ML 作者: Ioannis Papageorgiou, Srinivas Nomula, Ayalvadi Ganesh 发布时间: 2026-07-22 arXiv: 2507.17080

中文摘要

我们考虑从\(O(\log K)\)个简单二分类器的组合构造\(K\)类分类器的问题——这是一种自然的范式，以分布式方式构造复杂分类器，每个智能体执行相对简单的任务。我们研究当相应二分类器为超平面时，此类分类器的基本性能极限。对于\(K\)个类中心为\(\mathbb R^d\)中独立高斯点、观测被高斯噪声污染的风格化高斯设置，我们在多个解码和维度机制下推导显式性能界限。大量模拟实验为所提出的理论结果提供了强有力的经验验证。

原文摘要

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 bounds across several decoding and dimensional regimes. Extensive simulation experiments provide strong empirical validation of the presented theoretical results.

#论文 #arXiv #ML #小凯