The strange case of the symmetric binary perceptron: when standard statistical mechanics fails
Damien Barbier
Bocconi University, Milan
Seminar of the Series MLP@P (Machine Learning Physics @ Plateau), joint with LISN and IPhT.
Where: LISN, bat 660 salle 2014 (2° étage)
We define and study a statistical mechanics ensemble that characterizes connected solutions in
constraint satisfaction problems (CSPs). Built around a well-known local entropy bias, it allows
us to better identify hardness transitions in problems where the energy landscape is dominated by
isolated solutions. We apply this new device to the symmetric binary perceptron model (SBP), and
study how its manifold of connected solutions behaves. We choose this particular problem because,
while its typical solutions are isolated, it can be solved using local algorithms for a certain range of
constraint density α and threshold κ. With this new ensemble, we unveil the presence of a cluster
composed of delocalized connected solutions. In particular, we demonstrate its stability until a
critical threshold κ_{no−mem loc. stab.} (dependent on α). This transition appears as paths of solutions shatter,
a phenomenon that more conventional statistical mechanics approaches fail to grasp. Finally, we
compared our predictions to simulations. For this, we used a modified Monte-Carlo algorithm,
designed specifically to target these delocalized solutions. We obtained, as predicted, that the
algorithm finds solutions until κ ≈ κ_{no−mem loc. stab.}.