Advances in Algorithms for Sampling, Optimization and Inference in Disordered Systems

This thesis focuses on the development of advanced algorithmic techniques, primarily Markov Chain Monte Carlo (MCMC) methods, and message passing algorithms, to tackle high-dimensional optimization and inference problems. The algorithms used have a probabilistic inspiration, being based on constructing a Gibbs measure for the problem and then analyzing it. We study four separate applications: graph alignment, integer traffic assignment, sampling the posterior of a neural network, and an instance of rank-one matrix factorization with complex variables. In each of these cases, carrying out inference or optimization is NP-hard. We consider random or 'disordered' instances, which allow us to exploit the properties of typical realizations and tailor the algorithms accordingly.

Integer traffic assignment is an optimization problem consisting of routing multiple interacting paths over a graph. Each path has a fixed origin and destination and represents a commuter moving through a city. If many commuters pass through the same road (edge), it becomes congested. The goal of the optimization is to minimize the overall congestion in the graph. From convex relaxation to probabilistic inspired methods, we develop and compare several optimization algorithms. We also characterize the asymptotic properties of the problem in the large number of paths limit in the case of random regular graphs and random origins and destinations.

Bayesian learning is an alternative learning paradigm to empirical risk minimization (ERM). In the Bayesian approach, one wishes to sample from the posterior $P(W|D)$ of the weights $W$ of the neural network given the training set $D$. Unlike ERM, Bayesian analysis provides confidence estimates for the network's predictions. We design a Gibbs sampler that iteratively samples blocks of variables from their conditional distribution. The sampler is competitive with other common MCMCs. We also develop a criterion to characterize when the MCMC has thermalized, in the case of artificial data.

Indicating with $A,B$ the adjacency matrices of two graphs, graph alignment is an optimization problem consisting of finding the vertex permutation $\pi$ that maximizes $\sum_{i,j} A_{ij}B_{\pi(i)\pi(j)}$, the number of common edges in two graphs. We study the case in which the graphs are sparse and come from a correlated ensemble. We develop a message passing algorithm to align the graphs based on an approximation of the posterior where only local information is retained.

The XY model is a classical spin glass characterized by spin variables being two-dimensional unit norm vectors. We consider the case where the coupling matrix has a hidden rank-one component that must be retrieved. Using the approximate message passing and approximate survey propagation algorithms we find the phase diagram of the model.