PaperlayerView exact revision on arXiv

Source-linked AI summary

Networked Information Aggregation via Machine Learning

Michael Kearns, Aaron Roth, Emily Ryu

arXiv:2507.09683v2cs.LGcs.GTecon.TH

TL;DR

The paper asks when agents with partial, distributed feature access can aggregate information through a DAG to match predictors using all features. It analyzes linear and general learners and shows that depth, together with feature coverage along paths, governs success, while shallow networks can fail even when agents collectively observe every feature.

  • Problem

    The paper studies when sequential learners with limited, distributed feature access can aggregate information as accurately as a predictor using all features.

    Source: §1 · p. 3

  • Method

    It formalizes learning over DAGs and analyzes sequential predictors that combine each agent’s features with parents’ predictions, including greedy orthogonal regression.

    Source: §1 · p. 3, §4.2 · p. 17

  • Results

    Depth governs aggregation: sufficiently long paths with repeated feature coverage can achieve competitive linear prediction, whereas depth-at-most-D DAGs can incur MSE 1/(D + 1), even with hub-and-spokes coverage.

    Source: §1.1 · pp. 4, 6

  • Takeaways & Limitations

    Collectively observing all features is insufficient by itself; successful information aggregation depends on network depth and how features are distributed along paths.

    Source: §1.1 · pp. 4, 6

    The paper leaves unresolved whether excess-error dependence on path depth scales as 1/√p or 1/p.

    Source: §5.2 · p. 27

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 studies whether sequential empirical-risk minimization on a DAG can aggregate distributed feature information to match the best all-feature predictor. It shows that depth and feature coverage govern aggregation, develops orthogonality-based guarantees and lower bounds, and distinguishes this framework from prior opinion-dynamics and Bayesian-learning models.

1 Introduction

  • Agents sequentially fit predictors from their own feature subsets and parents’ predictions, aiming to match the best predictor using the union of all features.The framework allows arbitrary feature-label distributions, including arbitrarily correlated features, and evaluates performance within a fixed hypothesis class.Source: §1 · p. 3

1.1 Our Results and Techniques

  • Even when agents along a path collectively observe every feature, information aggregation can fail because early predictions may discard features that are individually uninformative but jointly essential.In the two-feature example, the first agent predicts the constant zero, leaving the second agent with MSE at least 1/2 despite a perfect joint linear predictor.Source: §1.1 · pp. 3–4
  • Sufficiently deep paths whose every contiguous block covers all features let linear learners approach the best all-feature linear model, with path length scaling roughly as 1/η^2 for excess error η.The analysis uses multiaccuracy and self-orthogonality: MSE decreases along paths, and long stretches of nearly equal-error predictors transfer feature-wise accuracy across agents.Source: §1.1 · pp. 4–5
  • The lower bounds show that seeing variables repeatedly can be necessary, while any DAG of depth at most D can suffer MSE at least 1/(D + 1) despite a perfect all-feature linear predictor.Thus hub-and-spokes graphs can fail in the worst case even when their spokes collectively observe every feature; experiments nevertheless find depth and subtree size predictive on real datasets.Source: §1.1 · p. 6

1.2 Additional Related Work

  • Unlike prior opinion-dynamics and Bayesian-learning models, this work studies one-shot empirical-risk minimization over arbitrary correlated feature distributions and gives finite-graph guarantees relative to fixed hypothesis classes.Its generalized method enforces approximate multiaccuracy together with exact parent and self-orthogonality, extending the analysis beyond linear regression while using weaker conditions than full multicalibration.Source: §1.2 · pp. 6–8

2 Preliminaries

The paper models sequential learning over a feature-partitioned DAG, where each agent combines locally observed features with parent predictions. It evaluates agents against a centrally trained all-feature linear benchmark and introduces MSE, multiaccuracy, and self-orthogonality for analysis.

