Where the really hard sampling problems are

Authors:
  • SCSimone Ciarella
    Simone Ciarella
  • JTJeanne Trinquier
    Jeanne Trinquier
  • MWMartin Weigt
    Martin Weigt
  • FZFrancesco Zamponi
    Francesco Zamponi

Abstract
Several strategies have been recently proposed in order to improve Monte Carlo sampling efficiency using machine learning tools. Here, we reconsider previous studies and find that most of the sampling problems that were considered before are not sufficiently hard. We then consider a class of problems that are known to be exponentially hard to sample using conventional local Monte Carlo at low enough temperatures, including in particular 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 provide good benchmarks for future proposals for smart sampling algorithms.