The exact selection time for an isolated cycle of NOTEARS and DAGMA is derived, and a truth-free separation statistic predicts selection time on 320 official NOTEARS/DAGMA trajectories.
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(\varepsilon)=\Theta(\varepsilon^{-(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/\varepsilon)\to0$. 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.
Best-of-$N$ reranking draws independent candidates from a reference policy and selects the response maximal under a fixed, sample-independent strict total order on outcomes. The selected law may differ substantially from the reference in Kullback–Leibler divergence. Prior work introduced a bounded statistic depending only on the accepted response's reference mass and conjectured that its expectation upper-bounds this divergence. This letter proves the conjecture for every finite ordered distribution. The proof applies to the full positive cumulative-distribution-function power family, not only integer sample counts. It combines a strictly monotone binary gauge, a top-atom chain-rule recursion, and induction, and yields an exact nonnegative slack decomposition and a quantitative tightness bound. A beta-quantile representation identifies the universal divergence cap. We also treat reference-preserving reward ties, provide deterministic high-precision illustrations, derive clipped fixed-sample confidence bounds, and specify stable evaluation and exact probability-logging requirements.
Yutong Zhang, Yaoran Yang· IEEE Signal Processing Lette...· 0 citations
We study exact single-source shortest paths when the output is only the materialized labeled distance vector ($\mathrm{DIST}$), rather than a distance order. In the full deterministic comparison-addition model, the minimum worst-case number of additions on every fixed directed topology is exactly the maximum number $\rho_{\mathrm{fwd}}$ of forward nonsource endpoint classes over rooted vertex orders; the lower bound permits adaptive control, literals, and arbitrary mixed sums. This arithmetic law aligns with the comparison optimum on DAGs, where the full resource region is an exact rectangle. Cycles destroy that alignment: a two-spoke shared-hub graph has coordinatewise optima $(4,2)$ but requires five comparisons at the two-addition budget. Its $k$-spoke extension forces $k\log_2 k+O(k)$ comparisons at the addition optimum and has an entropy-tight deterministic tradeoff $C_{k+r}^*(H_k)=\Theta(k+\Lambda_{k,r})$, where $\Lambda_{k,r}=\log_2(k!/[r!(r+1)^{k-r}])$, with leading constant one when $\Lambda_{k,r}/k\to\infty$. Because the two coordinatewise minima need not belong to one program, these conflicts lead to the same-program benchmark $\operatorname{OPT}_{\mathrm{DIST}}=\inf_A\sup_w(C_A(w)+P_A(w))$. An exact transcript-cone game yields one uniform interpreter whose charged addition-comparison cost equals $\operatorname{OPT}_{\mathrm{DIST}}$ on every topology; its optimal actions are synthesizable in polynomial space but may require exponential time. Finally, an active-core reduction and the current deterministic directed-SSSP bound give an efficient uniform $O\!\bigl(\operatorname{OPT}_{\mathrm{DIST}}\sqrt{\log(2+\operatorname{OPT}_{\mathrm{DIST}})\log\log(4+\operatorname{OPT}_{\mathrm{DIST}})}\bigr)$ charged-operation bound. Thus optimal numerical policies exist uniformly, while efficient constant-competitive navigation remains open.
It is proved that, as long as $p=o(\log n /n)$, for any $\varepsilon>0$, one can construct a confidence set of vertices of size $K(\varepsilon)$ that depends only on $\varepsilon$ and not on $n$, such that it contains the root with probability at least $1-\varepsilon$.
Luc Devroye, Gábor Lugosi, Neeladri Maitra· 1 citation· ⚡1
A known necessary condition for Fisher consistency of the structured support vector machine requires the task loss to be a metric for which every output triple has a common geodesic point. We show that this condition is not sufficient for the canonical coordinate-wise argmax decoder. A four-output unit star admits an exactly optimal score vector whose maximizers are all strictly non-Bayes, and four outputs are minimal among metrics satisfying the condition. We then completely classify positively weighted tree metrics whose vertex set is the output space: argmax consistency holds if and only if the tree is a path. The failure on branching trees is confined to boundary distributions; every tree retains the argmax property at every full-support distribution. Among metrics satisfying the common-geodesic condition, five outputs are necessary and sufficient for a full-support counterexample; $K_{2,3}$ is the smallest member of an infinite $K_{m,n}$ family. We additionally give a full-support counterexample for the three-dimensional Hamming cube. All optimality claims have exact primal-dual certificates. The counterexamples expose a concrete decoder gap: in this polyhedral setting, an embedding can guarantee the existence of a calibrated link without validating a prescribed argmax link on every surrogate-risk minimizer.
We analyze exact-metric, Metropolis-adjusted Dikin walks by keeping the proposal determinant and reverse quadratic form together. Their leading uncentered terms cancel in the complete logarithmic acceptance ratio, leaving centered fluctuations that can be controlled with second-order tools. For a polytope given by $n$ inequalities and a convex $L$-Lipschitz potential, this yields warm-start mixing in $\widetilde O((d^{2}+dL^{2}R^{2})\log(w/\delta))$ steps for the regularized Lee--Sidford walk. For a spectrahedron with $n\times n$ blocks, the log-det walk mixes in $\widetilde O((\psi^\star nd+dL^{2}R^{2})\log(w/\delta))$ steps, where $\psi^\star$ measures matrix leverage. The two analyses share an acceptance-to-mixing reduction. A proposal-comparison argument transfers the polytope bound to an appropriately padded $O(1/d)$-accurate metric computed from high-precision Lewis weights. For spectrahedra, given $\widehat\psi\ge\psi^\star$, a direct-or-two-seed TensorSRHT construction gives an exact-arithmetic implementation with $\psi^\star$ replaced by $\widehat\psi$ in the mixing bound.
A specific sparse post-processing pipeline for Random Indexing on kinship analogies in a small fairytales corpus is studied; the results do not establish a generally effective embedding method.
S. Loganathan, Gokul Anand, A. B. Bo et al.· 0 citations
A weeklong summer workshop brought higher education faculty to campus to explore how AI and machine learning materials can be adapted for their classrooms.
