Coupling and Maximal Inequalities for Graph-Dependent Empirical Processes

Coupling and Maximal Inequalities for Graph-Dependent Empirical Processes

\thispagestyle{empty}

\setcounter{page}{1}

Introduction

This paper develops theoretical tools for empirical process theory with graph-dependent data. Its main result is a maximal inequality for empirical processes indexed by a class of functions when observations are dependent through an underlying graph.

In the IID setting, maximal inequalities are among the cornerstones of empirical process theory. They provide the probabilistic control behind Glivenko--Cantelli, or uniform laws of large numbers, and Donsker-type results (see, e.g., VdV-W1996). They also underlie strong approximations (see, e.g., DudleyPhilipp1983) and stochastic equicontinuity. These results, in turn, are central to the asymptotic analysis of M- and GMM-estimators in Statistics and Econometrics (see, e.g., NeweyMcFadden1994).

While this theory is well developed for IID data, results for other data structures are more limited. For time series, although the theory is less developed than in the IID case, several results are available under appropriate mixing conditions; see, e.g., DMR1995,yu1994rates,ChenShen1998,Pouzo2026. For graph-dependent data, however, the analogous theory remains much less complete. This gap is important because graph dependence arises naturally in social interactions, peer effects, spillovers, worker--firm mobility, trade, financial networks, input--output linkages, dyadic data, and many modern data-science applications.

In graph-dependent data settings, observations are neither independent nor ordered along a single time dimension. Dependence is organized by a graph, whose geometry affects the behavior of empirical averages. Thus, relative to both IID and time-series data, graph dependence combines stochastic and geometric features. In time series, the ordering of observations provides a canonical notion of past and future, while the line geometry tightly controls the number of observations at a given distance: each observation has at most two observations at any positive distance. Graphs, by contrast, need not have a natural ordering, and their geometry can vary substantially. The number of observations at a given graph distance may be small in sparse, low-growth graphs but may grow rapidly in highly connected networks. Thus, a theory for empirical-process tools over graph-dependent data must account jointly for function-class complexity, dependence decay, and graph geometry.

We take a step toward developing such a theory by providing a maximal inequality of the form

where $G_n=(N_n,V_n)$ is a finite graph with $\lvert N_n\rvert=n$ and edge set $V_n$, and $\mathcal F$ is a class of measurable functions. The bound separates the complexity of the function class, $\mathcal C(\mathcal F)$, from a rate component, $\mathrm{rate}_n$, that summarizes the sample size, graph geometry, and a graph-based coupling bound. It therefore provides a network analogue of classical IID --- wherein $\mathrm{rate}_{n} \asymp n^{-1/2}$ --- and time-series maximal inequalities while making explicit how the rate depends on graph structure.

The complexity measure $\mathcal C(\mathcal F)$ is based on Talagrand's generic chaining functionals (talagrand2005,talagrand2014) under the semimetrics induced by the empirical process. This choice isolates the contribution of the indexing class from the dependence and geometry of the data, and thus, once the graph-dependent stochastic component has been controlled, standard complexity calculations can therefore be applied directly. Moreover, as shown by talagrand2014, generic chaining provides a measure of the size of $\mathcal F$ that is tighter than classical measures such as those proposed by dudley_sizes_1967 and ossiander1987 and permits the use of existing bounds based on entropy, bracketing, VC-type, and smoothness conditions; see, for example, VdV-W1996,VanHandel2018,VanHandel2018b.

The rate component, $\mathrm{rate}_n$, reflects the interaction of three features, two of which are absent or substantially simpler in IID and time-series settings: sample size, graph geometry, and stochastic dependence across graph-separated collections of observations.

The role of graph geometry can be understood by comparison with the standard blocking argument for time series. There, the natural ordering permits one to divide the sample into consecutive blocks and then separate them into, for example, odd and even subcollections. Within each subcollection, successive blocks are separated by an intervening block, so dependence can be controlled by a coupling argument using known mixing coefficients like $\beta$-mixing (e.g. DMR1995,yu1994rates) or $\tau$-mixing (e.g., dedecker2006inequalities,Pouzo2026). This construction relies on the one-dimensional ordering of time. For a general graph, there is no analogous canonical ordering of observations or natural notion of odd and even blocks.

Our approach replaces this ordering device with color classes. Given a partition of the node set into blocks, color classes group blocks so that any two blocks in the same class are separated by more than a prescribed graph distance. Thus, each color class plays the role of one of the interlaced block sequences in a time-series blocking argument. This construction permits the replacement of the original blocks by coupled copies that are mutually independent within each color class. The number of colors required is itself a geometric object: it depends on the expansion of graph neighborhoods and on the chosen block partition. The resulting rate therefore records the geometric cost of decomposing the graph into approximately independent pieces, a cost that is simple in the IID and time-series cases but must be explicitly controlled for general graphs.

Graph geometry also affects dependence within blocks. For a block $B$, the relevant variance depends not only on $\lvert B\rvert$, but also on the distribution of pairs of nodes across graph distances. Because dependence is typically stronger at short distances, two blocks of equal size can have different variances when one contains many more nearby pairs than the other. Thus, the graph-geometric component of the maximal inequality depends jointly on block size, the coloring number, and the within-block distribution of pairs of nodes.

This aspect is again simpler for time series. Consecutive intervals are natural blocks, and their coloring number and within-block shell profile are essentially determined by the line geometry. For general graphs, neither is automatic: neighborhoods may grow polynomially, exponentially, or irregularly; a block may conflict with many other blocks; and its shell profile need not be controlled by its cardinality alone. The maximal inequality makes these geometric features explicit.

The third component of the rate is, to our knowledge, a novel graph-based coupling error. Our construction relies on the $\tau$-dependence coefficient of dedecker2006inequalities. Within each color class, the blocks can be ordered and each original block is replaced by a copy with the same marginal distribution that is independent of the preceding blocks in that class. The average cost of this replacement is measured by a new graph-based $\tau$-dependence coefficient. This coefficient is defined relative to a metric induced by the function class and has an optimal transport interpretation: it is the minimal expected transportation cost required to replace a block by an independent copy while preserving its marginal law. The coupling result therefore converts graph-local dependence into exact within-color-class independence with an explicit approximation error.

The use of $\tau$-dependence is consequential. The $\tau$ coefficient is defined through Lipschitz test functions and is closely related to a Wasserstein--$1$, or Kantorovich--Rubinstein, distance between the conditional and unconditional laws of a block. It is weaker than absolute regularity: decay of the $\beta$-mixing coefficient implies decay of the corresponding $\tau$ coefficient under appropriate moment conditions, whereas the converse generally fails --- for instance, contractive autoregressive processes with discrete innovations; see, e.g., dedecker2004coupling,dedecker2005new,dedecker2006inequalities,doukhan2008weakly for more examples and a more thorough discussion.

Combining these ingredients yields a maximal inequality of the form (ref), in which the complexity of the indexing class is separated from the graph-geometric and stochastic-dependence components. We specialize the inequality to several canonical graph regimes: graphs with controlled polynomial growth, graphs with exponential growth, and directed dyadic graphs. These results show explicitly how the maximal-inequality rate changes with the expansion properties and local geometry of the underlying graph.

We further use the maximal inequality to establish Glivenko--Cantelli results for graph-dependent data and to characterize the effective sample size implied by different graph structures and dependence patterns. Finally, we verify the required coupling bounds in several models that arise in applications, including network autoregressive models, nonlinear local-propagation models, and treatment-effect models with network interference.

Taken together, the results establish that there is no graph-independent empirical-process rate. The relevant rate is jointly determined by function-class complexity, graph geometry, and the rate at which stochastic dependence decays with graph distance, as captured by the cost of coupling separated blocks to independent copies.

\paragraph{Related Literature.} There is an extensive literature establishing asymptotic results for spatial random fields (see Guyon1995 for a review), but its usual fixed-dimensional Euclidean indexing framework does not encompass general graph-dependent data, whose shortest-path geometry need not admit an isometric embedding into such a space and may exhibit substantially different neighborhood growth. A recent and growing literature has begun to bridge this gap by establishing pointwise laws of large numbers and central limit theorems for graph- or network-dependent data. JenishPrucha2009 establish central limit theorems for nonstationary, possibly heterogeneous arrays of $\alpha$- and $\phi$-mixing spatial random fields observed on irregular subsets of a fixed-dimensional Euclidean space. Kuersteiner2019 establish law of large numbers and a stable central limit theorem for network statistics under a conditional spatial mixingale-type condition based on a model-dependent random notion of distance. ChandrasekharJacksonMcCormickThiyageswaran2024 instead provide covariance-based sufficient conditions for a central limit theorem for general dependent triangular arrays. LeungMoon2026 derive a normal approximation for network statistics in generalized random-geometric graphs under a stabilization condition: each statistic is determined by a random local neighborhood whose size is controlled in probability. The contribution closest to ours is KOJEVNIKOV2021882, who use the conditional $\psi$-dependence framework of DOUKHAN1999 to control covariances between nonlinear functions of graph-separated collections of observations. kojevnikov2021 complements these results by establishing bootstrap validity for network-dependent data.

Our objective and method differ materially. Whereas KOJEVNIKOV2021882 and related work provide pointwise results, we derive a maximal inequality that controls the empirical process uniformly over a possibly infinite class $\mathcal F$. This requires separate control of the complexity of $\mathcal F$ through generic chaining, which pointwise covariance bounds do not provide. Their framework also permits conditioning on a “common shock,” unlike ours; extending our approach in this direction is outside the scope of this paper. Methodologically, rather than bounding covariances directly, we provide a coupling result. This permits the use of exponential inequalities and generic chaining, while making explicit the separate roles of function-class complexity, within-block graph geometry, the coloring cost, and dependence across graph-separated blocks.

