Local entropy as a measure for sampling solutions in constraint satisfaction problems

By Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, Riccardo Zecchina. 2015

71 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Mathematics of Deep Learning (2017, result): “This motivates algorithms like Entropy-SGD that are specialized to ﬁnd such regions and draw from similar results in the analysis of binary per-ceptrons in statistical physics [24]; they have been shown to perform well on deep networks [25].”
Parle: parallelizing stochastic gradient descent (2017, methodology): “Using different techniques, the two objectives can be shown equivalent under different approximations (Baldassi et al., 2016a).”
Shaping the learning landscape in neural networks around wide flat minima (2019, methodology): “…approach gets stuck at very high energies when trying to minimize the error loss function, the very same algo-rithm with the CE loss is indeed successful up to relatively high values of α , with just slightly worse performance compared to an analogous procedure based on local entropy (13).”
Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes (2016, background): “Better results can be obtained by using the following general deﬁnition instead: we deﬁne the energy E µ ( W ) associated to each pattern µ as the minimum number of synapses that need to be switched in order to classify the pattern correctly.”