Conceptio › Archive › arXiv CS

arXiv CSopen access

Optimal Rates for Agentic Networked Information Aggregation

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

arXiv:2609.05318v1 [cs.LG] 4 Sep 2026

Optimal Rates for Agentic Networked Information Aggregation MohammadHossein Bateni Google Research [email protected]

Zahra Hadizadeh University of California, Irvine [email protected]

MohammadTaghi Hajiaghayi University of Maryland [email protected]

Mahdi JafariRaviz University of Maryland [email protected]

Shayan Taherijam University of California, Irvine [email protected] Abstract Building on the pioneering paper of Kearns, Roth, and Ryu [KRR26] (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 [KRR26] proved that the excess mean squared error of the last agent on such a path is O(M/ 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) p beyond it. We first give a sharper analysis of the cyclic instance and improve its lower bound to Ω( M/D) for D < M 2 . We then construct, for every depth D ≥ 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. [BHH+26], 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.

Introduction

AI systems increasingly run as networks of agents rather than as one model. In a typical pipeline, no agent sees all the data. Each agent works on its own slice, limited by context windows, privacy, or cost, and passes forward only a short output such as a prediction [GCW+24]. For example, the Chain-of-Agents framework of Zhang et al. [ZSC+24] splits a long input across a chain of language-model agents, and each agent sends a single message to the next. The pattern is older than these systems: in social learning, going back to DeGroot [DeG74], parties publish predictions instead of sharing what they saw, and in vertical federated learning, parties hold different feature columns of the same data [YLC+19]. In all these settings, the same question comes up: can an agent late in the network predict as well as one centralized learner that sees all the data? Since each agent forwards only its prediction, information about the data builds up slowly, one hop at a time. Depth is what makes good prediction possible, but it is also the cost, since each hop is

Table 1: Bounds on the excess error of the last agent on an M -covered path of depth D. Setting

Result

Regime All D

Previous bound √ O(M/ D) [KRR26]

This work

Upper bound

D < M2

Ω(M/D) [KRR26]

Ω(1)

D ≥ M2

–

Cyclic example

D < M2

Ω(M/D) [KRR26]

Fixed distribution

All D

–

Ω(M 2 /D) p Ω( M/D) ⌊(D−1)/M ⌋

Upper bound

All D

√ O(M/ D) [BHH+26]

O(M 2 /D)

D < M2

Ω(M/D) [BHH+26]

Ω(1)

D ≥ M2

–

Cyclic example

D < M2

Ω(M/D) [BHH+26]

Fixed distribution

All D

–

Ω(M 2 /D) p Ω( M/D) ⌊(D−1)/M ⌋

Lower bound Regression

Lower bound Classification

O(M 2 /D)

O q for some q < 1

another trained model or model call. The real question is then a quantitative one: how fast does the error fall as depth grows? Kearns, Roth, and Ryu [KRR26] made this question precise in a distributed learning model where agents A1 , . . . , AN sit in a directed acyclic graph and act in a topological order. There is a distribution D over the features x1 , . . . , xd and the label Y . Each agent Ai sees only a subset of the features Si ⊆ [d], and the predictions of preceding agents that have edges to it. Agent Ai fits a linear predictor fi of the label that minimizes the mean squared error using all its inputs, and passes its prediction to its successors. Let MSE(f ) be the mean squared error of the predictor f . To measure the performance of this model, they consider the excess error MSE(fN ) − MSE(f ⋆ ) of the final agent’s prediction fN compared to the best possible linear predictor f ⋆ , where a single agent would have access to all the features x1 , . . . , xd . To analyze this model, Kearns, Roth, and Ryu [KRR26] considered two metrics: the depth of the graph and the coverage of the features along the path. If A1 , . . . , AD is a directed path of agents in the graph, we say that the path is M -covered if every block of M consecutive agents√sees all features. Kearns, Roth, and Ryu [KRR26] showed that the excess error of fD is bounded by O(M/ D) when there is an M -covered path of depth D to the final agent. They also provided an example (which we call the cyclic example) and showed that it has an excess error of Ω(M/D). This lower bound shows that the depth of the graph is a necessary condition for good performance, but leaves a large gap in the rate. Bateni et al. [BHH+26] also studied the same model, but instead of considering the regression problem with the least-squares loss, they considered the binary classification problem with the binary cross-entropy (BCE) loss. Each agent fits a linear logit predictor to its inputs, and the logit z also goes through the sigmoid function, so the final prediction is the probability σ(z). Agents send only the logit values (and not the probabilities) to their successors. Bateni et al. [BHH+26] showed that the same upper and lower bounds hold for the classification problem.

1.1

Our Contributions

We will show that most bounds given by Kearns, Roth, and Ryu [KRR26] and Bateni et al. [BHH+26] are far from tight, and close the gaps between the upper and lower bounds. Table 1 summarizes our bounds next to the previous ones. We will state our results in the regression setting first, and later show analogous results for classification.

1.1.1

Regression

√ We show that the earlier upper bound of O(M/ D) by Kearns, Roth, and Ryu [KRR26] is not tight in the following theorem. We use the exact same assumptions as the earlier upper bound. Theorem 1 (Improved regression upper bound). Consider an M -covered path of depth D. Assume the Pd P 2 global predictor f ⋆ (x) = ℓ=1 wℓ⋆ xℓ satisfies ℓ |wℓ⋆ | ≤ A⋆ , and each feature satisfies E[x2ℓ ] ≤ MX . Then MSE(fD ) − MSE(f ⋆ ) ≤ C

M2 , D

where C depends only on A⋆ and MX . Proof Sketch. To explain where the gain comes from, we briefly recall the argument of Kearns, Roth, and Ryu [KRR26]. The error is non-increasing along the path, so the total error drop over the path is at most the first agent’s excess error, which is bounded by MSE(0) − MSE(f ⋆ ) which itself is bounded by a constant depending only on A⋆ and MX . Splitting the path into ⌊D/M ⌋ blocks of M consecutive agents, the pigeonhole principle finds a block whose drop is O(M/D). A small drop over √ a block forces a small excess error at its end.√Quantitatively, a drop of ε over a block gives excess error O( M ε), and ε = O(M/D) gives the rate O(M/ D). We instead feed this argument its own output. Split the path in half. By induction on the depth, the agent at the midpoint already has excess error O(M 2 /D). The drop over the second half is at most this excess error, not a constant, so the pigeonhole now finds a block in the second half with drop O(M 3 /D2 ), and the √ block bound O( M ε) gives excess error O(M 2 /D) at the final agent, closing the induction. √ √ This improves on O(M/ D), but only once D > M 2 . Before that point, M 2 /D (or the previous M/ D) is at least constant. We next turn to the lower-bound path of Kearns, Roth, and Ryu [KRR26], which we call the cyclic example. For a fixed k, it considers independent standard Gaussian variables z1 , . . . , zk , and builds k features P as X1 = z1 and Xi = zi − zi−1 for i ≥ 2. The label is Y = zk , and the global predictor is exact since i Xi = zk . Each agent sees one feature, in the repeating cyclic order X1 , . . . , Xk , X1 , . . . , Xk , . . ., and a pass is one full cycle. The path has M = k and D = pk after p ≤ k − 1 passes, so it only tests the range D < M 2 . In this range, the previous bound on the excess error is Ω(M/D), though empirical evidence in Kearns, Roth, and Ryu [KRR26] points to their analysis of this example being loose. In pursuit of a tighter bound in this range, we analyze this instance more carefully. Theorem 2 (Cyclic example lower bound). Consider the cyclic example of Kearns, Roth, and Ryu [KRR26] for every integer k ≥2 and every integer 1 ≤ p ≤ k − 1. Then the excess error of the final agent is at least √ √ 1/(48 p) = Ω 1/ p . Equivalently, the excess error after D = pk agents is at least p p M/D . (1/48) k/D = Ω Proof Sketch. We change the basis of predictors to z1 , . . . , zk , since they are orthonormal. This reveals structure in the predictors. Let Y − ft be the residual of some agent t. We show that the residual of the agent at the end of pass p, denoted by r(p) , has the following shape in the new basis: (p) (p) r(p) = (1 + 2Sp )−1 Sp , Sp , µ1 , . . . , µp−1 , P (p) where Sp = i (µi )2 , and the excess error of this agent is Ep = Sp /(1 + 2Sp ). Moreover, the tail µ(p) is a probability vector and we show an exact recursion for finding µ(p) based on µ(p−1) . The recursion on the tail µ(p) matches a walk on the integers that starts at 1, and at each step moves up by one and then falls back by a geometrically distributed amount, and is killed when it reaches 0 or below. Encoding the steps of the walk as words over the alphabet {(, )} connects it to the Catalan numbers. We use the Catalan √ generating function to get a closed form for the survival probability of the walk, and show that it is Θ(1/ t) at time t. Conditioned on survival, the second moment of the walk grows only linearly with t. √ √ So after p passes the squared mass Sp of the tail is Ω(1/ p), and so the excess error Ep is Ω(1/ p). 3

Despite the challenges in analyzing the cyclic example, even the improved bound is still far from the constant upper bound in the range D < M 2 . The example also gives no bound for D ≥ M 2 , so we move on and consider a new example that covers the range D ≥ M 2 as well. Theorem 3 (Lower bound). For every M ≥ 8 and D ≥ M 2 , there is an M -covered path instance with an exact global predictor whose coefficient ℓ1 norm is at most 3, each feature has second moment at most 2, and whose path predictor fD satisfies M2 1 . E[(Y − fD )2 ] ≥ 2 1280π D Proof Sketch. We construct an example designed to make information aggregation as slow as possible. Fix M, D. We use three independent standard Gaussian variables Z0 , Z1 , Z2 , and introduce M features X0 , . . . , XM −1 where for j = 0, . . . , M − 1, Xj = Z1 + ρ(cos(jδ)Z0 + sin(jδ)Z2 ), where δ = 2π/M and ρ is a small radius chosen below. We then construct a path of length D where the agents see features X0 , X1 , . . . , XM −1 , X0 , X1 , . . . in the same cyclic manner as in the cyclic example. We set the label as Y = ρZ0 . This way, the target signal is in a direction that no single feature reveals, and the feature seen by successive agents rotates by the small angle δ. The residual of each agent is always orthogonal to the feature just seen, and the next feature points in almost the same direction, so each agent can remove only an O(ρ2 sin2 δ) fraction of the remaining error. Choosing ρ2 = Θ(M 2 /D) makes this fraction Θ(1/D), so a constant fraction of the starting error, itself of order ρ2 , survives all D agents, leaving excess error Ω(ρ2 ) = Ω(M 2 /D). Though this instance has label variance only ρ2 , the full construction fixes the scale by adding a common feature X⋆ , an independent standard Gaussian seen by every agent, and setting Y = X⋆ + ρZ0 . Every agent learns X⋆ at once, so the analysis is unchanged. Setting D = M 2 in the above theorem gives a constant lower bound for the agent at depth M 2 . Since the excess error is non-increasing, this gives the same constant lower bound for all agents at depths t ≤ M 2 . Corollary 1 (Constant error before quadratic depth). For every integer M ≥ 8, there is an M -covered path instance of depth M 2 with an exact global predictor, coefficient ℓ1 norm at most 3, and feature second moments at most 2, such that, if Et is the excess error after the first t agents, then Et ≥

1 1280π 2

(1 ≤ t ≤ M 2 ).

Together with the upper bound, this gives the right order up to constants: constant excess error can persist until depth M 2 , and after that the rate is M 2 /D. Our construction’s distribution depends on the depth D. We show that this cannot be avoided: under any fixed distribution on a finite set of features, the path predictor improves geometrically along every M -covered path, so no such fixed distribution can witness the M 2 /D lower bound at every depth. Theorem 4 (No fixed distribution for all depths). Fix M and a distribution D on (x1 , . . . , xd , Y ). Assume x1 , . . . , xd , Y have bounded second moments. For every c > 0, there is a depth Dc such that for any DAG of agents on D, if A1 → · · · → AD is an M -covered path in it with D ≥ Dc , then ED < c

M2 , D

where ED is the excess error of agent AD . To show this, we prove a geometric upper bound on the excess error for any fixed distribution. 4

Theorem 5 (Fixed-distribution geometric convergence). Fix M and a distribution D on (x1 , . . . , xd , Y ) with d finite. Assume x1 , . . . , xd , Y have bounded second moments. There is a constant q ∈ [0, 1), depending only on D and M , such that for any DAG of agents on D, if A1 → · · · → AD is an M -covered path in it, then for any 1 ≤ s ≤ D − M , Es+M ≤ qEs , where Et is the excess error of agent At . Consequently, ED ≤ E1 q ⌊(D−1)/M ⌋ . We prove this by considering a single path of M agents that together see all raw features. For the drop in the excess error along this path, we give a factor q ∈ [0, 1) that depends only on the feature subsets seen by the agents and the distribution D, and not on the rest of the network. The proof of the theorem then applies this to every block of M consecutive agents: since there are only finitely many possible tuples of feature subsets, the maximum of their factors is a single q < 1 that works for every block. This upper bound is also interesting in itself. It shows that any fixed distribution will eventually converge very quickly to the optimal solution. 1.1.2

Classification

We consider the binary classification protocol introduced by Bateni et al. [BHH+26], which uses the same underlying network model as regression. There is a distribution D over (x1 , . . . , xd , Y ) where Y ∈ {0, 1}, and a DAG of N agents A1 , . . . , AN . Each agent Ai sees the features xSi for a subset Si ⊆ [d], and the logits of all its parents in the DAG. The agent fits a linear logit zi , a linear combination of xSi and the parent logits, and then predicts Pr(Y = 1 | x) as σ(zi ), where σ is the sigmoid function. The agent chooses zi to minimize the binary cross-entropy loss. Instead of passing the probabilities, agents pass the logits zi to their successors. Let L(z) denote the binary cross-entropy loss. The proof of Theorem 1 uses only facts about least squares that have analogues in Bateni et al. [BHH+26], under the same kind of bounded coefficient and second-moment assumptions. So the same induction from the proof of the regression theorem again gives the optimal upper bound. Theorem 6 (Improved classification upper bound). For every depth D and every M -covered path, assume Pd P 2 the global BCE minimizer is z⋆ = ℓ=1 wℓ xℓ , that ℓ |wℓ | ≤ B⋆ , that E[x2ℓ ] ≤ BX for every feature, and that the protocol minimizers are attained at finite coefficients. Then L(zD ) − L(z⋆ ) ≤ C

M2 , D

where C depends only on B⋆ and BX . For lower bounds, we use the same examples as in Theorems 2 and 3. To transform the regression label Y ∈ R to a label Y c ∈ {0, 1}, we use Pr(Y c = 1 | x) = σ(Y ). To analyze these examples for classification, one may restate the regression analysis using the classification analogues of the regression facts. We instead take a shortcut. These regression examples contain only Gaussian features and a Gaussian label. We can therefore directly use their already proven bounds for classification once we prove the transfer theorem below. In the special case where a single agent sees all the features that generate Y , the logistic and least-squares fits are known to align [Bri83; EDB16]. Theorem 7 (Gaussian transfer to classification). Let x1 , . . . , xd be centered jointly Gaussian variables and G = wT x be a linear combination of them. Let Y ∈ {0, 1} satisfy Pr(Y = 1 | x) = σ(G). Assume that Var(G) ≤ B. Let zt be the logit predictor of agent At . Assume the same network is used to predict G with least-squares loss. Let ft be the predictor of At , and let Et be the excess error in this network, i.e., Et = ∥G − ft ∥22 . Then, for all t, zt = ct ft for some ct ∈ [0, 1], with ct > 0 whenever ft ̸= 0. Furthermore, for a constant κB > 0 depending only on B, 1 κB Et ≤ L(zt ) − L(G) ≤ Et . 8 5

Proof Sketch. We start from a simpler case. We consider a single agent with inputs u1 , . . . , um , and let z be its BCE predictor of Y . Let f be the least-squares predictor of G on the same inputs. We show that z = cf for some c ∈ [0, 1], with c > 0 whenever f ̸= 0. This means that the two predictors are in the same direction. To prove this, we write z = cf + r, where r lies in the span of the inputs and is orthogonal to f . The least-squares residual G − f is orthogonal to that whole span, so r is orthogonal to G, and orthogonal jointly Gaussian variables are independent, so r is independent of G, f , and Y . By Jensen’s inequality and the strict convexity of the BCE loss, removing such an independent component can only decrease the loss, so the minimizer lies on the line spanned by f . All that remains is to locate c. Restricted to the line, the loss is convex in c, so it suffices to check the derivative at the endpoints: when f ̸= 0, it is negative at c = 0, since f is positively correlated with Y , and nonnegative at c = 1. Hence c ∈ (0, 1]. Then consider a classification network with predictors z1 , . . . , zN and its corresponding regression network with predictors f1 , . . . , fN . Having z = cf for a single agent, we induct on the network according to its topological ordering, to show that the direction stays the same at all agents between the two networks. The first agent receives no predictions, so by the above, z1 = c1 f1 . For a later agent Ai , the induction hypothesis gives that its inputs span the same directions in the two networks, so zi = ci fi . We also show that there exists a constant κB depending only on B such that, whenever E[z 2 ] ≤ B and E[G2 ] ≤ B, 1 κB E[(z − G)2 ] ≤ L(z) − L(G) ≤ E[(z − G)2 ]. 8 Combining the fact that the two predictors point in the same direction with the above inequality, we derive the theorem’s inequality directly. Applying this transfer theorem to Theorems 2 and 3 gives the same lower-bound picture for classification. The shallow constant lower bound is again a corollary of the depth-dependent construction. Theorem 8 (Classification cyclic example lower bound). For every k ≥ 2, there is a k-covered Gaussian classification path instance with true logit G and Bernoulli labels with mean σ(G) such that, at the end of pass 1 ≤ p ≤ k − 1, κ1 L(zpk ) − L(G) ≥ √ . 48 p Equivalently, if D = pk, then κ1 L(zD ) − L(G) ≥ 48

k . D

Theorem 9 (Classification depth-dependent lower bound). For every M ≥ 8 and D ≥ M 2 , there is an M covered Gaussian classification path instance of depth D with true logit G, Bernoulli labels with mean σ(G), and G an exact linear combination of the features whose coefficient ℓ1 norm is at most 3, with E[x2ℓ ] ≤ 2 for every feature, and with M2 L(zD ) − L(G) ≥ cld D for a universal constant cld > 0. Corollary 2 (Classification constant loss before quadratic depth). There is a universal constant cquad > 0 such that, for every M ≥ 8, there is an M -covered Gaussian classification path instance of depth M 2 with true logit G an exact linear combination of the features whose coefficient ℓ1 norm is at most 3, with E[x2ℓ ] ≤ 2 for every feature, and with Bernoulli labels with mean σ(G) such that, for every 1 ≤ t ≤ M 2 , L(zt ) − L(G) ≥ cquad . Finally, as in the regression setting, the classification lower bound cannot come from one fixed finite distribution, unless the distribution changes with the target depth: the excess loss again contracts geometrically 6

along every covered path. The proof parallels the regression one, with the probability residual σ(zt ) − σ(z⋆ ) in place of f ⋆ − ft . The one difference is that the regression proof turned the excess error into a squared distance, and cross-entropy is not a squared norm; but every logit on the path has loss at most L(0) = log 2, and on this bounded set the loss is strongly convex, which again makes the excess loss comparable to the squared distance between logits. Theorem 10 (No fixed classification distribution for all depths). Fix M and a distribution D on (x1 , . . . , xd , Y ) with d finite, bounded second moments for the raw features, and Y ∈ {0, 1}. Assume the BCE minimum over the raw-feature span is attained, and call a minimizer z⋆ . For every c > 0 there is a Dc such that for any DAG of agents on D, if A1 → · · · → AD is a path whose every M consecutive raw-feature spans sum to the full raw-feature span and D ≥ Dc , then L(zD ) − L(z⋆ ) < c

M2 . D

Thus one fixed finite classification distribution with an attained minimizer cannot witness an M 2 /D lower bound for all depths.

1.2

Additional Related Work

The model we study is due to Kearns, Roth, and Ryu [KRR26]: the DAG formulation, the M -coverage condition, and the first depth-based regression bounds are all theirs, and Bateni et al. [BHH+26] adapted the protocol to binary classification with agents passing logits rather than predictions. Working in the same model without changes, we give matching upper and lower bounds of order M 2 /D on covered paths, and we show that no single distribution can realize the lower bound at every depth at once. Opinion dynamics and social learning. The older backdrop is social learning in networks. In the model of DeGroot [DeG74], an agent starts with a belief about a common state and at each step resets it to a weighted average of its neighbors’ beliefs, a fixed rule with no inference behind it, and Golub and Jackson [GJ10] give conditions under which the resulting consensus is correct. In sequential variants, agents instead act one at a time on their own signal and the actions they have seen, and Banerjee [Ban92] and Bikhchandani, Hirshleifer, and Welch [BHW92] show how this leads to herding, where a few early movers fix the outcome and later signals go unused. Gale and Kariv [GK03] analyze Bayesian agents learning from their neighbors’ actions, Mossel, Olsman, and Tamuz [MOT16] study agents who exchange Gaussian estimates over many rounds, and Mossel et al. [MMS+18] characterize when such exchange reaches an equilibrium that aggregates everyone’s information. Throughout this line there is one hidden state observed through noise, and the question is whether it is recovered in the limit. Ours is a different problem. There is no single hidden state: the label comes from a joint distribution over many correlated features, and we compare against the best linear predictor that sees all of them. The path is used only once, so what limits the final agent is its depth, not the number of rounds. Reusing predictions as features. Predictions can also be fed forward as features. Stacked generalization does exactly this, training a second model on the first model’s outputs [Wol92]. Multicalibration and multiaccuracy [HKR+18; KGZ19], and later outcome indistinguishability [GHK+23], ask when one predictor can stand in for many losses or downstream decisions at once, and Noarov and Roth [NR26] show a deterministic predictor already suffices, at optimal sample complexity. In all of this a downstream learner still sees the whole prediction next to the raw features. Our agents get far less to work with, just their own features and one number from upstream, and the whole question is how much of the label survives that number being recomputed at every hop. Agreement protocols. Prediction-passing is also the medium of the agreement literature. Aumann’s theorem [Aum76] already says that two Bayesians who keep trading posteriors cannot end up disagreeing, and Collina et al. [CGG+25] and Collina et al. [CGG+26] reach the same conclusion without full Bayesian 7

agents, needing only calibration conditions a learner can enforce, after which a few exchanges bring both parties to a shared prediction that pools what each of them knew. Eaton et al. [EGH+26] come at it from the other side and bound how far two independently trained models can disagree in the first place. Our upper bounds lean on multiaccuracy and self-orthogonality, cousins of those calibration conditions that ordinary least squares happens to satisfy for free. The one structural difference is traffic. Agreement runs both ways and many times over, each side updating against the other, whereas on our path a prediction is made once and passed on, and no agent ever answers back. Vertical federated learning and distributed optimization. Splitting features across parties is the setting of vertical federated learning and split learning. Yang et al. [YLC+19] survey the area. SecureBoost [CFJ+21] and split learning [VGS+18] train a single shared model over such a split without exposing raw features, by exchanging gradients, activations, or masked statistics over many rounds. The related literature on gossip and distributed optimization [BGP+06; ZDW13; CLZ17] studies how the communication graph slows a joint optimization. In our protocol there is no shared model to train. Each agent fits its own model once and passes on a single prediction or logit, and the error reflects how much is lost by reducing each agent’s output to that single number at every step.

Preliminaries

In this section we restate the model formally and introduce the necessary notation. We write [k] for the set {1, 2, . . . , k}. All expectations are over the distribution D.

2.1

Model, Regression Protocol, and MSE Benchmark

We start with the regression model of Kearns, Roth, and Ryu [KRR26]. There are agents A = {A1 , . . . , AN } in a directed acyclic graph G = (A, E). An edge Aj → Ai means that Ai receives the prediction made by Aj . We write Pa(i) = {Aj : (Aj → Ai ) ∈ E} for the parents of Ai . Agents learn in a topological order. The population distribution D is over feature-label pairs (x, Y ), where x ∈ Rd and Y ∈ R. Agent Ai sees only the coordinates xSi , for Si ⊆ [d]. Agent Ai also sees the parent predictions fj (x) for Aj ∈ Pa(i) and chooses the best linear prediction of Y from these inputs. Thus X fi (x) = wi⊤ xSi + vij fj (x), Aj ∈Pa(i) (1) {wi , vij } ∈ arg min E[(fi (x) − Y )2 ]. Following Kearns, Roth, and p Ryu [KRR26, Definitions 2.1 and 2.2], the error of a predictor is MSE(f ) = E[(f (x) − Y )2 ], and ∥Z∥2 = E[Z 2 ] for a random variable Z. The global predictor is f ⋆ (x) = (w⋆ )⊤ x, where w⋆ minimizes E[((w⊤ x) − Y )2 ] over all w ∈ Rd . On a path of depth D, we write the agents as A1 → A2 → · · · → AD . Each agent can always keep the incoming prediction, so the error along the path is non-increasing, as shown below in Lemma 2. For this path, we use the following definition of Kearns, Roth, and Ryu [KRR26]. Definition 1 (M -covered path). A path A1 → A2 → · · · → AD is M -covered if every block of M consecutive Si+M −1 Sj = [d] for every i ≤ D − M + 1. agents collectively sees all features in [d]. In other words, j=i

2.2

Regression Facts Used Later

We import the following two lemmas without proof from Kearns, Roth, and Ryu [KRR26]. Lemma 1 (Kearns, Roth, and Ryu [KRR26], Lemma 3.1 and Corollary 3.2). If f is the least-squares predictor from inputs u1 , . . . , um , then E[ur (f − Y )] = 0 for each input ur . Since f is a linear combination of its inputs, also E[f (f − Y )] = 0. 8

These are the multiaccuracy and self-orthogonality conditions from Kearns, Roth, and Ryu [KRR26, Definitions 2.3 and 2.4]. Lemma 2 (Kearns, Roth, and Ryu [KRR26], Lemmas 3.3, 3.7, and 3.8). For any predictors f and g, MSE(f ) = MSE(g) − 2E[g(f − Y )] + 2E[f (f − Y )] − E[(f − g)2 ].

(2)

If Aj ∈ Pa(i), then MSE(fi ) ≤ MSE(fj ) and E[(fi − fj )2 ] = MSE(fj ) − MSE(fi ).

(3)

The next lemma restates the least squares problem in a more useful way. Suppose the inputs are u1 , . . . , um , Pm and their span is the set of predictors that can be formed from them: { r=1 ar ur : a1 , . . . , am ∈ R}. We say two random variables U and W are orthogonal when E[U W ] = 0. Thus the equations in Lemma 1 say that least squares leaves a residual Y − f that is orthogonal to every predictor in the span. Lemma 3 (Least squares is projection). Let Y, u1 , . . . , um be random variables with finite second moments, and let V = span{u1 , . . . , um }. If f is the least-squares predictor from inputs u1 , . . . , um , then f is the orthogonal projection of Y onto V : up to almost sure equality, it is the unique random variable in V such that Y − f is orthogonal to every element of V . Proof. Lemma 1 gives E[v(Y − f )] = 0 for every v ∈ V by linearity. For uniqueness, suppose f1 , f2 ∈ V both have residuals orthogonal to V . Since f1 − f2 ∈ V , substituting v = f1 − f2 into the orthogonality condition for f1 and for f2 gives E[(Y − f1 )(f1 − f2 )] = 0,

E[(Y − f2 )(f1 − f2 )] = 0.

Subtracting the two equations we get E[(f1 − f2 )2 ] = 0. Hence f1 = f2 almost surely.

2.3

Classification Setup

For classification, Y ∈ {0, 1}. A logit z gives the probability p = σ(z), where σ(t) = 1/(1 + e−t ) is the sigmoid function. The population binary cross-entropy (BCE) loss is L(z) = E[log(1 + ez(x) ) − Y z(x)].

(4)

We also write L(p) when p = σ(z) and define ϕ(z) = log(1 + ez ). Note that ϕ(z) satisfies ϕ′ (z) = σ(z). The classification model follows the logit-passing setup of Bateni et al. [BHH+26] and is similar to the regression model. Agent Ai receives parent logits zj (x), not parent probabilities. It chooses the coefficients in X zi (x) = wi⊤ xSi + vij zj (x), Aj ∈Pa(i) (5) pi (x) = σ(zi (x)), {wi , vij } ∈ arg min L(zi ). We assumeP the protocol minimizers are attained at finite coefficients. The global BCE minimizer is written d as z⋆ (x) = ℓ=1 wℓ xℓ and p⋆ = σ(z⋆ ).

2.4

Classification Facts Used Later

We import the following facts from Bateni et al. [BHH+26]. Lemma 4 (Bateni et al. [BHH+26], Lemma 3.1). If z is a finite BCE minimizer over linear inputs u1 , . . . , um , then each input has zero correlation with the BCE residual. In particular, E[z(σ(z) − Y )] = 0. 9

Lemma 5 (Bateni et al. [BHH+26], Definition 3.2 and Lemmas 3.3–3.4). For two probability predictors p and q, define p 1−p D(p∥q) = E p log + (1 − p) log . (6) q 1−q Then, L(q) = L(p⋆ ) + D(p⋆ ∥q), D(p∥q) ≥ 2E[(p − q)2 ].

(7)

Here p⋆ is the BCE minimizer on the same inputs as q. If Aj ∈ Pa(i), then L(zj ) − L(zi ) = D(pi ∥pj ) ≥ 0. Lemma 6 (Bateni et al. [BHH+26], Lemma 3.5). If z minimizes BCE over its current inputs and zg is any other logit, then L(z) ≤ L(zg ) + |E[(σ(z) − Y )zg ]| . (8) This is the classification replacement for the least-squares residual comparison. The BCE loss is convex, a fact we rely on repeatedly when locating minimizers, so we record it once here. Lemma 7. ϕ(z) = log(1 + ez ) is strictly convex. The BCE loss L(z) = E[ϕ(z) − Y z] is convex. Proof. Since ϕ′′ (z) = σ ′ (z) = σ(z)(1 − σ(z)) > 0 for every z, ϕ is strictly convex. For each label Y , the map z 7→ ϕ(z) − Y z is convex, and averaging over the distribution shows that the BCE loss L(z) = E[ϕ(z) − Y z] is convex.

Improved Regression Upper Bound

For the rest of this section, we assume the following conditions from [KRR26]: • The global predictor f ⋆ (x) =

⋆ ℓ=1 wℓ xℓ satisfies

⋆ ⋆ ℓ |wℓ | ≤ A .

2 . • Each feature satisfies E[x2ℓ ] ≤ MX

Consider an M -covered path of agents A1 → A2 → · · · → An . By Lemma 2, the errors are non-increasing along the path, meaning that MSE(f1 ) ≥ MSE(f2 ) ≥ · · · ≥ MSE(fn ). Now consider a block of M agents Ai → Ai+1 → · · · → Ai+M −1 . Kearns, Roth, and Ryu [KRR26] show that if the error does not decrease significantly over the block, then the excess error of the last agent in the block is small. We formalize this in the following lemma, which is analogous to Theorem 3.9 in [KRR26]. We provide its proof for completeness. Lemma 8. Consider any path A1 → A2 → · · · → An and a block of k consecutive agents indexed by [a + 1, b] that sees every raw feature at least once, where b = a + k. If ε ≥ MSE(fa ) − MSE(fb ), then √ MSE(fb ) − MSE(f ⋆ ) ≤ 2A⋆ MX kε. Proof. Fix a feature xℓ , and let agent Aj in the block see it. Least-squares orthogonality from Lemma 1 gives E[xℓ (fj − Y )] = 0. By Equation (3) in Lemma 2, b X

∥fi − fi−1 ∥22 = MSE(fa ) − MSE(fb ) ≤ ε.

i=a+1

Since agent Aj sees xℓ , its orthogonality E[xℓ (fj −Y )] = 0 lets us replace the target Y with fj in the following equation: E[xℓ (fb − Y )] = E[xℓ (fb − fj )] + E[xℓ (fj − Y )] = E[xℓ (fb − fj )].

Pb Write fb − fj as fb − fj = i=j+1 (fi − fi−1 ). The sum has at most k terms, since j ≥ a + 1 and b = a + k. The triangle inequality followed by Cauchy–Schwarz across these terms gives

∥fb − fj ∥2 ≤

b X

∥fi − fi−1 ∥2 ≤



√

k

b X

1/2 ∥fi − fi−1 ∥22 

≤

√ kε,

i=j+1

Pb where the last step uses the bound i=a+1 ∥fi − fi−1 ∥22 ≤ ε from above. A final Cauchy–Schwarz over the 2 feature, with E[x2ℓ ] ≤ MX , then yields q √ |E[xℓ (fb − Y )]| = |E[xℓ (fb − fj )]| ≤ E[x2ℓ ] ∥fb − fj ∥2 ≤ MX kε. The bound just derived holds for every feature ℓ, since the block sees each raw feature at least once. To turn these per-feature bounds into an MSE bound, apply Equation (2) from Lemma 2 with f = fb and g = f ⋆ : MSE(fb ) − MSE(f ⋆ ) = −2E[f ⋆ (fb − Y )] + 2E[fb (fb − Y )] − E[(fb − f ⋆ )2 ]. Self-orthogonality of fb from Lemma 1 makes the middle term vanish, E[fb (fb − Y )] =P0, and the last term ⋆ ⋆ is nonpositive, so MSE(fb ) − MSE(f ) ≤ 2|E[f ⋆ (fb − Y )]|. Finally, expand f ⋆ = ℓ wℓ xℓ and use the P per-feature bound together with ℓ |wℓ⋆ | ≤ A⋆ , |E[f ⋆ (fb − Y )]| ≤

√ |wℓ⋆ | |E[xℓ (fb − Y )]| ≤ A⋆ MX kε,

ℓ

√

which gives MSE(fb ) − MSE(f ⋆ ) ≤ 2A⋆ MX kε. 2 We now state √ the following lemma. This lemma is what allows us to get a bound of O(M /D) instead of the O(M/ D) bound of Kearns, Roth, and Ryu [KRR26]. It states that in a long enough path, p if an agent near the start has excess error δ, then after another L agents, the excess error is at most O( δ/L).

Lemma 9 (A good suffix from a good prefix). Take an M -covered path A1 → A2 → · · · → An and an agent As on it with MSE(fs ) − MSE(f ⋆ ) ≤ δ. Let L = n − s and consider the suffix As+1 → · · · → As+L . If L ≥ 2M , then r √ ⋆ δ ⋆ MSE(fn ) − MSE(f ) ≤ 2 2 A MX M . L Proof. Split the suffix into K = ⌊L/M ⌋ full blocks. Since L ≥ 2M , K ≥ L/(2M ). The total MSE drop over these blocks is at most MSE(fs ) − MSE(f ⋆ ) ≤ δ, so by the pigeonhole principle, some block has drop ε ≤ δ/K ≤ 2M δ/L. Applying Lemma 8 on this block with k = M gives, at the end q of that block, r 2M 2 δ ⋆ ⋆ MSE(fq ) − MSE(f ) ≤ 2A MX . L By Lemma 2, the MSE is non-increasing along the path, so MSE(fn ) ≤ MSE(fq ). √ Kearns, Roth, and Ryu [KRR26] prove their O(M/ D) by considering the drop in the excess error along a path of depth D. They argue that this drop is bounded by the first agent’s excess error MSE(f1 ) − MSE(f ⋆ ), and then partition the path into K = ⌊D/M ⌋ blocks of size M . By the pigeonhole principle, there must be a block that has a drop of at most (MSE(f1 ) − MSE(f ⋆ ))/K. They then apply Lemma 8. We take a different approach by inducting on D. We break a path of depth D into a prefix of length s = ⌊D/2⌋ and a suffix of length D − s. We use the bound given by induction hypothesis, and apply Lemma 9 on the suffix. The following restated theorem proves this formally.

Theorem 1 (Improved regression upper bound). Consider an M -covered path of depth D. Assume the P Pd 2 . Then global predictor f ⋆ (x) = ℓ=1 wℓ⋆ xℓ satisfies ℓ |wℓ⋆ | ≤ A⋆ , and each feature satisfies E[x2ℓ ] ≤ MX MSE(fD ) − MSE(f ⋆ ) ≤ C

M2 , D

where C depends only on A⋆ and MX . √ Proof. Set c⋆ = 2 2 A⋆ MX , the constant of Lemma 9, and set C = 6c2⋆ . We first bound the excess error of any agent. The zero predictor is feasible for every agent, so MSE(fi ) ≤ MSE(0). Applying Equation (2) with f = f ⋆ and g = 0, and then using the self-orthogonality of f ⋆ from Lemma 1, gives X 2 MSE(0) − MSE(f ⋆ ) = ∥f ⋆ ∥22 ≤ |wℓ⋆ | ∥xℓ ∥2 ≤ (A⋆ MX )2 . ℓ

It follows that every agent satisfies MSE(fi ) − MSE(f ⋆ ) ≤ (A⋆ MX )2 . We now prove that MSE(fD ) − MSE(f ⋆ ) ≤ CM 2 /D for every M -covered path of depth D, arguing by induction on D. If D < 4M , then M 2 /D > M/4 ≥ 1/4, and hence MSE(fD ) − MSE(f ⋆ ) ≤ (A⋆ MX )2 ≤

M2 C ≤C . 4 D

Now suppose D ≥ 4M , and split the path at s = ⌊D/2⌋ into a prefix A1 → · · · → As and a suffix As+1 → · · · → AD of length L = D − s. Both are M -covered, being sub-paths of an M -covered path. We apply the induction hypothesis on the prefix. Since s = ⌊D/2⌋ ≥ (D − 1)/2 ≥ D/3 (using D ≥ 3), MSE(fs ) − MSE(f ⋆ ) ≤

3CM 2 CM 2 ≤ =: δ. s D

The suffix has length L = D − s ≥ D/2 ≥ 2M , so Lemma 9 applies with this δ. Substituting δ = 3CM 2 /D and L ≥ D/2 then gives s r √ δ 3CM 2 /D M2 ⋆ MSE(fD ) − MSE(f ) ≤ c⋆ M ≤ c⋆ M = c⋆ 6C . L D/2 D √ Finally, C = 6c2⋆ so c⋆ 6C = C. Thus the right-hand side is CM 2 /D, which completes the induction.

The Cyclic Example of Kearns, Roth, and Ryu

Kearns, Roth, and Ryu [KRR26, Definitions 5.1 and 5.2] used a path example to show that depth is necessary, and showed its excess error is Ω(M/D). Weprevisit the same example and show that it is harder than their analysis found: its excess error is in fact Ω( M/D). For a fixed k, the example constructs k features X1 , . . . , Xk and a label. It then constructs a path network where each agent sees one raw feature, and in a cyclic manner: agents A1 → A2 → · · · see features X1 , X2 , . . . , Xk , X1 , X2 , . . . , Xk , . . . . Let a pass be a single repetition of the features. Our analysis begins by giving the exact recursive formula for the predictor of the agent at the end of each pass in Section 4.2. We then show that this recursion is similar to a recursion induced by a walk over integers, and analyze the second moment of the variables in the walk recursion. To do this, in Section 4.3, we show a connection between the walk recursion and word over the parentheses alphabet {(, )}. This reveals a connection to the Catalan numbers. In Section 4.4, we use a general form of the Catalan generating function to close the arguments. Although the analysis proves to be challenging, we later show that this example is not the hardest possible one. The construction only reaches depth D < M 2 , and even in this regime, as shown in Section 5, there is a different example with constant lower bound. 12

4.1

The Path

Fix k ≥ 2. Let z1 , . . . , zk be independent standard Gaussians, let Y = zk , and set X1 = z1 and Xi = zi − zi−1 for 2 ≤ i ≤ k. The network is a single path that sees the features in the repeating cyclic order X1 , . . . , Xk , X1 , . . . , Xk , . . ., and one pass is one full cycle of X1 , . . . , Xk . Let ybp be the prediction of the last agent in pass p, the one that sees Xk , and let Rp = Y − ybp be its residual and Ep = E[Rp2 ]. Every block of k agents sees all features, thus the path is k-covered or M -covered with M = k. The features telescope to X1 + · · · + Xk = zk = Y , so the global predictor has zero error. Hence the error Ep is exactly the excess error after D = pk agents, which is what we lower bound. In the rest of this section, we will prove Theorem 2 restated below. Theorem 2 (Cyclic example lower bound). Consider the cyclic example of Kearns, Roth, and Ryu [KRR26] for every integer k ≥2 and every integer 1 ≤ p ≤ k − 1. Then the excess error of the final agent is at least √ √ 1/(48 p) = Ω 1/ p . Equivalently, the excess error after D = pk agents is at least p p M/D . (1/48) k/D = Ω

4.2

Residual Shape and Tail Update

We prove the theorem by tracking the residual Rp from pass to pass, and we first set up coordinates for it. Because z1 , . . . , zk are independent standard Gaussians, they are orthonormal, with E[za zb ] = 1 when a = b and 0 otherwise. So we can change the basis for every predictor and residual, from X1 , . . . , Xk to z1 , . . . , zk . We index the z-coefficients of a vector by position j ≥ 0: position j holds zk−j , so position 0 holds zk = Y . We write ej for the coefficient vector of zk−j . After p passes the residual involves only zk−p , . . . , zk , that is positions 0, . . . , p, so we may write Rp = Pp (p) (p) (p) (p) = (r0 , . . . , rp ). This fact is due to Kearns, Roth, and Ryu j=0 rj zk−j with coefficient vector r [KRR26, Lemma 5.5]; it is the first part of the lemma below, whose proof we restate for completeness, and the second part strengthens it by describing the structure of the residual. Lemma 10 (End-of-pass shape). For 1 ≤ p ≤ k − 1, the residual has the form above and p X (p) rj = 1,

Ep =

j=0

p X

(p)

(rj )2 = r0 ,

(p)

r0 = r1 .

j=0

The proof of the above lemma is in Appendix A. In the next lemma, we analyze what each agent in the pass does to the residual locally. The lemma after that aggregates these changes across a pass. Lemma 11 (One-agent update). Suppose an agent receives residual coefficient vector b, so its incoming prediction has coefficient vector e0 − b. Let b+ be the outgoing residual coefficient vector. If the feature seen by the agent is orthogonal to both Y and the incoming prediction, then b+ = b. If the feature is gj = ej−1 − ej with j ≥ 2, then for some scalar α, + b+ j−1 = bj =

α (bj−1 + bj ), 2

b+ m = αbm

(m ≥ 1, m ∈ / {j − 1, j}).

If the feature is g1 = e0 − e1 , then for some scalar α, + b+ 0 = b1 =

1 (1 − α) + α(b0 + b1 ) , 2

b+ m = αbm

(m ≥ 2).

Lemma 12 (Tail shape). Define probability vectors µ(p) recursively as follows. Start with µ(2) = (1). For P (p−1) 2 (p−1) (p−1) each 3 ≤ p ≤ k − 1, after µ(p−1) = (µ1 , . . . , µp−2 ) has been defined, set Sp−1 = i (µi ) . Initialize 13

(p)

u(p) = (u1 , . . . , up−1 ) to the zero vector, where ui

is the unnormalized mass assigned to position i + 1. Add

(p) (p−1) (p−1) (p) Sp−1 /2 to u1 . For every 1 ≤ m ≤ p − 2, the mass µm at position m + 1 adds 2−(m+2−i) µm to ui for P P (p) (p) each 1 ≤ i ≤ m + 1. Normalize: µ(p) = u(p) / i ui . Finally set Sp = i (µi )2 for every 2 ≤ p ≤ k − 1.

Then for every 2 ≤ p ≤ k − 1, (p)

(p)

r(p) = (1 + 2Sp )−1 (Sp , Sp , µ1 , µ2 , . . . , µp−1 ), Sp . Ep = 1 + 2Sp The proofs of the above lemmas are in Appendix A. To prove a lower bound on Ep , we will use the following lemma. Lemma P 13 (Second Pmoment forces √ squared mass). If µ is a probability vector on the positive integers and m = i i2 µi , then i µ2i ≥ 3/(16 m). √ √ Proof. Let L = ⌈2 m⌉. Since the support is positive, m ≥ 1 and L ≤ 3 m. Markov’s inequality P P gives 2 2 µ ≤ m/L ≤ 1/4, so the first L coordinates carry mass at least 3/4. By Cauchy–Schwarz, i i>L i µi ≥ √ 2 (3/4) /L ≥ 3/(16 m). With the above lemma in mind, all that is left is to show an upper bound on the second moment of µ(p) . We state this as the following lemma. Lemma 14. For 2 ≤ p ≤ k − 1, X

(p)

i2 µi

≤ 9p.

We will show this lemma later in the next subsection. Having the above lemma, we can now directly show Theorem 2 through Lemma 13. Proof of Theorem 2. For p = 1 the least-squares predictor of zk from Xk = zk − zk−1 leaves residual (zk + zk−1 )/2, so E1 = 1/2 ≥ 1/48. P √ √ (p) For p ≥ 2, Lemma 14 gives i i2 µi ≤ 9p. Thus Lemma 13 with m ≤ 9p gives Sp ≥ 3/(16 9p) = 1/(16 p). P (p) P (p) Since µ(p) is a probability vector, Sp = i (µi )2 ≤ i µi = 1, hence 1 + 2Sp ≤ 3, and Lemma 12 gives Ep =

4.3

Sp 1 Sp ≥ ≥ √ . 1 + 2Sp 3 48 p

The Killed Walk

The update rule for µ(p−1) to µ(p) in Lemma 12 can be described by tracking one unit of mass in a walk over the integers. The unit mass starts at W0 = 1. To take one step, it first increases this integer by one and then subtracts a random amount: Wt+1 = Wt + 1 − Gt+1 , where Pr(Gt+1 = ℓ) = 2−(ℓ+1) for ℓ ≥ 0, and G1 , G2 , . . . are independent. Lemma 15. Suppose WtP= j > 0. Then Pr(Wt+1 = i | Wt = j) = 2−(j+2−i) for 1 ≤ i ≤ j + 1, and Pr(Wt+1 ≤ 0 | Wt = j) = ℓ≥j+1 2−(ℓ+1) = 2−(j+1) . Proof. Landing at integer i ∈ {1, . . . , j + 1} means Gt+1 = j + 1 − i, so Pr(Wt+1 = i | Wt = j) = Pr(Gt+1 = j + 1 − i) = 2−(j+2−i) . Landing at 0 or below means Gt+1 ≥ j + 1, so Pr(Wt+1 ≤ 0 | Wt = j) = P −(ℓ+1) = 2−(j+1) . ℓ≥j+1 2 14

The transition probabilities from Wt to Wt+1 in Lemma 15 are very closely related to the update rule for µ(p−1) to µ(p) in Lemma 12. To make the transition explicit, we next consider the killed walk. We call the mass that lands at 0 or below killed : once its integer reaches 0 or below, it is removed. Let τ be the time the mass is killed: ( min{t ≥ 0 : Wt ≤ 0}, if this set is nonempty, τ= ∞, otherwise. For each integer t ≥ 0, define νt by looking at time t only among the outcomes that have not been killed: νt (i) = Pr(Wt = i | τ > t) for i ≥ 1. Thus ν0 puts all mass at integer 1. We now show the concrete connection between the killed walk and the tail probabilities µ(p) . Lemma 16 (Tail as a killed-walk mixture). For every 2 ≤ p ≤ k − 1, the vector µ(p) from Lemma 12 is a convex combination of ν0 , . . . , νp−2 . The proof is in Appendix A. Thus, to bound the second moment of µ(p) , we need to bound the second moment of the distributions ν0 , . . . , νp−2 . We state this as the following lemma, which is the main target of the rest of Section 4. Lemma 17 (Killed-walk moment). For every integer t ≥ 0, the distribution νt satisfies X i2 νt (i) = E[Wt2 | τ > t] ≤ 9(t + 1). i

Having the above lemma, we can directly show Lemma 14. Proof of Lemma 14. Lemma 16 writes µ(p) as a convex combination of ν0 , . . . , νp−2 . The killed-walk moment bound in Lemma 17 then gives X X (p) i2 µi ≤ max i2 νt (i) ≤ 9(p − 1) ≤ 9p. i

4.4

0≤t≤p−2

Killed-walk Second Moment Bound

To tackle Lemma 17, we use the decomposition E[Wt2 |τ > t] =

E[Wt2 1{τ >t} ] . Pr(τ > t)

(9)

We bound the numerator and denominator separately. P First, we compute Pr(τ > t). We will construct the generating function H(z) = t≥0 Pr(τ > t)z t and give a closed form for it. Intuitively, this distribution is closely related to the Catalan numbers. We will use two tools. The Catalan generating function is classical, so we state it without proof; the generalization we need is less standard, so we derive it with a short lemma. P Let Cn be the n-th Catalan number. The Catalan generating function is C(s) = i≥0 Ci si . This generating function satisfies the functional equation C(s) = 1 + sC(s)2 [Sta15], and hence √ 1 − 1 − 4s C(s) = . (10) 2s We will consider words over the alphabet {(, )}, i.e. strings of parentheses. We call a word valid if every prefix of the word has at least as many opening parentheses as closing parentheses. We call a word balanced if it has the same number of opening and closing parentheses. For a word w, we define o(w) to be the number of opening parentheses in w and c(w) to be the number of closing parentheses in w. 15

Define the bivariate generating function F (a, b) on valid balanced words as X F (a, b) = ao(w) bc(w) . valid balanced w

Since in balanced words the number of opening and closing parentheses is the same, we have F (a, b) = C(ab). Next, define the bivariate generating function G(a, b) on valid words as X G(a, b) = ao(w) bc(w) . valid w

The next lemma will establish a closed-form expression for G(a, b). Lemma 18. G(a, b) =

C(ab) . 1 − aC(ab)

Lemma 19 (Survival words). At time t, form a word w by writing, for each step s = 1, . . . , t, one opening parenthesis followed by Gs closing parentheses. Then w is valid if and only if the mass has not been killed by time t. The proofs of the above two lemmas are in Appendix A. We next use the fact that H(z) = G(z/2, 1/2) to get a closed form for H. This will later be used to get a closed form for Pr(τ > t). Lemma 20 (Survival generating function). X 2 H(z) = Pr(τ > t)z t = (1 − z)−1/2 − 1 . z t≥0

Proof. Fix t. For a sequence of outcomes G1 , . . . , Gt , construct a word w as in Lemma 19. Then w has Pt o(w) = t and c(w) = s=1 Gs . By Lemma 19, w is valid if and only if τ > t. Qt The probability of this outcome is s=1 2−(Gs +1) = 2−(o(w)+c(w)) . Then write X X X H(z) = Pr(τ > t)z t = 2−(o(w)+c(w)) z o(w) = (z/2)o(w) 2−c(w) = G(z/2, 1/2). t≥0

valid w

By Lemma 18, we have H(z) =

C(z/4) . 1 − (z/2)C(z/4)

Applying Equation (10) with s = z/4 and simplifying gives the claimed form. The closed form for H is useful because its coefficients are standard central binomial coefficients. Extracting them gives an exact survival probability. Lemma 21 (Coefficient extraction). For every integer t ≥ 0, the coefficient of z t in z2 ((1 − z)−1/2 − 1) is 2t+1 2t+2 . t+1 /2 Proof. By the generalized binomial theorem, (1 − z)

−1/2

X −1/2 n≥0

(−z)n ,

−1/2 1 · 3 · · · (2n − 1) (2n)! 1 2n n (−1) = = n = n . n 2n n! 4 (n!)2 4 n n n P Therefore (1 − z)−1/2 = n≥0 2n n z /4 . Subtracting 1 removes the n = 0 term, and dividing by z shifts t+1 which equals the power down by one. Hence the coefficient of z t in H(z) = z2 ((1 − z)−1/2 − 1) is 2 2t+2 t+1 /4 2t+1 2t+2 . t+1 /2 16

The above lemma gives a closed form for Pr(τ > t). The next lemma provides bounds on this probability. Its proof is in Appendix A. √ √ Lemma 22 (Survival probability). For every integer t ≥ 0, 1/ t + 1 ≤ Pr(τ > t) ≤ 2/ t + 1. Having bounded the denominator of Equation (9), we next aim to bound the numerator E[Wt2 1{τ >t} ] in the next three lemmas. This is the last step before proving Lemma 17. The proofs of the following two lemmas are in Appendix A. Lemma 23 (Increment moments). For each integer t ≥ 1, the increment 1 − Gt satisfies E[1 − Gt ] = 0 and Var(1 − Gt ) = 2. √ Lemma 24. For every integer t ≥ 0, E[min{t, τ }] ≤ 4 t. √ Lemma 25. For every integer t ≥ 0, E[Wt2 1{τ >t} ] ≤ 1 + 8 t. Proof. Put T = min{t, τ }. Since T is an integer between 0 and t, WT2 = W02 +

t−1 X

2 1{T >s} (Ws+1 − Ws2 ).

s=0

Fix s < t. The event {T > s} is determined by G1 , . . . , Gs . After fixing these values, Ws is fixed and Gs+1 is independent. Since Ws+1 = Ws + 1 − Gs+1 , Lemma 23 gives 2 E[Ws+1 − Ws2 | G1 , . . . , Gs ] = 2Ws E[1 − Gs+1 ] + E[(1 − Gs+1 )2 ] = 2.

Thus 2 E[1{T >s} (Ws+1 − Ws2 )] = 2 Pr(T > s).

Taking expectations in the telescoping identity gives E[WT2 ] = 1 + 2

t−1 X

Pr(T > s) = 1 + 2E[T ],

s=0

where√the last equality uses again that T is integer-valued and lies between 0 and t. By Lemma 24, E[WT2 ] ≤ 1 + 8 t. On τ > t, we have T = t and WT = Wt . On τ ≤ t, the term WT2 is nonnegative, so E[WT2 ] = E[Wt2 1{τ >t} ] + E[WT2 1{τ ≤t} ] ≥ E[Wt2 1{τ >t} ]. Combining the two inequalities proves the lemma. We finally have all the necessary tools to prove Lemma 17. Proof of Lemma 17. The equality follows from the definition νt (i) = Pr(Wt = i | τ > t). For the upper bound, combine Lemmas 22 and 25: √ √ E[Wt2 1{τ >t} ] ≤ (1 + 8 t) t + 1 ≤ 9(t + 1). Pr(τ > t) √ √ √ The last line uses 1 ≤ t + 1 and t ≤ t + 1. E[Wt2 | τ > t] =

Depth-Dependent Lower Bound and Fixed-Distribution Obstruction

The cyclic example of the previous section only reaches depth D < M 2 , and even there its bound is weak since it shrinks with a polynomial rate in D. We now close the picture. For each M and D with D ≥ M 2 , we build an M -covered path whose excess error is Ω(M 2 /D). As a special case, setting D = M 2 shows the error can stay bounded away from zero all the way up to the quadratic scale. An artifact of this construction is that the distribution itself depends on the specific value of D. One might aim to show the lower bound with a distribution only depending on M , similar to the cyclic example in Section 4. We show that this is not possible: under any fixed distribution, the path predictor converges to the global predictor at a geometric rate along every M -covered path, so no fixed distribution can witness the M 2 /D bound at every depth.

5.1

The Depth-Dependent Lower Bound

In this section, we will introduce the instance with Ω(M 2 /D) excess error. The plan is to make information aggregation as slow as possible. We hide a target signal of small size ρ in a direction that no single feature reveals, and we let the feature seen by successive agents rotate by only a tiny angle δ at each step. Because consecutive features point in almost the same direction, while the residual is already orthogonal to the current feature, each agent can remove only a tiny fraction of the remaining error. Matching ρ and δ to the depth D keeps the error at Ω(M 2 /D) even after D agents. Fix integers M ≥ 8 and D ≥ M 2 . Define δ=

2π , M

ρ2 =

1 . 80D sin2 δ

Let X⋆ , Z0 , Z1 , Z2 be independent standard Gaussians, and let Y = X⋆ + ρZ0 . We will directly give X⋆ to all agents. We also define features X0 , X1 , . . . , XM −1 as follows. For j = 0, . . . , M − 1, Xj = Z1 + ρ(cos(jδ)Z0 + sin(jδ)Z2 ). Agent At sees X⋆ , X(t−1) mod M , and the prediction from At−1 if t > 1. Thus every block of M agents sees all features. The common feature X⋆ is there only to keep the scale of the labels near 1. Every agent sees X⋆ , so this part of the label is learned immediately and is orthogonal to the variables Z0 , Z1 , Z2 that drive the lower bound. All the hard dynamics therefore live in the three-dimensional subspace with target ρZ0 . Dropping X⋆ and using the label ρZ0 would have a similar analysis, but then the whole label would have variance only ρ2 . Keeping X⋆ makes Var(Y ) = 1 + ρ2 ≤ 2. In this section, we will prove that this construction yields the following result. Theorem 3 (Lower bound). For every M ≥ 8 and D ≥ M 2 , there is an M -covered path instance with an exact global predictor whose coefficient ℓ1 norm is at most 3, each feature has second moment at most 2, and whose path predictor fD satisfies 1 M2 E[(Y − fD )2 ] ≥ . 1280π 2 D The common feature X⋆ is seen by every agent and is independent of everything else, so it is learned at once and the whole difficulty lives in the three-dimensional span of Z0 , Z1 , Z2 . For the rest of this section, we call the remaining part the hard part. We call the features Xj the hard features and Y − X⋆ the hard label. We track the error Et of the path in this hard part and prove two facts about it: it starts at a constant fraction of ρ2 (Lemma 26), and each later agent removes at most an O(ρ2 sin2 δ) fraction of it, that is Et+1 ≥ (1 − O(ρ2 sin2 δ))Et (Lemma 27). With the choice ρ2 = Θ(1/(D sin2 δ)) the per-step factor is 1 − Θ(1/D), so a constant fraction of the error survives all D steps, leaving ED = Ω(ρ2 ) = Ω(M 2 /D). 18

We now set up the hard part. After subtracting the common feature, everything that remains lives in the span of Z0 , Z1 , Z2 . These are independent standard Gaussians, hence orthonormal, so every hard predictor and residual is determined by its coefficient vector in R3 . Let e0 , e1 , e2 be the coefficient vectors of Z0 , Z1 , Z2 , that is the standard basis of R3 , and set u(θ) = cos θ e0 + sin θ e2 ,

x(θ) = e1 + ρu(θ).

The hard label Y − X⋆ = ρZ0 has coefficient vector ρe0 , and the hard feature Xj has coefficient vector x(jδ). Agent At sees X(t−1) mod M , so the feature direction u(θ) rotates by δ from one agent to the next. Let ybth ∈ R3 be the coefficient vector of the hard prediction after t agents, and define the residual, hard error, and st by Et (11) Rt := ρe0 − ybth , Et := ∥Rt ∥22 , st := 1 − 2 . ρ In contrast to Section 4 where Rt was a scalar, here Rt is a vector in R3 . The hard prediction at agent At is h the least-squares projection of ρe0 onto the span of ybt−1 and x((t − 1)δ) in R3 . By Lemma 3, Rt is orthogonal h h to the fitted span, hence to ybt . Pythagoras on ρe0 = ybt + Rt then gives ∥b yth ∥22 + Et = ρ2 , equivalently √ √ ∥Rt ∥2 = ρ 1 − st . (12) ∥b yth ∥2 = ρ st , In particular st ∈ [0, 1]. We analyze the starting error at the second agent. This agent sees x(δ), and the prediction of the first agent, which sees x(0). We will show that the prediction of the first agent is a nonzero multiple of x(0), so the second agent sees x(0) too. We analyze the error of the best predictor to these two features in the following lemma. Lemma 26. After the first two hard features, ρ2

E2 =

. 1 + ρ2 + tan2 (δ/2)

s2 =

ρ2 + tan2 (δ/2) . 1 + ρ2 + tan2 (δ/2)

Also,

Proof. Agent A1 sees x(0), and its prediction is a nonzero multiple of x(0), because otherwise R1 = ρe0 and R1 must be orthogonal to x(0), but is not. Agent A2 sees that prediction together with x(δ), so by Lemma 3 it projects ρe0 onto the plane spanned by x(0) and x(δ). Thus E2 is the squared distance from ρe0 to that plane. p The two features have length 1 + ρ2 , so the sum g = x(0) + x(δ) and difference d = x(δ) − x(0) are orthogonal, ⟨g, d⟩ = ∥x(δ)∥22 −∥x(0)∥22 = 0, and give an orthogonal basis of the plane. Using ⟨e0 , u(θ)⟩ = cos θ, ⟨ρe0 , g⟩ = ρ2 (1 + cos δ),

∥g∥22 = 4 + 2ρ2 (1 + cos δ),

⟨ρe0 , d⟩ = −ρ2 (1 − cos δ),

∥d∥22 = 2ρ2 (1 − cos δ).

The distance is ρe0 minus its projections onto g and d. Substituting the four quantities above, simplifying each fraction, and combining over a common denominator, ⟨ρe0 , g⟩2 ⟨ρe0 , d⟩2 − ∥g∥22 ∥d∥22 2 2 ρ (1 + cos δ) [ 2 + ρ (1 + cos δ) ] − ρ4 (1 + cos δ)2 = 2 [ 2 + ρ2 (1 + cos δ) ] 2 ρ (1 + cos δ) = 2 + ρ2 (1 + cos δ)

E2 = ∥ρe0 ∥22 −

Rewrite using 1 + cos δ = 2 cos2 (δ/2) then divide top and bottom by cos2 (δ/2) and use 1/ cos2 (δ/2) = 1 + tan2 (δ/2), =

ρ2 cos2 (δ/2) ρ2 . = 1 + ρ2 cos2 (δ/2) 1 + ρ2 + tan2 (δ/2)

Finally, using s2 = 1 − E2 /ρ2 from the setup, s2 = 1 −

E2 1 ρ2 + tan2 (δ/2) = 1 − = . ρ2 1 + ρ2 + tan2 (δ/2) 1 + ρ2 + tan2 (δ/2)

The heart of the construction is that, from the third agent on, one agent barely helps. The residual Rt is already orthogonal to the feature x(θ) that agent At just saw. The next feature x(θ + δ) differs from x(θ) only by a vector of length 2ρ sin(δ/2), so it too is nearly orthogonal to Rt , and a least-squares step along a direction nearly orthogonal to the residual removes almost none of it. Lemma 27 (One slow step). Suppose M ≥ 8 and 0 < ρ ≤ 1/8. For every t ≥ 2, Et+1 ≥ (1 − 40ρ2 sin2 δ)Et . Having the above lemma, we can prove Theorem 3. Proof of Theorem 3. First check the global predictor. Around the full circle, M −1 X

cos(jδ) = 0,

j=0

M −1 X

cos(jδ) sin(jδ) = 0,

j=0

cos2 (jδ) =

j=0

Hence

M . 2

M −1

Y = X⋆ +

2 X cos(jδ)Xj . M j=0

This predictor is exact, and its coefficient ℓ1 norm is at most 1 + (2/M )

j | cos(jδ)| ≤ 3.

We also need ρ to be small enough for Lemma 27. Since δ ≤ π/4, the bound sin x ≥ 2x/π on [0, π/2] gives sin δ ≥ 4/M . Since D ≥ M 2 , 1 D sin2 δ ≥ 16, ρ2 ≤ . 1280 Thus ρ ≤ 1/8, and the feature second moments are E[X⋆2 ] = 1 and E[Xj2 ] = 1 + ρ2 ≤ 2. The common feature X⋆ is independent of the hard variables and is available at every agent. Therefore the full prediction is X⋆ plus the hard prediction. Lemma 27 and the choice of ρ give 2

D−2

ED ≥ E2 (1 − 40ρ sin δ)

= E2

1 1− 2D

D−2 .

By Bernoulli’s inequality, (1 − 1/(2D))D−2 ≥ 1 − (D − 2)/(2D) ≥ 1/2. Also tan(δ/2) = tan(π/M ) ≤ tan(π/8) < 1/2 and ρ2 ≤ 1/1280, so Lemma 26 gives E2 ≥ ρ2 /2. Hence ED ≥

ρ2 1 M2 = ≥ . 4 1280π 2 D 320D sin2 (2π/M )

Since the global predictor is exact, MSE(f ⋆ ) = 0 and X⋆ is learned with no error, so this hard-part error ED equals the excess error MSE(fD ) − MSE(f ⋆ ) at agent AD . Setting D = M 2 directly shows Corollary 1.

Corollary 1 (Constant error before quadratic depth). For every integer M ≥ 8, there is an M -covered path instance of depth M 2 with an exact global predictor, coefficient ℓ1 norm at most 3, and feature second moments at most 2, such that, if Et is the excess error after the first t agents, then Et ≥

1 1280π 2

(1 ≤ t ≤ M 2 ).

Proof. Apply Theorem 3 with target depth D = M 2 . By Lemma 2, Et is non-increasing along the path. Thus, for every 1 ≤ t ≤ M 2 , Et ≥ EM 2 ≥ 1/(1280π 2 ).

5.2

Proof of Lemma 27

The residual Rt is orthogonal to the feature x(θ) = x((t − 1)δ) that agent At just saw, and the next feature x(θ + δ) differs from x(θ) by a vector of length only 2ρ sin(δ/2). So x(θ + δ) is also nearly orthogonal to Rt , and the least-squares step on it removes only an O(ρ2 sin2 (δ/2)) fraction of Et . Three lemmas formalize this. Lemma 28 sets up an orthonormal basis based on the prediction and residual of agent At , and Lemmas 29 and 30 supply some bounds in that basis. We combine these lemmas in the proof of Lemma 27. Lemma 28 (Setup). Fix t ≥ 2 and assume Et > 0. Set θ = (t − 1)δ and define m :=

ybth , ∥b yth ∥2

n :=

Rt ; ∥Rt ∥2

write n = (n0 , n1 , n2 ) in the basis e0 , e1 , e2 , and set h :=

(0, n2 , −n1 ) . √ st

Then {m, n, h} is an orthonormal basis of R3 , and there exist unique real numbers a, b with x(θ) = a m + b h. Define P (z) = z − ⟨z, m⟩m. Setting B = |b|, B = ∥P (x(θ))∥2 ,

B 2 = 1 + ρ2 −

ρ2 cos2 θ . st

Proof. Lemma 3 applied to agent At gives that Rt is orthogonal to both ybth and x(θ). The error is nonincreasing along the path (Lemma 2), so Et ≤ E2 , hence st ≥ s2 ; and s2 > 0 by Lemma 26. Combined with the assumption Et > 0, this gives 0 < st < 1, so the denominators in the definitions of m, n, h are nonzero. Using Equation (12), the identity ρe0 = ybth + Rt rewrites as √ √ e0 = st m + 1 − st n. The vectors m and n are perpendicular unit vectors orthogonal to ybth . Taking inner product of √ since Rt is 2 the previous identity with n gives n0 = ⟨e0 , n⟩ = 1 − st , so n1 + n22 = 1 − n20 = st . p √ For h: ∥h∥2 = n21 + n22 / st = 1; ⟨h, n⟩ = 0 by direct check; ⟨h, e0 ⟩ = 0 since h has zero first coordinate; and ⟨h, m⟩ = 0 since m ∈ span{e0 , n} by the previous identity. Hence {m, n, h} is orthonormal. Since Rt is orthogonal to x(θ), the vector x(θ) has no n-component, so x(θ) = a m + b h for unique real a, b, and P (x(θ)) = b h, giving B = |b| = ∥P (x(θ))∥2 . From ∥x(θ)∥22 = 1 + ρ2 and orthonormality of {m, h}, √ a2 + B 2 = 1 + ρ2 . Computing ⟨b yth , x(θ)⟩ in two ways, using ybth = ρ st m on the left, and on the right that Rt is orthogonal to x(θ) together with ⟨e0 , x(θ)⟩ = ρ cos θ, √ ρ st a = ⟨b yth , x(θ)⟩ = ⟨ρe0 , x(θ)⟩ = ρ2 cos θ. √ Therefore a = ρ cos θ/ st , and substituting into a2 + B 2 = 1 + ρ2 gives B 2 = 1 + ρ2 − ρ2 cos2 θ/st .

Throughout the rest of this subsection, we use the notation of Lemma 28. Lemma 29 (Two lower bounds on B). B ≥ sin(δ/2) and B ≥ | sin θ|. Proof. The error is non-increasing along the path (Lemma 2), so st ≥ s2 , and Lemma 26 gives s2 = For the first bound, st ≥ s2 yields

ρ2 + tan2 (δ/2) . 1 + ρ2 + tan2 (δ/2)

1 1 + ρ2 + tan2 (δ/2) . ≤ st ρ2 + tan2 (δ/2)

Plugging into the formula for B 2 gives B 2 ≥ 1 + ρ2 − ρ2 cos2 θ

1 + ρ2 + tan2 (δ/2) , ρ2 + tan2 (δ/2)

and combining over the common denominator ρ2 + tan2 (δ/2) (using cos2 θ = 1 − sin2 θ), B2 ≥

tan2 (δ/2) + ρ2 (1 + ρ2 + tan2 (δ/2)) sin2 θ tan2 (δ/2) ≥ . ρ2 + tan2 (δ/2) ρ2 + tan2 (δ/2)

For M ≥ 8 we have tan(δ/2) ≤ tan(π/8) < 1/2, and with ρ ≤ 1/8 this gives ρ2 + tan2 (δ/2) < 1. Hence B ≥ tan(δ/2) ≥ sin(δ/2). For the second bound, rewrite the formula for B 2 as ρ2 B 2 − sin2 θ = ρ2 + cos2 θ 1 − . st If st ≥ ρ2 , the right side is nonnegative. Otherwise the bracket is negative, and cos2 θ ≤ 1 gives B 2 − sin2 θ ≥ 1 + ρ2 − ρ2 /st . The formula for s2 gives s2 −

tan2 (δ/2) ρ2 = ≥ 0, 2 2 1+ρ (1 + ρ )(1 + ρ2 + tan2 (δ/2))

so st ≥ s2 ≥ ρ2 /(1 + ρ2 ), that is ρ2 /st ≤ 1 + ρ2 , and the last lower bound is again nonnegative. In either case | sin θ| ≤ B. Lemma 30 (Numerator bound). |⟨n, x(θ + δ)⟩| ≤ 8ρ sin(δ/2) B. Proof. We use both bounds from Lemma 29: sin(δ/2) ≤ B and | sin θ| ≤ B. The orthogonality ⟨n, x(θ)⟩ = 0 follows from n = Rt /∥Rt ∥2 and the fact that Rt is orthogonal to x(θ) (Lemma 3). The plan is to use this orthogonality together with the fact that the two features differ only by a short vector, so we just need to control how n pairs with that short vector. Expanding ⟨n, x(θ)⟩ = 0 with x(θ) = e1 + ρ(cos θ e0 + sin θ e2 ), n1 = −ρ(n0 cos θ + n2 sin θ). √ √ We first bound |n2 |. The identity b = ⟨x(θ), h⟩ together with ⟨e1 , h⟩ = n2 / st and ⟨e2 , h⟩ = −n1 / st gives √ b = (n2 − ρn1 sin θ)/ st ; substituting the formula for n1 , √ B st = n2 (1 + ρ2 sin2 θ) + ρ2 n0 sin θ cos θ . √ By the triangle inequality, |n0 | ≤ 1, | cos θ| ≤ 1, and st ≤ 1, the previous display gives |n2 |(1 + ρ2 sin2 θ) ≤ B + ρ2 | sin θ|. Dividing by 1 + ρ2 sin2 θ ≥ 1 and using | sin θ| ≤ B and ρ2 ≤ 1/64, 3 |n2 | ≤ B + ρ2 | sin θ| ≤ 65 64 B < 2 B.

Now define v(ϕ) = − sin ϕ e0 + cos ϕ e2 , a unit vector orthogonal to u(ϕ). Standard angle-addition identities give u(ϕ + α) − u(ϕ) = 2 sin(α/2) v(ϕ + α/2), v(ϕ + α) = cos α v(ϕ) − sin α u(ϕ). The first identity at ϕ = θ, α = δ gives x(θ + δ) − x(θ) = 2ρ sin(δ/2) v(θ + δ/2). We bound |⟨n, v(θ + δ/2)⟩| in two steps. First, by the triangle inequality and |n0 |, | cos θ| ≤ 1, |⟨n, v(θ)⟩| = | − n0 sin θ + n2 cos θ| ≤ | sin θ| + |n2 | ≤ B + 32 B < 3B. Second, the second angle-addition identity at ϕ = θ, α = δ/2 expands the inner product as ⟨n, v(θ + δ/2)⟩ = cos(δ/2) ⟨n, v(θ)⟩ − sin(δ/2) ⟨n, u(θ)⟩. Taking absolute values and using the bound |⟨n, v(θ)⟩| < 3B from above, |⟨n, u(θ)⟩| ≤ ∥n∥2 ∥u(θ)∥2 = 1 by Cauchy–Schwarz, and sin(δ/2) ≤ B from Lemma 29, |⟨n, v(θ + δ/2)⟩| ≤ cos(δ/2) · 3B + sin(δ/2) · 1 ≤ 3B + B = 4B. Combining and using ⟨n, x(θ)⟩ = 0, |⟨n, x(θ + δ)⟩| = |⟨n, x(θ + δ) − x(θ)⟩| = 2ρ sin(δ/2) |⟨n, v(θ + δ/2)⟩| ≤ 8ρ sin(δ/2) B. We are finally ready to prove Lemma 27. Proof of Lemma 27. If Et = 0, the error is non-increasing along the path (Lemma 2), so Et+1 ≤ Et = 0 and the conclusion holds trivially. Assume Et > 0, and adopt the notation of Lemma 28. We first derive a per-step ratio for the relative error reduction, then plug in the two lemmas above and a denominator bound. By Lemma 3, agent At+1 projects ρe0 onto V = span{b yth , x(θ + δ)} = span{m, x(θ + δ)}. This projection is the point of V closest to ρe0 , so Et+1 is the squared distance from ρe0 to V . Since ρe0 = ybth + Rt with ybth along m and Rt orthogonal to m, the vector ybth is already the projection of ρe0 onto the line span{m} ⊆ V , with leftover Rt . Let w := P (x(θ + δ))/∥P (x(θ + δ))∥2 , the part of x(θ + δ) orthogonal to m, normalized. If P (x(θ + δ)) = 0, then V = span{m}, the projection is unchanged, and Et+1 = Et , so the claim holds. Otherwise {m, w} is an orthonormal basis of V , so enlarging the line span{m} to V removes the component of the leftover Rt along w: the projection of ρe0 onto V is ybth + ⟨Rt , w⟩ w, leaving residual Rt − ⟨Rt , w⟩ w. By Pythagoras, Et+1 = Et − ⟨Rt , w⟩2 . Because w is orthogonal to m, projecting x(θ + δ) off m does √ not change its inner product with Rt , so ⟨Rt , w⟩ = ⟨Rt , x(θ + δ)⟩/∥P (x(θ + δ))∥2 . Substituting Rt = Et n and dividing by Et , Et − Et+1 ⟨n, x(θ + δ)⟩2 = . Et ∥P (x(θ + δ))∥22 Lemma 30 bounds the numerator. For the denominator, linearity of P gives P (x(θ +δ)) = P (x(θ))+P (x(θ + δ) − x(θ)), so the reverse triangle inequality and the fact that P does not increase length (since m is a unit vector, ∥z∥22 = ⟨z, m⟩2 + ∥P (z)∥22 by Pythagoras, so ∥P (z)∥2 ≤ ∥z∥2 ) give ∥P (x(θ + δ))∥2 ≥ ∥P (x(θ))∥2 − ∥x(θ + δ) − x(θ)∥2 = B − 2ρ sin(δ/2) ≥ B − 2ρB ≥ 34 B, using Lemma 29 (sin(δ/2) ≤ B) and ρ ≤ 1/8. Substituting both bounds, Et − Et+1 (8ρ sin(δ/2)B)2 1024 2 2 ≤ = ρ sin (δ/2). Et 9 ( 34 B)2 For M ≥ 8, cos2 (δ/2) ≥ cos2 (π/8) > 3/4, so sin2 (δ/2) = sin2 δ/(4 cos2 (δ/2)) ≤ sin2 δ/3. The relative error reduction is therefore at most (1024/27)ρ2 sin2 δ < 40ρ2 sin2 δ, and Et+1 ≥ (1 − 40ρ2 sin2 δ)Et . 23

5.3

The Fixed-Distribution Obstruction

The radius ρ in the construction above shrinks with D, which means that the distribution we introduce depends on D. This is not an artifact of the proof and we will show that the hard distribution must move with the depth. Theorem 4 (No fixed distribution for all depths). Fix M and a distribution D on (x1 , . . . , xd , Y ). Assume x1 , . . . , xd , Y have bounded second moments. For every c > 0, there is a depth Dc such that for any DAG of agents on D, if A1 → · · · → AD is an M -covered path in it with D ≥ Dc , then ED < c

M2 , D

where ED is the excess error of agent AD . Proof. This follows from a geometric convergence bound for fixed distributions, Theorem 5 below, which gives some q ∈ [0, 1) with ED ≤ E1 q ⌊(D−1)/M ⌋ . The base error is bounded by a constant of D alone, since the zero predictor is feasible for A1 and so E1 ≤ MSE(f1 ) ≤ E[Y 2 ]. Fix c > 0. Because q < 1, we have E[Y 2 ] Dq ⌊(D−1)/M ⌋ → 0 as D → ∞, so there is a Dc , depending only on D, M , and c, with E[Y 2 ] Dq ⌊(D−1)/M ⌋ < cM 2 for all D ≥ Dc . Then ED ≤ E[Y 2 ]q ⌊(D−1)/M ⌋ < cM 2 /D. We state the following two auxiliary lemmas. Both are slightly more general than needed in this section. This is because we will also use them later for the analogous results for the binary classification model. Lemma 31. Let H be a finite-dimensional space of random variables with the inner product ⟨U, W ⟩ = E[U W ], and let V1 , . . . , VM ⊆ H be subspaces with V1 + · · · + VM = H. Write PVi for the orthogonal projection onto Vi . Then there is a constant λ > 0, depending only on V1 , . . . , VM , such that M X

∥PVi (u)∥22 ≥ λ∥u∥22

for every u ∈ H.

i=1

PM Proof. The map u 7→ i=1 ∥PVi (u)∥22 is continuous on H and strictly positive on the unit sphere of H: if it vanished at a unit vector u, then u would be orthogonal to every Vi , hence to V1 + · · · + VM = H by coverage, forcing u = 0. Since H is finite-dimensional, its unit sphere is compact, so the map attains a minimum λ > 0 on it. Scaling by ∥u∥2 gives the stated bound for every u ∈ H. The second lemma is the geometric core of the block contraction. Along a block of agents, agent i fits the features spanning Vi , so its residual ends up orthogonal to Vi ; and when the loss barely drops over the block, consecutive residuals barely move. The lemma says that M -coverage then forces the part of the starting residual that lies in H to be small. Lemma 32 (Coverage bounds the starting residual). Let H, V1 , . . . , VM , and λ be as in Lemma 31, and write PH for the orthogonal projection onto H. Let r0 , r1 , . . . , rM be random variables with finite second moments such that PVi (ri ) = 0 for every 1 ≤ i ≤ M . Then λ∥PH (r0 )∥22 ≤ 2(M 2 + 1)

M X

∥ri − ri−1 ∥22 .

i=1

PM Proof. Write ∆ = i=1 ∥ri − ri−1 ∥22 . The plan is to bound the projections PVi (ri−1 ) from above by the steps, to bound them from below through PVi (r0 ), and to apply the coverage bound of Lemma 31 to PH (r0 ). For the upper bound, PVi (ri ) = 0 gives PVi (ri−1 ) = PVi (ri−1 −ri ), and orthogonal projections do not increase norm, so M M X X 2 ∥PVi (ri−1 )∥2 ≤ ∥ri−1 − ri ∥22 = ∆. i=1

i=1

For the lower bound, split PVi (ri−1 ) = PVi (r0 ) + PVi (ri−1 − r0 ), and write a = PVi (r0 ) and b = PVi (ri−1 − r0 ) for the two terms. Expanding the square, ∥PVi (ri−1 )∥22 = ∥a + b∥22 = ∥a∥22 + 2⟨a, b⟩ + ∥b∥22 . The cross term 2⟨a, b⟩ has no definite sign, so we bound it from below. Young’s inequality, in the form 2|⟨a, b⟩| ≤ 21 ∥a∥22 + 2∥b∥22 , gives 2⟨a, b⟩ ≥ − 12 ∥a∥22 − 2∥b∥22 . Substituting and collecting the ∥b∥22 terms, ∥PVi (ri−1 )∥22 ≥ ∥a∥22 − 12 ∥a∥22 − 2∥b∥22 + ∥b∥22 = 21 ∥a∥22 − ∥b∥22 . Since PVi does not increase norm, ∥b∥2 ≤ ∥ri−1 − r0 ∥2 . The drift ri−1 − r0 telescopes over the steps, so the triangle inequality and Cauchy–Schwarz across i − 1 ≤ M terms give ∥ri−1 − r0 ∥22 =

i−1 X

(rj − rj−1 )

j=1

≤ (i − 1) 2

i−1 X

∥rj − rj−1 ∥22 ≤ M ∆.

j=1

Putting a and b back and summing over i, M X

∥PVi (ri−1 )∥22 ≥ 12

M X

∥PVi (r0 )∥22 − M 2 ∆.

i=1

Each Vi ⊆ H, so projecting onto Vi factors through H: PVi (r0 ) = PVi (PH (r0 )). Applying Lemma 31 to PM PM PH (r0 ) ∈ H then gives i=1 ∥PVi (r0 )∥22 ≥ λ∥PH (r0 )∥22 . Combining the two bounds on i=1 ∥PVi (ri−1 )∥22 , 2 2 λ 2 ∥PH (r0 )∥2 − M ∆ ≤ ∆,

which rearranges to the claim. To show Theorem 5, we will first state the following intermediate lemma. Consider a fixed distribution and a path A1 → · · · → AM of agents on that distribution, in some network SM that may contain other agents too. Suppose agent Ai sees the raw features Si ⊆ [d] and assume that i=1 Si = [d]. We will show that there exists a constant q ∈ [0, 1) such that the excess error of the last agent is at most q times the excess error of the first agent. We will further show that this q does not depend on the rest of the network and only depends on S1 , . . . , SM . We formalize this in the following lemma. Lemma 33 (Per-block contraction). Fix a distribution D on (x1 , . . . , xd , Y ). Assume x1 , . . . , xd , Y have bounded second moments. Consider a path A1 → · · · → AM of agents on D in any DAG, with feature subsets SM S1 , . . . , SM ⊆ [d] satisfying i=1 Si = [d]. Suppose A0 is any agent in the DAG with an edge A0 → A1 . Let Et be the excess error of agent At for t = 0, 1, . . . , M . There is a constant q ∈ [0, 1), depending only on D and (S1 , . . . , SM ), such that EM ≤ q E0 . Proof. Let H = span{x1 , . . . , xd }. For a subspace V ⊆ H, PV denotes the orthogonal projection onto V . Write Vi = span{xℓ : ℓ ∈ Si }, rt = f ⋆ − ft , ∆ = E0 − EM . Here rt is the residual of At against the global predictor, and ∆ is the drop of the excess error over the block. Every agent’s prediction is a linear combination of inputs in H, so by induction over the DAG it lies in H; in particular rt ∈ H. Lemma 3 applied to the global predictor f ⋆ gives E[u(f ⋆ − Y )] = 0 for every u ∈ H, so Et = MSE(ft ) − MSE(f ⋆ ) = E[(ft − f ⋆ )2 ] + 2E[(ft − f ⋆ )(f ⋆ − Y )] = ∥rt ∥22 , where the second term vanishes by applying the orthogonality to u = ft − f ⋆ . 25

We check the hypotheses of Lemma 32 for r0 , . . . , rM . First, by Lemma 3, the residuals Y − fi and Y − f ⋆ are orthogonal to every v ∈ Vi . Subtracting the two orthogonality relations shows that ri = f ⋆ − fi is orthogonal to Vi , that is PVi (ri ) = 0. Second, Equation (3) of Lemma 2 controls the steps: ∥ri − ri−1 ∥22 = ∥fi − fi−1 ∥22 = Ei−1 − Ei , so summing telescopes to M X

∥ri − ri−1 ∥22 = E0 − EM = ∆.

i=1

By coverage, V1 + · · · + VM = H, so Lemma 31 gives a constant λ > 0 depending only on D and (S1 , . . . , SM ), and Lemma 32 applies. Since r0 ∈ H, we have PH (r0 ) = r0 and ∥r0 ∥22 = E0 , so its conclusion reads λE0 ≤ 2(M 2 + 1)∆. Hence λ E0 , EM = E0 − ∆ ≤ 1 − 2(M 2 + 1) and q := 1 − λ/(2(M 2 + 1)) ∈ [0, 1) depends only on D and (S1 , . . . , SM ). There are only finitely many possible tuples (S1 , . . . , SM ) in the lemma above. Thus, we can take the maximum over all tuples to obtain a global contraction factor. Theorem 5 (Fixed-distribution geometric convergence). Fix M and a distribution D on (x1 , . . . , xd , Y ) with d finite. Assume x1 , . . . , xd , Y have bounded second moments. There is a constant q ∈ [0, 1), depending only on D and M , such that for any DAG of agents on D, if A1 → · · · → AD is an M -covered path in it, then for any 1 ≤ s ≤ D − M , Es+M ≤ qEs , where Et is the excess error of agent At . Consequently, ED ≤ E1 q ⌊(D−1)/M ⌋ . Proof. Fix s with 1 ≤ s ≤ D − M . The sub-path As+1 → · · · → As+M is a block of M consecutive agents on the original path, so its feature subsets cover [d] by M -coverage, and its first agent has the on-path predecessor As . Apply Lemma 33 to this sub-path with starting predictor fs : there is q(Ss+1 , . . . , Ss+M ) ∈ [0, 1), depending only on D and (Ss+1 , . . . , Ss+M ), with Es+M ≤ q(Ss+1 , . . . , Ss+M ) Es . The tuple (Ss+1 , . . . , Ss+M ) takes at most 2dM values, so q = max q(Ss+1 , . . . , Ss+M ) ∈ [0, 1) over the finitely many feasible tuples; q depends only on D and M , and Es+M ≤ q Es for every s with 1 ≤ s ≤ D − M . By Equation (3) of Lemma 2, Et is non-increasing along the path. Iterating the per-block contraction from s = 1 over ⌊(D − 1)/M ⌋ full blocks and using monotonicity over the remaining steps gives ED ≤ E1 q ⌊(D−1)/M ⌋ .

Classification Results

We now state the matching results for binary classification. The protocol is the logit-passing protocol from the preliminaries. For the upper bound,√we use the same idea as in Theorem 1 to give a O(M 2 /D) upper bound, which improves upon the O(M/ D) bound from Bateni et al. [BHH+26]. For the lower bounds, we prove a Gaussian transfer result, which allows us to transfer the results directly from the regression model into classification. This includes a tighter analysis of the cyclic example (previously done by Bateni et al. [BHH+26]), and a Ω(M 2 /D) lower bound when D ≥ M 2 along with a constant lower bound for D < M 2 . The latter example still depends on D, so we show analogous results to Theorems 4 and 5.

6.1

Upper Bound

For the rest of this subsection, we assume the following conditions, which mirror those of the regression setting, and the ones used by Bateni et al. [BHH+26]: 26

• The global BCE minimizer z⋆ (x) =

ℓ |wℓ | ≤ B⋆ .

ℓ=1 wℓ xℓ satisfies

2 • Each feature satisfies E[x2ℓ ] ≤ BX .

• The protocol minimizers are attained at finite coefficients. Consider an M -covered path of agents A1 → A2 → · · · → An . By Lemma 5, the losses are non-increasing along the path, meaning that L(z1 ) ≥ L(z2 ) ≥ · · · ≥ L(zn ). As in the regression setting, if the loss does not decrease significantly over a block of agents that sees every feature, then the excess loss of the last agent in the block is small. The following lemma is the classification analogue of Lemma 8. Bateni et al. [BHH+26, Lemma 3.6] also shows a similar result. We provide the proof for completeness. Lemma 34. Consider any path A1 → A2 → · · · → An and a block of k consecutive agents indexed by [a + 1, b] that sees every raw feature at least once, where b = a + k. If ε ≥ L(za ) − L(zb ), then r kε . L(zb ) − L(z⋆ ) ≤ B⋆ BX 2 Proof. Fix a feature xℓ , and let agent Aj in the block see it. BCE orthogonality from Lemma 4 gives E[xℓ (σ(zj )−Y )] = 0. For consecutive agents on the path, Equation (7) gives ∥σ(zi )−σ(zi−1 )∥22 ≤ 12 (L(zi−1 )− L(zi )), so summing over the block, b X

∥σ(zi ) − σ(zi−1 )∥22 ≤

i=a+1

ε 1 L(za ) − L(zb ) ≤ . 2 2

Since agent Aj sees xℓ , its orthogonality E[xℓ (σ(zj ) − Y )] = 0 lets us replace the target Y with σ(zj ) in the following equation: E[xℓ (σ(zb ) − Y )] = E[xℓ (σ(zb ) − σ(zj ))] + E[xℓ (σ(zj ) − Y )] = E[xℓ (σ(zb ) − σ(zj ))]. Pb Write σ(zb )−σ(zj ) as σ(zb )−σ(zj ) = i=j+1 (σ(zi )−σ(zi−1 )). The sum has at most k terms, since j ≥ a+1 and b = a + k. The triangle inequality followed by Cauchy–Schwarz across these terms gives

∥σ(zb ) − σ(zj )∥2 ≤

b X

∥σ(zi ) − σ(zi−1 )∥2 ≤

i=j+1

√

 k

b X

1/2 ∥σ(zi ) − σ(zi−1 )∥22 

i=j+1

r ≤

kε , 2

Pb where the last step uses the bound i=a+1 ∥σ(zi ) − σ(zi−1 )∥22 ≤ ε/2 from above. A final Cauchy–Schwarz 2 , then yields over the feature, with E[x2ℓ ] ≤ BX r q kε |E[xℓ (σ(zb ) − Y )]| = |E[xℓ (σ(zb ) − σ(zj ))]| ≤ E[x2ℓ ] ∥σ(zb ) − σ(zj )∥2 ≤ BX . 2 The bound just derived holds for every feature ℓ, since the block sees each raw feature at least once. To turn these per-feature bounds into a loss bound, apply the comparator inequality of Lemma 6 with zg = z⋆ : since zb minimizes BCE over its inputs, L(zb ) − L(z⋆ ) ≤ |E[(σ(zb ) − Y )z⋆ ]|. Finally, expand z⋆ =

ℓ wℓ xℓ and use the per-feature bound together with

ℓ |wℓ | ≤ B⋆ ,

r |E[(σ(zb ) − Y )z⋆ ]| ≤

|wℓ | |E[xℓ (σ(zb ) − Y )]| ≤ B⋆ BX

ℓ

which gives L(zb ) − L(z⋆ ) ≤ B⋆ BX

kε/2.

kε , 2

We now state the classification analogue of Lemma 9. The proof for this lemma is almost identical to the proof of Lemma 9. Lemma 35 (A good suffix from a good prefix). Take an M -covered path A1 → A2 → · · · → An and an agent As on it with L(zs ) − L(z⋆ ) ≤ δ. Let L = n − s and consider the suffix As+1 → · · · → As+L . If L ≥ 2M , then r δ L(zn ) − L(z⋆ ) ≤ B⋆ BX M . L Proof. Split the suffix into K = ⌊L/M ⌋ full blocks. Since L ≥ 2M , K ≥ L/(2M ). The total loss drop over these blocks is at most L(zs ) − L(z⋆ ) ≤ δ, so by the pigeonhole principle, some block has drop ε ≤ δ/K ≤ 2M δ/L. Applying Lemma 34 on this block with k = M gives, at the end q of that block, r r M 2δ δ L(zq ) − L(z⋆ ) ≤ B⋆ BX = B⋆ BX M . L L By Lemma 5, the loss is non-increasing along the path, so L(zn ) ≤ L(zq ). Finally, we prove the upper bound theorem. Its proof is also almost identical to Theorem 1. Theorem 6 (Improved classification upper bound). For every depth D and every M -covered path, assume Pd P 2 the global BCE minimizer is z⋆ = ℓ=1 wℓ xℓ , that ℓ |wℓ | ≤ B⋆ , that E[x2ℓ ] ≤ BX for every feature, and that the protocol minimizers are attained at finite coefficients. Then L(zD ) − L(z⋆ ) ≤ C

M2 , D

where C depends only on B⋆ and BX . Proof. Set c⋆ = B⋆ BX , the constant of Lemma 35, and C = max{4 log 2, 6c2⋆ }. We prove that L(zD ) − L(z⋆ ) ≤ CM 2 /D for every M -covered path of depth D, arguing by induction on D. Since the loss is non-increasing along the path by Lemma 5 and BCE is nonnegative, L(zD ) − L(z⋆ ) ≤ L(zD ) ≤ L(z1 ) ≤ L(0) = log 2, using that the zero logit is feasible for the first agent. This establishes the bound for short paths: if D < 4M , then M 2 /D > M/4 ≥ 1/4, hence L(zD ) − L(z⋆ ) ≤ log 2 ≤

C M2 <C . 4 D

3CM 2 CM 2 ≤ =: δ. s D

The suffix has length L = D − s ≥ D/2 ≥ 2M , so Lemma 35 applies with this δ. Substituting δ = 3CM 2 /D and L ≥ D/2 then gives s r √ δ 3CM 2 /D M2 L(zD ) − L(z⋆ ) ≤ c⋆ M ≤ c⋆ M = c⋆ 6C . L D/2 D √ Finally, C ≥ 6c2⋆ implies c⋆ 6C ≤ C, so the right-hand side is at most CM 2 /D, which completes the induction.

6.2

Gaussian Transfer

Bateni et al. [BHH+26] show a lower bound of Ω(M/D) for the classification setting. They use the same cyclic example and apply σ to the label to obtain probabilities. Their analysis for this example does not directly use the regression bound. We instead take a shortcut. In this section, we show that any Gaussian instance from the regression setting has the same asymptotic error if the agents instead fit predictors for linear classification. The cyclic example given by Kearns, Roth, and Ryu [KRR26] and the example we provide in Section 5 are both Gaussian, so their bounds directly transfer to the classification setting. Lemma 36 (BCE loss and squared logit error). Let x1 , . . . , xd be centered jointly Gaussian variables and G = wT x be a linear combination of them. Let Y ∈ {0, 1} satisfy Pr(Y = 1 | x) = σ(G). If z is a linear combination of the features x, then 0 ≤ L(z) − L(G) ≤

1 E[(z − G)2 ]. 8

Moreover, for each 0 ≤ B < ∞ there is a constant κB > 0 such that, if E[G2 ], E[z 2 ] ≤ B, L(z) − L(G) ≥ κB E[(z − G)2 ]. Proof. Recall that ϕ(u) = log(1 + eu ), ϕ′ (u) = σ(u), and L(u) = E[ϕ(u) − Y u]. Since G and z are linear combinations of the centered Gaussian vector x, the pair (G, z) is centered jointly Gaussian. Also G and z are functions of x, so the assumption Pr(Y = 1 | x) = σ(G) gives E[Y | G, z] = σ(G) = ϕ′ (G). Hence E[Y (z − G)] = E[E[Y | G, z](z − G)] = E[ϕ′ (G)(z − G)]. Thus L(z) − L(G) = E[ϕ(z) − ϕ(G) − Y (z − G)] = E[ϕ(z) − ϕ(G) − ϕ′ (G)(z − G)]. For real numbers a and b, Taylor’s remainder formula gives some point ξ between a and b such that ϕ(b) − ϕ(a) − ϕ′ (a)(b − a) =

1 ′′ ϕ (ξ)(b − a)2 . 2

(13)

Also ϕ′′ (u) = σ(u)(1 − σ(u)), so 0 ≤ ϕ′′ (u) ≤ 1/4. Combining the above equalities with a = G and b = z gives 1 0 ≤ L(z) − L(G) ≤ E[(z − G)2 ]. 8 It remains to prove the lower bound under E[G2 ], E[z 2 ] ≤ B. If E[(z − G)2 ] = 0, then z = G almost surely and the claim is trivial. 2 Choose RB > 0 with RB ≥ 48B. By Chebyshev’s inequality, every centered random variable W with 2 E[W ] ≤ B satisfies Pr(|W | > RB ) ≤ 1/48. Define the event A = {|G| ≤ RB , |z| ≤ RB }. We first lower-bound the loss on A. For |u| ≤ RB ,

ϕ′′ (u) =

1 e−RB ≥ . 4 (eu/2 + e−u/2 )2

Here the last step uses eu/2 + e−u/2 ≤ 2eRB /2 . On A, the intermediate point of Equation (13) also lies in [−RB , RB ], so the equation gives ϕ(z) − ϕ(G) − ϕ′ (G)(z − G) ≥

1 −RB e (z − G)2 . 8

The same formula, namely the left-hand side of Equation (13), is nonnegative everywhere, so we can discard the contribution from Ac and get L(z) − L(G) ≥

1 −RB e E[(z − G)2 1 {A}]. 8 29

(14)

It remains to show that A contains a fixed fraction of E[(z − G)2 ]. Since (G, z) is centered jointly Gaussian, the difference z − G is centered Gaussian, and hence E[(z − G)4 ] = 3E[(z − G)2 ]2 . The choice of RB applies to both G and z. For an event E, Cauchy–Schwarz gives p E[(z − G)2 1 {E}] ≤ E[(z − G)4 ] Pr(E). Applying this with E = {|G| > RB } and then with E = {|z| > RB } gives p E[(z − G)2 1 {|G| > RB }] ≤ E[(z − G)4 ] Pr(|G| > RB ) p 1 ≤ 3E[(z − G)2 ]2 /48 = E[(z − G)2 ], 4 p E[(z − G)2 1 {|z| > RB }] ≤ E[(z − G)4 ] Pr(|z| > RB ) p 1 ≤ 3E[(z − G)2 ]2 /48 = E[(z − G)2 ]. 4 Since Ac = {|G| > RB } ∪ {|z| > RB }, E[(z − G)2 1 {A}] = E[(z − G)2 ] − E[(z − G)2 1 {Ac }] ≥ E[(z − G)2 ] − E[(z − G)2 1 {|G| > RB }] − E[(z − G)2 1 {|z| > RB }] 1 ≥ E[(z − G)2 ]. 2 Substituting this into Equation (14) gives 1 −RB e E[(z − G)2 1 {A}] 8 e−RB E[(z − G)2 ]. ≥ 16

L(z) − L(G) ≥

Thus the claim holds with κB = e−RB /16. We remark that the idea of restricting a Gaussian variable to a centered interval in order to bound the sigmoid function’s derivative also shows up in the proof of [BHH+26], though their reasoning considers a specific Gaussian variable. The next lemma shows that under the same Gaussian inputs, the BCE minimizer z and the least-squares minimizer f are proportional, z = cf . Similar proportionality results are known [Bri83; EDB16]. We include the proof for completeness and further show that c ∈ [0, 1]. Lemma 37 (Gaussian logistic regression keeps the least-squares direction). Let x1 , . . . , xd be centered jointly Gaussian variables and G = wT x be a linear combination of them. Let Y ∈ {0, 1} satisfy Pr(Y = 1 | x) = σ(G). Let u1 , . . . , uq be linear combinations of x. Let f be the linear least-squares minimizer for label G over u1 , . . . , uq , and let z be the BCE minimizer for label Y . Then z = cf for some c ∈ [0, 1], with c > 0 whenever f ̸= 0. Proof. Let V = span(u1 , . . . , uq ). By Lemma 3, applied with label G, f is the projection of G onto V , and the residual G − f is orthogonal to every element of V . First suppose f = 0. Since the residual G − f is orthogonal to V , G is independent of V . For any h ∈ V , the variable h is centered, and the symmetry of the centered Gaussian G gives E[σ(G)] = 1/2. Hence E[Y h] = E[σ(G)h] = E[σ(G)]E[h] = 0.

Thus L(h) = E[ϕ(h) − Y h] = E[ϕ(h)]. By Lemma 7, ϕ is strictly convex, so Jensen’s inequality gives E[ϕ(h)] ≥ ϕ(E[h]) = ϕ(0) = log 2 = L(0). Equality holds only when h = 0 almost surely, so the BCE minimizer is z = 0. Now suppose f ̸= 0. We first show that the BCE minimizer cannot use any direction orthogonal to f . Write z = cf + r, where r ∈ V is orthogonal to f . Since G − f is orthogonal to every element of V , the variable r is orthogonal to G − f . Since r is also orthogonal to f , it is orthogonal to G = (G − f ) + f . Joint Gaussianity then implies that r is independent of (G, f ). Also Pr(Y = 1 | G, f, r) = σ(G), so r is independent of Y after conditioning on (G, f ). Thus r is independent of (G, f, Y ) and remains centered after we condition on these variables. Therefore, Jensen gives E[ϕ(cf + r) − Y (cf + r) | G, f, Y ] ≥ ϕ(cf + E[r | G, f, Y ]) − Y cf = ϕ(cf ) − Y cf. Taking expectations shows that L(z) ≥ L(cf ). Since z is a minimizer and cf is feasible, equality must hold. Moreover, because ϕ is strictly convex, equality in Jensen can hold only if r is almost surely constant after conditioning on (G, f, Y ). But r is independent of (G, f, Y ) and centered, so this means r = 0 almost surely. Thus any finite BCE minimizer has the form z = cf . It remains to locate c. Recall that the residual G − f is independent of f . Define ψ(s) = E[σ(s + G − f )], with the expectation over the residual G − f . Along the scalar line, define F (a) = L(af ) = E[ϕ(af ) − σ(G)af ], and F ′ (a) = E[f (σ(af ) − ψ(f ))]. The function ψ is strictly increasing and ψ(0) = 1/2. Therefore, when f > 0, we have ψ(f ) > 1/2, and when f < 0, we have ψ(f ) < 1/2. In both cases, f (1/2 − ψ(f )) < 0 whenever f ̸= 0. Since f is not almost surely zero, taking expectations gives F ′ (0) = E[f (1/2 − ψ(f ))] < 0. Thus the loss decreases as we move to the right from 0. By Lemma 7, L is convex, so F is convex; thus no minimizer of F can lie at or to the left of 0. Since z = cf , this gives c > 0. We now show c ≤ 1. For s > 0 and every real n, 1 sinh s 1 sinh s σ(s + n) + σ(s − n) = + ≤ + = σ(s). 2 2 2(cosh s + cosh n) 2 2(cosh s + 1) The residual G − f is a centered Gaussian, so G − f and f − G have the same distribution. For s > 0, we can plug the random value G − f into the inequality above and take expectation: σ(s + G − f ) + σ(s + f − G) E ≤ σ(s). 2 Since G − f and f − G have the same distribution, the left side is E[σ(s + G − f )] = ψ(s). Thus ψ(s) ≤ σ(s) for s > 0. By symmetry, ψ(s) ≥ σ(s) for s < 0. Hence f (σ(f ) − ψ(f )) ≥ 0 for every value of f , and so F ′ (1) ≥ 0. Since F is convex, any minimizer of F is at most 1. Therefore c ∈ (0, 1], concluding the proof.

Theorem 7 (Gaussian transfer to classification). Let x1 , . . . , xd be centered jointly Gaussian variables and G = wT x be a linear combination of them. Let Y ∈ {0, 1} satisfy Pr(Y = 1 | x) = σ(G). Assume that Var(G) ≤ B. Let zt be the logit predictor of agent At . Assume the same network is used to predict G with least-squares loss. Let ft be the predictor of At , and let Et be the excess error in this network, i.e., Et = ∥G − ft ∥22 . Then, for all t, zt = ct ft for some ct ∈ [0, 1], with ct > 0 whenever ft ̸= 0. Furthermore, for a constant κB > 0 depending only on B, 1 κB Et ≤ L(zt ) − L(G) ≤ Et . 8 Proof. Suppose agents learn in order A1 , . . . , AN . We first prove the zt = ct ft part of the claim. Induct on t. For t = 1, agent A1 receives the same raw features in both the least-squares and classification settings. Thus Lemma 37 applies and proves the z1 = c1 f1 part of the claim with c1 ∈ [0, 1]. The same lemma gives c1 > 0 whenever f1 ̸= 0. Now fix t > 1 and assume the claim has been proved for all earlier agents. Let Vtls be the span of the raw features of At and the parent least-squares predictions fi for i ∈ Pa(t). Let Vtbce be the span of the same raw features and the parent logits zi for i ∈ Pa(t). By the induction hypothesis, zi = ci fi for each parent. If fi = 0, then zi = 0. If fi ̸= 0, then ci > 0, so zi spans the same line as fi . Thus Vtls = Vtbce ; call this common space Vt . The least-squares predictor ft minimizes squared loss over Vt , and the classification logit zt is the finite BCE minimizer over Vt . The raw features are coordinates of x, and the parent predictions are linear combinations of earlier inputs, so all elements of Vt are linear combinations of the Gaussian features x. Hence Lemma 37 applies and gives zt = ct ft for some ct ∈ [0, 1], with ct > 0 whenever ft ̸= 0. This completes the induction. It remains to compare the losses. Fix t. Again let Vt denote the span of the inputs of At . By Lemma 3, ft is the projection of G onto Vt , so G − ft is orthogonal to ft . Hence E[G2 ] = E[(ft + (G − ft ))2 ] = E[ft2 ] + 2E[ft (G − ft )] + E[(G − ft )2 ] = E[ft2 ] + E[(G − ft )2 ]. Thus E[ft2 ] ≤ E[G2 ]. Since zt = ct ft with ct ∈ [0, 1], and since G is centered, E[zt2 ] = c2t E[ft2 ] ≤ E[G2 ] = Var(G) ≤ B. The lower bound in Lemma 36 therefore applies to the pair (G, zt ). Also, zt ∈ Vt and ft is the projection of G onto Vt , so E[(G − zt )2 ] ≥ E[(G − ft )2 ] = Et . Thus L(zt ) − L(G) ≥ κB E[(G − zt )2 ] ≥ κB Et . For the upper bound, ft is a feasible logit for the BCE problem at agent At , because the two input spaces are the same. Since zt minimizes BCE over this space, L(zt ) ≤ L(ft ). Applying the upper bound in Lemma 36 to ft gives L(zt ) − L(G) ≤ L(ft ) − L(G) ≤

6.3

1 1 E[(G − ft )2 ] = Et . 8 8

Lower Bounds

We next apply the Gaussian transfer theorem to the regression cyclic and depth-dependent lower bounds. In both cases the true logit G is an exact linear combination of the features, and the label is drawn with conditional mean σ(G), so Theorem 7 applies. 32

Theorem 8 (Classification cyclic example lower bound). For every k ≥ 2, there is a k-covered Gaussian classification path instance with true logit G and Bernoulli labels with mean σ(G) such that, at the end of pass 1 ≤ p ≤ k − 1, κ1 L(zpk ) − L(G) ≥ √ . 48 p Equivalently, if D = pk, then κ1 L(zD ) − L(G) ≥ 48

k . D

√ Proof. The least-squares error after pass p is at least 1/(48 p) by Theorem 2. Here Var(G) = 1, so Theorem 7 gives the result. Theorem 9 (Classification depth-dependent lower bound). For every M ≥ 8 and D ≥ M 2 , there is an M covered Gaussian classification path instance of depth D with true logit G, Bernoulli labels with mean σ(G), and G an exact linear combination of the features whose coefficient ℓ1 norm is at most 3, with E[x2ℓ ] ≤ 2 for every feature, and with M2 L(zD ) − L(G) ≥ cld D for a universal constant cld > 0. Proof. Use the regression instance from Theorem 3, with the same Gaussian logit G = X⋆ +ρZ0 and Bernoulli mean σ(G). The coverage, exact predictor, coefficient bound, and second-moment bound are proved there. That theorem also gives 1 M2 ED ≥ 1280π 2 D for the matching least-squares path. In this construction Var(G) = 1 + ρ2 ≤ 2. Hence Theorem 7 gives the claim with cld = κ2 /(1280π 2 ). Corollary 2 (Classification constant loss before quadratic depth). There is a universal constant cquad > 0 such that, for every M ≥ 8, there is an M -covered Gaussian classification path instance of depth M 2 with true logit G an exact linear combination of the features whose coefficient ℓ1 norm is at most 3, with E[x2ℓ ] ≤ 2 for every feature, and with Bernoulli labels with mean σ(G) such that, for every 1 ≤ t ≤ M 2 , L(zt ) − L(G) ≥ cquad . Proof. Apply Theorem 9 with target depth D = M 2 . By Lemma 5, the loss is non-increasing along the path. Thus, for every 1 ≤ t ≤ M 2 , L(zt ) − L(G) ≥ L(zM 2 ) − L(G) ≥ cld . Take cquad = cld .

6.4

The Fixed-Distribution Obstruction

The depth-dependent lower bound in Section 5 used a distribution that changes with D, since the target radius ρ shrank with the depth. As in regression, we show that this is unavoidable. The argument parallels the regression proof of Lemma 33. Let H = span{x1 , . . . , xd }, which is finitedimensional. Every logit is a linear combination of raw features and parent logits, so every logit zt , along with the global BCE minimizer z⋆ , lies in H. The zero logit is always feasible, so L(zt ) ≤ L(0) = log 2 for every agent, so every predictor lies in the sublevel set K = {z ∈ H : L(z) ≤ L(0)}.

(15)

At agent At write Vt = span{xℓ : ℓ ∈ St } for the span of its raw features. The agent minimizes BCE over a space that contains Vt and other logits from Pa(t). We write Et = L(zt ) − L(z⋆ ) for the excess loss and consider a path that is M -covered. This means that every M consecutive raw-feature spans Vt sum to H.

The regression proof rested on the identity Et = ∥f ⋆ − ft ∥22 , which turns excess error into a squared distance. Cross-entropy is not a squared norm, but on the bounded set K it is strongly convex, and this lets us compare the excess loss with the squared logit distance to z⋆ . We record this comparison first and the block argument then follows the regression one. Lemma 38 (BCE excess loss and logit distance). Assume x1 , . . . , xd have bounded second moments. Suppose H ̸= {0}, the BCE minimum over H is attained at z⋆ , and L(0) > L(z⋆ ). Then K is compact, and there is a constant µ ∈ (0, 14 ], depending only on D, such that every z ∈ K satisfies E[(σ(z) − σ(z⋆ ))(z − z⋆ )] ≥ µ∥z − z⋆ ∥22

and

L(z) − L(z⋆ ) ≤ 18 ∥z − z⋆ ∥22 .

Proof. By Lemma 7, L is convex, and therefore K is convex. We first show K is compact. Since L is continuous, K is closed; as it lives in the finite-dimensional H, it is enough to bound it. The main step is a linear lower bound on L. Let η = E[Y | x1 , . . . , xd ], and for z ∈ H split z = z+ − z− with z+ = max{z, 0} and z− = max{−z, 0}. Each z ∈ H is a function of x, so E[Y z] = E[ηz], and ϕ(u) = log(1 + eu ) ≥ u+ gives L(z) = E[ϕ(z) − Y z] ≥ E[z+ − ηz] = E[(1 − η)z+ + ηz− ] =: r(z) ≥ 0. The functional r is continuous and positively homogeneous by definition: r(az) = a r(z) for a ≥ 0. We claim r(h) > 0 for every h ̸= 0. Suppose instead r(h) = 0. Its two terms are nonnegative, so (1−η)h+ = 0 and ηh− = 0 almost surely, meaning η = 1 where h > 0 and η = 0 where h < 0. Since z⋆ minimizes L over H and h ∈ H, Lemma 4 gives E[(σ(z⋆ ) − Y )h] = 0, and as h is a function of x this equals E[(σ(z⋆ ) − η)h]. But σ(z⋆ ) ∈ (0, 1), so σ(z⋆ ) − η < 0 where h > 0 and σ(z⋆ ) − η > 0 where h < 0; hence (σ(z⋆ ) − η)h < 0 on {h ̸= 0}, a set of positive probability, forcing E[(σ(z⋆ ) − η)h] < 0. This contradiction proves the claim. Thus r > 0 on the unit sphere of H, which is compact, so r ≥ ρ0 there for some ρ0 > 0. By homogeneity r(z) ≥ ρ0 ∥z∥2 for all z ∈ H, so L(z) ≥ ρ0 ∥z∥2 . Any z ∈ K then obeys ρ0 ∥z∥2 ≤ L(z) ≤ log 2, that is ∥z∥2 ≤ (log 2)/ρ0 . So K is closed and bounded in the finite-dimensional H, and therefore compact. Write σ ′ (w) = σ(w)(1 − σ(w)) ∈ (0, 14 ] for the derivative of the sigmoid. For w ∈ K and g ∈ H, the value E[σ ′ (w)g 2 ] is positive whenever g ̸= 0, and it varies continuously with (w, g) over the finite-dimensional space H × H. Since {(w, g) : w ∈ K, ∥g∥2 = 1} is compact, E[σ ′ (w)g 2 ] attains a positive minimum µ there, and µ ≤ 14 because σ ′ ≤ 14 . Scaling in g gives E[σ ′ (w)g 2 ] ≥ µ∥g∥22 for all w ∈ K and g ∈ H. Now fix z ∈ K and set g = z − z⋆ ; the segment from z⋆ to z stays in K, so z⋆ + θg ∈ RK for 0 ≤ θ ≤ 1. 1 The fundamental theorem of calculus, applied to θ 7→ σ(z⋆ + θg), gives σ(z) − σ(z⋆ ) = 0 σ ′ (z⋆ + θg) g dθ pointwise. Multiplying by g makes the integrand nonnegative, so expectation and integral exchange, and Z 1 E[(σ(z) − σ(z⋆ ))(z − z⋆ )] = E[σ ′ (z⋆ + θg)g 2 ] dθ ≥ µ∥g∥22 , 0 ′

since each z⋆ + θg ∈ K gives E[σ (z⋆ + θg)g ] ≥ µ∥g∥22 . For the second bound, z⋆ minimizes L over H ∋ g, so Lemma 4 gives E[(σ(z⋆ ) − Y )g] = 0. Writing ϕ(u) = log(1 + eu ), so ϕ′ = σ and ϕ′′ = σ ′ , this replaces Y by ϕ′ (z⋆ ) in the loss gap: L(z) − L(z⋆ ) = E[ϕ(z) − ϕ(z⋆ ) − ϕ′ (z⋆ )g]. Applying the second-order Taylor remainder as in Equation (13) with a = z⋆ and b = z writes the integrand as 21 ϕ′′ (ξ)g 2 for some ξ between z⋆ and z, and ϕ′′ = σ ′ ≤ 41 gives L(z) − L(z⋆ ) ≤ 18 ∥g∥22 . With this comparison in hand, the block contraction again rests on Lemma 32, now applied to the probability residual σ(zt ) − σ(z⋆ ) in place of the regression residual f ⋆ − ft . Lemma 39 (Per-block contraction). Fix a distribution D on (x1 , . . . , xd , Y ) with Y ∈ {0, 1}, d finite, and BCE minimum over H attained at z⋆ . Assume x1 , . . . , xd have bounded second moments. Consider a path A0 → A1 → · · · → AM of agents on D in any DAG, with raw-feature spans V1 , . . . , VM satisfying V1 + · · · + VM = H. There is a constant q ∈ [0, 1), depending only on D and (S1 , . . . , SM ), such that EM ≤ q E0 . 34

Proof. If E0 = 0, the loss is non-increasing along the path, so EM ≤ E0 = 0 and any q works. If H = {0} or L(0) = L(z⋆ ), every logit already minimizes and all Et = 0. So assume E0 > 0, H ̸= {0}, and L(0) > L(z⋆ ), and let µ be the constant of Lemma 38. Write pt = σ(zt ), p⋆ = σ(z⋆ ), and set rt = pt − p⋆ ,

∆ = E0 − EM ,

the probability residual of At and the loss drop over the block. For a subspace V , let PV be the orthogonal projection onto V . We check the hypotheses of Lemma 32 for r0 , . . . , rM . The residual ri is orthogonal to the block features: both zi and z⋆ minimize BCE over a space containing Vi , so Lemma 4 gives E[(pi − Y )v] = E[(p⋆ − Y )v] = 0 for every v ∈ Vi . Subtracting, E[ri v] = 0, that is PVi (ri ) = 0. Each step is small: for consecutive agents, Equation (7) gives ∥ri − ri−1 ∥22 = ∥pi−1 − pi ∥22 ≤ 21 (Ei−1 − Ei ), so summing telescopes to M X

∥ri − ri−1 ∥22 ≤ 12 ∆.

i=1

Lemma 31 gives a constant λ > 0 depending only on D and (S1 , . . . , SM ), so Lemma 32 gives λ∥PH (r0 )∥22 ≤ 2(M 2 + 1) · 21 ∆ = (M 2 + 1) ∆.

(16)

Finally, we bound ∥PH (r0 )∥2 from below by the excess loss. The predecessor logit z0 lies in K, and z0 ̸= z⋆ (else E0 = 0), with z0 − z⋆ ∈ H. Since z0 − z⋆ ∈ H, projecting r0 onto the line through it gives ∥PH (r0 )∥2 ≥

E[(p0 − p⋆ )(z0 − z⋆ )] ≥ µ∥z0 − z⋆ ∥2 , ∥z0 − z⋆ ∥2

using E[(p0 − p⋆ )(z0 − z⋆ )] ≥ µ∥z0 − z⋆ ∥22 from Lemma 38. The same lemma gives E0 ≤ 18 ∥z0 − z⋆ ∥22 , so ∥z0 − z⋆ ∥22 ≥ 8E0 and ∥PH (r0 )∥22 ≥ 8µ2 E0 . Substituting into Equation (16) gives 8µ2 E0 ≤ (M 2 + 1)∆/λ, that is ∆ ≥ 8µ2 λ E0 /(M 2 + 1). With ∆ = E0 − EM , 8µ2 λ EM ≤ 1 − 2 E0 = q E 0 . M +1 P Since µ ≤ 14 and λ ≤ M (because i ∥PVi (u)∥22 ≤ M ∥u∥22 ), we have 8µ2 λ ≤ M/2 < M 2 + 1, so q ∈ [0, 1), depending only on D and (S1 , . . . , SM ). Only finitely many feature tuples can arise along a path, so taking the worst one gives a single contraction factor, exactly as in Theorem 5. Theorem 11 (Classification fixed-distribution geometric convergence). Fix M and a distribution D on (x1 , . . . , xd , Y ) with d finite, Y ∈ {0, 1}, and BCE minimum over H attained at z⋆ . Assume x1 , . . . , xd have bounded second moments. There is a constant q ∈ [0, 1), depending only on D and M , such that for any DAG of agents on D, if A1 → · · · → AD is a path whose every M consecutive raw-feature spans sum to H, then Es+M ≤ q Es whenever 1 ≤ s ≤ D − M, and consequently ED ≤ E1 q ⌊(D−1)/M ⌋ . Proof. Fix s with 1 ≤ s ≤ D − M . The sub-path As+1 → · · · → As+M is a block of M consecutive agents whose raw-feature spans sum to H, and its first agent has the on-path predecessor As . Applying Lemma 39 to this block gives Es+M ≤ q(Ss+1 , . . . , Ss+M ) Es with a factor in [0, 1) depending only on D and the tuple (Ss+1 , . . . , Ss+M ). That tuple takes at most 2dM values, so q = max q(Ss+1 , . . . , Ss+M ) ∈ [0, 1) over the finitely many feasible tuples depends only on D and M , and Es+M ≤ q Es for every such s. The loss is non-increasing along the path (Lemma 5). Iterating the per-block contraction from s = 1 over ⌊(D − 1)/M ⌋ full blocks and using monotonicity on the remaining steps gives ED ≤ E1 q ⌊(D−1)/M ⌋ . 35

Theorem 10 (No fixed classification distribution for all depths). Fix M and a distribution D on (x1 , . . . , xd , Y ) with d finite, bounded second moments for the raw features, and Y ∈ {0, 1}. Assume the BCE minimum over the raw-feature span is attained, and call a minimizer z⋆ . For every c > 0 there is a Dc such that for any DAG of agents on D, if A1 → · · · → AD is a path whose every M consecutive raw-feature spans sum to the full raw-feature span and D ≥ Dc , then L(zD ) − L(z⋆ ) < c

M2 . D

Thus one fixed finite classification distribution with an attained minimizer cannot witness an M 2 /D lower bound for all depths. Proof. By Theorem 11, ED ≤ E1 q ⌊(D−1)/M ⌋ for some q ∈ [0, 1) depending only on D and M . The zero logit is feasible for A1 , so E1 ≤ L(0) − L(z⋆ ) ≤ log 2. Fix c > 0. Since q < 1, we have (log 2) Dq ⌊(D−1)/M ⌋ → 0 as D → ∞, so there is a Dc , depending only on D, M , and c, with (log 2) Dq ⌊(D−1)/M ⌋ < cM 2 for all D ≥ Dc . Then L(zD ) − L(z⋆ ) = ED ≤ (log 2) q ⌊(D−1)/M ⌋ < cM 2 /D.

References [Aum76]

Robert J Aumann. “Agreeing to Disagree”. In: The Annals of Statistics 4.6 (1976), pp. 1236– 1239.

[Ban92]

Abhijit V Banerjee. “A simple model of herd behavior”. In: The quarterly journal of economics 107.3 (1992), pp. 797–817.

[BGP+06]

Stephen P. Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. “Randomized gossip algorithms”. In: IEEE Trans. Inf. Theory 52.6 (2006), pp. 2508–2530. doi: 10 . 1109 / TIT . 2006.874516.

[BHH+26]

MohammadHossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, and Shayan Taherijam. “Networked Information Aggregation for Binary Classification”. In: CoRR abs/2605.01082 (2026). doi: 10.48550/ARXIV.2605.01082. arXiv: 2605.01082.

[BHW92]

Sushil Bikhchandani, David Hirshleifer, and Ivo Welch. “A theory of fads, fashion, custom, and cultural change as informational cascades”. In: Journal of political Economy 100.5 (1992), pp. 992–1026.

[Bri83]

David R. Brillinger. “A Generalized Linear Model With “Gaussian” Regressor Variables”. In: A Festschrift for Erich L. Lehmann. Ed. by Peter J. Bickel, Kjell Doksum, and J. L. Hodges. Wadsworth, 1983, pp. 97–114.

[CFJ+21]

Kewei Cheng, Tao Fan, Yilun Jin, Yang Liu, Tianjian Chen, Dimitrios Papadopoulos, and Qiang Yang. “SecureBoost: A Lossless Federated Learning Framework”. In: IEEE Intell. Syst. 36.6 (2021), pp. 87–98. doi: 10.1109/MIS.2021.3082561.

[CGG+25]

Natalie Collina, Surbhi Goel, Varun Gupta, and Aaron Roth. “Tractable agreement protocols”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025, pp. 1532– 1543.

[CGG+26]

Natalie Collina, Ira Globus-Harris, Surbhi Goel, Varun Gupta, Aaron Roth, and Mirah Shi. “Collaborative prediction: Tractable information aggregation via agreement”. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2026, pp. 4712–4798.

[CLZ17]

Zihao Chen, Luo Luo, and Zhihua Zhang. “Communication Lower Bounds for Distributed Convex Optimization: Partition Data on Features”. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA. 2017, pp. 1812–1818. doi: 10.1609/AAAI.V31I1.10912.

[DeG74]

Morris H DeGroot. “Reaching a consensus”. In: Journal of the American Statistical Association 69.345 (1974), pp. 118–121. 36

[EDB16]

Murat A Erdogdu, Lee H Dicker, and Mohsen Bayati. “Scaled least squares estimator for glms in large-scale problems”. In: Advances in Neural Information Processing Systems 29 (2016).

[EGH+26]

Eric Eaton, Surbhi Goel, Marcel Hussing, Michael Kearns, Aaron Roth, Sikata Bela Sengupta, and Jessica Sorrell. “Model Agreement via Anchoring”. In: arXiv preprint arXiv:2602.23360 (2026).

[GCW+24]

Taicheng Guo, Xiuying Chen, Yaqi Wang, Ruidi Chang, Shichao Pei, Nitesh V. Chawla, Olaf Wiest, and Xiangliang Zhang. “Large Language Model Based Multi-agents: A Survey of Progress and Challenges”. In: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI 2024, Jeju, South Korea, August 3-9, 2024. ijcai.org, 2024, pp. 8048–8057. doi: 10.24963/IJCAI.2024/890.

[GHK+23]

Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder. “Loss Minimization Through the Lens Of Outcome Indistinguishability”. In: 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10-13, 2023. Vol. 251. LIPIcs. 2023, 60:1–60:20. doi: 10.4230/LIPICS.ITCS.2023.60.

[GJ10]

Benjamin Golub and Matthew O Jackson. “Naive learning in social networks and the wisdom of crowds”. In: American Economic Journal: Microeconomics 2.1 (2010), pp. 112–149.

[GK03]

Douglas Gale and Shachar Kariv. “Bayesian learning in social networks”. In: Games Econ. Behav. 45.2 (2003), pp. 329–346. doi: 10.1016/S0899-8256(03)00144-1.

[HKR+18]

Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. “Multicalibration: Calibration for the (Computationally-Identifiable) Masses”. In: Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018. Vol. 80. Proceedings of Machine Learning Research. 2018, pp. 1944–1953.

[KGZ19]

Michael P. Kim, Amirata Ghorbani, and James Y. Zou. “Multiaccuracy: Black-Box PostProcessing for Fairness in Classification”. In: Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, AIES 2019, Honolulu, HI, USA, January 27-28, 2019. 2019, pp. 247–254. doi: 10.1145/3306618.3314287.

[KRR26]

Michael Kearns, Aaron Roth, and Emily Ryu. “Networked Information Aggregation via Machine Learning”. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026. SIAM. 2026, pp. 4799– 4845. doi: 10.1137/1.9781611978971.173.

[MMS+18]

Elchanan Mossel, Manuel Mueller-Frank, Allan Sly, and Omer Tamuz. “Social Learning Equilibria”. In: Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018. 2018, p. 639. doi: 10.1145/3219166.3219207.

[MOT16]

Elchanan Mossel, Noah Olsman, and Omer Tamuz. “Efficient Bayesian Learning in Social Networks with Gaussian Estimators”. In: 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016, Monticello, IL, USA, September 27-30, 2016. 2016, pp. 425–432. doi: 10.1109/ALLERTON.2016.7852262.

[NR26]

Georgy Noarov and Aaron Roth. “Optimal Deterministic Multicalibration and Omniprediction”. In: arXiv preprint arXiv:2606.20557 (2026).

[Sta15]

Richard P Stanley. Catalan numbers. Cambridge University Press, 2015.

[VGS+18]

Praneeth Vepakomma, Otkrist Gupta, Tristan Swedish, and Ramesh Raskar. “Split learning for health: Distributed deep learning without sharing raw patient data”. In: CoRR abs/1812.00564 (2018). arXiv: 1812.00564.

[Wol92]

David H. Wolpert. “Stacked generalization”. In: Neural Networks 5.2 (1992), pp. 241–259. doi: 10.1016/S0893-6080(05)80023-1.

[YLC+19]

Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. “Federated Machine Learning: Concept and Applications”. In: ACM Trans. Intell. Syst. Technol. 10.2 (2019), 12:1–12:19. doi: 10.1145/3298981.

[ZDW13]

Yuchen Zhang, John C. Duchi, and Martin J. Wainwright. “Communication-efficient algorithms for statistical optimization”. In: J. Mach. Learn. Res. 14.1 (2013), pp. 3321–3363. doi: 10. 5555/2567709.2567769.

[ZSC+24]

Yusen Zhang, Ruoxi Sun, Yanfei Chen, Tomas Pfister, Rui Zhang, and Sercan Ö. Arik. “Chain of Agents: Large Language Models Collaborating on Long-Context Tasks”. In: Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10-15, 2024. 2024. url: http: //papers.nips.cc/paper_files/paper/2024/hash/ee71a4b14ec26710b39ee6be113d7750Abstract-Conference.html.

Omitted Proofs

We will restate and prove lemmas whose proof was omitted from the main text. Lemma 10 (End-of-pass shape). For 1 ≤ p ≤ k − 1, the residual has the form above and p X (p) rj = 1,

Ep =

j=0

p X (p) (p) (rj )2 = r0 ,

(p)

r0 = r1 .

j=0

Proof. We show by induction that after pass p the residual involves only zk−p , . . . , zk , that is positions 0, . . . , p. In pass 1 the prediction stays zero until the path reaches Xk , since X1 , . . . , Xk−1 depend only on z1 , . . . , zk−1 and so are independent of Y = zk ; fitting zk from Xk = zk − zk−1 then leaves residual (zk + zk−1 )/2, which involves only zk−1 , zk . For the step, assume the residual after pass p involves only zk−p , . . . , zk . In pass p + 1, every feature before Xk−p depends only on z1 , . . . , zk−p−1 , hence is orthogonal to both Y and the incoming prediction. The incoming residual is orthogonal to the incoming prediction and to such a feature, so Lemma 3 shows that adjoining the feature does not change the projection. From Xk−p = zk−p − zk−p−1 on, the only new latent variable that can enter is zk−p−1 , so the residual after pass Pp (p) p + 1 involves only zk−p−1 , . . . , zk . This gives the stated form Rp = j=0 rj zk−j . Fix p ≤ k − 1. In every pass, X1 = z1 is the first feature. When it is seen in a pass q ≤ p, the incoming prediction is the end of pass q − 1, which involves only zk−q+1 , . . . , zk ; since q ≤ k − 1, none of these is z1 , and z1 is also orthogonal to Y = zk . So X1 receives coefficient zero in every pass and never enters the prediction, which therefore lies in span{X2 , . . . , Xk }. Each Xi with i ≥ 2 has z-coefficients summing to zero, Pp (p) while Y = zk sums to one, so the residual coefficients sum to j=0 rj = 1. Pp Pp (p) (p) Since Rp = j=0 rj zk−j and the z’s are orthonormal, Ep = E[Rp2 ] = j=0 (rj )2 . The final prediction ybp = Y − Rp has coefficient vector e0 − r(p) . By self-orthogonality of the least-squares P (p) (p) predictor (Lemma 1), the residual is orthogonal to the prediction, so 0 = ⟨e0 − r(p) , r(p) ⟩ = r0 − j (rj )2 , P (p) (p) giving Ep = j (rj )2 = r0 . The last agent also sees Xk = zk − zk−1 , with coefficient vector e0 − e1 , so, (p)

(p)

by Lemma 3, the residual is orthogonal to e0 − e1 as well: 0 = ⟨r(p) , e0 − e1 ⟩ = r0 − r1 . Lemma 11 (One-agent update). Suppose an agent receives residual coefficient vector b, so its incoming prediction has coefficient vector e0 − b. Let b+ be the outgoing residual coefficient vector. If the feature seen by the agent is orthogonal to both Y and the incoming prediction, then b+ = b. If the feature is gj = ej−1 − ej with j ≥ 2, then for some scalar α, + b+ j−1 = bj =

α (bj−1 + bj ), 2

b+ m = αbm

(m ≥ 1, m ∈ / {j − 1, j}).

If the feature is g1 = e0 − e1 , then for some scalar α, + b+ 0 = b1 =

1 (1 − α) + α(b0 + b1 ) , 2 38

b+ m = αbm

(m ≥ 2).

Proof. Let f be the incoming prediction. Since f is a least-squares predictor, the incoming residual is orthogonal to f by Lemma 3. If the new feature is orthogonal to both Y and f , then the incoming residual is also orthogonal to the new feature. By Lemma 3, the least-squares projection onto the span of f and the new feature is still f , and b+ = b. Now suppose the feature is gj = ej−1 − ej . The new prediction has vector α(e0 − b) + γgj for some scalars α, γ. Hence b+ = e0 − α(e0 − b) + γgj = (1 − α)e0 + αb − γgj . + By Lemma 3, the new residual is orthogonal to gj , so 0 = ⟨b+ , gj ⟩ = b+ j−1 − bj .

For an interior feature, j ≥ 2, the e0 term does not touch positions j − 1 and j. Reading off these two positions gives b+ b+ j−1 = αbj−1 − γ, j = αbj + γ. + The condition b+ j−1 = bj becomes αbj−1 − γ = αbj + γ, hence γ = α(bj−1 − bj )/2. Substituting this value back gives α + (bj−1 + bj ). b+ j−1 = bj = 2 The value at every other positive position is multiplied by the same factor α. Thus an interior update replaces the two touched positions by their average, up to the common factor α.

For the boundary feature j = 1, the feature is g1 = e0 − e1 . Now b+ 0 = (1 − α) + αb0 − γ,

b+ 1 = αb1 + γ,

+ and all positions m ≥ 2 become αbm . The condition b+ 0 = b1 reads (1 − α) + αb0 − γ = αb1 + γ, so

γ=

1 (1 − α) + α(b0 − b1 ) . 2

Substituting this value back gives + b+ 0 = b1 =

1 (1 − α) + α(b0 + b1 ) . 2

The boundary update therefore equalizes positions 0 and 1, while the values at positions m ≥ 2 are all multiplied by the same factor α. Lemma 12 (Tail shape). Define probability vectors µ(p) recursively as follows. Start with µ(2) = (1). For P (p−1) 2 (p−1) (p−1) each 3 ≤ p ≤ k − 1, after µ(p−1) = (µ1 , . . . , µp−2 ) has been defined, set Sp−1 = i (µi ) . Initialize (p)

(p)

u(p) = (u1 , . . . , up−1 ) to the zero vector, where ui

is the unnormalized mass assigned to position i + 1. Add

(p−1) (p) (p) (p−1) to ui for at position m + 1 adds 2−(m+2−i) µm Sp−1 /2 to u1 . For every 1 ≤ m ≤ p − 2, the mass µm P P (p) (p) each 1 ≤ i ≤ m + 1. Normalize: µ(p) = u(p) / i ui . Finally set Sp = i (µi )2 for every 2 ≤ p ≤ k − 1.

Then for every 2 ≤ p ≤ k − 1, (p)

(p)

r(p) = (1 + 2Sp )−1 (Sp , Sp , µ1 , µ2 , . . . , µp−1 ), Sp Ep = . 1 + 2Sp Proof. For p = 2, pass 1 leaves residual (zk + zk−1 )/2, so r(1) = ( 12 , 12 ). In pass 2, the first feature that changes the prediction is Xk−1 = zk−1 − zk−2 . The incoming prediction lies along Xk = zk − zk−1 , so by Lemma 3 the new predictor is the projection of zk onto span{zk − zk−1 , zk−1 − zk−2 }. Write the residual at this point as q0 zk + q1 zk−1 + q2 zk−2 . Orthogonality to Xk and Xk−1 gives 0 = ⟨q, Xk ⟩ = q0 − q1 ,

0 = ⟨q, Xk−1 ⟩ = q1 − q2 .

Thus q0 = q1 = q2 . The current prediction lies in the span of Xk and Xk−1 , and both directions have coefficient sum zero. Since Y = zk has coefficient sum one, the residual coefficients also sum to one, so 39

R2 = (zk +zk−1 +zk−2 )/3. This residual is already orthogonal to the current prediction and to Xk = zk −zk−1 , so Lemma 3 shows that the last agent of the pass leaves it unchanged. Thus r(2) = ( 31 , 13 , 31 ). Since µ(2) = (1) (2) and S2 = 1, the formula gives r(2) and E2 = r0 = S2 /(1 + 2S2 ). Now fix 3 ≤ p ≤ k − 1 and assume the formula holds after pass p − 1. Then r(p−1) = (1 + 2Sp−1 )−1 (Sp−1 , Sp−1 , µ(p−1) ). In pass p, all features before gp = ep−1 − ep leave the prediction unchanged by Lemma 11: their nonzero positions are outside 0, . . . , p − 1 and do not include the target position 0. It remains to follow gj = ej−1 − ej for j = p, p − 1, . . . , 1. By Lemma 11, the updates with j ≥ 2 average the two touched positive positions, up to a common rescaling, and the final update j = 1 only rescales positions 2, 3, . . . , p. We may ignore these common factors while computing the tail direction, since they will be absorbed into one scalar at the end. (p−1)

(p−1)

Before these updates, the positive positions 1, . . . , p are proportional to v = (Sp−1 , µ1 , . . . , µp−2 , 0), where vi is the unscaled value at position i. Let ui be the final unscaled value at position i + 1, and set up := 0. When gi+1 is reached, position i still has value vi . The current value at position i + 1 is ui+1 : for i = p − 1 this is the new zero position, and for i < p − 1 it was made equal to position i + 2 by the previous update and position i + 2 is never touched again. Thus averaging positions i and i + 1 gives ui =

1 1 vi + ui+1 2 2

(1 ≤ i ≤ p − 1).

Unrolling the recursion gives ui =

p−1 X

2−(m−i+1) vm .

m=i (p−1)

sits at Thus the mass Sp−1 at position 1 adds Sp−1 /2 to u1 . For every 1 ≤ m ≤ p − 2, the mass µm −(m+2−i) (p−1) to ui for 1 ≤ i ≤ m + 1. This is exactly the defining rule for u(p) . position m + 1 and adds 2 µm (p−1) It has positive total mass because µ is a probability vector, so µ(p) is defined. (p)

(p)

Restoring the common scale gives r(p) = (a, a, c′ µ1 , . . . , c′ µp−1 ) for some scalars a, c′ . P (p) It remains to determine a and c′ . Put S = Sp = i (µi )2 . The coefficient-sum identity from Lemma 10 (p) gives 2a + c′ = 1. The same lemma gives Ep = r0 = a, while orthonormality gives Ep = 2a2 + (c′ )2 S. Thus a = 2a2 + (c′ )2 S. Substituting c′ = 1 − 2a gives a = 2a2 + (1 − 2a)2 S, or equivalently 0 = (2 + 4S)a2 − (1 + 4S)a + S. The two roots are a = 21 and a = S/(1 + 2S). The error is non-increasing along the path by Lemma 2; since E2 = 13 and p ≥ 3, we have a = Ep ≤ 13 , so a = 12 is impossible. Hence a = S/(1 + 2S) and c′ = 1 − 2a = 1/(1 + 2S). This is exactly the claimed formula at pass p, and the induction is complete. Lemma 16 (Tail as a killed-walk mixture). For every 2 ≤ p ≤ k − 1, the vector µ(p) from Lemma 12 is a convex combination of ν0 , . . . , νp−2 . Proof. We prove this by induction on p. For p = 2, the claim is µ(2) = ν0 . Pp−2 Pp−2 Assume the claim holds for some 2 ≤ p ≤ k − 2. Write µ(p) = t=0 λt νt , where λt ≥ 0 and t=0 λt = 1. Let K be one unnormalized killed-walk step: if η is a vector on the positive integers, then (Kη)i is the mass i after one step, with all mass that lands at 0 or below removed. Equivalently, (Kη)i = P at integer −(j+2−i) . Hence, by Lemma 12, the unnormalized vector that is normalized to form µ(p+1) is j≥1, i≤j+1 ηj 2

Kµ(p) + (Sp /2)ν0 : the second term is the extra mass placed at integer 1, since ν0 is the unit mass at integer 1. It remains to see what K does to each νt . By definition of νt , starting from νt is the same as conditioning on τ > t. Thus, for i ≥ 1, (Kνt )i = Pr(Wt+1 = i, τ > t + 1 | τ > t) = Pr(τ > t + 1 | τ > t) Pr(Wt+1 = i | τ > t + 1, τ > t) = Pr(τ > t + 1 | τ > t) Pr(Wt+1 = i | τ > t + 1) = Pr(τ > t + 1 | τ > t)νt+1 (i). The equality that removes the condition τ > t uses that τ > t + 1 implies τ > t. Therefore Kνt = qt νt+1 , where qt = Pr(τ > t + 1 | τ > t) ≥ 0. Substituting the induction hypothesis gives Kµ(p) + (Sp /2)ν0 = (Sp /2)ν0 +

p−2 X

λt qt νt+1 .

t=0

This is a nonnegative combination of ν0 , . . . , νp−1 . Normalizing this combination gives a convex combination of the same vectors. Thus µ(p+1) is a convex combination of ν0 , . . . , νp−1 . Lemma 18. G(a, b) =

C(ab) . 1 − aC(ab)

Proof. Consider a valid word w. Since the word is valid, we can decompose it into a sequence of valid balanced words separated by opening parentheses. Suppose that o(w) − c(w) = h. These h extra opening parentheses split the word uniquely as w = u0 (u1 ( · · · (uh . where each ui is a valid balanced word. Summing over all possible values of h gives X X G(a, b) = F (a, b)(aF (a, b))h = C(ab)(aC(ab))h h≥0

= C(ab)

h≥0

(aC(ab))h =

h≥0

C(ab) . 1 − aC(ab)

Lemma 19 (Survival words). At time t, form a word w by writing, for each step s = 1, . . . , t, one opening parenthesis followed by Gs closing parentheses. Then w is valid if and only if the mass has not been killed by time t. Proof. For a prefix u of w, consider the value 1 + o(u) − c(u). At the end of the block for step s, this value is Ws . If the mass is killed by time t, then Ws ≤ 0 for some s ≤ t, so the prefix ending at that block has more closing than opening parentheses. Thus w is not valid. Conversely, suppose w is not valid, and take the first prefix u with o(u) < c(u). This first failure occurs during the closing parentheses of some step s. The rest of that block also consists of closing parentheses, so Ws ≤ 1 + o(u) − c(u) ≤ 0. Hence the mass is killed by time t. √ √ Lemma 22 (Survival probability). For every integer t ≥ 0, 1/ t + 1 ≤ Pr(τ > t) ≤ 2/ t + 1. Proof. By the definition of H(z) and Lemma 21, we have Pr(τ > t) = the following standard bounds: √ √ 2n 4n /(2 n) ≤ ≤ 4n / n. n 41

2t+2 2t+1 . Set n = t + 1. We use t+1 /2

Since 22t+1 = 22n−1 = 4n /2, substituting n = t + 1 in the exact formula gives the two displayed bounds on Pr(τ > t). Lemma 23 (Increment moments). For each integer t ≥ 1, the increment 1 − Gt satisfies E[1 − Gt ] = 0 and Var(1 − Gt ) = 2. P P Proof. From ℓ≥0 q ℓ = 1/(1 − q), differentiating once and multiplying by q gives ℓ≥0 ℓq ℓ = q/(1 − q)2 . P 2 ℓ 3 Differentiating this identity and multiplying by q gives ℓ≥0 ℓ q = q(1 + q)/(1 − q) . With q = 1/2, P P −(ℓ+1) 2 −(ℓ+1) E[Gt ] = = 1 and E[G2t ] = = 3. Thus E[1 − Gt ] = 0 and Var(1 − Gt ) = ℓ≥0 ℓ2 ℓ≥0 ℓ 2 2 Var(Gt ) = 3 − 1 = 2. √ Lemma 24. For every integer t ≥ 0, E[min{t, τ }] ≤ 4 t. Proof. For each outcome, min{t, τ } is the number of integers s ∈ {0, . . . , t − 1} for which τ > s. Taking expectations gives t−1 t−1 X X √ √ E[min{t, τ }] = Pr(τ > s) ≤ 2/ s + 1 ≤ 4 t. s=0

s=0

The last inequality is trivial for t = 0 and follows by comparison with an integral for t ≥ 1: Z t t−1 X √ √ 1/ s + 1 ≤ 1 + x−1/2 dx ≤ 2 t. 1

s=0

The Upper Bound Assumptions

Pd P Theorem 1 makes two assumptions: the global predictor f ⋆ (x) = ℓ=1 wℓ⋆ xℓ satisfies ℓ |wℓ⋆ | ≤ A⋆ , and 2 . In this section we show that neither assumption can be dropped. If either each feature satisfies E[x2ℓ ] ≤ MX one is removed, the excess error of the last agent can be made arbitrarily large, even when M and D are fixed. Both results start from the instance of Theorem 3 and multiply the label by a constant a. This multiplies every path predictor by a, since each agent projects the label onto a span that does not change. Thus the excess error is multiplied by a2 , and it grows without bound as a grows. Proposition 1 (The coefficient bound cannot be dropped). For every M ≥ 8, every D ≥ M 2 , and every R > 0, there is an M -covered path of depth D whose global predictor f ⋆ is exact and whose features satisfy E[x2ℓ ] ≤ 2, but MSE(fD ) − MSE(f ⋆ ) ≥ R. Proof. Take the instance of Theorem 3 for these M and D. Its features satisfy E[x2ℓ ] ≤ 2, its global predictor f ⋆ ispexact, and its last agent has excess error ED := MSE(fD ) − MSE(f ⋆ ) ≥ M 2 /(1280π 2 D) > 0. Set a = R/ED , keep the features, and replace the label by Y ′ = aY . The global predictor is still exact, since Y ′ = af ⋆ is a linear combination of the features, and it equals af ⋆ . ′ be the path predictors for the label Y ′ . We induct on t to show that ft′ = aft . Agent At sees Let f1′ , . . . , fD the features xSt as before and, by the induction hypothesis, the prediction aft−1 in place of ft−1 . These inputs span the same set as before, so by Lemma 3, ft′ is the projection of aY onto the same span as ft , which is aft . ′ Since fD = afD and the global predictor is af ⋆ , we have

′ MSE(fD ) − MSE(af ⋆ ) = a2 MSE(fD ) − MSE(f ⋆ ) = a2 ED = R. Proposition 2 (The second-moment bound cannot be dropped). For every M ≥ 8, every D ≥ M 2 , and Pd every R > is an M -covered path of depth D whose global predictor f ⋆ (x) = ℓ=1 wℓ⋆ xℓ is exact and P0, there satisfies ℓ |wℓ⋆ | ≤ 3, but MSE(fD ) − MSE(f ⋆ ) ≥ R. 42

p Proof. Take the same instance of Theorem 3 andPthe same a = R/ED as in the proof of Proposition 1. P Its global predictor f ⋆ = ℓ wℓ⋆ xℓ is exact with ℓ |wℓ⋆ | ≤ 3. Now multiply every feature and the label by a, so the new features are x′ℓ P = axℓ and P the new label is Y ′ = aY . The coefficients w⋆ still give an exact ′ ⋆ global predictor, since Y = a ℓ wℓ xℓ = ℓ wℓ⋆ x′ℓ , so the new global predictor is af ⋆ . We induct on t to show that ft′ = aft . Agent At now sees the features x′St = axSt and, by the induction hypothesis, the prediction aft−1 . These are the old inputs multiplied by a, so they span the same set as before, and as in the proof of Proposition 1, ft′ is the projection of aY onto that span, which is aft . Hence ′ MSE(fD ) − MSE(af ⋆ ) = a2 ED = R.

Record · ID 660799 · SHA-256 e507cddab86c2ec5
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.