2 Preliminaries

  • Agents form a DAG whose edges transmit predictions, and they learn sequentially in an order consistent with a topological sort.For agent Ai, Pa(i) denotes its set of parents.Source: §2 · p. 8
  • Each agent observes a specific subset of d features and trains a linear predictor from those local features plus its parents’ predictions.Root agents use only their local features, while parameters are chosen to minimize expected squared error.Source: §2 · p. 8
  • Mean squared error measures predictor performance through expected squared prediction error.The paper defines MSE as the expected squared difference between predictions and labels.Source: §2 · p. 8
  • Information aggregation is assessed by comparing an agent’s prediction accuracy with the optimal linear model trained centrally on all d features.The central benchmark f* minimizes expected squared error over linear predictors using the full feature vector.Source: §2 · p. 8
  • Multiaccuracy requires prediction errors to have low correlation with every function in a collection G, while self-orthogonality is self-referential multiaccuracy implied by, but substantially weaker than, calibration.If ϵ = 0, the properties are called multiaccurate and self-orthogonal, respectively.Source: §2 · p. 9

3 Linear Learners

This section analyzes linear learners, using path depth and feature coverage to characterize when sequential prediction improves toward the best linear model with access to all relevant features. It establishes guarantees under both deterministic coverage conditions and random feature allocation, including high-probability near-optimal prediction near the ends of sufficiently long paths.

3 Linear Learners

  • The section establishes linear-learner upper bounds by analyzing long paths in arbitrary DAGs, identifying depth as the central structural parameter.The guarantees assume the distributional, infinite-sample regime; finite-sample and out-of-sample guarantees are deferred to Appendices B–C.Source: §3 · p. 9

3.1 Structural Properties of Squared Error Regression

  • Least-squares predictors have residuals orthogonal to every input feature, are multiaccurate for all linear functions, and are self-orthogonal.An MSE decomposition further bounds error using comparison-model error, multiaccuracy, self-orthogonality, and prediction disagreement; it does not depend on linearity.Source: §3.1 · pp. 9–11

3.2 Analysis of Learners Along a Path

  • Along any DAG path, each learner is multiaccurate on local features and parent predictions, while MSE never increases and adjacent prediction differences equal MSE improvements.These properties imply that stable subsequences aggregate information across their union of features, yielding competitiveness with bounded-norm linear predictors under bounded coefficient norms and feature second moments.Source: §3.2 · pp. 12–13
  • If every contiguous interval of M path agents covers all d features, a length-D path produces a final predictor competitive with the optimal bounded-norm all-feature linear predictor.The guarantee follows by finding a subsequence with small cumulative MSE improvement and applying the path theorem; monotonicity extends it to later agents.Source: §3.2 · pp. 14–15

3.3 Performance Guarantee under a Random Allocation Model

  • Under independent random feature allocation with per-agent inclusion probability p, sufficiently long path subsequences are likely to cover the full feature set.This random-allocation model supplies depth-dependent performance guarantees and is also used for the paper’s experiments.Source: §3.3 · p. 15
  • With probability at least 1 −δ, every consecutive subsequence of length M along the main path observes the full feature set.The coverage result is the high-probability ingredient used to derive the overall random-model guarantee.Source: §3.3 · pp. 15–16
  • The full-coverage bound follows by bounding missed features for one subsequence and applying union bounds across features and disjoint subsequences along the path.For a fixed feature and subsequence, the miss probability is (1 −p)^M; union bounding over d features gives d(1 −p)^M before accounting for all path subsequences.Source: §3.3 · pp. 15–16
  • If a DAG contains a path of length at least N0, then with probability at least 1 −δL, an agent on that path and all subsequent agents are nearly optimal.Theorem 3.13 guarantees this for any target error η > 0 and confidence δL ∈(0, 1), with N0 determined by the random allocation parameters and desired guarantee.Source: §3.3 · p. 16

4 Extension to General Function Classes

