Anchored Variance Reduction for Large-Sample Nonlinear DAG Learning

Learning a causal graph from data means finding a directed acyclic graph (a DAG, a network of cause-to-effect arrows with no loops) that explains how each variable depends on the others. The dominant modern approach turns this into ordinary continuous optimization. It fits a model of each variable from its candidate parents and adds a smooth penalty that is zero only when the graph has no cycles. When the per-variable models are neural networks and the dataset has hundreds of thousands to millions of rows, as in DCDI's interventional experiments with up to $n=10^6$ samples (Differentiable Causal Discovery from Interventional Data), practitioners have two options. They can pay for a full pass over the data at every step, or they can use noisy mini-batch gradients. The noisy gradients never settle, so the learned edge weights keep jittering, and the procedure that decides when to tighten the acyclicity penalty reacts to that jitter rather than to real cycles.

This note proposes to fix that with variance reduction, which here means correcting each cheap mini-batch gradient using an occasional exact gradient computed at a reference point. The key design choice is structural. Differentiable DAG learners already solve a sequence of closely related subproblems, one per penalty level, and the solution of each subproblem makes a natural reference point for the next. One exact data pass per penalty stage, followed by corrected stochastic steps with a constant step size, should give the edge-weight precision of full-batch solvers at close to the cost of stochastic ones. It should also stop noise from triggering spurious increases in the penalty. The claim is deliberately limited to nonlinear, large-$n$ models. For linear models the whole idea is unnecessary, for a reason explained below.

Core Claim

In nonlinear continuous DAG learning, the data enters only through a finite sum of per-sample losses $\frac{1}{n}\sum_i \ell(\theta; x^{(i)})$. The acyclicity function $h$ depends only on the parameters, so it carries no sampling noise at all. The proposal therefore applies a control-variate correction to the data term only. At stage $k$ of the penalty path, let $\tilde\theta_k$ be the solution carried over from stage $k-1$, and let $B$ be a mini-batch. The inner loop then updates the network parameters $\theta$ with

$$g(\theta) = \nabla \ell_B(\theta) - c\,\big(\nabla \ell_B(\tilde\theta_k) - \nabla \mathcal{L}(\tilde\theta_k)\big) + \nabla_\theta\, \rho_k\, h(W(\theta)),$$

where $\ell_B$ is the mini-batch loss, $\mathcal{L}$ is the full-data loss, $W(\theta)$ is the implied weighted adjacency matrix, $\rho_k$ is the stage's penalty weight, and $c\in[0,1]$ is a scaling coefficient. The acyclicity gradient is exact. The correction term costs one full pass per stage. Because consecutive stages have nearby solutions, the reference point stays close to the iterate, and that closeness is what makes the correction effective.

The same scheme applies whether the path is augmented-Lagrangian (NOTEARS, GraN-DAG, DCDI) or barrier-style (DAGMA). The expected payoff is measured in causal terms rather than optimization gap: lower Structural Hamming Distance (SHD, the number of edge additions, deletions, or reversals needed to reach the true graph) and more stable edge thresholding at a fixed budget of per-sample gradient evaluations.

The central prediction is conditional. Gains appear when the cost of passing over the data dominates the cost of the acyclicity function. Evaluating $h$ costs $O(d^3)$ for $d$ variables, while a full data gradient through per-node networks of width $w$ costs roughly $O(n d^2 w)$. The data term therefore dominates when $n w \gg d$, which follows directly from comparing those two terms. The proposal is designed to test that crossover explicitly, not to assume it.

Relation to Prior Work

The continuous-optimization line supplies the problem and the constraint machinery, but always with full-batch solvers:

  • DAGs with NO TEARS introduced the trace-exponential acyclicity function inside an augmented Lagrangian solved with quasi-Newton methods.
  • DAGMA replaced it with a log-determinant function and a barrier path, reporting roughly 10x speedups up to 1,000 nodes.
  • Analytic DAG Constraints generalized the constraint family and reached 2,000 nodes.

All three evaluate every sample at every step. We keep their constraints unchanged and only change how the data gradient is estimated.

