BLISS Seminar: Towards an Average-case Complexity of High-dimensional Statistics

Seminar | November 13 | 3-4 p.m. | 400 Cory Hall

 Guy Bresler, MIT

 Electrical Engineering and Computer Sciences (EECS)

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.