Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms
Authors: Davide Straziota
Elizaveta Demyanenko
Carlo Baldassi
Carlo Lucibello
Venue: NeurIPS 2025 poster ()
Keywords: generative diffusion
approximate message passing
perceptron
spin glasses
statistical physics
markov chain monte carlo
Primary area: theory

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 $\alpha = 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 $\alpha$–$\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.

Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms
Davide Straziota"
Elizaveta Demyanenko" Department of Computing Sciences Bocconi University, Milan, Italy
Department of Computing Sciences Bocconi University, Milan, Italy
Carlo Baldassi
Carlo Lucibello
Department of Computing Sciences, BIDSA Bocconi University, Milan, Italy
Department of Computing Sciences, BIDSA Bocconi University, Milan, Italy
Abstract
We consider random instances of non-convex perceptron problems in the high- dimensional limit of large number of examples M and weights N, with finite load a M/N. We develop formalism based on replica theory to predict the fundamental limits of efficiently sampling the solution space using generative diffu- sion algorithms, conjectured to saturated when the score function is provided by Approximate Message Passing. For the spherical perceptron with negative margin K, 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 identify potential U(s) log(s) ()), under which the corresponding tilted distribution becomes efficiently samplable via diffu- sion. Moreover, of this potential yields a fast and robust Markov Chain Monte Carlo algorithm for sampling the solution space of the binary perceptron.
show numerically that annealing procedure the shape
Introduction
fundamental challenge in modern machine learning is the ability to efficiently sample from complex probability distributions. This problem is central to many areas, from generative modeling, where methods such as variational autoencoders and autoregressive transformers aim to approximate real- world data distributions, to Bayesian inference, where the goal is to explore posterior distributions over model parameters.
Diffusion models "Sohl-Dicksterd et al., 2015, Ho et al., 2020] have recently emerged as prominent class of generative models, capable of capturing very complex distributions across various domains, with high sample efficiency. These models simulate stochastic diffusion process in reverse, starting from a simple distribution and arriving at complex target distribution p( (()) via stochastic differential equation, process called denoising (the corresponding noising process being the forward diffusion process). All dependence on p( w) encoded a drift term determined by a time-dependent score function. In many applications, p(w) is not explicitly known, but samples from are available. neural approximation to the score function driving the generative process then learned using the denoising score matching objective [Vincent, 2011].
equal contributions
carloobbldasse @ unibocconi.it
lucibelo @ unibocconi.it
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Here instead we consider settings in which the target probability density is known, but only up to an intractable normalization factor:
1/( w))
p(w))= Z
This formulation is ubiquitous in probabilisttcc modeling, encompassing energy-based models and posterior inference in Bayesian statistics [LeCun et al., 2007, Neal, 2011]. It arises whenever probabilities are defined through unnormalized potentials, such in Bayesian inference where the posterior is proportional to the product of likelihood and prior, as well as in physical systems, graphical models, and deep mergy-based representations. Typical sampling algorithms in this setting belong to the Markov Chain Monte Carlo (MCMC) family Brooks et al. [2011]. These can suffer from slow mixing times, and their theoretical analysis is generally challenging. In contrast, for generative diffusion, the continuous stochastic process can be well approximated by small number of discrete steps, and the Bayesian structure induced by the noising/denoising process facilitates theoretical analysis. Recent efforts have explored hybrid approaches combining generative diffusion with MCMC methods [Grenioux et al., 2024, Noble et al., 2025, Vargas al., 2023, 2025].
fundamental question is whether the score function can be computed (at all times t) by a polynomial- time algorithm with access to the unnormalized density (w)), enabling efficient sampling from p (w) via generative diffusion, An answer to this question would, in turn, naturally bound the performance attainable in settings where only samples from the target distribution are available. Moreover, will show, an analysis capable of providing insights into the failure modes of generative diffusion can also suggest modifications and inform algorithmic design, even beyond the original scope.
In this work, we develop a theoretical framework to address this problem precisely in the high- dimensional limit, considering random instances of the distribution p itself (i.c., assuming quenched disorder, in statistical physics terminology). Our framework relies on the non-rigorous but extensively validated replica method from spin glass theory [Mézard et al., 1987, Charbonneau et al., 2023]. The sampling algorithm associated with the replica analysis employs Approximate Message Passing (AMP) [Donoho et al., 2009, Barbier et al., 2019] as the score approximator within the diffusion process. AMP is conjectured to be optimal among polynomial-ting algorithms for the denoising task involved in computing the score function.
Diffusion and AMP The diffusion flavor that we use is that of Stochastic Localization (SL) [Eldan, 2013], which can be mapped to a standard denoising diffusion process through time and space transformations [Montanari, 2023, EI Alaoui and Montanari, 2022]. We call Algorithmic Stochastic Localization (ASL) the algorithmic implementation of SL on a given target distribution where AMP is used to approximate the score function. ASL was introduced in El Alaoui et al. [2022] and proven to produce fair samples from the Eeerringtoo-Kiikpatrii temperature. ASL has also been applied in statistical inference settings, namely spiked matrix models and high- dingh-dimessional regression models [Montanari and Wu, 2023, Cui et al., 2024]. Closest to our work is Ghio et al. [2024], where the authors analyze the analogous of ASL within the stochastic interpolant framework [Albergo and Fanden-Eijnden, 2023] using the replica and cavity methods. They provide asymptotic thresholds for sampling by diffusion in several settings spanning statistical physics, statistics, and combinatorial optimization. Their formalism, however, is limited to so-called "planted"" ensembles, which allows avoid dealing with hard-to-compute normalizing factors Z in the denominator. We overcome this limitation by a double application of the replica trick, which significantly broadens the applicability of the approach. It worth also mentioning Ricci-Tersenghi and Semerjian [2009] for carrying out a similar analysis on the Belief Propagation-guide guiided decimation scheme for random SAT problems.
spin glass model for high enough
Perceptron Problems As applications of our formalism, we investigate the performance of sam- pling through ASL the solution space of random instances of two non-convex perceptron problems: the spherical perceptron with negative margin and the binary weight perceptron. These arguably the simplest neural network models whose solution space is non-convex and can therefore provide insights into the behavior of more complex multilayer models. The spherical perceptron with negative margin is a non-convex constraint satisfaction problem introduced in [Franz and Parisi, 2016] as a simple model of glassy behavior. The solution space has complex star-shaped geometry, recently
'This includes particular non non-planted problems that exhibit the "quiet planting" phenomenon and can be analyzed in the planted regime.
2

---

