Gespeichert in:
| Hauptverfasser: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2506.05197 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911297413578752 |
|---|---|
| author | Benedetti, Marco Bogdanov, Andrej Malatesta, Enrico M. Mézard, Marc Perrupato, Gianmarco Rosen, Alon Schwartzbach, Nikolaj I. Zecchina, Riccardo |
| author_facet | Benedetti, Marco Bogdanov, Andrej Malatesta, Enrico M. Mézard, Marc Perrupato, Gianmarco Rosen, Alon Schwartzbach, Nikolaj I. Zecchina, Riccardo |
| contents | Square Wave Perceptrons (SWPs) form a class of neural network models with oscillating activation function that exhibit intriguing ``hardness'' properties in the high-dimensional limit at a fixed constraint density $α= O(1)$. In this work, we examine two key aspects of these models. The first is related to the so-called \emph{overlap-gap property}, that is a disconnectivity feature of the geometry of the solution space of combinatorial optimization problems proven to cause the failure of a large family of solvers, and conjectured to be a symptom of algorithmic hardness. We identify, both in the storage and in the teacher-student settings, the emergence of an overlap gap at a threshold $α_{\mathrm{OGP}}(δ)$, which can be made arbitrarily small by suitably increasing the frequency of oscillations $1/δ$ of the activation. This suggests that in this small-$δ$ regime, typical instances of the problem are hard to solve even for small values of $α$. Second, in the teacher-student setup, we show that the recovery threshold of the planted signal for message-passing algorithms can be made arbitrarily large by reducing $δ$. These properties make SWPs both a challenging benchmark for algorithms and an interesting candidate for cryptographic applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_05197 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Overlap Gap and Computational Thresholds in the Square Wave Perceptron Benedetti, Marco Bogdanov, Andrej Malatesta, Enrico M. Mézard, Marc Perrupato, Gianmarco Rosen, Alon Schwartzbach, Nikolaj I. Zecchina, Riccardo Disordered Systems and Neural Networks Square Wave Perceptrons (SWPs) form a class of neural network models with oscillating activation function that exhibit intriguing ``hardness'' properties in the high-dimensional limit at a fixed constraint density $α= O(1)$. In this work, we examine two key aspects of these models. The first is related to the so-called \emph{overlap-gap property}, that is a disconnectivity feature of the geometry of the solution space of combinatorial optimization problems proven to cause the failure of a large family of solvers, and conjectured to be a symptom of algorithmic hardness. We identify, both in the storage and in the teacher-student settings, the emergence of an overlap gap at a threshold $α_{\mathrm{OGP}}(δ)$, which can be made arbitrarily small by suitably increasing the frequency of oscillations $1/δ$ of the activation. This suggests that in this small-$δ$ regime, typical instances of the problem are hard to solve even for small values of $α$. Second, in the teacher-student setup, we show that the recovery threshold of the planted signal for message-passing algorithms can be made arbitrarily large by reducing $δ$. These properties make SWPs both a challenging benchmark for algorithms and an interesting candidate for cryptographic applications. |
| title | Overlap Gap and Computational Thresholds in the Square Wave Perceptron |
| topic | Disordered Systems and Neural Networks |
| url | https://arxiv.org/abs/2506.05197 |