Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems

Abstract

The planted coloring problem is a prototypical inference problem for which thresholds for Bayes optimal algorithms, like Belief Propagation (BP), can be computed analytically. In this paper, we analyze the limits and performances of the Simulated Annealing (SA), a Monte Carlo-based algorithm that is more general and robust than BP, and thus of broader applicability. We show that SA is sub-optimal in the recovery of the planted solution because it gets attracted by glassy states that, instead, do not influence the BP algorithm. At variance with previous conjectures, we propose an analytic estimation for the SA algorithmic threshold by comparing the spinodal point of the paramagnetic phase and the dynamical critical temperature. This is a fundamental connection between thermodynamical phase transitions and out of equilibrium behavior of Glauber dynamics. We also study an improved version of SA, called replicated SA (RSA), where several weakly coupled replicas are cooled down together. We show numerical evidence that the algorithmic threshold for the RSA coincides with the Bayes optimal one. Finally, we develop an approximated analytical theory explaining the optimal performances of RSA and predicting the location of the transition towards the planted solution in the limit of a very large number of replicas. Our results for RSA support the idea that mismatching the parameters in the prior with respect to those of the generative model may produce an algorithm that is optimal and very robust.

References in corpus (5)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase transition in the detection of modules in sparse networks
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs

Cited by in corpus (11)

• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Hopfield model with planted patterns: a teacher-student self-supervised learning model
• Anomalous distribution of magnetization in an Ising spin glass with correlated disorder
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• SWAP algorithm for lattice spin models
• Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape
• Evidence of Replica Symmetry Breaking under the Nishimori conditions in epidemic inference on graphs
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Interacting Copies of Random Constraint Satisfaction Problems