論文の概要: Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information

• arxiv url: http://arxiv.org/abs/2411.11516v1
• Date: Mon, 18 Nov 2024 12:25:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-19 14:34:36.451818
• Title: Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information
• Title（参考訳）: ガウス的相互情報のサンプル最適テストによるガウス的木モデルの効率的なサンプル最適学習
• Authors: Sutanu Gayen, Sanket Kale, Sayantan Sen,
• Abstract要約: ガウス確率変数に対する条件付き相互情報テスタを開発した。 条件付き相互情報の連鎖ルールは、推定された(条件付き)相互情報の保持を継続することを示す。 また、基礎となるガウスモデルが木構造であることが分かっていない場合、$widetildeTheta(n2varepsilon-2)$サンプルが必要であることも示している。
• 参考スコア（独自算出の注目度）: 1.7419682548187605
• License:
• Abstract: Learning high-dimensional distributions is a significant challenge in machine learning and statistics. Classical research has mostly concentrated on asymptotic analysis of such data under suitable assumptions. While existing works [Bhattacharyya et al.: SICOMP 2023, Daskalakis et al.: STOC 2021, Choo et al.: ALT 2024] focus on discrete distributions, the current work addresses the tree structure learning problem for Gaussian distributions, providing efficient algorithms with solid theoretical guarantees. This is crucial as real-world distributions are often continuous and differ from the discrete scenarios studied in prior works. In this work, we design a conditional mutual information tester for Gaussian random variables that can test whether two Gaussian random variables are independent, or their conditional mutual information is at least $\varepsilon$, for some parameter $\varepsilon \in (0,1)$ using $\mathcal{O}(\varepsilon^{-1})$ samples which we show to be near-optimal. In contrast, an additive estimation would require $\Omega(\varepsilon^{-2})$ samples. Our upper bound technique uses linear regression on a pair of suitably transformed random variables. Importantly, we show that the chain rule of conditional mutual information continues to hold for the estimated (conditional) mutual information. As an application of such a mutual information tester, we give an efficient $\varepsilon$-approximate structure-learning algorithm for an $n$-variate Gaussian tree model that takes $\widetilde{\Theta}(n\varepsilon^{-1})$ samples which we again show to be near-optimal. In contrast, when the underlying Gaussian model is not known to be tree-structured, we show that $\widetilde{{{\Theta}}}(n^2\varepsilon^{-2})$ samples are necessary and sufficient to output an $\varepsilon$-approximate tree structure. We perform extensive experiments that corroborate our theoretical convergence bounds.
• Abstract（参考訳）: 高次元分布の学習は、機械学習と統計学において重要な課題である。 古典的な研究は主に適切な仮定の下でそのようなデータの漸近解析に集中してきた。 既存の研究(Bhattacharyya et al : SICOMP 2023, Daskalakis et al : STOC 2021, Choo et al : ALT 2024]は離散分布に重点を置いているが、現在の研究はガウス分布のツリー構造学習問題に対処し、確固とした理論的保証を備えた効率的なアルゴリズムを提供する。 実世界の分布はしばしば連続的であり、以前の研究で研究された離散的なシナリオとは異なるため、これは非常に重要である。 本研究では、2つのガウス確率変数が独立であるかどうかを検証できるガウス確率変数の条件付き相互情報テスタを設計し、その条件付き相互情報は少なくとも$\varepsilon$で、あるパラメータに対して$\varepsilon \in (0,1)$で$\mathcal{O}(\varepsilon^{-1})$サンプルを使用する。 対照的に、加法推定には$\Omega(\varepsilon^{-2})$サンプルが必要である。 我々の上界法は、好適に変換された一対の確率変数に対して線形回帰を用いる。 重要なことは、条件付き相互情報の連鎖規則が、推定された(条件付き)相互情報の保持を継続していることである。 そのような相互情報テスタの応用として、$\widetilde{\Theta}(n\varepsilon^{-1})$サンプルを取る$n$-variate Gaussianツリーモデルに対して、効率的な$\varepsilon$-approximate構造学習アルゴリズムを提供する。 対照的に、基礎となるガウスモデルが木構造であることが分かっていない場合、$\widetilde{{{\Theta}}}(n^2\varepsilon^{-2})$サンプルが必要であり、$\varepsilon$-approximateツリー構造を出力するのに十分であることを示す。 我々は、理論収束境界を腐食させる広範な実験を行う。

関連論文リスト

• Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
  本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。 我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
  論文  参考訳（メタデータ） (2024-10-02T15:21:07Z)
• Convergence Analysis of Probability Flow ODE for Score-based Generative Models [5.939858158928473]
  確率フローODEに基づく決定論的サンプリング器の収束特性を理論的・数値的両面から検討する。 連続時間レベルでは、ターゲットと生成されたデータ分布の総変動を$mathcalO(d3/4delta1/2)$で表すことができる。
  論文  参考訳（メタデータ） (2024-04-15T12:29:28Z)
• Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples [9.649879910148854]
  差分プライバシー(DP)制約下におけるガウシアン混合量の推定問題について検討する。 主な結果は、$textpoly(k,d,1/alpha,1/varepsilon,log (1/delta))$サンプルが$k$ Gaussians in $mathbbRd$から$alpha$までを推定するのに十分であることです。 これは GMM の構造的仮定を一切含まない問題に対する最初の有限標本複雑性上界である。
  論文  参考訳（メタデータ） (2023-09-07T17:02:32Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
  大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。 この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。 我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
  論文  参考訳（メタデータ） (2023-02-21T17:52:23Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization [96.26317627118912]
  群分散ロバスト最適化(GDRO) オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。 分布依存収束率を導出できる重み付きGDROの新規な定式化。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)

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

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