Circumventing spin glass traps by microcanonical spontaneous symmetry breaking

Abstract

The planted p-spin interaction model is a paradigm of random-graph systems possessing both a ferromagnetic phase and a disordered phase with the latter splitting into many spin glass states at low temperatures. Conventional simulated annealing dynamics is easily blocked by these low-energy spin glass states. Here we demonstrate that, actually this planted system is exponentially dominated by a microcanonical polarized phase at intermediate energy densities. There is a discontinuous microcanonical spontaneous symmetry breaking transition from the paramagnetic phase to the microcanonical polarized phase. This transition can serve as a mechanism to avoid all the spin glass traps, and it is accelerated by the restart strategy of microcanonical random walk. We also propose an unsupervised learning problem on microcanonically sampled configurations for inferring the planted ground state.

arXiv comment11 pages; final version as accepted by PRE; minor corrections to reference and affiliation name

References in corpus (19)

• The Bethe lattice spin glass revisited
• Statistical physics of inference: Thresholds and algorithms
• Reconstruction on trees and spin glass transition
• Learning by message-passing in networks of discrete synapses
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• A ferromagnet with a glass transition
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Random numbers for large scale distributed Monte Carlo simulations
• Circumspect descent prevails in solving random constraint satisfaction problems
• Advanced Mean Field Theory of Restricted Boltzmann Machine
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Equilibrium Microcanonical Annealing for First-Order Phase Transitions
• Random-field p-spin glass model on regular random graphs
• Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example
• Cavity approach to the Sourlas code system
• Kinked Entropy and Discontinuous Microcanonical Spontaneous Symmetry Breaking
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Active online learning in the binary perceptron problem
• Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process

Cited by in corpus (2)

• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• Entropic barriers as a reason for hardness in both classical and quantum algorithms