Fundamental limits of distributed multiclass classification from simple binary decisions

• URL: http://arxiv.org/abs/2607.19334v1
• Date: Tue, 21 Jul 2026 17:53:44 GMT
• Title: Fundamental limits of distributed multiclass classification from simple binary decisions
• Abstract summary: We study the fundamental performance limits of such a classifier when the corresponding binary classifiers are hyperplanes.<n>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.
• Score: 5.668668551176212
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Analytical study of the optimal combination of binary classifiers based on classifiers-induced partitioning of the training set [0.0]
  This paper studies an optimal linear combination of binary classifiers based on a logical structuration of the dataset via truth tables.<n>We derive explicit analytical formulae for optimal weights using Exponential (Boost) and Logistic (Logit) loss functions.<n>The stability of the resulting classifier and the analysis of data quality can be evaluated through the introduction of the notion of $$-frontiers.
  arXiv  Detail & Related papers  (2026-07-16T12:06:11Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• $V_1$: Unifying Generation and Self-Verification for Parallel Reasoners [69.66089681814013]
  $V_$ is a framework that unifies generation and verification through efficient pairwise ranking.<n>$V_$-Infer improves Pass@1 by up to $10%$ over pointwise verification.<n>$V_$-PairRL achieves $7$--$9%$ test-time scaling gains over standard RL and pointwise joint training.
  arXiv  Detail & Related papers  (2026-03-04T17:22:16Z)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses.<n>We establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the accuracy of the clustering.<n>We develop a computationally feasible variant of the Generalized Likelihood Ratio statistic and show that its performance gap to the lower bound can be accurately empirically estimated.
  arXiv  Detail & Related papers  (2026-02-05T14:16:47Z)
• Multiple Classifiers Based Maximum Classifier Discrepancy for Unsupervised Domain Adaptation [25.114533037440896]
  We propose to extend the structure of two classifiers to multiple classifiers to further boost its performance. We demonstrate that, on average, adopting the structure of three classifiers normally yields the best performance as a trade-off between the accuracy and efficiency.
  arXiv  Detail & Related papers  (2021-08-02T03:00:13Z)
• The Interplay between Distribution Parameters and the Accuracy-Robustness Tradeoff in Classification [0.0]
  Adrial training tends to result in models that are less accurate on natural (unperturbed) examples compared to standard models. This can be attributed to either an algorithmic shortcoming or a fundamental property of the training data distribution. In this work, we focus on the latter case under a binary Gaussian mixture classification problem.
  arXiv  Detail & Related papers  (2021-07-01T06:57:50Z)
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions [79.35722941720734]
  Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. We prove exacts characterising the estimator in high-dimensions via empirical risk minimisation. We discuss how our theory can be applied beyond the scope of synthetic data.
  arXiv  Detail & Related papers  (2021-06-07T16:53:56Z)
• SetConv: A New Approach for Learning from Imbalanced Data [29.366843553056594]
  We propose a set convolution operation and an episodic training strategy to extract a single representative for each class. We prove that our proposed algorithm is permutation-invariant despite the order of inputs.
  arXiv  Detail & Related papers  (2021-04-03T22:33:30Z)
• Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification [94.55805516167369]
  We propose a new approach for binary classification from m U-sets for $mge2$. Our key idea is to consider an auxiliary classification task called surrogate set classification (SSC)
  arXiv  Detail & Related papers  (2021-02-01T07:36:38Z)
• Consistency Regularization for Certified Robustness of Smoothed Classifiers [89.72878906950208]
  A recent technique of randomized smoothing has shown that the worst-case $ell$-robustness can be transformed into the average-case robustness. We found that the trade-off between accuracy and certified robustness of smoothed classifiers can be greatly controlled by simply regularizing the prediction consistency over noise.
  arXiv  Detail & Related papers  (2020-06-07T06:57:43Z)
• Distributionally Robust Weighted $k$-Nearest Neighbors [21.537952410507483]
  Learning a robust classifier from a few samples remains a key challenge in machine learning. In this paper, we study a minimax distributionally robust formulation of weighted $k$-nearest neighbors. We develop an algorithm, textttDr.k-NN, that efficiently solves this functional optimization problem.
  arXiv  Detail & Related papers  (2020-06-07T00:34:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.