Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms

Elizaveta Demyanenko, Davide Straziota, Carlo Baldassi +1

We consider random instances of non-convex perceptron problems in the high-dimensional limit of a large number of examples $M$ and weights $N$, with finite load $\alpha =M/N$. We develo…