Networked Information Aggregation via Machine Learning

Michael Kearns; Aaron Roth; Emily Ryu

Source-linked AI summary

Networked Information Aggregation via Machine Learning

Michael Kearns, Aaron Roth, Emily Ryu

arXiv:2507.09683v2Jul 13, 2025cs.LGcs.GTecon.TH

TL;DR

The paper asks when agents in a DAG, each seeing only some features, can aggregate information through sequential predictions to match an all-feature predictor. It develops learning and analysis tools for linear and general hypothesis classes, then proves that sufficiently deep paths with repeated feature coverage enable aggregation, while bounded-depth networks can fail even in the linear case. Experiments on two real datasets illustrate rapid convergence with depth and the influence of topology and feature coverage.

Problem
The paper asks when sequential predictors in a DAG can aggregate distributed feature information well enough to match the best predictor using all features.
Method
It analyzes agents that fit models from their own features and parents’ predictions, using greedy orthogonal regression and multiaccuracy/self-orthogonality properties.
Results
Sufficiently deep paths with repeated feature coverage enable low excess error, whereas bounded-depth DAGs can retain error at least 1/(D + 1) despite a perfect all-feature linear predictor.
Takeaways & Limitations
Depth is the key worst-case structural parameter for information aggregation, although experiments also find strong empirical correlations with other topology measures.
Takeaways & Limitations
The theory has a gap between upper and lower depth dependencies, with bounds scaling as 1/√p and 1/p in the lower-bound construction.

Abstract

from arXiv · show

We study a distributed learning problem in which learning agents are embedded in a directed acyclic graph (DAG). There is a fixed and arbitrary distribution over feature/label pairs, and each agent or vertex in the graph is able to directly observe only a subset of the features -- potentially a different subset for every agent. The agents learn sequentially in some order consistent with a topological sort of the DAG, committing to a model mapping observations to predictions of the real-valued label. Each agent observes the predictions of their parents in the DAG, and trains their model using both the features of the instance that they directly observe, and the predictions of their parents as additional features. We ask when this process is sufficient to achieve \emph{information aggregation}, in the sense that some agent in the DAG is able to learn a model whose error is competitive with the best model that could have been learned (in some hypothesis class) with direct access to \emph{all} features, despite the fact that no single agent in the network has such access. We give upper and lower bounds for this problem for both linear and general hypothesis classes. Our results identify the \emph{depth} of the DAG as the key parameter: information aggregation can occur over sufficiently long paths in the DAG, assuming that all of the relevant features are well represented along the path, and there are distributions over which information aggregation cannot occur even in the linear case, and even in arbitrarily large DAGs that do not have sufficient depth (such as a hub-and-spokes topology in which the spoke vertices collectively see all the features). We complement our theoretical results with a comprehensive set of experiments.

1 Introduction

The paper reframes networked social learning as distributed empirical-risk minimization over partially observed features and asks when predictions can aggregate information to match an all-feature benchmark. It shows that depth and repeated feature coverage enable aggregation, while insufficient depth can prevent it even for linear models.

Generalization and context: The framework extends beyond linear regression by requiring hypothesis classes to provide multiaccuracy and self-orthogonality, while contrasting with simpler DeGroot averaging and stronger Bayesian learners.The paper also relates its orthogonality requirements to calibrated multiaccuracy and prior network-learning work.
Problem and model: The paper models agents in a DAG that sequentially learn from their observed features and parents’ predictions, targeting performance competitive with the best predictor using all features.Agents may observe different, overlapping feature subsets, and each predictor incorporates predecessor predictions as additional inputs.
Why aggregation is non-trivial: A connected path or subtree whose agents collectively observe every feature is insufficient because early agents may see features that are individually uninformative but jointly predictive.In the two-feature construction, the first agent’s feature is independent of the label, so its passed prediction contains no useful information despite a perfect joint linear predictor.
Upper bounds: For linear learners, a path whose every contiguous block covers all d features lets the final agent approach the best all-feature linear model with excess error η using path depth scaling as O(1/η^2).The analysis relies on predictors being multiaccurate and self-orthogonal; linear regression satisfies both properties.
Lower bounds: The lower bound requires seeing the full feature sequence Ω(1/η) times in sequence before any path agent can achieve excess error η.Thus the upper and lower bounds differ in their depth dependence: O(1/η^2) versus Ω(1/η).
Lower bounds: For every depth D, some distribution has a perfect all-feature linear predictor while every DAG of depth at most D leaves every agent with MSE at least 1/(D + 1).This rules out worst-case guarantees based only on graph properties that do not imply growing depth, including hub-and-spokes size.

