Efficient Approximation of the CREM Gibbs Measure and the Hardness Threshold

Abstract The continuous random energy model (CREM) is a toy model of disordered systems introduced by Bovier and Kurkova in 2004 based on previous work by Derrida and Spohn in the 80s. In a recent paper by Addario-Berry and Maillard, they raised the following question: what is the threshold $$\beta _G$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>β</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:math> , at which sampling approximately the Gibbs measure at any inverse temperature $$\beta &gt;\beta _G$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>β</mml:mi> <mml:mo>&gt;</mml:mo> <mml:msub> <mml:mi>β</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> </mml:math> becomes algorithmically hard? Here, sampling approximately means that the Kullback–Leibler divergence from the output law of the algorithm to the Gibbs measure is of order o ( N ) with probability approaching 1, as $$N\rightarrow \infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi> </mml:mrow> </mml:math> , and algorithmically hard means that the running time, the numbers of vertices queries by the algorithms, is beyond of polynomial order. The present work shows that when the covariance function A of the CREM is concave, for all $$\beta &gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>β</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , a recursive sampling algorithm on a renormalized tree approximates the Gibbs measure with running time of order $$O(N^{1+\varepsilon })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . For A non-concave, the present work exhibits a threshold $$\beta _G&lt;\infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>β</mml:mi> <mml:mi>G</mml:mi> </mml:msub> <mml:mo>&lt;</mml:mo> <mml:mi>∞</mml:mi> </mml:mrow> </mml:math> such that the following hardness transition occurs: (a) For every $$\beta \le \beta _G$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>β</mml:mi> <mml:mo>≤</mml:mo> <mml:msub> <mml:mi>β</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> </mml:math> , the recursive sampling algorithm approximates the Gibbs measure with a running time of order $$O(N^{1+\varepsilon })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . (b) For every $$\beta &gt;\beta _G$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>β</mml:mi> <mml:mo>&gt;</mml:mo> <mml:msub> <mml:mi>β</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> </mml:math> , a hardness result is established for a large class of algorithms. Namely, for any algorithm from this class that samples the Gibbs measure approximately, there exists $$z&gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>z</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> such that the running time of this algorithm is at least $$e^{zN}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>e</mml:mi> <mml:mrow> <mml:mi>zN</mml:mi> </mml:mrow> </mml:msup> </mml:math> with probability approaching 1. In other words, it is impossible to sample approximately in polynomial-time the Gibbs measure in this regime. Additionally, we provide a lower bound of the free energy of the CREM that could hold its value.