Generalization bounds for learning under graph-dependence: A survey

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 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.

To appear in Machine Learning Journal

References in corpus (6)

• Concentration inequalities for dependent Random variables via the martingale method
• On Tree-Partition-Width
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Almost-everywhere algorithmic stability and generalization error
• Optimality of Poisson processes intensity learning with Gaussian processes
• When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence