Source-linked AI summary
Optimal Rates for Agentic Networked Information Aggregation
MohammadHossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Shayan Taherijam
TL;DR
The paper asks how quickly prediction error decreases when agents see only partial data and pass forward only predictions. It sharpens the regression analysis, constructs matching lower bounds, proves a fixed-distribution obstruction, and transfers the optimal rate to logistic classification. The resulting excess-error rate is constant through depth M^2 and Θ(M^2/D) thereafter.
Problem
Networked agents observe partial feature sets and pass only predictions, leaving the depth-dependent excess-error rate unresolved between prior upper and lower bounds.
Method
The paper sharpens the cyclic analysis, constructs depth-dependent M-covered lower-bound paths, proves geometric convergence for fixed distributions, and transfers regression results to logit-passing classification.
Results
Constant excess error persists through depth M^2, followed by the optimal Θ(M^2/D) rate, with the same optimal rate established for binary classification.
Takeaways & Limitations
The optimal depth-versus-coverage law is identified for both least-squares aggregation and logit-passing binary classification.
Takeaways & Limitations
The lower-bound construction depends on depth D, and no fixed finite distribution can witness the M^2/D lower bound at every depth.
Abstract
from arXiv · showhide
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 $Ω(M/D)$ for $D<M^2$. We close this gap: the correct rate is constant up to depth $M^2$, and $Θ(M^2/D)$ beyond it. We first give a sharper analysis of the cyclic instance and improve its lower bound to $Ω(\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 $Ω(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.
1 Introduction
This paper closes the rate gap for networked information aggregation, showing that constant excess error can persist through depth M^2, after which the optimal rate is Θ(M^2/D). It also establishes analogous bounds for binary classification and rules out fixed distributions witnessing polynomial decay at every depth.
- Motivation: Agent networks aggregate partial feature views by passing predictions rather than raw data, making error decay with network depth the central quantitative question.The model benchmarks the final agent against the best full-feature linear predictor.
- Prior work: Kearns, Roth, and Ryu established an O(M/√D) upper bound and an Ω(M/D) cyclic-example lower bound, leaving the optimal rate unresolved.Their model uses M-covered paths, where every M consecutive agents collectively see all features.
- Regression results: The cyclic example's lower bound improves to Ω(1/√p), equivalently Ω(√(M/D)) after D=Mp, but it does not cover D≥M^2.A separate depth-dependent construction supplies the long-depth lower bound and the constant shallow-depth lower bound.
- Regression results: The improved regression result is constant excess error through depth M^2 and Θ(M^2/D) beyond it, matching upper and lower bounds up to constants.The upper bound improves the earlier O(M/√D) rate under the same assumptions.
- Distribution dependence: For any fixed finite distribution, excess error contracts geometrically along every M-covered path, so no fixed distribution witnesses an M^2/D lower bound at every depth.The geometric convergence result gives E_D ≤ E_1 q^⌊(D−1)/M⌋ for q∈[0,1).
2 Preliminaries
The paper formalizes networked regression and classification in which agents learn from partial features and predecessor outputs, then records projection, orthogonality, and convexity facts used later.
- Networked learning model: Agents in a DAG learn in topological order from selected raw features and parent predictions, passing only their own prediction forward.The regression model uses linear predictors; the classification model uses linear logits and passes logits rather than probabilities.
- Regression setup: The regression benchmark is the best linear predictor using all features, and performance is measured by the final agent’s excess mean squared error.The excess error is MSE(f_N) − MSE(f⋆).
- Coverage and depth: An M-covered path is one where every block of M consecutive agents collectively sees all features.This coverage condition is paired with path depth in the paper’s analysis.
- Regression facts: Least-squares prediction is the orthogonal projection of the label onto the span of the available inputs, with residual orthogonal to that span.The projection characterization follows from the multiaccuracy and self-orthogonality conditions.
- Classification facts: The classification protocol minimizes binary cross-entropy over linear logits, with probabilities obtained by applying the sigmoid function.The loss is convex, and finite minimizers satisfy zero correlation between each input and the BCE residual.
3 Improved Regression Upper Bound
The paper improves the regression upper bound for M-covered paths from O(M/√D) to O(M^2/D) by combining block-level error control with an induction on path depth.
- Block analysis: A block seeing every raw feature converts a small MSE drop across that block into a small excess error at its end.The argument uses least-squares orthogonality and Cauchy–Schwarz to relate featurewise prediction changes to the block’s error drop.
- Inductive proof: Inductively splitting the path near its midpoint yields the O(M^2/D) rate instead of the earlier O(M/√D) rate.The suffix lemma supplies the contraction needed after applying the induction hypothesis to the prefix.
- Good suffix: The excess MSE is non-increasing along the path, allowing the proof to transfer a good prefix bound to the full suffix.A suffix of length at least 2M contains enough full blocks for the pigeonhole argument.
- Improved upper bound: O(M^2/D) bounds the final agent’s excess MSE on every M-covered path of depth D.The proof assumes a global linear predictor with bounded coefficient norm and feature second moments.
4 The Cyclic Example of Kearns, Roth, and Ryu
The cyclic example is analyzed through an exact pass-to-pass residual recursion, revealing a stronger lower bound than previously known for depths below M^2.
- Construction: The cyclic path is M-covered because each block of k agents sees every feature, while the global predictor has zero error.The features telescope to the label, so the path error equals excess error.
- Lower bound: Ω(1/√p) lower bounds the cyclic example’s excess error after p passes, for 1 ≤ p ≤ k−1.Since each pass has k agents and M=k, this covers depths D=pk below M^2.
- Residual recursion: The analysis tracks residual coefficients in a Gaussian basis and represents their tail through a recursively updated probability vector.The residual after p passes involves only positions 0 through p.
- Error conversion: The residual identity E_p = S_p/(1 + 2S_p) converts a lower bound on squared tail mass into the theorem’s error bound.A second-moment argument forces sufficient mass near the origin to obtain S_p = Ω(1/√p).
- Moment analysis: A killed random walk and Catalan generating functions control the second moment of the tail distribution.The walk removes mass that reaches zero or below, and its surviving distribution is connected to the recursive tail update.
5 Depth-Dependent Lower Bound and Fixed-Distribution Obstruction
A depth-dependent construction achieves Ω(M^2/D) excess error for D ≥ M^2 and constant error through the quadratic scale, while fixed distributions converge geometrically.
- Depth-dependent lower bound: Ω(M^2/D) is achieved by an M-covered path for every M ≥ 8 and D ≥ M^2.The construction has an exact global predictor, bounded coefficient ℓ1 norm, and bounded feature second moments.
- Fixed-distribution obstruction: For any fixed distribution, excess error contracts geometrically along every M-covered path, so no single distribution witnesses a polynomial lower bound at every depth.The contraction factor depends only on the distribution and M.
- Hard instance: The construction slows aggregation by rotating successive feature directions by a small angle while hiding the target signal from individual features.Each later least-squares step removes only a small fraction of the residual.
- Error dynamics: Choosing ρ^2 = Θ(1/(D sin^2 δ)) makes each step contract error by only 1−Θ(1/D), leaving Ω(M^2/D) error after D agents.The initial error is a constant fraction of ρ^2, and later agents remove at most an O(ρ^2 sin^2 δ) fraction.
- Quadratic-depth regime: A constant lower bound persists for all depths up to M^2 in the constructed instance.At depth M^2, the excess error remains bounded away from zero.
6 Classification Results
The classification analysis improves the upper bound to O(M^2/D), transfers Gaussian regression lower bounds through proportional logits, and establishes matching depth-dependent and constant lower bounds. Fixed-distribution paths nevertheless converge geometrically under stated regularity assumptions.
- 6.1 Upper Bound: O(M^2/D) is the improved BCE excess-loss upper bound for every M-covered path of depth D.The theorem assumes the global BCE minimizer is the full-feature linear logit and protocol minimizers are attained at finite coefficients.
- 6.2 Gaussian Transfer: Gaussian regression instances transfer to classification because each finite BCE path logit is a positive scalar multiple of its least-squares predictor.The proportionality factor lies in [0,1] and is positive whenever the least-squares predictor is nonzero.
- 6.3 Lower Bounds: For every k ≥2, the cyclic classification instance has BCE excess loss at least κ1/(48√p) after pass p, for 1 ≤p ≤k−1.This follows by transferring the least-squares cyclic lower bound under unit variance of the true logit.
- 6.3 Lower Bounds: For every M ≥8 and D ≥M^2, an M-covered Gaussian classification path has a depth-dependent lower bound of order M^2/D.The construction uses a true logit with controlled coefficient ℓ1 norm and feature second moments.
- 6.3 Lower Bounds: A constant classification loss lower bound holds before quadratic depth, while fixed finite distributions contract geometrically along M-covered paths.Thus no single fixed distribution can witness an M^2/D lower bound at every depth.
A Omitted Proofs
The omitted proofs analyze cyclic least-squares updates through residual coefficients, averaging operations, and killed-walk mixtures. These recurrences characterize the residual shape and error evolution across passes.
- Cyclic residual structure: In the cyclic construction, features encountered before the active tail leave the prediction unchanged because they are orthogonal to the target and incoming prediction.The residual after each pass therefore remains supported on a progressively expanding tail of coordinates.
- Orthogonality constraints: The residual construction uses coefficient-sum identities and orthogonality to determine the final prediction and its error.The prediction is e_0 − r(p), and self-orthogonality supplies the final scalar constraint.
- One-agent updates: Each interior feature update averages its two touched positive positions up to a common rescaling, while the boundary update equalizes positions 0 and 1.These local operations determine the recursive tail shape.
- Pass recurrences: After pass p, the residual has a tail form governed by recursively defined probability vectors µ(p), with squared error E_p = S_p/(1 + 2S_p).The base case gives E_2 = 1/3, and induction determines the scalar normalization of the residual.
- Killed-walk representation: The tail distribution µ(p) is a convex combination of killed-walk distributions ν_0 through ν_{p−2}.A killed-walk step maps each ν_t to a nonnegative multiple of ν_{t+1}, preserving the convex-combination representation after normalization.
B The Upper Bound Assumptions
The upper-bound analysis requires bounded predictor coefficients and bounded feature second moments. Without either assumption, the last agent’s excess error can be made arbitrarily large even with fixed M and D.
- Required assumptions: Removing either the coefficient bound or the second-moment bound allows arbitrarily large excess error for fixed M and D.The paper states that both assumptions are necessary for a finite upper bound.
- Coefficient bound: Scaling the label by a factor a multiplies every path predictor by a and the excess error by a^2, making the error unbounded as a grows.The feature inputs and projection spans remain unchanged under this construction.
- Coefficient bound: The coefficient-bound proposition provides an M-covered path with an exact global predictor and bounded feature second moments, yet arbitrarily large excess error.It applies for M ≥ 8, D ≥ M^2, and any target R > 0.
- Coefficient bound: The coefficient-bound counterexample starts from the lower-bound instance, whose last-agent excess error is at least M^2/(1280π^2D), then rescales the label.The global predictor remains exact after rescaling, while the path predictors and excess error scale accordingly.
- Second-moment bound: The second-moment-bound argument uses the same scaling construction, preserving the exact global predictor while multiplying feature and label magnitudes together.The path follows the correspondingly rescaled predictors because each projection acts on the same span.