Alternating Minimization for Mixed Linear Regression
Mixed linear regression involves the recovery of two (or more) unknown vectors from unlabeled linear measurements; that is, where each sample comes from exactly one of the vectors, but we do not know which one. It is a classic problem, and the natural and empirically most popular approach to its solution has been the EM algorithm. As in other settings, this is prone to bad local minima; however, each iteration is very fast (alternating between guessing labels, and solving with those labels). In this paper we provide a new initialization procedure for EM, based on finding the leading two eigenvectors of an appropriate matrix. We then show that with this, a re-sampled version of the EM algorithm provably converges to the correct vectors, under natural assumptions on the sampling distribution, and with nearly optimal (unimprovable) sample complexity. This provides not only the first characterization of EM's performance, but also much lower sample complexity as compared to both standard (randomly initialized) EM, and other methods for this problem.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
We consider the problem of solving mixed random linear equations with $k$ components. This is the noiseless setting of mixed linear regression. The goal is to estimate multiple linear models from mixed samples in the cas…
Tensor DecompositionAlternating Minimization Converges Super-Linearly for Mixed Linear Regression
We address the problem of solving mixed random linear equations. We have unlabeled observations coming from multiple linear regressions, and each observation corresponds to exactly one of the regression models. The goal …
regressionAgnostic Learning of Mixed Linear Regressions with EM and AM Algorithms
Mixed linear regression is a well-studied problem in parametric statistics and machine learning. Given a set of samples, tuples of covariates and labels, the task of mixed linear regression is to find a small list of lin…
regressionAsymptotic Dynamics of Alternating Minimization for Bilinear Regression
This study investigates the dynamics of alternating minimization applied to a bilinear regression task with normally distributed covariates, under the asymptotic system size limit where the number of parameters and obser…
regressionAn Improved Analysis of Alternating Minimization for Structured Multi-Response Regression
Multi-response linear models aggregate a set of vanilla linear models by assuming correlated noise across them, which has an unknown covariance structure. To find the coefficient vector, estimators with a joint approxima…
regression