📊 statistics

Concomitant DAG Learning: On the Roles of Noise Adaptivity, Sparsity, and Non-negativity

This tutorial reviews recent signal processing and optimization advances that reformulate directed acyclic graph (DAG) learning as a continuous, score-based estimation problem, with a specific focus on concomitant methods that jointly infer sparse causal structures and adaptive noise levels to overcome scalability and identifiability challenges in observational data.

Original authors: Gonzalo Mateos, Samuel Rey, Hamed Ajorlou, Mariano Tepper

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gonzalo Mateos, Samuel Rey, Hamed Ajorlou, Mariano Tepper

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out the order of events in a complex mystery. You have a pile of clues (data), but you don't have a witness who saw the crime happen. You only see the aftermath. Your goal is to draw a map showing who influenced whom, but with one strict rule: no time travel allowed. In other words, you cannot have a loop where A causes B, B causes C, and C causes A. This is the problem of learning a Directed Acyclic Graph (DAG).

This paper is a guidebook for detectives (data scientists) on how to draw this map more accurately, especially when the clues are messy. Here is the breakdown of their new tools and ideas, explained simply.

1. The Problem: The "Noisy" Clues

Usually, when detectives try to figure out cause-and-effect, they use a standard method called Ordinary Least Squares (OLS). Think of this like using a ruler that assumes every single clue is equally reliable.

The Flaw: In the real world, some clues are very clear, while others are fuzzy or distorted by "noise" (random interference). If your ruler assumes all noise is the same, but it's actually different for every clue, your map will be wrong.
The Tuning Knob: To fix this, old methods use a "tuning knob" (a parameter called $\lambda$ ) to decide how much to trust the data versus how much to assume the map should be simple (sparse). But here's the catch: you don't know how noisy the clues are. So, you have to guess the setting for the knob. If you guess wrong, your map is useless.

2. The New Tool: CoLiDE (The "Self-Calibrating" Detective)

The authors introduce a new method called CoLiDE (Concomitant Linear DAG Estimation).

The Analogy: Imagine a detective who doesn't just look at the clues but also carries a noise meter. Instead of guessing how loud the background noise is, the detective measures it while they are drawing the map.
How it works: CoLiDE solves two problems at once:
1. It figures out the map (who caused what).
2. It figures out the noise level for each specific clue.
The Benefit: Because it measures the noise itself, it doesn't need a "tuning knob" that you have to guess. It automatically adjusts to the situation. Whether the clues are crystal clear or very fuzzy, CoLiDE adapts. The paper shows that this works much better than old methods when the noise levels are different for different variables (a situation called heteroscedasticity).

3. The "No-Loop" Rule: Keeping the Map Valid

A major headache in this field is ensuring the map has no loops (cycles).

The Old Way: Previous methods used a complex mathematical "magic spell" (a function involving matrix exponentials) to check for loops. It was like trying to untangle a knot by looking at the whole ball of yarn at once. It worked, but it was computationally heavy and sometimes got stuck in "degenerate" spots where the math couldn't decide what to do.
The New Twist (Non-Negative Weights): The paper suggests a shortcut for certain types of problems. If you know that all influences are positive (e.g., one thing only adds to another, never subtracts), you can use a simpler, cleaner mathematical rule to ensure there are no loops.
The Result: This leads to a new algorithm called NOMAD. It's like switching from a tangled ball of yarn to a straight line. The math becomes much easier to solve, and the detective finds the correct map more reliably.

4. Real-World Testing

The authors tested their new tools on two types of scenarios:

Synthetic Data: They created fake worlds with 200 variables (nodes) and different types of noise. CoLiDE consistently drew more accurate maps than the previous "state-of-the-art" methods, especially when the noise was messy and varied.
Real Data (Cell Signaling): They applied their method to a famous dataset about how proteins interact in human immune cells. This is a real biological mystery. CoLiDE produced a map that was closer to the scientifically accepted "ground truth" than almost any other method tested, proving that their noise-adaptive approach works in the real world.

5. The Big Picture

