Networked Information Aggregation for Binary Classification

We study networked binary classification on a directed acyclic graph (DAG), where each agent observes only a subset of the feature coordinates. Agents act sequentially along the DAG: each receives logits from its parents, augments its local features with these logits, fits a logistic predictor by minimizing binary cross-entropy (BCE), and forwards its logit to its outgoing neighbors. We ask whether this sequential distributed protocol achieves information aggregation: can a downstream agent attain small excess loss compared to the best logistic predictor with access to all features? This question was studied for linear regression under squared loss by Kearns, Roth, and Ryu (2026). Extending their guarantees to classification is nontrivial because their squared-loss tools do not directly transfer to BCE with a logistic link. We analyze the resulting sequential logit-passing protocol and prove an excess-loss upper bound of $O(M/\sqrt{D})$ on depth-$D$ paths satisfying the $M$ coverage condition, namely that every contiguous block of $M$ agents collectively observes all features. We also prove complementary hard instances with excess loss at least $\Omega(k/D)$, where $k$ is the feature dimension. Together, these results show that network depth is a fundamental bottleneck for information aggregation in networked logistic regression.

Many learning problems involve binary classification, where the goal is to predict one of two possible outcomes, such as whether an event will happen or not. In some settings, the useful information is spread across many agents, and each agent can see only part of the input features. This paper studies how such agents can combine their information when they are connected in a network and are only allowed to pass simple prediction messages to downstream agents. We analyze a protocol where each agent uses its own features together with the prediction messages it receives, trains a logistic classifier, and passes its learned logit to the next agents. Our results show that, under a coverage condition on the network, enough network depth allows the final agent to approach the performance of a centralized classifier that sees all features. We also construct examples showing that this depth is genuinely necessary: if the network is too shallow, some information cannot be fully aggregated. This helps clarify how communication structure limits distributed binary classification.