investigated in Annesi et al. [2023]. In the binary weights case instead, the analysis of random instances of the problem has long tradition statistical physics [Krauth and Mézard, 1989, Engel and Van den Broeck, 2001]. Most solutions under the uniform distribution are conjecturally algo- rithmically unreachable by a large class of polynomial algorithms due to the overlap gap property [Gamarnik, 2021, Gamarnik et al., 2022], since typical (according to the uniform distribution) solu- tions are isolated [Huang and Kabashima, 2014, Baldassi et al., 2023]. Hardness of sampling has been rigorously proven in the symmetric binary perceptron case [EI Alaoui and Gamarnik, 2025]. Nonetheless, efficient algorithms for finding solutions do exist [Braunstein and Zecchina, 2006, Baldassi et al., 2016a, Abbe et al., 2022], thanks the presence of a subdominant but algorithmically accessible dense cluster of solutions [Baldassi et al., 2015]. See Barbier et al. [2024] and Barbier [2025] for further explorations of the geometry of the solution space.
The main contributions of this paper are the following:
We introduce a formalism, based on the analysis of time-dependent potential, (g) obtained through the replica method, that gives exact thresholds in the high-dimensionality limit for efficient sampling through generative diffusion. Our method extends the presented in Ghio et al. [2024] beyond planted models by handling unnormalized target densities.
We show that in the non-convex spherical perceptron model, the uniform distribution can be efficiently sampled by ASL in a large region of the parameters that define the model (the load a and the margin x),, roughly corresponding to the Replica Symmetric region from replica theory.
In the case of binary weights perceptron, we show that the uniform distribution cannot be efficiently sampled, consistent with previous analyses. However, our analysis allows us to discover that ASL can sample efficiently from a distribution tilted by a potential U(s) = -- log(s). This provides the first controlled sampler for the solution space of this problem, with an algorithmic threshold of Orag a 0.65 for x 0, rather close to the sat/unsat transition at a, s 0.83.
We adapt the newfound potential inside a simple MCMC annealing procedure that provides fast and robust sampling from the tilted target distribution.
The remainder of this paper is structured as follows: process. Section 3 presents an asymptotic analysis of SL using the replica formalism. Section 4 discusses the application of ASL to perceptron problems. In Section 5, we provide conclusions and perspectives.
Section 2 introduces the Stochastic Localization
2 Preliminaries on Stochastic Localization
In this Section, we introduce the key components of the sampling algorithm based on the Stochastic Localization (SL) process. Given probability density p( p(w), with R. referred to as the target distribution, our goal is to generate samples from p. We assume p to be known, possibly up to a hard-to-compute normalization factor, and write it as p(w) v(w) Z. where we call partition function the normalization = dw (w)) and we call (w) unnormalized density.
Given the target density p. SL can be defined as stochastic differential equation (SDE) that goes from time / = to +0o for a vector h, e IR N which we call the time-dependent field. The SL's SDE is the analogous of the reverse process SDE in denoising diffusion [Montanari, 2023]. The initial condition is ho 0, and for 2 the SDE reads:
dh, my (h:) dt + db,
where (bx) is the standard Wiener process in N dimensions. The drift term m; is computed as the expectation
m& Ew-pp.
[w].
what call the tilted distribution Ph, (w), obtained by convolving the target distribution with Gaussian noise:
Ph,((w) (w) (ww) (h 1 2u
(4)
Zn.
3

---

The key feature of the SL process is that as t + +oo the field diverges and p: := Ph.. peaks around single configuration w" that is statistically distributed (over the realizations of the process) as sample from the target distribution p. that is we have
Pt w
w p.
(5)
Therefore, a sample from the target distribution p can be obtained as the value of m. (hr) at large times.
Bayesian interpretation It can be shown [Montanari, 2023] that at any time t 2 0, the solution h, of eq. 2 has the same distribution as
h = tan" Vig.
(6)
where w" ~ and ~ (0, Ix). This is similar to the forward process of denoising diffusion. The distribution pb..t . can then be interpreted as the posterior over wx given the noisy observation h The function (h;) corresponds to the Bayesian denoiser.
The ASL algorithm The Algorithmic Stochastic Localization (ASL) method use for given sampling task consists of discretizing time in the SDE eq. 2, running it up to a large but finite final time ty, and decoding the solution from h,, m,, (he, ). The denoiser m (he) is obtained using Approximate Message Passing (AMP) [Donoho and Tanner, 2009], an iterative algorithm that updates the estimated marginal until convergence. Therefore, we have double-loop algorithm in which, at each step of the discretized SDE, the inner AMP loop must be iterated until convergence. While AMP has limited applicability to real-world tasks and datasets due to its failure in handling correlated or low-dimensional data, in the synthetic settings addressed in this paper it provides a fast and efficient algorithm for Bayesian denoising tasks, conjecturally outperforming any other polynomial-time algorithm for large system sizes. Moreover, the fixed points of AMP are in one- to-one correspondence with the stationary points of the replica free entropy diseussed in the next section, making the behavior of AMP amenable to simple asymptotic theoretical analysis [Zdeborová and Krzakala, 2016].
3 Asymptotic Analysis of ASL with the Replica Formalism
We devise a formalism to investigate the asymptotic behavior of the ASL sampling process in the large system size limit N +0o. The formalism relies on the non-rigorous but well-established [Mézard et al., 1987] replica method. The main outcome will be criterion for the feasibility of fair sampling involving the evaluation of time-dependent free entropy. What follows is a generalization of the scheme in Ghio et al. [2024] that allows for handling unnormalized densities, such as the ones we will deal with in the next sections.
Given the target distribution p. which we assume to be stochastic and drawn from an ensemble of distributions (quenched disorder), the solution h, of the SDE eq. (assuming the drift term is correctly estimated) is distributed as h, tw" Vīg. where w" is sample from p-rrefered to as the reference sample-an g is standard Gaussian noise (see eq. 6). A relevant parameter for tracking the dynamics is the overlap
(t) (w", w.)-
We argue that this quantity, while fluctuating over the realization of p and of the SDE path, concen- trates for large N to a deterministic quantity. This quantity emerges naturally as order parameter in the replica computation that we now describe.
In statistical physics, the free entropy is central quantity because it gives access to key observables and characterizes the typical behavior of the system. our case, for a given time I, we define the asymptotic average free entropy (or just free entropy) as
Φ
lim No
Elog Zn..t.
(8)
where the expectation is computed over the realization of the target unnormalized density 1 over the reference sample wi (i.c., over the quenched disorder) and over the Gaussian noise g of eq. 6.

---

To handle both the (usually) intractable expectation of a logarithm and the sampling from an un- normalized distribution, we employ the replica method twice: we introduce s replicas of the target distribution to account for the normalization (using Z-1 lim " and n replicas for the tilted distribution to linearize the logarithm (using log Z = limm-o On "), and obtain:
6
lim 1 lim lim On g No
f
π vb (dw
I s (dwa) e elee
(9)
N s=On-0
where h = twi Vig is computed from wj. the first (a= 1) of the replicas w associated to the larget distribution, which thus has a special role. The replicas wa, on the other hand, have symmetric roles. The structure of this computation is closely related to the one presented in the seminal work of Franz and Parisi [1995]. In the dense systems considered here, the resulting expression depends on all pairwise overlaps among the n + 8 replicas, determined in the large N limit by a saddle point computation. To perform the n + 0 and [Mézard et al., 1987, Mézard and Montanari, 2009], that is, we restrict the saddle point evaluation to the most symmetric overlap structure under replica exchanges compatible with the symmetries of eq. 9.2 Moreover, thanks to the Bayesian structure of the problem, the Nishimori conditions [Nishimori, 1980, Iba, 1999, Ghio al., 2024] can be applied to further simplify the overlap structure by enforcing additional symmetries (see Appendix B.3). Under these hypotheses, the overlap g(t) of eq. 7 can be computed from the overlaps of replicas involved in eq. as
0 limits, we assume the Replica Symmetric (RS) ansatz
1 ((1) = 7 (w0 w.) N
(Way ws..
Va, be E [m] and # a.
(10)
At time f 0, all the n s replicas are equivalent, therefore q( = 0) = r, where r the overlap between two distinct samples of the target distribution: = (w,, w3)/N for o, E [s] and a B.
We further mention that while the Nishimori conditions found for the planted distributions analyzed in Ghio et al. [2024] guarantee the correctness of the RS ansatz, in our more general setting they guarantee only that the analysis of the tilted system doesn't 't involve further replica symmetry breaking (RSB) compared to the standard replica analysis of the reference systems. Therefore, our RS analysis is exact only in the RS region of p.
In general, the replica computation will arrive at an expression in which the free entropy de is expressed as the saddle point of a function of several order parameters, one of which is q:
max de (1(g).
( extr Φe (q,
(11)
where we denoted with 0 all the remaining order parameters except The value Jmax that maximizes (4) represents the typical value of qtt).
Success and Failure of ASL As shown in Ghio et al. [2024], the study of (g) can reveal whether the ASL sampling scheme can recover samples from the target distribution, in the large N limit. More specifically, the success of ASL hinges on the unimodality of (x(g) as function of q. If it has a single maximum at all times f, moving smoothly from low to q 1 (assuming |/ol22- N), then the AMP messages correctly recover (with high probability in the limit of large N) the value (t) = argmax, (e()) and the algorithm successfully samples from the target distribution. Conversely, if (g) becomes multimodal, it could be the case that AMP doesn't return the correct estimate of (h:) and the SDE integration fails. The mechanism is follows: at / O, there is always a maximum located at low g, which is the one found by AMP. As / increases, this maximum will in general move toward higher q. and AMP will follow it: however, if any ł there is second, higher maximum and at higher q, it should be the correct one that solves the saddle point equations, but AMP will miss it. As we show below, this can happen both if the global maximum exists from the outset or if it develops over time. See Fig. 1 (Left) for a setting in which a high g maximum first appears and then becomes the global one.
"This may limit the exactness of our results to certain regions of parameter space, but the methodology can be straightforwardly if laboriously eexteedully-extendedd replica-symmetry broken regimes.
brooee
5

---

4 Applications on Perceptron Models
4.1 Definitions
The perceptron [Rosenblatt, 1958] is the simplest neural network model, used for binary classification tasks. Instead of the usual optimization perspective, we adopt a constraint satisfaction one [Engel and Van den Broeck, 2001], and define a family of probability distributions over the solution space. The problem defined by a dataset X, containing M examples x" RN, and scalar x that we call margin. For simplicity, we assume all labels are equal to 1. A given weight configuration w E R is
called solution if all the corresponding stabilities, defined as s" (x" w) satisty st 2 Vj. We define a family of distributions over the solution space by the unnormalized density (from eq. 1):
(x),,),
vN
M (ww) P(w) II O (s* R) e [N) [[-1
with s" =x0 w)
(12)
VN
Here ((s) is the Heaviside step function, (s) = 1 if s > 0 and 0 otherwise. The parameter T 0 is called temperature, and we call potential the function (s). Notice that for U(s)= (or any constant) or for T - +oo, the distribution p(w)= s (w)//2 becomes the uniform distribution over the solution space. The distribution P(w) is a prior on the weights, possibly unnormalized. In the paper, we consider two different priors, corresponding to the spherical weights perceptron, P(w)= 6(1w [2 N), and to the binary weights perceptron. P(w) II, P( wx)) and P(w;) 5(m; 1) 0(w; + 1).
The perceptron problems are generated by considering i.i.d. examples x²' -O Ix) or xt -n) The two settings are equivalent for our asymptotic analysis. The high-dimensional limit is obtained for N + + and M + + oo with fixed finite load a = M/N. This statistical setting has been extensively studied in the statistical physics literature, see Engel and Van den Broeck [2001]
and Gabrié et al. [2023] for broad reviews.
4.2 Implementation of ASL
In order to adapt the ASL sampling scheme, discussed in Section 2, to the target distributions of the perceptron family as defined in eq. 12, we have to implement the corresponding AMP algorithm. The AMP fixed point provides approximation to the Bayesian denoiser m. (h.)) to be used to solve the Stochastic Localization SDE. Since eq. 12 can be seen as a specific type of generalized linear model, we can adapt the GAMP algorithm from Rangan [2011] 1] for our purposes. The message passing scheme is reported as Algorithm and discussed Appendix
4.3 Spherical Non-Convex Perceptron
In this section, we present the asymptotic analysis of ASL, considering the spherical case |w]|²= = N and uniform distribution, i.e. U(s)= 0 in eq. 12. In particular, we're interested in the case x since in that case the space of the solutions (if non-empty. i.e. for small enough a) is non-convex on the sphere [Franz and Parisi, 2016, Annesi al., 2023]. As discussed in Section 3, we characterize the sampling behavior by studying the free entropy oe as function of The replica calculation yields decomposition of the free entropy in terms of an energetic and an entropic components (full derivation in Appendix B):
@)(9. =
2 (fa (g) + fr + lg Gs( + +
(13)
2
( (Q-
(a- + (f- f- (/-rx+1))
f)- (
+1))
(5(1) 2 log(û -ad)
(14)
2( ra)
g5(4) = f DzDr Åh- (T 2 log 11 (w/r + (iV/+=/g-77 //))
(15)
The function A is defined in the Appendix, eq. 21. The overlaps g and r have the interpretation discussed in Section 3, with in particular being the overlap between the denoiser prediction at time t and the clean configuration. The parameters ④ and i are their Lagrange conjugates, and fa the conjugate for the norm constraint of the reference.

---

The parameters for the reference system, r, á and fd.. are independent of t, and q. They are determined upfront, using the saddle point equation obtained from the reference system free entropy (see Appendix B.4.5). Therefore, they play the role of external parameters in the above expressions.
The above expressions allow to derive (g) extry (1 i) and gain direct insight into whether the SL sampling scheme can recover samples from the target distribution asymptotically. The left panel of Fig. shows (2(4) as a function of q for different values of with parameters a 278 and = 225. Initially, ox (g) exhibits a single global maximum. However, a second local maximum emerges as increases, eventually becoming the global optimizer of Φt. discussed in Section this transition marks the onset of multimodality in the free entropy landscape. The central panel of Fig. 1 presents the phase diagram for the ASL scheme for a fixed margin K, delineating the different sampling regimes. For each point in the t-a plane, we test for the presence or absence of distinct local maxima by initializing the optimization of the (1:1) q) in eq. 13 at two different values of q, low and high, and checking whether the results coincide.
1.30
-1.235
0.04
10
-3.0
-28
710.0
7w0 01
4 sabiunsat
-1.245
1 03
10
d1R50
-1.250
05
3.00
-2.5
-2.0
-1.
-1.0
-0.5
0.0
overlso
Figure 1: Asymptotic analysis of ASL sampling for the Spherical Perceptron with uniform distribution. Left: Free entropy function de (g) for different values of t and for a 278, x -2.5. Initially, (: has single maximum, but as & increases, a second maximum appears, eventually becoming the global one. Center: Phase diagram of ASL in the t-vs-a plane for = -255. Green region: (1 has single optimizer, meaning the AMP succeeds at denoising. Yellow region: Φ1(9) has two optimizers, but the global maximum corresponds to the smaller overlap q. AMP still succeeds. Red region: (x)g) has two optimizers, but the global maximum corresponds to a larger overlap g. 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 a-vs-K 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 dIRSB line.
The right panel of Fig. 1 shows the region in the a-k plane where ASL succeeds. The figure also shows replica byrmetry- transition lines and the IRSB prediction for the sat/unsat transition line reported in Baldassi et [2023]. Notably, the samplability frontier of ASL coincides with the (DAT) line and comes slightly short of the dynamical 1-step Replica Symmetry
De Almeida-Thouls Breaking (IRSB) transition. This result highlights fundamental limitation: the SL algorithm fails to sample from the target distribution when Replica Symmetry Breaking (RSB) occurs, which signals the fragmentation of the solution space into disconnected clusters. In other words, ASL ceases to function as soon as ergodicity is broken. In the case of the DAT transition, ergodicity is continuously broken and ASL reaches the transition line. In presence of a discontinuous (dIRSB) transition, failure of ASL happens earlier. See Ghio et al. [2024] for more details of phase transitions in similar contexts and Mézard et al. [1987]. Mézard and Montanari [2009] for the generic RSB picture.
To validate numerically the uniformity of the ASL sampling, we compare the empirical distribution of stabilities s" obtained via sampling to the asymptotic theoretical prediction, which can also be obtained by the replica method. The derivation and the results are reported in Appendix C. The empirical results match perfectly with the predictions, the whole region where ASL successfully samples solution to the constraint satisfaction problem. This strongly suggests that the obtained samples are distributed according to the target distribution, i.e., uniformly over the solution space in this case, expected.
7

---

N00000
0.4
04
P(s)
02
0.1
8.0
0.625
6.675
Figure 2: ASL sampling for the Binary Perceptron with (s) = -loo(ss) potential. Left: Phase diagram of ASL in the f-vs-a plane for 0 and T 0.5. The color scheme is the same for the central panel of Figure 1. Right: Empirical distribution of the stabilities s" for configuration obtained by ASL in the case of binary perceptron with the log-potential, N 5000, k O, T = 0.5, and a 0.3. The black line is the asymptotic theoretical prediction. The excellent agreement shows that ASL produces fair samples from the target distribution.
4.4 Binary Perceptron
In this section, we analyze the samplability of the binary perceptron measure. We focus the margin case, K = 0. The replica analysis is reported in Appendix E; the final expression for the free entropy de (g:9) time is the same eq. 13, except for the entropic term, which becomes
Gs( Σ [DaDr w²==1
log (2e -((--a)) cosh (zv ++ TVF+ (4 (Q-F)w") ))
2 2cosh(rVF))
(16)
4.4.1 Selecting a samplable potential
Sampling fails for non-diverging potentials As stated in Section 3, ASL fails in the presence of second peak in the free entropy (e(g) that becomes the global maximum at some time. For the binary perceptron under the uniform distribution, i.e. with (s) O, (q) exhibits a permanent peak at 1 with an infinite derivative. for all a > 0 and all t > O. This observation is related to the frozen-IRSB nature of the binary perceptron [Krauth and Mézard, 1989], implying that most solutions are isolated, and it is consistent with the known hardness of sampling from the uniform distribution [Huang and Kabashima, 2014, El Alaoui and Gamarnik, 2025]. More surprisingly, this difficulty cannot be removed even by tilting with potential, unless it diverges at the origin, as we will now discuss.
To understand the origin of the peak at q 1, we compute der(a) for g= 1-e, with << 1 [Huang and dg Kabashima, 2014]. The computations are reported in Appendix F. For the binary case, the expression of the free entropy derivative takes the form:
(e)(()) dg
1 log 11a()+ac()c++00)
(17)
2
1-=1-e
where (c) is a function whose scaling with e depends on the explicit form of the potential Us)). As it turns out, unless Us) diverges at 0, C O(1) and is always positive, and as consequence the free entropy unavoidably exhibits peak at = at all > 0 and all a > O. The second peak becomes dominant large enough time, before the first peak disappears, leading to the failure of ASI. sampling.
Diffusion with Log-potential The only way avoid the peak at q 1 is let the potential Us) diverge at the origin. The choice Us) = - log(s) is particularly simple to analyze: in that case, C(e) O(ezt) and therefore the corresponding term C(e) in eq. 17 becomes negligible for
8

---

MCMC U(s)= -5 T-annealing
MCMC U(s) = -log(s) r-annealiig
1.0
N-128
0.8
N-256
0.8
2-2
N-512
5-512
Solving Prob.
0.6
N-1024
Salving Prob.
0.6
N-4048
N-24
4055
0.
0.4
0.0
0.
0.4
0.5
0.5
0.7
0.8
0.0
0.3
0.4
0.5 0.6 0.7
0.5
Figure 3: Results for the Binary Perceptron problem, showing the probability finding solution as function of constraint density or and for different system sizes N, after 100 sweeps of MCMC. Simulated Annealing on temperature T (left) is compared to our proposed and much more effective T-annealing scheme.
small e when T < 1. The derivative of the free entropy at q becomes dominated by the logarithmic term and thus (4) always has local minimum q = 1.
In this case, the phenomenology becomes similar to the one observed for the spherical perceptron case, shown in Figure 2 (Left): with the choice T 0.5. there is a whole range of a up to about Oaal x 0.65 that is samplable. The transition is close to, although slightly lower than, the best known algorithmic thresholds from heuristic solvers [Braunstein and Zecchina, 2006, Baldassi and Braunstein, 2015, Baldassi et al., 2016a,b) 6a.b], which are known to find solutions from sub-dominant dense clusters. our case, we sample from the dense cluster well, but contrary all solvers we are aware of, the solutions found are fair samples from a target distribution which is fully under control analytically. This is corroborated by the comparison between the empirical stabilities from the ASL sampler and the theoretical predictions, shown in Fig. 2 (Right).
4.4.2 r-annealed MCMC
Using the ASL algorithm in combination with the potential Us)) log(s), we are able to sample solutions of random instances of the binary perceptron problem. ASL, however, inherits the well- known limitations of AMP, generally failing to converge the presence of structured data, and therefore ASL should not be considered a practical sampling algorithm for generic perceptron problems. On the other hand, direct use of the log-potential in an MCMC algorithm is infeasible, since the potential is not defined on negative stabilities which means that one should initialize the MC chain from solution. As a workaround, we propose a reshaping of the potential inspired by the replica trick, which, given parameter > 0, is defined by
1 (1 (1-s)) 8*) U+(s) = (1
>> 0,
(18)
S 0.
Notice that lim,-u -logsss for s >> 0 and +o0 for s S O. We set p- (w) x e E,, U-(x") as algorithm, where each MC sweep we decrease
the moving target density of a Metropolis-Hastinn linearly т, starting with initial value 1 and down to 0. Keeping T fixed and with sufficiently slow annealing, we should be able sample from the solution space weighted by the log-potential. We call this procedure r-annealing. In Figure 3, we compare it with a standard Simulated Annealing (SA) on the potential (ss) =-s(--s), where the temperature T is decreased linearly each MC sweep from I down to 0, so that final samples at T' = 0 should be distributed according to the uniform measure for a slow enough annealing. While SA fails quickly when increasing N, the r-annealing scheme remains very effective at finding solutions. In the Appendix E.3, we present further experiments showing that, by scaling the number of sweeps as nsweeps N, we solve up to a 0.55 using r-annealing, while temperature annealing keeps struggling at large system sizes. We also note that, with r-annealing, the MCMC dynamics able to diffuse far in solution space, supporting the hypothesis that the algorithm targets a large, dense cluster of solutions. Experiments on real-world datasets reported E.4, also show improved performance of the --anealgnng scheme compared to other MCMC algorithms.

---

Conclusion
In this work, we investigated the feasibility of sampling solutions to perceptron problems via the diffusion scheme based on Approximate Message Passing, known Algorithmic Stochastic Localization (ASL). For the spherical perceptron, we showed that ASL can sample from the target distribution as long as the free entropy landscape remains unimodal along the trajectory, which holds for constraint density a = M/N below a threshold depending on the margin n. In contrast, in the binary case, the uniform distribution is always unsamplable. An investigation of the origin of the issue that prevents ASI. from working led us to introduce a potential (+))= = log(s) to bias the distribution. This enables efficient sampling over broad range of a values. This potential also leads to robust MCMC scheme, r-annealing, that overcomes ASL's limitations (inherited from AMP) on structured instances of the problem. Looking forward, similar analyses and tailored potentials could enhance sampling and solving in other hard constraint satisfaction problems, especially with isolated solutions. For instance, Budzynski al. [2019] propose different reweighting scheme favoring more stable solutions in the context of the k-NAESAT problem. Finally, a promising direction is to rigorously establish our results, particularly for the mathematically simpler binary symmetric perceptron Aubin et al. [2019].
Acknowledgments
CL. acknowledges the European Union - Next Generation EU fund, component M4.C2, investment 1.1 CUP J53D23001130001, and PRIN PNRR 2022 project P20229PBZR.
References
Emmanuel Abbe, Shuangping Li, and Allan Sly. Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 860-873, 873, 2022. doi:10.1 150.5111///1119555551100
Michael Samuel Albergo and Eric Vanden-Eijnden. Building normalizing flows with stochastic interpolants. In The Eleventh International Conference Learning Representations, 2023, URL https://openreview/ wwt.:e/e/tttoootee :ett://orrmmidd1117ggBBBtB
Brandon Livio Annesi, Clarissa Lauditi, Carlo Lucibello, Enrico M. Malatesta, Gabriele Perugini, Fabrizio Pittorino, and Luca Saglietti. Star-shaped space of solutions the spherical negative perceptron. Physical Review Letters, 131(22):223301, 2023. doi: 10. 1003/hysseell.c.om ett. wtt....1......... 31.227301.
Benjamin Aubin, Will Perkins, and Lenka Zdeborová. Storage capacity in symmetric binary perceptrons. Journal of Physics A: Mathematical and Theoretical, 52(29):294003, 2019.
Carlo Baldassi and Alfredo Braunstein. A max-sum algorithm for training discrete neural net- works. Journal of Statistical Mechanics: Theory and Experiment, 2015(8):P08008, 2015. 1121110088/17225488888 5/0.
Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses. Physical Review Letters, 115(12):128101, sep 2015. doi: 10.11003//yseeeeett. 115.128101.
Carlo Baldassi, Christian Borgs, Jennifer T. Chayes, Alessandro Ingrosso, Carlo Lucibello. Luca Saglietti, and Riccardo Zecchina. Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes. Proceedings the National Academy of Sciences. 113(48):E7555EEV)
2016a. 1oi:10.1073/pnas. 1608 103113.
Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Lo- cal entropy as measure for sampling solutions in constraint satisfaction problems. Journal of Statistical Mechanics: Theory and Experiment, 2016(2):023301, 2016b. 1.8880.008/1
5468/2001602/023301..
10

---

Carlo Baldassi, Enrico M Malatesta, Gabriele Perugini, and Riccardo Zecchina. Typical and atypical solutions in nonconvex neural networks with discrete and continuous weights. Physical Review E. 108(2):024310, 2023. 1o 103/PhysRevE. 108.0 108.024310.
Damien Barbier. How to escape atypical regions in the symmetric binary percep- tron: a journey through connected-solutions states. SciPost Physics, 18()):15, 2025.
1oi:10.21 4688SciiPsss 18.3....8...11... 18.
Damien Barbier, Ahmed EI Alaoui, Florent Krzakala, and Lenka Zdeborová. On the atypical solutions of the symmetric binary perceptron. Journal of Physics A: Mathematical and Theoretical, 57(19): 195202, 2024. doi:
Jean Barbier, Florent Kızakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová. Optimal errors and phase transitions high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 1 1 (16(12):5551-466) 2019, doi: 10. 10.1070/pnas. (073/pnas.18027055 1802705 116.
Alfredo Braunstein and Riccardo Zecchina. Learning by message passing in networks of discrete synapses. Physical Review Letters, 96()):33200, 2006. doi:10. www.PooyeeeLLee....oo..
Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of Markov Chain Monte Carlo. Chapman & Hall/CRC Handbooks of Modern Statistical Methods. Taylor & Francis, 2011.
ISBN 978-1-4200-7941- -8. doi:10. 1201/b10905.
Louise Budzynski, Federico Ricci-Tersenghi and Guilhem Semerjian. Biased landscapes for random constraint satisfaction problems. Journal of Statistical Mechanics: Theory and Experiment, 2019 (2)0023302, 2019. doi: 10. (488/1742-5688//b022
Patrick Charbonneau, Enzo Marinari, Giorgio Parisi, Federico Ricci Ricci-Tersenghi, Gabriele Sicuro, Francesco Zamponi, and Mare Mézard. Spin Glass Theory and Far Beyond: Replica Symmetry Breaking After 40 Years. World Scientifie, 2023.
Han Cui, Zhiyuan Yu, and Jingbo Liu. Sampling from the random linear model via stochastic localization up to the amp threshold. arXiv preprint arXiv:2407.10763 2024. doi: 1tt.:00..500/axx..440....
David Donoho and Jared Tanner. Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367(1) 4273 4293, 2009. doi: 1098//stt.2009.011...1
David L. Donoho, Arian Maleki, and Andrea Montanari. Message-passinn algorithms for com- pressed sensing. Proceedings of the National Academy of Sciences, 106(45):19114-1919 2009. 1o 100..1073//// 11w.:///...000000000 0909892106..
Ahmed El Alaoui and David Gamarnik. Hardness of sampling solutions from the symmetric binary perceptron. Random Structures & Algorithmss 66(4):c7002, 2025, doi: 102.0...02///AA.00222
Ahmed El Alaoui and Andrea Montanari. An inoomatton-thhoredee view of stochas- tic localization. IEEE Transactions on Information Theory, 68(11):7423 doi: 200.1100/1...022.31111
2022.
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Sampling from the sherrington- kirkpatrick gibbs measure via algorithmic stochastic localization. In 2022 IEEE 63rd An- nual Symposium on Foundations of Computer Science (FOCS), pages 323-334. IEEE, 2022. doi: 10.110.1100
Ronen Eldan. Thin shell implies spectral gap up polylog via stochastic localization scheme. Geometric and Functional Analysis, (3(2):332566) 2013.
Andreas Engel and Chris Van den Broeck. Statistical Mechanics of Learning. Cambridge University Press, Cambridge, 2001. doi:
Silvio Franz and Giorgio Parisi, Recipes for metastable states in spin glasses. Journal de Physique I 1995. doi: 101:1001551/pp11119999
France,

---

Silvio Franz and Giorgio Parisi. The simplest model of jamming. Journal of Physics A: Mathematical and Theoretical, 495141144000, 2016. do::10.1088/17511881344/9///
Marylou Gabrié, Surya Ganguli, Carlo Lucibello, and Riccardo Zecchina. Neural networks: From the perceptron deep nets. In Spin Glass Theory and Far Beyond: Replica Symmetry Breaking After 40 Years, pages 477-497, World Scientific, 2023. doi: 10w.1/8550//./...........
David Gamarnik. The overlap gap property: A topoloical barrier to optimizing over random structures. Proceedings of the National Academy of Sciences, 118(41)=210849221 18, 2021.
doi:10.
David Gamarnik, Eren C. Kızıidag, Will Perkins, and Changji Xu. Algorithms and barriers in the symmetric binary perceptron model. In 2022 IEEE 63rd Anmual Symposium on Foundations of Computer Science (FOCS), pages 576-587, 2022. doi: 10. (099FFO0S5445..2222.0000
Davide Ghio, Yatin Dandi, Florent Krzakala, and Lenka Zdeborová. Sampling with flows, diffusion, and autoregressive neural networks from spin-glass perspective. Proceedings of the National Academy of Sciences, 121(27):c231 18101111, 2024, doi: No0:10..073/ppas2211888 181001..
Louis Grenioux, Maxence Noble, Marylou Gabrié, and Alain Oliviero Durmus. Stochastic localization via iterative posterior sampling. In Proceedings of the 41st International Conference on Machine Learning (ICML 2024), volume 235 of Proceedings of Machine Learning Research, pages 16337- 16376. PMLR, 2024. URL attpss//proceeddngg mlr. www.sprssseeee......... secass/vv35//2 gresio//rexxxx2a... htmm..
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic mod- els. In Advances in Neural Information Processing Systems 33, pages 6840- 2020.
6851,
URL https://proceddings www.igg...uiis... wwwwrpp...cppapeeeeeeeeee 4cbcceesBB4440000011111000110aa0
wttpcc//ppppp..e htcppappr/22200000 paperr2220/hash/
Haiping Huang and Yoshiyuki Kabashima. Origin of the computational hardness for learning with binary synapses. Physical Review E, 90(5):052813, 2014. 10. (00/PhhyseeE..9005288
Yukito Iba. The Nishimori line and bayesian statistics. Journal of Physics A: Mathematical and General, 32(21))3875-388) January 1999. ISSN 1361-6447.
Werner Krauth and Marc Mézard. Storage capacity of memory networks with binary couplings. Journal de Physique, 50020):307733666, 1989. doi: 1055100.0111//0 /055//pphh00019990000000033
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009. URL https://wwwt cs.
toronto. edu/ wdw.eeeud//rr///e http//kriz//eeee httpe//eannnng-faattuee
2009-TR. pdf.
Yann Lecun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recogmition. Proceedings of the IEEE, 86(11):2278-233) -2224, 1998. doi: 10110/007679999
Yann LeCun, Sumit Chopra, Raia Hadsell, Marc' Aurelio Ranzato, and Fu Jie Huang. Energy-based models. In Gökhan Bakur, Thomas Hofmann, Bernhard Schölkopf, Alexander Smola, Ben Taskar, and S.V.N. Vishwanathan, editors, Predicting Structured Data, pages 191-246. MIT Press, 2007. doi: 1...10..55mmii /mppr/////ppe///444........
Mare Mézard and Andrea Montanari. Information, Physics, and Computation. Oxford University Press, Inc., USA, 2009. ISBN 019857083X. 1oi:10.1193/aa www.:////cpooooo0000001111111110
.0001.
Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro. Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9. World Scientifie Publishing Company, 1987. 1oi:10.1142/022
Andrea Montanari. Sampling, diffusions, and stochastic localization. arXiv:2305. 10690, 2023. 30.4
arXiv preprint
Andrea Montanari and Yuchen Wu. Posterior sampling in high dimension via diffusion processes. arXiv preprint arXhv:2304.11449 2023, doi: 20010044550//arx1.2344..44 11499.
12

---

Radford M. Neal. MCMC using Hamiltonian dynamics. In Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng, editors, Handbook of Markov Chain Monte Carlo, pages 113-162. CRC Press, 2011 1. doi:
Hidetoshi Nishimori. Exact results and critical properties of the Ising model with competing interac- tions. Journal of Physics C: Solid State Physics, 13(21):4071-4077 jul 1980. doi:10. 1088/0.0. 3719/13/210012.
Maxence Noble, Louis Grenioux, Marylou Gabrié, and Alain Oliviero Durmus. Learned reference- based diffusion sampler for multi-modal distributions. In Proceedings of the 2025 International Conference Learning Reprexentations (ICLR 2025), 2025. URL https: htttt:::////peeviiiii net/ furumnidd-f.JyymmMbbb.
Sundeep Rangan. Generalized approximate message passing for estimation with random linear mixing. 2011 IEEE International Symposium on Information Theory Proceedings, pages 1168-2172. IEEE, 2011. doi: 109/1SIT.201 1,6633999..
Federico Ricci-Tersengh and Guilhem Semerjian. On the cavity method for decimated random constraint satisfaction problems and the analysis belief propagation guided decimation al- gorithms. Journal of Statistical Mechanics: Theory and Experiment, 2009(09): 2009,
Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386 408, 1958. doi: 103.0000///00251199
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan. and Surya Ganguli. Deep unsu- pervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd Inter- national Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2256-2265. PMLR, 2015. URL https: https: https://prooeedingss mml. mlr press/v37/ sohl- fhnl-dickktein15 htmll
Francisco Vargas, Will Grathwohl, and Arnaud Doucet. Denoising diffusion samplers. In International Conference on Learning Representations (ICLR 2023), 2023, URL openreview net/forum?
id=8pynfTAbulf.
Francisco Vargas, Shreyas Padhy, Denis Blessing, and Nikolas Nüsken. Transport meets variational inference: Controlled monte carlo diffusions. In Proceedings of the International Conference on Learning Representations (ICLR 2025), 2025. URL https:://// //pprreviee/eeeeeee//// /Utpstttssss///pprrrrree net/forum?dd= PPirudnxiW.
Pascal Vincent. A connection between score matching and denoising autoencoders. Neural Computa- tion, 23(7):1661-1674 2011. doi: 10. 11..111.........11111111 a_00142.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. CoRR, abs/1708.07747, 2017. URL http: http://///xxv.or//bbbb.. 1708. 1708.07747
Lenka Zdeborová and Florent Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 65(5):453-55 5552,,5522222 2016. 000:0010000000003332220001111113
13

---

Appendix
Approximate Message Passing for the Perceptron
14
B Replica Computation for ASL on the Perceptron
15
B.1 General framework
15
B.2 Replica Symmetric Ansatz..
17
B.3 Nishimori conditions
17
B.4 Replica Symmetric Free Entropy
18
Computation of the stability distribution
21
D Spherical Perceptron
21
D.I Free Entropy
22
D.2 Reference system
22
D.3 Stability Distribution
22
Binary Perceptron
22
E.1
Free Entropy
23
E.2
Reference system
23
E.3
Other plots for 7-annealing
24
E,4 Experimental results for sampling binary perceptron solutions with Log-potential on
structured datasets
26
Limiting behavior of the free entropy derivative
30
F.1
Interaction term
30
F.2
Energetic term
A Approximate Message Passing for the Perceptron
In this Section, we present the Approximate Message Passing (AMP) algorithm used to estimate the drift term m, (h₂) in the Stochastic Localization SDE eq. 2. The AMP algorithm has to derived for the perceptron target distribution eq. 12, tilted by the observation of h, as described in eq. 4. The resulting p. (w) corresponds
specific case of the Generalized Linear Model family, therefore, the AMP variant we use is adapted from the GAMP algorithm proposed in Rangan [2011].
The AMP framework relies the definition of two key functions (din and @out), commonly referred to as the input- and output-channel free entropies, given by:
di (A, B) log ʃ P(dw) e BB
(19)
Pout (w, V) log f ds O(s O(s k)) e. {(((-a)) 6 w) w) 2V
log Hy (-W))),
(20)
V2
where
Ha(b)= = f Dr D20((b-a + Vaz)e [((-b-t(aa))
(21)
with the shorthand notation Dz ds
/2z 2"21 For the case U(s) 0, H simplifies Hb)b)
H ben ) with H(z) = er
x /2
In the binary weights case f P(dw) Eweet- For the
14

---

spherical case, the ||0|22 N norm constraint has to be relaxed to factorized Gaussian prior, P(w) = e 2m2 with 7 tuned adaptively during the AMP iterations. The relaxed prior is equivalent to the hard one in the limit of large N, but AMP can handle only factorized priors. As a consequence, the integral in @i can always be computed in closed form. Furthermore, for some choices of the potential (s), notably (s) = 0 and (s) - log(s), the integration in @out can also be carried out analytically. Therefore, the AMP used in the settings discussed in the main text quite fast since it does not contain any integrals.
The full set of the AMP equations is given in Algorithm 1.
Algorithm AMP for ASL on the Perceptron model
Imput: Data X (ax") M R MxNN ASI. time 2 0 and field h2 c RR <>> 0, K Set mn". A Vo, w. Equt: Pia, A", B², Aiters and le 0
while not converged on m² and A' (number of iters = K or Aiter < do
Update mean and variance estimates wa,, Vya:
(x")²²
Σ
4
(22)
N
w Σ
k-1
V k-1
(23)
Update estimates A., B., 9p
g/ Aomu (ut Vit)
(24)
4 Σ (v!1)
O² done (wit vo))
(25)
N
B Σ
m.
(26)
Only spherical case: enforce norm constraint solving eq. 29 for 7. Update marginals m; and A,;
m 0g, din 1 + t. 13. he,s
(27)
A Sb den
A + e, B, + ho,e)
(28)
Aisur + |m=* A-1 |2/N and & 1o
end while Return: Converged marginuls vra. 8 and A
In the case of spherical perceptron, the algorithm enforces (in expectation) the norm constraint / = N by assuming a unnormalized prior P(w) = e &yn?" and then solving for yy the equation
-2 -2Σ 0, (A) + B, he.)) NN i-1
(29)
in each AMP iteration using a root-fnddngg algorithm. Notice that yy appears implicitely in Φin defined in eq. 19.
B Replica Computation for ASL on the Perceptron
B.1 General framework
In this Section, we outline the key steps of the replica calculation used to derive the time-dependent free-entropy Φi of the Stochastic Localization process, as outlined in Section 3. The formalism is applied to the general perceptron model given in eq. 12, and then specialized on the spherical and binary case in Appendix D and Appendix E respectively.
We assume M = aN Gaussian-distributed examples, X (x*) 3,M x - (O) The weights will have a factorized prior P(w) = II: P(w:), where we slightly abused the notation. The case of the factoriieee global spherical prior will be handled naturally by setting P(w) 1 but then constraining the diagonal overlap instead of optimizing it, as explained later.
15

---

We want to compute the free entropy at time of the model in eq. 12 averaged over the realization of the sample and the noise in the SL process (eq. 6):
Φi lim
Elog Zm...
(30)
N
This computation is performed using the replica trick twice (the second one used express the expectation over the reference configurations):
E log Z lim 0,
and
Z-1 = lim Za=1
n-+0
We can thus write
sb (dw., w.b Φ: lim lim lim On Esgg f I v (dw No+
12 II a=1
(31)
N s-On--
o=1
where h, /wi + Vlg, with g NN IN). For convenience, we define the replicated partition function
vb (dw,) wa)e, T Il
II (dw) a=1
(32)
For the model in eq. 12, the expectation reads
EZZ Ex,g S H P(dw a II P(dwaa) I Σ I +
2
Wasty
Σ
(33)
N
N
a=l
uce
x e Eui wi was Eus Mewass ffr Eui wis
(34)
where the realization sa depends from the realization of the dataset X, and defined as
Ó(s) 0(s -k) k) - (U(--N)
(35)
Here (s)) is the Heaviside theta function. Introducing X = E, 10 and 2 Σ, a conjugate Lagrange multipliers, we obtain
and their
EZA =Ex,g ʃ I P(dw II P(dwa)) II dyydaa
duf
I (w(t
(36)
2m
2n
a=1 x
a=1
40
pa
Ema S
Ay "
E, nan
Masatt Jx
+t E.s
ui,
wast
/
91 Wa
1 EtEt wa
(37)
It is now possible to compute the average over the dataset X and the Gaussian noise g, obtaining
EZI
ʃ I ((dw") ) a=1
II P(dw.) a=1
II dAgdia
du
[ (
(38)
2T
2x
Eme An AMAR-1 E Wha E., wi, wast f Ens
E. u
(39)
t (E. AgAge wh of ay was us Ene Ay Syarw war)
(40)
We now introduce the overlaps
Gab
N Σ WatWhi;
Tag
N E
Paa
Σ
W Wai:
(41)
N
where qob is the overlap between replicas of the tilted distribution, Fag overlap in the reference system, and Paa is cross-overlap between reference and tilted system. We also introduce the conjugate parameters ÿoh, fa.. Poa enforce their definitions.
The overlaps foa and Too will be fixed to 1, since |w,,]/2 = N in both the spherical and binary case. For the spherical case, the diagonal multipliers qaa will have be optimized, while their value will be irrelevant in the binary case.
16

---

With the introduction of the overlaps, and using the factorization of P(w). we can write
EZI
P (dw as)
II P(war) II
dr drasdras as Il
dqubdgab II
daaa
(42)
n-1
a-l
as,
asb
04
x xe NN Eas Pastas- AN ANE Eas Aab9ab-N E PaaPan
(43)
x Ena far E, whe +t J Eas Has En was wast Enn Poo Ex w Was
(44)
dy
duddin
(45)
2x
2x
pace
Ma
JACK
x Eua An - Eua af +AN Plat Eab 2ab 3 Ea Sea
(46)
x Ep (E.o Aoor Ens ag auo E An Paa)
(47)
Site-dependent and denteded terms are now decoupled and factorized, A few more straight- forward steps lead to the following expression, amenable to saddle point evaluation:
EZ,
{ π as8
dragdñad ad π daa I ddoadpac Noo
(48)
where
$ G G aGE
(49)
1
1 3'Enn
G
Σ
Pastap
aB
Σ
Jaslab
EooaPaa + Epla -1
lab Σ Gaas
(50)
2 0i
2 ab
ab
Gs =log
II P(dw
II P(dwa) e² fasw, wa+ Eub wob Ina Daa W/
(51)
a=1
a=1
d
du, dú,
Ge log
( (T)(a))
2T
2T
(52)
- A. A Ba Eas Andara Eas á. Aagannn Eaaggn-Ennn SahaPas
As it is usually done in the replica method, we will first choose an Ansatz for the structure of the overlaps, so that we can perform analytic continuation and take the small n and s limit, followed by saddle point evaluation.
B.2 Replica Symmetric Ansatz
The Ansatz (RS) choose is the Replica Symmetric one. Given the symmetries of the problem, it takes the form
9d =1
a =
Fa = 1
a= - B² Poo
(p" a= p
Gab
b TaB
(53)
9
1.
The Nishimori conditions discussed the next Section guarantee that if the RS ansatz is correct for the reference system, e.g. s it is by definition for the spherical perceptron in the RS regime, then the RS ansatz above will give a correct prediction for dr. More generally, the correct Ansatz for tilted system has the same number of steps of symmetry breaking as the correct one for the reference system.
B.3 Nishimori conditions
Thanks to the Bayesian nature of the problem, the Nishimori conditions apply [Iba, 1999, Nishimori, 1980]. They are set of identities that we will to further simplify the overlap structure. We will state the identities in our context and review their derivation.
Let's fix the time t. and also fix the realization of the disorder in the distribution p (i.e. the realization of the examples X). Assume w² p, and call h tw" Vtg, with g standard Gaussian, the
17

---

observed field (as in eq. 6). The corresponding posterior over w is Ph..: given in equation eq. 4. For convenience we drop the time index and write = h, and p(w[h) Ph.e( w).
Given i.i.d. samples from the posterior, wy ~ p( (w)),, given a continuous bounded test function f: R. RxN IR, the following identity (Nishimori identity) holds:
Enw Emsl E (we)) Min
s(ww", w2,....;; wxx = Ens Enjw (anw:((we)) (wx)) [i, f(w), ; wx)
(54)
In order to show this, fixing 2 for simplicity, we rewrite the l.h.8. of the previous equation as
E f(w", w2) f dwo ch dwz ((a"")))(""")
w2)
(55)
f /wo dh dw2 P(h) (())"("))()>>)))))))))))))))))") w2),
(56)
where we used Bayes' rule. The r.h.s. instead can be rewritten
f dw dwn duz2
E s(wi, w2)
(57)
= =f dh dw2
W2).
(58)
The s.h.s. and the r.h.s. of eq. 54 are now clearly shown to be the same, once we rename w" to W1- We can eq. 54 to establish identities among the overlaps appearing in the replicated free entropy 4, of eq. 49. In fact, within the RS Ansatz, assuming large and at saddle point, consider the overlaps
p" (w) wo) N
(Wa, u7b
bbe [n]]
q
Va.be[n].or
(59)
Since in the replicated partition function w, and wr independent samples of the posterior contiditional on wi, the Nishimori identities imply
p
(60)
Now consider the overlaps
(w wa) N
(w w')
Va [x)
Vo e (s), B.
(61)
N
Since wa is decoupled from w when + O, its distribution is the same reference configuration when wi is traced out, therefore we have
p p=r.
(62)
Similar reasoning can be applied the conjugate order parameters, that we obtain:
4 p = f.
(63)
(64)
These conditions simplify considerably the expressions in the computation of the free entropy. The Nishimori conditions can be also used within Replica Symmetry Breaking (RSB) scenarios for the reference distribution p. They guarantee that no further RSB steps are needed in the analysis of the tilted free entropy Φi-
B.4
Replica Symmetric Free Entropy
B.4.1
Entropic term
Let's first look at the entropic term Gy within the RS ansatz:
-s-log log
I P(dw:) ) II P(dw,) et((fa-r) wi (f wz
(65)
a=1
==1
x xe* + (Wa-0) E. w (0-D)) --(00--) E. w. (EE + w.)²
(66)
18

---

Using the RS ansatz, and the Nishimori conditions, this simplifies to:
Gs log
[ II P(dw") a-1 x xe* (Fr-()) E. 104++99-0000 w.,) En we 1 t.. E. m.,)?
A II o=1
P(dwa) e)(a==)) Ea "
(67)
(68)
Using the Bubbard--Strtonovve transformation twice we can get rid of the quadratic summations like (Ea wa)² in the exponentials, at the cost of introducing two extra integration variables:
Gş = log f II P(dw II P(dwa) f DzDy (f "2 a-1
(69)
a=1
x (f( En - w. (a+(ftt)u W. wht wa)
(70)
where we used Dz dz 1212 factorized:
as a shorthand to denote a gaussian integral. This can now be V2x
Gs log f P(dwi) f DzDy cdtrt +n bat
(,,"
(71)
where
2(wi,2,7) = f P( (1V 2 (x,,)) f P(dw" ) (e
(72)
(73)
(74)
The last step of the replica computation consists in performing the limit n and 0, which enables to obtain the final expression of Φx:
9s ()) lim lim G,
(75)
+0n-~ n-
The final expression of the entropic term depends on the prior the weights. Its functional form reported in section D and E, respectively for the spherical and binary perceptron cases.
B.4.2
Energetic term
Let's now focus our attention on the energetic term
di
du
Ge = log
O (
(76)
2TT
2T
x e -1 E. Aaaa-i E. ha un - Eas daderas- 1 Eas dh Easaa-Eas dn la Paaa
(77)
After using the RS ansatz over the overlap parameters, the Nishimori conditions, and some manipula- tions the energetic term simplifies
G = log
[ II
dAa
du
I (A,,) (A))
(78)
2T
2π
e - En 3ado-i -EE aave- (1-r) En 82 --
(79)
(1- E. 6 F(E. Ea R.) 2- ( ao)²
(80)
We use again two Sulbbard-Stratonovvie substitutions to make the integrand factorized in the and indices, at the cost introducing two more gaussian integrals:
GE = log S
du
Dz D2D7 Dy
I (
(81)
2T
2m
xe -E, (Aa (us
(82)
xe - -((11)) En 18 -i
(83)
19

---

Finally, collecting the factors and taking the limits for n and - 0, we arrive at
(E(4)= lim lim Gn 000
(84)
= ff DzDr H1-9
log (TVF+
(85)
(1-((11))
where
(b)b) = f Dz O(-b-- Vaz)e +
(86)
In the uniform measure case U(s) = 0, simplifies to Hb) = H( bor with H(x) = Se 1.000 D==
errf
I
/2
B.4.3 Interaction term
Finally we compute the interaction term
1 Σ FaoTaB -
1
t
G -1=-2 ng
Σ
Aus4ab PeaPPa + ΣE Ple +
=t Σ lab
Σ
gear
(87)
2
2
ab
which, after using the RS ansatz, the Nishimori conditions, and taking the limits n and reduces to:
1 fr 20
1 2 2t
9 lim lim d,G,,= 500
(88)
B.4.4 Saddle Point Equations
The optimization of de can now be performed using the saddle point method [Mézard et al., 1987]. This amounts at solving the following system of equations
i + 20r Gm(g),
(89)
0q
q = 2 0 0q
(g)
(90)
The optimization is usually performed iteratively, starting from an initial guess, inserting it in the right hand side, obtaining updated values, and iterating until convergence.
It is important to point out that the overlap parameters for the reference network are not obtained from the free entropy expression derived above; rather, they need to be determined independently from an analogous (but simpler) free entropy expression that only involves the reference replicas. The procedure schematically shown in the next section, and the full computation is reported in Engel and Van den Broeck [2001].
B.4.5 Reference system
The free entropy associated to the reference system is simply that of standard perceptron problem, which is well known and can be found in Engel and Van den Broeck [2001]. The equations of the overlap parameters depend only on (r, fa). This results from the Bayesian structure of the problem: the reference probability measure is independent of the tilted one; for this reason, the reference free entropy independent of q. One can recover the expression of reference system free entropy (lr) (r, f,) fixing and taking the limit s - 0 of &,, in eq. 49. The RS expression reads:
(r, g( (r.f,f) + o (f, fv) (t)
(r),
(91)
(r, (ré- fa),
(92)
(P, log (ʃ P(dw" (itu")ee000t)) 2mVBF"))))))
(93)
gl (r) f BologHr-rr (Vrz))
(94)
20

---

given target stability 8, the average ö(s s²") over all patterns and all solutions sampled from the The corresponding saddle point equations, that can be used to determine r, f and Pa as function of and K, are:
0
0 (f,
1
(95)
Of
0 (r)
0i 9
(f,fa):
(96)
== 20 g()) (r).
(97)
dr
Our treatment differs from the standard one present in the literature only by the addition of the potential (s), which however only affects the energetic term and is fully absorbed in the definition of the H function.
C Computation of the stability distribution
In this Appendix, perform the computation of the stability distribution in the perceptron problem with an arbitrary potential U().. This is a simple generalization to include the potential a standard calculation that can be performed with the replica trick Engel and Van den Broeck [2001].
Given an v-diimensional weight vector w, representing a solution of the perceptron problem with
margin K, and pattern x", the stability is defined as s = (w.w=)) Our goal is to compute, for
vN
target distribution p (eq. 1), and subsequently average over all realizations of the patterns:
M Σ
P(s) = Ex
8(s-
(98)
M
Since all patterns are statistically equivalent, we can just compute the average stability of the first pattern:
P(s) Ex Ex- 5(s s²).
(99)
We now expand the formula using the definition of p (w) in eq. 12:
P(s) = Ex f P (dw) I ô (ss*)((s-)) P ((dw)) θ (s")
(100)
where will also used the definition of Ô in eq. 35. In order to take the expectation, we introduce replicas, with n integer at first, and to be sent zero through analytical continuation, so that we can rewrite the denominator as Z-1 lim =n- We give special role to replica 1, and obtain the formula
S P
II é ( (w x²*) ))) 1 VN (
(wi,z²))
(s) = lim Ex R-0
(101)
p.a
The computation can then be carried out usual, leading to the free entropy of the reference system
in Section B.4.5, followed by saddle point evaluation. In fact, the observable 8 VN
(1), x'))
being subdominant does not influence the saddle point. Given the stationary values of the overlaps, one can then obtain the RS expression for the stability distribution, given by
(
(()) = Os)
1
f
DI. 6
(102)
2T (1 (1-r)
Hr-, (Vrt)
where 1 has been defined in eq. 21.
D Spherical Perceptron
In this section, we consider the spherical weights case, in which the prior is P(w) 8([1w]|12 NN.
21

---

D.1 Free Entropy
We obtain the free energy by specializing the entropic term eq. 51 to the spherical prior, which together with eq. 50 and eq. 52 gives:
0c Q) = 9r(9.9) 9) + (g( aGE(1)
(103)
1
91 = - fd- qq + fr tg
(104)
2 2
(q- (4 (²-
F +
Gs(() 2 log(# fa) 2( - fd)
g 2F
(105)
(f-
(f - fd)
f-
DzDr H1-9 (yvF+ + 2-7-)
9x(() ʃ
log H1-6 (2/r+ + =
(106)
H1-r (7VF)
D.2 Reference system
Once the prior for the perceptron model is specified, the free energy equations for the reference system become the following:
(r,f,)) 0 ( (r,f, +
0 (F, oo
(107)
(r,,fa)) (rf-
(108)
d (r, 2 log(2T) - log(f- fff) fa) + (f (f-fa) fr)
1
-
(109)
gf ( = f D2 log H.., (Vrz).
(110)
They are obtained by specializing the entropic term for the reference system in eq. 93 the case of spherical perceptron prior, together with eq. 92 and eq. 94.
D.3 Stability Distribution
In this section, we present the distribution of stabilities computed through ASI, and we compare them with the theoretical expectation, whose derivation is provided in Section C. The distribution of the stabilities for U+)) O is reported in Fig. 4 for K = 2211 and several values of a [5, 20, 80).
1031
1031
0.7
0.5
2
0.3
0.3
Figure 4: Distribution of the stabilities s" of spherical perceptron with negative margin, where
8 (w. ) For number of variables N 1001, A -2.1 and a 5 (Left), a 20 (Center) and
V/ N
a = 80 (Right). The empirical distribution of the stabilities of the ASL samples (blue) coincides for different parameter regimes with the distribution computed through replica method (black solid line).
E Binary Perceptron
In this section, we consider the binary weights case, in which the (improper) prior is P(w:) 6(w; 1) 5(w; + 1).
22

---

E.1 Free Entropy
We obtain the free energy by specializing the expression for the entropic term in eq. 51 to the binary prior, together with eq. 50 and eq. 52:
- - g5(()+ + +gg((1),
(111)
eivte"
9s(9) Σ ʃ D2 200sh((7/F) log (2e cosh (aV f+ WVF (g (q-f)w")
=-=+1
(112)
H1-4 (7V++2/9-7
9F(()= = ʃ DzD7 11 (7VF)
log H1-9 (7VT =
(113)
1 1
91 = 2 fd 99 + fr 14..
(114)
2
2
E.2 Reference system
The free energy equations for the reference system the following:
(r,,,t)))))) of (r, g (F.fa) (g (r),
(115)
9f (r,A,a) = 1 (ri-fa) - rt);
(116)
2
g (F, = -f (A- fa)+ f Dzlog (2cosh (=vr)),
(117)
0 (r) = D Hi-r (Vrz).
(118)
where we have specialized the entropic term in eq. 93, together with the interaction term and the energetic one in eq. 92 and eq. 94. As a side note, we may observe that in this case the fa order parameter simplifies away with the expression of the interaction term Gr, in both the reference and the tilted systems. This is expected since in the binary case the norm fixed automatically. We keep this term in the expressions only for uniformity of notation.
E.2.1 Replica results for the binary perceptron under the uniform distribution
We investigate the output of the replica formalism for the binary case under the uniform distribution, i.c. with (s)) = O. The left panel of Fig. 5 shows the free entropy Φx(g) as a function of the overlap q for different values of with parameters a 0.5 and k 0. The phenomenology observed in this case is completely different from that observed for the spherical case: for all and all t there is always a second maximum at q = 1. Even though it is not always evident from the plots, we showed analytically that that is indeed the case, see Section F. As shown in the figure, the maximum at q 1 eventually becomes the global one for sufficiently large while there is still lower-q maximum. As explained in Section 3, this implies that during the sampling procedure the information on the target not correctly reconstructed, leading to the failure of ASI.. The phase diagram shown in the right panel of Fig. 5 shows that this phenomenology is present for all a 0.
23

---

030
163
0.00
0.9
Cemolrg Fiped sersing
overlap
Figure 5: Left: Free entropy (4) for the binary perceptron problem for several times. For all 4 the curves have local maxima: at low q that grows with I, and persistent Eventually, the persistent one becomes global, while the lower-q one is still present, which leads to the failure of ASL. Right: Phase diagram of SI. sampling for the binary perceptron. At all the situation is like the one in the left panel: there is a region of t where the lower-q maximum is not the global maximum (red regions) and sampling fails, even though eventually the lower-g maximum eventually disappears (green regions).
q 1.
E.2.2 Experimental results for sampling binary perceptron solutions with Log-potential random data
In Figure 6, we report the probability of sampling correct configuration from the binary perceptron loss measure with the log-pou tog-potential, for T 0.5, using the ASL sampling scheme. The asymptotic algorithmic threshold of a 0.65 predicted by the RS replica theory (see the left plot in Figure 2) seems consistent with the large N extrapolation of numerical data. Finite size effects are quite strong, though, and cannot rule out small gap due to RSB effects.
N1000
N5000
Probability sampling
0.8
N8000
0.2
0.50
0.52
0.54
0.56
0.58
0
Figure 6: The probability of sampling a solution satisfying the binary perceptron constraints with the ASL. algorithm as a function the constraint density a from a measure with the nog-potential with T' 0.5. Each point is averaged over 250 simulations.
E.3
Other plots for r-annealing
For the r-annealing scheme described in Section 4.4.2, we show in Figure additional experiments with different values of the number of MC sweeps, eventually also scaling them O(N). Similar experiments but with the potential U(s) = s0(-s), and annealing the temperature T instead (from I to O, linearly in the number of sweeps) are presented in Figure 8. It is important to notice that T-annealing on (+) -=((=s) fails large also when scaling the number of sweeps as N, while the 7-anncaling reaches an algorithmic threshold of 0.55.

---

MCMC U(S) -lgg() baaneallnng nsweeps-100
58
p700 s0h
W=4020
N=0122
5.0
0.3
0.4
0.5
0.5
6.7
MCMC Uts) -lgtss r-annealing nsweeps-200
Ne64
1-122
58
2-254
N-512
prob s01e
5.8
MCMC Uts) logis) e-annealing nsweeps-N
W-128
2-256
1924
prob K01
2010
MCMC lagls)
r-annealing
0-0.5
pieb sol
525
55
0.2
98.00
Figure Probability of finding a solution for the r-annelled MCMC scheme in the Binary Perceptron, with 7 = 0.5.
25

---

MCMC 01s) <8X T-annealing nsweeps-100
R-:54
8=220
-55
Rw022
Nw1224
MCMC T-annealing nswaeps-200
1.0
Nw512
R=1224
0.6
T-annealing nsweeps-N
1.0
0.5
0.6
0.4
02
0.0
5.5
0.4
2.5
5.
Figure 8: Probability of finding solution for the Tannneleed MCMC in the Binary Perceptron with potential U(s) = s-ss...
E.4 Experimental results for sampling binary perceptron solutions with Log-potential on structured datasets
In this section, use the a-annealing scheme to perform binary classification on structured datasets. We consider three different datasets: MNIST [Lecun et al., 1998]. FashionMNIST [Xiao et al., 2017]. and CIFAR10 10 [Krizhevsky and Hinton, 2009]. For each of them, we choose two classes and assigne to them the labels {-1,+1). We then compare r-anealling scheme with Simulated Annealing on few losses.
E.4.1 MNIST dataset
MNIST patterns classification: We considered the classes 3 and 8. We constructed binary perceptron architecture with N 784 units (the MNIST image dimension 28 x 28), and we run the 7- annelaing procedure with the log potentaaaia,,, with nsweeeps in (100, 784) and T 0.5. The results have been compared with the -nanealing MCMC schemes with potential U(s) b) 0(s) or U(s) (s), with the same number of MCMC sweeps. The results reported in Fig. 9.
26

---

MCNCIMNIST) nswesps (digts
MCMCIMIIISI nzwoops (digit 3,
1.20
LXV1 -000
1.2
Ual 2010)
0.75
pro6 50
1/2
Figure 9: Fraction of correctly classifying MNIST patterns, i.c., the fraction of instances producing zero classification error on digits and 8, as a function of M//N. The number of different problem instances is fixed to 100 (the error bars represent the standard deviation estimated over the 100 instances). The number MCMC sweeps fixed to 100 (left) and 784 (right).
Linearly transformed MNIST patterns classification: The analysis be performed in the case in which the patterns that the binary perceptron needs to classify are not directly the MNIST ones, but obtained by applying linear transformation the MNIST images. Given {x" vy), data in the MNIST dataset, i.e. xx IR with D 784, and y" R. apply linear transformation to the patterns xe using a projection matrix F e R NxD so that binary perceptron needs to classify " Fx The entries of the projection matrix
i.i.d. sampled from Normal distribution, i.e. Fiy (0, 1) Vi E (I,...,N ]} Vj E (L...., D). In this case, the number of MCMC sweeps has been fixed N, and the number of considered instances is 100. In the case of the anancalling results with U (s)) - (s),s), the temperature has been fixed to T = 0.5. The results are reported in Fig. 10
and Fig.11.
MCMCIMNISTI nsweeps 32 (digit 3,
MCMCIMNISTI noweeds N (digts 3.
405
(81)
0.73
pro0 50Ve
g70b sole
0.58
0:52
0.23
0.23
6.00
6.03
05
3.2
Figure 10: Fraction of correctly classified MNIST patterns (digits and 8), as function of M/N. The number of different problem instances is fixed to 100, and the number of MCMC sweeps fixed to N with N 32 (left), and 64 (right).
27

---

MCMMIMISTT nEwceOs tolghts
noweeps
loigts
3.00
LXS (000
1.0
2012)
0.75
pr06 50
603 3.25
0.50 0.75
Figure 11: Fraction of correctly classified MNIST patterns (digits 3 and 8), as a function of a M/N. The number of different problem instances is fixed 100, and the number of MCMC sweeps is fixed to N with N 1024 (left), and N 2048 (right).
E.4.2 FashionMNIIT dataset
FaSHionMNIST patterns classification: A similar analysis to the previous one has been performed on the FashionMNIST dataset, where we considered classes and We constructed a binary perceptron architecture with N 784 units and ran the annealing procedure with the log -potential, using nsweeps MCMC sweeps in { (100, 784] and T = 0.5. The results have been compared with the 7 annealing MCMC schemes with potential U(s) ((s) or U(s) -sQ(s), with the same number MCMC sweeps. The results are reported in Fig. 12.
MCMC(RushioMH ST) nsweeps ldigts 5,7)
MCMCCRSSNOOMNETT, noweeps jdigis 5,
1.20
-5200
(10) -gg0
2010
0.75
prob 50
2.4
0.0
Figure 12: Fraction of correctly classifying FashionMNIST patterns, i.e., fraction of instances producing zero classification emror on digits 5 and function different problem instances is fixed to 100 (the error bars represent the standard deviation estimated over the 100 instances). The number of MCMC sweeps is fixed to 100 (left) and 784 (right).
M/N. The number of
Linearly transformed FashionMNIST patterns classification: Analogously to the MNIST case, for FashionMNIST, we computed the fraction of correctly solved instances as a function of a M/N, the case in which we try to classify the linear transformation of the patterns, via the feature matrix F, (i.))__,...M.. As in the case of the MNIST dataset, the number of MCMC sweeps has been fixed the temperature for the T annealing scheme 0.5, and the considered classes are and The results reported in Fig. 13 and 14g.
28

---

McCCCFaSNONNNIST nsweeps (digits 5.7)
MCMCIFasNioNNN (S)) reweeps (diglts 5.
1.00
LX1 -200
1.00
2010)
0.75
0.75
pro6 50
1.0
0.0
20
Figure 13: Fraction of correctly classified FaSH patterns (digits 5 and 7), as function of M/N. The number of different problem instances is fixed 100, and the number of MCMC sweeps is fixed to N with N = 32 (left), and N 64 (right).
MCMCITishonMMWSST noweeps (digits 7)
NEMCCTeshonNNISST noweeps (digits
1.00
100
211 1e:0mm-0000 oggo)
0.75
0.71
proa sol
prob solv
0.98
693
0.25
0.30
3.00
Figure 14: Fraction of correctly classified FashionMNIST patterns (digits 5 and 7), as a function of M/N. The number of different problem instances is fixed 100, and the number of MCMC sweeps is fixed to N with N = 1024 (left), and N = 2048 (right).
E.4.3 CIFAR10 dataset
CIFAR10 patterns classification: A similar analysis to the one performed for the MNIST and FashionMNIST datasets has been performed over the CIFAR1O dataset, where we considered the classes 3 and 8. We constructed a binary perceptron architecture with N 3072 units (the dimension of the CIFARIO images 32 32 for different color channels), and we ran the annealing procedure with the log potential, with nsweeps (1000, 3000) MCMC sweeps and T 0.5. The results have been compared with the T- annnealln MCMC schemes with potential U(s) O(s) or U(s) (s), with the same number of MCMC sweeps. The results are reported in Fig. 15.
29

---

nowesps (digtts
nswerps (dight
1.00
LX11 -000
1.2
(010)
0.75
pro6 50
0.1
Figure 15: Fraction of correctly classifying CIFAR patterns, i.c., fraction of instances producing zero classification error on digits and 8, as a function of M/N. The number of different problem instances is fixed to 100 (the error bars represent the standard deviation estimated over the 100 instances). The number of MCMC sweeps fixed to 1000 (left) and 3000 (right).
Limiting behavior of the free entropy derivative
In this section, report the analysis of (g)x(4) as q 1. We set q and expand for small 6, leading to the results reported in 4.4.
The starting expression is:
(1( = 2
(fa + (q) + fr tq 9s(() + (
(119)
and its derivative is:
dø --q dg
(120)
dg
dq
We consider the two terms separately.
F.1
Interaction term
We start from the first (interaction) term. The dependency of on c can be determined from the saddle point equations. The spherical and binary perceptron models need to be considered separately, since the relevant equation involves Gs, which differs between the two.
F1111 Spherical Perceptron
In the spherical case, the saddle point equation for reads:
(Gs(1)
q=
(121)
Oq
0 1
1
g+ 2 (q-
(q (q=
f
log(4 Fa)
(122)
0ÿ
2
2(
fa)
(f-fa) fa) (f-fa) F-
2
(123)
i Pa
(f (f-
We can now use the saddle point for the reference system, see Section B.4.5, to rewrite the expression of q. concluding that & diverges as
1 Fd
(124)
with e constant. This shows that the part of the derivative due to the interaction term diverges as Oc- The sign of the derivative is negative, meaning that the free entropy has local minimum at q= unless this is overcome by the energetic contribution (which will not the case with U(s) will show below).
30

---

F.1.2 Binary perceptron
An analogous computation for the binary perceptron case, already presented in Huang and Kabashima [2014], results in:
enVFw"
1+q Σ
S Dz Dy
log (2 coshi (=v +/v=f++-+++++ (4 (Q-1) (o-frww))
(125)
2
0q Wt =s1
2cosh(rVP)) envf="
Σ
{
DDDy
tanh (2 (q-
2/Q-- + w"
2 2cosh(rVP)
(126)
As for the spherical case,
q 1. We can then rewrite the previous expression as
1 2 = 2(5-)) f Dz en (/ -
- & ((=V/-FtTW/)
(127)
cosh(?//))
and thus
1
i = log
+
(128)
2
e e (aVFFmM)) + e ([VT--
1 =+ log
S Dz Dy
(129)
2
cosh(?>V))
This shows that, as q 1, the part of the derivative that comes from the interaction term also diverges in the binary case, but this time logarithmically. as O(log c). The sign of the derivative is again negative, meaning that the free entropy has a local minimum at q = unless the effect is overcome by the energetic contribution. As we shall show, the energetic contribution does indeed overcome this effect and produce a local maximum at q unless the potential (s) diverges at the origin.
F.2 Energetic term
Next, we compute the derivative of the energetic term. This does not depend on the model. We expand G5 e)) for small and then study (GE(1-) - - /e", keeping in mind that:
dg
dGæ
(130)
dg
de
We perform the expansion, trying keep the setting general with respect to the potential U. Indeed, our only starting assumption is that U is twice differentiable over (0, oo).
The energetic term, after some manipulations, and using 1 can be written as:
GB= = f
DyDz N22
(131)
D(v)
D(7)
DAe DAC (AVTT-T--
(132)
.VF VI-
N(2.7)
DAe (0 A A(2,9,1)
(133)
VIT
A(2,7,A) = log
[.
Due (3((uutta(aaA)
(134)
C = - /--------------------
d
(135)
VI-r
"To the sake of simplicity, from now do make explicit the dependence of GE.
31

---

We first perform two change of variables, in both N and D, from X
-
D(7)= 1
VI-r / dpG
p
7/r
-((()
(136)
vI-r
N(2,7)= VI-r L
dpG
p+7/r
e e-BU(A) --0U(0)A(E,T,)) A(2,7.p)
(137)
V1-r
A(2,7,p) log
DuE DuE
(138)
D+
á(2,y, - 1-r v1-r
(139)
where G(x)
2
Next, expand the potential U inside the expression of A for small up the first order:
U (p) U (uVE+t(( ~ U (p) VEU" (p) (u 2) 1-r (Vry+ p) +
1 ze (u
(140)
This allows us to compute the integral Á, which converges as long as U" (p) Be 2 (which is obviously always true if U is convex), After some explicit integration and further expansions, we arrive at:
A(z,Y,p) Ao VEA1/2 EA + log H
(141)
Ao -3U
(142)
A1/2 3=U' (p)
(143)
B (OU) U" (p) (1+29)+
U ('( 1-r
A1 3
(144)
2
At this point, we can observe that the term A1/2 does not contribute because gets canceled by the integral over z. Indeed, with further manipulations and changes of variables we arrive at:
GE= f Dr N(r)
(145)
D(7)
D(7)= l0d dpG
0+ TVT
(p)
(146)
V1-r
N(7) 6 dpG
P+
e (BU(p) [Ao + eăi}+
(147)
V--r
TC+
(UU(T) (
Ve drG
Dz log H (z 72
Vi-r
Ao -BU (p)
(148)
8 (U' (P))
U (p)
(p+
A LU" (V)
(149)
We can observe that GE receives three contributions from N. The ones from As and A are straightforward: they represent zero-order and first-order contributions. In particular the first one gives us the limiting value 92- lim,- 9 The first-order term then gives a finite contribution to the derivative.
Thus, the only way to avoid the local maximum at q = in the binary perceptron case is to choose potential ((s)) that diverges for + 0. Then the scaling of the last term with can be manipulated.
32

---

For the specific choice (s) = - log(s) we can easily see that we obtain an additional factor e//² which makes the term -+1 and the derivative O sub-dominant and it does not contribute to the derivative: we revert to the situation where the dominant contribution no longer comes from the energetic term, but from the interaction term, and has the right sign to ensure that 1 will correspond to a local minimum rather than a maximum.
For > 1, this term therefore becomes
33

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: All claims in the abstract and introduction are supported by theoretical and numerical analysis in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
34

---

Justification:
Some limitations, particularly of AMP, are discussed throughout the paper. Other stated limitation is that the results are not rigorous but conjecturally correct.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Our theoretical results are computations that follow the style and standard of rigor of statistical physics: our conclusions conjectural but likely correct. This is clearly stated right at the outset. The supporting arguments and limits of the analysis (e.g. where replica symmetry holds) are discussed. All the steps of the computations are reported in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
35

---

Answer: [Yes]
Justification: Numerical experiments are fully explained and straightforward to reproduce.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c)
If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The data is synthetic and easy produce. The code is very standard, the only custom algorithm used is short, simple and fully detailed in the text.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
public/gun public/guides/ httg///dd//oodsuiee soreddeSummsssooolliiiiii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips.co httpc//pcccggudpe///eeeeeeeeeeee httgguude////// /eoiddeS//o wwweeeeuummsssoooooll.looo ssioolllcyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
36

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: no training is involved
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate
information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All plots reporting numerical experiments that involve some degree of sampling contain error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Experiments CPU and are quite cheap computationally
37

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compule required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't I make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tteer///euerppeee hww.ips.u..eeeeeeeeeeeee ccc/public/Bthicsuuuie ines?
Answer: [Yes]
Justification:
We comply with the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Being mostly theoretical paper focused simple models, we do not believe there are any direct positive or negative societal consequences.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
38

---

Answer: [NA]
Justification:
the paper poses no such risk
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: no existing assets are used
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: no assets released
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
39

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
no crowdsourcing and no research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: does not apply
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
LLMs not involved
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.MM policy (https http///eenppp//ee/ htc//oonfereccee/20000 /LLM) for what should or should be described.
40


Reviews:
[{"review_id": "CMFZFwlyXW", "reviewer": "Reviewer_r88Y", "summary": "The authors study algorithms in the family of the recently introduced \"algorithmic stochastic localization\", generative diffusion algorithms for sampling where an approximation to the score function is not learned from data but is implemented directly using knowledge of the structure of the target distribution. In particular, as in previous work on the Sherrington-Kirkpatrick model and related applications, the authors use a variant of approximate message passing (AMP) to approximately compute the score function. The authors extend some of the prior work in this area to problems without a statistical structure of a \"hidden\" or \"planted\" signal to be estimated, but rather \"pure optimization\" problems where one seeks to sample something like solutions of a constraint satisfaction problem (though in a continuous setting). They develop tools for applying the (non-rigorous) replica trick of statistical physics to calculate when such sampling algorithms succeed. As applications, they study sampling problems associated to the spherical and binary perceptrons. In the case of the binary perceptron, they show that while the uniform distribution cannot be sampled in this way, a certain tilting of it motivated by the replica analysis can be sampled.", "questions": "- I appreciate that the choice of $U_{\\tau}$ in (20) is charmingly motivated by the way that the actual replica trick works, and this formal idea is delightful, but that aside it does seem like various other approximations of the logarithm might be just as suitable. Have the authors tried any alternatives to this choice and can they comment on whether or why this is the best choice?\n\n- Could the authors comment on, in terms of the actual distribution of solutions to the binary perceptron problem, what the distribution tilted by their potential looks like compared to the uniform distribution? Which parts of the solution space are favored? Is there any very down-to-earth explanation of why might plausibly make it easier to sample?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths: The replica analysis involves what seems to me to be a significant generalization of the analysis in the recent work (Ghio et al, 2024), which focused on \"planted\" models with a distinguished signal object. While the calculations are technical and, as usual, mysterious-looking, the authors make a reasonable effort to summarize the main highlights of the calculation. The perceptron examples are very helpful for explaining what kinds of conclusions one can draw from this analysis, and the case of the binary perceptron and the potential function designed based on the replica analysis are in my opinion a very nice application. (Without this observation, I would be more tempted to complain that these are quite niche applications.) The numerical experiments associated to this make a convincing case that this analysis leads to a powerful method that outperforms a straightforward implementation of simulated annealing.\n\nWeaknesses: I do not have many complaints about the paper - it convincingly solves the problems it sets out to solve and presents the findings reasonably well. I think it is unfortunately pretty much unavoidable that the discussion of the physics analysis will be inscrutable to some (perhaps many) readers, but, as I mentioned, the authors make a commendable effort to compress the main points into a few pages at the beginning. An intrinsic limitation of this entire approach is that it is mathematically non-rigorous and can only be validated numerically, but the authors acknowledge this and their numerical experiments are thorough and convincing.", "was_revised": true, "final_justification": "I did not raise any substantial issues but just a few clarifying questions, and the authors replied to my satisfaction. I am leaving my positive rating of the paper unchanged.", "rebuttal": "We thank the reviewer for the positive feedback. In what follows, we address the questions raised.\n\n> I appreciate that the choice of in (20) is charmingly motivated by the way that the actual replica trick works, and this formal idea is delightful, but that aside it does seem like various other approximations of the logarithm might be just as suitable. Have the authors tried any alternatives to this choice and can they comment on whether or why this is the best choice?\n> \n\nThe $\\tau$-annealing MCMC scheme inspired by the replica trick is the first and only attempt we made. Since it worked very well, we didn’t explore any further. We suspect there is a large family of methods with similar or even better performance, but at the moment, we cannot give generic prescriptions. An empirical and possible theoretical analysis of the problem is an avenue for further research.\n\n> Could the authors comment on, in terms of the actual distribution of solutions to the binary perceptron problem, what the distribution tilted by their potential looks like compared to the uniform distribution? Which parts of the solution space are favored? Is there any very down-to-earth explanation of why might plausibly make it easier to sample?\n> \n\nWe propose the following conjecture regarding the types of solution favored by our tilting, based on the understanding of the geometry of the solution space gained in recent years.\n\nUnder the uniform measure, typical solutions of the binary perceptron are known to be isolated [Huang and Kabashima 2014], which means they are also inaccessible to a broad class of algorithms known as “stable algorithms” (see the discussion on the overlap gap property in Gamarnik [2021]). \n\nNonetheless, an exponentially rare (under the uniform measure) but algorithmically accessible dense region of solutions was shown to exist in Baldassi et al. [2015]. It is important to note that the existence of such regions was established via replica theory computations, while their algorithmic accessibility was conjectured based only on empirical evidence and heuristic arguments. We conjecture that our tilted measure gives more mass to this region so that algorithmically accessible solutions arranged in a dense cluster become the typical ones under the new measure. Unlike previously studied algorithms, the ASL process in our case remains under tight analytical control.\n\nA more quantitative characterization of the relation of the typical solutions from our tilted measure and the dense cluster uncovered in Baldassi et al. [2015] needs to be established and could be an avenue for future investigations. \n\n**[Huang et Kabashima 2014]** Origin of the computational hardness for learning with binary synapses, H. Huang and J. Kabashima, PRE, 2014.\n\n**[Baldassi et al. 2015]** Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses, C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti and R. Zecchina, PRL., 2015.\n\n**[Gamarnik 2021]** The overlap gap property: A topological barrier to optimizing over random structures, D. Gamarnik, *Proc. Natl. Acad. Sci.*, 2021."}, {"review_id": "b6V8mFEolj", "reviewer": "Reviewer_4wxK", "summary": "The paper analyzes the use of Algorithmic Stochastic Localization (ASL), a diffusion method combining Stochastic Localization (SL) and Approximate Message Passing (AMP), to sample from target distributions defined over solution spaces of perceptron models. Using the replica method, the authors derive asymptotic thresholds for successful sampling. They apply the framework to two cases: the spherical perceptron with negative margin, where uniform sampling is possible in the replica symmetric phase; and the binary perceptron, where they identify a log-shaped potential enabling efficient sampling and introduce a $\\tau -$annealed MCMC scheme for practical implementation.", "questions": "**1.** In Figure 1, the value of $\\alpha$ varies around $300$. Is this just a matter of scaling, or does it imply that one needs $M\\sim 10^2 N$ samples in order to reach the regime where AMP fails for the spherical perceptron?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Quality**\n\nThe theoretical analysis is carefully executed and builds on established tools from statistical physics, notably the replica method. The connection between the shape of the free entropy landscape and the success of the ASL sampling scheme is well described. The application to two well-studied models provides useful benchmarks, and the introduction of a log-shaped potential—motivated by the asymptotic analysis of an unnormalized probability density—yields an efficient sampler over a broader range of $\\alpha$ values for the binary perceptron. Numerical experiments are well-designed and support the theoretical claims.\n\n**Clarity**\n\nThe exposition is clear, with a logical structure and helpful figures. The authors carefully articulate how their work differs from [Ghio et al., 2024].\n\n**Significance**\n\nThe paper addresses a relevant question: under which conditions can generative diffusion methods be used to sample from complex high-dimensional distributions in constraint satisfaction problems. Naturally, the setting is idealized and, although it may be far from practical cases, it provides insights into the interplay between algorithmic tractability and diffusion-based generative models. The proposed annealed MCMC scheme, based on the potential identified in the theoretical analysis, is particularly relevant for binary perceptron sampling.\n\n**Originality**\n\nThe extension of the replica analysis of diffusion-based samplers beyond planted models to unnormalized target distributions is a novel contribution. The identification and use of a diverging potential to enable tractable sampling in the binary perceptron setting, along with the associated annealing scheme, adds originality to the algorithmic aspect of the work.", "was_revised": true, "final_justification": "I thank the authors for addressing my question. I maintain my recommendation for acceptance.", "rebuttal": "We thank the reviewer for the positive feedback. In the following, we address the question raised.\n\n> In Figure 1, the value of $\\alpha$ varies around 300. Is this just a matter of scaling, or does it imply that one needs $M\\approx10^2N$ samples in order to reach the regime where AMP fails for the spherical perceptron?\n> \n\nIn the central panel of Fig. 1, where we set $\\kappa = -2.5$, we focus our evaluation on values of the denisty of constraints $\\alpha$ around 300, as this is the region where “interesting” phenomena occur in the thermodynamic limit ($N \\to \\infty$): the replica symmetry breaking transition occurs at $\\alpha \\approx 280$, and our plot shows that the algorithmic transition for ASL takes place at $\\alpha \\approx 270$."}, {"review_id": "fgeYkYMnEF", "reviewer": "Reviewer_6gzG", "summary": "The paper considers the problem of sampling from a high-dimensional distribution \n$$p(\\mathbf{w}) = \\frac{\\psi(\\mathbf{w})}{Z},$$\nin a setting where only the unnormalized density $\\psi(\\mathbf{w})$ is known.\n\nThe authors study an approach based on generative diffusion (or stochastic localization), \nwhich allows to sample from $p$ by solving a stochastic differential equation (SDE). \nAt each time $t$, one has to compute the Bayes-optimal estimator of $\\mathbf{w}^\\star$ \nfrom the observation \nof $\\mathbf{y} = t \\mathbf{w}^\\star + \\sqrt{t} \\mathbf{g}$, where $\\mathbf{w}^\\star \\sim p$ and $\\mathbf{g} \\sim \\mathcal{N}(0,1)$. \nBased on existing literature, a natural approach to compute this BO estimator is via the Approximate Message-Passing (AMP) algorithm.\nUsing non-rigorous methods from statistical physics (namely the replica method), the authors show that whether this sampling procedure (called ASL -- Algorithmic Stochastic Localization) succeeds can be characterized \nfrom the study of a one-dimensional potential $\\phi_t(q)$, for which they provide an explicit form.\n\nThey apply this framework to perceptron-type problems:\nfocusing on the region where the problem is solvable, the goal is to sample uniformly from the set of solutions.\nFor the negative spherical perceptron, the analysis of the paper shows that ASL succeeds in (almost) all the replica-symmetric region of the phase diagram.\nIn the binary perceptron with zero margin, the authors show that instead ASL fails in the whole phase diagram, in agreement with previous works that argue computational hardness of sampling in the binary perceptron.\nOn the other hand, by tilting the measure over the space of solutions by a well-chosen potential, ASL is shown to succeed at sampling this modified measure in a large region of the phase diagram.\nFinally, sampling of this tilted measure is also shown numerically to be achievable by a MCMC algorithm.", "questions": "- (Line 36): The motivation of sampling from such unnormalized probability distributions is quite brief, and \n  could be developed further.\n\n- (Line 59): I think that [Ghio\\&al '24] also considers sampling from non-planted distributions, such as the p-spin model and the solutions of random graph coloring.\n  Could the authors correct me, or clarify what they mean?\n  On line 139, it is also implied that the specificity of [Ghio\\&al '24] is to consider normalized densities, which makes it a bit confusing.\n  More generally, I would be potentially willing to change my rating and confidence score \n  if the authors were to convince me better regarding the technical novelty of their work with respect to [Ghio\\&al '24].\n\n- I think that at several points (e.g. regarding the introduction of the free entropy line 150, or the replica results line 177), \n  reading the paper might be complex for an audience which is not expert in statistical physics techniques. It would be good to give a more pedagogical presentation \n  of these tools for this audience, which is the vast majority of the NeurIPS attendees.\n\n- In the conclusion, the authors mention that the $\\tau$-annealing procedure proposed overcomes ASL's limitation on structured instances of the problem, but this is not explored in the paper. \n  I imagine this is rather an informal conjecture made by the authors, by analogy with similar statistical learning problems?\n  Moreover, the authors mention that the ideas developed in this paper could enhance \"sampling and solving\" in other hard CSPs: I wonder how would the present analysis help in solving (i.e. finding a solution to the problem in a given instance)?\n\nFinally, I list here more minor points:\n\n- (Line 66) I believe the negative spherical perceptron was introduced before the work of Franz \\& Parisi in 2016. \n  While I don't know the earliest references, it is studied for instance in the work \"Negative spherical perceptron\" (Stojnic '13), \n  and is mentioned in Chapter 8 of the book \"Mean-field models for spin glasses\" (Talagrand '10), see Chapter 8 (for instance in Problem 8.4.3).\n\n- (Line 122) It would be good to mention again in this paragraph the works that introduced ASL, and that are cited in the introduction.\n\n- (Line 128) I would say that in terms of limitations of AMP, time complexity should also be mentioned, it's possibly a stronger limitation in practice than low-dimensionality of the data.\n\n- Equation (12): the introduction of both $T$ and $U$ is a bit redundant, and makes part of the exposition slightly confusing (since $T$ is not really the temperature of the problem, as we are still trying to sample zero-energy states and not the Gibbs measure at temperature $T$). Maybe a different name for $T$ would be best.\n\n- (Line 243) It is quite surprising at first sight that the paratmeters of the reference system are independent of $t, q$ and $\\hat{q}$, since they interact via the replica $w_1^\\star$: could the authors comment on that? \n  Does this suggest some effective decoupling of the term $Z^{-1}$ with the other terms in the replica computation? \n\n- (Line 263) Since the computation here is done assuming that $p$ is RS, wouldn't the whole approach break down beyond the dAT line? \n  As such, can the authors conclude \n  from this calculation that sampling being hard in a RSB phase follows from their analysis?\n\n- Finally, I found the following typos/misprints:\n  - Line 110: I think $p_{\\mathbf{h}, t}(\\mathbf{w})$ is not really a convolution with the Gaussian noise (this would rather be the distribution of $\\mathbf{h}_t$).\n  - (Line 233) The wording \"quite fast\" reads off as a bit vague.\n  - (Line 244): \"system free entropy\"\n  - (Line 246): \"allow us\"\n  - Caption of Fig.2: I would say the agreement \"suggests\" rather than \"shows\" (although \n    this analysis is indeed a convincing argument for the fairness of produced samples).\n  - (Line 285) It should be \"El Alaoui\" rather than \"Alaoui\"\n  - (Line 325) \"for SA\"\n  - (Line 327) \"we sample\" might be a better word than \"we solve\"", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Let me clarify that I read through the main text in detail (following the computations and arguments),\nbut did not check the supplementary material for reasons of time.\nMoreover, while I am quite familiar with the statistical physics approaches to learning theory, this is slightly less the case for generative diffusion.\n\n**Strengths --**\n\n- The paper is written in a clear fashion. Concepts are exposed very clearly while \n  remaining concise (Section 2 is a good example), and I want to thank the authors for this effort in the writing.\n  The technical tools used here (the replica method and the analysis of AMP algorithms) are well presented and detailed. \n  The results are well described, e.g. via clear figures. \n- The replica computation in this generic setting, as well as the phenomenology of sampling in perceptron models \n  are contributions which would be of interest to the audience engaged in similar topics, as this a subject of strong recent activity and the paper \n  shows interesting results in this regard (e.g. that sampling a weighted measure over the space of solutions rather than the uniform one can make the problem drastically easier \n  in binary perceptrons).\n\n\n**Weaknesses --**\n\n- The manuscript (both by the subject of study and the presentation) ends up being targeted towards an audience already quite knowledgeable in the statistical physics approach to the theory of statistical learning, \n  and because of this the NeurIPS audience might not be the best fit for it in my opinion.\n  I tend to think it would be better suited e.g. in venues closer to statistical physics interests.\n  On the other hand, I also understand the upsides of introducing part of this audience to these powerful techniques, so I don't consider this a very weak point.\n- The main weakness of the paper, in my eyes, is the seemingly small novelty with respect to the analysis of \n  [Ghio \\& al '24], which conducts a very similar analysis, although the authors claim that it applies only to planted models (line 59) or normalized densities (line 139). \n  The replica computation seems very similar in nature, modulo the computation of $Z^{-1}$ with an additional use of the replica method. \n  At a high level, this work seems like a fairly close computation, applied to $p$ being the solutions of perceptron problems, rather than e.g. graph coloring or p-spin models which are analyzed in [Ghio\\&al '24].", "was_revised": true, "final_justification": "The authors clarified many of my concerns, especially regarding the novelty with [Ghio & al], see our discussion below.", "rebuttal": "We thank the reviewer for raising several important points, which give us the opportunity to highlight the key novelties and strengths of our work. Below, we address each major concern in detail (within the constraints of the rebuttal format) and acknowledge the remaining minor points.\n\nWe would be happy to further discuss any remaining concerns, and we would appreciate if the reviewer could consider raising their score in case our responses address their questions adequately.\n\n> The manuscript (both by the subject of study and the presentation) ends up being targeted towards an audience already quite knowledgeable in the statistical physics … On the other hand, I also understand the upsides of introducing part of this audience to these powerful techniques, so I don't consider this a very weak point.\n\nWe believe that, given our work involves fundamental neural network models, generative diffusion, sampling problems, and message passing algorithms, a venue such as NeurIPS would allow us to reach a broader audience of potentially interested readers compared to a stat. physics journal.\n\nWe acknowledge that our paper does not provide a pedagogical introduction to the statistical physics approach to statistical learning, and it assumes some prior background. Fortunately, thanks to the growing interest of the statistical physics community in machine learning and the openness of the ML community, this knowledge has been spreading in recent years. We hope to contribute to this trend, at least by offering motivation to explore these techniques more deeply.\n\n> The main weakness of the paper, in my eyes, is the seemingly small novelty with respect to the analysis of [Ghio & al '24], which conducts a very similar analysis, although the authors claim that it applies only to planted models (line 59) or normalized densities (line 139) …\n\nand also\n\n> (Line 59): I think that [Ghio & al '24] also considers sampling from non-planted distributions, such as the p-spin model and the solutions of random graph coloring. Could the authors correct me, or clarify what they mean? On line 139, it is also implied that the specificity of [Ghio & al '24] is to consider normalized densities, which makes it a bit confusing. **More generally, I would be potentially willing to change my rating and confidence score if the authors were to convince me better regarding the technical novelty of their work with respect to [Ghio & al '24]**.\n\nWe thank the reviewer for these well-motivated comments. The work Ghio et al is indeed very close and provided inspiration to our work.\n\nLet us first highlight in more detail the **main limitation of Ghio et al**  that concerns us:\n\n- Their formalism is limited to planted ensembles, where the reference configuration (the one eventually sampled at the end of the generation process) can always be assumed to be the planted one in the theoretical analysis, since it is statistically identical to any other sample from the target distribution thanks to the Bayesian structure of the problem. This allows to avoid dealing with hard-to-compute normalizing factors Z in the denominator.\n- The reviewer is correct in noting that Ghio *et al.* also analyze the $p$-spin and NAE-SAT models in the non-planted setting. However, their analysis relies on a property of these problems, namely, that they are contiguous to their planted counterparts. This is not a general property: it holds only for specific problems and within certain regions of the parameter space. This phenomenon is known as *quiet planting*, and is explained in detail in Section 1 of the Supplementary Information of Ghio et al. Thus, even in these non-planted settings, they are ultimately analyzing planted models, which is what their formalism is equipped to handle.\n\n**We address this limitation as follows**\n\n- We introduce a formalism that allows us to handle generic target distributions, possibly with hard-to-compute normalization factors. It is based on a double application of the replica trick, which significantly broadens the scope of its applicability.\n- Thanks to the Bayesian structure of the generative diffusion process, we can show that the Nishimori conditions hold and simplify the solution of the saddle point equations.\n\nMoreover, **we provide the following further contributions:**\n\n- In the case of the binary weight perceptron, we don’t just confirm the difficulty of sampling from the uniform distribution: our analysis lets us pinpoint precisely the failure mode of the ASL procedure, and identify a minimal correction that overcomes this problem. While some heuristic solvers for the binary perceptron are known (e.g. Braunstein Zecchina [2006], Baldassi Braunstein [2015], and others), this is the first approach that produces samples from a well-defined and theoretically motivated target distribution over binary perceptron solutions.\n- On the algorithmic side, the failure mode analysis also inspired a practical MCMC annealing scheme as a robust solver for generic (non-random) instances of the problem, which is far more effective than standard simulated annealing.\n- Finally, the models that we investigate are non-convex neural networks that are of particular interest to the machine learning community and are also prototypical examples of constraint satisfaction problems. Dense regions of solutions / wide minima of the training loss landscape have been linked to improved generalization properties (Chaudari et al [2019], Foret et al [2021]). We thus believe that our theoretical and algorithmic insights go beyond the simple perceptron models we consider.\n\n**[Braunstein Zecchina 2006]** *Learning by message passing in networks of discrete synapses.* *PRL*\n\n**[Baldassi Braunstein 2015]** *A max-sum algorithm for training discrete neural networks*. *JSTAT* \n\n**[Ghio et al 2024]** Ghio, Dandi, Krzakala, and Zdeborová, *Sampling with flows, diffusion, and autoregressive neural networks from a spin-glass perspective*, *PNAS* \n\n**[Chaudari et al 2019]** Chaudhari, Choromanska, Soatto, LeCun, Baldassi,  \nBorgs, Chayes, Sagun, and Zecchina, *Entropy-sgd: Biasing gradient descent into wide valleys*. *JSTAT*\n\n**[Foret et al. 2021]** Forêt, Kleiner, Mobahi, Neyshabur, *Sharpness‐Aware Minimization for Efficiently Improving Generalization,* ICLR  \n\n**Questions:**\n\n> (Line 36): The motivation of sampling from such unnormalized probability …\n\nThis is a very broad and important topic, for instance, in Bayesian statistics and statistical physics. We will provide more motivation in the revised version.\n\n> I think that at several points .. reading the paper might be complex …\n\nWe agree with the reviewer. In the revised version, we will move to the appendices some non-essential definitions, such as the input- and output-channel free entropies for AMP, and make some room for a more pedagogical explanation. \n\n> In the conclusion, the authors mention that the $\\tau$-annealing procedure proposed overcomes ASL's limitation ..\n\nIt is true that the claim that $\\tau$-annealing overcomes ASL’s limitation on structured data is not explored, but it is well motivated by empirical observations and theoretical considerations: AMP is notoriously sensitive to structured or correlated data [Donoho et al., 2009; Rangan, 2011], whereas $\\tau$-annealing operates via a standard Metropolis-Hastings MCMC scheme and is agnostic to the statistical properties of the dataset. We therefore expect the method to remain robust in more structured or real-world instances. In the revised version, we will provide experiments on structured problems.\n\n**[Donoho et al 2009]** Donoho, Maleki, and Montanari, *Message-passing algorithms for compressed sensing*, *PNAS.* 2009.\n\n**[Rangan 2011]** *Generalized Approximate Message Passing for Estimation with Random Linear Mixing*, IEEE ISIT 2011.\n\n> Moreover, the authors mention that the ideas developed in this paper could enhance \"sampling and solving\" in other hard CSPs:…\n\nOur analysis allowed us to identify the underlying reason for the failure of ASL in the binary perceptron, due to the isolated geometry of typical solutions, and to devise a way to overcome this limitation by introducing an appropriate potential that leverages the existence of sub-dominant but accessible regions of the solution space. Other hard-to-sample CSPs with similarly structured solution spaces could be amenable to an analogous treatment. In such cases, solvers can be designed as samplers that target a favorable distribution over the solution space.\n\n> Finally, I list here more minor points:\n\n> (Line 128) I would say that in terms of limitations of AMP, time complexity …\n\nThe cost of AMP is $O(N M)$ per iteration, and we conjecture that only a finite number of iterations are needed to sample within a given precision. On a distribution that is parameterized by $O(N M)$ bits, it is hard to do better. For instance, an MCMC sweep would take $O(N M)$. And if one tried to implement the score function with a neural net, one would need to either have that order of parameters or give up on optimality.\n\n> Equation (12): the introduction of both $T$ and $U$ is a bit redundant…\n\nIt is true that in the most common formulations of CSPs, the temperature is usually associated with violated constraints. However, in systems with both hard and soft constraints, it is not uncommon to use the term “temperature” for the parameter controlling the soft part; therefore, we prefer to keep the symbol $T$.\n\n> (Line 243) It is quite surprising at first …\n\nAs the reviewer correctly notes, the reference‐system order parameters $r$ and $\\hat{r}$ define the “equilibrium” target distribution and do not evolve with the tilted measure; they are set *a priori*. This decoupling is formally induced by the $s\\to 0$ limit.\n\n> (Line 263) Since the computation here is done assuming that is RS…\n\nOur analytical approach can be extended to include RSB, but we think AMP-based solvers will fail, and sampling in general to be hard in the RSB phase."}, {"review_id": "4QDrQJffZh", "reviewer": "Reviewer_5GDK", "summary": "This paper presents a theoretical framework to analyze the efficiency of sampling the solution space of high-dimensional random perceptron problems using generative diffusion algorithms. The authors employ a statistical physics approach, using the non-rigorous but well-validated replica method, to predict the performance of Algorithmic Stochastic Localization (ASL) , where Approximate Message Passing (AMP) serves as the score approximator.", "questions": "* Could you elaborate on the motivation for studying the spherical non-convex perceptron? While it is described as a model for \"glassy behavior\", what specific algorithmic or theoretical challenges does it present that makes it a crucial case study for your generative diffusion framework?\n* The τ-annealing MCMC scheme is proposed as a robust alternative to AMP for the binary perceptron. Could you provide a more detailed analysis of its scalability, perhaps by discussing its computational complexity and how its performance (e.g., time-to-solution) compares to other state-of-the-art heuristic solvers for this problem, especially as the system size N increases?", "limitations": "yes.", "rating": 3, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 1, "originality": 2, "strengths_and_weaknesses": "## Strength\n\n* The problem consists of novel formulation of perceptron problems. A key strength is the generalization of prior work (e.g., Ghio et al. [2024]) to handle unnormalized target densities.\n* The authors provide a detailed asymptotic analysis for both the spherical and binary perceptron models. The main contributions are explicitly stated and well-supported by the derivations.\n\n## Weaknesses\n\n* **Significance.** The method heavily relies on approximate message passing, which is a well-established concept but also has limited use in real-world application. The authors claimed that the method provides a fast enough algorithm for their \"synthetic\" setting (pp. 4). Therefore, I have a concern about its significance since I have the impression from literature that the solution acquisition method for perceptrons will not scale well. Since it relies on the quality of the sample of MCMC method, it is likely that the scalability of the proposed method is severely limited.\n* **Novelty.** Most of the concepts outlined in this paper are well-known and this paper does not produce new distinct theorems. Therefore, I believe the contributions of this paper are more in the empirical side, and I think a new formalism is in Eqs. (15-17) serve that purpose. However, the authors do not clearly articulate the reason why we look for Spherical Non-Convex Perceptrons. The novelty of this paper is not clearly expressed and the motivation of the work needs a comprehensive revision.\n* **Experiment.** The paper needs some experimental results on scalability, and the application side of spherical nonconvex perceptions. I also suggest the authors to include demonstrative illustrations and figures in Section 1 or 3, which help understanding of broad audience", "was_revised": true, "final_justification": "I have read the rebuttal and decided to lower my confidence score based on my unfamiliarity with the subject.", "rebuttal": "We thank the reviewer for their comments. We try to answer in detail to the concerns they raised. Some of the questions are not entirely clear to us; therefore, we provide additional context to try to disambiguate the conversation. We hope our responses adequately address the raised concerns, and we would be grateful if the reviewer could consider revising their score considering these clarifications.\n\n> **Significance.** The method heavily relies on approximate message passing, which is a well-established concept but also has limited use in real-world application. The authors claimed that the method provides a fast enough algorithm for their \"synthetic\" setting (pp. 4). Therefore, I have a concern about its significance since I have the impression from literature that the solution acquisition method for perceptrons will not scale well. Since it relies on the quality of the sample of MCMC method, it is likely that the scalability of the proposed method is severely limited.\n\nUnfortunately, here we are not sure we fully understand the referee’s comment. There may have been a misunderstanding regarding the setting and goals of our work, which we try to clarify below.\n\nIn our setting, the target distribution is known up to a normalization factor that is hard to compute. We provide a formalism to assess the limitations of sampling from the target distribution using generative diffusion. The score function is implemented algorithmically using AMP, which is optimal for i.i.d. samples in the large size limit. This setting contrasts with the typical ML setting, where the target distribution is unknown but samples from it are available, and a neural network is trained to approximate the score function based on those samples. \n\nTherefore, we believe that concerns about scalability due to limited sample availability (if this is what the question refers to) do not apply in our setting, as no sampling from the target distribution is required.\n\n> **Novelty.** Most of the concepts outlined in this paper are well-known and this paper does not produce new distinct theorems. Therefore, I believe the contributions of this paper are more in the empirical side, and I think a new formalism is in Eqs. (15-17) serve that purpose. However, the authors do not clearly articulate the reason why we look for Spherical Non-Convex Perceptrons. The novelty of this paper is not clearly expressed and the motivation of the work needs a comprehensive revision.\n\nWe don’t provide theorems, we provide precise conjectures with a well-established and exact (although non-rigorous) method, replica theory. The resulting findings are, to the best of our knowledge, novel and not previously reported. We introduce a new general theoretical framework to investigate the ultimate limits of samplability via generative diffusion. As concrete applications, we explore two paradigmatic examples of neural networks and constraint satisfaction problems. We discuss the motivation for investigating the spherical non-convex perceptron model below, in a response to a question. \n\nFor further details on the novelty of our work, please see our rebuttal to Referee 6gzG.\n\n> **Experiment.** The paper needs some experimental results on scalability, and the application side of spherical nonconvex perceptions. I also suggest the authors to include demonstrative illustrations and figures in Section 1 or 3, which help understanding of broad audience\n\nWe are not entirely sure what the reviewer means by scalability. If it refers to larger system sizes, we believe that the sizes we have already explored are sufficiently large, as our experimental results align perfectly with the theoretical predictions in the infinite-size limit (as verified in the experiments for the negative spherical perceptron setting).\n\nAlthough we doubt that we will be able to add new figures due to space constraints, in the revised version, we will try to provide a gentler introduction for the broader audience.\n\n> Could you elaborate on the motivation for studying the spherical non-convex perceptron? While it is described as a model for \"glassy behavior\", what specific algorithmic or theoretical challenges does it present that makes it a crucial case study for your generative diffusion framework?\n\nThe simplest model of a neural network, the perceptron as originally defined, is convex. Therefore, the geometry of its solution space is not sufficiently rich to exhibit the features that characterize more complicated, non-convex neural networks. Characterizing analytically the typical behavior of multi-layer neural networks, on the other hand, is very challenging, even when using powerful frameworks such as replica theory. An approach that has been demonstrated to be fruitful is that of considering modified, non-convex perceptron models. Two simple ways to disrupt the convexity of the model are to use a negative value for the stability (negative spherical perceptron) and to constrain the weights to binary values, which are the two models we study in our paper. Both models have been used in the study of the geometry of solution spaces, the effects of overparameterization, and aspects of generalization. Recent work on the negative spherical perceptron has uncovered a star-shaped connectivity of solution clusters [Annesi et al. 2023], a property later observed empirically in deep neural networks trained on MNIST and CIFAR benchmarks [Lin et al. 2024]. Furthermore, Montanari et al. [2024] investigated the generalization behavior of simple non-convex perceptron networks, bridging theoretical predictions and empirical performance in more complex architectures. \n\n**[Annesi et al. 2023]** The star-shaped space of solutions of the spherical negative perceptron, B. Annesi, C. Lauditi, C. Lucibello, E. Malatesta, G. Perugini, F. Pittorino, and L. Saglietti, Phys. Rev. Lett.  2023.\n\n**[Lin et al. 2024]** Exploring Neural Network Landscapes: Star-Shaped and Geodesic Connectivity, Z. Lin, P. Li and L. Wu,  ArXiv (2024).\n\n**[Montanari et al. 2024]** Tractability from overparametrization: The example of the negative perceptron, A. Montanari, Y. Zhong and K. Zhou, *Probab. Theory Relat. Fields*, (2024).\n\n> The τ-annealing MCMC scheme is proposed as a robust alternative to AMP for the binary perceptron. Could you provide a more detailed analysis of its scalability, perhaps by discussing its computational complexity and how its performance (e.g., time-to-solution) compares to other state-of-the-art heuristic solvers for this problem, especially as the system size N increases?\n\nOur experiments already show a finite algorithmic threshold in alpha with $O(1)$ sweeps (which implies $O(N^2)$ complexity), see Fig. 3 (right). Taking $O(N)$ sweeps or more appears to further increase the algorithmic threshold, as shown in Fig. 6.\n\nOther known algorithms that find solutions to binary perceptron problems [Braunstein and Zecchina 2006; Abbe 2022] have complexity at least $O(N^2)$. We stress that ours is the first solver that outputs solutions that are both diverse and under control, as they are sampled from a well-defined target distribution.\n\n**[Braunstein and Zecchina 2006]** Braunstein, A. and Zecchina, R., Learning by message passing in networks of discrete synapses. *Physical Review Letters*, 2006.\n\n**[Abbe 2022]** Abbe, Li, Sly, *Binary perceptron: efficient algorithms can find solutions in\na rare well-connected cluster*, STOC 2022"}, {"review_id": "mozSJLHEKf", "reviewer": "Reviewer_SCko", "summary": "The paper presents a theoretical extension of the analysis of the Stochastic Localisation framework through replica calculations. In particular, through the study of free entropy, one is able to asymptotically determine thresholds for sampling feasibility via AMP, being the latter conjectured to be optimal for the Bayesian denoising task in a high-dimensional setting. Furthermore, the authors apply their method to the perceptron model, in the spherical and binary weights setup. The spherical case is studied in the case of a uniform distribution on the solution space (non-convex), discussing AMP limits. The binary case is further explored: the authors show that with a peculiar choice of the potential $U(s)$ it is possible to circumvent the issue of a second maximum in the free entropy function, which would make AMP inapplicable. However, they stress that in the presence of structured data AMP would fail either, and it would be necessary to use MCMC; hence, they propose a potential $U_\\tau(s)$ that is a sort of regularised version of $-\\log s$ in order for MCMC to be applied and anneal $\\tau\\to 0$, showing such a procedure is more effective than standard $T$ annealing.", "questions": "1. The paper’s style sits ambiguously between a physics-oriented and a mathematically rigorous presentation, making it difficult to follow for readers outside the core replica theory community. In this form the paper needs, in my opinion, a major reformatting, in accordance with the Limitations I described above. \n2. Key theoretical results lack formal statements (e.g., propositions or theorems) and are not clearly distinguished from prior work such as Ghio et al. (2024). Could the authors explicitly state these results in a formal way to better highlight the novelty and assumptions of their contributions? Even if they prefer a physics-oriented presentation, such highlighting would be beneficial.\n3. The connection to the broader machine learning community currently appears somewhat limited, being mostly confined to the introduction and a few remarks on AMP. In particular, the MCMC component—presented as a key contribution—is discussed rather briefly and remains somewhat disconnected from the wider context of modern sampling techniques in ML. It would significantly enhance the paper’s impact if the authors could elaborate on how their results relate to existing methods in the sampling literature, and clarify both the practical relevance and the limitations of their approach in more realistic ML settings. While additional examples are not necessary beyond those already included, a stronger effort to draw connections or analogies with practical ML applications would be greatly appreciated, especially given the acknowledged limitations of AMP and ASL in real-world scenarios.", "limitations": "Yes, they recognise the limitations inherited from AMP and also from replica calculations.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strenghts**\n- The content of the paper is original, and the claims made in the introduction are convincingly supported throughout the manuscript.\n- From a theoretical standpoint, the results are sound and well validated, even though they rely on the replica method, which the authors correctly acknowledge as “non-rigorous but extensively validated.”\n- The theoretical predictions are empirically verified in a synthetic setup that, while not of direct practical relevance to modern generative models, provides a reasonably novel benchmark for the application of replica methods in machine learning.\n- The authors are transparent about the limitations of the proposed theoretical and algorithmic methods, particularly regarding the use of AMP in realistic data scenarios, which is appropriately acknowledged in several parts of the paper.\n\n**Weaknesses**\n\n#### **1. Style and Structure**\n\nThe paper sits stylistically between a physics-oriented and a mathematically formal presentation. To improve clarity and accessibility:\n\n- If the authors wish to target the *physics-oriented style*, it would be helpful to enhance the intuition behind the derivations and the results, both theoretical and experimental. This should be feasible, as the treated examples are standard and well-known. This would also align better with a broad conference audience rather than a narrow community of replica theory experts.\n- If instead aiming for a more *mathematically rigorous style*, the paper should be revised to adopt a more formal structure, including clearly stated propositions, theorems, assumptions, etc.\n\nCurrently, the hybrid format makes the paper difficult to follow — even for readers familiar with replica theory but not embedded in the specialized community. In its present form, the structure is not well-suited to either tradition.\n\n#### **2. Theoretical Contribution**\n\n- The level of generality beyond *Ghio et al. (2024)* is not entirely clear. To highlight the originality of your contribution, it would be very helpful to explicitly state a proposition from *Ghio et al. (2024)* and then present your generalization as a formal result, ideally in a comparative form. This would greatly assist readers in understanding the novelty of your approach.\n- The discussion on MCMC is presented as a major contribution in both the abstract and the introduction, and it indeed forms an interesting bridge to the sampling community. However, the space dedicated to this result is extremely limited. I recommend expanding the explanation and clarifying its implications and connections to the rest of the work.\n\n#### **3. Presentation of AMP and Replica Results**\n\n- Section 4.2, which introduces AMP, feels isolated and incomplete. It could either be moved to the appendix or expanded to give a more self-contained and pedagogical explanation, especially clarifying the role of $\\phi_{{in}}$ and $\\phi_{{out}}$, which are introduced but never used later.\n- A similar issue arises with the replica computations (e.g., Equations 15–18): they occupy a significant amount of space, but are not discussed or interpreted in the main text. Either move them to the appendix or incorporate them into the narrative with interpretation and relevance.", "was_revised": true, "final_justification": "I appreciate the authors’ detailed and thoughtful response, which carefully addresses my concerns regarding clarity, structure, and theoretical positioning. Their planned revisions—particularly toward a more physics-oriented and accessible presentation—would, in my view, significantly improve the manuscript. However, since I cannot evaluate the revised version directly within the constraints of the NeurIPS review process, I am not in a position to raise my score. I nonetheless believe the proposed changes are promising and encourage the authors to pursue them, as they would strengthen both the clarity and impact of the work.", "rebuttal": "We thank the reviewer for their comments. We appreciate that the reviewer values the significance and novelty of our work, while their main concerns are mostly about style and clarity. \n\nWe agree that statistical‐physics methods used in machine learning may be unfamiliar to some (most!) readers; therefore, we will strive for a gentler introduction to techniques and the concepts employed.\n\nUnfortunately, we don’t have the opportunity to produce an updated version of the manuscript during the rebuttal process, but we will take into consideration the reviewer’s recommendations and improve the readability of the manuscript in the camera-ready version.\n\nIn what follows, we answer their main concerns in detail. We hope that in the light of these answers, the reviewer will be willing to upgrade the overall score.\n\n**Weaknesses and Questions**\n\n> **1. Style and Structure**\n> \n> \n> The paper sits stylistically between a physics-oriented and a mathematically formal presentation. To improve clarity and accessibility...\n> \n\nand also\n\n> The paper’s style sits ambiguously between a physics-oriented and a mathematically rigorous presentation, …\n> \n\nWe agree that the clarity can (and will) be improved. We will embrace the physics-oriented style, which is also quite aligned with certain branches of the theoretical ML literature, and make every effort to enhance the intuition behind the derivations and the results, as suggested by the reviewer, in order to make it more accessible to a broader audience.\n\n> **2. Theoretical Contribution**\n> \n> - The level of generality beyond *Ghio et al. (2024)* is not entirely clear…\n\nand also\n\n> Key theoretical results lack formal statements (e.g., propositions or theorems) and are not clearly distinguished from prior work such as Ghio et al. (2024)…\n> \n\nWe thank the reviewer for these well-motivated comments. The work of Ghio et al. is indeed very close and provides inspiration to our work. In the revised version of the paper, we will highlight more formally the differences between our work and Ghio et al., as we now discuss.\n\nLet us first emphasise the **main limitation of Ghio et al.** that concerns us:\n\n- Their formalism is limited to planted ensembles, where the reference configuration (the one eventually sampled at the end of the generation process) can always be assumed to be the planted one in the theoretical analysis, since it is statistically identical to any other sample from the target distribution thanks to the Bayesian structure of the problem. This allows to avoid dealing with hard-to-compute normalizing factor Z in the denominator.\n- The authors also consider some non-planted settings. However, their analysis hinges on the fact that they are contiguous to their planted versions (a property known as quiet planting). This is not a general feature but is limited to specific problems and regions of the parameter space. These details are thoroughly explained in Section 1 of the Supplementary Information of Ghio et al. Therefore, even in the non-planted settings, they ultimately analyze planted models, which is what their formalism is designed to handle.\n\n**We address this limitation as follows:**\n\n- We introduce a formalism that allows us to deal with generic target distributions, possibly with hard-to-compute normalization factors. It is based on a double application of the replica trick. This greatly expands the range of applicability of the approach.\n- Thanks to the Bayesian structure of the generative diffusion process, we show that the Nishimori conditions hold and simplify the solution of the saddle point equations.\n\nMoreover, **we provide the following further contributions:**\n\n- In the case of the binary weight perceptron, we don’t just confirm the difficulty of sampling from the uniform distribution: our analysis lets us pinpoint precisely the failure mode of the ASL procedure, and identify a minimal correction that overcomes this problem. While some heuristic solvers for the binary perceptron are known (e.g. Braunstein Zecchina [2006], Baldassi Braunstein [2015], and others), this is the first approach that produces samples from a well-defined and theoretically motivated target distribution over binary perceptron solutions.\n- On the algorithmic side, the failure mode analysis also inspired a practical MCMC annealing scheme as a robust solver for generic (non-random) instances of the problem, which is far more effective than standard simulated annealing.\n\n**[Braunstein Zecchina 2006]** *Learning by message passing in networks of discrete synapses.* *PRL* \n\n**[Baldassi Braunstein 2015]** *A max-sum algorithm for training discrete neural networks*. *JSTAT* \n\n**[Ghio et al 2024]** Ghio, Dandi, Krzakala, and Zdeborová, *Sampling with flows, diffusion, and autoregressive neural networks from a spin-glass perspective*, *PNAS* \n\n> The discussion on MCMC is presented as a major contribution in both the abstract and the introduction… However, the space dedicated to this result is extremely limited…\n> \n\nUnfortunately we had to limit that section due to space constraints, and provided a few additional experiments in Appendix C.3. In the revised version, we will comment on possible extensions of our MCMC scheme to other constraint satisfaction problems, discuss the geometry of the solution space on which the tilted measure focuses (dense cluster of solutions) and provide experiments on structured problems. \n\n> **3. Presentation of AMP and Replica Results**\n> \n> - Section 4.2, which introduces AMP, feels isolated and incomplete. It could either be moved to the appendix or …\n> - A similar issue arises with the replica computations (e.g., Equations 15–18)…\n\nWe agree with the referee and we will move to appendices the definitions of the channel free entropies, making room for a more pedagogical explanation of AMP. \n\nOn the other hand, we report the free entropy given by the replica computation in the main text mainly to demonstrate how the analysis of the high-dimensional system is reduced to the analysis of a simple low-dimensional function. We will provide more intuition around the different terms appearing in the formulas.\n\n> The connection to the broader machine learning community currently appears somewhat limited... In particular, the MCMC component—presented as a key contribution—is discussed rather briefly and remains somewhat disconnected from the wider context of modern sampling techniques in ML..\n> \n\nWe thank the reviewer for this thoughtful comment. We agree that clarifying the broader ML relevance of our MCMC-based approach would enhance the paper. In the final version, to the extent allowed by space constraints, we plan to touch on the following aspects:\n\n1. **Connection to Modern ML Sampling:**\n    \n    In the discussion, we will more explicitly connect our work to modern efforts in score-based and diffusion-based generative modeling, and specifically to recent hybrid samplers that combine score estimation with MCMC techniques (e.g., Grenioux et al. [2024]; Vargas et al. [2023]).\n    \n2. **Practical Relevance and Limitations:**\n    \n    We will clarify that ASL, although limited in scope, can be viewed as a diagnostic and conceptual tool for understanding when and how diffusion methods can succeed in sampling hard posterior-like distributions. Its analysis can suggest how to adjust the scheme when it fails, as well as produce algorithmic fallouts such as $\\tau$-annealing MCMC.\n    \n3. **Broader ML Implications:**\n    \n    The models that we investigate in great detail are non-convex neural networks that are of particular interest to the ML community and are also prototypical examples of CSPs. For CSPs, our approach could be extended to other settings and produce tilting strategies that allow for efficient samplers and solvers.\n    \n    In ML contexts, dense regions of solutions / wide minima of the training loss landscape (that are targeted by the introduced tilted measure) have been linked to improved generalization properties (Chaudari et al [2019], Foret et al [2021]). It could be the case that the sampling schemes developed for binary perceptrons can be applied to quantized neural networks: $\\tau$-annealing could potentially improve training and distillation procedures for quantized neural networks. \n    \n\nWe hope these remarks will help clarify the relevance of our work to the broader ML community and demonstrate the practical implications and novelty of the proposed MCMC approach.\n\n**[Grenioux et al 2024]** Grenioux, Noble, Gabrié, and Durmus, *Stochastic localization via iterative posterior sampling*, 2024.\n\n**[Vargas et al 2023]** Vargas, Grathwohl, and Doucet, *Denoising diffusion samplers,* 2023.\n\n**[Chaudari et al 2019]** Chaudhari, Choromanska, Soatto, LeCun, Baldassi,  \nBorgs, Chayes, Sagun, and Zecchina, *Entropy-sgd: Biasing gradient descent into wide valleys*. *JSTAT*\n\n**[Foret et al. 2021]** Forêt, Kleiner, Mobahi, Neyshabur, *Sharpness‐Aware Minimization for Efficiently Improving Generalization,* ICLR"}]

Author rebuttal:

Meta-review: This paper studies sampling in perceptron-type constraint satisfaction problems through the lens of generative diffusion. By analyzing several perceptron variants, the authors characterize regimes of hardness and connect diffusion-based generative processes to the geometry of high-dimensional solution spaces. This provides a fresh and rigorous angle on classical models, bridging ideas from statistical physics and modern generative modeling.

Reviewers found the work technically solid, original, and timely. They highlighted the value of importing diffusion-based perspectives into the study of sampling, and the potential of the framework to inspire further developments. Concerns were raised mainly about scope and accessibility, since the paper is focused on a particular family of models and assumes familiarity with both statistical physics and generative modeling.

The rebuttal clarified positioning and reinforced the motivation, which the reviewers found satisfactory. The consensus after discussion was positive, recognizing that while the paper is specialized, its conceptual contribution is of strong interest.

Overall, I find this a strong and interesting submission. The marriage of diffusion processes with perceptron sampling yields new theoretical insights and broadens the conversation at the intersection of physics and machine learning. I recommend acceptance.
Decision: Accept (poster)