Smooth, Sparse, and Stable: Finite-Time Exact Skeleton Recovery via Smoothed Proximal Gradients
Rui Wu, Yongjun Li · 2026
Read Smooth, Sparse, and Stable: Finite-Time Exact Skeleton Recovery via Smoothed Proximal Gradients by Rui Wu, Yongjun Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18189.txt.
Introduction
Rui Wu and Yongjun Li give causal discovery a method that lands exactly on a graph in finite time. Their 2026 preprint builds on continuous optimization, the approach made famous by NOTEARS. Such methods usually promise only that they approach a fixed point as steps go on forever. In practice they return dense weighted matrices. Users then cut weak edges by a threshold picked by hand, which makes the found graph shaky.
The authors use smoothed proximal gradients to fix that. Their method recovers an exact skeleton, and it does so in finite time. The result is smooth, sparse, and stable, as their title says. Cleaner causal graphs matter wherever cause, not just correlation, drives a choice.
Catalog record
| CREATOR | Rui Wu, Yongjun Li |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-18189
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Smooth, Sparse, and Stable: Finite-Time Exact Skeleton Recovery via Smoothed Proximal Gradients Rui Wu, Yongjun Li Abstract Continuous optimization has significantly advanced causal discovery, yet existing methods (e.g., NOTEARS) generally guarantee only asymptotic convergence to a stationary point. This often yields dense weighted matrices that require arbitrary post-hoc thresholding to recover a DAG. This gap between continuous optimization and discrete graph structures remains a fundamental challenge. In this paper, we bridge this gap by proposing the Hybrid-Order Acyclicity Constraint (AHOC) and optimizing it via the Smoothed Proximal Gradient (SPG-AHOC) . Leveraging the Manifold Identification Property of proximal algorithms, we provide a rigorous theoretical guarantee: the Finite-Time Oracle Property . We prove that under standard identifiability assumptions, SPG-AHOC recovers the exact DAG support (structure) in finite iterations, even when optimizing a smoothed approximation. This result eliminates structural ambiguity, as our algorithm returns graphs with exact zero entries without heuristic truncation. Empirically, SPG-AHOC achieves state-of-the-art accuracy and strongly corroborates the finite-time identification theory. Keywords Causal Discovery \cdot Continuous Optimization \cdot Proximal Gradient \cdot Acyclicity Constraint 1 Introduction The transition from correlation to causation relies on dissecting the precise structure of interactions. However, a chasm exists between the discrete nature of graphs and the continuous optimization tools used to find them. Historically, this problem was addressed using combinatorial search algorithms ( 4 ) , which scale poorly with the number of variables d . The field witnessed a paradigm shift with the introduction of NOTEARS ( 10 ) , which reformulated the discrete Directed Acyclic Graph (DAG) constraint into a continuous equality constraint, enabling the use of efficient continuous optimization techniques. The Gap: Asymptotic Convergence vs. Exact Structure. Despite the computational advances, a critical disconnect remains. Existing methods typically guarantee only asymptotic convergence to a stationary point. In practice, this results in dense weighted adjacency matrices where "zero" edges are represented by small non-zero values (e.g., 10^{-4} ). This necessitates arbitrary post-hoc thresholding to recover a valid DAG. In scientific discovery, this introduces Scientific Ambiguity : does a small weight represent a weak causal link or numerical noise? Furthermore, standard constraints suffer from Structural Constraint Instability (SCI) , facing a trade-off between vanishing gradients (hindering sparsity) and exploding gradients (causing numerical divergence). Our Solution: Topological Locking. To bridge this gap, we propose a theoretically grounded framework that ensures Finite-Time Exact Recovery . We introduce the Hybrid-Order Acyclicity Constraint (AHOC) , which satisfies a complete set of stability axioms. Crucially, we optimize this constraint using the Smoothed Proximal Gradient (SPG-AHOC) . We identify a mechanism we term Topological Locking (visualized in Figure 2 ): while standard gradient descent asymptotically approaches zero, the proximal operator explicitly "snaps" the optimization trajectory onto the sparse manifold in finite steps once it enters a Geometric Stability Zone . This allows our method to return graphs with exact zero entries , eliminating the need for heuristic truncation. Contributions. Our main contributions are threefold: • Axiomatic Framework & Impossibility Theorem: We identify the root causes of instability in existing methods and prove that standard smooth constraints cannot simultaneously satisfy gradient non-vanishing and boundedness axioms. We propose the AHOC family to resolve this. • Finite-Time Oracle Property: We provide a rigorous proof that SPG-AHOC achieves exact support recovery in finite iterations. We show that the "Topological Locking" effect of the proximal operator makes the support recovery robust to the smoothing bias required for optimization. • SOTA Performance & Robustness: Empirically, SPG-AHOC achieves state-of-the-art accuracy on synthetic benchmarks and real-world data (Sachs), while demonstrating superior computational efficiency in low-to-mid dimensions compared to unconstrained baselines. 2 Theoretical Analysis of Acyclicity Constraints In this section, we analyze the numerical properties of differentiable acyclicity constraints and propose our solution. 2.1 Our Method: An Axiomatic Diagnosis We propose three fundamental axioms for stable acyclicity constraints h(\mathbf{W}) : Axiom 2.1 (Correctness) . h(\mathbf{W})=0\iff\mathcal{G}(\mathbf{W})\text{ is a DAG} . Consequence of Violation: Converges to incorrect structures. Axiom 2.2 ( L_{1} -Synergy) . \liminf_{\delta\to 0^{+}}\left\lVert\nabla_{\mathbf{W}}h(\delta\cdot\mathbf{U})\right\rVert_{F}>0 . Consequence of Violation (Type I SCI): L_{1} gradient dominates, hindering sparse DAG discovery. Axiom 2.3 (Numerical Boundedness) . \sup_{\mathbf{W}}|h(\mathbf{W})|<\infty and \sup_{\mathbf{W}}\left\lVert\nabla_{\mathbf{W}}h(\mathbf{W})\right\rVert_{F}<\infty . Consequence of Violation (Type II SCI): Exploding gradients cause numerical divergence (‘NaN‘/‘Inf‘). This can be fatal unless the optimizer employs a "safety net". 2.2 Core Finding 1: The \mathcal{H} Family and its Incompatibility We reveal a fundamental Impossibility Theorem for the standard family of constraints. Definition 2.4 (Standard Hadamard Constraint Class \mathcal{H} ) . Let \mathcal{H} be the family of spectral constraints where the dependency on \mathbf{W} acts exclusively through the entry-wise magnitude matrix \mathbf{A}=\mathbf{W}\circ\mathbf{W} (or \mathbf{A}=\left\lvert\mathbf{W}\right\rvert ). Specifically, h(\mathbf{W})=F(\mathbf{A}) where F is a C^{1} smooth function on the cone of non-negative matrices. Theorem 2.5 (Refined Incompatibility Theorem) . For any constraint h\in\mathcal{H} satisfying h(\mathbf{0})=0 , if the core function F is smooth at the origin, then h(\mathbf{W}) cannot simultaneously satisfy Axiom 2.2 ( L_{1} -Synergy) and Axiom 2.3 (Numerical Boundedness). Implication: Standard constraints face an unavoidable trade-off. Quadratic dependencies (required for smoothness at origin) inherently conflict with the linear sensitivity required by L_{1} regularization. Figure 1: Visualizing Structural Constraint Instability (SCI). Left (Red/Green): Standard constraints suffer from either vanishing gradients at the origin (Type I) or exploding gradients near the boundary (Type II). Right (Blue): Our AHOC formulation maintains a stable, non-vanishing gradient signal near zero due to the smoothed L_{1} -Synergy (Axiom 2), while preventing explosion via normalization (Axiom 3). 2.3 An Intermediate Step: AAC Solves Type II SCI Introducing Adaptive Scale Normalization (ASN), \phi_{\text{ASN}}(\mathbf{W};\epsilon)=\frac{\mathbf{A}}{\left\lVert\mathbf{A}\right\rVert_{F}+\epsilon} , yields the AAC constraint: h_{\text{AAC}}(\mathbf{W};\epsilon)\coloneqq\tr\left(\expm\left(\phi_{\text{ASN}}(\mathbf{W};\epsilon)\right)\right)-d Theorem 2.6 (Axiomatic Analysis of AAC) . AAC satisfies Axioms 2.1 and 2.3 , but fails Axiom 2.2 . Implication: AAC fixes Type II SCI (satisfies A3) but not Type I SCI (fails A2), as its gradient is \mathcal{O}(\left\lVert\mathbf{W}\right\rVert_{F}/\epsilon) and still vanishes. 2.4 The Theoretical Solution: Hybrid-Order Constraints (AHOC/S-AHOC) To satisfy Axiom 2 ( L_{1} -Synergy), which requires a non-vanishing gradient signal as \mathbf{W}\to 0 , we introduce a first-order term via the Hybrid-Order Core (HOC): \mathbf{M}(\mathbf{W};\alpha)\coloneqq\alpha(\mathbf{W}\circ\mathbf{W})+(1-\alpha)\left\lvert\mathbf{W}\right\rvert,\quad\alpha\in[0,1) Applying normalization yields two variants: Definition 2.7 (AHOC and S-AHOC Constraints) . Let h_{\exp}(\mathbf{M})=\tr(\expm(\mathbf{M}))-d . • AHOC (ASN Core): h_{\text{AHOC}}(\mathbf{W};\alpha,\epsilon)\coloneqq h_{\exp}\left(\frac{\mathbf{M}(\mathbf{W};\alpha)}{\left\lVert\mathbf{M}(\mathbf{W};\alpha)\right\rVert_{F}+\epsilon}\right) • S-AHOC (S-ASN Core): h_{\text{S-AHOC}}(\mathbf{W};\alpha)\coloneqq\tr\left(\expm\left(\frac{\mathbf{M}(\mathbf{W};\alpha)}{\left\lVert\mathbf{M}(\mathbf{W};\alpha)\right\rVert_{F}+1}\right)\right)-d Theorem 2.8 (Axiomatic Analysis of AHOC/S-AHOC) . Both h_{\text{AHOC}} and h_{\text{S-AHOC}} satisfy all three axioms: Correctness (A1), L_{1} -Synergy (A2), and Numerical Boundedness (A3). Implication: The AHOC/S-AHOC family is the first theoretically complete solution, resolving both SCI types. 2.5 The Smoothness Barrier: Theory vs. Optimization While the S-AHOC constraint theoretically satisfies all three stability axioms, it represents a Platonic ideal rather than a directly optimizable function. Specifically, because the core \mathbf{M}(\mathbf{W}) involves \left\lvert\mathbf{W}\right\rvert , the constraint h_{\text{S-AHOC}} is non-differentiable at any point where \mathbf{W}_{ij}=0 . This violates the standard assumption of Proximal Gradient methods, which require the smooth part of the objective to have a Lipschitz-continuous gradient ( 1 ) . Directly applying subgradient methods would forfeit the convergence rates we desire. Therefore, SPG-AHOC (Section 2.6 ) serves as the necessary algorithmic bridge: it optimizes a smoothed approximation to recover the properties of the ideal S-AHOC via the topological locking mechanism. Remark 2.9 (Theoretical Barrier for Proximal-LS) . The convergence guarantees of Proximal-LS strictly require that the smooth component of the objective function, let’s call it f(\mathbf{W}) (which includes h_{\text{AHOC}} ), has a Lipschitz continuous gradient