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

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.

We 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.

Unfortunately, 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.

In 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.

Weaknesses and Questions

1. Style and Structure

The paper sits stylistically between a physics-oriented and a mathematically formal presentation. To improve clarity and accessibility...

and also

The paper’s style sits ambiguously between a physics-oriented and a mathematically rigorous presentation, …

We 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.

2. Theoretical Contribution

• The level of generality beyond Ghio et al. (2024) is not entirely clear…

and also

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)…

We 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.

Let us first emphasise the main limitation of Ghio et al. that concerns us:

• 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.
• 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.

We address this limitation as follows:

• 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.
• 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.

Moreover, we provide the following further contributions:

• 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.
• 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.

[Braunstein Zecchina 2006] Learning by message passing in networks of discrete synapses. PRL

[Baldassi Braunstein 2015] A max-sum algorithm for training discrete neural networks. JSTAT

[Ghio et al 2024] Ghio, Dandi, Krzakala, and Zdeborová, Sampling with flows, diffusion, and autoregressive neural networks from a spin-glass perspective, PNAS 

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…

Unfortunately 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.

3. Presentation of AMP and Replica Results

• Section 4.2, which introduces AMP, feels isolated and incomplete. It could either be moved to the appendix or …
• A similar issue arises with the replica computations (e.g., Equations 15–18)…

We 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.

On 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.

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..

We 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:

1. Connection to Modern ML Sampling:

   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]).

2. Practical Relevance and Limitations:

   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.

3. Broader ML Implications:

   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.

   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.

We 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.

[Grenioux et al 2024] Grenioux, Noble, Gabrié, and Durmus, Stochastic localization via iterative posterior sampling, 2024.

[Vargas et al 2023] Vargas, Grathwohl, and Doucet, Denoising diffusion samplers, 2023.

[Chaudari et al 2019] Chaudhari, Choromanska, Soatto, LeCun, Baldassi,
Borgs, Chayes, Sagun, and Zecchina, Entropy-sgd: Biasing gradient descent into wide valleys. JSTAT

[Foret et al. 2021] Forêt, Kleiner, Mobahi, Neyshabur, Sharpness‐Aware Minimization for Efficiently Improving Generalization, ICLR

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.

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.

Unfortunately, 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.

In 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.

Therefore, 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.

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.

We 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.

For further details on the novelty of our work, please see our rebuttal to Referee 6gzG.

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

We 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).

Although 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.

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?

The 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.

[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.

[Lin et al. 2024] Exploring Neural Network Landscapes: Star-Shaped and Geodesic Connectivity, Z. Lin, P. Li and L. Wu, ArXiv (2024).

[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).

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?

Our 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.

Other 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.

[Braunstein and Zecchina 2006] Braunstein, A. and Zecchina, R., Learning by message passing in networks of discrete synapses. Physical Review Letters, 2006.

[Abbe 2022] Abbe, Li, Sly, Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster, STOC 2022

I have read the rebuttal and decided to lower my confidence score based on my unfamiliarity with the subject. I will discuss this with the other reviewers later to determine the final recommendation score.

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.

We 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.

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.

We 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.

We 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.

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) …

and also

(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].

We thank the reviewer for these well-motivated comments. The work Ghio et al is indeed very close and provided inspiration to our work.

Let us first highlight in more detail the main limitation of Ghio et al that concerns us:

• 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.
• 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.

We address this limitation as follows

• 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.
• 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.

Moreover, we provide the following further contributions:

• 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.
• 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.
• 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.

[Braunstein Zecchina 2006] Learning by message passing in networks of discrete synapses. PRL

[Baldassi Braunstein 2015] A max-sum algorithm for training discrete neural networks. JSTAT

[Ghio et al 2024] Ghio, Dandi, Krzakala, and Zdeborová, Sampling with flows, diffusion, and autoregressive neural networks from a spin-glass perspective, PNAS 

[Chaudari et al 2019] Chaudhari, Choromanska, Soatto, LeCun, Baldassi,
Borgs, Chayes, Sagun, and Zecchina, Entropy-sgd: Biasing gradient descent into wide valleys. JSTAT

[Foret et al. 2021] Forêt, Kleiner, Mobahi, Neyshabur, Sharpness‐Aware Minimization for Efficiently Improving Generalization, ICLR

Questions:

(Line 36): The motivation of sampling from such unnormalized probability …

This is a very broad and important topic, for instance, in Bayesian statistics and statistical physics. We will provide more motivation in the revised version.

I think that at several points .. reading the paper might be complex …

We 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.

In the conclusion, the authors mention that the $\tau$-annealing procedure proposed overcomes ASL's limitation ..

It 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.

[Donoho et al 2009] Donoho, Maleki, and Montanari, Message-passing algorithms for compressed sensing, PNAS. 2009.

[Rangan 2011] Generalized Approximate Message Passing for Estimation with Random Linear Mixing, IEEE ISIT 2011.

Moreover, the authors mention that the ideas developed in this paper could enhance "sampling and solving" in other hard CSPs:…

Our 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.

Finally, I list here more minor points:

(Line 128) I would say that in terms of limitations of AMP, time complexity …

The 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.

Equation (12): the introduction of both $T$ and $U$ is a bit redundant…

It 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$.

(Line 243) It is quite surprising at first …

As 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.

(Line 263) Since the computation here is done assuming that is RS…

Our 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.

We thank the reviewer for the positive feedback. In the following, we address the question raised.

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?

In 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$.

We thank the reviewer for the positive feedback. In what follows, we address the questions raised.

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?

The $\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.

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?

We 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.

Under 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]).

Nonetheless, 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.

A 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.

[Huang et Kabashima 2014] Origin of the computational hardness for learning with binary synapses, H. Huang and J. Kabashima, PRE, 2014.

[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.

[Gamarnik 2021] The overlap gap property: A topological barrier to optimizing over random structures, D. Gamarnik, Proc. Natl. Acad. Sci., 2021.