Structure Learning with Adaptive Random Neighborhood Informed MCMC

• URL: http://arxiv.org/abs/2311.00599v1
• Date: Wed, 1 Nov 2023 15:47:18 GMT
• Title: Structure Learning with Adaptive Random Neighborhood Informed MCMC
• Authors: Alberto Caron, Xitong Liang, Samuel Livingstone and Jim Griffin
• Abstract summary: We introduce a novel MCMC sampler, PARNI-DAG, for the problem of structure learning under observational data. Under the assumption of causal sufficiency, the algorithm allows for approximate sampling directly from the posterior distribution on Directed Acyclic Graphs (DAGs) We empirically demonstrate its mixing efficiency and accuracy in learning DAG structures on a variety of experiments.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce a novel MCMC sampler, PARNI-DAG, for a fully-Bayesian approach to the problem of structure learning under observational data. Under the assumption of causal sufficiency, the algorithm allows for approximate sampling directly from the posterior distribution on Directed Acyclic Graphs (DAGs). PARNI-DAG performs efficient sampling of DAGs via locally informed, adaptive random neighborhood proposal that results in better mixing properties. In addition, to ensure better scalability with the number of nodes, we couple PARNI-DAG with a pre-tuning procedure of the sampler's parameters that exploits a skeleton graph derived through some constraint-based or scoring-based algorithms. Thanks to these novel features, PARNI-DAG quickly converges to high-probability regions and is less likely to get stuck in local modes in the presence of high correlation between nodes in high-dimensional settings. After introducing the technical novelties in PARNI-DAG, we empirically demonstrate its mixing efficiency and accuracy in learning DAG structures on a variety of experiments.

Related papers

• Locally Regularized Sparse Graph by Fast Proximal Gradient Descent [6.882546996728011]
  We propose a novel Regularized Sparse Graph abbreviated SRSG. Sparse graphs have been shown to be effective in clustering high-dimensional data. We show that SRSG is superior to other clustering methods.
  arXiv  Detail & Related papers  (2024-09-25T16:57:47Z)
• The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication [37.210933391984014]
  Local SGD is a popular optimization method in distributed learning, often outperforming other algorithms in practice. We provide new lower bounds for local SGD under existing first-order data heterogeneity assumptions. We also show the min-max optimality of accelerated mini-batch SGD for several problem classes.
  arXiv  Detail & Related papers  (2024-05-19T20:20:03Z)
• Rethinking Clustered Federated Learning in NOMA Enhanced Wireless Networks [60.09912912343705]
  This study explores the benefits of integrating the novel clustered federated learning (CFL) approach with non-independent and identically distributed (non-IID) datasets. A detailed theoretical analysis of the generalization gap that measures the degree of non-IID in the data distribution is presented. Solutions to address the challenges posed by non-IID conditions are proposed with the analysis of the properties.
  arXiv  Detail & Related papers  (2024-03-05T17:49:09Z)
• A GAN Approach for Node Embedding in Heterogeneous Graphs Using Subgraph Sampling [35.94125831564648]
  Our research addresses class imbalance issues in heterogeneous graphs using graph neural networks (GNNs) We propose a novel method combining the strengths of Generative Adversarial Networks (GANs) with GNNs, creating synthetic nodes and edges that effectively balance the dataset.
  arXiv  Detail & Related papers  (2023-12-11T16:52:20Z)
• Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topology [6.6682038218782065]
  We develop a general framework unifying several gradient-based optimization methods for empirical risk minimization problems. We provide a unified perspective for variance-reduction (VR) and gradient-tracking (GT) methods such as SAGA, Local-SVRG and GT-SAGA. The rate results reveal that VR and GT methods can effectively eliminate data within and across devices, respectively, enabling the exact convergence of the algorithm to the optimal solution.
  arXiv  Detail & Related papers  (2022-07-08T07:50:08Z)
• Federated Minimax Optimization: Improved Convergence Analyses and Algorithms [32.062312674333775]
  We consider non minimax optimization, is gaining prominence many modern machine learning applications such as GANs. We provide a novel and tighter analysis algorithm, improves convergence communication guarantees in the existing literature.
  arXiv  Detail & Related papers  (2022-03-09T16:21:31Z)
• Bayesian Structure Learning with Generative Flow Networks [85.84396514570373]
  In Bayesian structure learning, we are interested in inferring a distribution over the directed acyclic graph (DAG) from data. Recently, a class of probabilistic models, called Generative Flow Networks (GFlowNets), have been introduced as a general framework for generative modeling. We show that our approach, called DAG-GFlowNet, provides an accurate approximation of the posterior over DAGs.
  arXiv  Detail & Related papers  (2022-02-28T15:53:10Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  We introduce a novel GP regression to incorporate the subgroup feedback. Our modified regression has provably lower variance -- and thus a more accurate posterior -- compared to previous approaches. We execute our algorithm on two disparate social problems.
  arXiv  Detail & Related papers  (2021-07-07T03:57:22Z)
• Cyclic Label Propagation for Graph Semi-supervised Learning [52.102251202186025]
  We introduce a novel framework for graph semi-supervised learning called CycProp. CycProp integrates GNNs into the process of label propagation in a cyclic and mutually reinforcing manner. In particular, our proposed CycProp updates the node embeddings learned by GNN module with the augmented information by label propagation.
  arXiv  Detail & Related papers  (2020-11-24T02:55:40Z)
• Improving Generative Adversarial Networks with Local Coordinate Coding [150.24880482480455]
  Generative adversarial networks (GANs) have shown remarkable success in generating realistic data from some predefined prior distribution. In practice, semantic information might be represented by some latent distribution learned from data. We propose an LCCGAN model with local coordinate coding (LCC) to improve the performance of generating data.
  arXiv  Detail & Related papers  (2020-07-28T09:17:50Z)
• Bayesian Graph Neural Networks with Adaptive Connection Sampling [62.51689735630133]
  We propose a unified framework for adaptive connection sampling in graph neural networks (GNNs) The proposed framework not only alleviates over-smoothing and over-fitting tendencies of deep GNNs, but also enables learning with uncertainty in graph analytic tasks with GNNs.
  arXiv  Detail & Related papers  (2020-06-07T07:06:35Z)

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.