Regarding uniform asymptotic results, the literature is, to our knowledge, more sparse. In the spatial random-field setting, JenishPrucha2009 derive a generic ULLN and sufficient conditions for stochastic equicontinuity under $\alpha$- and $\phi$-mixing, but only for observations indexed by irregular subsets of a fixed-dimensional Euclidean space. For graph-dependent data, sasaki2026gmmmestimationnetwork establish a ULLN for finite-dimensional parameter-indexed classes under the conditional $\psi$-dependence framework of KOJEVNIKOV2021882, combining a pointwise LLN with compactness, a high-level uniform equicontinuity condition, and a finite-net approximation. This condition excludes classes whose modulus of continuity depends on realized data, including quadratic-loss and other unbounded criterion functions. Our maximal inequality may relax such restrictions by directly controlling the empirical process over a function class. CaoLeung2025 establish stochastic equicontinuity for double/debiased machine learning under metric-space dependence, combining $\beta$-mixing with neighborhood stability of the learned nuisance function to avoid cross-fitting. Their objective differs from ours which is a maximal inequality for empirical process uniformly over a possibly infinite function class. Like us, they use a coupling argument, but rely on $\beta$-dependence and Berbee's lemma. Our construction instead uses the weaker Lipschitz-based notion of $\tau$-dependence and makes graph geometry explicit, which may permit extensions to weaker dependence conditions or more general score classes.

Setup

\paragraph{Graph-dependent data.} Let \(G_n=(N_n,V_n)\) be a finite graph with vertex set \(N_n : = \{1,\ldots,n\}\) and edge set \(V_n\). Let $(Z_i)_{i\in N_n}$ be a collection of random elements each taking values in a Polish space \((\mathsf{Z}, \mathcal Z)\). The data $(Z_i)_{i\in N_n}$ is drawn from $\mathbb P$, a probability measure on \((\mathsf{Z}, \mathcal Z)\). We use $\mathbb E$ to denote the expectation and $P_{Z}$ to denote the marginal distribution of $Z$.

\paragraph{Graph distance.} For \(i,j\in N_n\), define the graph distance as the shortest path between them: \[ d_n(i,j) : = \inf\{ k\ge 0:\ \exists (i_0,\dots,i_k),\ i_0=i,\ i_k=j,\ (i_{\ell-1},i_\ell)\in V_n\}. \] If no path exists, set \(d_n(i,j)=+\infty\). In addition, by convention, we set $d_{n}(i,i) = 0$. For any $A,B \subseteq N_n$, define the distance between them by $d_n(A,B):=\inf_{i\in A,j\in B} d_n(i,j)$.

We assume that for any disjoint subsets \(A,B\subseteq N_n\), if $d_n(A,B) = + \infty$ then $\sigma(Z_i:i\in A) \ \text{is independent of}\ \sigma(Z_j:j\in B)$.

\paragraph{Function class and empirical process.} The empirical process is defined as

over a class $\mathcal F$ of real-valued measurable functions on $\mathsf Z$.

\(\tau\)-mixing on graph-dependent data

We now introduce a notion of $\tau$-mixing for graph-dependent data. The construction requires two ingredients. The first is a measure of dependence between a random element and a sigma-field. The second is a geometric device that identifies collections of blocks that are mutually well separated in the graph. We use a proper coloring of a block partition for the latter purpose.