Two methods motivate the proposal by showing that stochasticity is already in use here, only uncorrected:

  • DCDI and GraN-DAG train neural conditionals with Adam- or RMSprop-style optimizers inside an augmented Lagrangian.
  • ψDAG is the closest existing work. It casts linear DAG learning as stochastic approximation with a discrete topological-ordering projection, scales to $d=10{,}000$, and proves an $O(1/\sqrt{T})$ rate that it attributes to plain stochastic gradients.

We differ from ψDAG in three ways. We target nonlinear models, where the finite sum is real. We keep a smooth acyclicity function rather than a discrete projection. And the noise correction is the whole contribution.

DAGs with No Fears constrains the design. It shows that the squared-weight constraint makes exact first-order stationarity (the KKT conditions) nearly unattainable, and that a local search guided by those conditions cuts SHD by a factor of two or more. We therefore do not claim that variance reduction fixes landscape pathologies. We treat that local search as a post-processing step that is orthogonal to ours and can be stacked on top.

The method comes from the variance-reduction literature:

We choose snapshot methods over table-based methods like SAGA because a stored gradient per sample, costing $O(np)$ memory for $p$ parameters, is infeasible at $n=10^6$. Stochastic Optimization with Variance Reduction for Infinite Datasets makes that trade-off explicit.

Research Program

The build has three parts.

The anchored estimator. First, we implement the estimator above inside two reference learners: a DCDI-style augmented Lagrangian with Gaussian neural conditionals, and a DAGMA-style barrier path with multilayer-perceptron conditionals. The reference point is refreshed at every stage transition. We also add an optional mid-stage refresh, triggered when $\|\theta-\tilde\theta_k\|$ grows beyond a multiple of the previous stage's step. This keeps the correction valid when a stage moves far, and it addresses the sensitivity to epoch length that both Acc-Prox-SVRG and TRSVR document.

Noise-free penalty decisions. Second, we make the decisions that move along the path depend only on quantities that are free of sampling noise. Multiplier updates and the choice to increase $\rho$ are taken at reference points, using $h$ at the stage's final iterate and the exact full gradient already computed there. We then measure how often plain stochastic training inflates $\rho$ prematurely.

Analysis. Third, the analysis combines standard nonconvex SVRG complexity within each stage with a warm-start argument. If consecutive stage solutions are within distance $\delta_k$, the variance of the correction at the start of stage $k$ is bounded by a smoothness constant times $\delta_k^2$. This yields a total cost of roughly $K$ data passes plus stochastic steps for $K$ stages. We will state this only as far as it can actually be proved, and we will measure $\delta_k$ empirically.

Baselines

Naive reference. The published DCDI and GraN-DAG training recipes run unchanged, using adaptive stochastic optimizers with their original batch sizes and step-size schedules. This is what practitioners do today. We use the authors' hyperparameters and then give them the same per-sample-gradient budget as our method, including any extra passes that our reference gradients consume.

Strongest stochastic competitor. The same learners trained with Adam under a tuned step-size decay and a tuned batch size up to 10% of $n$. Each method receives an identical hyperparameter search of 30 configurations scored on held-out log-likelihood, never on SHD. This baseline is the real threat, because large batches plus decay also shrink the noise.

Strongest full-batch competitor. Full-data DAGMA-nonlinear and NOTEARS-style quasi-Newton, run on a random subsample sized so that wall-clock matches ours. We sweep subsample fractions of 1%, 10%, and 100% where the full set is feasible.

For large-$d$ linear graphs, ψDAG with its released settings is included only as a reference point for where the stochastic linear frontier sits.

On Sachs, the best reported figure in the file is GraN-DAG's SHD of 13. For ψDAG the file reports only that it beats GOLEM and NOTEARS in SHD and that DAGMA failed, with no numbers. For DCDI's synthetic interventional benchmarks there is no reported result found on Lacuna for SHD or SID. The Adam baselines will therefore be rerun, not quoted.