The extension preserves monotonic error reduction and strong-benchmark guarantees for general hypothesis classes, including decision trees and neural networks. A greedy orthogonal regression procedure combines local functions with parent predictions and achieves benchmark-competitive accuracy along sufficiently long paths.

4.1 Model Definition with General Predictors

  • Each agent projects the outcome onto a pool containing parent predictions and selected local functions, yielding self-orthogonality and approximate multiaccuracy while retaining the linear analytic structure.The projection can be implemented through standard least squares, and the final residual is orthogonal to the feature pool.Source: §4.1 · p. 17, §4.2 · p. 18

4.2 The Greedy Orthogonal Regression Algorithm

  • The Greedy Orthogonal Regression Algorithm repeatedly adds the hypothesis-class function most correlated with the residual, re-solving least squares over the expanded feature pool until correlation falls below ∆.Unlike additive-update multiaccuracy methods, it re-solves the optimal linear regression over the accumulated feature span at every round.Source: §4.2 · p. 17
  • The greedy procedure terminates after O(1/∆2) rounds, and its final predictor is ∆-multiaccurate with respect to the agent’s hypothesis class.Each accepted feature reduces MSE, while the halting condition controls correlation with every function in the class.Source: §4.2 · pp. 17–18

4.3.1 A Norm-Constrained Benchmark

  • The norm-constrained benchmark is the expected best MSE from the span of M independently sampled hypothesis classes, and a path of length L ≥ M ln(1/δ) ln(1+γ/Cmse) approximates it with probability at least 1 − δ.The agents’ classes are sampled independently from an arbitrary distribution over hypothesis classes.Source: §4.3.1 · p. 20

4.3 Overall Guarantee for Non-Linear Models

  • For general hypothesis classes, a sufficiently long DAG path can yield diminishing excess error relative to a benchmark formed from randomly sampled classes, with intrinsic, propagation, and approximation errors separated.The benchmark permits arbitrary nonlinear relationships within an agent’s observed variables and additive combinations across agents.Source: §4.3 · p. 19, §4.3.2 · p. 20

4.3.2 Final Guarantee

  • The final guarantee bounds an agent’s MSE by the norm-constrained benchmark MSE plus γ(1 + 2L1,gBg), provided the DAG contains a sufficiently long path and agents use ∆ = γ.With probability at least 1 − δ, a subsequence of the required length ends at an agent attaining this bound.Source: §4.3.2 · p. 21

5 Lower Bounds: Depth is Necessary

These lower bounds characterize how DAG depth constrains distributed information aggregation, showing that sequential propagation over paths is necessary and that limited depth restricts the latent information available to individual nodes. They establish error lower bounds for arbitrary DAGs and compare the theoretical dependence with simulation results.

5.1 Learning Requires Seeing Each Variable Many Times in Sequence

  • On a path with cyclically assigned features, the agent observing x_k after pass p has MSE at least 1/(p+1), so accuracy requires seeing each variable repeatedly in sequence.The construction assigns x_1,…,x_k cyclically along the path, making each full cycle a pass.Source: §5.1 · p. 23

5.1.1 Analysis of the Predictor Structure

  • After pass p, the predictor’s latent-variable support is exactly contained in {z_k, z_{k−1}, …, z_{k−p}}, because only one deeper variable can be introduced per pass.The predictor remains unchanged through the initial phase of each pass and first updates at feature x_{k−p+1}.Source: §5.1.1 · p. 23

5.1.2 Lower Bound on Mean Squared Error

  • A linear predictor restricted to suffix features {x_j,…,x_k} has minimum MSE 1/(k−j+2), yielding the path lower bound 1/(p+1).The path predictor depends only on the suffix {x_{k−p+1},…,x_k}, so the suffix-error calculation applies directly.Source: §5.1.2 · p. 25

