Non-negative Weighted DAG Structure Learning

• URL: http://arxiv.org/abs/2409.07880v1
• Date: Thu, 12 Sep 2024 09:41:29 GMT
• Title: Non-negative Weighted DAG Structure Learning
• Authors: Samuel Rey, Seyed Saman Saboksayr, Gonzalo Mateos,
• Abstract summary: We address the problem of learning the true DAGs from nodal observations. We propose a DAG recovery algorithm based on the method that is guaranteed to return ar.
• Score: 12.139158398361868
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We address the problem of learning the topology of directed acyclic graphs (DAGs) from nodal observations, which adhere to a linear structural equation model. Recent advances framed the combinatorial DAG structure learning task as a continuous optimization problem, yet existing methods must contend with the complexities of non-convex optimization. To overcome this limitation, we assume that the latent DAG contains only non-negative edge weights. Leveraging this additional structure, we argue that cycles can be effectively characterized (and prevented) using a convex acyclicity function based on the log-determinant of the adjacency matrix. This convexity allows us to relax the task of learning the non-negative weighted DAG as an abstract convex optimization problem. We propose a DAG recovery algorithm based on the method of multipliers, that is guaranteed to return a global minimizer. Furthermore, we prove that in the infinite sample size regime, the convexity of our approach ensures the recovery of the true DAG structure. We empirically validate the performance of our algorithm in several reproducible synthetic-data test cases, showing that it outperforms state-of-the-art alternatives.

Related papers

• $ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning [6.612096312467342]
  Learning the structure of Directed A Graphs (DAGs) presents a significant challenge due to the vast search space of possible graphs, which scales with the number of nodes. Recent advancements have redefined this problem as a continuous optimization task by incorporating differentiable a exponentiallyity constraints. We present a novel framework for learning DAGs, employing a Approximation approach integrated with Gradient Descent (SGD)-based optimization techniques.
  arXiv  Detail & Related papers  (2024-10-31T12:13:11Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Causal Structural Learning from Time Series: A Convex Optimization Approach [12.4517307615083]
  Structural learning aims to learn directed acyclic graphs (DAGs) from observational data. Recent DAG learning remains a highly non-adaptive structural learning problem. We propose a data approach for causal learning using a recently developed monotone variational (VI) formulation.
  arXiv  Detail & Related papers  (2023-01-26T16:39:58Z)
• On the Sparse DAG Structure Learning Based on Adaptive Lasso [39.31370830038554]
  We develop a data-driven DAG structure learning method without the predefined threshold, called adaptive NOTEARS [30] We show that adaptive NOTEARS enjoys the oracle properties under some specific conditions. Furthermore, simulation results validate the effectiveness of our method, without setting any gap of edges around zero.
  arXiv  Detail & Related papers  (2022-09-07T05:47:59Z)
• Truncated Matrix Power Iteration for Differentiable DAG Learning [47.69479930501961]
  We propose a novel DAG learning method with efficient truncated matrix power to approximate series-based DAG constraints. Empirically, our DAG learning method outperforms the previous state-of-the-arts in various settings.
  arXiv  Detail & Related papers  (2022-08-30T23:56:12Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints. We propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly. We show that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models.
  arXiv  Detail & Related papers  (2021-06-14T07:11:36Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Learning DAGs without imposing acyclicity [0.6526824510982799]
  We show that it is possible to learn a directed acyclic graph (DAG) from data without imposing the acyclicity constraint. This approach is computationally efficient and is not affected by the explosion of complexity as in classical structural learning algorithms.
  arXiv  Detail & Related papers  (2020-06-04T16:52:01Z)

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.