David Gamarnik, Ph.D.

MIT

TITLE: High-dimensional statistics and the algorithmic intractability.

ABSTRACT: Conducting statistical inference often amounts to solving optimization problems involving many dimensions. While many such optimization problems admit scalable computational procedures, other problems resisted multi-year efforts. Examples include sparse high dimensional linear regression, largest independent set problem in a random graph, sparse principal component analysis, stochastic block model and many others. Despite the fact that these problems exhibit an apparent algorithmic hardness, no universally accepted formal theory of such hardness is available.

In this talk we will describe a new approach based on the solution space geometry, called the Overlap Gap Property (OGP). We will discuss how this property a) emerges in most models known to exhibit an apparent algorithmic hardness; b) is consistent with the hardness/tractability phase transition for many models analyzed to the day; and, importantly, c) allows to mathematically rigorously rule out a large class of algorithms as potential contenders, specifically the algorithms that exhibit the input stability (insensitivity).

BIO: David Gamarnik is a Nanyang Technological University Professor of Operations Research at the Operations Research and Statistics Group, Sloan School of Management of Massachusetts Institute of Technology. He received B.A. in mathematics from New York University in 1993 and Ph.D. in Operations Research from MIT in 1998. Since then he was a research staff member of IBM T.J. Watson Research Center, before joining MIT in 2005.

His research interests include probability, theory of random graphs, optimization and algorithms, statistics and machine learning, stochastic processes and queueing theory. He is a fellow of the INFORMS and the American Mathematical Society. He is a recipient of the Erlang Prize and the Best Publication Award from the Applied Probability Society of INFORMS, and was a Laureate of Franz Edelman Prize competition of INFORMS. In the past he served as an area editor of the Operations Research journal, and as an associate editor of the Mathematics of Operations Research, the Annals of Applied Probability, Queueing Systems and the Stochastic Systems journals.