5.2 Learning Requires Depth in Arbitrary DAGs

  • For any depth-D DAG, a distribution admits perfect global linear prediction, yet every node’s distributed predictor remains subject to a depth-dependent error lower bound under any single-feature allocation.Thus, depth—not another independently scalable graph property—is the fundamental worst-case bottleneck.Source: §5.2 · pp. 25–26
  • Even with the most favorable feature allocation, a node at depth p can depend on at most {z_k,…,z_{k−p}}, so depth bottlenecks sequentially uncovering the latent chain.The only productive feature for introducing z_{k−p} is x_{k−p+1}, which links it to already available information.Source: §5.2 · pp. 25–26
  • Any node v in a depth-D DAG has MSE at least 1/(depth(v)+1), even under the best possible allocation of single features.Because depth(v) ≤ D, the predictor can depend on only a bounded span of latent variables, limiting its attainable accuracy.Source: §5.2 · p. 27
  • Figure 1’s lower-bound simulation fits β/√p better than α/p, suggesting the general upper bounds may be close to tight.Errors decrease in phases along the chain, while train and test error are nearly identical at the large sample size.Source: §5.2 · p. 27, Figure 1 · p. 27
  • The analysis leaves unresolved whether the correct dependence on vertex depth p is 1/√p or 1/p.The general upper bounds scale as 1/√p, whereas the lower-bound construction scales as 1/p; a sharper analysis of the same instance may resolve the gap.Source: §5.2 · p. 27

6 Experimental Results

Experiments on two regression datasets show that information aggregation generally improves with structurally relevant network position, while neural networks can surpass the all-feature linear baseline. The results also show that the best empirical correlate depends on topology, extending beyond depth alone.

Linear chain experiments

  • Linear learners rapidly approached the all-feature optimum along 50-learner chains, with convergence improving as each learner observed a larger feature fraction.For appliance usage, the 0.1 feature fraction had not converged after 50 learners, unlike the other settings and the wine dataset.Source: §6 · p. 28, Figure 2 · p. 30

Top-down tree experiments

  • In top-down trees, performance resembled chains but was non-monotonic in topological order and often remained suboptimal at leaves because tree paths aggregate less information.The comparison used 50-learner trees across both datasets and varied feature fractions.Source: §6 · p. 28, Figure 2 · p. 30
  • Ordering top-down tree learners by depth restored monotonic convergence and substantially reduced error bars, identifying depth as the relevant performance correlate.Breadth-first ordering mixed learners with different depths, whereas depth ordering removed that variability across random trees.Source: §6 · p. 28, Figure 2 · p. 30

Bottom-up tree experiments

  • For bottom-up trees, topological order was nearly random with respect to performance, whereas ordering by subtree size restored monotonicity and tight error bars.Subtree size measures how many learners feed into a given learner and therefore better captures aggregated information in this direction.Source: §6 · p. 28, Figure 2 · p. 30

Empirical implications

  • Across chains and trees, the experiments suggest that empirical performance correlates with topology-dependent measures beyond worst-case depth, including centrality, degree distribution, and clustering.The study used wine quality and appliance energy regression datasets with 11 and 26 features, respectively, under repeated train/test trials.Source: §6 · pp. 27, 29

Neural-network experiments

  • Neural networks retained the tree-topology patterns of linear models while sometimes increasing error along chains, yet ultimately beat the globally optimal linear baseline on both datasets.Learners used three-hidden-unit networks with learning rate 0.01 for 100 epochs; occasional non-monotonicities reflect the lack of guaranteed optimal training fits.Source: §6 · p. 29, Figure 4 · p. 32

A Deferred Proofs from Section 4 · B Generalization Bound Preliminaries

The deferred proofs establish multiaccuracy, MSE relationships, monotonic improvement, and high-probability path guarantees for Greedy Orthogonal Regression. The accompanying preliminaries frame the generalization-error analysis for linear and nonlinear models.

