论文标题
关于学习两组分组的最小算法的最小算法最佳性能混合线性回归
On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression
论文作者
论文摘要
我们研究了所有信噪比（SNR）的EM算法的收敛速率，用于学习两个组件混合线性回归。我们解决了一个长期存在的问题，即最近的许多结果试图解决：我们完全表征了EM的收敛行为，并表明EM算法在所有SNR制度下都实现了最小的最佳样品复杂性。特别是，当SNR足够大时，EM更新会收敛到True参数$θ^{*} $，以标准参数收敛速率$ \ MATHCAL {O}（（（d/n）^{1/2}）$ $ \ \ \ \ \ \ \ \ \ \ \ \ m nathcal {o}（o}（o）{o}（n/d log（n/d/d d））$ iTerations。在SNR高于$ \ MATHCAL {O}（（（d/n）^{1/4}）$且低于某些常数的状态下$ \ MATHCAL {O}（{\ rm snr}^{ - 2} \ log（n/d））$。在低snR式中，SNR低于$ \ MATHCAL {O}（（（d/n）^{1/4}）$，我们表明EM收敛到$ \ MATHCAL {O}（（（d/n）^{1/4} {1/4}）$ ney true参数neker of true参数之后值得注意的是，这些结果是在随机初始化或有效计算的局部初始化的温和条件下实现的。通过在中低SNR制度中提供EM算法的紧密收敛保证，我们填补了文献中的剩余空白，并且显着地表明，在低SNR中，EM变化速率，与MLE的$ N^{ - 1/4} $匹配，MLE的率是MEL的率，这是一种先前工作无法显示的行为。
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 $θ^{*}$ 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.
