論文の概要: 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変化率(以前の研究では示せなかった挙動)が明らかになる。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization [0.7373617024876725]
Lipschitz-of-$nabla f$
$mathcalS_k|p$。
$mathcalS_k|p$。
$nabla f$.
$mathcalS_k|p$。
論文 参考訳（メタデータ） (2024-09-28T18:16:32Z) - Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。
我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction [16.82220229840038]
それぞれ$mathcalO(d1/2T-1/2 + dn-1/2)$と$mathcalO(d1/4T-1/4)$の収束率を改善する2つの新しいアルゴリズムを導入する。
提案手法の有効性を検証した数値実験を行った。
論文 参考訳（メタデータ） (2024-06-01T16:38:43Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52: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) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。