論文の概要: The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians

• arxiv url: http://arxiv.org/abs/2002.00329v2
• Date: Fri, 19 Jun 2020 17:36:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-04 19:57:15.580886
• Title: The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
• Title（参考訳）: 高度分離ガウスの混合学習におけるサンプル最適性を与えるEMアルゴリズム
• Authors: Jeongyeol Kwon, Constantine Caramanis
• Abstract要約: 我々は、期待最大化(EM)に対する新しい結果を証明する: EMは、分離された$Omega(sqrtlog k)$の下で局所的に収束することを示す。 我々の結果は、(潜在的に異なる)ガウス成分の事前の知識を前提としない。
• 参考スコア（独自算出の注目度）: 21.780375994511324
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of spherical Gaussian Mixture models with $k \geq 3$ components when the components are well separated. A fundamental previous result established that separation of $\Omega(\sqrt{\log k})$ is necessary and sufficient for identifiability of the parameters with polynomial sample complexity (Regev and Vijayaraghavan, 2017). In the same context, we show that $\tilde{O} (kd/\epsilon^2)$ samples suffice for any $\epsilon \lesssim 1/k$, closing the gap from polynomial to linear, and thus giving the first optimal sample upper bound for the parameter estimation of well-separated Gaussian mixtures. We accomplish this by proving a new result for the Expectation-Maximization (EM) algorithm: we show that EM converges locally, under separation $\Omega(\sqrt{\log k})$. The previous best-known guarantee required $\Omega(\sqrt{k})$ separation (Yan, et al., 2017). Unlike prior work, our results do not assume or use prior knowledge of the (potentially different) mixing weights or variances of the Gaussian components. Furthermore, our results show that the finite-sample error of EM does not depend on non-universal quantities such as pairwise distances between means of Gaussian components.
• Abstract（参考訳）: 成分が十分に分離されたとき、$k \geq 3$成分を持つ球状ガウス混合モデルの問題を考察する。 基本的な以前の結果は、$\Omega(\sqrt{\log k})$ の分離が多項式サンプルの複雑性を持つパラメータの識別に必要で十分であることを証明した(Regev and Vijayaraghavan, 2017)。 同じ文脈で、$\tilde{o} (kd/\epsilon^2)$ のサンプルが任意の$\epsilon \lesssim 1/k$ に対して十分であり、多項式から線型へのギャップを閉じていることを示す。 我々は、期待最大化(EM)アルゴリズムの新たな結果を証明することでこれを達成した: EMは、分離$\Omega(\sqrt{\log k})$の下で局所的に収束することを示す。 以前の最もよく知られている保証は$\Omega(\sqrt{k})$ separation(Yan, et al., 2017)であった。 以前の研究とは異なり、我々の結果はガウス成分の重みや分散を(潜在的に異なる)混合する事前の知識を前提としない。 さらに,EMの有限サンプル誤差はガウス成分間の対距離などの非ユニバーサル量に依存しないことを示す。

関連論文リスト

• Sample-Efficient Private Learning of Mixtures of Gaussians [11.392841244701605]
  およそ$kd2 + k1.5 d1.75 + k2 d$サンプルは、$k$任意の$d$次元ガウスの混合を学ぶのに十分である。 我々の作業は、以前の最高の結果 [AAL24b] よりも改善され、$d$が$k2$よりもはるかに大きい場合、確実に最適です。
  論文  参考訳（メタデータ） (2024-11-04T17:23:52Z)
• 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)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures [9.670578317106182]
  kgeq 2$ Gaussian 成分と未知の手段と未知の共分散(すべての成分について同一視される)の混合を考える。 混合重量が指数関数的に小さい場合にのみこのような硬さが現れることを示す。 我々は,最小混合重量の時間準多項式を用いた2乗法に基づくアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-12-10T10:51:44Z)
• Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EM [15.251738476719918]
  パラメータを既知の重みのK成分を用いたガウス混合モデルとして推定する問題を考察する。 本稿では, EM と勾配 EM の局所収束について, 従来の研究と比較し, より鮮明な解析を行った。 第2のコントリビューションは,EMと勾配EMによる精度評価のための試料サイズ要件の改善である。
  論文  参考訳（メタデータ） (2021-01-03T08:10:01Z)
• 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)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Outlier-Robust Clustering of Non-Spherical Mixtures [5.863264019032882]
  統計的に分離されたd-次元ガウスアン(k-GMM)の混合をクラスタリングするための最初のアウトリー・ローバストアルゴリズムを与える。 この結果は、$d$次元単位球面上の均一分布の任意のアフィン変換のクラスタリング混合に拡張される。
  論文  参考訳（メタデータ） (2020-05-06T17:24:27Z)
• Algebraic and Analytic Approaches for Parameter Learning in Mixture Models [66.96778152993858]
  1次元の混合モデルにおけるパラメータ学習のための2つの異なるアプローチを提案する。 これらの分布のいくつかについては、パラメータ推定の最初の保証を示す。
  論文  参考訳（メタデータ） (2020-01-19T05:10:56Z)

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

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