Coupling and Maximal Inequalities for Graph-Dependent Empirical Processes
Abstract
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. As an application, we 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. We specialize the results to graphs with polynomial and exponential growth and to directed dyadic graphs. Finally, we apply the results to network autoregressive models, nonlinear local-propagation models, and treatment-interference settings.
Related
- Endpoint power weight inequalities for spherical maximal functions
- Parabolic Poincaré inequalities and maximal function estimates for systems of partial differential equations
- Sharp derivative inequalities for maximal functions
- Full-radius dimension-free maximal inequalities for discrete Euclidean balls
- Counterexamples to Hardy--Littlewood maximal inequalities on solvable groups
BibTeX
@misc{gao2026coupling,
title = {{Coupling and Maximal Inequalities for Graph-Dependent Empirical Processes}},
author = {Mengsi Gao and Demian Pouzo},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.31936},
eprint = {2606.31936},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.31936},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Coupling and Maximal Inequalities for Graph-Dependent Empirical Processes
AU - Mengsi Gao
AU - Demian Pouzo
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2606.31936
UR - https://arxiv.org/abs/2606.31936
AB - 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. As an application, we 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. We specialize the results to graphs with polynomial and exponential growth and to directed dyadic graphs. Finally, we apply the results to network autoregressive models, nonlinear local-propagation models, and treatment-interference settings.
ER -