Constraint-Free Structure Learning with Smooth Acyclic Orientations
- URL: http://arxiv.org/abs/2309.08406v1
- Date: Fri, 15 Sep 2023 14:08:09 GMT
- Title: Constraint-Free Structure Learning with Smooth Acyclic Orientations
- Authors: Riccardo Massidda, Francesco Landolfi, Martina Cinquini, Davide Bacciu
- Abstract summary: We introduce COSMO, a constraint-free continuous optimization scheme for acyclic structure learning.
Despite the absence of explicit constraints, we prove that COSMO always converges to an acyclic solution.
- Score: 16.556484521585197
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The structure learning problem consists of fitting data generated by a
Directed Acyclic Graph (DAG) to correctly reconstruct its arcs. In this
context, differentiable approaches constrain or regularize the optimization
problem using a continuous relaxation of the acyclicity property. The
computational cost of evaluating graph acyclicity is cubic on the number of
nodes and significantly affects scalability. In this paper we introduce COSMO,
a constraint-free continuous optimization scheme for acyclic structure
learning. At the core of our method, we define a differentiable approximation
of an orientation matrix parameterized by a single priority vector. Differently
from previous work, our parameterization fits a smooth orientation matrix and
the resulting acyclic adjacency matrix without evaluating acyclicity at any
step. Despite the absence of explicit constraints, we prove that COSMO always
converges to an acyclic solution. In addition to being asymptotically faster,
our empirical analysis highlights how COSMO performance on graph reconstruction
compares favorably with competing structure learning methods.
Related papers
- Non-negative Weighted DAG Structure Learning [12.139158398361868]
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.
arXiv Detail & Related papers (2024-09-12T09:41:29Z) - Kernel-Based Differentiable Learning of Non-Parametric Directed Acyclic Graphical Models [17.52142371968811]
Causal discovery amounts to learning a directed acyclic graph (DAG) that encodes a causal model.
Recent research has sought to bypass the search by reformulating causal discovery as a continuous optimization problem.
arXiv Detail & Related papers (2024-08-20T16:09:40Z) - Recovering Linear Causal Models with Latent Variables via Cholesky
Factorization of Covariance Matrix [21.698480201955213]
We propose a DAG structure recovering algorithm, which is based on the Cholesky factorization of the covariance matrix of the observed data.
On synthetic and real-world datasets, the algorithm is significantly faster than previous methods and achieves the state-of-the-art performance.
arXiv Detail & Related papers (2023-11-01T17:27:49Z) - 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) - Object Representations as Fixed Points: Training Iterative Refinement
Algorithms with Implicit Differentiation [88.14365009076907]
Iterative refinement is a useful paradigm for representation learning.
We develop an implicit differentiation approach that improves the stability and tractability of training.
arXiv Detail & Related papers (2022-07-02T10:00:35Z) - Efficient Neural Causal Discovery without Acyclicity Constraints [30.08586535981525]
We present ENCO, an efficient structure learning method for directed, acyclic causal graphs.
In experiments, we show that ENCO can efficiently recover graphs with hundreds of nodes, an order of magnitude larger than what was previously possible.
arXiv Detail & Related papers (2021-07-22T07:01:41Z) - 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) - A Bregman Method for Structure Learning on Sparse Directed Acyclic
Graphs [84.7328507118758]
We develop a Bregman proximal gradient method for structure learning.
We measure the impact of curvature against a highly nonlinear iteration.
We test our method on various synthetic and real sets.
arXiv Detail & Related papers (2020-11-05T11:37:44Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem.
We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent.
Our algorithm is applied to solve problems with one variable under the sparsity constraint.
arXiv Detail & Related papers (2020-06-16T13:41: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.