論文の概要: Mapping and Advancing the Scalability-Accuracy Frontier of Nonlinear Causal Discovery

• arxiv url: http://arxiv.org/abs/2610.03258v1
• Date: Fri, 02 Oct 2026 13:03:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.378963
• Title: Mapping and Advancing the Scalability-Accuracy Frontier of Nonlinear Causal Discovery
• Title（参考訳）: 非線形因果発見のスケーラビリティ-精度フロンティアのマッピングと改善
• Abstract要約: 非線形因果発見に対処するために、いくつかのアルゴリズムファミリーが提案されている。 我々は,4つの主要なアプローチ – 微分可能な構造学習,償却された構造学習,スコアマッチング,探索 – を経験的に比較した。 このボトルネックに触発されたSPADEは,スプラインベースのスコア評価方式で,十分な統計情報を一度にコンパイルし,検索を通して再利用する。
• 参考スコア（独自算出の注目度）: 32.86812546916038
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Scalable nonlinear causal discovery requires methods that combine flexible mechanism estimators with efficient search over large graph spaces. Several algorithmic families have been proposed to address this challenge, yet their accuracy-runtime trade-offs remain poorly understood. We empirically compare the four major approaches: differentiable structure learning, amortized structure learning, score-matching, and combinatorial search. Our results reveal complementary bottlenecks: differentiable and amortized methods scale well but exhibit an accuracy gap, score-matching methods can be accurate in low dimensions but degrade quickly for increasing feature sizes, and combinatorial methods remain accurate but are slowed by repeated and redundant local scoring. Motivated by this bottleneck, we develop SPADE, a spline-based score-evaluation scheme that compiles sufficient statistics once and reuses them throughout combinatorial search. Under bounded indegree, its Gaussian variant reduces algorithmic complexity from O(nd^3) to O(nd^2+d^3). Empirically, SPADE shifts the observed scalability-accuracy frontier by orders of magnitude: it solves 100-variable problems with 160K samples in seconds and 1600-variable problems with 2.5K samples in minutes, while retaining high structural accuracy across synthetic and real-world benchmarks. These results reveal a substantial shift in the practical scale of combinatorial search and highlight the importance of evaluating scalable causal-discovery methods along the full accuracy-runtime frontier.
• Abstract（参考訳）: スケーラブルな非線形因果探索には、フレキシブルな機構推定器と大きなグラフ空間上の効率的な探索を組み合わせた手法が必要である。 この課題に対処するためにいくつかのアルゴリズムのファミリーが提案されているが、その精度と実行時のトレードオフはよく分かっていない。 我々は,4つの主要なアプローチ – 微分可能な構造学習,償却された構造学習,スコアマッチング,組合せ探索 – を経験的に比較した。 その結果, 相補的ボトルネックが明らかとなった: 相補的手法のスケールは良好だが, 精度の差がみられ, スコアマッチング法は低次元では正確だが, 特徴量の増加のために急速に劣化し, 組合せ法は精度が保たれるが, 繰り返し, 冗長な局所スコアリングにより遅くなる。 このボトルネックに触発されたSPADEは,スプラインに基づくスコア評価方式で,十分な統計情報を一度にコンパイルし,組合せ探索を通じて再利用する。 有界次数の下では、ガウス変法はアルゴリズムの複雑さを O(nd^3) から O(nd^2+d^3) に還元する。 数秒で160Kのサンプルで100変数の問題を、分で1600変数のサンプルで2.5Kのサンプルで1600変数の問題を、合成および実世界のベンチマークで高い構造精度を維持しながら解決する。 これらの結果は,組合せ探索の実践規模が大きく変化していることを示し,完全精度-実行時フロンティアに沿って,スケーラブルな因果発見手法を評価することの重要性を強調した。

関連論文リスト

• The K-SCAN Clustering Algorithm [0.0]
  本稿では,このトレードオフを最適化する新しいハイブリッドアルゴリズムK-SCANを提案する。 この方法は予備ベクトル量子化(Stochastic Mini-Batch K-Means)を統合し、減量されたマイクロクラスターを抽出する。 階層的BIRCHアルゴリズムよりも3倍以上のスピードアップを実現し、木構造体のコスト管理を回避する。
  論文  参考訳（メタデータ） (2026-07-27T15:16:19Z)
• Robust low-rank estimation with multiple binary responses using pairwise AUC loss [0.0]
  複数のバイナリ応答は、多くの現代のデータ分析問題に現れる。 低ランクモデルはタスク間の遅延依存をエンコードする自然な方法を提供する。 既存のバイナリデータの方法は概ね可能性ベースであり、ポイントワイズ分類に重点を置いている。
  論文  参考訳（メタデータ） (2026-01-13T15:00:10Z)
• Efficient Differentiable Causal Discovery via Reliable Super-Structure Learning [51.20606796019663]
  本稿では,新たな因果発見パイプラインであるALVGLを提案する。 ALVGLはスパース分解とローランク分解を用いてデータの精度行列を学習する。 ALVGLは最先端の精度を達成するだけでなく、最適化効率を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2026-01-09T02:18:59Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Reinforcement Learning with Function Approximation: From Linear to Nonlinear [4.314956204483073]
  本稿では,線形あるいは非線形近似設定における強化学習アルゴリズムの誤差解析に関する最近の結果についてレビューする。 近似誤差に関する諸特性について考察し、遷移確率と報酬関数に関する具体的条件について述べる。
  論文  参考訳（メタデータ） (2023-02-20T00:31:18Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。 新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。 反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
  論文  参考訳（メタデータ） (2022-12-06T12:42:11Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  本稿では、分散正規化損失最小化問題に対する2倍加速勾配降下法(ADSGD)を提案する。 まず、ADSGDが線形収束率を達成でき、全体的な計算複雑性を低減できることを示す。
  論文  参考訳（メタデータ） (2022-08-11T22:27:22Z)
• Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions [17.097192646470372]
  線形ガウス設定における正確なスコアベース手法のスケーラビリティを向上させるためのいくつかの戦略を導入する。 我々は,忠実度よりも厳密な仮定を必要とする逆共分散行列の支持に基づく超構造推定法を開発した。 また,各変数とその近傍が生成する局所クラスタを,超構造内の2つのホップ内で正確に探索する局所探索戦略を提案する。
  論文  参考訳（メタデータ） (2022-01-14T20:52:30Z)
• Hybrid Bayesian network discovery with latent variables by scoring multiple interventions [5.994412766684843]
  離散データから構造学習を行うためのハイブリッドmFGS-BSアルゴリズムを提案する。 このアルゴリズムは潜伏変数の存在下で因果不整合を仮定し、部分アンセストラルグラフ(PAG)を生成する。 実験の結果,mFGS-BSは最先端技術と比較して構造学習精度が向上し,計算効率が向上した。
  論文  参考訳（メタデータ） (2021-12-20T14:54:41Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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