A Deferred Proofs from Section 4

  • Greedy Orthogonal Regression’s final predictor is Δ-multiaccurate with respect to H_k.The termination condition bounds the maximum residual correlation over H_k by Δ, which bounds every function’s correlation.Source: A Deferred Proofs from Section 4 · p. 35
  • The general MSE decomposition relates an agent’s orthogonal-projection predictor to any benchmark by separating the benchmark’s feature-subspace and orthogonal components.Orthogonality eliminates the component within span(F_k) from the relevant cross-term, leaving only the residual interaction with the orthogonal component.Source: A Deferred Proofs from Section 4 · p. 35
  • Each agent’s MSE is no larger than that of any parent, with the improvement equal to the squared L2 distance between their predictors.A parent predictor is included in the child’s feature pool, so it lies entirely in the child’s projection subspace.Source: A Deferred Proofs from Section 4 · pp. 35–36
  • For a path of length L ≥ M ln(1/δ) ln(1+γ/Cmse), i.i.d. hypothesis-class assignments achieve the stated benchmark guarantee with probability at least 1 − δ.The bound uses benchmark size M, norm bounds L1,g and B_g, approximation error γ, and a universal single-class MSE bound C_mse.Source: A Deferred Proofs from Section 4 · p. 36
  • The deferred results support the broader analysis of information aggregation through formal MSE and path-length guarantees.The proposition’s condition depends on benchmark size, approximation error, confidence, and an upper bound on single-class MSE.Source: A Deferred Proofs from Section 4 · p. 36
  • The path guarantee follows by partitioning agents into independent blocks, bounding each block’s bad-event probability with Markov’s inequality, and controlling the probability that all blocks fail.Choosing the path length to meet the proposition’s logarithmic condition makes the overall failure probability at most δ.Source: A Deferred Proofs from Section 4 · p. 36

B Generalization Bound Preliminaries

  • The generalization-bound preliminaries introduce foundational concepts and theoretical results for analyzing generalization error in linear and nonlinear models.This section serves as the stated foundation for the subsequent analysis.Source: B Generalization Bound Preliminaries · p. 37

B.1 In-Sample and Out-of-Sample Error · B.2 Complexity Measures and Concentration

These sections define out-of-sample risk and empirical in-sample risk, framing their difference as the generalization gap. They then introduce Rademacher complexity and concentration inequalities as tools for controlling generalization and covariance deviations.

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

  • Out-of-sample squared error measures a predictor’s risk under the true distribution D over feature-label pairs.The predictor maps x ∈ R^d to real-valued predictions, and risk is defined with respect to D.Source: §B.1 · p. 37
  • Empirical in-sample risk evaluates a predictor on a finite training set of m independent samples drawn from D.The training set is denoted D_m and consists of i.i.d. feature-label pairs.Source: §B.1 · p. 37
  • The generalization gap is the difference between true risk and empirical risk, written |R(f) − R̂_Dm(f)|.Generalization theory seeks to bound this gap.Source: §B.1 · p. 37

B.2 Complexity Measures and Concentration

  • Rademacher complexity measures function-class complexity and is used to control the generalization gap.The empirical version is defined on a fixed sample using independent random signs, while population complexity averages over datasets of size m.Source: §B.2 · p. 37
  • Talagrand’s contraction principle bounds the Rademacher complexity of a class after composing its outputs with an L_φ-Lipschitz function.The principle applies to classes formed as φ ◦ G.Source: §B.2 · p. 37
  • McDiarmid’s inequality controls deviations of functions of independent variables when changing one variable has a bounded effect.The analysis also uses matrix Bernstein concentration for independent bounded zero-mean random matrices, particularly sample covariance matrices.Source: §B.2 · pp. 37–38
  • Matrix Bernstein inequality provides concentration for sample covariance analysis using independent zero-mean matrix summands with bounded operator norm.The lemma is attributed to Tropp [2015], Theorem 1.6.2.Source: §B.2 · p. 38

C Generalization Bounds for Linear Predictors · C.1 Linearity of Sequential Predictors

The section proves that every predictor generated by sequential learning in a DAG is linear in the full feature vector. This representation enables standard generalization bounds for linear models.