2 Preliminaries

The paper models sequential distributed learning in a DAG, where agents use local feature subsets and parent predictions to minimize squared error. Its analysis centers on multiaccuracy and self-orthogonality as error and prediction-quality conditions.

The target benchmark is an optimal centralized predictor using all d features, while each agent sees only x_Si and parent predictions.
Agents learn in topological order from local feature subsets and their parents’ predictions, using models optimized for squared error.
The framework measures predictor performance with mean squared error and studies whether network predictions approach the centralized linear benchmark.
Multiaccuracy requires low residual correlation with every function in a reference collection, while self-orthogonality applies this condition to the predictor itself.

3 Linear Learners

For linear learners, long paths can aggregate distributed features because least-squares predictors are multiaccurate and self-orthogonal, while error decreases monotonically along paths. Depth and repeated feature coverage determine when a path can approach the all-feature benchmark.

3 Linear Learners: Depth drives the linear upper bound: sufficiently long paths contain subsequences whose predictors compete with bounded-norm predictors over the union of observed features.
3 Linear Learners: The analysis assumes the distributional regime, so agents optimize over the true distribution and obtain exact multiaccuracy and self-orthogonality.
3 Linear Learners: Least-squares residuals are orthogonal to observed features, making each predictor multiaccurate with respect to linear functions and self-orthogonal.
3 Linear Learners: Mean squared error is non-increasing along a path, and consecutive predictors’ squared L2 distance equals their MSE improvement.
3 Linear Learners: If every contiguous interval of M agents covers all d features, the final agent on a length-D path is competitive with the optimal bounded-L1 linear predictor.
3 Linear Learners: Under random feature allocation, sufficiently long subsequences have full feature coverage with high probability, yielding near-optimal agents on sufficiently deep paths.

4 Extension to General Function Classes

The paper extends the path-based aggregation analysis to general hypothesis classes using greedy orthogonal regression. The algorithm builds parent-and-local feature pools, terminates after boundedly many additions, and obtains benchmark guarantees with approximation and propagation errors.

4 Extension to General Function Classes: General function classes preserve monotonic error reduction and benchmark competition, extending the framework beyond linear predictors to models such as decision trees and neural networks.
4.2 The Greedy Orthogonal Regression Algorithm: Each final predictor is exactly self-orthogonal and multiaccurate with respect to parent predictions, while MSE does not increase relative to a parent.
4.2 The Greedy Orthogonal Regression Algorithm: Greedy Orthogonal Regression repeatedly adds the local hypothesis most correlated with the current residual, re-solving least squares over the expanded feature pool.
4.2 The Greedy Orthogonal Regression Algorithm: The algorithm terminates after O(1/∆2) rounds under normalized hypotheses and produces a predictor that is ∆-multiaccurate with respect to the local class.
4.3 Overall Guarantee for Non-Linear Models: The overall guarantee compares an agent with a benchmark formed from M randomly sampled hypothesis classes and separates intrinsic, propagation, statistical, and algorithmic errors.

5 Lower Bounds: Depth is Necessary

The lower bounds show that information aggregation can require repeated sequential exposure to variables and that DAG depth is the fundamental bottleneck, even when a perfect linear predictor exists.

Lower-bound construction: The construction has a perfect linear predictor over all features, while earlier feature subsets remain independent of the target or distant latent variables.These independence properties create the sequential dependency that drives both lower bounds.
5.1 Learning Requires Seeing Each Variable Many Times in Sequence: In the path construction, information advances only one latent variable per complete variable sequence, so achieving excess error η may require observing every variable 1/η times.The cyclic assignment gives agents x1, x2, ..., xk repeatedly, although efficient propagation would require the reverse order.
5.1 Learning Requires Seeing Each Variable Many Times in Sequence: The path lower bound gives E[(Y − ŷ_p,k)^2] ≥ 1/(p+1) after pass p.This follows from the best predictor available using features x_{k-p+1}, ..., x_k.
5.1 Learning Requires Seeing Each Variable Many Times in Sequence: After pass p, the predictor can depend on at most {z_k, z_{k-1}, ..., z_{k-p}}, limiting how much target information has reached the end of the path.The predictor remains unchanged through the initial phase of each pass and first updates at feature x_{k-p+1}.
5.2 Learning Requires Depth in Arbitrary DAGs: For every DAG of depth D, a distribution exists with optimal linear MSE 0 while every node's distributed predictor has MSE at least 1/(D+1).Thus, increasing graph size or changing topology cannot replace sufficient depth in the worst case.
5.2 Learning Requires Depth in Arbitrary DAGs: The lower bound scales as 1/p whereas the general upper bound scales as 1/√p; simulations fit β/√p better, leaving the tight dependence unresolved.The better fit persists at longer chain lengths for the same construction, suggesting the upper bound may be close to tight.

