Georgia Institute of Technology College of Sciences

We consider the task of estimating a rank-one matrix from noisy observations. Models that fall in this framework include community detection and spiked Wigner models. In this talk, I will discuss pseudo-maximum likelihood theory for such inference problems. We provide a variational formula for the asymptotic maximum pseudo-likelihood and characterize the asymptotic performance of pseudo maximum likelihood estimators. We will also discuss the implications of these findings to least squares estimators. Our approach uses the recent connections between statistical inference and statistical physics, and in particular the connection between the maximum likelihood and the ground state of a modified spin glass.

Based on joint work with Curtis Grant and Aukosh Jagannath.

A classic problem in probability theory and combinatorics is to estimate the probability that the random graph G(n,p) contains no triangles.  This problem can be viewed as a question in "non-linear large deviations".   The asymptotics of the logarithm of this probability (and related lower tail probabilities) are known in two distinct regimes.  When p>> 1/\sqrt{n}, at this level of accuracy the probability matches that of G(n,p) being bipartite; and when p<< 1/\sqrt{n}, Janson's Inequality gives the asymptotics of the log.  I will discuss a new approach to estimating this probability in the "critical regime": when p = \Theta(1/\sqrt{n}).  The approach uses ideas from statistical physics and algorithms and gives information about the typical structure of graphs drawn from the corresponding conditional distribution.  Based on joint work with Matthew Jenssen, Aditya Potukuchi, and Michael Simkin.

Motivated by applications to group synchronization and quadratic assignment on random data, we study a general problem of Bayesian inference of an unknown “signal” belonging to a high-dimensional compact group, given noisy pairwise observations of a featurization of this signal.

We establish a quantitative comparison between the signal-observation mutual information in any such problem with that in a simpler model with linear observations, using interpolation methods. For group synchronization, our result proves a replica formula for the asymptotic mutual information and Bayes-optimal mean-squared error. Via analyses of this replica formula, we show that the conjectural phase transition threshold for computationally-efficient weak recovery of the signal is determined by a classification of the real-irreducible components of the observed group representation(s), and we fully characterize the information-theoretic limits of estimation in the example of angular/phase synchronization over SO(2)/U(1). For quadratic assignment, we study observations given by a kernel matrix of pairwise similarities and a randomly permuted and noisy counterpart, and we show in a bounded signal-to-noise regime that the asymptotic mutual information coincides with that in a Bayesian spiked model with i.i.d. signal prior.

This is based on joint work with Kaylee Yang and Zhou Fan.