論文の概要: Finding Front-Door Adjustment Sets in Linear Time
- arxiv url: http://arxiv.org/abs/2211.16468v1
- Date: Tue, 29 Nov 2022 18:44:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-30 15:36:18.037950
- Title: Finding Front-Door Adjustment Sets in Linear Time
- Title（参考訳）: 線形時間におけるフロントドア調整セットの探索
- Authors: Marcel Wien\"obst, Benito van der Zander, Maciej Li\'skiewicz
- Abstract要約: フロントドア調整は、特定の有向非巡回グラフ(DAG)と観測データから因果効果を推定する手法である。
本稿では,DAGのフロントドア基準を満たす集合を初めて検出するアルゴリズムを提案する。
また,DAGのすべての前ドア調整セットを遅延で列挙するアルゴリズムも提供する。
- 参考スコア（独自算出の注目度）: 5.190207094732672
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Front-door adjustment is a classic technique to estimate causal effects from
a specified directed acyclic graph (DAG) and observed data. The advantage of
this approach is that it uses observed mediators to identify causal effects,
which is possible even in the presence of unobserved confounding. While the
statistical properties of the front-door estimation are quite well understood,
its algorithmic aspects remained unexplored for a long time. Recently, Jeong,
Tian, and Barenboim [NeurIPS 2022] have presented the first polynomial-time
algorithm for finding sets satisfying the front-door criterion in a given DAG,
with an $O(n^3(n+m))$ run time, where $n$ denotes the number of variables and
$m$ the number of edges of the graph. In our work, we give the first
linear-time, i.e. $O(n+m)$, algorithm for this task, which thus reaches the
asymptotically optimal time complexity, as the size of the input is
$\Omega(n+m)$. We also provide an algorithm to enumerate all front-door
adjustment sets in a given DAG with delay $O(n(n + m))$. These results improve
the algorithms by Jeong et al. [2022] for the two tasks by a factor of $n^3$,
respectively.
- Abstract（参考訳）: フロントドア調整は、特定の有向非巡回グラフ(DAG)と観測データから因果効果を推定する古典的な手法である。
このアプローチの利点は、観測されたメディエーターを使用して因果効果を識別することであり、これは観測されていないコンファウンディングの存在においても可能である。
フロントドア推定の統計的特性はかなりよく理解されているが、アルゴリズム的な側面は長い間解明されていない。
最近、Jeong, Tian, Barenboim [NeurIPS 2022] は、与えられたDAGのフロントドア基準を満たす集合を見つけるための最初の多項式時間アルゴリズムを提示し、$O(n^3(n+m))$ run time で、$n$は変数の数を表し、$m$はグラフのエッジの数を表す。
私たちの研究では、このタスクに最初の線形時間、すなわち$o(n+m)$というアルゴリズムを与え、入力のサイズが$\omega(n+m)$であるので漸近的に最適な時間複雑性に達する。
また、与えられたDAGのすべてのフロントドア調整セットを遅延$O(n(n + m))$で列挙するアルゴリズムも提供する。
これらの結果はjeongらによるアルゴリズムを改善する。
[2022] の2つのタスクはそれぞれ$n^3$ である。
関連論文リスト
- Almost linear time differentially private release of synthetic graphs [6.076406622352115]
本稿では,指数関数的メカニズムから,ほぼ線形時間と空間のアルゴリズムをサンプリングする。
直接的な結果として、差分入力を指数関数的に大きな$G$mエッジとして定義する。
これらは合成グラフを公開するためのプライベートファーストのプライベートアルゴリズムである。
論文 参考訳（メタデータ） (2024-06-04T09:44:24Z) - Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。
この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。
我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-02-27T18:12:58Z) - Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
グラフィック平均フィールドゲーム(GMFG)のための強化学習アルゴリズムを設計する。
我々は、正規化されたGMFGのナッシュ平衡(NE)を、グラフンが未知のときに学習することを目指している。
これらのアルゴリズムは、サンプルエージェントからグラモンを学習するために設計された最初のものである。
論文 参考訳（メタデータ） (2023-10-26T16:19:24Z) - The First Proven Performance Guarantees for the Non-Dominated Sorting
Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem [6.793248433673384]
NSGA-II(Non-Maninated Sorting Genetic Algorithm-II)は、多目的最適化問題を解くアルゴリズムの1つである。
従来の最適化問題であるNP完全二目的最小スパンニングツリー問題に対して、初めて証明された性能保証を与える。
論文 参考訳（メタデータ） (2023-05-22T19:59:19Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Efficient Mean Estimation with Pure Differential Privacy via a
Sum-of-Squares Exponential Mechanism [16.996435043565594]
純微分プライバシーを受ける独立サンプルの共分散で$d$正確率分布の平均を推定するアルゴリズムを初めて与える。
我々の主な手法は、強力なSum of Squares法(SoS)を用いて微分プライベートアルゴリズムを設計する新しいアプローチである。
論文 参考訳（メタデータ） (2021-11-25T09:31:15Z) - Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文 参考訳（メタデータ） (2021-09-29T16:25:02Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。