EM Converges for a Mixture of Many Linear Regressions
EM Converges for a Mixture of Many Linear Regressions
复制标题
DOI：
--
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Jeongyeol Kwon;C. Caramanis
中科院分区：
文献类型：
--
作者：
Jeongyeol Kwon;C. Caramanis
我们研究了具有任意数量 $k$ 分量的线性回归混合的期望最大化 (EM) 算法的收敛性。我们证明，只要信噪比 (SNR) 为 $\tilde{\Omega}(k)$，良好初始化的 EM 就会收敛到真实的回归参数。 $k \geq 3$ 的先前结果仅在无噪声设置（即 SNR 无限大）下建立了局部收敛。我们的结果将范围扩大到有噪声的环境，值得注意的是，我们建立了一个独立于回归参数的范数（或成对距离）的统计错误率。特别是，我们的结果意味着精确恢复为 $\sigma \rightarrow 0$，这与大多数先前的 EM 局部收敛结果相反，其中统计误差随参数范数缩放。可以应用标准矩方法来保证我们处于局部收敛保证适用的区域。
We study the convergence of the Expectation-Maximization (EM) algorithm for mixtures of linear regressions with an arbitrary number $k$ of components. We show that as long as signal-to-noise ratio (SNR) is $\tilde{\Omega}(k)$, well-initialized EM converges to the true regression parameters. Previous results for $k \geq 3$ have only established local convergence for the noiseless setting, i.e., where SNR is infinitely large. Our results enlarge the scope to the environment with noises, and notably, we establish a statistical error rate that is independent of the norm (or pairwise distance) of the regression parameters. In particular, our results imply exact recovery as $\sigma \rightarrow 0$, in contrast to most previous local convergence results for EM, where the statistical error scaled with the norm of parameters. Standard moment-method approaches may be applied to guarantee we are in the region where our local convergence guarantees apply.