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 (23)

• The Bethe lattice spin glass revisited
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical physics of inference: Thresholds and algorithms
• Phase transition in the detection of modules in sparse networks
• Phase Transitions in the Coloring of Random Graphs
• Coloring random graphs
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• A ferromagnet with a glass transition
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Typology of phase transitions in Bayesian inference problems
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Quiet Planting in the Locked Constraint Satisfaction Problems
• A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Glassy nature of the hard phase in inference problems
• Biased landscapes for random Constraint Satisfaction Problems
• Parallel Tempering for the planted clique problem
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Optimization of the dynamic transition in the continuous coloring problem
• Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection

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