Generalization bounds for learning under graph-dependence: A survey

arXiv:2203.13534v2 Announce Type: replace
Abstract: 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 …

abstract applications arxiv cs.lg data distributed examples explore graph however life relationship statistical stat.ml survey theory type