Return to Colloquia & Seminar listing
Algorithmic Challenges in High-Dimensional Inference Models: Insights from the Statistical Physics
Mathematics of Data & Decisions| Speaker: | David Gamarnik, MIT Sloan School of Management |
| Related Webpage: | http://www.mit.edu/~gamarnik/home.html |
| Location: | 1147 MSB |
| Start time: | Tue, Mar 3 2020, 4:10PM |
Inference problems arising in modern day statistics, machine learning and artificial intelligence fields often involve models with exploding dimensions, giving rise to a multitude of computational challenges. Many such problems "infamously" resist the construction of tractable inference algorithms, and thus are possibly fundamentally non-solvable by fast computational methods. A particularly intriguing form of such intractability is the so-called computational vs information theoretic gap, where effective inference is achievable by some form of exhaustive search type computational procedure, but fast computational methods are not known and conjectured not to exist. A great deal of insight into the mysterious nature of this gap has emerged from the field of statistical physics, where the computational difficulty is linked to a phase transition phenomena of the solution space topology. We will discuss one such phase transition obstruction, which takes the form of the Overlap Gap Property: the property referring to the topological disconnectivity (gaps) of the set of valid solutions.
This is a joint MADDD-Statistics seminar. Refreshments will be served in 1147 MSB from 3:30pm.