$ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910679307386880 |
|---|---|
| author | Ziu, Klea Hanzely, Slavomír Li, Loka Zhang, Kun Takáč, Martin Kamzolov, Dmitry |
| author_facet | Ziu, Klea Hanzely, Slavomír Li, Loka Zhang, Kun Takáč, Martin Kamzolov, Dmitry |
| contents | Learning the structure of Directed Acyclic Graphs (DAGs) presents a significant challenge due to the vast combinatorial search space of possible graphs, which scales exponentially with the number of nodes. Recent advancements have redefined this problem as a continuous optimization task by incorporating differentiable acyclicity constraints. These methods commonly rely on algebraic characterizations of DAGs, such as matrix exponentials, to enable the use of gradient-based optimization techniques. Despite these innovations, existing methods often face optimization difficulties due to the highly non-convex nature of DAG constraints and the per-iteration computational complexity. In this work, we present a novel framework for learning DAGs, employing a Stochastic Approximation approach integrated with Stochastic Gradient Descent (SGD)-based optimization techniques. Our framework introduces new projection methods tailored to efficiently enforce DAG constraints, ensuring that the algorithm converges to a feasible local minimum. With its low iteration complexity, the proposed method is well-suited for handling large-scale problems with improved computational efficiency. We demonstrate the effectiveness and scalability of our framework through comprehensive experimental evaluations, which confirm its superior performance across various settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23862 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | $ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning Ziu, Klea Hanzely, Slavomír Li, Loka Zhang, Kun Takáč, Martin Kamzolov, Dmitry Machine Learning Optimization and Control Learning the structure of Directed Acyclic Graphs (DAGs) presents a significant challenge due to the vast combinatorial search space of possible graphs, which scales exponentially with the number of nodes. Recent advancements have redefined this problem as a continuous optimization task by incorporating differentiable acyclicity constraints. These methods commonly rely on algebraic characterizations of DAGs, such as matrix exponentials, to enable the use of gradient-based optimization techniques. Despite these innovations, existing methods often face optimization difficulties due to the highly non-convex nature of DAG constraints and the per-iteration computational complexity. In this work, we present a novel framework for learning DAGs, employing a Stochastic Approximation approach integrated with Stochastic Gradient Descent (SGD)-based optimization techniques. Our framework introduces new projection methods tailored to efficiently enforce DAG constraints, ensuring that the algorithm converges to a feasible local minimum. With its low iteration complexity, the proposed method is well-suited for handling large-scale problems with improved computational efficiency. We demonstrate the effectiveness and scalability of our framework through comprehensive experimental evaluations, which confirm its superior performance across various settings. |
| title | $ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2410.23862 |