論文の概要: Adaptivity Complexity for Causal Graph Discovery
- arxiv url: http://arxiv.org/abs/2306.05781v1
- Date: Fri, 9 Jun 2023 09:49:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-12 14:00:26.812915
- Title: Adaptivity Complexity for Causal Graph Discovery
- Title（参考訳）: 因果グラフ発見のための適応複雑性
- Authors: Davin Choo, Kirankumar Shiragur
- Abstract要約: 本稿では,アルゴリズム設計者が合計$r$連続ラウンドで因果グラフを復元する,$r$適応性の問題を考察する。
我々は、検証数に関して$O(minr,log n cdot n1/minr,log n)$近似を達成する$r$適応アルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 7.424262881242935
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Causal discovery from interventional data is an important problem, where the
task is to design an interventional strategy that learns the hidden ground
truth causal graph $G(V,E)$ on $|V| = n$ nodes while minimizing the number of
performed interventions. Most prior interventional strategies broadly fall into
two categories: non-adaptive and adaptive. Non-adaptive strategies decide on a
single fixed set of interventions to be performed while adaptive strategies can
decide on which nodes to intervene on sequentially based on past interventions.
While adaptive algorithms may use exponentially fewer interventions than their
non-adaptive counterparts, there are practical concerns that constrain the
amount of adaptivity allowed. Motivated by this trade-off, we study the problem
of $r$-adaptivity, where the algorithm designer recovers the causal graph under
a total of $r$ sequential rounds whilst trying to minimize the total number of
interventions. For this problem, we provide a $r$-adaptive algorithm that
achieves $O(\min\{r,\log n\} \cdot n^{1/\min\{r,\log n\}})$ approximation with
respect to the verification number, a well-known lower bound for adaptive
algorithms. Furthermore, for every $r$, we show that our approximation is
tight. Our definition of $r$-adaptivity interpolates nicely between the
non-adaptive ($r=1$) and fully adaptive ($r=n$) settings where our
approximation simplifies to $O(n)$ and $O(\log n)$ respectively, matching the
best-known approximation guarantees for both extremes. Our results also extend
naturally to the bounded size interventions.
- Abstract（参考訳）: 介入データからの因果発見は重要な問題であり、そのタスクは、実行された介入の数を最小化しながら、隠れた基底真理因果グラフである$g(v,e)$ on $|v| = n$ノードを学ぶ介入戦略を設計することである。
従来の介入戦略は、非適応と適応の2つのカテゴリに大別される。
非適応戦略は単一の固定された介入セットを決定し、適応戦略は過去の介入に基づいてどのノードに順次介入するかを決定することができる。
適応アルゴリズムは、非適応アルゴリズムよりも指数関数的に少ない介入を用いるが、許容される適応性量を制限する実用的な懸念がある。
このトレードオフによって、アルゴリズム設計者が介入の総数を最小限に抑えながら、合計$r$シーケンシャルラウンドで因果グラフを復元する、$r$-adaptivityの問題を研究する。
この問題に対して、r$適応アルゴリズムを提供し、適応アルゴリズムの有名な下限である検証数に対して、$o(\min\{r,\log n\} \cdot n^{1/\min\{r,\log n\}})$近似を達成する。
さらに、$r$ ごとに、近似値がタイトであることが分かる。
r$-adaptivityの定義は、非適応的(r=1$)と完全適応(r=n$)の設定とをうまく補間し、近似値がそれぞれ$o(n)$ と $o(\log n)$ に簡単になるようにします。
また,この結果は境界サイズの介入にも自然に拡がる。
関連論文リスト
- Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - Verification and search algorithms for causal DAGs [11.038866111306728]
クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。
我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。
この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-30T15:52:30Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Intervention Efficient Algorithms for Approximate Learning of Causal
Graphs [22.401163479802094]
我々は、潜時の存在下で観察された変数の集合間の因果関係を学習する問題を研究する。
我々の目標は、介入の最小限の費用で、すべての因果関係や祖先関係の方向性を$G$で回収することです。
我々のアルゴリズムは効率的な介入設計と低コストな分離集合系の設計を組み合わせる。
論文 参考訳（メタデータ） (2020-12-27T17:08:46Z) - Budgeted and Non-budgeted Causal Bandits [2.9005223064604078]
因果グラフで良い介入を学ぶことは、サイド情報を持つマルチアームのバンディット問題としてモデル化することができる。
介入コストに基づいて観察と介入を最適にトレードオフする単純な後悔を最小限に抑えるアルゴリズムを提案する。
本研究は,現在の文献で最もよく知られた境界と比較し,実験的に検証した。
論文 参考訳（メタデータ） (2020-12-13T13:31:14Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Robust estimation via generalized quasi-gradients [28.292300073453877]
最近提案されたロバスト推定問題の多くが効率的に解ける理由を示す。
我々は「一般化された準次数」の存在を識別する
一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-05-28T15:14:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。