Online-to-PAC generalization bounds under graph-mixing dependencies

• URL: http://arxiv.org/abs/2410.08977v1
• Date: Fri, 11 Oct 2024 16:49:01 GMT
• Title: Online-to-PAC generalization bounds under graph-mixing dependencies
• Authors: Baptiste Abélès, Eugenio Clerico, Gergely Neu,
• Abstract summary: 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.
• Score: 9.763215134790478
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 temporal (mixing) dependencies, or graph-dependencies, where non-adjacent vertices correspond to independent random variables. Both approaches have their own limitations, the former requiring a temporal ordered structure, and the latter lacking a way to quantify the strength of inter-dependencies. In this work, we bridge these two lines of work by proposing a framework where dependencies decay with graph distance. We derive generalization bounds leveraging the online-to-PAC framework, by deriving a concentration result and introducing an online learning framework incorporating the graph structure. The resulting high-probability generalization guarantees depend on both the mixing rate and the graph's chromatic number.

Related papers

• Independent Distribution Regularization for Private Graph Embedding [55.24441467292359]
  Graph embeddings are susceptible to attribute inference attacks, which allow attackers to infer private node attributes from the learned graph embeddings. To address these concerns, privacy-preserving graph embedding methods have emerged. We propose a novel approach called Private Variational Graph AutoEncoders (PVGAE) with the aid of independent distribution penalty as a regularization term.
  arXiv  Detail & Related papers  (2023-08-16T13:32:43Z)
• Uniform Risk Bounds for Learning with Dependent Data Sequences [0.0]
  This paper extends standard results from learning theory with independent data to sequences of dependent data. We do not rely on mixing arguments or sequential measures of complexity and derive uniform risk bounds with classical proof patterns and capacity measures.
  arXiv  Detail & Related papers  (2023-03-21T07:51:52Z)
• DyTed: Disentangled Representation Learning for Discrete-time Dynamic Graph [59.583555454424]
  We propose a novel disenTangled representation learning framework for discrete-time Dynamic graphs, namely DyTed. We specially design a temporal-clips contrastive learning task together with a structure contrastive learning to effectively identify the time-invariant and time-varying representations respectively.
  arXiv  Detail & Related papers  (2022-10-19T14:34:12Z)
• Combinatorial and algebraic perspectives on the marginal independence structure of Bayesian networks [0.0]
  We show that unconditional dependence graphs of Bayesian networks correspond to the graphs having equal independence and intersection numbers. GrUES recovers the true marginal independence structure via a penalized maximum likelihood or MAP estimate at a higher rate than simple independence tests.
  arXiv  Detail & Related papers  (2022-10-03T11:12:39Z)
• Learning the Evolutionary and Multi-scale Graph Structure for Multivariate Time Series Forecasting [50.901984244738806]
  We show how to model the evolutionary and multi-scale interactions of time series. In particular, we first provide a hierarchical graph structure cooperated with the dilated convolution to capture the scale-specific correlations. A unified neural network is provided to integrate the components above to get the final prediction.
  arXiv  Detail & Related papers  (2022-06-28T08:11:12Z)
• Generalization bounds for learning under graph-dependence: A survey [4.220336689294245]
  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.
  arXiv  Detail & Related papers  (2022-03-25T09:33:49Z)
• 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)
• Structural Landmarking and Interaction Modelling: on Resolution Dilemmas in Graph Classification [50.83222170524406]
  We study the intrinsic difficulty in graph classification under the unified concept of resolution dilemmas'' We propose SLIM'', an inductive neural network model for Structural Landmarking and Interaction Modelling.
  arXiv  Detail & Related papers  (2020-06-29T01:01:42Z)
• Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks [91.65637773358347]
  We propose a general graph neural network framework designed specifically for multivariate time series data. Our approach automatically extracts the uni-directed relations among variables through a graph learning module. Our proposed model outperforms the state-of-the-art baseline methods on 3 of 4 benchmark datasets.
  arXiv  Detail & Related papers  (2020-05-24T04:02:18Z)
• Residual Correlation in Graph Neural Network Regression [39.54530450932135]
  We show that conditional independence assumption severely limits predictive power. We address this problem with an interpretable and efficient framework. Our framework achieves substantially higher accuracy than competing baselines.
  arXiv  Detail & Related papers  (2020-02-19T16:32:54Z)

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.