# Global Optimality in Bivariate Gradient-based DAG Learning

arXiv: https://arxiv.org/abs/2306.17378 · HTML: https://mlsanity.com/paper/2306.17378/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 57 references that are in the map.
- First posted on arXiv 30 Jun 2023.

## Builds on (most cited first, 30 of 30)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [Gradient-Based Neural DAG Learning](https://mlsanity.com/paper/1906.02226/) (2019)
- [Learning Sparse Nonparametric DAGs](https://mlsanity.com/paper/1909.13189/) (2019)
- [On the Role of Sparsity and DAG Constraints for Learning Linear DAGs](https://mlsanity.com/paper/2006.10201/) (2020)
- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/1906.04477/) (2019)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [High-dimensional learning of linear causal networks via inverse covariance estimation](https://mlsanity.com/paper/1311.3492/) (2013)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks](https://mlsanity.com/paper/2010.09133/) (2020)
- [Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs](https://mlsanity.com/paper/1702.07966/) (2017)
- [On Causal Discovery with Equal Variance Assumption](https://mlsanity.com/paper/1807.03419/) (2018)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [On the Convergence of Continuous Constrained Optimization for Structure Learning](https://mlsanity.com/paper/2011.11150/) (2020)
- [On Graduated Optimization for Stochastic Non-Convex Problems](https://mlsanity.com/paper/1503.03712/) (2015)
- [Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems](https://mlsanity.com/paper/1411.1134/) (2014)
- [Adding One Neuron Can Eliminate All Bad Local Minima](https://mlsanity.com/paper/1805.08671/) (2018)
- [Single Loop Gaussian Homotopy Method for Non-convex Optimization](https://mlsanity.com/paper/2203.05717/) (2022)
- [Bayesian Network Learning via Topological Order](https://mlsanity.com/paper/1701.05654/) (2017)
- [Bivariate Causal Discovery and its Applications to Gene Expression and Imaging Data Analysis](https://mlsanity.com/paper/1805.04164/) (2018)
- [Bivariate Causal Discovery for Categorical Data via Classification with Optimal Label Permutation](https://mlsanity.com/paper/2209.08579/) (2022)
- [Convergence Analysis of Homotopy-SGD for non-convex optimization](https://mlsanity.com/paper/2011.10298/) (2020)
- [A Greedy Homotopy Method for Regression with Nonconvex Constraints](https://mlsanity.com/paper/1410.7241/) (2014)

## Built on by (most cited first, 10 of 10)

- [CoLiDE: Concomitant Linear DAG Estimation](https://mlsanity.com/paper/2310.02895/) (2023)
- [Non-negative Weighted DAG Structure Learning](https://mlsanity.com/paper/2409.07880/) (2024)
- [psiDAG: Projected Stochastic Approximation Iteration for DAG Structure Learning](https://mlsanity.com/paper/2410.23862/) (2024)
- [Concomitant DAG Learning: On the Roles of Noise Adaptivity, Sparsity, and Non-negativity](https://mlsanity.com/paper/2605.23537/) (2026)
- [Interventional Causal Structure Discovery over Graphical Models with Convergence and Optimality Guarantees](https://mlsanity.com/paper/2408.04819/) (2024)
- [Revisiting Differentiable Structure Learning: Inconsistency of ℓ1 Penalty and Beyond](https://mlsanity.com/paper/2410.18396/) (2024)
- [Causal Order Discovery based on Monotonic SCMs](https://mlsanity.com/paper/2410.19870/) (2024)
- [Differentiable Structure Learning and Causal Discovery for General Binary Data](https://mlsanity.com/paper/2509.21658/) (2025)
- [Non-negative DAG Learning from Time-Series Data](https://mlsanity.com/paper/2512.07267/) (2025)
- [Structure Learning on Clustered Data](https://mlsanity.com/paper/2607.08238/) (2026)

## Abstract (arXiv)

Recently, a new class of non-convex optimization problems motivated by the statistical problem of learning an acyclic directed graphical model from data has attracted significant interest. While existing work uses standard first-order optimization schemes to solve this problem, proving the global optimality of such approaches has proven elusive. The difficulty lies in the fact that unlike other non-convex problems in the literature, this problem is not "benign", and possesses multiple spurious solutions that standard approaches can easily get trapped in. In this paper, we prove that a simple path-following optimization scheme globally converges to the global minimum of the population loss in the bivariate setting.