Optimal Lower Bounds for Networked Information Aggregation

Ambar Pal

Source-linked AI summary

Optimal Lower Bounds for Networked Information Aggregation

Ambar Pal

arXiv:2608.15472v1Aug 16, 2026cs.LGcs.AIstat.ML

TL;DR

Networked information aggregation studies learners that sequentially combine local features and parent predictors, with error depending on graph depth. This paper constructs worst-case instances achieving Ω(1/√p) error, extends the result to regular convex losses, and settles the depth dependence for MSE and logistic loss.

Problem
Networked information aggregation requires learners on a directed acyclic graph to learn predictors from local features and parent predictors, with the goal of characterizing how error decays along the path.
Method
The paper defines a Gaussian worst-case family with singleton local features arranged across passes and analyzes learners' population-loss errors using an inductive argument under two regularity conditions.
Results
Ω(1/√p) lower bounds match the O(1/√p) upper bounds for both MSE and logistic loss, settling their correct depth dependence in the networked information aggregation model.
Takeaways & Limitations
The same Ω(1/√p) lower-bound dependence extends from MSE to convex losses satisfying the stated regularity conditions, including logistic loss.
Takeaways & Limitations
The analysis assumes singleton local feature sets, at most one parent per learner, and a population-loss minimizer positively correlated with the label.

Abstract

from arXiv · show

The problem of networked information aggregation, studied in Kearns et al. (2026), involves a group of learners situated on the vertices of a directed acyclic graph $G$, each learning a linear predictor $\widehat Y$ for a fixed random variable $Y$ given access to a local feature, as well as the predictors learnt by its parents. Learning proceeds iteratively, with learners ordered according to a topological sort of $G$. The main quantity of interest is the error incurred by the current learner, constrained to this flow of information, with respect to the best linear predictor using all the features seen so far. When the studied error is the MSE, i.e., $\mathbb{E} (\widehat Y - Y)^2$, Kearns et al. (2026) show that the error is at most $O(1/\sqrt{D})$ along a path of length $D$. They also obtain a hard instance where the MSE is lower bounded by $Ω(1/D)$, leaving the correct order open. In this work, we resolve this central open problem, and obtain a family of worst case problem instances with a MSE lower bound of $Ω(1/\sqrt{D})$. By exploiting invariances in the structure of the learnt predictors, our analysis generalizes to all convex loss functions $\ell(\widehat Y, Y)$ satisfying regularity conditions which include strong convexity in a ball around the origin, and that the ideal predictor minimizing the population loss is positively correlated with the label. We show that networked information aggregation on a gaussian instance in our worst case family incurs an $\ell$-error lower bounded by $Ω(1/\sqrt{D})$ with respect to this ideal predictor. We demonstrate that a variety of common losses satisfy these regularity conditions. In particular, the logistic loss satisfies them, and hence our analysis also closes the gap between the upper and lower bounds in Bateni et al. (2026).

1 Problem Setup

Networked information aggregation places learners on a directed acyclic graph, where each learns a linear predictor from local features and parent predictors. The paper studies error under this information flow and establishes a square-root depth lower bound, including for logistic loss.

Learners are vertices of a directed acyclic graph, with edges indicating access to parent predictors.
Each learner optimizes population loss over predictors linear in its accessible local features and parent predictors.The analysis assumes singleton local feature sets and at most one parent per learner.
For MSE, the paper generalizes a prior worst-case instance and shows error decays inversely with the square root of path length.
The same lower-bound rate applies to logistic regression.

2 Main Results

The paper constructs a repeated-pass worst-case family whose learners receive differenced features and information only through a path. It proves Ω(1/√p) lower bounds for MSE, logistic loss, and broader regular convex losses, matching known upper bounds.

The worst-case family uses k latent variables with zero means, unit variances, and pairwise zero correlations.
Each pass repeats the same feature collection: Z1 first, followed by differences Zi − Zi−1, with label Y = Zk.
The end-of-pass error Errℓ(p) measures the population loss of the final learner in pass p.
Least Squares Regression: The ideal linear predictor sums all pass features to recover Y and achieves zero MSE.
Least Squares Regression: Ω(1/√p) is a worst-case MSE lower bound for every pass p ≤ k − 1, matching the prior O(1/√p) upper bound.
Logistic Regression: The logistic-loss lower bound also has 1/√p depth dependence and matches Bateni et al.’s O(1/√p) upper bound.
General Convex Loss: For gaussian instances, any convex loss satisfying the two regularity conditions incurs an Ω(1/√p) error lower bound relative to the ideal loss.

3 Overall proof technique

The proof tracks each learner’s predictor through its latent-variable coefficients. It expresses each pass as a sequence of coefficient transformations and uses these transformations to analyze the final learner.

