A high-dimensional probability lens on estimation, testing, and optimization.

Speaker: Ahmed El Alaoui

Location: 60 Fifth Avenue Open Space

Date: Feb. 11, 2020, 1:50 p.m.

Estimating a faint signal buried in large amounts of noise, or merely telling whether it is present in the data is a central task in many experimental sciences. In modern high-dimensional applications, this requires the deployment of inference algorithms that are efficient, scalable and produce reliable answers. On the theoretical front however, the inherent tension between statistical efficiency and algorithmic tractability in such problems is still poorly understood.    

In this talk, I will present two cases where at the core of this tradeoff lies a question in high-dimensional probability. I will first discuss the problem of estimating and testing the presence of a low-rank structure buried inside a large random matrix. Next, I will consider the problem of computing the global maximum of a highly non-convex random function, known as the mixed p-spin Hamiltonian, solely based on gradient information. In both cases, I will report on the fundamental feasibility frontiers of these tasks and present efficient algorithms achieving them.