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

Elizaveta Demyanenko, Davide Straziota, Carlo Baldassi, Carlo Lucibello

TL;DR

This paper uses tools from statistical physics to map out the fundamental limits of generative diffusion models when sampling from complex, non-convex solution spaces. The authors show that while uniform sampling is highly efficient for spherical perceptrons, it fails completely for binary perceptrons due to structural geometry; however, introducing a clever logarithmic potential "unlocks" efficient sampling and inspires a powerful new MCMC optimization algorithm.

What Problem Does This Paper Address?

Generative diffusion models have revolutionized machine learning by making it easy to sample from complex probability distributions. However, understanding when and why these models succeed or fail in high-dimensional, non-convex landscapes remains a major theoretical challenge.

To explore this, the authors focus on random constraint satisfaction problems—specifically the spherical perceptron with negative margin and the binary weight perceptron. These serve as minimal, mathematically tractable models for understanding the glassy, non-convex landscapes typical of deep neural networks. The core question is: can a polynomial-time diffusion algorithm efficiently sample fair solutions from these landscapes, and what geometric features act as barriers to sampling?

Methods

The authors analyze a specific flavor of generative diffusion known as Algorithmic Stochastic Localization (ASL). In ASL, the reverse denoising process is driven by a time-dependent score function, which the authors approximate using Approximate Message Passing (AMP)—an algorithm conjectured to be optimal among polynomial-time methods for this task.

To theoretically predict the performance of ASL, the paper introduces a novel framework using the replica method from spin glass theory. Standard replica methods struggle when the target distribution has an intractable normalization factor (the partition function $Z$). The authors overcome this by applying a double replica trick:

  1. Introducing $s$ replicas to handle the normalization of the reference system.
  2. Introducing $n$ replicas to linearize the log-term in the free entropy.

Additionally, to bypass the practical limitations of AMP on structured data, the authors introduce $\tau$-annealing MCMC, a Markov Chain Monte Carlo variant that uses a reshaped, parameterized potential to smoothly guide the sampler toward valid binary solutions.

Datasets

The theoretical analysis and initial validations rely on synthetic random ensembles:

  • Synthetic Data: i.i.d. Gaussian inputs $\mathbf{x}^\mu \sim \mathcal{N}(0, I_N)$ or uniform random inputs $\mathbf{x}^\mu \sim \text{Unif}(\{-1, +1\}^N)$.

To test their derived MCMC algorithm on realistic, structured data, the authors evaluate it on binary classification tasks using three standard image datasets:

  • MNIST (classifying digits 3 vs 8)
  • FashionMNIST (classifying classes 5 vs 7)
  • CIFAR10 (classifying classes 3 vs 8)

Key Insights and Ideas

  • Ergodicity Breaking as a Hard Barrier: For the spherical perceptron, diffusion works perfectly as long as the solution space remains connected (the Replica Symmetric phase). The exact moment the space fragments into disconnected clusters (Replica Symmetry Breaking), the diffusion process fails because the underlying free-entropy landscape becomes multimodal.
  • The Geometry of Isolation: In the binary perceptron, typical solutions are completely isolated. This creates an inescapable mathematical peak in the free entropy at perfect overlap ($q=1$), causing standard uniform diffusion to fail at all constraint densities ($\alpha > 0$).
  • Tilted Landscapes via Log-Potentials: The authors discovered that a singular potential $U(s) = -\log(s)$ perfectly counteracts the mathematical obstruction at $q=1$. Tilting the distribution with this potential smooths out the landscape, making a subdominant, dense cluster of solutions algorithmically accessible to the diffusion process.

Key Results

  • Spherical Perceptron: The exact samplability frontier matches the De Almeida-Thouless (DAT) line perfectly, showing that diffusion succeeds across almost the entire Replica Symmetric region.
Figure 1: Asymptotic analysis of ASL sampling for the Spherical Perceptron with uniform distribution. Left: Free entropy function ϕt(q) for different values of t and for α = 278,κ = −2.5. Initially, ϕt(q) has a single maximum, but as t increases, a second maximum appears, eventually becoming the global one. Center: Phase diagram of ASL in the t-vs-α plane for κ = −2.5. Green region: ϕt(q) has a single optimizer, meaning the AMP succeeds at denoising. Yellow region: ϕt(q) has two optimizers, but the global maximum corresponds to the smaller overlap q. AMP still succeeds. Red region: ϕt(q) has two optimizers, but the global maximum corresponds to a larger overlap q. In this case, AMP fails the denoising task. In order for ASL to succeed at sampling, a vertical line at the corresponding α should lie entirely in the green region. Right: Phase diagram delineating the samplable and non-samplable regions for ASL in α-vs-κ plane. Transition lines predicted from replica theory are taken from Baldassi et al. [2023]. The green region can be sampled by ASL. The zoom in the inset shows the failure of ASL at reaching the d1RSB line.
  • Binary Perceptron: Under the uniform distribution, sampling is impossible. However, by introducing the log-potential, ASL achieves a high algorithmic threshold of $\alpha_{alg} \approx 0.65$ (for margin $\kappa = 0$), approaching the theoretical sat/unsat transition at $\alpha_c \approx 0.83$.
  • $\tau$-Annealing Performance: The proposed MCMC scheme successfully finds binary perceptron solutions up to $\alpha \approx 0.55$ at large system sizes ($N=8192$), completely outperforming standard temperature-based simulated annealing, which fails as $N$ scales. It also demonstrates superior accuracy and robustness on MNIST, FashionMNIST, and CIFAR10.

Limitations and Future Work

While highly powerful, the ASL framework inherits the standard limitations of AMP: it struggles to converge when applied directly to highly structured or correlated real-world data without preprocessing.

Additionally, the theoretical analysis assumes a Replica Symmetric (RS) ansatz for the tilted system. While valid for tracking the algorithm's success, it does not fully capture the dynamics deep within replica-symmetry-broken regimes. The authors note that a promising future direction is to rigorously prove these thresholds for mathematically simpler variants, such as the binary symmetric perceptron.

Summary updated

Abstract

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 $κ$, we find that the uniform distribution over solutions can be efficiently sampled in most of the Replica Symmetric region of the $α$-$κ$ 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.
BibTeX
@inproceedings{demyanenko2025generative,
  author = {Elizaveta Demyanenko and Davide Straziota and Carlo Baldassi and Carlo Lucibello},
  title = {{Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=SyJ3PdcokV},
}
Figure