Learning mixtures of linear regressions in subexponential time via Fourier moments

We consider the problem of learning a mixture of linear regressions (MLRs). An MLR is specified by k nonnegative mixing weights p 1, …, p k summing to 1, and k unknown regressors w 1,...,w k ∈ℝ d . A sample from the MLR is drawn by sampling i with probability p i , then outputting (x, y) where y = ⟨ x, w i ⟩ + η, where η∼(0,ς2) for noise rate ς. Mixtures of linear regressions are a popular generative model and have been studied extensively in machine learning and theoretical computer science. However, all previous algorithms for learning the parameters of an MLR require running time and sample complexity scaling exponentially with k.