Title：The all-or-nothing phenomenon in sparse estimation
Speaker： Jonathan Niles-Weed New York University
Time： 2021-05-12 09:00-2021-05-12 10:30
Venue：online

Abstract:

We explore a sharp phase transition known as the "all-or-nothing" phenomenon in estimation problems. This phenomenon arises when there exists a critical signal to noise ratio (SNR) such that below this threshold it is impossible to achieve any positive correlation with the hidden signal, whereas above this threshold it is possible to achieve almost perfect correlation with the hidden signal. This phenomenon has been observed in a few different models and settings, but with no unified explanation. We give a sharp characterization of this phenomenon in the presence of Gaussian noise and give general conditions under which it holds. As a corollary, we obtain the all-or-nothing phenomenon for the sparse tensor PCA theorem, Bernoulli group testing, and the planted Gaussian perceptron problem. Joint work with Ilias Zadik.

Short Bio:

I am an Assistant Professor of Mathematics and Data Science at the Courant Institute of Mathematical Sciences and the Center for Data Science at NYU, where I am a core member of the Math and Data group. I study statistics, probability, and the mathematics of data science. I am especially interested in statistical and computational problems arising from data with geometric structure, and my recent work focuses on optimal transport. I received my Ph.D. in Mathematics and Statistics from MIT, under the supervision of Philippe Rigollet.