"Fast Algorithms and (Other) Minimax Optimal Algorithms for Mixed Regression"
March 28, 2016
Duncan Hall 1064
Department of Electrical and Computer Engineering
The University of Texas at Austin
Mixture models represent the superposition of statistical processes, and are natural in machine learning and statistics. In mixed regression, the relationship between input and output is given by one of possibly several different (noisy) linear functions. Thus the solution encodes a combinatorial selection problem, and hence computing it is difficult in the worst case.
We give a (tractable) convex optimization formulation, and provide matching minimax lower bounds, showing that for random design, our algorithm is information-theoretically optimal. We show that while in the high-SNR regime we recover parametric learning rates, this behavior is fundamentally different in the low-SNR regime. We also give general conditions for linear convergence of an EM-like (and hence fast) algorithm for latent-variable problems in high dimensions, and show, in particular, that this applies to sparse (or low-rank) mixed regression.
Our results represent what is, as far as we know, the only tractable algorithm guaranteeing successful recovery with tight bounds on recovery errors and sample complexity.
Shell Lectures Series are made possible through the generous support of the Shell Oil Company.