The central challenge of causal discovery is identifying the directed acyclic graph (DAG) that represents the "ground truth" of how variables influence one another. Because the number of possible DAGs grows super-exponentially with the number of variables, finding the best-fitting model is an NP-hard combinatorial problem.
Historically, researchers relied on greedy search heuristics—like hill-climbing—to navigate this space. However, a recurring theme across recent literature is that these local search strategies are fundamentally limited by local optima. A search algorithm can become "trapped" in a sub-optimal graph structure where no single local change (adding, removing, or reversing an edge) improves the model score, even if a vastly superior global structure exists.
The Greedy Trap and Precision Saturation
Greedy algorithms, such as Greedy Equivalence Search (GES), operate by making the best immediate move available. As Sofia Triantafillou and Peter Bühlmann have noted, these strategies are highly susceptible to early mistakes. If an algorithm incorrectly orients an edge early in the process, it may create a structural constraint that prevents it from ever reaching the true graph.
This leads to a phenomenon Kun Zhang identifies as precision saturation. In Improving Causal Discovery By Optimal Bayesian Network Learning, Zhang observes that for greedy algorithms, simply providing more data does not always improve accuracy. Once the search is trapped in a local optimum, the model maintains incorrect beliefs that are "consistent enough" with the data to prevent further movement, causing precision to plateau or even drop as the algorithm adds spurious edges to compensate for its initial structural errors.
Continuous Relaxations and Differentiable Search
To bypass the "jumpy," discrete nature of graph-based search, researchers like Xun Zheng and Pradeep Ravikumar introduced DAGs with NO TEARS. This framework transforms the combinatorial problem into a smooth, continuous optimization task by using a differentiable constraint for acyclicity.
By treating the adjacency matrix as a set of continuous weights, gradient-based solvers can navigate the landscape more fluidly. Sebastien Lachapelle extended this with GraN-DAG, using neural networks to capture nonlinear relationships. While these methods provide a more global view of the graph structure, they are not a silver bullet; Pavel Rytíř and Jakub Marecek point out in ExDBN that continuous relaxations can still fail to reach the true global optimum, sometimes settling for mathematically convenient approximations.
Searching Orderings Instead of Edges
A different strategy to avoid local optima involves changing the search space entirely. Instead of searching the space of all possible edge configurations, algorithms like FLOP (Fast Learning of Order and Parents) by Marcel Wienöbst and Sebastian Weichwald search the space of topological orderings.
The intuition is that if you know the correct order of variables (e.g., $X$ comes before $Y$), finding the optimal parents for each node becomes a much simpler, independent problem. While the space of permutations is still vast, it is often more "well-behaved" than the space of DAGs. Liam Solus and Yuhao Wang have worked to provide consistency guarantees for these permutation-based searches, ensuring they can converge to the true model as sample sizes grow.
Global Optimality through Exact Search
For high-stakes applications where "good enough" is insufficient, researchers have turned to exact search methods. These bypass heuristics entirely to find the mathematically optimal score.
- Integer Programming: Rui Chen and Sanjeeb Dash developed AGIP, which uses Integer Programming to learn causal structures even in the presence of unobserved confounders.
- Dynamic Programming: Mikko Koivisto and Kevin P. Murphy have explored using dynamic programming to calculate exact posterior probabilities for edges.
While computationally expensive, these exact methods serve as a vital baseline. They prove that the "local optima" problem is not a property of the data itself, but a limitation of the search strategies we use to uncover the underlying causal truth.