2023/08/01 by Fu-Hsuan Ho, Ho, Fu-Hsuan
Mathematics · Physics and Astronomy · #60J80 #60K35 #68Q17 #82D30 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.2308.00857
openalex publication_date 2023/08/01 · openalex created_date 2023/08/19 · openalex updated_date 2026/07/28
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 βG, at which sampling approximately the Gibbs measure at any inverse temperature β>βG 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→∞, 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 β>0, a recursive sampling algorithm on a renormalized tree approximates the Gibbs measure with running time of order O(N1+ε). For A non-concave, the present work exhibits a threshold βG<∞ such that the following hardness transition occurs: a) For every β≤ βG, the recursive sampling algorithm approximates the Gibbs measure with running time of order O(N1+ε). b) For every β>βG, 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>0 such that the running time of this algorithm is at least ezN 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 own value.