Branching at the Saddles Where Continuous DAG Learners Choose an Ordering

Continuous causal discovery methods learn a directed acyclic graph (DAG, a graph of cause-and-effect arrows with no loops) by turning the search over graphs into smooth optimization of a weight matrix. A penalty that rises with the number of cycles is turned up gradually until the matrix becomes acyclic. These methods are fast, but they often land on graphs with many wrong edges. On a 50-node complete graph, NOTEARS reaches a structural Hamming distance (SHD, the count of edge additions, deletions and reversals needed to reach the true graph) of about 1198, against 19 for a discrete-swap method (Optimizing NOTEARS Objectives via Topological Swaps). Our hypothesis is that much of this error is decided at a few identifiable moments. As the penalty grows, symmetric configurations, where two variables point at each other with similar weight, turn into saddle points. A saddle is a stationary point that curves down in some direction. At each one the optimizer must commit to one arrow direction or the other. Today that choice is made by whatever numerical or mini-batch noise happens to push the iterate off the saddle.

The proposal is to detect those saddles cheaply, using Hessian-free negative-curvature probes borrowed from the saddle-escape literature, and to replace the noise-driven choice with a deliberate two-sided test. The optimizer steps off the saddle in both directions along the downward-curving direction, descends briefly on each side, and keeps the better branch. In two sentences: continuous DAG learners pick a causal ordering at saddle points that appear along the penalty schedule, and they pick it by accident. We find those saddles with stochastic first-order curvature probes and pick deliberately, which should give much of the benefit of discrete topological swaps inside a single continuous run.

Core Claim

The obvious combination of the two directions is to run perturbed gradient descent on NOTEARS. That combination is probably wrong-headed. Perturbation methods such as How to Escape Saddle Points Efficiently only help at strict saddles, and the end-of-run traps in DAG learning are mostly genuine local minima. A DAG with a reversed edge is optimal within its own ordering, and no small perturbation reaches the other ordering. This is exactly why Optimizing NOTEARS Objectives via Topological Swaps (TOPO) needs discrete swaps, and why L-BFGS solutions studied by On the Convergence of Continuous Constrained Optimization for Structure Learning still stall at suboptimal points.

Our claim concerns where those local minima come from. A two-variable example shows the mechanism. Take standardized variables with correlation $r$, edge weights $a$ (for $x_1 \to x_2$) and $b$ (for $x_2 \to x_1$), and the leading-order cycle penalty:

$$f_\rho(a,b) = \tfrac12(1 - 2ar + a^2) + \tfrac12(1 - 2br + b^2) + \tfrac{\rho}{2}a^2 b^2 .$$

The symmetric stationary point $a=b=s$ satisfies $s + \rho s^3 = r$. There, the Hessian (matrix of second derivatives) has eigenvalue $1 - \rho s^2$ along the direction $(1,-1)$. Once $\rho s^2 > 1$, the symmetric point is a strict saddle, and its downward direction is exactly "strengthen one arrow, weaken the other." The ordering is chosen when the iterate leaves this saddle. With unequal noise variances the two branches have different loss, and the optimizer has no reason to take the better one.

We conjecture that in larger graphs such bifurcations occur for contested pairs, and small groups of variables, at different penalty levels. We further conjecture that the eventual wrong orientations are mostly traceable to bad exits from them. If so, a curvature-triggered two-sided branch addresses the error where it is created. It does so before the acyclicity constraint becomes degenerate, which in the Ng et al. sense means the constraint's gradient vanishes at every DAG.

Research Program

The program has three parts: a landscape census, an algorithm, and a small theory.

Landscape census. The census comes first because the whole idea depends on it. We will run the standard quadratic-penalty and augmented-Lagrangian continuations on linear-Gaussian, Gumbel and exponential-noise structural equation models. Data will come from Erdős–Rényi and scale-free graphs with 10 to 100 nodes. At the end of each penalty stage we will estimate the most negative Hessian eigenvalue and its eigenvector using Lanczos iteration on automatic-differentiation Hessian-vector products. We will then record three things: when strict saddles appear, which edge pairs their downward directions load on, and whether the final orientation of those pairs is correct. The outcome is a measured fraction of final orientation errors that trace back to a detected saddle exit.

Algorithm. The algorithm keeps the usual penalty continuation and inner solver, L-BFGS as recommended by Ng et al., and adds a probe after each stage. The probe follows the first-order power-iteration idea of First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time: perturb the iterate randomly, take a few mini-batch gradient steps, and compare against the unperturbed trajectory. This amplifies the downward direction $v$ without forming a Hessian. To keep cost low, the probe can be restricted to "contested" pairs where both $w_{ij}$ and $w_{ji}$ are non-negligible. If the estimated eigenvalue is below a threshold $-\gamma$, we form the two points $W \pm \eta v$, run a short descent from each, and keep the one with the lower penalized score. A beam variant keeps the best $B$ branches.

This step differs from both lines of prior work. Perturbed methods in the style of Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent exit in one random direction, because for them any exit is good. Here the two exits lead to different orderings, so the choice between them is the point. TOPO, in contrast, swaps orderings only after convergence and evaluates many candidate swaps with repeated inner solves. Our branching fires only where the landscape actually forks, which should be a small number of events.

