CSP Seminar, David Gamarnik (MIT), Thursday, 3/14, 4:00pm, Room 1005 EECS

Communications and Signal Processing Seminar (CSP)
David Gamarnik, PhD

Professor of Operations Research at the Operations Research and Statistics Group

Sloan School of Management of Massachusetts Institute of Technology

“Algorithms and Algorithmic Obstacles in High-Dimensional Regression“

Abstract: Many optimization problems arising in studying of high-dimensional inference problems exhibit an apparent gap between the optimal values which can be estimated by non-constructive means, and the best values achievable by fast (polynomial time) algorithms. Recently it became apparent that a potential and in some cases a provable obstruction for designing algorithms bridging this gap is a phase transition in the geometry of nearly optimal solutions, in particular the presence of a certain Overlap Gap Property (OGP). In this talk we will discuss this property in the context of sparse high dimensional linear regression problem. We show that, on the one hand, in the sampling regime where the known fast methods for this problem are effective, including LASSO, Basis Pursuit, Orthogonal Matching Pursuit, the space of solutions exhibits a monotonicity with respect to the proximity to the ground truth regression vector and no local optimums exist apart from the ground truth. On the other hand, once the sampling number is asymptotically in the regime where the known methods fail, we show that the monotonicity is lost, and the model exhibits an OGP. In the context of the regression problem this means every solution exhibiting a small mean squared error is either fairly close to the ground truth or is very far from it, with no middle ground. Joint work with Ilias Zadik (MIT).

Biography: David Gamarnik is a 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 recipient of the Erlang Prize and the Best Publication Award from the Applied Probability Society of INFORMS, and he was a finalist for Franz Edelman Prize competition of INFORMS. He serves and served on the editorial boards of several journals including Operations Research, Mathematics of Operations Research, Annals of Applied Probability, Queueing Systems and Stochastic Systems.

https://www.eecs.umich.edu/eecs/etc/events/showevent.cgi?5071