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

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.

References in corpus (17)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Universality in three-dimensional Ising spin glasses: A Monte Carlo study
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• A Landscape Analysis of Constraint Satisfaction Problems
• Efficient generative modeling of protein sequences using simple autoregressive models
• Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
• Variational Neural Annealing
• Potts Glass on Random Graphs
• Graph Coloring with Physics-Inspired Graph Neural Networks
• Unbiased Monte Carlo Cluster Updates with Autoregressive Neural Networks
• Free-then-freeze: transient learning degrees of freedom for introducing function in materials
• Creating bulk ultrastable glasses by random particle bonding
• Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut
• Optimization of the dynamic transition in the continuous coloring problem
• Finding spin glass ground states through deep reinforcement learning

Cited by in corpus (17)

• Roadmap on machine learning glassy dynamics
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Irreversible Monte Carlo algorithms for hard disk glasses: from event-chain to collective swaps
• Normalizing flows as an enhanced sampling method for atomistic supercooled liquids
• Policy-guided Monte Carlo on general state spaces: Application to glass-forming mixtures
• The autoregressive neural network architecture of the Boltzmann distribution of pairwise interacting spins systems
• Accelerating equilibrium spin-glass simulations using quantum annealers via generative deep learning
• Creating equilibrium glassy states via random particle bonding
• Sparse Autoregressive Neural Networks for Classical Spin Systems
• Characterising the slow dynamics of the swap Monte Carlo algorithm
• Performance of machine-learning-assisted Monte Carlo in sampling from simple statistical physics models
• Efficient Optimization of Variational Autoregressive Networks with Natural Gradient
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm
• Nearest-Neighbours Neural Network architecture for efficient sampling of statistical physics models
• Ratio Divergence Learning Using Target Energy in Restricted Boltzmann Machines: Beyond Kullback--Leibler Divergence Learning
• Sampling the Liquid-Gas Critical Point with Boltzmann Generators