Error Dependence From Shared Training Data

Why Shared Training Data Matter

Averaging predictions can reduce error when member errors do not move together. But learners trained on overlapping samples reuse some of the same information, so their prediction errors may be associated even if their remaining training data are independent. To quantify this effect, we need to distinguish the variation due to shared observations from the variation due to each learner’s private observations.

We study prediction at a fixed input $x$, under squared error relative to a fixed target $f_0(x)$. This avoids including a common test-response noise term: the errors below measure deviations of fitted predictions from the target, not deviations of a future noisy response from its realized value.

Definition: Let $U$ denote a block of shared training observations, and let $V_1,\ldots,V_M$ be private training data for $M$ learners. Write learner $j$'s prediction error at $x$ as $e_j=\hat f_j(x;U,V_j)-f_0(x)$. The shared-data component of its conditional mean error is $m_j(U)=E[e_j\mid U]$. We assume these errors have finite second moments whenever their variances or covariances are used.

A useful sampling model is that $U,V_1,\ldots,V_M$ are mutually independent blocks, except that every learner uses the same $U$; each $V_j$ is independent of the other private blocks and of $U$. The learners may also use algorithmic randomness, provided those random seeds are independent across learners and independent of all training data. Under this model, after conditioning on $U$, the remaining sources of randomness for different learners are independent. This conditional independence is the key assumption behind the covariance calculation.

Covariance From the Shared Block

The law of total covariance separates the covariance between two errors into a term remaining after conditioning and a term due to their conditional means. Conditional independence makes the first term zero.

Theorem: Suppose $e_1,e_2$ have finite second moments and are conditionally independent given $U$. Then $$ \operatorname{Cov}(e_1,e_2)=\operatorname{Cov}\bigl(E[e_1\mid U],E[e_2\mid U]\bigr). $$ If, in addition, $E[e_1\mid U]=E[e_2\mid U]$ almost surely, then $$ \operatorname{Cov}(e_1,e_2)=\operatorname{Var}\bigl(E[e_1\mid U]\bigr)\geq 0. $$

Proof. The law of total covariance gives

\operatorname{Cov}(e_1,e_2) =E[\operatorname{Cov}(e_1,e_2\mid U)] +\operatorname{Cov}(E[e_1\mid U],E[e_2\mid U]).

Conditional independence implies $\operatorname{Cov}(e_1,e_2\mid U)=0$ almost surely. Substitution proves the first identity. If the two conditional means agree almost surely, their covariance is the variance of that common random variable, which is nonnegative. $\square$

The equality of conditional means is a substantive condition, not a consequence of merely using the same algorithm and the same sample size. A standard sufficient condition is that both learners use the same permutation-invariant learning rule: its output depends on the training observations as an unordered collection, not on their positions in an ordered list. If the private data have the same distribution for both learners, then, conditional on the shared observations, the learners have the same distribution of prediction errors and hence the same conditional mean. The equality can also be assumed directly when symmetry is not appropriate.

For $M$ errors with common mean $b$, common variance $v$, and common pairwise covariance $c$, the error of their equally weighted average is $\bar e=M^{-1}\sum_{j=1}^M e_j$. Expanding its squared error gives

E[\bar e^2] =b^2+\operatorname{Var}(\bar e) =b^2+\frac{v}{M}+\frac{M-1}{M}c.

Thus, when the conditional means match under the theorem’s assumptions, $c\geq 0$. Averaging still reduces the variance contribution compared with a single member when $c<v$, but a positive covariance limits that reduction. The formula identifies precisely where the overlap enters: through the pairwise error covariance.

Worked Calculations for Overlapping Samples

Worked Example: Sample Means With a Shared Core

Let $X_1,\ldots,X_k$ be the shared observations and let $Z_{jr}$, for $j=1,\ldots,M$ and $r=1,\ldots,n-k$, be private observations. Suppose all these variables are independent and identically distributed with mean $\mu$ and variance $\sigma^2$. Each learner predicts with its training-sample mean, based on the $k$ shared observations and its own $n-k$ private observations. The target is $\mu$. Find the covariance between two member errors and the squared risk of their average.

For learner $j$, the error is

e_j=\frac{1}{n}\left\{\sum_{i=1}^k(X_i-\mu)+\sum_{r=1}^{n-k}(Z_{jr}-\mu)\right\}.

Given the shared observations, the private sums have conditional mean zero, so

E[e_j\mid U]=\frac{1}{n}\sum_{i=1}^k(X_i-\mu), \qquad U=(X_1,\ldots,X_k).

The two learners have the same conditional mean. Its variance, and therefore their covariance, is

\operatorname{Cov}(e_j,e_\ell) =\operatorname{Var}\left(\frac{1}{n}\sum_{i=1}^k(X_i-\mu)\right) =\frac{1}{n^2}\sum_{i=1}^k\operatorname{Var}(X_i) =\frac{k\sigma^2}{n^2},\qquad j\ne \ell.

Each individual error has variance $\sigma^2/n$, since it averages $n$ independent centered observations. The average of the $M$ errors has squared risk