The paper argues that to understand complex systems (like biology, finance, or social networks), we need to stop assuming all our data is equally clean. By building a system that learns the noise level while it learns the structure, we get a much more robust and accurate picture of cause and effect.

In summary:

Old Way: Guess the noise, guess the map, hope for the best.
CoLiDE: Measure the noise, draw the map, adapt automatically.
NOMAD: If you know the influences are only positive, use a simpler, faster math trick to get a perfect map.

The paper concludes that these tools are a significant step forward, but there is still work to be done on handling non-linear relationships and hidden variables that we can't see.

Technical Summary: Concomitant DAG Learning

Problem Statement

The paper addresses the fundamental challenge of learning Directed Acyclic Graphs (DAGs) from observational data, a task central to causal inference in fields ranging from biology to finance. This problem is formulated as recovering the adjacency matrix $W$ of a latent DAG $G$ from a dataset $X$ generated by a Structural Equation Model (SEM).

The core difficulties identified are:

Combinatorial Complexity: The space of DAGs grows superexponentially with the number of variables, making exact combinatorial search intractable.
Acyclicity Constraint: Enforcing the acyclicity constraint ( $G \in \mathcal{D}$ ) is non-convex and computationally difficult.
Identifiability and Noise: Distinguishing between DAGs that generate the same observational distribution is nontrivial. Furthermore, standard Ordinary Least Squares (OLS) approaches implicitly assume homoscedasticity (identical noise variances across variables). In heteroscedastic settings (where noise variances differ), OLS introduces bias, and the sparsity regularization parameter $\lambda$ becomes coupled with the unknown noise level, requiring laborious manual tuning.
Optimization Landscapes: Existing continuous relaxation methods often suffer from degenerate Karush-Kuhn-Tucker (KKT) conditions where gradients vanish at valid DAGs, complicating convergence.

Methodology

The paper proposes CoLiDE (Concomitant Linear DAG Estimation), a framework that integrates concomitant scale estimation into causal structure learning. The methodology is built on three pillars:

1. Concomitant Scale Estimation

