Mixture models represent the superposition of statistical processes, and are natural in machine learning and statistics. Despite the prevalence and importance of mixture models, little is known in the realm of efficient algorithms with strong statistical guarantees. The Expectation-Minimization (EM) approach is perhaps the most popular, yet save for the Gaussian mixture clustering problem, few guarantees exist. For mixed regression in the noiseless setting, in particular, only recently has an EM-like algorithm been able to provide near-tight guarantees. In the noisy setting, tensor approaches have recently succeeded in providing a tractable and statistically consistent approach, but require a sample complexity much higher than the information-theoretic limits. We consider the mixed regression problem with two components, under adversarial and stochastic noise. Using a lifting to a higher dimensional space, we give a convex optimization formulation that provably recovers the true solution, with near-optimal sample complexity and error bounds. In the noiseless setting, our results remove the extra log factor from recent (and best-to-date) work, thus achieving exact recovery with order-wise as many samples as the degrees of freedom. In the general setting with noise, our results represent the first (and currently only known) tractable algorithm guaranteeing successful recovery with tight bounds on sample complexity and recovery errors.

通过凸优化公式，我们解决了双成分混合回归问题，提供了对同时存在随机和对抗噪声下真实解的可行恢复方案，给出了任意噪声和随机噪声下的上限和匹配的极小值下限，表明我们的算法在特定假设下是信息 量论上最优的，这些结果是首个具有恢复成功保障和恢复误差及样本复杂度紧密界限的可行算法。

混合回归的凸问题形式：两个成分的极小极大优化率