E[\bar e^2] =\operatorname{Var}(\bar e) =\frac{1}{M^2}\left(M\frac{\sigma^2}{n} +M(M-1)\frac{k\sigma^2}{n^2}\right) =\frac{\sigma^2}{Mn}\left(1+(M-1)\frac{k}{n}\right).

When $k=0$, the risk is $\sigma^2/(Mn)$. When $k=n$, all members use exactly the same observations and the expression becomes $\sigma^2/n$: averaging identical sample means gives no variance reduction.

Worked Example: Three Members With One Shared Observation

Take $M=3$, $n=2$, and $k=1$ in the preceding model. Each sample consists of the common observation $X_1$ and one private observation. The common covariance between two errors is $\sigma^2/4$, and each error variance is $\sigma^2/2$. Therefore

E[\bar e^2] =\frac{1}{9}\left(3\frac{\sigma^2}{2} +6\frac{\sigma^2}{4}\right) =\frac{1}{9}\left(\frac{3\sigma^2}{2}+\frac{3\sigma^2}{2}\right) =\frac{\sigma^2}{3}.

If the three samples were disjoint, their errors would be independent and the average risk would instead be $(1/3)(\sigma^2/2)=\sigma^2/6$. Reusing one observation in every sample doubles the risk of the average in this example. It does not double any individual member’s risk; it changes the covariance between members.

Worked Example: Bernoulli Data and the Shared-Mean Contribution

Suppose the observations are Bernoulli with success probability $p=1/4$. Each learner uses a sample of size $n=4$, with $k=2$ observations shared by all learners and two private observations per learner. Its prediction is the sample proportion, and the target is $p$. The observation variance is $p(1-p)=3/16$. The shared-data theorem gives the pairwise error covariance

c=\frac{k p(1-p)}{n^2} =\frac{2(3/16)}{16} =\frac{3}{128}.

The variance of each member’s prediction error is

v=\frac{p(1-p)}{n}=\frac{3/16}{4}=\frac{3}{64}.

For $M=4$ learners, the average’s squared risk is

E[\bar e^2] =\frac{v}{4}+\frac{3c}{4} =\frac{3}{256}+\frac{9}{512} =\frac{15}{512}.

With four independent samples, the risk would be $v/4=3/256=6/512$. The positive excess, $9/512$, is exactly the contribution from the six unordered pairs of shared-data errors in the variance expansion.

Overlap Does Not Automatically Mean Positive Covariance

The nonnegative covariance conclusion requires matching conditional means. Sharing observations alone is not enough. An order-dependent learning rule can use the same observation differently in different positions, so the conditional mean errors need not agree.

Worked Example: An Order-Dependent Rule

Let $U,A,C$ be independent with mean zero and variance one. The ordered training samples are $(U,A)$ and $(C,U)$, so they share the observation $U$, but it occupies different positions. Let both learners use the deterministic rule that returns the first observation as its prediction, with target zero. Then $e_1=U$ and $e_2=C$. Their covariance is

\operatorname{Cov}(e_1,e_2)=E[UC]-E[U]E[C]=0.

However, $E[e_1\mid U]=U$, whereas $E[e_2\mid U]=0$. Thus

\operatorname{Var}(E[e_1\mid U])=\operatorname{Var}(U)=1, \qquad \operatorname{Cov}(E[e_1\mid U],E[e_2\mid U])=0.

The covariance theorem gives zero, not one. Its stronger variance form cannot be used because the conditional means do not match. A permutation-invariant rule, such as the sample mean, avoids this position mismatch: for these two samples its conditional mean error is $U/2$ for each learner.

Common Pitfall and Practical Interpretation

Wrong reasoning: “The learners use the same algorithm and sample size, so their conditional mean errors given the shared data must be identical.” This overlooks the possibility that the rule depends on observation order or that the shared observations occupy different positions.
Correction: Establish conditional independence given the shared block and separately justify equality of conditional means. Permutation invariance with identically distributed private data is a sufficient symmetry condition; direct equality of conditional means is another.
Wrong reasoning: “Any overlap forces positive covariance.” The general covariance is the covariance of the two conditional means, which can be zero or negative when those means differ.
Correction: Positive covariance follows from the variance identity only when the conditional means agree. Without that condition, calculate their covariance rather than replacing it with a variance.

In applications, the shared-data calculation clarifies why increasing the number of ensemble members need not keep lowering risk at the rate expected under independent errors. More members can average away private-sample variation, but a component induced by reused observations remains. The sample-mean calculation makes this especially transparent: the shared fraction $k/n$ controls how much of each member’s variance is common to the ensemble. For more complex learners, the same logic applies through the conditional mean error, but its size depends on how the fitted prediction responds to the shared observations.

Check Your Understanding

Use the assumptions stated in each question; distinguish conditional independence from equality of conditional means.

State the conditional-independence assumption needed to express the covariance of two errors using only their conditional means given $U$.
Why does permutation invariance help establish equality of conditional mean errors for learners with identically distributed private data?
For sample means based on $n$ observations with $k$ shared observations, what is the covariance between two errors when each observation has variance $\sigma^2$?
In the shared-core sample-mean model, what happens to the average’s risk when $k=n$, and why?
In the order-dependent example, identify which equality needed for the variance form of the theorem fails.