Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
Open Access
- 1 March 2023
- journal article
- research article
- Published by IOP Publishing in Machine Learning: Science and Technology
- Vol. 4 (1) , 010501
Abstract
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
All Related Versions
Funding Information
- H2020 European Research Council (723955)
This publication has 41 references indexed in Scilit:
- Potts glass on random graphsEurophysics Letters, 2008
- Phase transitions in the coloring of random graphsPhysical Review E, 2007
- Landscape analysis of constraint satisfaction problemsPhysical Review E, 2007
- Gibbs states and the set of solutions of random constraint satisfaction problemsProceedings of the National Academy of Sciences, 2007
- Universality in three-dimensional Ising spin glasses: A Monte Carlo studyPhysical Review B, 2006
- Coloring Random GraphsPhysical Review Letters, 2002
- Analytical solution of the off-equilibrium dynamics of a long-range spin-glass modelPhysical Review Letters, 1993
- Comparison between dynamical theories and metastable states in regular and glassy mean-field spin models with underlying first-order-like phase transitionsPhysical Review A, 1988
- Optimization by Simulated AnnealingScience, 1983
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982