論文の概要: TriOpt: A Scalable Algorithm for Linear Causal Discovery

• arxiv url: http://arxiv.org/abs/2605.17465v1
• Date: Sun, 17 May 2026 14:07:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-19 17:57:48.104053
• Title: TriOpt: A Scalable Algorithm for Linear Causal Discovery
• Title（参考訳）: TriOpt: 線形因果発見のためのスケーラブルなアルゴリズム
• Authors: Rafat Ashraf Joy, Elena Zheleva,
• Abstract要約: 順序付け法と最適化法を密に統合した線形因果発見のための新しい定式化を導入する。 我々は,TriOptが高次元状態における最先端の線形因果探索法よりも高次精度を実現していることを示す。
• 参考スコア（独自算出の注目度）: 5.185131234265025
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning causal relations from observational data is challenging because the graph search space grows super-exponentially with the number of variables. Ordering-based methods reduce this space by first identifying the topological ordering, whereas continuous optimization methods explore most likely regions of the space by casting DAG learning as a differentiable objective with an acyclicity constraint. Despite their conceptual appeal, both paradigms face significant scalability limitations in high-dimensional settings, restricting their practical applicability. In this work, we introduce a new formulation for linear causal discovery that tightly integrates these two paradigms to achieve substantial gains in scalability without sacrificing accuracy. Our approach, TriOpt, decomposes the problem into two efficient stages. First, it recovers the topological ordering by exploiting the Sherman-Morrison rank-1 downdate together with the additive structure of linear kernels, enabling fast and scalable ordering estimation. Second, given this ordering, we reformulate structure learning as a convex continuous optimization problem that entirely avoids the need for enforcing costly acyclicity constraints. We theoretically show that, under the true ordering, TriOpt exactly recovers the underlying linear DAG. Empirically, across synthetic, semi-synthetic, and real-world datasets, TriOpt achieves orders-of-magnitude speedups over state-of-the-art linear causal discovery methods in high-dimensional regimes, while maintaining comparable or superior accuracy.
• Abstract（参考訳）: グラフ探索空間は変数数とともに指数関数的に増大するため,観測データから因果関係を学習することは困難である。 順序付けに基づく手法は、まず位相的順序付けを同定することによってこの空間を減少させる一方、連続最適化法は、DAG学習を非巡回性制約付き微分可能な目的としてキャストすることで、空間の最も可能性の高い領域を探索する。 概念上の魅力にも拘わらず、両方のパラダイムは高次元設定において大きなスケーラビリティの制限に直面し、実用性を制限する。 本研究では,これらの2つのパラダイムを密に統合し,精度を犠牲にすることなくスケーラビリティを大幅に向上させる線形因果発見の新しい定式化を提案する。 我々のアプローチであるTriOptは、問題を2つの効率的な段階に分解する。 まず、線形カーネルの付加構造とともにシャーマン・モリソンランク1のダウンデートを利用してトポロジ的順序付けを復元し、高速でスケーラブルな順序付け推定を可能にする。 第二に、この順序を考えると、構造学習を凸的連続最適化問題として再構成し、コストのかかる非循環的制約を強制する必要性を完全に回避する。 理論上は、真の順序付けの下で、TriOptは基礎となる線形DAGを正確に回復することを示す。 経験的に、合成、半合成、および実世界のデータセットを通して、TriOptは、高次元状態における最先端の線形因果探索法よりも精度の高いオーダー・オブ・マグニチュード・スピードアップを達成し、同等または優れた精度を維持している。

関連論文リスト

• GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs [7.079949618914198]
  ブランチ・アンド・バウンド(BnB)フレームワークは、パースペクティブ・リラクゼーションを使って最適性を証明できる。 これらの緩和を解く既存の手法は計算集約的であり、スケーラビリティを制限している。 我々は線形収束性と計算効率の両立した近位フレームワークを開発する。
  論文  参考訳（メタデータ） (2026-03-01T22:26:09Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  乱摂動の分布は, 摂動段差がゼロになる傾向にあるため, 推定子の分散を最小限に抑える。 以上の結果から, 一定の長さを維持するのではなく, 真の勾配に方向を合わせることが可能であることが示唆された。
  論文  参考訳（メタデータ） (2025-10-22T19:06:39Z)
• A Practical Solver for Scalar Data Topological Simplification [7.079737824450954]
  本稿では,トポロジカル単純化の最適化のための実践的アプローチを提案する。 フィラメントループを除去する標準的なトポロジカル手法よりも,本手法が優れていることを示す。 また,本手法は表面処理における遺伝子欠陥の修復にも有効であることを示す。
  論文  参考訳（メタデータ） (2024-07-17T08:25:32Z)
• Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models [2.0738462952016232]
  関数因果モデルに基づく手法は、ユニークなグラフを識別することができるが、次元性の呪いや強いパラメトリックな仮定を課すことに苦しむ。 本研究では,局所的な因果構造を利用した観測データにおけるグローバル因果発見のための新しいハイブリッド手法を提案する。 我々は, 合成データに対する実証的な検証を行い, 正確性および最悪の場合の時間複雑度を理論的に保証する。
  論文  参考訳（メタデータ） (2024-05-23T12:28:16Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。