Rice Header
CAAM Header

Shell Lecture Series - 3/28, 3:00PM, Duncan Hall 1064

Constantine Caramanis

Department of Electrical and Computer Engineering
The University of Texas at Austin

"Fast Algorithms and (Other) Minimax Optimal Algorithms for Mixed Regression"

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.

Department of Computational and Applied Mathematics
6100 Main MS-134   Houston, TX 77005   713.348.4805

Rice University   |   School of Engineering   |   Pearlman Memorial Fund   |   Weiser Memorial Fund for Student Excellence   |   Contact Webmaster