分布式分类中,节点通过传递预测结果实现信息聚合,深度是关键瓶颈。
Networked Information Aggregation for Binary Classification
- 节点按有向无环图顺序传递预测值,融合特征逐步优化分类器。
- 理论证明深度为D的路径上误差上限为O(M/√D),下限为Ω(k/D)。
- 适用于多节点协同学习但特征不全的场景,适合研究分布式算法者。
我们研究在有向无环图(DAG)上的网络化二分类问题,每个代理仅观察共享数据集的部分特征列。代理沿DAG顺序行动:接收父节点的预测列,将其与本地特征融合,通过最小化二元交叉熵(BCE)拟合逻辑回归模型,并将预测列转发给子节点。核心问题是:这种序列式分布式训练能否实现信息聚合,即是否存在某个代理的超额损失接近于全局最优逻辑回归器(使用全部特征)的性能?该问题在平方损失下的线性回归中已有研究(Kearns, Roth, Ryu, SODA 2026),但扩展到分类面临挑战,因其分析依赖二次结构,不直接适用于带逻辑链接的BCE。本文分析了该序列逻辑传递协议,证明:(i) 在深度为D的路径上,若每连续M个代理共同观测全部特征,则超额损失上界为O(M/√D);(ii) 构造实例显示存在至少Ω(k/D)的超额损失,其中k为特征维度。两者共同揭示网络深度是网络化逻辑回归中信息聚合的根本瓶颈。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。