論文の概要: Information Theoretically Optimal Sample Complexity of Learning
Dynamical Directed Acyclic Graphs
- arxiv url: http://arxiv.org/abs/2308.16859v1
- Date: Thu, 31 Aug 2023 17:03:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-01 13:42:24.292367
- Title: Information Theoretically Optimal Sample Complexity of Learning
Dynamical Directed Acyclic Graphs
- Title（参考訳）: 学習動的有向非巡回グラフの理論的に最適なサンプル複雑性
- Authors: Mishfad Shaikh Veedu, Deepjyoti Deka, and Murti V. Salapaka
- Abstract要約: 直進非巡回グラフ(DAG)を用いた線形力学系(LDS)の相互作用/依存性を学習する際の最適なサンプル複雑性について検討する。
DDAGを再構築するために、静的設定にインスパイアされた観測時系列のPSD行列に基づくメトリックとアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 1.433758865948252
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this article, the optimal sample complexity of learning the underlying
interaction/dependencies of a Linear Dynamical System (LDS) over a Directed
Acyclic Graph (DAG) is studied. The sample complexity of learning a DAG's
structure is well-studied for static systems, where the samples of nodal states
are independent and identically distributed (i.i.d.). However, such a study is
less explored for DAGs with dynamical systems, where the nodal states are
temporally correlated. We call such a DAG underlying an LDS as \emph{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 settings, a metric and an algorithm
based on the PSD matrix of the observed time series are proposed to reconstruct
the DDAG. The equal noise PSD assumption can be relaxed such that
identifiability conditions for DDAG reconstruction are not violated. For the
LDS with WSS (sub) Gaussian exogenous noise sources, 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)上での線形力学系(LDS)の相互作用/依存性を学習する際の最適なサンプル複雑性について検討する。
dagの構造を学習するサンプルの複雑さは、ノード状態のサンプルが独立かつ同一に分散する静的システムではよく研究されている(i.i.d.)。
しかし, 動的系を持つDAGでは, 正弦波状態が時間的に相関しているため, そのような研究は少ない。
LDS の基盤となる DAG を \emph{dynamical} DAG (DDAG) と呼ぶ。
特に、時間的に広義の定常(wss)でありながら相互に相関のない非観測外因性ノイズ源によってノーダルダイナミクスが駆動されるddagを考えると、同じ<power spectral density(psd)" を持つ。
DDAGを再構築するために、静的設定にインスパイアされた観測時系列のPSD行列に基づくメトリックとアルゴリズムを提案する。
等価ノイズPSD仮定は、DDAG再構成の識別可能性条件が違反しないように緩和することができる。
WSS (sub) Gaussian exogenous noise source を持つ LDS の場合、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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。