Identifiability of the minimum-trace directed acyclic graph and hill climbing algorithms without strict local optima under weakly increasing error variances
By: Hyunwoong Chang, Jaehoan Kim
Potential Business Impact:
Finds the real cause-and-effect order.
We prove that the true underlying directed acyclic graph (DAG) in Gaussian linear structural equation models is identifiable as the minimum-trace DAG when the error variances are weakly increasing with respect to the true causal ordering. This result bridges two existing frameworks as it extends the identifiable cases within the minimum-trace DAG method and provides a principled interpretation of the algorithmic ordering search approach, revealing that its objective is actually to minimize the total residual sum of squares. On the computational side, we prove that the hill climbing algorithm with a random-to-random (R2R) neighborhood does not admit any strict local optima. Under standard settings, we confirm the result through extensive simulations, observing only a few weak local optima. Interestingly, algorithms using other neighborhoods of equal size exhibit suboptimal behavior, having strict local optima and a substantial number of weak local optima.
Similar Papers
Consistent causal discovery with equal error variances: a least-squares perspective
Statistics Theory
Finds the real cause-and-effect connections.
Consistent DAG selection for Bayesian causal discovery under general error distributions
Statistics Theory
Finds cause-and-effect relationships in data.
Non-negative DAG Learning from Time-Series Data
Signal Processing
Finds hidden causes in changing data.