$ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning
This work addresses the problem of DAG structure learning for researchers and practitioners in machine learning, offering an incremental improvement over existing methods by optimizing computational complexity.
The paper tackles the challenge of learning Directed Acyclic Graph (DAG) structures by introducing a novel framework that uses Stochastic Approximation with SGD-based optimization and tailored projection methods to enforce DAG constraints efficiently, resulting in improved computational efficiency and scalability for large-scale problems.
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.