Every learned predictor is represented as a linear combination of latent variables with coefficient vector a.
The analysis records the coefficient vector at the last vertex of each pass.
Vertices are divided into three types, each inducing a coefficient transformation on its predecessor.Lemma 4.1 provides closed-form transformations for starting, intermediate, and final vertices.

2. Lemma 4.2 then derives the coefficient invariants at the end of every pass. In particular,

At the end of each pass, coefficient invariants constrain which latent variables contribute to the learned predictor. These invariants support the lower-bound argument by controlling the final learner’s coefficient structure.

Only the last p + 1 coefficients are nonzero at the end of pass p.
All nonzero coefficients except the last are negative.
A coefficient-based expression at the final vertex, combined with Cauchy–Schwarz, recovers the earlier lower bound.

3. The zero-sum invariant, along with the fact that ErrMSE

The proof uses a lower bound on cumulative coefficient sums and bypasses normalization factors through a ratio involving partial sums and MSE error. The same argument extends to broader losses under regularity conditions including strong convexity.

p ≥ 1/(p+1) follows by applying Cauchy–Schwarz to the last N+1 coefficients.The cumulative-sum argument uses the zero-sum relation among coefficients.
N ≲√p suffices if 1−c_(k−N) ≥1/3, reducing the lower bound to controlling a partial cumulative sum.
A recurrence relates a^(p) to earlier coefficient vectors, but normalization factors introduce complicated nonlinear terms.
The proof avoids tracking normalization by bounding the ratio of partial coefficient sums to 1−Err_MSE.
The argument extends to general losses satisfying regularity conditions, including strong convexity, using a conditioning argument for misspecified regression.

4 Least Squares Regression

The least-squares analysis represents learner predictions through latent-variable coefficient vectors and studies their transformations across passes. Invariants and recurrence manipulations yield the inverse-square-root lower bound, with improved constants available through tighter bookkeeping.

4. Least Squares Regression: Least-squares learning analyzes every prediction as a linear combination of latent variables Z1,...,Zk, with coefficients updated along the learner path.The analysis focuses on the coefficient vector at the last vertex of each pass.
4.1 Vertex Transformations: A_i replaces adjacent coefficients a_(i−1) and a_i by their average, while A_1 sets the first coefficient to zero.The remaining coordinates are unchanged by A_i.
4.1 Vertex Transformations: Each vertex map is invariant to positive scaling, so intermediate normalization factors can be ignored when composing one pass.Normalization is retained only for the final Type-III update.
4.2 Coefficient invariants: Coefficient invariants connect the last coordinate to MSE error, impose a zero coefficient sum, and characterize the squared norm and coordinate ranges.The last two coordinates of pass-end vectors also satisfy a specified relation.
4.3 Cumulative-sum lower bound: A one-pass recurrence expresses w^(p+1) as a weighted sum of the vectors T^n e_1, enabling cumulative sums to be analyzed through the same decomposition.Generating functions are used to calculate the relevant cumulative sums.
4.3 Cumulative-sum lower bound: For p ≥4, the proof establishes the inverse-square-root lower bound by choosing N=⌈2√p⌉ in the cumulative-sum argument.
4.4 Controlling the cumulative sum: The simplified constant 1/36 is loose, while improved bookkeeping yields a tighter lower bound, including p ≥1/(3.75√p) for sufficiently large p and k.

5 Regression with a Convex Loss

The section extends the lower-bound analysis from MSE to convex losses on the Gaussian worst-case instance. Under two regularity conditions, learned predictors remain positive rescalings of their MSE counterparts, yielding Ω(1/√p) error bounds for several losses.

Regularity conditions: The analysis assumes a convex loss whose population loss is differentiable, strongly convex within radius 2, and minimized at the true-label coefficient.These are the conditions called (Regular-I).
Regularity conditions: The second regularity condition requires the one-dimensional population-loss minimizer to lie in (0, 2], expressing positive alignment with the label.This is condition (Regular-II).
Predictor invariance: For every learner i ≥ 0, the predictor learned under the general loss is a positive scaled multiple of the predictor learned under MSE.This invariance reduces the general-loss optimization to a scalar rescaling problem.
Predictor invariance: The Gaussian structure and independence arguments show that an optimal feasible predictor can always be chosen in the form γ bY_i,MSE.The resulting scalar minimizer is shown to exist, be positive, and be unique using convexity and strong convexity.
Lower bound: Ω(1/√p) is the resulting error lower-bound dependence for regular convex losses, matching the MSE dependence.The theorem transfers the MSE lower bound through the predictor rescaling and regularity conditions.
Examples: Logistic loss satisfies both regularity conditions, with strong-convexity parameter μ ≥ 0.048 and a unique scalar minimizer in (0, 1].Huber loss and other suitably normalized strongly convex losses are also covered.