C.1 Linearity of Sequential Predictors

  • Every agent’s prediction can be expressed as a linear function of the full feature vector x.Lemma C.1 states that each agent Ak has a vector βk ∈ R^d such that its prediction is represented linearly in x.Source: §C.1 · p. 38
  • The proof establishes this representation by induction over agents in a topological sort of the DAG.The induction proceeds from root agents to agents with parents.Source: §C.1 · p. 38
  • For a root agent, the locally linear predictor over its observed features is embedded into a d-dimensional coefficient vector by setting unobserved-feature coefficients to zero.This yields a linear representation in the full feature vector while preserving the root agent’s original predictor.Source: §C.1 · p. 38
  • For a non-root agent, the inductive hypothesis treats every parent prediction as a linear function of x.The proof assumes this representation for all parents Ap of agent Ak.Source: §C.1 · p. 38
  • Substituting the parents’ linear representations into the agent’s predictor expresses its output as a combination of its observed features and parent coefficient vectors.The parent predictions enter through scalar weights vk,p.Source: §C.1 · p. 38
  • Because the local and parent coefficients are d-dimensional and the parent weights are scalars, the resulting coefficient vector is also d-dimensional.Thus the agent’s prediction remains linear in x, completing the inductive step for all agents in the DAG.Source: §C.1 · p. 38

C.2 Standard Generalization Bound for Linear Predictors

The section establishes a high-probability generalization bound for L1-bounded linear predictors under bounded features and labels. It shows that the generalization gap becomes small with sufficiently many samples relative to dimension and confidence requirements.

Generalization bound

  • Theorem C.2 gives a high-probability generalization bound for all linear predictors with L1 norm at most Λ1, assuming ∥x∥∞≤Xmax and |y|≤Ymax.The result applies in particular to each learned predictor whose coefficient vector satisfies the same L1 bound.Source: §C.2 · p. 39
  • The bound’s complexity dependence includes log d, reflecting the complexity of L1-constrained linear functions in d dimensions.Bounding predictions and squared loss uses |f(x)|≤Λ1Xmax and ML=Λ1Xmax+Ymax.Source: §C.2 · p. 39

Proof

  • The proof combines symmetrization and concentration, Talagrand’s contraction principle for squared loss, and a Rademacher-complexity bound for the L1-constrained hypothesis class.The final hypothesis-class complexity estimate uses dual norms, Hoeffding’s inequality, and a union bound over d coordinates.Source: §C.2 · pp. 39–40

Implication

  • The resulting guarantee states that the true-versus-empirical error gap for agents’ learned linear predictors is small when sample size m is sufficiently large relative to dimension d and the desired confidence.The guarantee holds with probability at least 1−δ under the stated boundedness and coefficient-norm assumptions.Source: §C.2 · pp. 39–40

C.3 Matrix Concentration for Sample Covariance

The section establishes operator-norm concentration of the empirical covariance around the population covariance for bounded i.i.d. samples, using Matrix Bernstein. It then derives an empirical minimum-eigenvalue guarantee when the population covariance is positive definite and the sample size is sufficiently large.

Matrix Concentration for Sample Covariance

  • Theorem C.3 bounds the operator-norm deviation between empirical and population covariance matrices with high probability for i.i.d. samples satisfying ∥x_i∥_2 ≤ R_X almost surely.The bound holds for any δ ∈ (0, 1) with probability at least 1 − δ and a universal constant C.Source: §C.3 · p. 41

Proof of Theorem C.3

  • The proof applies Matrix Bernstein to centered matrices Y_i = x_i x_i^T − Σ, establishing bounds on their norm and variance parameters from the almost-sure feature bound.Independence and zero mean follow from the i.i.d. sampling assumption, while Jensen’s inequality controls the relevant operator norms and moments.Source: §C.3 · p. 41

