In the existing literature, the hard phase is located using the simplest (replica symmetric) version of the message passing algorithms that ignores the fact that from the physics point of view this hard phase is glassy. Our contribution is the development of the approximate survey propagation (ASP) algorithm that takes glassines into account, in particular by breaking of the replica symmetry. We show that the large size limit of ASP algorithm leads to the one-step-replica symmetry breaking fixed-point equations well known from the context of spin glasses. Using this setting, we characterize the glassy property of the hard region, measuring the entropy of the metastable glassy states, called complexity. We show that this glassiness extends even outside of the hard phase thus strongly suggesting that sampling based algorithms such as Monte Carlo or Langevin sampling will not be able to match the performance of the simple message passing algorithms. This is contrary to what was widely believe in the field and is being confirmed using numerical simulations and analytical studies of the dynamics in simpler models.<\/p>\n
Analyzing the ASP algorithm we reached another striking conclusion: ASP is unable to outperform the simpler message passing algorithm and so in particular ASP also does not work in the hard phase, this is despite taking correctly into account the glassiness while the simpler algorithm ignores it. This is a considerable evidence towards the fact that the hard phase is impenetrable for efficient algorithms for perhaps fundamental reasons, that are however ou of reach of current computational complexity theory. Further investigation of this point is an exciting direction both for physics and theoretical computer science.<\/p>\n<\/div>\n\n\n
![\"samurai\"\/](\"\/images\/Highlights\/samurai.png\")
<\/figure>Mean Square Error of the ASP algorithm as a function of the Parisi parameter s on which the algorithm depends. We see that the minimal error is always reached for s=1 for which the ASP algorithm reduces to the simpler form that ignores glassy aspects of the hard phase. <\/em><\/p>\n<\/div><\/div>\n\n\n\n F. Antenucci (CEA), P. Urbani (CEA), F. Krzakala (ENS), L. Zdeborov\u00e1 (CEA), Approximate Survey Propagation for Statistical Inference, Journal of Statistical Mechanics (2019)<\/p>\n\n\n\n F. Antenucci (CEA), S. Franz (LPTMS), P. Urbani (CEA), L. Zdeborov\u00e1 (CEA), On the glassy nature of the hard phase in inference problems, Phys. Rev. X 9<\/strong>, 011020 (2019)<\/p>\n\n\n\n R\u00e9sultats obtenus dans le cadre du projet SaMURai<\/strong> financ\u00e9 par le th\u00e8me \u00e9mergence du LabEx PALM et port\u00e9 par Lenka Zdeborov\u00e1 (CEA) et Silvio Franz (LPTMS)<\/p>\n","protected":false},"excerpt":{"rendered":" F. Antenucci (CEA), P. Urbani (CEA), F. Krzakala (ENS), S. Franz (LPTMS), L. Zdeborov\u00e1 […]<\/p>\n","protected":false},"author":1,"featured_media":4024,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[53,2],"tags":[],"acf":[],"yoast_head":"\n