# McDiarmid-Type Inequalities for Graph-Dependent Variables and Stability Bounds

arXiv: https://arxiv.org/abs/1909.02330 · HTML: https://mlsanity.com/paper/1909.02330/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2019.

## Built on by (most cited first, 15 of 15)

- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Toward Understanding Generative Data Augmentation](https://mlsanity.com/paper/2305.17476/) (2023)
- [Understanding Model Ensemble in Transferable Adversarial Attack](https://mlsanity.com/paper/2410.06851/) (2024)
- [Generalization bounds for learning under graph-dependence: A survey](https://mlsanity.com/paper/2203.13534/) (2022)
- [Towards Understanding the Mechanism of Contrastive Learning via Similarity Structure: A Theoretical Analysis](https://mlsanity.com/paper/2304.00395/) (2023)
- [Distribution-aware Margin Calibration for Semantic Segmentation in Images](https://mlsanity.com/paper/2112.11554/) (2021)
- [Towards Understanding Generalization of Macro-AUC in Multi-label Learning](https://mlsanity.com/paper/2305.05248/) (2023)
- [A Unified Framework for Generative Data Augmentation: A Comprehensive Survey](https://mlsanity.com/paper/2310.00277/) (2023)
- [Online-to-PAC generalization bounds under graph-mixing dependencies](https://mlsanity.com/paper/2410.08977/) (2024)
- [On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning](https://mlsanity.com/paper/2410.09156/) (2024)
- [Enhancing Node-Level Graph Domain Adaptation by Alleviating Local Dependency](https://mlsanity.com/paper/2512.13149/) (2025)
- [Finite-sample guarantees for data-driven forward-backward operator methods](https://mlsanity.com/paper/2512.19172/) (2025)
- [Sharper Risk Bound for Multi-Task Learning with Multi-Graph Dependent Data](https://mlsanity.com/paper/2502.18167/) (2025)
- [PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification](https://mlsanity.com/paper/2509.06600/) (2025)
- [On McDiarmid's Inequality under Dependence via Approximate Tensorization of Entropy](https://mlsanity.com/paper/2606.12720/) (2026)

## Abstract (arXiv)

A crucial assumption in most statistical learning theory is that samples are independently and identically distributed (i.i.d.). However, for many real applications, the i.i.d. assumption does not hold. We consider learning problems in which examples are dependent and their dependency relation is characterized by a graph. To establish algorithm-dependent generalization theory for learning with non-i.i.d. data, we first prove novel McDiarmid-type concentration inequalities for Lipschitz functions of graph-dependent random variables. We show that concentration relies on the forest complexity of the graph, which characterizes the strength of the dependency. We demonstrate that for many types of dependent data, the forest complexity is small and thus implies good concentration. Based on our new inequalities we are able to build stability bounds for learning from graph-dependent data.