Empirical Eigenvalue Bound

  • Corollary C.4 shows that if λ_min(Σ) > 0 and m satisfies the stated sample-size condition, then the empirical covariance has a high-probability positive minimum eigenvalue bound.The conclusion follows by combining Theorem C.3 with Weyl’s inequality and requiring the covariance deviation to be smaller than half the population minimum eigenvalue.Source: §C.3 · pp. 42–43

C.4 Bounding Predictor Norms via Covariance

The section bounds learned predictor coefficients by assuming the full feature covariance matrix has a strictly positive minimum eigenvalue. Orthogonal-projection non-expansiveness controls predictor norms, which then yields L2 and L1 coefficient bounds without changing unregularized least squares.

Population predictor bounds

  • Orthogonal projection ensures every agent’s predictor has L2 norm no larger than the true label’s L2 norm.Each least-squares predictor minimizes population risk over the linear span of its observed features and parent predictions.Source: §C.4 · p. 43

Covariance-based coefficient bounds

  • A positive covariance minimum eigenvalue λmin(Σ) > 0 converts the predictor-norm bound into an L2 bound on each coefficient vector βk.The assumption is weaker than feature independence and applies when features are not perfectly collinear.Source: §C.4 · p. 43

L1 norm control

  • The resulting L2 coefficient bound can be converted into the required L1 bound using the standard inequality ∥β∥1 ≤ … .This supplies the Λ1 control needed for the generalization bound while preserving the unregularized least-squares procedure and its multiaccuracy properties.Source: §C.4 · pp. 43–44

C.5 Bounding the Norm of Empirically Learned Predictors

Lemma C.7 bounds the coefficient norm of an empirically learned predictor from a finite sample with high probability, under bounded labels and the conditions of Corollary C.4. The proof combines empirical projection, label boundedness, and covariance concentration, then derives an L1 bound from the L2 bound.

C.5 Bounding the Norm of Empirically Learned Predictors

  • Lemma C.7 establishes a high-probability L2 norm bound for the coefficient vector learned from a training set of size m.The result assumes |y| ≤ Ymax and the conditions of Corollary C.4, with probability at least 1 − δ over the sample draw.Source: §C.5 · p. 44
  • The corresponding L1 norm bound follows from the standard inequality relating the L1 and L2 norms of the coefficient vector.The argument first obtains the L2 bound by rearranging the empirical covariance inequality, then applies the norm inequality.Source: §C.5 · p. 44
  • The proof bounds the empirical predictor norm using orthogonal projection onto the observed feature span, bounded labels, and the empirical covariance minimum-eigenvalue guarantee.Corollary C.4 supplies λmin(Σ̂) > λmin(Σ)/2 with probability at least 1 − δ.Source: §C.5 · p. 44

C.6 Combined Performance Guarantee with Finite Samples … D.2 Generalization Bound for Function Compositions

The paper extends path-based information aggregation to finite samples, showing that empirical predictors approach the optimal linear predictor under sufficient path length, sample size, and distributional assumptions. It also develops nonlinear generalization tools based on empirical greedy regression and Rademacher complexity bounds for function compositions.

C.6 Combined Performance Guarantee with Finite Samples

  • For any DAG path P of length at least N0, with probability at least 1−δL−2δm, an agent exists such that all subsequent predictors achieve true error at most MSE(g∗) + η + 2ϵgen.Source: §C.6 · pp. 45–46
  • The finite-sample guarantee combines feature coverage, covariance concentration, and uniform generalization events through a union bound.Feature coverage and uniform generalization occur with probabilities at least 1−δL and 1−δm, while all three events jointly occur with probability at least 1−δL−2δm.Source: §C.6 · p. 45

D Generalization Bounds for Non-Linear Models

  • The nonlinear analysis bridges in-population guarantees and finite-sample performance by bounding the gap between empirical and true errors under complexity and distributional assumptions.This framework is intended to extend the paper’s main theorems beyond linear predictors.Source: D Generalization Bounds for Non-Linear… · p. 46

