Generalization bounds for learning under graph-dependence: A survey
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsLearning TheorySurveySimilar Papers 제목 키워드 기반
PAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Network
Graph neural networks (GNNs) have gained popularity for various graph-related tasks. However, similar to deep neural networks, GNNs are also vulnerable to adversarial attacks. Empirical studies have shown that adversaria…
Generalization BoundsGraph Neural NetworkWhen Do Early-Exit Networks Generalize? A PAC-Bayesian Theory of Adaptive Depth
Early-exit neural networks enable adaptive computation by allowing confident predictions to exit at intermediate layers, achieving 2-8$\times$ inference speedup. Despite widespread deployment, their generalization proper…
Online-to-PAC generalization bounds under graph-mixing dependencies
Traditional generalization results in statistical learning require a training data set made of independently drawn examples. Most of the recent efforts to relax this independence assumption have considered either purely …
Generalization BoundsStability Based Generalization Bounds for Exponential Family Langevin Dynamics
Recent years have seen advances in generalization bounds for noisy stochastic algorithms, especially stochastic gradient Langevin dynamics (SGLD) based on stability (Mou et al., 2018; Li et al., 2020) and information the…
Generalization BoundsSpectrum-Adaptive Generalization Bounds for Trained Deep Transformers
Understanding why trained Transformers generalize well is a fundamental problem in modern machine learning theory, and complexity-based generalization bounds provide a principled way to study this question. While existin…