# Generalization bounds for learning under graph-dependence: A survey

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 79 references that are in the map.
- First posted on arXiv 25 Mar 2022.

## Builds on (most cited first, 7 of 7)

- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Discovering Latent Network Structure in Point Process Data](https://mlsanity.com/paper/1402.0914/) (2014)
- [McDiarmid-Type Inequalities for Graph-Dependent Variables and Stability Bounds](https://mlsanity.com/paper/1909.02330/) (2019)
- [Representation Learning and Pairwise Ranking for Implicit Feedback in Recommendation Systems](https://mlsanity.com/paper/1705.00105/) (2017)
- [Learning from networked examples](https://mlsanity.com/paper/1405.2600/) (2014)
- [Optimality of Poisson processes intensity learning with Gaussian processes](https://mlsanity.com/paper/1409.5103/) (2014)

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

- [Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models](https://mlsanity.com/paper/2407.18158/) (2024)
- [AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation](https://mlsanity.com/paper/2409.20398/) (2024)
- [Understanding Model Ensemble in Transferable Adversarial Attack](https://mlsanity.com/paper/2410.06851/) (2024)
- [Towards Understanding Generalization of Macro-AUC in Multi-label Learning](https://mlsanity.com/paper/2305.05248/) (2023)
- [Online-to-PAC generalization bounds under graph-mixing dependencies](https://mlsanity.com/paper/2410.08977/) (2024)
- [Sharper Risk Bound for Multi-Task Learning with Multi-Graph Dependent Data](https://mlsanity.com/paper/2502.18167/) (2025)

## Abstract (arXiv)

Traditional statistical learning theory relies on the assumption that data are identically and independently distributed (i.i.d.). However, this assumption often does not hold in many real-life applications. In this survey, we explore learning scenarios where examples are dependent and their dependence relationship is described by a dependency graph, a commonly utilized model in probability and combinatorics. We collect various graph-dependent concentration bounds, which are then used to derive Rademacher complexity and stability generalization bounds for learning from graph-dependent data. We illustrate this paradigm through practical learning tasks and provide some research directions for future work. To our knowledge, this survey is the first of this kind on this subject.