Abstract:  Motivated by applications such as discovering strong ties in social networks and assembling genome subsequences in biology, we study the problem of recovering a hidden nearest neighbor (NN) graph in a random complete graph, whose edge weights are independent and distributed according to P for edges in the hidden NN graph and Q otherwise. This model incorporates the celebrated Watts-Strogatz small-world graph as a special case. For both the exact and almost exact recovery problems, we characterize the sharp information-theoretic limits, which are governed by two divergence measures between P and Q. I will highlight the key proof strategies and provide some intuition behind the sharp thresholds, with the help of a lot of pictures.

Bio:  Dana Yang is a Postdoctoral Researcher hosted by Dr. Jiaming Xu at the Fuqua School of Business, Duke University. Dana received her PhD in Statistics and Data Science in 2019 from Yale University, where she was co-advised by Dr. John Lafferty, Dr. David Pollard, and Dr. Yihong Wu. She received her MA in Statistics from Yale University in 2014, and her BS in Mathematics from Tsinghua University in 2013. Her research interest is in the broad area of high-dimensional statistics and machine learning, including random network analysis, optimality analysis, Bayesian analysis, oracle inequalities, nonparametric estimation, convergence analysis, and ethics and safety in machine learning.