Alternating Minimization for Mixed Linear Regression
arXiv:1310.3745
Abstract
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.
References in corpus (1)
Cited by in corpus (34)
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Non-convex Optimization for Machine Learning
- Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
- Robust Federated Learning in a Heterogeneous Environment
- Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
- Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
- Reducibility and Statistical-Computational Gaps from Secret Leakage
- Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation
- Solving Almost all Systems of Random Quadratic Equations
- Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
- Estimation, Confidence Intervals, and Large-Scale Hypotheses Testing for High-Dimensional Mixed Linear Regression
- Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression
- Alternating Minimization Converges Super-Linearly for Mixed Linear Regression
- Sample Complexity of Learning Mixtures of Sparse Linear Regressions
- Iterative Least Trimmed Squares for Mixed Linear Regression
- Provable Sparse Tensor Decomposition
- Inference in Multi-Layer Networks with Matrix-Valued Unknowns
- Efficient Algorithms for Estimating the Parameters of Mixed Linear Regression Models
- On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression
- Parameter Estimation in Gaussian Mixture Models with Malicious Noise, without Balanced Mixing Coefficients
- Tensor Graphical Model: Non-convex Optimization and Statistical Inference
- Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms
- Alternating Estimation for Structured High-Dimensional Multi-Response Models
- Convergence of Parameter Estimates for Regularized Mixed Linear Regression Models
- Learning Combinations of Sigmoids Through Gradient Estimation
- Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
- On InstaHide, Phase Retrieval, and Sparse Matrix Factorization
- Uniform Consistency in Nonparametric Mixture Models
- Learning Mixtures of Graphs from Epidemic Cascades
- High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees
- Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective
- Learning Mixtures of Sparse Linear Regressions Using Sparse Graph Codes
- Learning Mixtures of Low-Rank Models
- A Wasserstein Minimax Framework for Mixed Linear Regression