論文の概要: Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixtures
- arxiv url: http://arxiv.org/abs/2506.06584v1
- Date: Fri, 06 Jun 2025 23:32:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-10 16:33:10.343992
- Title: Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixtures
- Title（参考訳）: 過パラメータ化ガウス混合系のグラディエントEMの大域的収束
- Authors: Mo Zhou, Weihang Xu, Maryam Fazel, Simon S. Du,
- Abstract要約: 勾配EMの力学を考察し, テンソル分解を用いて幾何的景観を特徴付ける。
これは、m=2$という特別な場合を超えるEMや勾配EMに対する最初の大域収束と回復の結果である。
- 参考スコア（独自算出の注目度）: 53.51230405648361
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Learning Gaussian Mixture Models (GMMs) is a fundamental problem in machine learning, with the Expectation-Maximization (EM) algorithm and its popular variant gradient EM being arguably the most widely used algorithms in practice. In the exact-parameterized setting, where both the ground truth GMM and the learning model have the same number of components $m$, a vast line of work has aimed to establish rigorous recovery guarantees for EM. However, global convergence has only been proven for the case of $m=2$, and EM is known to fail to recover the ground truth when $m\geq 3$. In this paper, we consider the $\textit{over-parameterized}$ setting, where the learning model uses $n>m$ components to fit an $m$-component ground truth GMM. In contrast to the exact-parameterized case, we provide a rigorous global convergence guarantee for gradient EM. Specifically, for any well separated GMMs in general position, we prove that with only mild over-parameterization $n = \Omega(m\log m)$, randomly initialized gradient EM converges globally to the ground truth at a polynomial rate with polynomial samples. Our analysis proceeds in two stages and introduces a suite of novel tools for Gaussian Mixture analysis. We use Hermite polynomials to study the dynamics of gradient EM and employ tensor decomposition to characterize the geometric landscape of the likelihood loss. This is the first global convergence and recovery result for EM or Gradient EM beyond the special case of $m=2$.
- Abstract（参考訳）: 学習ガウス混合モデル(GMM)は機械学習の基本的な問題であり、期待-最大化(EM)アルゴリズムとその一般的な変分勾配EMは、実際最も広く使われているアルゴリズムである。
基礎的真理GMMと学習モデルが同じコンポーネント数$m$の正確なパラメータ設定では、EMの厳密な回復保証を確立することを目的としている。
しかし、大域収束は$m=2$の場合のみ証明されており、m\geq 3$のとき、EMは基底真実を回復できないことが知られている。
本稿では、学習モデルが$m$-component ground truth GMMに適合するために$n>m$コンポーネントを使用する場合、$\textit{over-parameterized}$setを考える。
正確なパラメータ化の場合とは対照的に、勾配EMに対して厳密な大域収束を保証する。
具体的には、任意のよく分離された GMM に対して、弱過パラメータ化 $n = \Omega(m\log m)$ で、ランダムに初期化された勾配 EM が多項式サンプルを持つ多項式速度で大域的に基底真理に収束することを証明する。
分析は2段階に及び,ガウス混合解析のための新しいツール群を紹介する。
我々は、Hermite多項式を用いて勾配EMの力学を研究し、テンソル分解を用いて、チャンス損失の幾何学的景観を特徴づける。
これは、m=2$という特別な場合を超えた、EM あるいは Gradient EM に対する最初の大域収束と回復の結果である。
関連論文リスト
- Learning large softmax mixtures with warm start EM [17.081578976570437]
ソフトマックス混合モデル(SMM)は、$p$候補からRRL$の$x_jを選択する確率をモデル化するために導入された離散的な$K$混合モデルである。
本稿では,高次元SMMにおけるEMアルゴリズムの包括的解析を行う。
論文 参考訳（メタデータ） (2024-09-16T00:14:48Z) - Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Models [47.294535652946095]
ガウス混合モデル(GMM)の勾配予測-最大化(EM)アルゴリズムについて検討する。
これは、2ドル以上の成分を持つガウス混合に対する最初の大域収束結果である。
論文 参考訳（メタデータ） (2024-06-29T16:44:29Z) - MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。
一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文 参考訳（メタデータ） (2024-05-29T18:36:59Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Transformers as Support Vector Machines [54.642793677472724]
自己アテンションの最適化幾何と厳密なSVM問題との間には,形式的等価性を確立する。
勾配降下に最適化された1層変圧器の暗黙バイアスを特徴付ける。
これらの発見は、最適なトークンを分離し選択するSVMの階層としてのトランスフォーマーの解釈を刺激していると信じている。
論文 参考訳（メタデータ） (2023-08-31T17:57:50Z) - Learning Gaussian Mixtures with Generalised Linear Models: Precise
Asymptotics in High-dimensions [79.35722941720734]
多クラス分類問題に対する一般化線形モデルは、現代の機械学習タスクの基本的な構成要素の1つである。
実験的リスク最小化による高次元推定器の精度を実証する。
合成データの範囲を超えて我々の理論をどのように適用できるかを論じる。
論文 参考訳（メタデータ） (2021-06-07T16:53:56Z) - 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) - The EM Algorithm gives Sample-Optimality for Learning Mixtures of
Well-Separated Gaussians [21.780375994511324]
我々は、期待最大化(EM)に対する新しい結果を証明する: EMは、分離された$Omega(sqrtlog k)$の下で局所的に収束することを示す。
我々の結果は、(潜在的に異なる)ガウス成分の事前の知識を前提としない。
論文 参考訳（メタデータ） (2020-02-02T05:09:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。