Beating the baselines means reaching a lower median SHD over 10 seeds at matched gradient budget in the large-$n$ regime ($n \ge 10^5$). The advantage should be at least one standard error, it should hold against both the tuned Adam and the subsample full-batch baselines, and it should come with no worse SID (structural interventional distance, the number of interventional distributions the learned graph gets wrong).

Ablations. Four ablations isolate the ingredients:

  • Coefficient $c=0$ recovers plain stochastic training on our path.
  • Coefficient $c=1$ is full-strength SVRG.
  • A per-epoch reference refresh that ignores the stage structure tests whether anchoring to the path matters.
  • Stochastic penalty decisions paired with variance-reduced inner steps separate the benefit of cleaner iterates from the benefit of cleaner penalty control.

Why not just…?

Why not just precompute sufficient statistics? For linear least-squares models the loss depends on the data only through the $d\times d$ sample covariance. After one $O(nd^2)$ pass, full gradients cost nothing in $n$, and stochastic gradients of any kind, including ψDAG's, buy nothing in sample size. This objection is decisive for linear models, and it is why we exclude them from the core claim. It fails for neural conditionals, where no fixed-size summary of the data exists. We will include the linear case once, as a sanity check where our method should tie the covariance-based full-batch solver.

Why not just subsample the data and run a full-batch solver? This is a genuine threat. Statistical error scales like $1/\sqrt{n}$, and if a 10% subsample already recovers the graph, extra optimization precision is wasted. Our bet is that large $n$ matters for weak edges and for interventional settings where each intervention regime contributes only part of the data. The subsample sweep settles it. If full-batch training on 10% matches us at equal wall-clock, including on edges with small weights, the proposal's value collapses to convenience, and we will report that.

Why not just use Adam with bigger batches and step-size decay? Decay does remove the noise floor asymptotically, and TRSVR reports adaptive stochastic methods plateauing at optimality gaps of $10^{-2}$ to $10^{-5}$ versus $10^{-10}$ for variance-reduced ones. However, that result is on classification, not causal discovery, and optimization gap is not SHD. The tuned-Adam baseline, together with our count of premature penalty increases, will show whether the noise actually costs edges. We commit to reporting SHD, not gap.

Why not just use ψDAG? ψDAG is fast and scales in $d$. However, it is linear, it uses a discrete projection, and it is limited to an $O(1/\sqrt{T})$ rate. It does not address nonlinear large-$n$ learning, which is our target regime. We compare against it only where regimes overlap, and we do not claim to beat it at $d=10{,}000$.

Proposed Experiments and Decisive Checks

Synthetic benchmarks. These use Erdős–Rényi and scale-free graphs (the latter have hub nodes, as gene networks do) with expected degrees 1, 2, and 4, $d\in\{20,50,100\}$, and $n\in\{10^4,10^5,10^6\}$. Mechanisms are nonlinear additive-noise and random-MLP, following GraN-DAG, plus DCDI's perfect and imperfect interventional regimes.

Additional benchmarks. CausalProfiler's NN-Large space (CausalProfiler) guards against benchmark-specific tuning. Sachs serves as a small real-data check against the reported SHD of 13.

Metrics. We report SHD and SID, and curves of SHD against per-sample gradient evaluations and against wall-clock. We also report the number of penalty increases, the final value of $h$, and the variance of each thresholded edge's inclusion across seeds, broken down by true edge weight.

Decisive checks. Four results would decide the question:

  1. At $n=10^6$, $d=100$, the anchored method should reach tuned-Adam's final SHD in fewer gradient evaluations, and it should beat full-batch training on a subsample at equal time.
  2. The gain should concentrate on weak edges and shrink as $n$ falls to $10^4$.
  3. Premature penalty increases should drop measurably relative to $c=0$.
  4. Across a sweep of $d$ at fixed $n$, the advantage should vanish as $d$ grows past $n w$, where acyclicity evaluation dominates cost.

If the first or second check fails, the idea does not hold in its current form. If the fourth fails in the opposite direction, meaning gains persist even when data passes are cheap, the benefit would be coming from penalty control rather than cost, and the claim would be reframed around that.