A.2 Proof of Lemma 4.2

This proof establishes coefficient invariants for the Gaussian worst-case construction and relates the final coefficient coordinates to the learner’s MSE error. The invariants support the pass-by-pass lower-bound analysis.

Coefficient identities: The last coefficient of any returned predictor is linked directly to its MSE error through the coefficient invariants.The proof derives this relation using orthogonal projection and Gaussian covariance identities.
Coefficient invariants: The coefficient vectors satisfy a zero-sum condition throughout the relevant passes.The Type-II averaging updates preserve coordinate sums, while the construction establishes the initial condition.
Error behavior: MSE error is non-increasing along the path because each learner can retain its incoming predictor by assigning zero weight to the new feature.At the first Type-III learner, the error is 1/2; thereafter, 0 ≤ Err ≤ 1/2.
Error behavior: At the end of pass p, the last two coordinates obey a fixed relation that combines with the error identity to constrain the final coefficient.The proof also uses the signs and support pattern of the coefficient vector across passes.
Sign and support: The induction preserves zero coordinates to the left and negative coordinates immediately before the final coordinate during passes p ≤ k − 1.Positive scaling leaves the support and signs unchanged, while averaging propagates the sign pattern.

A.4 Proof of Lemma 4.4

The proof represents each pass as a sequence of coefficient transformations, isolating positive scaling from the averaging dynamics. This yields a linear recurrence for the evolving coefficient profile.

Pass recurrence: Each pass is represented by positive normalization factors and a linear transformation T acting on the coefficient profile.The resulting one-pass recurrence is the basis for later analysis.
Averaging dynamics: Type-II learners successively replace neighboring coefficient pairs by their averages.Ignoring positive scales is valid because the final transformation is scale invariant.
Averaging dynamics: After the Type-II updates, the entering vector is obtained through a running-average recurrence over the prior pass’s coefficients.The recurrence is derived by tracking the first two entries and propagating the averaging rule.
Pass recurrence: The Type-III update applies A_k, rescales the vector positively, and adds a fixed vector affecting the first profile coordinate.The additive term has final entries −1/2 and 1/2.

A.5 Proof of Theorem 4.6

This proof solves the recurrence governing cumulative coefficient sums using generating functions and the kernel method. Formal power-series manipulations then provide the expressions needed for Theorem 4.6.

Theorem bound: Theorem 4.6 provides the resulting bound for every 2 ≤ p ≤ k − 1 and admissible t > 0.The admissibility condition is ⌈t√p − 1 + 1⌉ ≤ k − 1.
Theorem bound: The proof retains the exact dependence on N and applies the one-pass estimates for every integer 1 ≤ N ≤ k − 1.The argument covers p ≥ 4 directly and also holds for p = 2, 3.
Generating functions: A generating function V(x,y) is introduced to encode the coefficients of iterated transformations and obtain the cumulative sum c(p,N).The variables x and y are formal variables for this proof.
Kernel method: The coefficient recurrence is converted into a functional equation whose kernel factors through roots U(x) and eU(x).Only U(x) is a formal power series; the other root contains a 1/x term.
Kernel method: The recurrence’s triangular coefficient support makes substituting U(x) into V(x,y) well-defined as a formal power series.This justifies the kernel-method substitution despite the nonzero constant term of U(x).
Coefficient extraction: Lagrange inversion and coefficient extraction yield the required cumulative-sum expressions and their exponential bounds.The derivation uses a differentiated implicit equation and generalized binomial coefficients.

B.1 Proof of Lemma B.1

The proof combines Hoeffding’s lemma, Gaussian density calculations, and a change of variables to establish auxiliary expectation bounds and derivative sign conditions.

Hoeffding’s lemma is applied to a Rademacher variable S for every real u.The proof uses E[S] = 0 and S ∈ [−1, 1].
The sigmoid definition σ(t) = (1 + e^−t)^−1 is combined with the preceding bound using u = t/2.
Gaussian expectations are rewritten against the standard Gaussian density and transformed using z = √(1 + 2a)x.The change of variables gives dx = (1 + 2a)^−1/2 dz and x^2 = (1 + 2a)^−1z^2.
Setting a = r^2/4 and using the preceding identities yields lower bounds for both expectations when r ≤ 2.The argument also uses that the standard Gaussian density integrates to one and E[G^2] = 1.
For the auxiliary function F, the proof establishes F′(0) < 0 and F′(1) ≥ 0.The proof represents X as E + γ0Z, applies Gaussian identities including Stein’s identity, and compares sigmoid derivatives at scaled arguments.