Machine Learning: Science and Technology (Jan 2023)

Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems

  • Simone Ciarella,
  • Jeanne Trinquier,
  • Martin Weigt,
  • Francesco Zamponi

DOI
https://doi.org/10.1088/2632-2153/acbe91
Journal volume & issue
Vol. 4, no. 1
p. 010501

Abstract

Read online

Several strategies have been recently proposed in order to improve Monte Carlo sampling efficiency using machine learning tools. Here, we challenge these methods by considering a class of problems that are known to be exponentially hard to sample using conventional local Monte Carlo at low enough temperatures. In particular, we study the antiferromagnetic Potts model on a random graph, which reduces to the coloring of random graphs at zero temperature. We test several machine-learning-assisted Monte Carlo approaches, and we find that they all fail. Our work thus provides good benchmarks for future proposals for smart sampling algorithms.

Keywords