Generalization bounds for learning under graph-dependence: A survey
It addresses the challenge of dependent data in real-world applications for machine learning researchers, but is incremental as a survey.
This survey tackles the problem of learning from non-i.i.d. data by exploring generalization bounds for graph-dependent data, collecting concentration bounds to derive Rademacher complexity and stability bounds.
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.