홈 › Papers

Networked Information Aggregation for Binary Classification

2026-05-01 · MohammadHossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Shayan Taherijam arxiv

We study networked binary classification on a directed acyclic graph (DAG) where each agent observes only a subset of the feature columns of a shared dataset. Agents act sequentially along the DAG: each receives prediction columns from its parents (if any), augments its local features with these columns, fits a logistic predictor by minimizing binary cross-entropy (BCE), and forwards its prediction column to its outgoing neighbors. We ask whether this sequential distributed training procedure achieves information aggregation, meaning that some agent attains small excess loss compared to the best logistic predictor trained with access to all feature columns. This question was studied for linear regression under squared loss by Kearns, Roth, and Ryu (SODA 2026). Extending their guarantees to classification is nontrivial because their analysis relies on quadratic structure that does not directly transfer to BCE with a logistic link. We analyze the resulting sequential logit-passing protocol and prove: (i) an excess loss upper bound of $O(M/\sqrt{D})$ on depth-$D$ paths under the condition that every $M$ contiguous subsequence of $M$ agents collectively observe all features, and (ii) a close lower bound showing instances with excess loss of at least $Ω(k/D)$ where $k$ is the dimension of the feature space. Together, these results identify network depth as a fundamental bottleneck for information aggregation in networked logistic regression.

📄 PDF Abstract BibTeX arXiv:2605.01082

Code (0)

등록된 구현이 없습니다.

Tasks

Binary Classification

Optimal Rates for Agentic Networked Information Aggregation

2026-09-04 · MohammadHossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz 외 arxiv

Building on the pioneering paper of Kearns, Roth, and Ryu (SODA'26), we study information aggregation in a networked learning model. The model captures a central pattern in agentic AI: each agent sees only part of the da…

Multi-Agent Reinforcement Learning in Stochastic Networked Systems

2020-06-11 · NeurIPS 2021 12 · Yiheng Lin, Guannan Qu, Longbo Huang, Adam Wierman

We study multi-agent reinforcement learning (MARL) in a stochastic network of agents. The objective is to find localized policies that maximize the (discounted) global reward. In general, scalability is a challenge in th…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Optimal Binary Classifier Aggregation for General Losses

2015-10-01 · NeurIPS 2016 12 · Akshay Balsubramani, Yoav Freund

We address the problem of aggregating an ensemble of predictors with known loss bounds in a semi-supervised binary classification setting, to minimize prediction loss incurred on the unlabeled data. We find the minimax o…

Binary Classification General Classification

Graph Infomax Adversarial Learning for Treatment Effect Estimation with Networked Observational Data

2021-06-05 · Zhixuan Chu, Stephen L. Rathbun, Sheng Li

Treatment effect estimation from observational data is a critical research topic across many domains. The foremost challenge in treatment effect estimation is how to capture hidden confounders. Recently, the growing avai…

Causal Inference Graph Learning Node Classification

Convex Optimization for Binary Classifier Aggregation in Multiclass Problems

2014-01-16 · Sunho Park, TaeHyun Hwang, Seungjin Choi

Multiclass problems are often decomposed into multiple binary problems that are solved by individual binary classifiers whose results are integrated into a final answer. Various methods, including all-pairs (APs), one-ve…