Carlo Lucibello — Politecnico di Torino #
Local Entropy and Coupling Methods for Optimization Problems#
The ubiquitous problem  of cost function minimization greatly benefited in the last decades from the connection with ground state search in statistical mechanics systems. Physics' inspired Monte Carlo methods, such as Simulated Annealing and Parallel Tempering, and heuristics, such as Belief Propagation, proved to be highly effective in dealing with rough free energy landscapes.
Here we present a slightly different mapping for the minimization problem, where the Gibbs weight is modified with the addition of a bias towards configurations having an high local entropy. For integer bias exponents, the resulting partition function is that of a replicated system with an attractive coupling among replicas. This leads to a general prescription that can be applied to many existing algorithms, resulting sometimes in huge improvements in their performances. I will discuss the performance of Simulated Annealing and Belief Propagation on the replicated system for the problems of neural networks and KSAT.
<br>
Bibliography:
[1] C Baldassi, A Ingrosso, C Lucibello, L Saglietti and R Zecchina.  Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks
with Discrete Synapses. PRL 2015.

[2] C Baldassi, A Ingrosso, C Lucibello, L Saglietti and R Zecchina. Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems. JSTAT 2016.