論文の概要: Theoretical Guarantees for Causal Discovery on Large Random Graphs

• arxiv url: http://arxiv.org/abs/2511.02536v1
• Date: Tue, 04 Nov 2025 12:43:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 18:47:05.992898
• Title: Theoretical Guarantees for Causal Discovery on Large Random Graphs
• Title（参考訳）: 大規模ランダムグラフの因果発見のための理論的保証
• Authors: Mathieu Chevalley, Arash Mehrjou, Patrick Schwab,
• Abstract要約: 偽陰性率(FNR)の理論的保証について検討する。 我々は、FNRが平均値$O(fraclog dsqrt d)$で集中していることを示し、次元が増加するにつれて、予想される誤差を超える大きな偏差が指数関数的にありそうにないことを示唆する。 シミュレーション結果はこれらの理論予測を裏付けるものであり、FNRは次元が大きくなるにつれて実際に集中し、しばしば消滅することを示している。
• 参考スコア（独自算出の注目度）: 10.555608566624112
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate theoretical guarantees for the false-negative rate (FNR) -- the fraction of true causal edges whose orientation is not recovered, under single-variable random interventions and an $\epsilon$-interventional faithfulness assumption that accommodates latent confounding. For sparse Erd\H{o}s--R\'enyi directed acyclic graphs, where the edge probability scales as $p_e = \Theta(1/d)$, we show that the FNR concentrates around its mean at rate $O(\frac{\log d}{\sqrt d})$, implying that large deviations above the expected error become exponentially unlikely as dimensionality increases. This concentration ensures that derived upper bounds hold with high probability in large-scale settings. Extending the analysis to generalized Barab\'asi--Albert graphs reveals an even stronger phenomenon: when the degree exponent satisfies $\gamma > 3$, the deviation width scales as $O(d^{\beta - \frac{1}{2}})$ with $\beta = 1/(\gamma - 1) < \frac{1}{2}$, and hence vanishes in the limit. This demonstrates that realistic scale-free topologies intrinsically regularize causal discovery, reducing variability in orientation error. These finite-dimension results provide the first dimension-adaptive, faithfulness-robust guarantees for causal structure recovery, and challenge the intuition that high dimensionality and network heterogeneity necessarily hinder accurate discovery. Our simulation results corroborate these theoretical predictions, showing that the FNR indeed concentrates and often vanishes in practice as dimensionality grows.
• Abstract（参考訳）: 我々は, 単一変数のランダムな介入の下で, 向きが回復しない真の因果エッジの分数, 潜伏共起を許容する$\epsilon$-interventional faithfulnessの仮定の理論的保証について検討する。 スパース Erd\H{o}s--R\enyi の非巡回グラフでは、辺確率は $p_e = \Theta(1/d)$ とスケールし、FNR はその平均値が $O(\frac{\log d}{\sqrt d})$ で集中していることを示す。 この濃度は、大規模設定において、導出上界が高い確率で保持されることを保証する。 解析を一般化されたBarab\'asi-Albertグラフに拡張すると、さらに強い現象が示される: 次数指数が$\gamma > 3$ を満たすとき、偏差幅は$O(d^{\beta - \frac{1}{2}})$ with $\beta = 1/(\gamma - 1) < \frac{1}{2}$ となる。 このことは、現実的なスケールフリートポロジーが本質的に因果発見を規則化し、向きの誤差のばらつきを減らすことを示している。 これらの有限次元の結果は、因果構造回復のための最初の次元適応的で忠実でロバストな保証を与え、高次元性とネットワークの不均一性が必ずしも正確な発見を妨げているという直感に挑戦する。 シミュレーション結果はこれらの理論予測を裏付けるものであり、FNRは次元が大きくなるにつれて実際に集中し、しばしば消滅することを示している。

関連論文リスト

• Understanding Robust Machine Learning for Nonparametric Regression with Heavy-Tailed Noise [10.844819221753042]
  我々は、Tikhonov-regularized risk minimizationのクローズアップ例として、Huberレグレッションを使用している。 i)弱モーメント仮定下での標準濃度ツールの分解と,(ii)非有界仮説空間によってもたらされる解析的困難に対処する。 我々の研究は、原則化されたルールを提供し、ハマーを超えて他の堅牢な損失に拡張し、頑健な学習を分析するための基本的なレンズとして、過剰なリスクではなく予測エラーを強調します。
  論文  参考訳（メタデータ） (2025-10-10T21:57:18Z)
• A Unified Analysis for Finite Weight Averaging [50.75116992029417]
  Gradient Descent(SGD)の平均イテレーションは、SWA(Weight Averaging)、EMA(Exponential moving Average)、LAWA(Latest Weight Averaging)といったディープラーニングモデルのトレーニングにおいて、経験的な成功を収めている。 本稿では、LAWAを有限重み平均化(FWA)として一般化し、最適化と一般化の観点からSGDと比較して、それらの利点を説明する。
  論文  参考訳（メタデータ） (2024-11-20T10:08:22Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Theory of free fermions under random projective measurements [43.04146484262759]
  本研究では,一次元自由フェルミオンを局所的占有数のランダム射影的測定対象とする解析的手法を開発した。 問題の有効場理論として非線形シグマモデル(NLSM)を導出する。
  論文  参考訳（メタデータ） (2023-04-06T15:19:33Z)
• A High-dimensional Convergence Theorem for U-statistics with Applications to Kernel-based Testing [3.469038201881982]
  次数2のU-統計量に対して収束定理を証明し、データ次元$d$はサンプルサイズ$n$でスケールすることができる。 我々はこの理論を、高次元性能の研究が困難である2つのカーネルベースの分散テスト MMD と KSD に適用した。
  論文  参考訳（メタデータ） (2023-02-11T12:49:46Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Stability and Risk Bounds of Iterative Hard Thresholding [41.082982732100696]
  アルゴリズム安定性の概念の下でIHTの新しいスパース一般化理論を導入する。 スパースレベル$k$のIHTは、スパース過剰リスクにおける収束率を$mathcaltilde O(n-1/2sqrtlog(n)log(p))$で楽しむことを示す。 理論的予測を確認するための予備的な数値的証拠が提供される。
  論文  参考訳（メタデータ） (2022-03-17T16:12:56Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。 SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。 その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
  論文  参考訳（メタデータ） (2021-02-20T13:45:11Z)

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

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