Generalization bounds for learning under graph-dependence: A survey

• URL: http://arxiv.org/abs/2203.13534v2
• Date: Thu, 28 Mar 2024 18:38:18 GMT
• Title: Generalization bounds for learning under graph-dependence: A survey
• Authors: Rui-Ray Zhang, Massih-Reza Amini,
• Abstract summary: We explore learning scenarios where examples are dependent and their dependence relationship is described by a dependency graph. We collect various graph-dependent concentration bounds, which are then used to derive Rademacher complexity and stability bounds generalization. To our knowledge, this survey is the first of this kind on this subject.
• Score: 4.220336689294245
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Online-to-PAC generalization bounds under graph-mixing dependencies [9.763215134790478]
  We propose a framework where dependencies decay with graph distance. We derive generalization bounds leveraging the online-to-PAC framework. The resulting high-probability generalization guarantees depend on both the mixing rate and the graph's chromatic number.
  arXiv  Detail & Related papers  (2024-10-11T16:49:01Z)
• Learning Divergence Fields for Shift-Robust Graph Representations [73.11818515795761]
  In this work, we propose a geometric diffusion model with learnable divergence fields for the challenging problem with interdependent data. We derive a new learning objective through causal inference, which can guide the model to learn generalizable patterns of interdependence that are insensitive across domains.
  arXiv  Detail & Related papers  (2024-06-07T14:29:21Z)
• Towards Bounding Causal Effects under Markov Equivalence [13.050023008348388]
  We consider the derivation of bounds on causal effects given only observational data. We provide a systematic algorithm to derive bounds on causal effects that exploit the invariant properties of the equivalence class.
  arXiv  Detail & Related papers  (2023-11-13T11:49:55Z)
• Spurious Correlations and Where to Find Them [17.1264393170134]
  Spurious correlations occur when a model learns unreliable features from the data. We collect some of the commonly studied hypotheses behind the occurrence of spurious correlations. We investigate their influence on standard ERM baselines using synthetic datasets generated from causal graphs.
  arXiv  Detail & Related papers  (2023-08-21T21:06:36Z)
• On the Joint Interaction of Models, Data, and Features [82.60073661644435]
  We introduce a new tool, the interaction tensor, for empirically analyzing the interaction between data and model through features. Based on these observations, we propose a conceptual framework for feature learning. Under this framework, the expected accuracy for a single hypothesis and agreement for a pair of hypotheses can both be derived in closed-form.
  arXiv  Detail & Related papers  (2023-06-07T21:35:26Z)
• Adaptive Data Analysis with Correlated Observations [21.969356766737622]
  We show that, in some cases, differential privacy guarantees even when there are dependencies within the sample. We show that the connection between transcript-compression and adaptive data analysis can be extended to the non-iid setting.
  arXiv  Detail & Related papers  (2022-01-21T14:00:30Z)
• Typing assumptions improve identification in causal discovery [123.06886784834471]
  Causal discovery from observational data is a challenging task to which an exact solution cannot always be identified. We propose a new set of assumptions that constrain possible causal relationships based on the nature of the variables.
  arXiv  Detail & Related papers  (2021-07-22T14:23:08Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  We provide guarantees on identifiability and learnability under mild assumptions. We develop efficient algorithms based on coupled tensor decomposition with linear constraints to obtain scalable and guaranteed solutions.
  arXiv  Detail & Related papers  (2021-01-17T07:48:45Z)
• Amortized Causal Discovery: Learning to Infer Causal Graphs from Time-Series Data [63.15776078733762]
  We propose Amortized Causal Discovery, a novel framework to learn to infer causal relations from time-series data. We demonstrate experimentally that this approach, implemented as a variational model, leads to significant improvements in causal discovery performance.
  arXiv  Detail & Related papers  (2020-06-18T19:59:12Z)
• On Disentangled Representations Learned From Correlated Data [59.41587388303554]
  We bridge the gap to real-world scenarios by analyzing the behavior of the most prominent disentanglement approaches on correlated data. We show that systematically induced correlations in the dataset are being learned and reflected in the latent representations. We also demonstrate how to resolve these latent correlations, either using weak supervision during training or by post-hoc correcting a pre-trained model with a small number of labels.
  arXiv  Detail & Related papers  (2020-06-14T12:47:34Z)
• Neural Relation Prediction for Simple Question Answering over Knowledge Graph [0.0]
  We propose an instance-based method to capture the underlying relation of question and to this aim, we detect matching paraphrases of a new question. Our experiments on the SimpleQuestions dataset show that the proposed model achieves better accuracy compared to the state-of-the-art relation extraction models.
  arXiv  Detail & Related papers  (2020-02-18T16:41:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.