論文の概要: On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery

• arxiv url: http://arxiv.org/abs/2310.13553v1
• Date: Fri, 20 Oct 2023 14:52:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-23 22:24:47.842777
• Title: On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery
• Title（参考訳）: Von Mises 推定器を用いた条件独立試験のサンプル複雑性と因果発見への応用
• Authors: Fateme Jamshidi, Luca Ganassali, Negar Kiyavash
• Abstract要約: 条件付き独立テストは制約に基づく因果探索アルゴリズムにおいて不可欠なステップである。 我々は、最適パラメトリックレートを達成するVM-CIと呼ばれる推定器に基づいて、条件独立性の試験を設計する。 VM-CIは、時間またはサンプルの複雑さの観点から、他の一般的なCIテストよりも優れていることを実証的に示します。
• 参考スコア（独自算出の注目度）: 21.12645737093305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by conditional independence testing, an essential step in constraint-based causal discovery algorithms, we study the nonparametric Von Mises estimator for the entropy of multivariate distributions built on a kernel density estimator. We establish an exponential concentration inequality for this estimator. We design a test for conditional independence (CI) based on our estimator, called VM-CI, which achieves optimal parametric rates under smoothness assumptions. Leveraging the exponential concentration, we prove a tight upper bound for the overall error of VM-CI. This, in turn, allows us to characterize the sample complexity of any constraint-based causal discovery algorithm that uses VM-CI for CI tests. To the best of our knowledge, this is the first sample complexity guarantee for causal discovery for continuous variables. Furthermore, we empirically show that VM-CI outperforms other popular CI tests in terms of either time or sample complexity (or both), which translates to a better performance in structure learning as well.
• Abstract（参考訳）: 制約に基づく因果発見アルゴリズムにおける必須ステップである条件付き独立性テストに動機づけられ,カーネル密度推定器上に構築された多変量分布のエントロピーに対する非パラメトリックなフォン・ミセス推定器について検討した。 この推定器の指数集中不等式を確立する。 我々は,VM-CIと呼ばれる推定器をベースとした条件独立性テスト(CI)を設計し,スムーズな仮定の下で最適なパラメトリックレートを達成する。 指数集中を利用して、VM-CIの全体的な誤差に対して厳密な上限を証明した。 これにより、CIテストにVM-CIを使用する制約ベースの因果探索アルゴリズムのサンプル複雑性を特徴付けることができる。 我々の知る限りでは、これは連続変数の因果発見のための最初のサンプル複雑性保証である。 さらに,vm-ciは他の一般的なciテストよりも時間やサンプルの複雑さ(あるいはその両方)において優れており,構造学習のパフォーマンスも向上していることを示す。

関連論文リスト

• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  CoT(Chain-of-Thought)の促進とその変種は、多段階推論問題を解決する効果的な方法として人気を集めている。 統計的推定の観点からCoTのプロンプトを解析し,その複雑さを包括的に評価する。
  論文  参考訳（メタデータ） (2024-08-25T04:07:18Z)
• Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests [5.3595271893779906]
  フェデレート学習は、さまざまな場所でデータが収集され分析される広範囲な設定で適用可能であることから、近年大きな注目を集めている。 分散差分プライバシー(DP)制約下でのホワイトノイズ・ウィズ・ドリフトモデルにおける非パラメトリック適合性試験について検討した。
  論文  参考訳（メタデータ） (2024-06-10T19:25:19Z)
• Approximate Global Convergence of Independent Learning in Multi-Agent Systems [19.958920582022664]
  本稿では,Q$ラーニングとNatural Act-criticの2つの代表的なアルゴリズムについて,価値ベースのフレームワークとポリシーベースのフレームワークで検討する。 結果は、大域収束を達成する際のILの基本的な限界を特徴づけるエラー項まで、$tildemathcalO(epsilon-2)$のサンプル複雑性を示唆している。
  論文  参考訳（メタデータ） (2024-05-30T08:20:34Z)
• Finite-Time Convergence and Sample Complexity of Actor-Critic Multi-Objective Reinforcement Learning [20.491176017183044]
  本稿では多目的強化学習(MORL)問題に取り組む。 MOACと呼ばれる革新的なアクター批判アルゴリズムを導入し、競合する報酬信号間のトレードオフを反復的に行うことでポリシーを見出す。
  論文  参考訳（メタデータ） (2024-05-05T23:52:57Z)
• Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
  本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。 線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
  論文  参考訳（メタデータ） (2023-11-01T04:41:16Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Non-Stochastic CDF Estimation Using Threshold Queries [3.6576781735746513]
  実験的な分布を2つの課題で推定する問題に取り組む。 まず、アルゴリズムはデータを直接観察するのではなく、サンプルについて限られた数のしきい値クエリしか要求しない。 第二に、データは独立で同一の分散であると仮定されず、代わりにサンプルを生成する任意のプロセスが可能である。
  論文  参考訳（メタデータ） (2023-01-13T18:00:57Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities [8.010966370223985]
  通信制約下での単純な二項仮説テストのサンプルの複雑さは、少なくとも制約のない設定よりも大きい対数係数であることが示される。 我々のフレームワークは、分布が全変動距離で破壊されるような頑健な仮説テストにまで拡張する。
  論文  参考訳（メタデータ） (2022-06-06T17:42:11Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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