Smooth, Sparse, and Stable: Finite-Time Exact Skeleton Recovery via Smoothed Proximal Gradients

• URL: http://arxiv.org/abs/2601.18189v1
• Date: Mon, 26 Jan 2026 06:16:47 GMT
• Title: Smooth, Sparse, and Stable: Finite-Time Exact Skeleton Recovery via Smoothed Proximal Gradients
• Abstract summary: We bridge the gap between continuous optimization and discrete graph structures by proposing the Hybrid-Order Acyclicity Constraint (AHOC) and optimizing it via the Smoothed Proximal Gradient (SPG-AHOC)<n>We prove that under standard identifiability assumptions, SPG-AHOC recovers the exact DAG support (structure) in finite iterations, even when optimizing a smoothed approximation.<n>This result eliminates structural ambiguity, as our algorithm returns graphs with exact zero entries without truncation.
• Score: 2.7920588009522755
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Optimization-Free Topological Sort for Causal Discovery via the Schur Complement of Score Jacobians [7.046544692710195]
  Continuous causal discovery typically represents learning with structural optimization via non-dimensional structural error penalties.<n>We introduce WeSSTS, which allows causal structural analysis graphs up to d-sample estimation of the global score.
  arXiv  Detail & Related papers  (2026-04-28T07:03:04Z)
• From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity [12.097833603814252]
  We show that Byzantine-robust distributed optimization can be cast as a general optimization with inexact gradient oracles.<n>We propose two optimization schemes to speed up the convergence.
  arXiv  Detail & Related papers  (2026-02-03T09:56:23Z)
• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences [51.56484100374058]
  We study stopping rules for gradient descent (SGD) for convex optimization.<n>We develop an anytime-valid, data-dependent upper confidence sequence for the weighted average suboptimality of projected SGD.<n>These are the first rigorous, time-uniform performance guarantees and finitetime $varepsilon$-optimality certificates.
  arXiv  Detail & Related papers  (2025-12-15T09:26:45Z)
• An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition [0.0]
  In this paper, we aim to investigate the sparse low-rank characteristics rectified on non-negative matrices.<n>We propose a novel regularization term incorporating useful structures in clustering and compression tasks.<n>We derive corresponding closed-form solutions while maintaining the $L$-smooth property always holds for any $Lge 1$.
  arXiv  Detail & Related papers  (2025-03-04T08:20:34Z)
• Non-negative Weighted DAG Structure Learning [12.139158398361868]
  We address the problem of learning the true DAGs from nodal observations. We propose a DAG recovery algorithm based on the method that is guaranteed to return ar.
  arXiv  Detail & Related papers  (2024-09-12T09:41:29Z)
• CoLiDE: Concomitant Linear DAG Estimation [12.415463205960156]
  We deal with the problem of learning acyclic graph structure from observational data to a linear equation. We propose a new convex score function for sparsity-aware learning DAGs.
  arXiv  Detail & Related papers  (2023-10-04T15:32:27Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• On the Convergence of mSGD and AdaGrad for Stochastic Optimization [0.696125353550498]
  convex descent (SGD) has been intensively developed and extensively applied in machine learning in the past decade. Some modified SGD-type algorithms, which outperform the SGD in many competitions and applications in terms of convergence rate and accuracy, such as momentum-based SGD (mSGD) and adaptive gradient optimization (AdaGrad) We focus on convergence analysis of mSGD and AdaGrad for any smooth (possibly non-possibly non-possibly non-possibly) loss functions in machine learning.
  arXiv  Detail & Related papers  (2022-01-26T22:02:21Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Stochastic Reweighted Gradient Descent [4.355567556995855]
  We propose an importance-sampling-based algorithm we call SRG (stochastic reweighted gradient) We pay particular attention to the time and memory overhead of our proposed method. We present empirical results to support our findings.
  arXiv  Detail & Related papers  (2021-03-23T04:09:43Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  We provide sharp upper and lower bounds for several forms of gradient descent (SGD) on arbitrary Lipschitz nonsmooth convex losses. Our bounds allow us to derive a new algorithm for differentially private nonsmooth convex optimization with optimal excess population risk.
  arXiv  Detail & Related papers  (2020-06-12T02:45:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.