論文の概要: On the Minimax Optimality of the EM Algorithm for Learning Two-Component
Mixed Linear Regression
- arxiv url: http://arxiv.org/abs/2006.02601v2
- Date: Fri, 5 Feb 2021 17:17:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 09:16:51.882931
- Title: On the Minimax Optimality of the EM Algorithm for Learning Two-Component
Mixed Linear Regression
- Title(参考訳): 2成分混合線形回帰学習のためのEMアルゴリズムの最小最適性について
- Authors: Jeongyeol Kwon, Nhat Ho, Constantine Caramanis
- Abstract要約: 信号-雑音比(SNR)の全ての条件下での2成分混合線形回帰学習のためのEMアルゴリズムの収束率について検討する。
EMアルゴリズムは,すべてのSNR条件下で,最小限のサンプル複雑性を実現する。
- 参考スコア(独自算出の注目度): 30.09238179576628
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the convergence rates of the EM algorithm for learning two-component
mixed linear regression under all regimes of signal-to-noise ratio (SNR). We
resolve a long-standing question that many recent results have attempted to
tackle: we completely characterize the convergence behavior of EM, and show
that the EM algorithm achieves minimax optimal sample complexity under all SNR
regimes. In particular, when the SNR is sufficiently large, the EM updates
converge to the true parameter $\theta^{*}$ at the standard parametric
convergence rate $\mathcal{O}((d/n)^{1/2})$ after $\mathcal{O}(\log(n/d))$
iterations. In the regime where the SNR is above $\mathcal{O}((d/n)^{1/4})$ and
below some constant, the EM iterates converge to a $\mathcal{O}({\rm SNR}^{-1}
(d/n)^{1/2})$ neighborhood of the true parameter, when the number of iterations
is of the order $\mathcal{O}({\rm SNR}^{-2} \log(n/d))$. In the low SNR regime
where the SNR is below $\mathcal{O}((d/n)^{1/4})$, we show that EM converges to
a $\mathcal{O}((d/n)^{1/4})$ neighborhood of the true parameters, after
$\mathcal{O}((n/d)^{1/2})$ iterations. Notably, these results are achieved
under mild conditions of either random initialization or an efficiently
computable local initialization. By providing tight convergence guarantees of
the EM algorithm in middle-to-low SNR regimes, we fill the remaining gap in the
literature, and significantly, reveal that in low SNR, EM changes rate,
matching the $n^{-1/4}$ rate of the MLE, a behavior that previous work had been
unable to show.
- Abstract(参考訳): 信号-雑音比(SNR)の全ての条件下で2成分混合線形回帰を学習するためのEMアルゴリズムの収束率について検討する。
我々は、EMの収束挙動を完全に特徴付け、EMアルゴリズムが全てのSNR体制下で最小限のサンプル複雑性を達成することを示す。
特に、SNR が十分に大きいとき、EM の更新は、標準パラメトリック収束率 $\mathcal{O}((d/n)^{1/2})$ の後に $\mathcal{O}(\log(n/d))$ の繰り返しで真のパラメータ $\theta^{*}$ に収束する。
SNR が $\mathcal{O}((d/n)^{1/4})$ を超え、ある定数以下では、EM 反復は $\mathcal{O}({\rm SNR}^{-1} (d/n)^{1/2})$ に収束する。
SNR が $\mathcal{O}((d/n)^{1/4})$ 以下である低 SNR 状態において、EM は $\mathcal{O}((d/n)^{1/4})$ の真のパラメータの近傍に収束し、$\mathcal{O}((n/d)^{1/2})$ の反復に続くことを示す。
特に、これらの結果はランダム初期化または効率的に計算可能な局所初期化という穏やかな条件下で達成される。
中低snr領域におけるemアルゴリズムの厳密な収束保証を提供することで、文献の残りのギャップを埋め、snrの低さにおいては、mleの$n^{-1/4}$レートと一致するem変化率(以前の研究では示せなかった挙動)が明らかになる。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum
Optimization [7.096368428610449]
そこで本研究では,正規写像を用いたリシャッフル法(ノルム点収束法)と呼ばれる新しい最適化アルゴリズムを提案する。
本稿では,提案手法を実証する機械学習の問題点について述べる。
論文 参考訳(メタデータ) (2023-12-02T07:12:00Z) - Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex
Optimization [14.69450310695133]
signSGDの既存の分析は、データが各イテレーションで置き換えられていることを前提にしている。
Signは同じ$O(log(nT)/stnT + log (nT)sqrtn/sT)$を持つことを示す。
実世界のシミュレートされた問題に関する実験を通じて理論的知見を裏付ける。
論文 参考訳(メタデータ) (2023-10-24T16:25:13Z) - 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) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳(メタデータ) (2022-06-16T17:10:57Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳(メタデータ) (2021-11-29T19:26:28Z) - Fundamental limits of over-the-air optimization: Are analog schemes
optimal? [23.71982686172067]
その結果,SNR の低値に対して$sqrtd$ の係数で収束速度が低下することがわかった。
注目すべきは、$Amplitude$$Shift$$Keying$を使用し、ほぼすべてのSNRにおける最適収束率を達成する単純な量子化・変調スキームを示すことである。
論文 参考訳(メタデータ) (2021-09-11T08:50:24Z) - A Stochastic Path-Integrated Differential EstimatoR Expectation
Maximization Algorithm [19.216497414060658]
予測最大化(EM)アルゴリズムは、回帰器と専門家の混在を含む潜在変数モデルにおける推論において重要な要素である。
本稿では,条件予測推定器からの推測のための新しいEMであるtextttSPを提案する。
論文 参考訳(メタデータ) (2020-11-30T15:49:31Z) - Escaping Saddle-Points Faster under Interpolation-like Conditions [19.9471360853892]
過度なパラメータ化の下では、いくつかの標準的な最適化アルゴリズムがサドルポイントを回避し、局所最小化器に収束する。
本稿では、PSGDアルゴリズムの1次オラクル複雑性について論じ、$epsilon$ localminimizerに到達した。
次に、Cubic-Regularized Newton (SCRN)アルゴリズムのアンダーライクな条件を分析し、局所最小化剤アンダーライクな条件に到達するためのオラクルの複雑さが$tildemathcalO (1/epsilon2.5)であることを示す。
論文 参考訳(メタデータ) (2020-09-28T02:15:18Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。