Scalable Causal Discovery with Score Matching

• URL: http://arxiv.org/abs/2304.03382v1
• Date: Thu, 6 Apr 2023 21:28:16 GMT
• Title: Scalable Causal Discovery with Score Matching
• Authors: Francesco Montagna, Nicoletta Noceti, Lorenzo Rosasco, Kun Zhang, Francesco Locatello
• Abstract summary: We show how to discover the whole causal graph from the second derivative of the log-likelihood in non-linear additive Gaussian noise models. Our approach enables principled and scalable causal discovery, significantly lowering the compute bar.
• Score: 37.13308785728276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper demonstrates how to discover the whole causal graph from the second derivative of the log-likelihood in observational non-linear additive Gaussian noise models. Leveraging scalable machine learning approaches to approximate the score function $\nabla \log p(\mathbf{X})$, we extend the work of Rolland et al. (2022) that only recovers the topological order from the score and requires an expensive pruning step removing spurious edges among those admitted by the ordering. Our analysis leads to DAS (acronym for Discovery At Scale), a practical algorithm that reduces the complexity of the pruning by a factor proportional to the graph size. In practice, DAS achieves competitive accuracy with current state-of-the-art while being over an order of magnitude faster. Overall, our approach enables principled and scalable causal discovery, significantly lowering the compute bar.

Related papers

• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  We study learning problems on correlated block models with two balanced communities. Our main result gives the first efficient algorithm for graph matching in this setting. We extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible.
  arXiv  Detail & Related papers  (2024-12-03T18:36:45Z)
• Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modeling [82.36856860383291]
  We demonstrate that accurate estimation of the score function is achievable by training a standard deep ReLU neural network. We establish bounds on the error rate of recovering causal relationships using the score-matching-based causal discovery method.
  arXiv  Detail & Related papers  (2023-10-27T13:09:56Z)
• Relationship between Batch Size and Number of Steps Needed for Nonconvex Optimization of Stochastic Gradient Descent using Armijo Line Search [0.8158530638728501]
  We show that SGD performs better than other deep learning networks when it uses deep numerical line. The results indicate that the number of steps needed for SFO as the batch size grows can be estimated.
  arXiv  Detail & Related papers  (2023-07-25T21:59:17Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• Practical Algorithms for Orientations of Partially Directed Graphical Models [5.833272638548153]
  In observational studies, the true causal model is typically unknown and needs to be estimated from available observational and limited experimental data. In such cases, the learned causal model is commonly represented as a partially directed acyclic graph (PDAG) The main focus of this paper is on the maximal orientation task, which, for a given PDAG, aims to orient the undirected edges maximally.
  arXiv  Detail & Related papers  (2023-02-28T08:15:49Z)
• A Meta-Reinforcement Learning Algorithm for Causal Discovery [3.4806267677524896]
  Causal structures can enable models to go beyond pure correlation-based inference. Finding causal structures from data poses a significant challenge both in computational effort and accuracy. We develop a meta-reinforcement learning algorithm that performs causal discovery by learning to perform interventions.
  arXiv  Detail & Related papers  (2022-07-18T09:26:07Z)
• Score matching enables causal discovery of nonlinear additive noise models [63.93669924730725]
  We show how to design a new generation of scalable causal discovery methods. We propose a new efficient method for approximating the score's Jacobian, enabling to recover the causal graph.
  arXiv  Detail & Related papers  (2022-03-08T21:34:46Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)

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.