Alternating Minimization Converges Super-Linearly for Mixed Linear Regression
This work addresses a theoretical gap for practitioners in machine learning by explaining the faster empirical convergence of AM compared to gradient-based methods, though it is incremental as it focuses on the special case of two linear regressions.
The paper tackles the problem of solving mixed linear regression with unlabeled observations from multiple linear models, showing that Alternating Minimization (AM) achieves a super-linear convergence rate in certain regimes, requiring only O(log log(1/ε)) iterations to recover regressors with error ε.
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 is to learn the linear regressors from the observations. Classically, Alternating Minimization (AM) (which is a variant of Expectation Maximization (EM)) is used to solve this problem. AM iteratively alternates between the estimation of labels and solving the regression problems with the estimated labels. Empirically, it is observed that, for a large variety of non-convex problems including mixed linear regression, AM converges at a much faster rate compared to gradient based algorithms. However, the existing theory suggests similar rate of convergence for AM and gradient based methods, failing to capture this empirical behavior. In this paper, we close this gap between theory and practice for the special case of a mixture of $2$ linear regressions. We show that, provided initialized properly, AM enjoys a \emph{super-linear} rate of convergence in certain parameter regimes. To the best of our knowledge, this is the first work that theoretically establishes such rate for AM. Hence, if we want to recover the unknown regressors upto an error (in $\ell_2$ norm) of $ε$, AM only takes $\mathcal{O}(\log \log (1/ε))$ iterations. Furthermore, we compare AM with a gradient based heuristic algorithm empirically and show that AM dominates in iteration complexity as well as wall-clock time.