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

Abstract

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 }^{\prime }(h)\asymp h^{\nu }$, the feasibility-only time is $T_0(\epsilon )=\Theta ({\epsilon }^{-(2\nu +1)})$; a score margin changes the leading dynamics at scale $T_0^{-1}$ for $\nu >0$, while $\nu =0$ has a logarithmic boundary layer requiring $\gamma T_0\log (1/\epsilon )\to 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.

49 pages, 17 figures, 20 tables