\paragraph{$\tau$-mixing coefficient.} We first recall the definition of the $\tau$-mixing coefficient on a generic metric space; see dedecker2006inequalities. Let $(\mathsf X,\mathcal X)$ be a Polish space equipped with a pseudometric $d_{\mathsf X}$, let $X$ be an $\mathsf X$-valued random element, and let $\mathcal M$ be a sub-sigma-field. Suppose that, for some $x_0\in\mathsf X$, $\mathbb E\left[ d_{\mathsf X}(X,x_0) \right] < \infty$. The $\tau$-coefficient between $\mathcal M$ and $X$ is \footnote{Let $\operatorname{Lip}_1(\mathsf X,d_{\mathsf X})$ denote the class of measurable functions $g:\mathsf X\to\mathbb R$ satisfying $ |g(x)-g(x')| \le d_{\mathsf X}(x,x')$ for all $x,x'\in\mathsf X$. }

The coefficient in (ref) measures the extent to which the conditional distribution of $X$ given $\mathcal M$ differs from its marginal distribution, where the discrepancy is evaluated against Lipschitz test functions.

This notion is weaker than measuring discrepancy against all bounded measurable functions, as in the usual $\beta$-mixing coefficient. In particular, when $d_{\mathsf X}$ is bounded, $\tau_{d_{\mathsf X}}(\mathcal M,X)$ is dominated, up to the conventional normalization constant, by the corresponding $\beta$-mixing coefficient. The weaker Lipschitz requirement is useful for processes for which total-variation-based dependence does not decay, but Wasserstein-type dependence does decay with separation; for instance, for processes with discrete outcomes, the $\beta$-mixing coefficient remains bounded away from zero, whereas the $\tau$-mixing coefficient can be made to be arbitrarily close to zero provided $\mathcal{M}$ and $X$ are “sufficiently separated" (see dedecker2002maximal,dedecker2004coupling,dedecker2005new,dedecker2006inequalities for formal results and discussion in the time series context).

\paragraph{Block partitions and graph colorings.} In this paper, we apply the notion of $\tau$-mixing to blocks of graph-dependent random variables of the form $Z_{B} := (Z_{i_1},\dots,Z_{i_m}) \in \mathsf{Z}^{m}$ for some blocks \(B=\{i_1,\dots,i_m\}\subseteq N_n\). Unlike time series, where there is a clear direction in terms of past and future, graphs do not supply a canonical temporal ordering. To tackle this issue we employ the notion of coloring classes. Let $\mathcal P_{N_n,M} = \left\{ B_1,\ldots,B_M \right\}$ be a partition of $N_n$ into $M$ nonempty blocks.

The sets $\{ C_1,\ldots, C_K\}$ are called color classes. A color class collects blocks that are pairwise separated by graph distance strictly greater than $r$. For every $k\in[K]$, write the elements of $ C_k$ in increasing order as

The order in (ref) does not represent a causal or geometric direction in the graph, but is useful to construct a sequential coupling of the blocks in each color class. For every $k\in[K]$ and $\ell\in[L_k]$, define the within-class predecessor set of the $\ell$-th block by

with the convention that $\operatorname{Pred}_{1}( C_k) = \varnothing$. Thus, $\operatorname{Pred}_{\ell}( C_k)$ is the union of the blocks in $ C_k$ that precede $B_{m_{k,\ell}}$ under the ordering in (ref) and are “well-separated" in the sense that, if $\ell\ge2$, $d_n\left( \operatorname{Pred}_{\ell}( C_k), B_{m_{k,\ell}} \right) > r$.

\paragraph{Coloring-adapted $\tau$-coefficients.} Let $\mathcal B\subseteq\mathcal F$. For every $m\in\mathbb N$, equip $\mathsf Z^m$ with the pseudometric

The coefficient inside the sums in (ref) is the block-level $\tau$-dependence between $Z_{B_{m_{k,\ell}}}$ and the sigma-field generated by its within-class predecessors.

The coefficient $\bar{\tau}_{\mathcal B,G_n}$ is therefore an average of the actual coupling costs generated by the given partition and coloring. This average is the natural aggregation for the goal of the present paper that is to provide a coupling argument used for empirical processes --- this claim becomes apparent in the proof of Lemma (ref), where the block-specific coupling errors are summed over the partition.

A perhaps more widely applicable measure, not tailored to empirical processes, is one that does not rely on the average and provides a bound uniform over color classes:

Finally, yet another alternative measure is given by a version that is uniform over every $r$-coloring with maximal size block given by $q$,

for any $r\ge0$ and $q\in\mathbb N$.

For every $q\ge\max_{m\in[M]}|B_m|$, the preceding coefficients satisfy

The first inequality follows because $\bar{\tau}_{\mathcal B,G_n}$ is a weighted average of the normalized block-level coefficients appearing in $\tau^{\mathrm{max}}_{\mathcal B,G_n}$. The second follows because the predecessor set $\operatorname{Pred}_{\ell}(C_k)$ and the block $B_{m_{k,\ell}}$ are separated by graph distance strictly greater than $r$.\footnote{The term corresponding to $\ell=1$ is zero because its predecessor sigma-field is trivial.}

The three coefficients differ in the extent to which they are tailored to the coupling construction. The coefficient $\bar{\tau}_{\mathcal B,G_n}$ is the average of the block-specific coupling costs induced by the chosen partition, coloring, and within-class ordering; it is therefore the sharpest quantity for our maximal inequality. The coefficient $\tau^{\max}_{\mathcal B,G_n}$ replaces this average by a uniform bound over the blocks of the same construction. Finally, $\tau_{\mathcal B,G_n}(r,q)$ is uniform over all graph-separated pairs of sets with second component of cardinality at most $q$. It is consequently the most convenient primitive condition, but may be conservative because it ignores the particular predecessor sets generated by the coloring.

\paragraph{Coupling.} By the results of dedecker2006inequalities, like the $\beta$-mixing coefficient, the $\tau$-dependence coefficient admits an optimal-transport interpretation through minimal couplings, which is useful for the implementation of our results. Formally, \[ \tau_{d_{\mathsf{X}}}(\mathcal M,X) = \inf \Big\{ \mathbb E [ d(X',X) ] \colon X' \stackrel{d}{=} X,\; X' \perp\!\!\!\perp \mathcal M \Big\}. \] That is, the $\tau$-coefficient in ((ref)) is the minimal transportation cost needed to replace $X$ by an independent copy $X'$ while preserving its marginal distribution. So, letting $$\mathcal F^{m_{k,\ell} - 1}_{C_{k}} : = \sigma\left( Z_j: j\in\operatorname{Pred}_{\ell}( C_k) \right),$$

A similar result holds for $\tau^{\mathrm{max}}_{\mathcal B,G_n}$ and also

Coupling Result

This section presents a coupling result that replaces $(Z_i)_{i\in N_n}$ by a coupled process $(Z_i^\ast)_{i\in N_n}$ whose blocks are mutually independent within each color class, while providing explicit and uniform control of the resulting coupling error. Henceforth, let $\Pr$ denote the joint law on the extension supporting the original and coupled processes, and let $\mathbb E_{\Pr}$ denote expectation under this law.

Theorem (ref) provides a blockwise decoupling device for graph-dependent data. Given a partition of the nodes, $\{B_{1},...,B_{M}\}$, and a proper $r$-coloring, $\{C_{1} , ... , C_{K} \}$, it constructs a coupled array $(Z_i^\ast)_{i\in N_n}$ with three properties.

The first part ensures that each block $Z_{B_m}^\ast$ preserves exactly the same distribution as the original block $Z_{B_m}$. Hence, the coupling does not distort the marginal behavior within blocks.

The second part yields that, within each color class $C_k$, the coupled blocks $\{Z_{B_m}^\ast : m\in C_k\}$ are mutually independent. Thus, after coloring, the dependent array can be decomposed into $K$ subcollections that behave as independent block sequences.

The last part quantifies the approximation error induced by the coupling. The expected discrepancy between the original and coupled block, measured in $d_{\mathcal B,|B_m|}$, is exactly the $\tau$-dependence coefficient relative to the past blocks in the same color class. This error is uniformly bounded by $\tau_{\mathcal B,G_n}(r,q)$, which depends only on the separation radius $r$ and the maximal block size $q$.

Expression (ref) in part 3 is the implication we used to obtain maximal inequalities. The LHS presents the relevant notion of distance between the original and coupled process implied by the empirical processes. The RHS is our $\tau$-dependence coefficient defined in expression (ref). Expression (ref) is the basis of expression (ref) and is a direct consequence of the minimal coupling representation of the $\tau$-coefficient (see expressions (ref)-(ref) above). It implies that, for each color class $C_k$ and each $m\in C_k$, the variable $Z_{B_m}^\ast$ is constructed as a minimizer of this problem with $\mathcal M = \mathcal F^{m-1}_{C_k}$ and $X = Z_{B_m}$.

The minimal-coupling representation is useful because it facilitates bounds on $\mathbb E\!\left[ d_{\mathcal{B},|B_m|}\!\left(Z_{B_m}^\ast,Z_{B_m}\right) \right]$ by just constructing some coupling --- something that in most applications is not hard to do; see the examples below in Section (ref) and the examples in dedecker2004coupling in the time series context.

Henceforth, we use $\mathbb P^{\ast}$ and $\mathbb E^{\ast}$ to denote the probability measure and expectation corresponding to the stochastic process $(Z^{\ast}_{i})_{i}$.

Maximal Inequality

In this section we derive a maximal inequality for the empirical process $\mathbb{G}_n(f) = \frac{1}{\sqrt{n}} \sum_{i\in N_n} \Big( f(Z_i) - \mathbb{E}[f(Z_i)] \Big)$ over a class of measurable functions \(f:\mathsf Z\to\mathbb R\) denoted by \(\mathcal F\).

To state the result, we define the metric we endow $\mathcal{F}$ with and the corresponding complexity measure.

\paragraph{Talagrand's measure of complexity.} Let $\mathcal B \subseteq \mathcal F$ and $r>0$. A sequence of partitions $T^\infty := (T_l)_{l\in \mathbb{N}_0}$ is called an admissible partition sequence of order $r$ for $\mathcal B$ if:

Let $\mathcal T_r(\mathcal B)$ denote the collection of all such admissible partition sequences.

For any $f \in \mathcal B$ and $l\in\mathbb{N}_0$, let $T(f,T_l)$ be the unique element of $T_l$ containing $f$, and let \[ z \mapsto D(f,T_l)(z) := \sup_{f_1,f_2 \in T(f,T_l)} |f_1(z) - f_2(z)| \] be the diameter function associated to it.

\paragraph{Graph-induced semi-norms over $\mathcal F$.} Dating back at least to Dudley-1967, the natural metric for measuring the complexity of a function class is the one dictated by the concentration behavior of the associated empirical process. In the present setting, the empirical process is approximated by the color-wise block independent process constructed in Theorem (ref) and the relevant concentration inequality is the Bernstein inequality (presented in Lemma (ref) below). Consequently, the appropriate distances over $\mathcal F$ are those that separately control the two quantities entering that inequality: a variance component of the block independent process and a uniform boundedness component.

For time series, the variance component is typically measured through the standard deviation of partial sums over blocks of consecutive observations. For a block $B = \{ 1,..., L \}$ of length $L$, this quantity takes the form $\sqrt{ \operatorname{Var} \left( L^{-1/2} \sum_{l=1}^{L} g(Z_{l}) \right) }$. Under stationarity and suitable mixing conditions, one can use Theorem 1.1 in rio2017asymptotic to obtain, for $p\geq 1$,

where

is the $\alpha$-mixing coefficient as in rio2017asymptotic expression 1.8a.\footnote{This formulation of the $\alpha$-coefficient is no larger than the standard one and in some cases is non-trivially smaller. To see this observe that the standard one can be taken as $\sup_{f,g} |\operatorname{Cov}(f(Z_{i}),g(Z_{j}))|$ where the supremum is over the class of bounded (by one) measurable functions. On the other hand, in the present formulation of $\alpha$ the supremum is taken over the class given by $BV_{1} \circ \mathcal F$, which is no larger, and in some cases strictly smaller than the former class.} The right-hand side of (ref) therefore induces the relevant metric for the chaining argument.

We follow the same principle in this paper, but the graph structure changes the geometry of the variance term. Blocks are no longer intervals of consecutive observations. Instead, they are elements $B$ of a partition of the node set $N_n$. Thus the object to be controlled is $\sqrt{ \operatorname{Var} \left( |B|^{-1/2} \sum_{i\in B} g(Z_i) \right) }$, and, in contrast to the stationary time-series case, there is generally no translation-invariant structure that reduces this expression to a function of the block length alone.

A second difference is that graph distance is no longer one-dimensional. In a time series, the distance between observations $i$ and $j$ is simply $|i-j|$, and the number of observations at any fixed distance from a given point is uniformly bounded by two. In general graphs, distance is given by $d_n$, and, as we shall see in detail in Section (ref) below, the number of node pairs inside a block at each distance can vary substantially. Since dependence is typically stronger at shorter graph distances, blocks with many pairs at small distances have larger variance than blocks whose pairs are mostly far apart. The graph-induced norm must therefore account not only for the size of the block, but also for how its pairwise distances are distributed.

As iwill become apparent from the proof of Lemma (ref) below, the appropriate quantity for capturing this feature is the so-called within-block distance neighbor pair profile: For any block $B$, the within-block $B$ distance neighbor pair profile is

and $|S_{B}(r)|$ is the count of neighbor pairs at distance $r$.

The following result formalizes these observations and provides a natural (pseudo) metric for graph-dependent data.\footnote{Here are throughout, $\lesssim$ denotes “less or equal than up to universal constants".}

Henceforth, for any $n \in \mathbb{N}$, any $p \in [1,\infty]$, and any $B \subseteq N_{n}$, let

This quantity is a within-block $B$ dependence factor. It summarizes the combined effect of two features of the block \(B\): the number of within-block $r$-distance neighbor pairs, measured by \(|S_B(r)| \) and the strength of dependence at distance \(r\), measured by \(\alpha_{\mathcal F,B}(r)\), for all possible distances in $B$. Thus, \(\Gamma_p(B)\) controls the variance inflation generated by local network dependence inside \(B\).

\paragraph{Maximal inequality.} We are now in position to state the maximal inequality.

This theorem is the generalization of Theorem 1 in Pouzo2026 for time series to graph-dependent data. In time series, the maximal inequality is controlled by the generic chaining complexity of the class and the relevant marginal norms. The present result preserves that structure but extends it to general graph-dependent data by introducing two additional objects: a graph-coloring device, which separates approximately independent blocks, and dependence coefficients, which control the error from replacing the original process by blockwise independent approximations.

Since the partition and the coloring are arbitrary and the left-hand side does not depend on either of them, the bound may be optimized over all admissible choices by minimizing the right-hand side over all partitions $\{B_m\}_{m=1}^{M}$ and over all admissible $r$-colorings of the induced block graph. In practice, carrying out this minimization may be impractical. But, it is enough to find one partition and coloring for which the resulting geometric and dependence terms are controlled.

Another relevant feature of the bound is that its components separate three distinct sources. The first source is the size of the function class, measured by the generic chaining functionals $\gamma_{2,a}\left(\mathcal F,\max_{i\in N_n} ||\cdot||_{L^{2p}(P_{Z_i})}\right)$ and $\gamma_{1,b}(\mathcal F,||\cdot||_\infty)$, these are standard complexity measures, introduced by Talagrand (cf. talagrand2005,talagrand2014), further developed and used in several papers (e.g., VanHandel2018,VanHandel2018b), and bounded above by classical entropy quantities such as Dudley’s entropy integral (see talagrand2014). The second source is the geometry of the graph and of the chosen block partition. This is summarized by the block size $q_n$, the $r_n$ coloring and its chromatic number $K_n$, and the within-block distance neighbor pair profile, $S_{B_m}$. The third source is the mixing structure. This enters in two distinct ways: one captured by the $\tau$-coefficient, and another, local within-block dependence, captured by the within-block dependence factor, $\Gamma_p(B_m)$. The latter combines the within-block distance neighbor-pair profile with the decay of the $\alpha$-mixing coefficients.

Consequently, the theorem reduces the problem of proving a maximal inequality to three tasks: bounding the chaining complexity of $\mathcal F$, constructing a block partition with a manageable $r_n$-chromatic number and distribution of within-block distance neighbor pairs, and verifying sufficient decay of the $\tau$-mixing and within-block $\alpha$-mixing coefficients.

The next section discusses further the first two tasks which appear to be novel and intrinsic to the graph-dependent data --- bounds on the $\tau$-mixing coefficient are also discussed in the examples in Section (ref).\footnote{For the first task, bounding the complexity measures, one can rely on existing literature: talagrand2005,talagrand2014 shows that these complexity measures can be bounded by commonly used measures like Dudley's entropy and Ossiander's bracketing (see VdV-W1996), in addition Talagrand's work also shows that under some conditions on $\mathcal F$ and the norm used the complexity measure can be bound by the supremum of a Gaussian process; see also Pouzo2026 for a discussion on how to apply this to empirical processes with time series data. Also, VanHandel2018,VanHandel2018b proposes a series of results where, under the some conditions on $\mathcal F$, the complexity measures can be bounded by quantities depending on entropy numbers of “simple sets".}

Geometric Structure of Graphs

The biggest difference between the bounds obtained for IID and time series data (e.g., see talagrand2014 and Pouzo2026) and the one in Theorem (ref) is due to the intrinsic “geometric structure" of the time series graph. In the time series setting $N_{n} \subseteq \mathbb{Z}$ and $d_n(i,j)=|i-j|$, giving the graph a clear geometric structure.

This structure suggests the partition into consecutive blocks,

(we assume that $qM = n$ for simplicity). Given an $r \geq 1$, blocks that conflict at radius $r$ are precisely those with sufficiently nearby indices. Indeed, any blocks $B_{m},B_{\ell}$ have distance $d_n(B_m,B_{\ell}) = \max\{0,\; (|m-\ell|-1)q\}+1$. Hence, if they are within $r$ of each other then

For a radius \(r\ge 0\), define the conflict graph $H_{n,r}=([M],E_{n,r})$ by

Thus two blocks are adjacent in \(H_{n,r}\) whenever they are within time distance \(r\). For nonadjacent block indices, this implies $\bigl(|m-\ell|-1\bigr)q+1 \le r$, and therefore $|m-\ell| \le 1+\frac{r-1}{q} \le 1+\frac{r}{q}$. Thus, every block $B_m$ can conflict only with blocks whose indices lie within approximately $1+r/q$ positions to its left or right.

Hence, for each $m\in[M]$, $\deg_{H_{n,r}}(m) \le 2\left\lfloor 1+\frac{r-1}{q} \right\rfloor \lesssim 1+\frac rq$, which readily implies that the maximal degree of the conflict graph satisfies $\Delta(H_{n,r}) \lesssim 1+\frac{r}{q}$. This and the greedy coloring bound imply $\chi(H_{n,r}) \le 1+\Delta(H_{n,r}) \lesssim 1+\frac{r}{q}$. In particular, if $K_{n,r}$ denotes the $r$-chromatic number,

Next, consider the average within-block $\rho$-distance count. For a block \(B_m\), since \(B_m\) has length \(q\), $|S_{B_m}(0)| = q$, and, for \(1\le \rho\le q-1\), $|S_{B_m}(\rho)| = 2(q-\rho)$, where the factor \(2\) comes from ordered pairs \((i,j)\) and \((j,i)\). Hence $\frac{|S_{B_m}(0)|}{|B_m|} = 1$, and, for \(1\le \rho\le q-1\), $\frac{|S_{B_m}(\rho)|}{|B_m|} = 2\left(1-\frac{\rho}{q}\right) \le 2$. Therefore, uniformly over blocks and distances, the average within-block $\rho$-distance count is bounded:

By inputting these bounds into Theorem (ref) and setting $q_{n}=r_{n}$ we obtain (up to constants) Theorem 1 in Pouzo2026.

The following examples show how departures from the line geometry affect the two geometric ingredients in Theorem (ref): the coloring cost and the within-block shell profile.

\paragraph{ Uniform doubling graphs with polynomial growth.} The next result isolates the key geometric features of a time series graphs to obtain sufficient conditions that deliver a result analogous to the time series one but for a larger class of graphs which we call uniform doubling with polynomial growth of dimension $d$.

A sequence of metric spaces $(X_n,d_n)_n$ is uniformly doubling metric space with dimension $d$ if there exists a constant $C_{\mathrm{dbl}} < \infty$, independent of $n$, such that for every $x \in X_n$ and every $R>0$,

for some points $x_1,\dots,x_{C_{\mathrm{dbl}}} \in X_n$. The associated dimension is given by $d : = \log_{2} C_{\mathrm{dbl}}$.

The sequence $(X_n,d_n)_n$ is said to have polynomial (shell) growth if there exists a constant $C < \infty$, independent of $n$, such that

By combining this lemma and Theorem (ref), we obtain the following maximal inequality for the class of uniform doubling with polynomial growth graphs.

\paragraph{Exponential Growth Graphs.} We now analyze the maximal inequality for graphs that have more rapidly expanding neighborhoods than the class of polynomial growth graphs.

We say \(G_n=(N_n,V_n)\) has exponential (shell) growth with constant $a$ if there exist constants \(C,a>0\), independent of \(n\), such that

The next result specializes the maximal inequality in Theorem (ref) to this class of graphs.

\paragraph{Directed Dyadic Graphs.} We conclude this section by studying dyadic graphs that capture the dependence generated by the latent individual effects --- prominent examples include directed friendship nominations, bilateral trade flows, migration flows, communication networks, input--output linkages, and interbank exposures.

Formally, let $N_n := \{(i,j): i,j\in \{1,\ldots,n\},\ i\neq j\}$ denote the set of directed dyads. For each \((i,j)\in N_n\), suppose

where $\{\mu_i:1\leq i\leq n\}$ and $\{\varepsilon_{ij}:(i,j)\in N_n\}$ are mutually independent collections of IID random variables. The function \(F\) is measurable.

We endow \(N_n\) with the natural dyadic dependency graph \(G_n=(N_n,E_n)\), where two directed dyads are adjacent whenever they share at least one endpoint:

Therefore, \(d_n\) is such that $d_{n}((i,j),(k,l)) = 0$ if $(i,j) = (k,l)$, $d_{n}((i,j),(k,l)) = 1$ if $(i,j) \ne (k,l)$ but $\{i,j\}\cap\{k,\ell\}\neq\varnothing$, and $d_{n}((i,j),(k,l)) = 2$ otherwise.

The next lemma summarizes the relevant geometry and dependence of the graph.

Thus, in some sense, dyadic graphs are diametrically opposed to the time series case. For the time series case, $\tau_{\operatorname{cone} \mathcal F , G_{n}}$ has a non-trivial decay (except in particular cases like IID or M-dependent data), but, the structure related to the graph (e.g., coloring number, $K_{n}$, the within-block $B_{m}$ distance neighbor pair profile, $S_{B_{m}}$, etc) are trivial. On the other hand, for dyadic graphs, the dependence measure is trivial, but the within-block distance neighbor pair profile and chromatic number are unevenly distributed, heavily tilted towards low values of $r$.

The next result applies Theorem (ref) to this case of dyadic graphs.

Perhaps somewhat surprisingly, the the maximal inequality bound is completely analogous to an IID case, but where the effective sample size is of order $n$, not $n(n-1)$. Observe that the result holds for $p>1$. The reason for this is that for $p=1$ one obtains a worse bound because of the behavior of $\Gamma_{1}(\cdot)$ for our chosen partition.

Glivenko--Cantelli Results and Effective Sample Size

The purpose of this section is twofold. First, we employ Theorem (ref) to obtain Glivenko--Cantelli results over graph-dependent data. Second, we provide convergence rates and interpret them in terms of effective sample size. The main message is that, contrary to IID data, there is no universal Glivenko--Cantelli rate. The rate is determined jointly by graph geometry, local dependence, and the decay of long-range dependence.

A Glivenko--Cantelli result for graph-dependent data

For any finite partition \(T_{L}\) of \(\mathcal F\), with $|T_{L}| \leq 2^{2^{L}}$, let \(\Pi[T_{L}] : = (\pi_C)_{C \in T_{L}} \) be a representative class: For each $C \in T_{L}$, the element is such that $\pi_{C}$ for all $f \in C$, $\pi_{C} : = \pi_{L} f$. Also, let $ \mathcal D[T_{L}] := \{D_C \colon C \in T_{L}\}$ be the class of diameter functions,

We approximate $\mathcal F$ by a finite representative class and control the residual variation within each cell. The maximal inequality is applied to the representatives, while the average cell diameter controls the approximation error.

Theorem (ref) provides sufficient conditions over the class of function $\mathcal{F}$, as well as over the graph $G_{n}$, to support a uniform law of large numbers. The conditions require that the partition \( T_{L_n}\) must balance two requirements. Its representative class \(\Pi[ T_{L_n}]\) must be sufficiently small for the stochastic term to vanish, while its cells must be sufficiently fine for the mean cell oscillation to vanish.

One way to construct such a partition is to take $T_{L}$ as $(B_{||.||_{\infty}}(f_{j},\epsilon))_{j=[M]}$ where $\{f_{1},...,f_{M}\}$ is the $\epsilon$-packing of $\mathcal{F}$ under $||.||_{\infty}$ and $M : = M(\epsilon,\mathcal F, ||.||_{\infty})$ is the corresponding packing number. Under this choice, $|T_{L}| = M$ and $||D_{C}||_{\infty} \leq 2 \epsilon$, therefore the conditions hold provided that there exists a vanishing sequence $(\epsilon_{n})_{n}$ such that

These conditions are extensions of the “classical" Glivenko-Cantelli restriction, $ \frac{\log M(\epsilon_{n},\mathcal F, ||.||_{\infty})}{n} \to 0$ (cf. VdV-W1996) for IID data, to graph-dependent data.

On the other hand, if the Talagrand's measures of complexity are finite, one can verify the conditions in the theorem by simply choosing $T_{L}$ as member of the (approximate) minimizing admissible sequence. Under this choice $\sup_{C\in T_{L} } ||D_{C}||_{\infty} \lesssim \gamma_{1,b}(\mathcal F , || . ||_{\infty})/2^{L}$ and condition (ref) readily follows for any divering $L_{n}$, provided that the graph $G_{n}$ admits a partition and coloring such that $\frac{\sqrt{ K_{r_{n}} } }{\sqrt n} \max_{m\in[M_n]}\Gamma_p(B_m) \to 0$ and $\frac{K_{r_{n}} q_n}{n} + \bar{\tau}_{\operatorname{cone} \Pi[T_{L_{n}}] ,G_n} \left( \mathcal P_{n}, \mathcal C_{r_{n}}[\mathcal P_{n} ] \right) \to 0$.

Effective sample size

Theorems (ref) and (ref) provide more than a maximal inequality and a Glivenko--Cantelli result. They also provide a measure of the effective amount of independent information contained in a graph-dependent sample. In IID settings, empirical averages fluctuate at the rate \(n^{-1/2}\), and hence the effective sample size is the cardinality of the sample. For graph-dependent data, the rate need not be \(n^{-1/2}\). The graph may contain highly dependent local neighborhoods, and the number of approximately independent pieces of information may be much smaller than \(n\).

To shed more light on this claim, in this section we assume that there exists $a,b>0$ and $p \in [1,\infty]$ such that $\gamma_{2,a}(\mathcal F , \max_{i \in N_{n}} || . ||_{L^{2p}(P_{Z_{i}})})$ and $ \gamma_{1,b}(\mathcal F , || . ||_{\infty})$ are both finite.

Theorem (ref) suggests an effective sample size given by

for the partition and coloring ($\mathcal P_{n} : = \{B_{1},...,B_{M_{n}}\}, \mathcal C_{r_{n}}[\mathcal P_{n} ] $) that minimize the quantity in the parenthesis.

In the IID case, this expression is of order $n$, recovering the usual effective sample size. For time series data, if the mixing coefficient decays fast enough with $r=q$, then the effective sample size coincides with the IID (see, for example, DMR1995,yu1994rates for $\beta$-mixing), however, without this restriction, Pouzo2026 shows that the sample size can diverge much slower than the actual one.\footnote{The word “coincides" in the last sentence should be qualified. It is true that asymptotically the implied effective sample size and the actual sample size coincide, but in finite sample the former can be much smaller --- Pouzo2026 for an example and a more thorough discussion.}

For graph-dependent data this quantity is more nuanced: it depends on the graph structure and dependence structure through $\{ K_{r_{n}},\Gamma_p,q_{n}, \bar{\tau}_{ \operatorname{cone} \mathcal F , G_{n}} \}$. Thus, contrary to IID or time series data, large graphs (i.e., large number of observations) need not imply a large effective sample size. A graph with many nodes can still have a small effective sample size if neighborhoods expand rapidly, if many colors are required to separate blocks, or if dependence decays slowly.

We illustrate this claim by deriving the effective sample size associated to particular graph structures.

\paragraph{Polynomial-growth graphs.} Consider a sequence of uniformly doubling graphs with polynomial shell growth of dimension \(d\). As shown in Lemma (ref) for each \(q_n\) one can construct a partition satisfying $\max_m |B_m| \lesssim q_n$, $ \operatorname{diam}(B_m) \lesssim q_n^{1/d}$, and, for \(r_n=q_n^{1/d}\), $K_{r_{n}} = O(1)$. Thus, by Proposition (ref),

where \(\Lambda_{p,d}(q_n)\) summarizes the within-block distance profile and local dependence.

Polynomial growth prevents the number of nearby blocks from exploding too quickly, so the graph can be decomposed into a bounded number of approximately independent color classes. However, the slower the coupling term decays, the smaller the effective sample size is. For example, suppose $\tau_{\mathrm{cone} \mathcal F,G_n}(r,q) \lesssim r^{-\beta}$. Then $\tau_{\mathrm{cone} \mathcal F,G_n}(q_n^{1/d},q_n) \lesssim q_n^{-\beta/d}$ and the bound in (ref) becomes

If \(\Lambda_{p,d}(q_n)=O(1)\) --- e.g. there exists a $P_{0}$ as in Lemma (ref) and $\alpha_{ \mathcal{F} , B }$ decays sufficienly fast --- and there is a fast $\tau$-mixing rate (polynomial of at least $\beta/d \geq 1$), the IID effective sample size is achieved. However, for slower mixing, the effective sample size will be smaller --- ultimately, the resulting effective sample size depends on intra block dependence, on the mixing decay (exponent \(\beta\) and the graph dimension \(d\). However, as long as the data is $\tau$-mixing and there exists a diverging $(q_{n})_{n}$ such that $q_{n} = o(n)$ and $ \frac{\Lambda_{p,d}(q_n)}{\sqrt n} = o(1)$, then the effective sample size will diverge with $n$ and $(\mathcal F , G_{n})$ will be graph Glivenko--Cantelli.

\paragraph{Exponential growth graphs.} Graphs with exponential shell growth behave differently. Proposition (ref) implies

Due to the exponential growth, the trade-off between reducing the coupling error but increasing the chromatic number is more delicate. If $ \bar{\tau}_{ \operatorname{cone} \mathcal F , G_{n}}(r_{n}) \lesssim e^{-br}$, then $r_{n} \asymp \frac{\log n}{2b + a} $ balances both terms and $ \mathfrak{n}_{\mathrm{eff}}(\mathcal{F},G_{n}) \asymp n^{\frac{2b}{2b+a} }$, which is smaller than $n$. If there is only polynomial $\tau$-mixing, $ \bar{\tau}_{ \operatorname{cone} \mathcal F , G_{n}}(r_{n}) \lesssim r^{-b}$, then, $r_{n} \asymp a^{-1} \log n $ and $ \mathfrak{n}_{\mathrm{eff}}(\mathcal{F},G_{n}) \asymp \log n$. Hence, a graph Glivenko--Cantelli result still holds in this case, but the effective sample size grows only at logaritmic rate.

\paragraph{Directed dyadic graphs.} By Lemma (ref), this graph has diameter two and $ \tau_{\mathrm{cone} \mathcal F,G_n}(r,q) = 0 $ for $r \geq 2$. However, the local geometry is dense. A dyad has order \(n\) neighbors at distance one and order \(n^2\) dyads at distance two. Consequently, although there are \(n(n-1)\) observations, the effective amount of independent information is of order \(n\), not \(n^2\).

Indeed, by Proposition (ref) for any \(p>1\),

and since here \(|N_n|=n(n-1)\), $ \mathfrak{n}_{\mathrm{eff}}(\mathcal F , G_{n}) \asymp n $. Thus dyadic samples behave as if they contained order \(n\) independent observations. This is consistent with the latent structure of the model: although the number of dyads is of order \(n^2\), the dependence is generated by only \(n\) latent unit-level effects.

Examples

We now consider two illustrative examples. The first is a network autoregressive model, motivated by production networks, spatial autoregressions, and social-interaction models. In this case, a primitive shock can affect distant nodes through chains of network links. By exploiting a layered structure in the interaction matrix, we show $\tau$-coefficient decreases at a geometric rate. Combining this bound with the maximal inequality, we obtain a uniform law of large numbers and an effective-sample-size bound that depend on the maximal size of a production layer and on the number of relevant layers.

The second example is a nonlinear smooth local propagation model. This class includes network-interference models in which a unit's outcome depends on its own treatment and on treatment exposure among nearby nodes. Unlike the autoregressive model, dependence is nonlinear, but local. We show that the $\tau$-mixing coefficient vanishes beyond that radius and establish a maximal inequality results, which in the particular case of network-tretment effect interference models can be used to establish asymptotic properties of commonly used estimation techniques.

Network autoregressive model

\paragraph{Setup.} Consider a collection of firms indexed by $N_n$. Let $Z_i$ denote the log output of firm $i$, and write

The vector $\xi$ collects firm-specific primitive shocks. In the production-network interpretation, one may write $\xi_i = X_i^{\top}\beta+\eta_i$, where $X_i\in\mathbb R^p$ contains observable firm-level production shifters, such as factor prices, input availability, or demand conditions, and $\eta_i$ is an unobserved productivity or technology shock. We assume that $(\xi_i)_{i\in N_n}$ are IID across firms with $\sup_{i\in N_n} \mathbb E \left[ |\xi_i| \right] \leq M_{\xi} < \infty$.

Although the production-network interpretation is the leading example, the same specification also covers standard spatial autoregressive and social-interaction models. In those settings, $Z_i$ may be an outcome for a region or individual, $\xi_i$ a location- or individual-specific shock, and $w_{ij}$ a geographic, peer, or other interaction weight. Network autoregressive models of this form are standard in spatial econometrics and social-interaction models; see LeSagePace2009,BramoulleEtAl2009, and LiuEtAl2014. In the production-network setting, the relevant reference is AcemogluCarvalhoOzdaglarTahbazSalehi2012, who study the propagation of idiosyncratic shocks through input--output linkages.

In the production-network interpretation, the matrix $W=(w_{ij})_{i,j\in N_n}$ describes directed production linkages. In particular, $w_{ij}\neq 0$ means that the production state of firm $j$ affects the output of firm $i$. For example, $j$ may be an upstream supplier of intermediate inputs used by $i$, or a firm whose output enters the production technology of $i$. The weights need not be symmetric: generally, $w_{ij}\neq w_{ji}$. To connect the model to the network $G_n$, let $(i,j)\in V_n \Longleftrightarrow w_{ij}\neq 0 \text{ or } w_{ji}\neq 0$. That is, $G_n$ is the undirected skeleton of the directed production network. This graph records whether two firms are directly linked by a production relationship in either direction, while the direction and strength of the relationship remain encoded in $W$.

We impose

Under this condition, $I-\rho W$ is invertible and

Thus, a primitive shock to a supplier affects its direct customers through $W$, their customers through $W^2$, and so on. The contraction condition in (ref) guarantees that the cumulative effect of these propagation chains decays geometrically with their length.

We next impose a hierarchical restriction on the production network. We assume there is $L_{n}$ production layers, $N_n = \bigsqcup_{\ell=1}^{L_n}W_{\ell}$ --- for instance, level $1$: firms producing basic inputs, such as raw materials, energy, or generic intermediate goods; level $2$: firms transforming those inputs into components; and all the way to the last level which are firms producing final goods or distributing them downstream. We impose that for every $i\in W_\ell$ and $j\in W_u$,

That is, the integer $D$ is a uniform bound on the production distance covered by a direct input--output linkage: a firm may use inputs produced at its own layer or at one of the preceding $D$ layers, but cannot be directly linked to firms farther upstream or to downstream firms. Thus, the restriction on $W$ formalizes a locally layered production structure in which dependence can propagate across distant layers only through a sequence of intermediate supplier--customer links.

The goal is to bound provide a bound on $\tau$-mixing coefficient and on

This is useful for at least two reasons. First, if $\mathcal F$ is the normalized unit Lipschitz class, the displayed quantity is the Wasserstein-$1$ distance between the empirical cross-sectional distribution of firm outcomes and the average marginal distribution $\frac{1}{n} \sum_{i\in N_n} P_{Z_i}$. A bound therefore controls the distributional accuracy of the observed cross section, not merely the accuracy of finitely many moments. This is relevant here because firms need not share a common marginal distribution: downstream firms may be exposed to a larger set of propagated shocks than upstream firms. Second, $\mathcal F$ may be a family of welfare functions, $\mathcal F = \left\{ u_a: a\in\mathbb A \right\}$, where $a$ is a policy or structural parameter and $\sum_{i \in N_{n}} u_{a}(e^{Z_{i}})$ is a (additive) aggregate welfare associated to policy/parameter $a$. The same bound then delivers uniform control of the discrepancy between sample and population average welfare over all $a\in\mathbb A$.

We assume that $\mathsf Z\subset\mathbb R^{d_z}$ compact, and that for some $s>d_z$ and $L<\infty$, $\mathcal F \subseteq \mathcal H^s(L) := \left\{ f:\mathcal Z\to\mathbb R: \|f\|_{\mathbb C^s(\mathsf Z)} \leq L \right\}$. This assumption ensures that $\mathcal F$ belongs to the class of Lipschitz functions with constant $L$ and, by known results (see talagrand2014), for every $p\in[1,\infty]$,

(The implicit constants depend only on $a$, $b$, $d_z$, $s$, and $\mathsf Z$)

\paragraph{Natural partition and coloring.} The natural partition is that provided by the production layers, i.e.,

For any $r \geq 1$, the associated $r$-coloring is given by

where, for each $k\in[h_r]$, $C_k := \left\{ m\in[L_n]: m\equiv k \pmod{h_r} \right\}$ and $ h_r := Dr+1$.

Thus, the collection $\mathcal C_{r}[\mathcal P_{N_n,M}]$ is essentially a coloring of the production-layer partition at separation scale $r$. For each set $C_k$ any two distinct layers in it are separated by at least $h_{r} = Dr+1$ production layers. Since a single nonzero link in $W$ can span at most $D$ layers, a shock must traverse at least $r+1$ links to propagate between two layers in the same color class. Removing empty sets simply ensures that $K_r$ counts only colors actually used by the finite collection of layers.

There are $h_r$ “residue classes modulo $h_r$", so the construction yields at most $h_{r}$ nonempty color classes. Since each nonempty color class contains at least one of the $L_n$ layers, it also follows that $K_r\leq L_n$. Therefore,

\paragraph{$\tau$-mixing.} We now show that, given our choice of paritition of $G_{n}$ and coloring,

Fix $r\geq1$ and a color class $C_k$. Let $m_{k,1} < \cdots < m_{k,L_k}$ denote the elements of this class.

By construction of our coloring, for any $\ell \in [L_k]$, the set of predecessors of the production layer with index $m_{k,\ell}$ is included in the set of production layers at least $h_{r}$ layers down. I.e., $ \operatorname{Pred}_{\ell} \left( C_k \right) \subseteq \bigcup_{u=1}^{m_{k,\ell}-h_r} W_u = : A_{m_{k,\ell},r}$.

The restriction in $W$ implies that, if firm $j$ belongs to the $m(j)$ production layer, then $Z_j$ is measurable with respect to $\sigma\left( \xi_v: v\in \bigcup_{u=1}^{m(j)}W_u \right)$. This observaton and the previous one imply that $\sigma \left( Z_j: j\in \operatorname{Pred}_{\ell} \left( C_k \right) \right) \subseteq \sigma \left( \xi_j: j\in A_{m_{k,\ell},r} \right)$.

Therefore, to generate a coupling of the firm outputs that is independence of $\operatorname{Pred}_{\ell} \left( C_k \right)$, it suffices to construct one that is independent of $A_{m_{k,\ell},r}$. To achieve this, let $(\xi_i')_{i\in N_n}$ be an independent copy of $(\xi_i)_{i\in N_n}$ and define

It is clear that $ Z_{B_m}^\star \perp\!\!\!\perp \sigma \left( Z_j: j\in \operatorname{Pred}_{\ell} \left( C_k \right) \right)$.

Since every element of $A_{m_{k,\ell},r}$ belongs to a block with index at most $m-h_r = m-Dr-1$. The restriction on $W$ implies that a propagation chain of length $s\leq r$ can move forward by at most $sD\leq rD$ block indices. Thus, for any $i \in W_{m_{k,\ell}}$ and $j \in A_{m_{k,\ell},r}$, it follows that $[W^s]_{ij}=0$ for any $s \leq r$. Consequently,

Since $W$ is nonnegative and has maximal row sum bounded by $\kappa$, $\sum_{j\in N_n} (W^s)_{ij} \leq \kappa^s$. Hence,

By the Lipschitz property of $\mathcal F$, $d_{\mathcal F,|W_m|} \left( Z_{W_m}, Z_{W_m}^{k,\ell} \right) \leq L \sum_{i\in W_m} \left| Z_i-Z_i^{k,\ell} \right|$. By the minimal coupling result in Theorem (ref),

And this in turn implies $\tau^{\mathrm{max}}_{\mathcal F,G_n} \left( \mathcal P_{N_n,M}, \mathcal C_{r,K}[\mathcal P_{N_n,M}] \right) \leq \frac{ 2L M_\xi }{ 1-\rho \kappa } (\rho \kappa)^{r+1}$, which proves expression (ref).

\paragraph{Maximal inequality.} Given our choice of partition and coloring and expressions (ref) and (ref) it follows from Theorem (ref), for every $a,b>0$ and $p\in[1,\infty]$,

for any $r_{n}$.

By using the (admittedly crude) bound of $\Gamma_p(W_{m}) \leq \sqrt{q_{n}}$ for $p=1$; expression (ref) that ensures finite Talagrand measures of complexity; and by choosing $r_n = \left\lceil \frac{ \log n }{ 2|\log (\rho \kappa)| } \right\rceil$ to balance the terms, one obtains

Therefore, by Theorem (ref) the autoregressive network with a H\"older ball is graph Glivenko-Cantelli provided the maximal production layer size does not grow too fast, i.e., $ \frac{q_n\min\{\log n,L_n\} }{ n } = o(1)$, and it has an effective sample size satisfying the following bound $\mathfrak{n}_{\mathrm{eff}} \geq \frac{n}{q_n\min\{\log n,L_n\} }$.

Nonlinear smooth local propagation model

Setup

Let \((\varepsilon_j)_{j\in N_n}\) be IID primitive shocks, and suppose

for some $R > 0$ and $\mathcal N(i,R) : = \{ j \in N_{n} \colon d_{n}(i,j) \leq R \}$. Assume that the map \(H_i\) satisfies the coordinatewise Lipschitz bound

This model allows nonlinear propagation of shocks within a local neighborhood. The condition (ref) is a coordinatewise Lipschitz condition on the structural map \(H_i\). It requires the effect of perturbing the primitive shock vector to be bounded by the sum of the coordinatewise perturbations, with weights \(c_{ij}\). Thus \(c_{ij}\) measures the maximal sensitivity of observation \(i\) to the primitive shock at node \(j\). The local restriction that only shocks within distance $R$ can affect the outcome imposes network structure on these sensitivities: the influence of shock \(j\) on observation \(i\) is bounded by the graph distance \(d_n(i,j)\).

An important case is the network-interference model in estimation of treatment effects which we now discuss.

\paragraph{Network interference in treatment-effect models.} A central concern in the literature on causal inference under interference is that the treatment assigned to one unit may affect the outcomes of other, network-connected units; see, for example, hudgens2008toward,aronow2017estimating,leung2020treatment. A tractable specification, consistent with the exposure-mapping approach of aronow2017estimating, allows the outcome of unit $i$ to depend on its own treatment status and on the average treatment exposure among units at different network distances. In particular, consider

where $D_i \sim \operatorname{Bernoulli}(\pi)$ denotes the treatment status of unit $i$,

and $U_i$ is an idiosyncratic shock. We assume that $\{(D_i,U_i):i\in N_n\}$ is IID across nodes and that $D_i$ is independent of $u_i$. The parameter $\tau_0$ captures the direct effect of own treatment, whereas $\rho_s$ captures the spillover effect of average treatment exposure among units at network distance $s$. This is a finite-range version of the network-spillover models studied by leung2020treatment: the restriction that $\rho_s=0$ for every $s>R$ implies that $Z_i = (Y_{i},D_{i},U_{i})$ is measurable with respect to the primitive variables indexed by $\mathcal N(i,R)$. \footnote{ We maintain the convention that $\bar D_i(s)=0$ whenever $S_n(i,s)=\varnothing$. }

This model is a particular instance of the nonlinear smooth propagation model, where the primitive shock is given by \(\varepsilon_j=(D_j,u_j)\), and \footnote{One can add exogenous covariates, $X_{j}$, we omit these for the sake of presentation.} \[ H_i((d_j,v_j)_{j\in N_n}) = \alpha+\tau_0 d_i+v_i + \sum_{s=1}^{R}\rho_s \frac{1}{|S_n(i,s)|} \sum_{j\in S_n(i,s)}d_j . \]

Equip the primitive-shock space with the product metric. For two shock arrays \(\varepsilon=(d_j,v_j)_j\) and \(\varepsilon'=(d'_j,v'_j)_j\), \[

\] where \[ c_{ij} = (|\tau_0|+1)1\{j=i\} + 1\{j\neq i\} \frac{|\rho_{d_n(i,j)}|} {|S_n(i,d_n(i,j))|}. \] Therefore the coordinatewise Lipschitz condition holds.

$\tau$-mixing coefficient

We now show that for model (ref)-(ref), for every $q\ge 1$,

and thus, $\bar{\tau}$ and $\tau^{\mathrm{max}}$ also satisfy this bound for any partition-coloring pair.

Fix $A,B\subseteq N_n$ such that $d_n(A,B)\ge r>2R$. Define the primitive-shock index sets relevant for the two collections of observations by \[ \mathcal E_A := \bigcup_{a\in A}\mathcal N(a,R), \qquad \mathcal E_B := \bigcup_{b\in B}\mathcal N(b,R). \] We claim that $\mathcal E_A\cap \mathcal E_B=\varnothing$. Indeed, suppose instead that there exists $j\in\mathcal E_A\cap\mathcal E_B$. Then there exist $a\in A$ and $b\in B$ such that $d_n(a,j)\le R$ and $d_n(b,j)\le R$. By the triangle inequality, $d_n(a,b) \le d_n(a,j)+d_n(j,b) \le 2R$, which contradicts $d_n(A,B)\ge r>2R$.

Therefore, the vectors $Z_A$ and $Z_B$ are measurable with respect to disjoint collections of primitive shocks: \[ \sigma(Z_i:i\in A) \subseteq \sigma(\varepsilon_j:j\in\mathcal E_A)~and~\sigma(Z_i:i\in B) \subseteq \sigma(\varepsilon_j:j\in\mathcal E_B). \] Since the primitive shocks are IID and $\mathcal E_A\cap\mathcal E_B=\varnothing$, these two sigma-fields are independent, i.e., $\sigma(Z_i:i\in A) \perp\!\!\!\perp \sigma(Z_i:i\in B)$. Consequently, $\tau_{d_{\mathcal B,|B|}} \bigl( \sigma(Z_i:i\in A),Z_B \bigr) = 0$. Since this holds for any admissibles sets $A$ and $B$, taking the supremum over them proves that $\tau_{\mathcal B,G_n}(r,q)=0$ whenever $r>2R$.

Maximal inequality and Glivenko--Cantelli results: Application to uniform convergence of the least-squares criterion.

Let $X_i := \left( 1, D_i, \bar D_i(1), \ldots, \bar D_i(R) \right)^{\top}$ and $\theta_0 := \left( \alpha_0, \tau_0, \rho_{0,1}, \ldots, \rho_{0,R} \right)^{\top}$. Suppose $\theta_{0}$ belongs to a compact subset $\Theta \subset\mathbb R^{R+2}$.

The network intereference model (ref) can be cast as $Y_i = X_i^{\top}\theta_0 + U_i$. Since $U_{i}$ is IID, for estimation of $\theta_0$ one can consider the OLS estimator which minimizes

In order to establish the asymptotic properties of the estimator is useful to control

To do this, we employ Theorem (ref). A technical hurdle is that $\ell_{\theta}$ is Lipschitz, but not with uniform bounded constant (as it depends on the data). To circumvent this issue, for any $M>0$, we split $ \ell_\theta = \ell_{\theta,M} + r_{\theta,M}$ with

We also assume that, for some $\delta>0$,

Since $\|X_i\|_2\le \sqrt{R+2}$ we have $\sup_{\theta\in\Theta} \ell_\theta(Y_i,X_i) \le 2Y_i^2 + 2C_\Theta^2(R+2)$, where $C_\Theta := \sup_{\theta\in\Theta} \|\theta\|_2 < \infty$. This result and (ref) imply $\max_{i\in N_n} \mathbb E\left[ \sup_{\theta\in\Theta} r_{\theta,M}(Y_i,X_i) \right] \lesssim M^{-\delta}$. Therefore,

For any $\theta,\theta'\in\Theta$, $\left| \ell_{\theta,M}(Y_i,X_i) - \ell_{\theta',M}(Y_i,X_i) \right| \le 2\sqrt{R+2} \left\{ M+ C_\Theta\sqrt{R+2} \right\} \|\theta-\theta'\|_2$. Consequently,

where $\mathcal L_M := \left\{ \ell_{\theta,M}: \theta\in\Theta \right\}$.

Moreover, truncation does not alter the finite-range dependence structure. Thus, by expression (ref), $\bar\tau_{\operatorname{cone}\mathcal L_M,G_n}(r_n,1) = 0$ with $r_n=2R+1$. Let $K_n$ denote the associated chormatic number which can always be bounded by the degree $\widetilde{\operatorname{deg}}_{n} : = \max_{i\in N_n} \operatorname{deg}_{G_{n}}(i)$. Since $\Theta$ is a bounded subset of $\mathbb R^{R+2}$, the preceding complexity bounds and Theorem (ref) imply

Combining (ref) and (ref) gives

Therefore, provided the degree does not grow too fast --- formally $\frac{\widetilde{\operatorname{deg}}_{n} }{n} \to 0 $ --- then, for any sequence $M_n\to\infty$ satisfying $M_n \sqrt{\frac{\widetilde{\operatorname{deg}}_{n} }{n}} \to 0$, it follows that

Proofs of Theorems (ref), (ref), and (ref)

Proof of Theorem (ref)

The following lemma is a re-statement of Lemma 1 in dedecker2006inequalities and is here merely for completeness; we refer the reader to that paper for a proof.

Fix $k\in [K]$. Write the elements of $C_k$ in increasing order as \[ C_k=\{m_{k,1},\ldots,m_{k,L_k}\},~ m_{k,1}<\cdots<m_{k,L_k}~and~m_{k,i} \in [M]. \]

For $\ell\in [L_{k}]$, define $X_{k,\ell}:=Z_{B_{m_{k,\ell}}}$, viewed as a random element of $\mathsf Z^{|B_{m_{k,\ell}}|}$ equipped with the averaged product metric $ d_{\mathcal{B},|B_{m_{k,\ell}}|}$. Also define the past $\sigma$-field within color $k$ by \[ \mathcal M_{k,\ell-1} := \sigma\!\left( Z_j: j\in \bigcup_{1 \leq u<\ell} B_{m_{k,u}} \right), \qquad \ell\ge 1, \] with the convention that $\mathcal M_{k,0}$ is the trivial $\sigma$-field.

On a suitable extension of the original probability space, let $\left(U_{k,\ell}\right)_{k\in[K],\,\ell\in[L_k]}$ be IID \(\operatorname{Unif}[0,1]\) random variables, independent of \(\sigma(Z_i:i\in N_n)\). For every \(k\in[K]\) and \(\ell\in[L_k]\), define \[ \widetilde{\mathcal M}_{k,\ell-1} := \mathcal M_{k,\ell-1} \vee \sigma(U_{k,1},\ldots,U_{k,\ell-1}), \] where \(\widetilde{\mathcal M}_{k,0}\) is trivial.

Since $\sigma(U_{k,1},\ldots,U_{k,\ell-1}) \perp\!\!\!\perp \sigma(X_{k,\ell})\vee\mathcal M_{k,\ell-1}$, for every bounded measurable function \(h\), $E\left[ h(X_{k,\ell}) \mid \widetilde{\mathcal M}_{k,\ell-1} \right] = E\left[ h(X_{k,\ell}) \mid \mathcal M_{k,\ell-1} \right] \qquad\text{a.s.}$ It follows that

For every \(k\in[K]\) and \(\ell\in[L_k]\), apply Lemma (ref) with $X=X_{k,\ell}$, $\mathcal M=\widetilde{\mathcal M}_{k,\ell-1}$, and $U=U_{k,\ell}$. This yields a random element \(X_{k,\ell}^{\ast}\), measurable with respect to $\sigma(U_{k,\ell}) \vee \sigma(X_{k,\ell}) \vee \widetilde{\mathcal M}_{k,\ell-1}$, such that

Combining (ref) and (ref), we obtain

We next verify mutual independence. For \(u<\ell\), $X_{k,u}^{\ast} \in \sigma(U_{k,u}) \vee \sigma(X_{k,u}) \vee \widetilde{\mathcal M}_{k,u-1}$. Since \(u<\ell\), $\sigma(U_{k,u}) \vee \sigma(X_{k,u}) \vee \widetilde{\mathcal M}_{k,u-1} \subseteq \widetilde{\mathcal M}_{k,\ell-1}$. Therefore, $\sigma\left( X_{k,1}^{\ast},\ldots,X_{k,\ell-1}^{\ast} \right) \subseteq \widetilde{\mathcal M}_{k,\ell-1}$. By (ref), $X_{k,\ell}^{\ast} \perp\!\!\!\perp \sigma\left( X_{k,1}^{\ast},\ldots,X_{k,\ell-1}^{\ast} \right)$. An induction on \(\ell\) therefore shows that $\left( X_{k,1}^{\ast},\ldots,X_{k,L_k}^{\ast} \right) $ is mutually independent.

For every \(k\in[K]\) and \(\ell\in[L_k]\), define $Z_{B_{m_{k,\ell}}}^{\ast}:= X_{k,\ell}^{\ast}$. Since \(\{C_1,\ldots,C_K\}\) is a partition of \([M]\), this defines \(Z_{B_m}^{\ast}\) for every \(m\in[M]\). By (ref), $Z_{B_m}^{\ast}\stackrel{d}{=}Z_{B_m},~m\in[M]$. Moreover, for every \(k\in[K]\), the family $\left( Z_{B_m}^{\ast} \right)_{m\in C_k}$ is mutually independent.

It remains to establish the coupling bound. Fix \(k\in[K]\) and \(\ell\in[L_k]\), and define \[ A_{k,\ell} := \bigcup_{1\leq u<\ell}B_{m_{k,u}}. \] Since the coloring is proper, $d_n(B_{m_{k,u}},B_{m_{k,\ell}})>r$ for every $u<\ell$. Hence, $d_n(A_{k,\ell},B_{m_{k,\ell}})>r$. Therefore,

Combining (ref) and (ref), we obtain \[ E\left[ d_{\mathcal{B},|B_{m_{k,\ell}}|} \left( Z_{B_{m_{k,\ell}}}^{\ast}, Z_{B_{m_{k,\ell}}} \right) \right] = \tau_{d_{\mathcal{B},|B_{m_{k,\ell}}|}} \!\left( \sigma\!\left( Z_j: j\in A_{k,\ell} \right), \, Z_{B_{m_{k,\ell}}} \right). \]

By taking sum over $\ell \in [L_{k}]$ and over $k \in [K]$, it follows that

thereby proving the desired result.

Observe also that

Combining (ref) and this expression, we obtain \[ E\left[ d_{\mathcal{B},|B_{m_{k,\ell}}|} \left( Z_{B_{m_{k,\ell}}}^{\ast}, Z_{B_{m_{k,\ell}}} \right) \right] \le |B_{m_{k,\ell}}| \tau_{\mathcal B,G_n} \left( r,|B_{m_{k,\ell}}| \right). \] This proves the second result.

Proof of Theorem (ref)

The theorem follows from the following, more general, lemma. This lemma allows for the partition of the graph and the coloring to depend on the scale $l$ implied by the partition $(T_{l})_{l \in \mathbb N_0}$ --- it is a generalization of Lemma 3.1 in Pouzo2026 the general graph-dependent data.

To state the lemma we need to introduce some additional concepts. First, the lemma uses a slightly more general concept of admissible sequence partition: A $T^{\infty}(c,d) : = (T_{l}(c,d))_{l \in \mathbb N_0}$ is a sequence of partitions of $\mathcal F$ with $|T_{0}(c,d)| = 1$ and $|T_{l}(c,d)| \leq 2^{d2^{l/c}}$ for some $c,d \geq 1$.

A sequence of partitions of the graph is given by $(\{ B_{1},\ldots,B_{M_{l}} \})_{l \in \mathbb{N}_0} $ where for each $l$, $B_{1},...,B_{M_{l}} $ is a partition of $N_{n}$. The associated coloring of this partition is denoted $\mathcal C_{r_{l},K_{l}}[B_{1},\ldots,B_{M_{l}} ]$.

Before stating the general lemma, it is useful to provide an upper bound on $\operatorname{Var}\left( |B|^{-1/2} \sum_{i \in B} g(Z_{i}) \right) $ for any block $B \subseteq N_{n}$ and any $g \in \mathcal{F}$. This bound will be key to defining the relevant topology for measuring complexity of the space $\mathcal F$.

We are now in position to state the lemma.

The proof of this lemma is relegated to section (ref). We now show Theorem (ref) taking this lemma as given.

Proof of Theorem (ref)

Take Lemma (ref) and specialize it to $c = \min\{a,b\}$, $\ell(l) = 2 d 2^{l/c}$ and $K : = K_{r}$, $r$, and $M$ chosen to be constant in $l$. Since $a,b \geq 1$, it follows that $\ell(l) \leq 2d 2^{l}$ for all $l \in \mathbb{N}_{0}$. Then, with $q = \max_{m \in [M]} |B_{m}|$,

For any $B \subseteq N_{n}$, by inspection of the proof of Lemma (ref) it readily follows that

Therefore,

We now chose the partition $T^{\infty}(c,d) : = ( T_{l}(c,d) )_{l \in \mathbb{N}_{0}} \in \mathcal T _{r} (\mathcal F)$. Let $T^{\infty}(a) \in \mathcal T_{a}(\mathcal F)$ and $T^{\infty}(b) \in \mathcal T_{b}(\mathcal F)$ be some arbitrary partition sequences. For any $l \geq 1$, let $T_{l}(c,d)$ be a partition comprised of sets of the form $A \cap B$ for $A \in T_{l-1}(a)$ and $B \in T_{l-1}(b)$. Under this choice, for any $l \in \mathbb{N}$, $card T_{l}(c,d) \leq 2^{2^{(l-1)/a} + 2^{(l-1)/b}}$. For $c = \min \{a,b\}$, $2^{(l-1)/a} + 2^{(l-1)/b} = 2^{l/c} 2^{-1/c} ( 2^{(l-1)(1/a-1/c)} + 2^{(l-1)(1/b-1/c)} ) \leq 2^{l/c} 2^{1-1/c} = d 2^{l/c}$. Hence, $card T_{l}(c,d) \leq 2^{d2^{l/c}}$ for all $l \in \mathbb{N}_{0}$. Hence, $T^{\infty}(c,d)$ is indeed in $\mathcal T _{r} (\mathcal F)$. This construction holds for arbitrary $T^{\infty}(a) \in \mathcal T_{a}(\mathcal F)$ and $T^{\infty}(b) \in \mathcal T_{b}(\mathcal F)$, we now choose them so as to be (approximate) minimizers of the Talagrand's Complexity Measure in Definition (ref), i.e.,

Moreover, the last display implies that $||\Delta_l f||_{\infty} \leq 1.5 \frac{ \gamma_{1,b}(\mathcal F , ||\cdot||_{\infty}) }{2^{l}}$ for all $f \in \mathcal{F}$. Thus, we can choose $u(l) = 1.5 \frac{\gamma_{1,b} (\mathcal{F} , ||.||_{\infty})}{2^{l}} $ for any $l \in \mathbb{N}_{0}$.

Hence,

and Theorem (ref) follows.

Proof of Lemma (ref)

It follows that $\mathbb{G}_n(f - f_0) = \sum_{l=1}^{\infty} \mathbb{G}_n(\Delta_l f)$, where for each $l\geq 1$,

For any scale $l \in \mathbb{N}$, let $\mathcal{P}_{N_{n},M_{l}} = \{ B_{1} , \ldots , B_{M_l} \}$ be partition of $N_{n}$. Given this partition, we can split the sum in previous display into a sum within blocks and between blocks, i.e.,

where the within block $B_{m}$ sum is $f \mapsto U_{m}(f) : = \sum_{i \in B_{m}} \{ f(Z_{i}) - \mathbb E [f(Z_{i})]\}$.

Moreover, for any $r_l$-coloring, $\mathcal{C}_{r_l}[\mathcal{P}_{N_{n},M_l}] = \{ C_{1} , \ldots, C_{K_l} \}$, it follows that

Let $(Z^{\ast}_{i})_{i \in N_{n}}$ be the stochastic process from Theorem (ref) associated to the $r$-coloring, $\mathcal{C}_{r_l}[\mathcal{P}_{N_{n},M}]$. Let $\mathbb{G}^{\ast}_{n} : \Delta_{l} \mathcal F \rightarrow \mathbb{R}$ be given by

with $f \mapsto U^{\ast}_{m}(f) : = \sum_{i \in B_{m}} \{ f(Z^{\ast}_{i}) - \mathbb E [f(Z^{\ast}_{i})]\}$ --- observe that for any $i \in B_{m}$, $Z^{\ast}_{i}$ has the same distribution as $Z_{i}$, so $\mathbb E^{\ast} [f(Z^{\ast}_{i})] = \mathbb E [f(Z_{i})]$.

By these calculation and the triangle inequality,

We now proceed to bound the two terms in the RHS of this expression individually.

\refstepcounter{subsubsubsection} \thesubsubsubsection\quad Bound for $ \left \| \sup_{f\in\mathcal{F}} \sum_{l=1}^{\infty} \{ \mathbb G_{n}(\Delta_l f ) - \mathbb{G}^{\ast}_n(\Delta_l f) \} \right\|_{L^{1}(\Pr)} $

Observe that for any $l \in \mathbb{N}$,

because $d_{\Delta_{l} \mathcal{F}, |B_{m}|}(Z_{B_{m}},Z^{\ast}_{B_{m}}) = \sup_{h \in \Delta_{l} \mathcal{F}} \sum_{i \in B_{m}} |h(Z_{i}) - h(Z^{\ast}_{i}) |$.

By Theorem (ref),

and thus

\refstepcounter{subsubsubsection} \thesubsubsubsection\quad Bound for $\left \| \sup_{f\in\mathcal{F}} \sum_{l=1}^{\infty} \mathbb{G}^{\ast}_n(\Delta_l f) \right \|_{L^{1}(\mathbb P^{\ast})}$

Observe that

To do bound this term we follow the steps in the proof of Lemma 3.1 in Pouzo2026 which rest on the results by talagrand2014. For that we need to establish a Bernstein type inequality for the coupled color-class empirical process $g \mapsto \frac{1}{\sqrt{ | C_{k} | }} \sum_{m \in C_{k}} \sqrt{ \frac{ | C_{k} | }{n} } U^{\ast}_{m}(g) $.

We can now establish the following bound for the empirical process $\mathbb{G}^{(k),\ast}_{n}$

An immediate implication of this result is that

Observe that

where the first inequality follows by Jensen's inequality.

Therefore,

\refstepcounter{subsubsubsection} \thesubsubsubsection\quad Bound on $\left \| \sup_{f\in\mathcal{F}} \sum_{l=1}^{\infty} \mathbb G_{n}(\Delta_l f ) \right\|_{L^{1}(\mathbb P)} $

By combining the expressions (ref) and (ref) with expression (ref), it follows that

Suppose there exists a $u : \mathbb{N}_{0} \to \mathbb{R}_{+}$ such that $\sup_{f \in \mathcal{F}} ||\Delta_{l} f||_{\infty} \leq u(l)$ for all $l \in \mathbb{N}_{0}$. By Lemma (ref) and the fact that $\Delta_l \mathcal F \subseteq \mathcal F$ and $u(l) \geq ||f||_{\infty}$ for all $f \in \Delta_{l} \mathcal F$, $\tau_{ \Delta_l \mathcal F , G_{n}}(r_{l}, \max_{m \in [M_l]} |B_{m}| ) \leq u(l) \tau_{ \operatorname{cone} \mathcal F , G_{n}}(r_{l},\max_{m \in [M_l]} |B_{m}| ) $. Hence, setting $\ell(l) = 2^{l/2}$,

Thus the desired result is shown.

Proof of Theorem (ref)

Fix \(n\). Let $f \mapsto P^{0}_{n}f : = n^{-1} \sum_{i \in N_{n}} \mathbb E [f(Z_{i})] $. For every \(f\in\mathcal F\), let \(C(f)\in T_{L_n}\) be the cell containing \(f\). Then

Taking the supremum over \(f\in\mathcal F\), we obtain

We control the first term by Theorem (ref). Applying the theorem with $\mathcal F = \Pi_{L_{n}}$ and then dividing by \(\sqrt n\), yields

We now control the second term in (ref). If \(f\in C\), then $|f(z)-\pi_{L_n}f(z)| \le D_C(z)$, $z\in \mathsf Z$. Therefore,

Taking suprema over \(f\in\mathcal F\), equivalently over \(C\in T_{L_n}\), gives

If we show that the RHS of expressions (ref) and (ref) vanish as $n$ diverges, the desired result follows by the Markov inequality.

By assumption, the RHS of (ref) vanishes as $n$ diverges, thus, it only remains to control the RHS of expression (ref). By Lemma (ref) with $T = \Pi_{L_{n}}$,

Since $\sup_{ f \in \mathcal F } ||f||_{\infty} < \infty$, $\sup_{n \in \mathbb{N}} \operatorname{diam}(\Pi_{L_{n}} , \max_{i \in N_{n}} ||.||_{L^{2p}(P_{Z_{i}})} ) \leq \operatorname{diam}(\Pi_{L_{n}} , ||.||_{\infty}) < \infty$. Thus, the RHS in the previous display vanishes as $n$ diverges by condition (ref).