Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems

Abstract

We introduce a novel Entropy-driven Monte Carlo (EdMC) strategy to efficiently sample solutions of random Constraint Satisfaction Problems (CSPs). First, we extend a recent result that, using a large-deviation analysis, shows that the geometry of the space of solutions of the Binary Perceptron Learning Problem (a prototypical CSP), contains regions of very high-density of solutions. Despite being sub-dominant, these regions can be found by optimizing a local entropy measure. Building on these results, we construct a fast solver that relies exclusively on a local entropy estimate, and can be applied to general CSPs. We describe its performance not only for the Perceptron Learning Problem but also for the random $K$-Satisfiabilty Problem (another prototypical CSP with a radically different structure), and show numerically that a simple zero-temperature Metropolis search in the smooth local entropy landscape can reach sub-dominant clusters of optimal solutions in a small number of steps, while standard Simulated Annealing either requires extremely long cooling procedures or just fails. We also discuss how the EdMC can heuristically be made even more efficient for the cases we studied.

46 pages (main text: 22), 7 figures. This is an author-created, un-copyedited version of an article published in Journal of Statistical Mechanics: Theory and Experiment. IOP Publishing Ltd is not responsible for any errors or omissions in this version of the manuscript or any version derived from it. The Version of Record is available online at http://dx.doi.org/10.1088/1742-5468/2016/02/023301

References in corpus (9)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• Survey propagation: an algorithm for satisfiability
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Efficient supervised learning in networks with binary synapses
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Origin of the computational hardness for learning with binary synapses
• Generalization learning in a perceptron with binary synapses
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy

Cited by in corpus (31)

• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Shaping the learning landscape in neural networks around wide flat minima
• Mathematics of Deep Learning
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Unveiling the structure of wide flat minima in neural networks
• Learning may need only a few bits of synaptic precision
• Biased landscapes for random Constraint Satisfaction Problems
• On the role of synaptic stochasticity in training low-precision neural networks
• The large deviations of the whitening process in random constraint satisfaction problems
• Parle: parallelizing stochastic gradient descent
• Clustering of solutions in the symmetric binary perceptron
• Teacher-student learning for a binary perceptron with quantum fluctuations
• Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
• Wide flat minima and optimal generalization in classifying high-dimensional Gaussian mixtures
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Maximally flexible solutions of a random $K$-satisfiability formula
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Partial local entropy and anisotropy in deep weight spaces
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Optimization of the dynamic transition in the continuous coloring problem
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Capacity lower bound for the Ising perceptron
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Interacting Copies of Random Constraint Satisfaction Problems
• Native state of natural proteins optimises local entropy