6 Experimental Results

Experiments on wine-quality and appliance-energy regression datasets show that information aggregation improves with effective path depth, while graph traversal order can obscure performance. Neural networks preserve these structural patterns but can be non-monotonic and surpass the globally optimal linear baseline.

Linear chains: Convergence to the globally optimal linear model is rapid on wine quality and improves with larger feature fractions, while appliance usage with the smallest fraction remains unconverged after 50 learners.The experiments vary each learner’s observed feature fraction from 0.1 to 0.5 and compare against a full-feature linear-model baseline.
Top-down trees: Depth is the strongest performance correlate in top-down trees: ordering learners by depth restores monotone convergence and sharply reduces error bars.Breadth-first ordering mixes learners with different depths and therefore produces non-monotone performance.
Bottom-up trees: Bottom-up tree performance is poorly aligned with topological order but becomes monotone with tight error bars when learners are ordered by subtree size.Subtree size measures how many learners feed into a learner during bottom-up aggregation.
Implications: The experiments suggest that performance correlates with topology more subtly than worst-case depth alone, motivating study of centrality, degree distribution, and clustering.The study uses two tabular regression datasets and chain, top-down tree, and bottom-up tree topologies.
Neural networks: Neural-network learners retain the qualitative tree-position effects but show occasional non-monotonicity and can beat the globally optimal linear model.The neural networks use 3 hidden units, learning rate 0.01, and 100 epochs per trial.

A Deferred Proofs from Section 4

The deferred proofs establish the general orthogonality-based analysis and its consequences for sequential learners. They show monotone MSE improvement, multiaccuracy, and high-probability path guarantees under independently assigned hypothesis classes.

General proof framework: Greedy Orthogonal Regression is multiaccurate with respect to each agent’s hypothesis class when its residual has small correlation with every class function.The termination condition controls the maximum residual correlation by the multiaccuracy tolerance.
General proof framework: Orthogonal projection decomposes benchmark error into prediction error, projection distance, and a residual component orthogonal to the learned feature subspace.This decomposition supports comparisons with arbitrary benchmark predictors.
Monotone improvement: Each agent’s MSE is no greater than any parent’s, with the exact reduction equal to the squared L2 distance between their predictors.The parent predictor is included in the agent’s feature span, making the residual component vanish in the decomposition.
Path guarantee: A path of length L ≥ M ln(1/δ) ln(1+γ/Cmse) achieves the benchmark guarantee with probability at least 1 −δ when hypothesis classes are assigned independently.The proof partitions the path into M-agent blocks and bounds failure using Markov’s inequality and independence.

B.1 In-Sample and Out-of-Sample Error

This section defines true and empirical squared error and the generalization gap, then identifies Rademacher complexity and concentration inequalities as tools for controlling finite-sample deviations.

Error definitions: True risk is the out-of-sample squared error under the data distribution, while empirical risk evaluates squared error on an i.i.d. training sample.The training set contains m independent samples from the underlying distribution.
Generalization gap: The generalization gap is the absolute difference between true risk and empirical risk, and it is typically controlled by function-class complexity.Rademacher complexity is introduced as a standard complexity measure for this purpose.
Complexity measure: Rademacher complexity measures the richness of a function class on a fixed sample and averages this quantity over datasets for its population version.The definition uses independent Rademacher signs taking values −1 and 1 with equal probability.
Concentration tools: The analysis uses Talagrand contraction, McDiarmid concentration, and matrix Bernstein inequalities to control transformed-function complexity, sample deviations, and covariance matrices.These tools address Lipschitz compositions, bounded differences, and sums of independent random matrices, respectively.

C Generalization Bounds for Linear Predictors

