Fundamental limits of distributed multiclass classification from simple binary decisions

arXiv:2607.19334 · stat.ML, cs.IT, cs.LG, math.ST · Submitted 2026-07-21 · Read on arXiv

Ioannis Papageorgiou, Srinivas Nomula, Ayalvadi Ganesh, Sidharth Jaggi, Parimal Parag

stat.ML, cs.IT, cs.LG, math.ST

Submitted: 2026-07-21

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Decoder — 43× in this paper · explained in 2 episodes
• Monte Carlo — 14× in this paper
• Benchmark — 3× in this paper · explained in 2 episodes
• Error Exponents — 2× in this paper · explained in 2 episodes
• Hamming Distance — 2× in this paper · explained in 2 episodes
• Robustness — 2× in this paper · explained in 6 episodes
• Abstraction — 1× in this paper · explained in 1 episode
• Accuracy — 1× in this paper · explained in 1 episode
• Binary Symmetry Channel — 1× in this paper
• Data Fusion — 1× in this paper · explained in 3 episodes
• Edge Devices — 1× in this paper · explained in 2 episodes
• Embeddings — 1× in this paper · explained in 2 episodes
• Federated Learning — 1× in this paper · explained in 19 episodes
• Intermediate Regime — 1× in this paper · explained in 2 episodes
• Non-asymptotic Analysis — 1× in this paper · explained in 2 episodes
• Redundancy — 1× in this paper · explained in 2 episodes
• Scaling Laws — 1× in this paper · explained in 4 episodes

Related papers

• Behavior of prediction performance metrics with rare events
• Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
• A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
• Scalable Posterior Uncertainty for Flexible Density-Based Clustering
• A Transport Geometry of Benign Overfitting
• Efficient quadratic entropy with distance sketches