Inspired by concomitant estimators in robust statistics (e.g., Huber's work and the smoothed concomitant lasso), CoLiDE jointly estimates the DAG adjacency matrix $W$ and the exogenous noise levels.

Homoscedastic Setting (CoLiDE-EV): The method minimizes a convex score function $S(W, \sigma; X)$ that includes a weighted least squares term, a sparsity penalty ( $\ell_1$ -norm), and a term for the noise scale $\sigma$ . The score is:
$\min_{W, \sigma \ge \sigma_0} \frac{1}{2n\sigma}\|X - W^\top X\|_F^2 + \frac{d\sigma}{2} + \lambda\|W\|_1$
subject to an acyclicity constraint. This formulation decouples the regularization parameter $\lambda$ from the unknown noise level $\sigma$ , eliminating the need for re-tuning across different noise regimes.
Heteroscedastic Setting (CoLiDE-NV): The framework extends to scenarios where each variable has a distinct noise variance. It estimates a diagonal matrix $\Sigma$ of noise standard deviations, minimizing a weighted trace loss:
$\min_{W, \Sigma \ge \Sigma_0} \frac{1}{2n} \text{tr}((X - W^\top X)^\top \Sigma^{-1} (X - W^\top X)) + \frac{1}{2}\text{tr}(\Sigma) + \lambda\|W\|_1$

2. Continuous Optimization and Acyclicity Characterization

The paper utilizes smooth, non-convex functions to relax the combinatorial acyclicity constraint.

DAGMA Penalty: CoLiDE adopts the log-determinant regularizer $H_{ldet}(W; s) = d \log(s) - \log(\det(sI - W \circ W))$ . This function is an exact characterization of acyclicity over a specific domain and offers improved gradient behavior and the ability to detect longer cycles compared to matrix exponential-based approaches (like NOTEARS).
Optimization Algorithm: The constrained problem is solved via a sequence of unconstrained problems using a barrier method approach. The algorithm employs an inexact Block Coordinate Descent (BCD) strategy:
1. Update $W$ using a first-order method (e.g., a single step of ADAM) on the augmented objective.
2. Update the noise estimate ( $\sigma$ or $\Sigma$ ) in closed form based on the current residuals.
3. This process repeats until convergence or a maximum iteration count is reached.

3. Non-Negative Edge Weights (NOMAD)

The paper also explores the impact of imposing non-negativity constraints on edge weights ( $W \ge 0$ ), which is valid in specific domains like excitatory neural networks or flow models.

Simplified Acyclicity: Under non-negativity, the acyclicity condition simplifies to $H_+(W; s) = d \log(s) - \log(\det(sI - W)) = 0$ . This avoids the Hadamard product ( $W \circ W$ ), leading to a more benign optimization landscape.
NOMAD Algorithm: The authors introduce NOMAD (Non-negative Optimization via Multipliers for Acyclic Digraphs), which uses the Method of Multipliers (Augmented Lagrangian) to solve the constrained problem. This approach avoids the KKT degeneracy found in general DAG learning, as DAGs are no longer stationary points of the penalty function.

Key Contributions

Noise-Adaptive Score Function: The introduction of a convex score function that jointly estimates the DAG and noise levels. This removes the coupling between the sparsity penalty and unknown noise levels, making the method robust to heteroscedasticity and distribution shifts without manual hyperparameter tuning.
Theoretical Guarantees: For linear Gaussian SEMs, the paper establishes that CoLiDE yields a DAG that is "quasi-equivalent" to the ground truth as the sample size $n \to \infty$ , even in non-identifiable heteroscedastic settings.
Optimization Landscape Analysis: The paper demonstrates that imposing non-negativity constraints eliminates degenerate KKT conditions, creating a landscape where the true DAG is the unique global minimizer of the population augmented Lagrangian (under specific assumptions).
Scalability and Online Learning: The framework supports mini-batch stochastic gradient descent and online updates, allowing for the tracking of time-varying structures and scalability to large datasets.

Results

The paper evaluates CoLiDE and NOMAD against state-of-the-art baselines (including GOLEM, DAGMA, NOTEARS, and GES) on synthetic and real-world data:

Synthetic Data: On Erdős–Rényi (ER4) and Scale-Free (SF4) graphs with 200 nodes, CoLiDE variants consistently outperform competitors in Structural Hamming Distance (SHD), False Discovery Rate (FDR), and True Positive Rate (TPR). Notably, CoLiDE maintains high performance when noise variance increases (from 1.0 to 5.0) without re-tuning, whereas OLS-based methods degrade significantly.
Heteroscedasticity: In heteroscedastic scenarios with varying noise distributions (Gaussian, Exponential, Laplace), CoLiDE-NV is the clear winner, outperforming all alternatives. CoLiDE-EV also performs robustly, often ranking second, demonstrating the value of the noise-adaptive formulation even when the problem is technically homoscedastic.
Real-World Data (Sachs Dataset): On the Sachs cell-signaling dataset ( $d=11, n=853$ ), CoLiDE-NV achieved an SHD of 12, outperforming other continuous optimization methods. The best overall performance (SHD=10) was achieved by NOMAD, which leverages the non-negativity constraint inherent in the biological system.

Significance and Claims

The paper positions CoLiDE as a significant step forward in bridging signal processing, optimization, and causal inference. Its primary significance lies in:

Robustness: By making the score function noise-adaptive, the method effectively handles the "unknown noise level" problem that plagues standard sparse regression and DAG learning, reducing the need for extensive hyperparameter tuning.
Handling Heteroscedasticity: It provides a principled solution for learning DAGs in heteroscedastic settings, a scenario where traditional OLS-based methods are known to be biased.
Optimization Efficiency: The use of concomitant estimation and specific acyclicity penalties (like DAGMA and the non-negative log-determinant) leads to better optimization landscapes and faster convergence compared to previous continuous relaxation methods.
Practical Applicability: The framework is designed to be scalable, supporting mini-batch and online learning, making it suitable for modern high-dimensional and streaming data applications.

The authors conclude that while global optimality guarantees remain elusive for general non-convex DAG learning, the combination of concomitant estimation and structural constraints (like non-negativity) offers a promising path toward reliable, scalable, and robust causal discovery.