In this talk I will describe some simple average-case reduction techniques and use these techniques to connect several statistical problems with widely varying structures. These reduction techniques transform the probability distribution defining a problem in an algorithmically efficient way while preserving the strength of the underlying signal, thereby transferring the computational phase transitions from one problem to another. We'll focus especially on the mixtures of linear regressions problem, and show how this supervised learning problem over continuous variables can be precisely related to the planted clique problem, a combinatorial unsupervised learning problem. Along the way we'll see a method for turning positive correlations into negative correlations amongst a subset of variables without knowing which subset is the correlated one, as well as a clean but non-obvious way to turn a supervised learning problem into an unsupervised one. The talk is based on joint work with Matthew Brennan (https://arxiv.org/abs/2005.08099).
Bio: Guy Bresler is an associate professor in the Department of Electrical Engineering and Computer Science at MIT, and a member of LIDS and IDSS. Previously, he was a postdoc at MIT and before that completed his PhD in the Department of EECS at UC Berkeley. His undergraduate degree is from the University of Illinois at Urbana-Champaign. A major focus of his research is on the computational complexity of statistical inference, a direction that combines his interests in information theory, probability, and computation.