論文の概要: The Statistical Cost of Causal Discovery with Feedback
- arxiv url: http://arxiv.org/abs/2609.34050v1
- Date: Mon, 28 Sep 2026 00:19:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-04 07:26:19.209136
- Title: The Statistical Cost of Causal Discovery with Feedback
- Title（参考訳）: フィードバックによる因果発見の統計的コスト
- Abstract要約: 観測データから正確な凝縮回収について検討した。
変数$p$、最大 SCC サイズ $s_max$、最大外用値 $d_B$ の場合、任意の推定器は$s_maxlog(ep/s_max)+d_Blog(ep/d_B)$サンプルを必要とする。
- 参考スコア（独自算出の注目度）: 0.802904964931021
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: What determines the unavoidable sample cost of learning cyclic causal structure? For cyclic linear non-Gaussian models, we study exact condensation recovery from observational data: identifying the strongly connected component (SCC) partition and all edges between components. We establish the first information-theoretic lower bounds on sample complexity for this target. For $p$ variables, maximum SCC size $s_{\max}$, and maximum external-parent count $d_B$, any estimator requires order $s_{\max}\log(ep/s_{\max})+d_B\log(ep/d_B)$ samples in the worst case over a regular model class. These bounds distinguish the costs of SCC membership and external-parent selection. Under principal invertibility and without correlation faithfulness, we establish a population block-exogeneity principle that identifies unknown root SCCs through residual independence and inclusion minimality. A sparse-adjustment characterization shows that small adjustment sets suffice to identify SCCs and their direct external parents, without regressing on all previously recovered variables. These characterizations yield BlockExo, which attains a structurally matching sample bound without knowing $s_{\max}$ or $d_B$ under suitable conditions. Simulations support the structural dependence of our sample bound and demonstrate BlockExo's sample-efficient recovery in comparisons with other methods for cyclic causal discovery.
- Abstract（参考訳）: 循環因果構造学習における避けられないサンプルコストは何か?
循環線形非ガウスモデルでは, 観測データから, 強結合成分(SCC)の分割と成分間のすべてのエッジを同定し, 正確な凝縮回復について検討する。
この目的に対して,サンプルの複雑さに関する情報理論的下界を初めて確立する。
変数$p$、最大 SCC size $s_{\max}$、最大外付けのcount $d_B$の場合、任意の推定器は、通常のモデルクラスよりも最悪の場合、$s_{\max}\log(ep/s_{\max})+d_B\log(ep/d_B)$サンプルを必要とする。
これらの境界は、SCCメンバーシップと外見選択のコストを区別する。
主可逆性と相関性のない信頼の下では、残留独立性および包含最小性を通じて未知の根のSCCを識別する集団ブロック・異種性原理を確立する。
スパース調整の特徴づけは、小さい調整セットは、以前に回復した全ての変数に回帰することなく、SCCとその直接的な外部親を特定するのに十分であることを示している。
これらの特徴付けは、適切な条件下で$s_{\max}$や$d_B$を知らずに構造的に整合したサンプルバウンドを得るBlockExoを生成する。
シミュレーションは, 試料境界の構造的依存性を支持し, 循環因果発見法と比較してBlockExoの試料効率の回復を実証する。
関連論文リスト
- Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。
我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
論文 参考訳（メタデータ） (2026-08-06T19:49:48Z) - Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue [17.761018390014602]
mathbbRn$ の自然パラメータ $z を、部分集合 $S に制約された独立標本から学ぶことは、高次元統計学における基礎的な挑戦である。
既存のパラメータ推定保証を太さ仮定で洗練し、前のサンプルの複雑さを$O( log n / 2)$ for $ell_infty$-recovery に改善し、未実行のミニマックスレートと一致させる。
論文 参考訳（メタデータ） (2026-07-24T20:01:15Z) - SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。
我々は悲観的な収束分析を避ける分析を提供する。
我々の成果は、既存の最先端の体制を改善した。
論文 参考訳（メタデータ） (2026-06-14T14:11:07Z) - Leave-One-Out Prediction for General Hypothesis Classes [9.855978207725549]
本稿では,EMM周辺における経験的リスクレベルセットに基づく一般的な集約手法であるMLSA(Median of Level-Set Aggregation)を紹介する。
LOO_S(hath) ;le; C cdot frac1n min_hin H L_S(h) ;+; fracComp(S,
論文 参考訳（メタデータ） (2026-03-02T16:27:44Z) - Phase-space entropy at acquisition reflects downstream learnability [54.4100065023873]
楽器分解位相空間に基づく取得レベルスカラー$S_mathcal B$を提案する。
本稿では, (S_mathcal B) が周期サンプリングの位相空間コヒーレンスを正確に同定できることを理論的に示す。
$|S_mathcal B|$は一貫してサンプリングジオメトリをランク付けし、トレーニングなしで下流での再構築/認識の困難を予測します。
論文 参考訳（メタデータ） (2025-12-22T10:03:51Z) - Improved Sample Complexity for Full Coverage in Compact and Continuous Spaces [0.0]
我々は$d$次元単位ハイパーキューブにおける一様ランダムサンプリングについて検討した。
故障確率に対数依存するサンプル複雑性を導出する。
我々の発見は、グリッドベースのカバレッジ保証に依存するアルゴリズムに対して、よりシャープな理論的ツールを提供する。
論文 参考訳（メタデータ） (2025-11-21T21:06:14Z) - Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。
近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。
非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
論文 参考訳（メタデータ） (2024-10-31T15:56:50Z) - Robustly estimating heterogeneity in factorial data using Rashomon Partitions [4.76518127830168]
我々は、羅生門分割セット(RPS)と呼ばれるモデル不確実性のための新しい枠組みを提案する。
RPSは、最大後部(MAP)モデルに近い後部密度を持つすべてのモデルで構成されている。
実験的な例として,チャリタブルギフトの価格効果,染色体構造の不均一性,マイクロファイナンスの導入の3つを挙げる。
論文 参考訳（メタデータ） (2024-04-02T17:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。