IT-Forum and ISL Colloquium SPECIAL SEMINAR: "Towards an Average-case Complexity of High-dimensional Statistics"

Towards an Average-case Complexity of High-dimensional Statistics
Friday, November 15, 2019 - 1:15pm
Packard 202
Guy Bresler (MIT)
Abstract / Description: 

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.

Special joint seminar:  IT-Forum and The Information Systems Laboratory Colloquium (ISLC)


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.