NOTEARS: Transforming Graph Structure Learning into a Continuous Optimization Problem

In machine learning and statistics, learning directed acyclic graphs (DAGs) from data has long been a highly challenging task. Traditional structure learning methods typically rely on combinatorial optimization, requiring navigation through complex discrete search spaces and often enforcing the 'acyclic' constraint via local heuristic rules. This discreteness makes algorithm implementation difficult, and computational complexity grows super-exponentially with the number of nodes.

In 2018, Xun Zheng et al. proposed a fundamentally different strategy in their paper "DAGs with NO TEARS: Continuous Optimization for Structure Learning": reformulating the structure learning problem as a purely continuous optimization problem over real-valued matrices. The core idea lies in constructing a smooth and exact function h(W), whose zero level set precisely characterizes acyclic graphs. By introducing this smooth equality constraint, the originally intractable combinatorial constraints are entirely eliminated, enabling the use of standard numerical algorithms (such as L-BFGS) for solution. This approach not only avoids the need for specialized algorithm design tailored to specific graphical models but also greatly simplifies implementation—core logic can be implemented in just about 50 lines of Python code.

The method's significant advantages lie in its generality and efficiency. Experiments show that even under small sample sizes or high-dimensional settings, the NOTEARS algorithm with ℓ1 regularization maintains high accuracy in structure recovery. Compared to previous methods relying on complex heuristic searches, NOTEARS demonstrates that state-of-the-art performance can be achieved—or even surpassed—through a continuous optimization framework, without imposing additional assumptions on the graph’s topology (e.g., bounded tree width or in-degree). For readers seeking deeper understanding of causal inference, Bayesian network structure learning, and modern optimization techniques in statistical modeling, this paper provides a clear and elegant example. It is recommended to read "DAGs with NO TEARS: Continuous Optimization for Structure Learning" (2018), starting from the abstract and introduction, focusing especially on Equation (1) and its corresponding technical contribution description, to quickly grasp the core idea of transforming discrete constraints into continuous ones.