論文の概要: Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?

• arxiv url: http://arxiv.org/abs/2610.07551v1
• Date: Tue, 06 Oct 2026 00:29:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 02:58:29.723893
• Title: Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?
• Title（参考訳）: グラディエントEMが高次元ガウス混合を学習するためには$\sqrt{d}$分離が必要か?
• Abstract要約: 次元依存は高次元設定では避けられないことを示す。 本稿では, 標準EM更新を混合重みと勾配EM更新に用いたハイブリッドEMアルゴリズムについて検討する。
• 参考スコア（独自算出の注目度）: 54.060185145753714
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning Gaussian mixture models (GMMs) using the Expectation-Maximization (EM) algorithm and its gradient-based variants is a fundamental problem in machine learning. It is known that randomly initialized (gradient) EM fails to learn multi-component GMMs in the exact-parameterized setting, where the number of components matches that of the ground-truth GMM. Recently, global convergence of gradient EM has been established in the over-parameterized setting, where more components are used, provided that the ground-truth components are well separated. In particular, the minimum separation between ground-truth components is required to scale as $Ω(\sqrt{d})$, where $d$ is the dimension. In this paper, we show that this dimensional dependence is unavoidable in high-dimensional settings. Specifically, we consider a hybrid EM algorithm that uses standard EM updates for the mixing weights and gradient EM updates for the component means. For any $ε> 0$, we prove that when the dimension is sufficiently large, in the worst case a separation of order $Ω(d^{0.5-ε})$ is insufficient to guarantee global convergence of population gradient EM in sub-exponential time under random initialization, even in the over-parameterized regime. Our result establishes an almost optimal worst-case lower bound on the ground-truth separation required for learning Gaussian mixtures via gradient EM in high dimensions.
• Abstract（参考訳）: expectation-Maximization (EM)アルゴリズムを用いたガウス混合モデル(GMM)の学習とその勾配に基づく変形は、機械学習の基本的な問題である。 ランダムに初期化(漸進)されたEMは、基幹GMMの成分数と一致する正確なパラメータ設定で多成分GMMを学習できないことが知られている。 近年, 地上構造成分が十分に分離されている場合, より多くの成分が使用される過パラメータ化環境において, 勾配EMのグローバル収束が確立されている。 特に、グラウンドトルース成分間の最小分離は、$d$が次元であるような$Ω(\sqrt{d})$としてスケールする必要がある。 本稿では,この次元依存は高次元設定では避けられないことを示す。 具体的には、標準EM更新を混合重みと勾配EM更新に使用するハイブリッドEMアルゴリズムについて検討する。 任意の$ε> 0$に対して、次元が十分に大きいとき、最悪の場合、位数$Ω(d^{0.5-ε})$の分離は、ランダム初期化の下で、過度にパラメータ化された状態であっても、サブ指数時間において、集団勾配EMの大域的な収束を保証するには不十分であることを示す。 以上の結果から,高次元の勾配EMによるガウス混合の学習に必要な接地構造分離の最小値がほぼ最適であることがわかった。

関連論文リスト

• A Parameter-Free Zeroth-Order Method with Covariance Matrix Adaptation and Effective Dimension [85.30100781543337]
  POEMCMAは複雑なブラックボックス問題に対する新しいパラメータフリーゼロ次アルゴリズムである。 我々は, POEMCMA がほぼ最適収束速度を達成し, L2 D_mathcalX2varepsilon2right)$ 0 次オラクルクエリを必要とせず, 約$tildemathcalOleft(fracd* (hat) L2 D_mathcalX2varepsilon2right) のみを必要とすることを示した。
  論文  参考訳（メタデータ） (2026-09-29T21:22:43Z)
• Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixtures [53.51230405648361]
  勾配EMの力学を考察し, テンソル分解を用いて幾何的景観を特徴付ける。 これは、m=2$という特別な場合を超えるEMや勾配EMに対する最初の大域収束と回復の結果である。
  論文  参考訳（メタデータ） (2025-06-06T23:32:38Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  分散サーバ(DFL)はクライアント・クライアント・アーキテクチャへの依存をなくす。 非滑らかな正規化はしばしば機械学習タスクに組み込まれる。 本稿では,これらの問題を解決する新しいDNCFLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-17T08:32:25Z)
• Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Models [47.294535652946095]
  ガウス混合モデル(GMM)の勾配予測-最大化(EM)アルゴリズムについて検討する。 これは、2ドル以上の成分を持つガウス混合に対する最初の大域収束結果である。
  論文  参考訳（メタデータ） (2024-06-29T16:44:29Z)
• 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)
• 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)

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

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