The strange case of the binary perceptron: when standard statistical mechanics fails
Damien Barbier (post-doc, Department of Computer Sciences (Bocconi University), Milan, Italy)
| Quand ? |
Le 03/02/2026, de 13:00 à 14:00 |
|---|---|
| Où ? | M7 101 |
| S'adresser à | Pierre Borgnat |
| Participants |
Damien Barbier |
| Ajouter un événement au calendrier |
vCal
iCal
|
Damien Barbier
Title: The strange case of the binary perceptron: when standard statistical mechanics fails
Abstract: 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.}
Website: https://scholar.google.com/citations?hl=fr&user=_tDnkoUAAAAJ&view_op=list_works&sortby=pubdate
In Room M7 101, 1st floor, Monod campus, ENSL.