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

arXiv:2608.08103v1 Announce Type: new 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'(h)asymp h^nu, the feasibility-only time is T_0(arepsilon)=Theta(arepsilon^{-(2nu+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_0log(1/arepsilon)o0. 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.

Source: arXiv cs.LG | 2026-08-11