Northeastern University
Sign Up

Title: Computational and Statistical Limits of High Dimensional Inference

 

Abstract: Modern machine learning methods require the statistically and computationally efficient use of large "high-dimensional" datasets. The field of high dimensional inference, at the intersection of mathematics, computer science, and statistics, aims to exactly quantify the power and limitations of high dimensional datasets. Albeit an intense area of theoretical research, the exact fundamental limits of (computationally constrained or not) estimators in even simple high dimensional inference remain elusive. In this talk, I will discuss two new phase transition results in the context of high dimensional linear regression (HDLR). The first is a sharp phase transition taking place at the information-theoretic limit of the model, called the "all-or-nothing" phenomenon. The second concerns the fact that in HDLR all known computationally efficient estimators perform significantly worse than computationally unconstrained ones. This is a ubiquitous and not well-understood phenomenon in high dimensional inference, called the presence of a "computational-statistical gap". We establish a geometric Overlap Gap Property (OGP) phase transition for the model which takes place exactly at the point where all known computationally efficient estimators begin to fail. OGP originates in spin glass theory and is known to suggest algorithmic hardness when it appears. Our correspondence provides evidence that the computational-statistical gap of HDLR is of fundamental nature. 

 

 

Short Bio: Ilias Zadik is a CDS Moore-Sloan postdoctoral fellow at the Center for Data Science of NYU. He received his Ph.D. in September 2019 from the Operations Research Center at MIT, under the supervision of David Gamarnik. Prior to his Ph.D. studies at MIT, he completed a Master of Advanced Studies in Mathematics (Part III of the Mathematical Tripos) at the University of Cambridge and a BA in Mathematics at the University of Athens.

Event Details

0 people are interested in this event


Please email a.mcguinness@northeastern.edu for hte Zoom password

User Activity

No recent activity