Efficient approximation of branching random walk Gibbs measures

Abstract

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 ${\beta }_G$, at which sampling (approximately) from the Gibbs measure at inverse temperature $\beta$ 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 $\beta <{\beta }_c$, the (static) critical point. More precisely, we show that for every $\epsilon >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 $\beta$ is less than $\epsilon$ with high probability. In the supercritical regime $\beta >{\beta }_c$, we provide the following hardness result. Under a mild regularity condition, for every $\delta >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-\delta$.

arXiv commentJournal version, minor corrections, Sec 1.1 in v1 moved to Sec 1.2 in v2 and thoroughly rewritten. 19 pages, 1 figure

References in corpus (10)

• Convergence in law of the minimum of a branching random walk
• Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Spectral gap estimates in mean field spin glasses
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Glassy nature of the hard phase in inference problems
• On the Spectral Gap of Spherical Spin Glass Dynamics
• Search cost for a nearly optimal path in a binary tree
• Spectral gap critical exponent for Glauber dynamics of hierarchical spin models
• On the trajectory of an individual chosen according to supercritical Gibbs measure in the branching random walk