論文の概要: Learning Gaussian DAG Models without Condition Number Bounds

• arxiv url: http://arxiv.org/abs/2511.06164v1
• Date: Sat, 08 Nov 2025 23:42:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 21:18:44.787554
• Title: Learning Gaussian DAG Models without Condition Number Bounds
• Title（参考訳）: 条件数境界のないガウスDAGモデルの学習
• Authors: Constantinos Daskalakis, Vardis Kandiros, Rui Yao,
• Abstract要約: ガウス図形モデルのトポロジを学習する問題について検討する。 以前の作業では、$O(d log n)$サンプルがこのタスクに十分であることがわかった。 基礎となるグラフを復元し,必要なサンプルの数が条件数に依存しないことを証明するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 23.343281561400033
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We study the problem of learning the topology of a directed Gaussian Graphical Model under the equal-variance assumption, where the graph has $n$ nodes and maximum in-degree $d$. Prior work has established that $O(d \log n)$ samples are sufficient for this task. However, an important factor that is often overlooked in these analyses is the dependence on the condition number of the covariance matrix of the model. Indeed, all algorithms from prior work require a number of samples that grows polynomially with this condition number. In many cases this is unsatisfactory, since the condition number could grow polynomially with $n$, rendering these prior approaches impractical in high-dimensional settings. In this work, we provide an algorithm that recovers the underlying graph and prove that the number of samples required is independent of the condition number. Furthermore, we establish lower bounds that nearly match the upper bound up to a $d$-factor, thus providing an almost tight characterization of the true sample complexity of the problem. Moreover, under a further assumption that all the variances of the variables are bounded, we design a polynomial-time algorithm that recovers the underlying graph, at the cost of an additional polynomial dependence of the sample complexity on $d$. We complement our theoretical findings with simulations on synthetic datasets that confirm our predictions.
• Abstract（参考訳）: 配向ガウス図形モデルのトポロジーを等分散仮定で学習する問題について検討し、このグラフはノードが$n$、最大が$d$である。 以前の作業では、$O(d \log n)$サンプルがこのタスクに十分であることがわかった。 しかし、これらの分析でしばしば見過ごされる重要な要因は、モデルの共分散行列の条件数に依存することである。 実際、以前の研究から得られた全てのアルゴリズムは、この条件数で多項式的に成長する多くのサンプルを必要とする。 条件数は$n$で多項式的に増加し、これらの以前のアプローチは高次元の設定では実用的ではない。 本研究では,基礎となるグラフを復元し,必要なサンプルの数が条件数に依存しないことを証明するアルゴリズムを提案する。 さらに、上界が$d$-factorにほぼ一致するような下界を確立し、問題の真のサンプル複雑性をほとんど正確に評価する。 さらに、変数のすべての分散が有界であるという仮定の下で、$d$上のサンプル複雑性のさらなる多項式依存性を犠牲にして、基礎となるグラフを復元する多項式時間アルゴリズムを設計する。 我々は、予測を裏付ける合成データセットのシミュレーションで理論的な結果を補完する。

関連論文リスト

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Feature Adaptation for Sparse Linear Regression [20.923321050404827]
  スパース線形回帰は高次元統計学における中心的な問題である。 少数の近似依存を許容するアルゴリズムを提供する。 我々のフレームワークは、疎線形回帰のためのより広範な機能適応のフレームワークに適合する。
  論文  参考訳（メタデータ） (2023-05-26T12:53:13Z)
• Optimal estimation of Gaussian DAG models [14.240183323622288]
  観測データからガウス指向非巡回グラフ(DAG)を学習する際の最適なサンプル複雑性について検討した。 我々の結果は、より一般的な同定の仮定や、ガウス以下の誤りにも及んでいる。
  論文  参考訳（メタデータ） (2022-01-25T18:56:56Z)
• On Model Selection Consistency of Lasso for High-Dimensional Ising Models on Tree-like Graphs [13.14903445595385]
  近傍型最小絶対収縮・選択演算子(Lasso)を用いた高次元イジングモデル選択の問題点を考察する。 常磁性相の任意の木様グラフに対して、サンプルサイズ$n=Omega(d3logp)$で一貫したモデル選択が達成できることは厳密に証明されている。 ラッソの人気と効率性を考えると、厳密な解析はイジングモデル選択における実践的利用の理論的裏付けとなる。
  論文  参考訳（メタデータ） (2021-10-16T07:23:02Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

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