TITLE: Towards an Average-case Complexity of High-dimensional Statistics

Abstract: The prototypical high-dimensional statistical estimation problem entails finding a structured signal in noise. These problems have traditionally been studied in isolation, with researchers aiming to develop statistically and computationally efficient algorithms, as well as to try to understand the fundamental limits governing the interplay between statistical and computational cost. In this talk I will describe a line of work that yields average-case reductions directly between a number of central high-dimensional statistics problems, relating two problems by transforming one into the other. It turns out that several problems described by robust formulations can be addressed by one set of techniques, and we will focus on these in the talk. In this direction, we obtain the following average-case lower bounds based on the planted clique conjecture: a statistical-computational gap in robust sparse mean estimation, a detection-recovery gap in community detection, and a universality principle for computational-statistical gaps in sparse mixture estimation. In addition to showing strong computational lower bounds tight against what is achievable by efficient algorithms, the methodology gives insight into the common features shared by different high-dimensional statistics problems with similar computational behavior. Joint work with Matthew Brennan.

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 received his PhD from the Department of EECS at UC Berkeley. His undergraduate degree is from the University of Illinois at Urbana-Champaign. In the last several years his research has focused on the interface between computation and statistics with the aim of understanding the relationship between combinatorial structure and computational tractability of high-dimensional inference.