Research map / Probabilistic and scientific modeling / Variational and generative sampling
Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Develops a replica-based formalism predicting when algorithmic stochastic localization (diffusion with AMP score) can fairly sample perceptron solution spaces, finds uniform sampling works for spherical negative-margin perceptron in most of the RS region, and proposes a -log(s) potential with a tau-annealed MCMC for binary perceptron.
Problem
Sampling solution spaces of random non-convex perceptron problems (spherical with negative margin, binary weights) efficiently when the target is known only up to a normalization constant, via generative diffusion with AMP-estimated scores.
Approach
Uses a double replica trick to compute time-dependent free entropy for unnormalized target densities, predicting when AMP-based stochastic localization succeeds; identifies the potential U(s)=-log(s) that makes the tilted binary perceptron distribution samplable, and reshapes it into a tau-annealed MCMC.
Key results
- For the binary perceptron with U(s)=-log(s) and T=0.5, ASL samples up to alpha_alg approximately 0.65 at kappa=0, close to the sat/unsat threshold near 0.83.
- For the spherical perceptron, ASL samples uniformly over most of the replica-symmetric region, with the samplability frontier coinciding with the DAT line.
- Tau-annealed MCMC solves binary perceptron instances up to alpha approximately 0.55 with n_sweeps = N, while temperature annealing struggles at large N.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use ASL with the uniform distribution over solutions | Spherical perceptron with negative margin · Replica Symmetric region of the α–κ plane | sampling feasibility | Helped |
| use ASL to sample the uniform distribution | Binary perceptron · Binary perceptron (κ=0) | sampling feasibility | Hurt |
| tilt the target distribution with U(s) = -log(s) | ASL for the binary perceptron · Binary perceptron (κ=0) | algorithmic threshold α_alg: α_alg≈0.65 | Helped |
| use a potential that does not diverge at the origin | ASL for the binary perceptron · Binary perceptron | sampling feasibility | Hurt |
| use τ-annealing rather than temperature annealing | MCMC for the binary perceptron · Binary perceptron | solution-finding performance as system size increases | Helped |
| scale the number of sweeps as n_sweeps=N | τ-annealing MCMC · Binary perceptron | solved constraint density α: α ≈ 0.55 | Helped |
Surprising findings
- Uniform distribution over binary perceptron solutions cannot be efficiently sampled by ASL for any alpha, because the free entropy always has a peak at q=1 unless the potential diverges at the origin.
Limitations
- RS ansatz is exact only in the replica-symmetric region; RSB regimes (e.g. d1RSB) cause ASL to fail earlier.
- AMP fails to converge on structured or correlated data, so ASL is not a practical general sampler.
- Rigorous justification is lacking; results rely on the non-rigorous replica method.
Experimental setup
Datasets: synthetic Gaussian perceptron instances synthetic binary perceptron instances
Benchmarks: synthetic spherical perceptron synthetic binary perceptron
Metrics: probability of finding a solution empirical stability distribution vs replica prediction algorithmic threshold alpha
Baselines: Simulated Annealing
Builds on: Algorithmic Stochastic Localization generalized approximate message passing stochastic interpolants replica method
Closest papers by meaning
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.89)
- Towards Non-Asymptotic Convergence for Diffusion-Based Generative Models (ICLR 2024 · similarity 0.88)
- Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity (NeurIPS 2024 · similarity 0.87)
- Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems (NeurIPS 2026 · similarity 0.87)
- Evaluating the design space of diffusion-based generative models (NeurIPS 2024 · similarity 0.87)
- Accelerating Convergence of Score-Based Diffusion Models, Provably (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.