D.1 Empirical Learning Process

  • The empirical learning process replaces expectations with averages over m i.i.d. samples and greedily adds locally selected functions until residual correlation falls below ∆.Each update recomputes empirical least squares over the expanded feature pool, including empirically evaluated parent predictors.Source: §D.1 · p. 46
  • The empirical algorithm’s central technical challenge is bounding the complexity of the class containing its final predictor so uniform convergence can be applied.The learned predictor is formed through successive greedy additions and empirical least-squares refits.Source: §D.1 · p. 46

D.2 Generalization Bound for Function Compositions

  • For L1-norm-bounded linear combinations of a bounded base class, the generalization analysis controls uniform convergence using the base class’s Rademacher complexity.The result assumes bounded function outputs and labels on an i.i.d. training set.Source: §D.2 · p. 47
  • The function-composition proof bounds predictor and squared-loss outputs, applies symmetrization and contraction, and then transfers complexity control from the base class to its L1-ball.The output bound is |g(x)| ≤ Λ1Bh, yielding loss bound (Λ1Bh + Ymax)^2 before contraction.Source: §D.2 · p. 47

D.3 Bounding the Norm of Empirically Learned Predictors

This section bounds the coefficient norms of empirically learned predictors using an empirical incoherence assumption, then derives a generalization guarantee. Greedy selection supports local feature independence, but parent predictions and the final basis still require the assumption.

D.3 Bounding the Norm of Empirically Learned Predictors

  • Greedy selection ensures each newly added local function has empirically orthogonal component norm at least ∆/Ymax, but parent predictions and the final basis remain formally covered only by Assumption 1.Parent predictions are fixed inputs and may be highly collinear; stepwise independence alone does not guarantee a lower bound for the final Gram matrix.Source: §D.3 · p. 48
  • Assumption 1 requires every reasonably sized candidate function set to have empirical Gram-matrix minimum eigenvalue at least λmin,H, preventing perfect collinearity.The assumption applies with high probability over the training data and covers any set that could form an agent’s predictor basis.Source: §D.3 · p. 48
  • Under Assumption 1, Lemma D.2 bounds each empirical greedy predictor’s L1 coefficient norm using its basis size, Bbasis, Ymax, and λmin,H.The basis size is Tk = |Pa(k)| + Tk,local, with Tk,local bounded by (BhYmax/∆)^2.Source: §D.3 · p. 48
  • The greedy algorithm’s local feature count is bounded because each selected function reduces empirical squared error by at least ∆^2/Bmax^2, while parent-prediction count remains fixed.This yields the stated bound Tk,local ≤ (BhYmax/∆)^2.Source: §D.3 · pp. 48–49
  • Corollary D.3 states a generalization result for predictors learned by the algorithm, under the assumptions of Theorem D.1 and Assumption 1, with probability at least 1 −δ over training-data draw.Source: §D.3 · p. 49

D.4 Main Generalization Theorem

The main generalization theorem guarantees that empirically trained predictors learned by empirical Greedy Orthogonal Regression have true risk close to empirical risk under boundedness, label, incoherence, and model-complexity conditions.

Assumptions

  • The theorem assumes the conditions of Theorem D.1 and Lemma D.4, including bounded functions, bounded labels, and empirical incoherence.It also assumes that any agent selects at most Tmax functions.Source: §D.4 · p. 50

Generalization guarantee

  • With probability at least 1 −δ, the learned predictor’s true risk is close to its empirical risk.The guarantee applies over the draw of a training set Dm of size m for any δ ∈(0, 1).Source: §D.4 · p. 50

Proof mechanism

  • The proof places each learned predictor in the class GΛ1(Huniv), enabling direct application of Theorem D.1.Lemma D.4 supplies a linear combination of at most Tmax functions from Huniv with L1 norm bounded by Λ1.Source: §D.4 · p. 50

Related papers

Loading 2507.09683v2…