Theory. We will derive, for the pairwise-decoupled linear model, the penalty level at which each contested pair bifurcates. We will also show that the downward direction aligns with the orientation flip, and that two-sided branching selects the orientation with lower penalized score. Noise-driven exit, by contrast, selects by basin geometry. We will not claim second-order stationarity guarantees on the acyclic set itself. That set is a union of subspaces with vanishing constraint gradients, the setting that both Escaping Saddle Points in Constrained Optimization and Efficiently escaping saddle points on manifolds exclude. Instead, we deliberately act at finite penalty, where the problem is smooth and unconstrained.

If time permits, we will run the same census on the indefinite graph-matching relaxation of Graph Matching: Relax at Your Own Risk under correlated Bernoulli graphs. This is a secondary check of generality, not part of the core claim.

Baselines

Plain penalty continuation. The naive reference is NOTEARS solved by quadratic-penalty or augmented-Lagrangian continuation with L-BFGS, as analyzed by On the Convergence of Continuous Constrained Optimization for Structure Learning, with whatever numerical noise it has. It isolates what branching adds to an otherwise identical run. The strongest reported figure is NOTEARS at SHD about 1198 on the 50-node complete graph in the TOPO paper, which we will reproduce before comparing.

TOPO. The strongest competitor is TOPO (Optimizing NOTEARS Objectives via Topological Swaps). It attacks the same failure, wrong orderings, directly and reports SHD 19 on the 50-node complete graph and up to a 90% SHD reduction over NOTEARS on dense graphs. We will run TOPO from its released settings and in two further configurations: from our method's output as initialization, and under a wall-clock budget matched to ours.

Beating TOPO in the strict sense means equal or lower SHD at lower wall-clock as $d$ grows to 100 and beyond. The weaker but still useful outcome is that our output, used as TOPO's initialization, cuts TOPO's swap count and runtime substantially without hurting SHD.

Bayesian samplers. For context on stochastic exploration of orderings we include BayesDAG (BayesDAG: Gradient-Based Posterior Inference for Causal Discovery), which reports an expected SHD of about 296 on 100-variable ER graphs versus about 362 for BCD. Its metric is a posterior expectation, so we will compare on its own metric, with matched compute, rather than against our point estimate's SHD.

Real data. On Sachs, the reported references are an SHD of 16 for DAGs with No Curl, and 7 correct plus 3 reversed edges for NOTEARS-MLP in Learning Sparse Nonparametric DAGs.

Ablations. Two ablations isolate the key ingredient. The first, a one-sided random exit, uses the same probe and the same trigger but a single random-sign exit. It tests whether the deliberate two-sided choice matters, or whether simply detecting and escaping the saddle is enough. The second, untargeted branching, branches at the same number of stage boundaries along random directions. It tests whether the curvature direction carries information.

All methods get the same samples, the same score (least squares plus $\ell_1$), the same final threshold, and the same hyperparameter search budget of 20 configurations each on held-out seeds.

Why not just…?

Why not just use L-BFGS, which already uses curvature? Ng et al. show that L-BFGS fixes the ill-conditioning that breaks Adam, yet it still converges to suboptimal stationary points. The 1198-versus-19 SHD gap in the TOPO paper is with an L-BFGS-B solver. A quasi-Newton method descends away from a saddle along whichever side it happens to be nudged toward; it does not compare the two sides. The plain-continuation baseline measures exactly this.

Why not just add perturbed gradient descent noise or use random restarts? This is the most direct cheap rival. A random exit is a coin flip between orderings. Restarts multiply cost by the number of restarts and resample every decision at once, rather than only the contested ones. The one-sided ablation and a restart baseline matched in total gradient evaluations will settle this. If restarts at equal compute match our SHD, the branching idea adds nothing and we will report that.

Why not just run TOPO after NOTEARS? This is a real threat. TOPO already escapes ordering traps and has strong reported numbers. Our bet is cost: TOPO evaluates candidate swaps with repeated inner solves, whereas branching acts only at the few saddles the census finds. If matched-wall-clock TOPO dominates at every scale we test, the method's contribution shrinks to an initializer for TOPO. The initialization experiment measures exactly that.

Why not just reparameterize so cycles are impossible? DAG-NoCurl and BayesDAG avoid the penalty, but neither removes the ordering decision. DAG-NoCurl's projection inherits its ordering from the initial unconstrained estimate, and BayesDAG needs MCMC chains to move between orderings. Our census can be run on BayesDAG's potential parameterization as a check on whether saddle-located ordering choices are specific to penalty methods.

Proposed Experiments

The decisive first check is the census. If fewer than roughly a third of final orientation errors on 20–100 node ER and scale-free graphs trace to detected saddle exits, the premise fails and we stop. In that case orderings are set at initialization or at true minima, and branching cannot help.

If the census passes, the main experiments run three tests. The first is SHD, final penalized score, and wall-clock against all baselines on linear SEMs with Gaussian, Gumbel and exponential noise, including the 50-node complete-graph setting where TOPO's number is reported. The second runs on both raw and standardized data. Standardization equalizes variances, and with equal variances the two branches in the two-variable example have equal loss. So we expect the two-sided test to matter most on unstandardized, unequal-noise data, and that difference is itself a prediction. The third is Sachs as a real-data check.

A scaling run to several hundred nodes, using the edge-preselection idea of Stable Differentiable Causal Discovery to limit contested pairs, will test whether branching events stay few as $d$ grows. That outcome determines whether the cost advantage over TOPO holds. Finally, we will run the probe with both full-batch and mini-batch gradients to see whether mini-batch noise alone resolves saddles well. That would be consistent with Escaping Saddles with Stochastic Gradients. Persistent trapping would instead be consistent with SGD May Never Escape Saddle Points.