Coupling and Maximal Inequalities for Graph-Dependent Empirical Processes

We develop maximal inequalities for empirical processes indexed by graph-dependent observations.

Our bounds separate the complexity of the indexing class from two features specific to graph dependence: the geometry of the underlying graph and the cost of coupling graph-separated blocks to independent copies.

The coupling construction combines a novel graph-adapted dependence coefficient with a coloring of a block partition.

We specialize the results to graphs with polynomial and exponential growth and to directed dyadic graphs.

We then derive Glivenko--Cantelli results and characterize the associated effective sample size.

A central implication is that graph-dependent empirical processes need not exhibit a generic root-$n$ rate: convergence is jointly determined by function-class complexity, graph geometry, and the decay of dependence with graph distance.

Finally, we apply the results to obtain uniform laws of large numbers for network autoregressive models, nonlinear local-propagation models, and treatment-interference settings.