The linear generalization analysis shows that every sequential DAG predictor can be represented as a linear function of the full feature vector. This representation follows inductively from linear local models and linear parent predictions.

Linearity of DAG predictors: Every agent’s predictor is a linear function of the original full feature vector, even when the agent directly observes only a subset of features.The result is established by induction over a topological ordering of the DAG.
Base case: A root agent embeds its local coefficient vector into the full feature space by assigning zero coefficients to unobserved features.Thus its local prediction can be written as β_k^T x.
Inductive step: For a non-root agent, substituting the linear representations of parent predictions into its linear model preserves linearity in x.The resulting coefficient vector combines the agent’s locally observed-feature weights with weighted parent coefficient vectors.

C.2 Standard Generalization Bound for Linear Predictors

The section derives a high-probability generalization bound for L1-bounded linear predictors with bounded features and labels, using uniform convergence and Rademacher complexity. The resulting gap is small when sample size is sufficiently large relative to dimension and confidence.

The loss is bounded by M_L^2 with M_L = Λ1Xmax + Ymax, enabling McDiarmid’s inequality for the empirical-to-true error gap.Changing one training example changes the supremum gap by at most M_L^2/m.
Theorem C.2 bounds the generalization gap uniformly for all linear predictors with ||β||1 ≤ Λ1, assuming ||x||∞ ≤ Xmax and |y| ≤ Ymax.The bound therefore applies to each learned predictor whose coefficient vector satisfies the same L1 constraint.
The complexity dependence includes log d because L1-constrained linear functions in d dimensions have dimension-dependent Rademacher complexity.The coordinate-wise bound uses Hoeffding’s inequality and a union bound over the d coordinates.
The proof combines symmetrization, a high-probability concentration step, Talagrand’s contraction principle, and a Rademacher-complexity bound for HΛ1.The squared loss is treated as a Lipschitz composition on the bounded prediction-error interval.
The theorem’s constants can be written using C = 8(Λ1Xmax + Ymax) and C′ = 2, matching the stated bound format.The result is described as small when the number of training samples is sufficiently large relative to dimension and confidence.

C.3 Matrix Concentration for Sample Covariance

The section establishes a high-probability operator-norm bound for the difference between empirical and population covariance matrices. It derives the result with matrix Bernstein by controlling summand norms and variance, then obtains an empirical minimum-eigenvalue guarantee.

Theorem C.3 gives a high-probability bound on ||Σ̂ − Σ||op for i.i.d. samples with ||xi||2 ≤ R_X.The proof represents the covariance error as an average of centered random matrices Yi = x_i x_i^T − Σ.
Matrix Bernstein is applied after bounding the summand norm and total variance parameter using the almost-sure radius R_X and Jensen’s inequality.The argument controls the relevant operator norms through bounds involving powers of R_X.
The proof solves the resulting quadratic inequality in the covariance error and combines the terms into a single universal-constant bound.A separate small-sample argument ensures the same form remains valid when m < log(2d/δ).
Corollary C.4 transfers the covariance concentration result to the empirical minimum eigenvalue when λmin(Σ) > 0 and m is sufficiently large.Weyl’s inequality yields λmin(Σ̂) ≥ λmin(Σ) − ||Σ̂ − Σ||op, so the empirical eigenvalue remains bounded away from zero.

C.4 Bounding Predictor Norms via Covariance

The section bounds predictor and coefficient norms by combining orthogonal-projection geometry with a positive minimum-eigenvalue assumption on the feature covariance. This supplies the L1 coefficient bound needed for the generalization analysis.

The resulting L2 coefficient bound is converted to the required L1 bound using the standard norm inequality.This establishes a finite Λ1 without changing the unregularized least-squares procedure or the multiaccuracy properties used by the main results.
Each population predictor is the orthogonal projection of y onto the span of its input features, so its L2 norm is at most ||y||L2.This follows because orthogonal projections are non-expansive in the Hilbert space of square-integrable random variables.
Assuming λmin(Σ) > 0 converts the predictor’s L2 norm bound into an L2 coefficient bound through the covariance quadratic form.The assumption is weaker than feature independence and corresponds to a well-conditioned, non-collinear feature distribution.

C.5 Bounding the Norm of Empirically Learned Predictors

The section extends the population norm argument to predictors learned from finite samples. Under bounded labels and empirical covariance conditioning, the learned coefficient vectors satisfy high-probability L2 and L1 bounds.

