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.

本研究解决了有向无环图（DAG）结构学习中的优化难题，尤其是由于DAG约束的非凸性和高计算复杂度带来的挑战。通过引入一种新的随机逼近框架，该方法结合了随机梯度下降（SGD）优化技巧，并设计了高效的投影方法以确保算法能收敛到可行的局部最优解。实验结果表明，该方法在大规模问题上具有显著的计算效率和优越的表现。

$ψ$DAG：用于DAG结构学习的投影随机逼近迭代