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

arXiv: https://arxiv.org/abs/2502.16292 · HTML: https://mlsanity.com/paper/2502.16292/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 58 references that are in the map.
- First posted on arXiv 22 Feb 2025.

## Builds on (most cited first, 22 of 22)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Building Normalizing Flows with Stochastic Interpolants](https://mlsanity.com/paper/2209.15571/) (2022)
- [Stochastic Interpolants: A Unifying Framework for Flows and Diffusions](https://mlsanity.com/paper/2303.08797/) (2023)
- [Denoising Diffusion Samplers](https://mlsanity.com/paper/2302.13834/) (2023)
- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022)
- [Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes](https://mlsanity.com/paper/1605.06444/) (2016)
- [Sampling, Diffusions, and Stochastic Localization](https://mlsanity.com/paper/2305.10690/) (2023)
- [Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses](https://mlsanity.com/paper/1509.05753/) (2015)
- [Stochastic Localization via Iterative Posterior Sampling](https://mlsanity.com/paper/2402.10758/) (2024)
- [Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective](https://mlsanity.com/paper/2308.14085/) (2023)
- [Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems](https://mlsanity.com/paper/1511.05634/) (2015)
- [Origin of the computational hardness for learning with binary synapses](https://mlsanity.com/paper/1408.1784/) (2014)
- [Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster](https://mlsanity.com/paper/2111.03084/) (2021)
- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [Algorithms and Barriers in the Symmetric Binary Perceptron Model](https://mlsanity.com/paper/2203.15667/) (2022)
- [Learned Reference-based Diffusion Sampling for multi-modal distributions](https://mlsanity.com/paper/2410.19449/) (2024)
- [Hardness of sampling solutions from the Symmetric Binary Perceptron](https://mlsanity.com/paper/2407.16627/) (2024)
- [A Max-Sum algorithm for training discrete neural networks](https://mlsanity.com/paper/1505.05401/) (2015)

## Built on by (most cited first, 1 of 1)

- [Joint stochastic localization and applications](https://mlsanity.com/paper/2505.13410/) (2025)

## Abstract (arXiv)

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 α = M/N. We develop a formalism based on replica theory to predict the fundamental limits of efficiently sampling the solution space using generative diffusion algorithms, conjectured to be saturated when the score function is provided by Approximate Message Passing. For the spherical perceptron with negative margin kappa, we find that the uniform distribution over solutions can be efficiently sampled in most of the Replica Symmetric region of the α-kappa plane. In contrast, for binary weights, sampling from the uniform distribution remains intractable. A theoretical analysis of this obstruction leads us to identify a potential U(s) = -log(s), under which the corresponding tilted distribution becomes efficiently samplable via diffusion. Moreover, we show numerically that an annealing procedure over the shape of this potential yields a fast and robust Markov Chain Monte Carlo algorithm for sampling the solution space of the binary perceptron.