# Support Selection Beyond Smooth DAG Exactness: Completion Geometry,Score Margins, and Selective Certificates

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 8 Aug 2026.

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

- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks](https://mlsanity.com/paper/2010.09133/) (2020)
- [DAGs with No Curl: An Efficient DAG Structure Learning Approach](https://mlsanity.com/paper/2106.07197/) (2021)
- [Structure Learning with Continuous Optimization: A Sober Look and Beyond](https://mlsanity.com/paper/2304.02146/) (2023)
- [Stable Differentiable Causal Discovery](https://mlsanity.com/paper/2311.10263/) (2023)
- [Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration](https://mlsanity.com/paper/1706.01081/) (2017)
- [Constraint-Free Structure Learning with Smooth Acyclic Orientations](https://mlsanity.com/paper/2309.08406/) (2023)
- [Markov Equivalence and Consistency in Differentiable Structure Learning](https://mlsanity.com/paper/2410.06163/) (2024)
- [Analytic DAG Constraints for Differentiable DAG Learning](https://mlsanity.com/paper/2503.19218/) (2025)
- [Exploiting Non-Negativity in DAG Structure Learning](https://mlsanity.com/paper/2605.19947/) (2026)
- [Learning Large DAGs by Combining Continuous Optimization and Feedback Arc Set Heuristics](https://mlsanity.com/paper/2107.00571/) (2021)
- [Testing Many Constraints in Possibly Irregular Models Using Incomplete U-Statistics](https://mlsanity.com/paper/2208.11756/) (2022)

## Abstract (arXiv)

Smooth acyclicity constraints answer whether a weighted support is a DAG, whereas structure learning asks which support change should be made. Existing analyses establish degeneracy for particular constraint formulas but do not isolate what follows from smooth exactness itself. At a DAG boundary, we show that minimal cycle completions generate a squarefree monomial ideal containing every restricted Taylor jet of an exact representation. If the smallest completion has q edges, the first possible response has order q for a vector residual and 2q for a nonnegative scalar. Exponentially many constant-scale cyclic manifolds exhibit the same lack of ranking away from the boundary for NOTEARS and DAGMA. We derive the exact selection time for an isolated cycle. When Psi'(h)asymp h^nu, the feasibility-only time is T0(varepsilon)=Theta(varepsilon-(2nu+1)); a score margin changes the leading dynamics at scale T0-1 for nu>0, while nu=0 has a logarithmic boundary layer requiring γ T0log(1/varepsilon)→0. Experiments verify this law, and a truth-free separation statistic predicts selection time on 320 official NOTEARS/DAGMA trajectories (Spearman -0.52 and -0.66, permutation p<10-4). For finite samples, a parent-set confidence family and forced-opposite queries certify skeleton and unshielded-collider labels shared by every population optimum of a frozen score. Across 320 runs, every regret bound covers an independent oracle-score audit. None of 3,042 certified skeleton or 2,396 collider labels disagrees with the oracle-score optimum, although 4.4% and 5.5%, respectively, disagree with the generating graph. These results separate DAG feasibility, score-based support selection, and causal identification.