We consider the problem of reconstructing a hidden assignment of random variables (x_1,…, x_n) sitting on the nodes of a graph, given noisy observations of pairs (x_u, x_v) for every edge (u,v) of the graph. Such problems have been extensively studied when the underlying graph is ‘mean-field’ (e.g., the complete graph, Erdos-Renyi, random regular,…), in which case the existence of a ``possible-but-hard’’ phase where reconstruction is possible but computationally difficult is ubiquitous.

In contrast, the picture is dramatically different when the graph is amenable. I will represent a generic result about the optimality of local algorithms for computing marginals under a somewhat strong model of side information. Next, I will focus on Z_2 synchronization (aka planted Ising model) on the Euclidean lattice with weaker side information, and discuss a renormalization-based procedure for reconstructing the assignment.

Joint work with Andrea Montanari.

In this talk I will consider extreme behavior of the extremal eigenvalues of white Wishart matrices, which play an important role in multivariate analysis. I will focus on the case when the dimension of the feature p is much larger than or comparable to the number of observations n, a common situation in modern data analysis. I will discuss asymptotic approximations for the tail probabilities of the extremal eigenvalues. In addition, I will discuss the construction of an efficient Monte Carlo importance sampling algorithm to estimate the tail probabilities. Simulation results show that our method has the best performance among known approximation approaches, and furthermore provides an efficient and accurate way for evaluating the tail probabilities in practice. Based on joint work with Tiefieng Jiang and Gongjun Xu.

We propose a strategy for improving the existing methods for solving synchronization problems that arise from various computer vision tasks. Specifically, our strategy identifies severely corrupted relative measurements based on cycle consistency information. To the best of our knowledge, this paper provides the first exact recovery guarantees using cycle consistency information. This result holds for a noiseless but corrupted setting as long as the ratio of corrupted cycles per edge is sufficiently small. It further guarantees linear convergence to the desired solution. We also establish stability of the proposed algorithm to sub-Gaussian noise.

How many critical points does a smooth random function on a high-dimensional space typically have at a given height? how are their distances distributed? what is the volume or geometry of the level sets? can we design efficient optimization algorithms for the random function? For the spherical spin glass models, those questions are closely related to the structure of the Gibbs measures, which have been extensively studied in physics since the 70s.

I will start with an overview of the celebrated Parisi formula and ultrametricity property. I will then describe an alternative method to analyze the Gibbs measure using critical points, in the setting of the pure spherical models. Finally, I will explain how the latter can be extended to all spherical models, using another (soft) geometric approach, while at the same time making rigorous and generalizing the famous Thouless-Anderson-Palmer approach from physics.