Over the past few years, insights from computer science, statistical physics, information theory, and statistics have revealed phase transitions in a wide array of high-dimensional statistical problems. At these transitions, where the observation becomes too noisy, it suddenly becomes impossible to reliably learn the ground truth structure. Such problems include community detection in networks, clustering with mixtures of Gaussians, and noisy matrix factorization. Many of these results first appeared as conjectures in statistical physics, based on compelling but non-rigorous calculations. The challenge of making them rigorous has led to an exciting interdisciplinary effort between computer scientists, physicists, mathematicians, and statisticians.

This talk will present two recent results on phase transitions. One is an “All-or-Nothing” phase transition for recovering a sparse vector from independent linear Gaussian measurements. We show that the optimal accuracy rate jumps from 0 to 1 at a critical sample size. The other is a phase transition for recovering a hidden matching in a weighted, n by n bipartite graph, motivated by particle tracking applications. By assuming every edge weight is independently and exponentially distributed with rate lambda if the edge is on the hidden matching and with rate 1/n otherwise, we show that the accuracy rate of the maximum likelihood estimator (which corresponds to the minimum weighted matching) is 1 if and only if λ≥4. For analysis, we use first/second-moment methods, local weak convergence (objective method), and phase space method in non-linear ordinary differential equations.


Jiaming Xu is an assistant professor in the Fuqua School of Business at Duke Universit. He was an assistant professor in the Krannert School of Management at Purdue University from August 2016 to June 2018, a research fellow with the Simons Institute for the Theory of Computing, UC Berkeley from January 2016 to June 2016, and a postdoctoral fellow with the Statistics Department, The Wharton School, University of Pennsylvania from January 2015 to December 2015. He received a Ph.D. degree from UIUC in 2014 under the supervision of Prof. Bruce Hajek, an M.S. degree from UT-Austin in 2011, and a B.E. degree from Tsinghua University in 2009, all in Electrical and Computer Engineering. His research interests include network science, high-dimensional statistics, information theory, convex and non-convex optimization, queueing theory, and game theory.