Spectral Experts for Estimating Mixtures of Linear Regressions

Abstract

Discriminative latent-variable models are typically learned using EM or gradient-based optimization, which suffer from local optima. In this paper, we develop a new computationally efficient and provably consistent estimator for a mixture of linear regressions, a simple instance of a discriminative latent-variable model. Our approach relies on a low-rank linear regression to recover a symmetric tensor, which can be factorized into the parameters using a tensor power method. We prove rates of convergence for our estimator and provide an empirical evaluation illustrating its strengths relative to local optimization (EM).

Accepted at ICML 2013. Includes supplementary material

References in corpus (2)

• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Identifiability and Unmixing of Latent Parse Trees

Cited by in corpus (29)

• Nonparametric modal regression
• Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing
• Alternating Minimization for Mixed Linear Regression
• 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
• Learning Mixtures of Linear Classifiers
• A Tensor-EM Method for Large-Scale Latent Class Analysis with Binary Responses
• A Convex Program for Mixed Linear Regression with a Recovery Guarantee for Well-Separated Data
• Estimation, Confidence Intervals, and Large-Scale Hypotheses Testing for High-Dimensional Mixed Linear Regression
• Alternating Minimization Converges Super-Linearly for Mixed Linear Regression
• Estimation from Indirect Supervision with Linear Moments
• Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression
• Robust Meta-learning for Mixed Linear Regression with Small Batches
• Iterative Least Trimmed Squares for Mixed Linear Regression
• Sample Complexity of Learning Mixtures of Sparse Linear Regressions
• Neural Mixture Distributional Regression
• 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
• Distributed Linear Model Clustering over Networks: A Tree-Based Fused-Lasso ADMM Approach
• Convergence of Parameter Estimates for Regularized Mixed Linear Regression Models
• Global Convergence of Least Squares EM for Demixing Two Log-Concave Densities
• Meta-learning for mixed linear regression
• Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
• Estimating Mixture Models via Mixtures of Polynomials
• Recovery of sparse linear classifiers from mixture of responses
• Learning Mixtures of Low-Rank Models
• Support Recovery of Sparse Signals from a Mixture of Linear Measurements
• A Wasserstein Minimax Framework for Mixed Linear Regression