Paper detail

Efficient approximation of branching random walk Gibbs measures

Disordered systems such as spin glasses have been used extensively as models for high-dimensional random landscapes and studied from the perspective of optimization algorithms. In a recent paper by L. Addario-Berry and the second author, the continuous random energy model (CREM) was proposed as a simple toy model to study the efficiency of such algorithms. The following question was raised in that paper: what is the threshold $β_G$, at which sampling (approximately) from the Gibbs measure at inverse temperature $β$ becomes algorithmically hard? This paper is a first step towards answering this question. We consider the branching random walk, a time-homogeneous version of the continuous random energy model. We show that a simple greedy search on a renormalized tree yields a linear-time algorithm which approximately samples from the Gibbs measure, for every $β< β_c$, the (static) critical point. More precisely, we show that for every $\varepsilon>0$, there exists such an algorithm such that the specific relative entropy between the law sampled by the algorithm and the Gibbs measure of inverse temperature $β$ is less than $\varepsilon$ with high probability. In the supercritical regime $β> β_c$, we provide the following hardness result. Under a mild regularity condition, for every $δ> 0$, there exists $z>0$ such that the running time of any given algorithm approximating the Gibbs measure stochastically dominates a geometric random variable with parameter $e^{-z\sqrt{N}}$ on an event with probability at least $1-δ$.