ORIE Colloquium: Ahmed El Alaoui (Cornell SDS)

Description

When is finding a solution easy but sampling a typical one hard?

We consider the questions of sampling and finding solutions in two high-dimensional probability models: the random perceptron model and the mean-field p-spin model. We will discuss an interesting regime of parameters in both problems where it is known how to efficiently return a solution with high probability, but sampling a solution uniformly at random is not possible with a large class of algorithms. We will then identify a property of the probability model which implies that in this regime, there exists an exponentially small set of solutions with the property that any “stable” algorithm is very likely to land in this rare set, provided that it succeeds at finding a solution at all. We then speculate on the relevance of this phenomenon to the good generalization properties of solutions found with efficient algorithms in neural networks.
 

Bio:
Ahmed El Alaoui joined the Department of Statistics and Data Science faculty as an assistant professor in January 2021. He received his Ph.D. in 2018 in electrical engineering and computer sciences from UC Berkeley, advised by Michael I. Jordan. He was afterwards a postdoctoral researcher at Stanford University, hosted by Andrea Montanari. His research interests revolve around high-dimensional phenomena in statistics and probability theory, statistical physics, algorithms, and problems where these areas meet.