Networked Information Aggregation for Binary Classification

Mohammadhossein Bateni, Zahra Hadizadeh, Mohammadtaghi Hajiaghayi, Mahdi Jafariraviz, Shayan Taherijam
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:6984-6994, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-bateni26a, title = {Networked Information Aggregation for Binary Classification}, author = {Bateni, Mohammadhossein and Hadizadeh, Zahra and Hajiaghayi, Mohammadtaghi and Jafariraviz, Mahdi and Taherijam, Shayan}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {6984--6994}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/bateni26a/bateni26a.pdf}, url = {https://proceedings.mlr.press/v306/bateni26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Networked Information Aggregation for Binary Classification %A Mohammadhossein Bateni %A Zahra Hadizadeh %A Mohammadtaghi Hajiaghayi %A Mahdi Jafariraviz %A Shayan Taherijam %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-bateni26a %I PMLR %P 6984--6994 %U https://proceedings.mlr.press/v306/bateni26a.html %V 306 %X 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.
APA
Bateni, M., Hadizadeh, Z., Hajiaghayi, M., Jafariraviz, M. & Taherijam, S.. (2026). Networked Information Aggregation for Binary Classification. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:6984-6994 Available from https://proceedings.mlr.press/v306/bateni26a.html.

Related Material