揭示智能体网络信息聚合的最优误差率,统一了线性回归与分类场景。
Optimal Rates for Agentic Networked Information Aggregation
- 构建深度为D的有向无环图,每段连续M个智能体共同覆盖全部特征。
- 证明深度小于M²时误差恒定,超过则以M²/D衰减,首次实现紧致率界。
- 适用于研究分布式学习、联邦智能体系统或通信受限场景的研究者。
基于Kearns、Roth和Ryu(SODA'26)的工作,本文研究网络化学习模型中的信息聚合问题。该模型刻画了代理型AI的核心模式:每个智能体仅观察部分数据,并仅传递其预测结果。在均方误差(MSE)损失下的线性回归设置中,智能体构成有向无环图(DAG),每个智能体仅可见部分特征及其父节点的预测值,拟合线性预测器后仅传递自身预测。基准是能观测全部原始特征的全特征学习者。若一条长度为D的路径满足每连续M个智能体联合覆盖所有原始特征,则称其为M-覆盖。Kearns、Roth和Ryu证明该路径末尾智能体的超额均方误差为O(M/√D),并构造出在D < M²时误差下界为Ω(M/D)的循环实例。本文填补该差距:正确速率在深度不超过M²时为常数,超过时为Θ(M²/D)。我们首先对循环实例进行更精细分析,将下界提升至Ω(√(M/D))(当D < M²)。随后,对任意D ≥ M²,构造出一个M-覆盖路径,其超额误差达到Ω(M²/D)。同一实例亦在D < M²时给出常数下界。此外,我们证明对任意固定分布,误差沿路径几何级收缩,排除了存在单一实例在所有深度均呈现多项式下界的可能。最后,我们将结果推广至Bateni等人的逻辑分类模型(采用二元交叉熵损失),证明相同的上界O(M²/D)成立;并通过证明在这些实例中逻辑路径仅需重缩放即与最小二乘路径一致,转移了所有回归下界。
原文摘要 · Abstract (English)
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 data and passes on only its own conclusion. Their model considers a linear regression problem with the mean squared error (MSE) loss. Agents sit in a DAG and each sees only a subset of the features and its parents' predictions, fits a linear predictor, and passes only its prediction forward. The benchmark is the full-feature learner that sees all raw features. A path of depth $D$ is $M$-covered if every block of $M$ consecutive agents collectively sees all raw features. Kearns, Roth, and Ryu proved that the excess mean squared error of the last agent on such a path is $O(M/\sqrt D)$, and gave a cyclic instance with excess error $\Omega(M/D)$ for $D<M^2$. We close this gap: the correct rate is constant up to depth $M^2$, and $\Theta(M^2/D)$ beyond it. We first give a sharper analysis of the cyclic instance and improve its lower bound to $\Omega(\sqrt{M/D})$ for $D<M^2$. We then construct, for every depth $D\ge M^2$, an $M$-covered path of depth $D$ with excess error $\Omega(M^2/D)$. The same instance gives the constant lower bound for all $D < M^2$. We also show that for any fixed distribution the excess error contracts geometrically along the path, ruling out any single instance that witnesses any polynomial lower bound at every depth. Finally, we prove the same optimal rate for logistic classification in the logit-passing model of Bateni et al., which considers the binary cross-entropy (BCE) loss. The same improved upper bound of $O(M^2/D)$ holds, and we transfer all the regression lower bounds by showing that on those examples the logistic path follows the least-squares path up to rescaling.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。