論文の概要: Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs

• arxiv url: http://arxiv.org/abs/2308.16859v2
• Date: Sun, 31 Mar 2024 16:03:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-02 15:44:31.020184
• Title: Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs
• Title（参考訳）: 動的指向非巡回グラフ学習における情報理論的に最適サンプル複雑度
• Authors: Mishfad Shaikh Veedu, Deepjyoti Deka, Murti V. Salapaka,
• Abstract要約: 直交非巡回グラフ(DAG)上での線形力学系(LDS)の相互作用や依存性を学習する際の最適なサンプル複雑性について検討する。 静的DAG設定にインスパイアされ,観測時系列のPSD行列に基づくメトリックとアルゴリズムが提案され,DDAGを再構築する。
• 参考スコア（独自算出の注目度）: 1.433758865948252
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this article, the optimal sample complexity of learning the underlying interactions or dependencies of a Linear Dynamical System (LDS) over a Directed Acyclic Graph (DAG) is studied. We call such a DAG underlying an LDS as dynamical DAG (DDAG). In particular, we consider a DDAG where the nodal dynamics are driven by unobserved exogenous noise sources that are wide-sense stationary (WSS) in time but are mutually uncorrelated, and have the same {power spectral density (PSD)}. Inspired by the static DAG setting, a metric and an algorithm based on the PSD matrix of the observed time series are proposed to reconstruct the DDAG. It is shown that the optimal sample complexity (or length of state trajectory) needed to learn the DDAG is $n=\Theta(q\log(p/q))$, where $p$ is the number of nodes and $q$ is the maximum number of parents per node. To prove the sample complexity upper bound, a concentration bound for the PSD estimation is derived, under two different sampling strategies. A matching min-max lower bound using generalized Fano's inequality also is provided, thus showing the order optimality of the proposed algorithm.
• Abstract（参考訳）: 本稿では,DAG(Directed Acyclic Graph)上での線形力学系(LDS)の相互作用や依存性を学習する際の最適なサンプル複雑性について検討する。 このようなDAGを動的DAG (DDAG) と呼ぶ。 特に,広義の定常雑音源(WSS)と相互に相関がなく,スペクトル密度(PSD)が同じであるDDAGについて考察する。 静的DAG設定にインスパイアされ,観測時系列のPSD行列に基づくメトリックとアルゴリズムが提案され,DDAGを再構築する。 DDAGを学習するのに最適なサンプルの複雑さ(あるいは状態軌跡の長さ)は$n=\Theta(q\log(p/q))$であり、$p$はノード数、$q$はノード当たりの親数の最大値である。 試料の複雑さ上限を証明するために,2つの異なるサンプリング戦略の下でPSD推定のための濃度境界を導出する。 一般化されたファノの不等式を用いた min-max 下限のマッチングも提供され、提案アルゴリズムの順序最適性を示す。

関連論文リスト

• Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
  非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。 対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。 我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
  論文  参考訳（メタデータ） (2024-05-27T00:53:18Z)
• Scaling up Stochastic Gradient Descent for Non-convex Optimisation [5.908471365011942]
  本稿では,共有並列計算問題に対する新しいアプローチを提案する。 2つの戦略を統一されたフレームワークに組み合わせることで、DPSGDはより良い取引計算フレームワークになります。 深層学習(DRL)問題と深層学習(DRL)問題(アドバンテージアクター - A2C)についてDPSGDにより潜在ゲインを達成できる。
  論文  参考訳（メタデータ） (2022-10-06T13:06:08Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。 Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。 提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
  論文  参考訳（メタデータ） (2022-08-29T18:01:42Z)
• Sparse-Group Log-Sum Penalized Graphical Model Learning For Time Series [12.843340232167266]
  定常多変量ガウス時系列の条件独立グラフ(CIG)を推定する問題を考察する。 スパース群ラスソに基づく周波数領域の定式化が文献で検討されている。 合成データと実データの両方を活用するアプローチについて説明する。
  論文  参考訳（メタデータ） (2022-04-29T00:06:41Z)
• From graphs to DAGs: a low-complexity model and a scalable algorithm [0.0]
  本稿では,低ランク行列因数分解とDAGの連続的な最適化のためのスペース化機構を組み合わせたLoRAM for Low-Rank Additive Modelを提案する。 提案手法は,NoTearsと同じDAG特性関数を扱いながら,立方的複雑性から二次的複雑性への還元を実現する。
  論文  参考訳（メタデータ） (2022-04-10T10:22:56Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  我々は、$K関連ガウス非巡回グラフ(DAG)の発見問題を考える。 マルチタスク学習環境下では, 線形構造方程式モデルを学習するためのMLE ($l_1/l$-regularized maximum chance estimator) を提案する。 理論的には、関係するタスクにまたがるデータを活用することで、因果順序を復元する際のサンプルの複雑さをより高めることができることを示す。
  論文  参考訳（メタデータ） (2021-11-03T22:10:18Z)
• Learning linear non-Gaussian directed acyclic graph with diverging number of nodes [12.49848873864773]
  有向非巡回グラフ(DAG)として表される非巡回モデルは、収集ノード間の方向因果関係を表現するために広く用いられている。 本研究では,高次元の場合において,連続的な非ガウス分布の雑音が生じるような線形非ガウスDAGを効率よく学習する方法を提案する。
  論文  参考訳（メタデータ） (2021-11-01T07:34:53Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。 この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。 本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。 我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
  論文  参考訳（メタデータ） (2021-05-27T23:41:01Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。 本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
  論文  参考訳（メタデータ） (2020-11-10T11:36:30Z)
• Your GAN is Secretly an Energy-based Model and You Should use Discriminator Driven Latent Sampling [106.68533003806276]
  本研究では,潜時空間におけるサンプリングは,潜時空間の前対数密度と判別器出力スコアの和によって誘導されるエネルギーベースモデルに従って,潜時空間におけるサンプリングを行うことによって達成できることを示す。 判別器駆動潜時サンプリング(DDLS)は,高次元画素空間で動作する従来の手法と比較して,高効率であることを示す。
  論文  参考訳（メタデータ） (2020-03-12T23:33:50Z)

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

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