Speaker: Ahmed El Alaoui
Time: 4pm – 5pm
Location: 60 5th Avenue, 7th Floor, CDS Open Space
Abstract:
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.
The speaker will present two cases where at the core of this tradeoff lies a question in high-dimensional probability. He will discuss the problem of estimating and testing the presence of a low-rank structure buried inside a large random matrix. Next, he 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, he will report on the fundamental feasibility frontiers of these tasks and present efficient algorithms achieving them.