Continuous causal discovery treats learning a causal graph as one smooth optimization problem. The graph is a directed acyclic graph (DAG): a set of cause-to-effect arrows with no loops. The method fits a weighted adjacency matrix $W$ to data under an algebraic penalty that is zero only when the matrix has no cycles. The cost is that every iteration updates all $d^2$ possible edges and evaluates a $d \times d$ matrix exponential, which takes order $d^3$ time. Yet the graphs people care about are sparse. A gene network over 600 genes might have a few thousand real edges out of 360,000 candidates. Sparse regression solved the same mismatch long ago with active-set (working-set) methods. These solvers keep a small set of variables they currently believe are nonzero, optimize only those, and periodically check the optimality conditions to decide which excluded variables should come back in.
We propose to carry that machinery into continuous DAG learning. The solver optimizes only a small working set of edges. An edge is admitted when a cheap per-edge optimality test fails, and in that test the acyclicity penalty acts as an extra, edge-specific sparsity weight. The cycle penalty is evaluated only on the strongly connected pieces of the current sparse graph. Edges are recruited and released throughout the solve rather than fixed by a screening step in advance. This should make continuous DAG learning scale with the number of true edges rather than with $d^2$ or $d^3$, without the error propagation that comes from freezing a skeleton (the undirected set of connections) up front.
Core Claim
Take the linear structural-equation objective with the non-smooth absolute-value acyclicity function advocated in DAGs with No Fears:
$$\min_W \; \ell(W) + \lambda \|W\|_1 \quad \text{s.t.} \quad h(|W|) = \operatorname{Tr}(e^{|W|}) - d = 0.$$
Here $\ell(W) = \frac{1}{2n}\|X - XW\|_F^2$ is the least-squares fit on the data matrix $X$ ($n$ samples by $d$ variables), $\lambda$ is the sparsity weight, and $|W|$ is the entrywise absolute value. Inside an augmented Lagrangian loop with multiplier $\alpha$ and penalty $\rho$, the constraint grows locally linearly in $|W_{ij}|$ at a zero entry, with slope $G_{ij} = (e^{|W|})_{ji}$. That slope is a weighted count of directed paths from $j$ to $i$; Wei et al. prove this pathfinding property of the gradient. The optimality (KKT) condition for keeping an edge at zero is therefore
$$|\nabla_{ij}\ell(W)| \le \lambda + (\alpha + \rho\, h(|W|))\, G_{ij}.$$
This is a weighted-lasso screening test in which edges that would close a cycle carry a larger threshold. Edges whose reverse path does not exist have $G_{ij}=0$ and reduce to the ordinary lasso test.
Two consequences make an active-set solver natural. First, $G_{ij}$ is nonzero only for pairs connected by a path in the current sparse graph, so it can be computed with sparse reachability and sparse matrix-exponential-times-vector products rather than a dense $e^{W}$. Second, the trace of the matrix exponential counts closed walks, which never leave a strongly connected component. So $h$ and its gradient decompose exactly over the strongly connected components of the active graph, and those components are typically tiny and vanish as the solve converges to a DAG. The claim is that a solver built on these two facts converges to the same KKT points as the dense absolute-value solver. It should also run in time governed by the active-set size and the largest strongly connected component, not by $d^3$.
Relation to Prior Work
Prior work plays three roles here: some papers supply the method, some motivate the gap, and some set the bar.
Three papers supply the method. DAGs with No Fears supplies the formulation. It shows that the squared form $W \odot W$ has vanishing gradients at zero, so KKT conditions essentially never hold, whereas $|W|$ restores meaningful KKT conditions. It then uses those conditions only in a discrete local search (KKTS) run after an early-stopped dense solve. We use the same conditions during optimization to decide which edges exist at all. The working-set mechanics come from sparse regression. Thunder recruits features from a warm/cold two-tier pool with sampling and duality-gap stopping, and scales with the true support up to $10^8$ features. PDASC partitions variables using primal and dual information and walks down a $\lambda$ continuation path with a BIC stopping rule. Both assume convex objectives; ours is non-convex, which is where the new analysis is needed.
The analysis lens comes from "Active-set complexity" of proximal gradient. That paper bounds the iterations needed to lock onto the final sparsity pattern as logarithmic in $1/\delta$, where the margin $\delta$ measures how far the optimal gradient sits inside the subdifferential, but only under strong convexity. We aim at a local analogue for a fixed augmented-Lagrangian subproblem.
Two papers motivate the gap. On the Sparse DAG Structure Learning Based on Adaptive Lasso replaces ad hoc thresholding with a reweighted second pass. That shows the field wants principled sparsity, but it doubles the dense $d \times d$ cost. Our acyclicity-weighted threshold is a structurally motivated reweighting that comes for free from the KKT condition. SPOT constrains the design. It reports that treating an estimated skeleton as a hard constraint fails because screening errors cannot be undone, and it softens the skeleton with a posterior and annealing. Our working set is dynamic for the same reason, and it uses a deterministic dual test rather than a learned posterior.
The closest competitor is Optimizing NOTEARS Objectives via Topological Swaps. TOPO searches over node orderings with KKT-guided swaps and solves an order-constrained inner problem. It reports SHD 19 versus about 1198 for NOTEARS on a fully connected 50-node graph, where SHD (structural Hamming distance) counts the edge additions, deletions, and reversals needed to turn the estimate into the true graph. TOPO keeps a working set over orders. We keep one over edges and never fix an order, and TOPO itself names inner-loop cost at thousands of nodes as its open problem. Active Set Ordering shares the name but concerns top-$k$ identification of a black-box function under Gaussian-process models, so it is not a competitor here.
Research Program
We will build the solver in three layers. The inner layer runs proximal-gradient or block coordinate descent on the active edges only, for a fixed $(\alpha, \rho)$. Each step costs time proportional to the number of active edges times $n$, plus the strongly connected component computation on the active graph.
The recruitment layer computes the loss gradient for candidate inactive edges. In the linear model this is a column of $S(W - I)$ for the sample covariance $S$; the gradient of the regression of $X_j$ on its parents is $S_{\cdot j} - S W_{\cdot j}$. Candidates are drawn from a warm pool, consisting of recently released edges and edges with large covariance with current residuals, while the cold pool is scanned by sampling in the style of Thunder. The path weights $G_{ij}$ are computed only for candidates that sparse reachability flags as cycle-closing. The single largest violation per column, or a batch of them, is admitted. Active edges that hit zero and satisfy the test with margin are released. Released edges stay eligible for re-entry, which separates this design from static screening.
The outer layer is the usual augmented-Lagrangian schedule on $(\alpha, \rho)$, combined with continuation in $\lambda$ from large to small, with a BIC stopping rule borrowed from PDASC. This replaces the fixed 0.3 weight threshold.
On the analysis side, we will prove that a full scan with an exact KKT test certifies first-order stationarity of the dense augmented-Lagrangian subproblem. The working-set solver therefore loses nothing at convergence; only the sampled cold scan is heuristic, and we will measure how often a final full scan finds a violation. We will also attempt a local identification result: near a nondegenerate KKT point where the subproblem restricted to the correct support is strongly convex, proximal steps lock the support within a number of iterations logarithmic in $1/\delta$. Here $\delta$ is the slack in the displayed inequality, which now includes the acyclicity term. We expect the margin to be largest exactly for reversed edges, because the path weight inflates their threshold. That would predict reversals are identified faster than spurious additions, and this prediction can be checked empirically.
Baselines
The naive reference point is dense NOTEARS-style optimization with the absolute-value constraint, run to convergence and followed by the conventional 0.3 threshold. This is the same objective without the working set, so any accuracy gap isolates numerical rather than modelling effects, and the runtime gap isolates the working set. The same objective with the squared constraint is reported too, as the historically standard variant.
The strongest repair method is KKTS from DAGs with No Fears: an early-stopped dense solve followed by KKT-guided local search. That paper reports SHD reduced "by a factor of 2 or more" relative to NOTEARS across ER and SF graphs up to 100 nodes. Beating it means matching its SHD at those sizes while cutting wall-clock time, and remaining runnable where its dense phase runs out of memory.
The strongest accuracy competitor is TOPO from Optimizing NOTEARS Objectives via Topological Swaps. On the fully connected 50-node challenge it reports SHD 19, and it reports up to 90% SHD reduction over NOTEARS on dense graphs. We will run TOPO both with its released inner solver and with a fast sparse lasso inner solver substituted, as described below. Every method gets the same data, the same $\lambda$ grid or BIC selection, the same thread count, and the same per-instance time limit. Beating TOPO means comparable SHD on ER/SF graphs and better SHD-versus-time curves beyond a few hundred nodes. We do not expect to beat it on the fully connected graph, where sparsity buys nothing; we report that case as a stress test where we expect to lose.
For sparsity selection we compare against NOTEARS-AL, which reports Sachs SHD 19 versus 20 for NOTEARS. For Sachs skeleton recovery the bar is SPOT's skeleton F1 of 0.63 versus 0.48 for ABIC, though SPOT targets latent-confounder graphs and the comparison is indicative only.
On CausalBench the naive non-causal references are GRNBoost and Sortnregress, which CausalBench found frequently outperform causal methods. The file gives no specific values; no reported result found on Lacuna for GRNBoost or Sortnregress scores on K562/RPE1. For speed, Sample, estimate, aggregate reports SEA producing a 622-gene prediction in 5 seconds, against 5 minutes for the fastest traditional baseline and 9 hours for the most advanced deep learning baseline.
Two ablations isolate the key ingredient. The first freezes the working set after the first recruitment round (no re-entry), which is static screening by another name. The second drops the acyclicity term from the recruitment threshold, so edges are tested by the plain lasso rule and cycles are left to the outer penalty.
Why not just…?
Why not just screen a skeleton with neighborhood lasso and run NOTEARS on that fixed support? This is the main threat, because at large $d$ most of the speedup might come from screening alone. SPOT reports that hard skeleton constraints propagate screening errors, but in a latent-confounder setting. We settle the question with the frozen-working-set ablation, matched to the same final support size. We report the fraction of true edges lost by screening and the resulting SHD gap, as a function of $n/d$. If static screening matches us at $n = 1000$, we expect the gap to open at $n = 2d$, where lasso screening is least reliable. If it does not open, the honest conclusion is that dynamic recruitment is unnecessary for linear Gaussian data, and we will say so.
Why not just plug a fast lasso solver into TOPO? Given an order, the inner problem is $d$ independent lasso regressions, each restricted to predecessors, which Thunder-style solvers handle well. This is a real competitor, so we include it as a baseline rather than dismiss it. Our expected advantage is that TOPO must still evaluate swap candidates over orders and resolve affected regressions after each swap, whereas we never commit to an order. The SHD-versus-time curves at $d$ = 500 to 5000 decide which matters more.
Why not just early-stop and repair with KKTS? The repair is cheap, but the early-stopped dense phase still holds a $d \times d$ matrix and computes a dense matrix exponential. Our method can feed KKTS a sparse near-DAG, so we also run working-set solve plus KKTS. That would show whether the two are complements rather than rivals.
Why not just use GRNBoost or variance sorting? On CausalBench these are strong for recall, but they return rankings rather than acyclic directed graphs. We report them and expect to lose to them on some ranking metrics. Our claim on that benchmark is that we make a causal-structure method feasible at 622 nodes, not that we resolve its biological evaluation paradox.
Proposed Experiments
The synthetic suite follows the ER1/ER2/ER4 and SF protocols used by Wei et al., TOPO, and NOTEARS-AL. It covers Gaussian, Gumbel, and exponential noise and $n \in \{1000, 2d\}$, but extends $d$ from 100, the largest size those papers report, to 500, 1000, 2000, and 5000. Metrics are SHD, true positive rate, false discovery rate, wall-clock time, peak memory, maximum active-set size, and largest strongly connected component over the run. The real-data checks are Sachs (11 proteins, 911 samples) and the CausalBench K562 subset with 622 interventions, using the benchmark's STRING/CORUM overlap and Wasserstein/false-omission metrics; interventional samples enter only through the loss.
The decisive checks are four. First, at $d \le 100$ the working-set solver must reach SHD within noise of the dense absolute-value solver, and a final exact full scan must find KKT violations in fewer than a small fraction of runs. Otherwise the speedup is bought with accuracy. Second, runtime should grow roughly with the number of true edges, as Thunder found for sparse regression: a log-log slope near 1 in edge count for ER2, against roughly 3 in $d$ for the dense solver. Third, the full method must beat the frozen ablation at $n = 2d$ by a margin larger than seed variance; this is what justifies dynamic recruitment over screening. Fourth, removing the acyclicity term from the threshold should increase the number of cycles the outer loop must break and the number of recruited-then-released edges. That tests whether the path-weight term does real work.
References
- DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks
- Thunder: a Fast Coordinate Selection Solver for Sparse Learning
- A Primal Dual Active Set Algorithm with Continuation for Compressed Sensing
- "Active-set complexity" of proximal gradient: How long does it take to find the sparsity pattern?
- On the Sparse DAG Structure Learning Based on Adaptive Lasso
- Scalable Differentiable Causal Discovery in the Presence of Latent Confounders with Skeleton Posterior
- Optimizing NOTEARS Objectives via Topological Swaps
- Active Set Ordering
- CausalBench: A Large-scale Benchmark for Network Inference from Single-cell Perturbation Data
- Sample, estimate, aggregate: A recipe for causal discovery foundation models