Local entropy as a measure for sampling solutions in constraint satisfaction problems
From MaRDI portal
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 -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.
Recommendations
- Gibbs states and the set of solutions of random constraint satisfaction problems
- scientific article; zbMATH DE number 7301529
- Entropy landscape of solutions in the binary perceptron problem
- On the solution-space geometry of random constraint satisfaction problems
- Perturbed message passing for constraint satisfaction problems
Cites work
- A Max-Sum algorithm for training discrete neural networks
- Determining computational complexity from characteristic ``phase transitions
- Entropy landscape of solutions in the binary perceptron problem
- Generalization learning in a perceptron with binary synapses
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Information, Physics, and Computation
- Statistical mechanics methods and phase transitions in optimization problems
- Survey propagation: An algorithm for satisfiability
Cited in
(19)- Deep relaxation: partial differential equations for optimizing deep neural networks
- Biased landscapes for random constraint satisfaction problems
- Optimization of the dynamic transition in the continuous coloring problem
- Entropic gradient descent algorithms and wide flat minima*
- Entropy-SGD: biasing gradient descent into wide valleys
- Clustering of solutions in the symmetric binary perceptron
- Shaping the learning landscape in neural networks around wide flat minima
- Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
- Wide flat minima and optimal generalization in classifying high-dimensional Gaussian mixtures
- Frozen 1-RSB structure of the symmetric Ising perceptron
- On the atypical solutions of the symmetric binary perceptron
- Searching for (sharp) thresholds in random structures: where are we now?
- Capacity lower bound for the Ising perceptron
- Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
- How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
- Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
- A CLuP algorithm to practically achieve 0.76 SK-model ground state free energy
- Finding the right path: statistical mechanics of connected solutions in constraint satisfaction problems
- Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms
This page was built for publication: Local entropy as a measure for sampling solutions in constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3302534)
