Why Ghost-Sample Arguments Need Care
A ghost-sample proof often looks like a sequence of simple substitutions: replace a population average by an independent empirical average, introduce random signs, and separate two terms. Each step has a specific justification. A change in the order of a supremum and an expectation, or an unnoticed dependence between observations, can reverse an inequality or make a purported identity false.
We will work with a nonempty countable class \(\mathcal{G}\) of measurable functions \(g:\mathcal{Z}\to[0,1]\), and independent identically distributed observations \(Z_1,\ldots,Z_n\) with distribution \(P\). Countability ensures the suprema below are measurable; suitable separability assumptions can extend the statements to some uncountable classes. Write \(Pg=E[g(Z)]\) and \(P_ng=n^{-1}\sum_{i=1}^n g(Z_i)\). A ghost sample \(Z'_1,\ldots,Z'_n\) is an independent sample from the same distribution, also independent of \(Z_1,\ldots,Z_n\).
Suprema and Expectations: The Safe Inequality
The fundamental inequality is that the supremum of expectations is no larger than the expectation of the supremum. If \(U_g\) is an integrable random variable for each \(g\), and the relevant suprema are measurable, then \(\sup_g E[U_g]\le E[\sup_g U_g]\). Indeed, \(U_g\le\sup_h U_h\) for every \(g\), so taking expectations gives \(E[U_g]\le E[\sup_h U_h]\); taking the supremum over \(g\) proves the claim. The reverse inequality, and equality in general, do not follow.
Worked Example: Expectation of a Supremum Is Not a Supremum of Expectations
Let the sample space contain two equally likely outcomes, \(a\) and \(b\), and define \(U_1(a)=1,\ U_1(b)=0,\ U_2(a)=0,\ U_2(b)=1\). At either outcome, one of \(U_1,U_2\) equals 1, so \(E[\max(U_1,U_2)]=1\). But \(E[U_1]=E[U_2]=1/2\), and hence \(\max(E[U_1],E[U_2])=1/2\). Thus \(\sup_g E[U_g]\le E[\sup_g U_g]\) is strict here.
The distinction matters when conditioning on the observed sample. Conditional on \(Z_1,\ldots,Z_n\), each \(Pg\) is the conditional expectation of \(P'_ng=n^{-1}\sum_i g(Z'_i)\). Applying the safe inequality conditionally gives \(\sup_g(Pg-P_ng)\le E_{Z'}[\sup_g(P'_ng-P_ng)\mid Z_1,\ldots,Z_n]\). Taking expectations then yields the first step of symmetrization. Replacing this inequality by equality is an unjustified exchange of supremum and expectation.
A Correct Symmetrization Bound
The first inequality uses the ghost sample only to express a population mean as a conditional expectation. The second uses the exchangeability of each independent pair \((Z_i,Z'_i)\), followed by a supremum inequality. Neither step says that the observed and ghost empirical averages are equal.
For each \(g\), \(E[P'_ng\mid Z_1,\ldots,Z_n]=Pg\). Apply \(\sup_g E_{Z'}[\cdot\mid Z]\le E_{Z'}[\sup_g\cdot\mid Z]\), then take expectation.
Each pair \((Z_i,Z'_i)\) has the same distribution after its entries are swapped. Independent random swaps therefore preserve the joint distribution of the entire indexed difference process.
Use \(\sup_g(A_g+B_g)\le\sup_g A_g+\sup_g B_g\), and take expectations. Each resulting term has expected value \(E_Z[R_n(\mathcal{G};Z)]\).
For completeness, the full derivation is
To justify the equality on the third line, condition on any fixed vector of signs. For each coordinate with sign \(-1\), swap \(Z_i\) and \(Z'_i\); leave the pair unchanged when the sign is \(+1\). The pairs are independent and identically distributed within each pair, so these swaps preserve their joint law. Consequently the signed difference process, simultaneously for all \(g\), has the same distribution as the unsiged difference process. On the fourth line, \(-\varepsilon_i\) is again an independent Rademacher sign, and \(Z'\) has the same distribution as \(Z\). This proves the stated bound. \(\square\)
What the Ghost Sample Must—and Must Not—Do
Worked Example: Reusing the Training Observation Destroys the Argument
Let \(Z\) be Bernoulli with \(P(Z=1)=P(Z=0)=1/2\), take \(n=1\), and use the single function \(g(z)=z\). Then \(Pg=1/2\) and \(P_1g=Z\). The population-minus-empirical deviation is \(1/2\) when \(Z=0\) and \(-1/2\) when \(Z=1\), so its expected value is 0; its expected absolute value is \(1/2\).
Now set the supposed “ghost” observation equal to the training observation: \(Z'=Z\). Then \(P'_1g-P_1g=g(Z)-g(Z)=0\) always. This cannot serve as the independent ghost step: in particular, it does not reproduce the conditional expectation \(Pg\), since \(E[g(Z')\mid Z]=g(Z)\), not \(Pg=1/2\) in general. For \(Z=0\), these values are 0 and \(1/2\); for \(Z=1\), they are 1 and \(1/2\). The independence of a genuine ghost sample is what makes \(E[P'_ng\mid Z]=Pg\) valid.
A ghost observation is not a second name for the training observation, nor is it a value chosen after looking at the training sample. It is an independent copy from \(P\). Conditioning on the training data leaves the distribution of the ghost sample unchanged. Without that fact, the conditional-expectation identity used in symmetrization can fail.
When Rademacher Signs Are Legitimate
The signs in the theorem are auxiliary random variables, independent of both samples. They enter because independent identically distributed pairs can be swapped without changing their joint distribution. Sign randomization is therefore a statement about the distribution of the whole process indexed by \(g\), not a pointwise identity for a particular pair of samples.
Worked Example: Checking the Bound for a Two-Function Class
Let \(Z\) be Bernoulli with probability \(1/2\) of 1, let \(n=1\), and set \(\mathcal{G}=\{g_0,g_1\}\), where \(g_0(z)=\mathbf{1}\{z=0\}\) and \(g_1(z)=\mathbf{1}\{z=1\}\). Both population means equal \(1/2\). If \(Z=0\), the two values of \(Pg-P_1g\) are \(-1/2\) and \(1/2\); their supremum is \(1/2\). If \(Z=1\), the values are \(1/2\) and \(-1/2\), again with supremum \(1/2\). Therefore \(E[\sup_g(Pg-P_1g)]=1/2\).
For an independent ghost \(Z'\), the supremum of \(P'_1g-P_1g\) is 0 if \(Z'=Z\). If \(Z'\ne Z\), one of the two indicator functions has difference 1 and the other has difference \(-1\), so the supremum is 1. The two observations differ with probability \(1/2\), giving \(E[\sup_g(P'_1g-P_1g)]=1/2\).
Finally, for a fixed observed \(Z\), exactly one of \(g_0(Z),g_1(Z)\) is 1 and the other is 0. If \(\varepsilon=1\), the supremum of \(\varepsilon g(Z)\) is 1; if \(\varepsilon=-1\), it is 0. Hence \(R_1(\mathcal{G};Z)=(1+0)/2=1/2\), whatever \(Z\) is. The theorem gives \(1/2\le1/2\le 2(1/2)=1\), as required.
A common invalid step is to choose signs based on which function or observation makes a term largest, and then treat those signs as independent Rademacher variables. The theorem does not permit that: its signs are independent of the data and of the class-indexed values. Another invalid step is to claim that sign randomization leaves every realized expression unchanged. In the example, swapping a particular unequal pair changes its signed difference; it is the distribution over the independent pairs that is preserved.
Common Errors and Their Corrections
| Invalid reasoning | Correction |
|---|---|
| “The supremum can pass through expectation without changing anything.” | Use \(\sup_g E[U_g]\le E[\sup_g U_g]\). Equality requires additional conditions and is not automatic. |
| “The ghost sample can reuse or depend on the training sample.” | Use an independent sample from \(P\), so \(E[P'_ng\mid Z]=Pg\). |
| “For any realized samples, inserting signs leaves the sum unchanged.” | Use exchangeability of each independent pair to establish equality in distribution of the indexed processes. |
| “The signs may be chosen after seeing the data.” | Take independent Rademacher signs; dependence changes the expectation and invalidates the complexity calculation. |
| “A supremum of a sum is the sum of the suprema.” | Use only the inequality \(\sup_g(A_g+B_g)\le\sup_g A_g+\sup_g B_g\); equality need not hold. |
These checks are useful because a ghost-sample proof is a chain of inequalities, not a collection of interchangeable expressions. Before accepting a line, identify what is random, what is conditioned upon, and whether the step is an equality in distribution, a conditional-expectation identity, or an inequality. Also check that the relevant suprema are measurable; countability is one simple way to ensure this.
Check Your Understanding
For each question, identify the justification needed or the error in the proposed step.
- Why does conditioning on the training sample leave \(E[P'_ng\mid Z_1,\ldots,Z_n]=Pg\) true for a genuine ghost sample?
- Give the general direction of the inequality between \(\sup_g E[U_g]\) and \(E[\sup_g U_g]\), and explain why equality need not hold.
- What property of independent ghost-training pairs permits Rademacher signs to be introduced?
- Why is a ghost sample set equal to the training sample generally unsuitable for the conditional-expectation step?
- In the symmetrization bound, which independence conditions must hold for the Rademacher signs?