Random high-dimensional cost functions and random probability distributions arise in a number of applied fields. For instance, in high-dimensional statistics, an M-estimator is the solution of a random optimization problem (the randomness being related to the data distribution). In statistical physics, the Gibbs measure of a disordered physical system is a random probability measure (whose randomness is related to frozen atom positions).
In these problems, one is often interested in algorithms that can find near optima or sample from the given distribution efficiently. I will discuss a simple-to-describe and yet-rich example known as Z2 synchronization. This is closely related to the celebrated Sherrington-Kirkpatrick model of mean field spin glasses.
I will present recently developed algorithms to solve the optimization, inference and sampling problems, as well as rigorous evidence suggesting that these algorithms are optimal for this model and in a broader context.