Lemma C.7 bounds the L2 norm of each empirically learned coefficient vector with probability at least 1 − δ.The result assumes bounded labels and the conditions ensuring empirical covariance remains sufficiently well-conditioned.
The finite-sample proof uses the empirical orthogonal-projection property to bound the predictor’s empirical squared norm by the empirical squared norm of the labels.Because |y| ≤ Ymax, the label term is uniformly bounded.
The empirical covariance lower bound from Corollary C.4 converts the predictor-norm control into a coefficient-norm bound.On the high-probability event, λmin(Σ̂) exceeds λmin(Σ)/2, which controls the coefficient quadratic form.
The L2 coefficient bound is then converted into the L1 bound required by the generalization theorem.This completes the finite-sample justification for applying the L1-bounded linear-predictor analysis to learned agents.

C.6 Combined Performance Guarantee with Finite Samples

With sufficiently long DAG paths and enough training data, empirically trained predictors achieve error close to the optimal linear predictor with high probability.

C.6 Combined Performance Guarantee with Finite Samples: With high probability, a sufficiently long path contains an agent whose later predictors have true error at most MSE(g∗) + η + 2ϵgen.The guarantee requires bounded features and labels, λmin(Σ) > 0, and sufficiently large training sets.
C.6 Combined Performance Guarantee with Finite Samples: The proof combines a feature-coverage event, covariance concentration, and uniform generalization, jointly holding with probability at least 1 −δL −2δm.These events connect the population path guarantee to finite-sample empirical predictors.
C.6 Combined Performance Guarantee with Finite Samples: The finite-sample argument bounds the empirical predictor’s true risk by relating empirical and population risks through uniform generalization.The proof first bounds the empirical predictor’s risk and then combines it with the in-distribution performance guarantee.
C.6 Combined Performance Guarantee with Finite Samples: The empirical process trains each agent by initializing with parent predictions, greedily adding local functions, and repeatedly solving empirical least squares.The resulting predictor class is controlled to enable uniform convergence bounds.

D.3 Bounding the Norm of Empirically Learned Predictors

The analysis bounds coefficient norms for empirically learned predictors by combining empirical incoherence, bounded basis functions, and the greedy algorithm’s finite pool size.

D.3 Bounding the Norm of Empirically Learned Predictors: Each greedy addition has empirical residual correlation at least ∆, making the newly selected local function substantially linearly independent of earlier functions.This yields a bound on the number of locally selected features through the per-step error reduction.
D.3 Bounding the Norm of Empirically Learned Predictors: Empirical incoherence remains formally necessary because parent predictions enter the basis without greedy filtering and may be highly collinear.The assumption therefore covers the entire basis, including fixed parent-prediction inputs.
D.3 Bounding the Norm of Empirically Learned Predictors: The L1 norm of each empirically learned coefficient vector is bounded under empirical incoherence, bounded labels and functions, and a finite basis size.The bound depends on the number of parent predictions, the local feature-selection threshold, Bbasis, Ymax, and λmin,H.
D.3 Bounding the Norm of Empirically Learned Predictors: The coefficient norm proof uses least-squares normal equations, a lower-bounded Gram-matrix eigenvalue, and bounded basis-function correlations with labels.The resulting L2 bound is converted to an L1 bound using the standard norm inequality.
D.3 Bounding the Norm of Empirically Learned Predictors: The bounded coefficient norm places each empirical predictor in an L1-constrained function class, enabling the subsequent generalization analysis.The section establishes the norm control needed for the generalization guarantee.

D.4 Main Generalization Theorem

The main generalization theorem shows that empirical predictors have true risk close to empirical risk under boundedness, empirical incoherence, and a bound on the number of selected functions.

D.4 Main Generalization Theorem: The result follows by combining the coefficient-norm bound with uniform convergence for the resulting constrained hypothesis class.The proof is a direct application of the preceding norm and generalization results.
D.4 Main Generalization Theorem: Under bounded functions and labels, empirical incoherence, and at most Tmax selected functions, the learned predictor’s true risk is close to its empirical risk with high probability.The theorem applies the L1-norm coefficient bound and uniform convergence over GΛ1(Huniv).
D.4 Main Generalization Theorem: The theorem treats each learned predictor as a linear combination of at most Tmax functions from Huniv with an L1 norm bounded by Λ1.This representation permits application of the L1-bounded function-combination generalization result.