Learning with Restricted Boltzmann Machines: Asymptotics of AMP and GD in High Dimensions
Authors: Yizhou Xu
Florent Krzakala
Lenka Zdeborova
Venue: NeurIPS 2025 poster ()
Keywords: Restricted Boltzmann Machine
Approximate Message Passing
High-dimensional Limit
Multi-index Models
Primary area: theory

Abstract: The Restricted Boltzmann Machine (RBM) is one of the simplest generative neural networks capable of learning input distributions. Despite its simplicity, the analysis of its performance in learning from the training data is only well understood in cases that essentially reduce to singular value decomposition of the data. Here, we consider the limit of a large dimension of the input space and a constant number of hidden units. In this limit, we simplify the standard RBM training objective into a form that is equivalent to the multi-index model with non-separable regularization.  This opens a path to analyze training of the RBM using methods that are established for multi-index models, such as Approximate Message Passing (AMP) and its state evolution, and the analysis of Gradient Descent (GD) via the dynamical mean-field theory. We then give rigorous asymptotics of the training dynamics of RBMs on data generated by the spiked covariance model as a prototype of a structure suitable for unsupervised learning.  We show in particular that RBMs reach the optimal computational weak recovery threshold, aligning with the Baik-Ben Arous-Péché (BBP) transition, in the spiked covariance model.

Learning with Restricted Boltzmann Machines: Asymptotics of AMP and GD in High Dimensions
Yizhou Xu
Florent Krzakala
Information, Learning & Physics Laboratory Statistical Physics of Computation Laboratory EPFL, Switzerland
Information, Learning & Physics Laboratory
EPFL, Switzerland
Lenka Zdeborová
Statistical Physics of Computation Laboratory EPFL, Switzerland
Abstract
The Restricted Boltzmann Machine (RBM) is one of the simplest generative neural networks capable of learning input distributions. Despite its simplicity, the analysis of its performance in learning from the training data is only well understood in cases that essentially reduce to singular value decomposition consider the limit of large dimension of the input space and constant number of hidden units. In this limit, we simplify the standard RBM training objective into a form that is equivalent the multi-index model with non-separable regularization. This opens a path to analyze training of the RBM using methods that are established for multi-index models, such Approximate Message Passing (AMP) and its state evolution, and the analysis of Gradient Descent (GD) via the dynamical mean-field theory. We then give rigorous asymptotics of the training dynamics of RBMs on data generated by the spiked covariance model as prototype of a structure suitable for unsupervised learning. We show particular that RBMs reach the optimal computational weak recovery threshold, aligning with the Baik-Ben Arous-Péché (BBP) transition, in the spiked covariance model.
the data. Here, we
Introduction
The Restricted Boltzmann Machine (RBM) [Hinton 2002 Salakhutdinov et al. 2007 a founda- tional generative model that effectively learns input distributions in unsupervised manner and can be extended to multi-layer architectures [Salakhutdinov and Hinton| 2009]. RBMs have significantly influenced machine learning development and, despite not being sfate-of-the-arr for e.g.,image gen- eration, remain scientific interest and can enhance interpretability (Hu et af.) 2018). They are in particular very popular in modeling the quantum
function in many-body quantum problems [Carloo and Troyer 2017 Melko et al. 2019 Krenn et al. 2023 Nys et al. 2024 in physics and in
modeling protein folding [Mrcoo al. 2011 Muntoni et 2021).
In the wake of generative Al's recent successes, achieving a precise mathematical understanding of how RBMs learn from data is natural first step toward tackling the more intricate dynamics of modern architectures. Yet, the learning behavior of RBMss remains poorly understood, primarily due the intractability of the likelihood function. In practice, stochastic approximations such as contrastive divergence are widely used. While exactly solvable models-Sui such as -Gaussian and Caassian-Spherica RBMs [Karakida et al.) (2066] Decelle [ecelle and Furtlehner 2020) Genovese and Tantari 2020 arr are well understood, they essentially reduce to singular value decomposition (SVD) and fail capture the mechanisms underlying empirical performance. Heuristic analyses using the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

replica method also exist in the statistical physics literature [Alemanno et al., 2023 Thériault et al. 2024 Manzan and Tantari 2024). but in addition to their non-rgooouu nature, they often fail reflect the actual training procedure used in practice-namelyy maximum likelihood estimation. Instead, they focus on Bayesian posterior sampling, which yields qualitatively different predictions. The only works studying the full learning on the usual likelihood objective is as far as we know (Bachtis et al., 2024| Harsh et al. 2020], and we will comment on the differences with our work below.
This gap in our theoretical understanding of RBMs stands in stark contrast to recent progress on feed- forward networks, a field that has seen a surge of analytical results, especially in high high-dimensional regimes with synthetic data, where rigorous insights are increasingly available, see e.g. Soltanolkotabi ct al. [2018), MMi et al. [2019), Celentano et al. 2020). Gerbellt et al. (2024). Bietti al. [2023].
Motivated by this progress, we analyze empirical likelihood maximization for RBMs directly, in a setting that mirrors practical training procedures. Specifically, we consider the high-dimensional limit in which both the data dimension and the number of samples tend to infinity, while the number of hidden units remains fixed. This regime is relevant for many real-world applications, where data often lies on low-dimensional manifolds embedded in high-dimensional spaces. In this limit, the likelihood function admits simplified form that reduces to an unsupervised variant of the multi-index model-a framework that has proven useful for studying neural networks and gradient descent in non-convex, high- nigh-dimensional settings (Saad and Solla 1995 Abbe al., 2023 Damian et al.) 2023 Troiani et al.) 2024]. Leveraging this connection, one can characterize the learning dynamics and derive sharp asymptotic results for data generated by the celebrated spiked covariance model [Johnstone] 2001
Main results- - Our contributions are the following:
i) We prove that, in high dimensions and with finitely many hidden units, the RBM training objective asymptotically equivalent to an unsupervised multi-index model with non-separable regularization. This characterization is key to our analysis, as it allows the use of established mathematical techniques for synthetic data. As a model for data, we consider the well-studied spiked covariance model and emphasise its equivalence to teacher RBM.
ii) Thanks to this mapping, we show that one can rigorously analyze the asymptoties of RBMs trained on the spiked covariance data. We apply large body of recent results from multi-index and supervised models to RBMs. In particular, we derive sharp asymptotics for the simplified objective and introduce an Approximate Message Passing (AMP) algorithm to train the model. This allows us to characterize the global optimum of the objective for a number of cases. We establish that the weak recovery threshold of RBMs matches the optimal BBP threshold (Baik et al. 20055. J. i.e., the minimal signal-to-noise ratio to detect the signal).
iii) We provide rigorous, closed-form equations describing the exact high- -ish-iiiensional asymptotics of gradient descent dynamics. These results generalize dynamical mean-field theory, which was previously limited to multi-index and tensor learning problems.
Overall, our analysis opens the door a precise mathematical understanding of unsupervised learning in RBMs, a foundational generative model. By mapping the likelihood landscape of RBMs in the high-dimensional regime that of an effective model, we are able import a range of tools and results that were previously restricted to supervised learning in single- and two-layer networks. This connection not only yields sharp predictions for optimization and dynamics in RBMs, but also lays the groundwork for extending these techniques to more complex generative architectures such as diffusion models.
Related works - Decelle et al. 2017 2018) analyze the learning dynamics of RBMs, primarily focusing on the linear regime, which corresponds to Gaussian- -Gaussian RBMs. In the non-linear regime, their analysis relies on the assumption that the weights remain sampled from a spiked ensemble throughout training. However, this assumption breaks down in practice, as the training process induces strong correlations among the weights. Certain versions of RBMs have been analyzed within the framework of the Hopfield model [Barra al. 2012 Mézard 2017 Barra al. 2018), but for fixed weights (patterns). A series of works have employed heuristic statistical mechanics techniques- such as the replica method to study the training of RBMs in peacher-studer settings [Huang and Toyoizumi 2016 Huang 2017 Hou et al. [019 Alemanno et al. 2023 Thériault et al.) 2024| Manzan and Tantari 2024]. However, their approach is closer to Bayesian sampling of the posterior over weights and deviates from the standard likelihood maximization typically used in practice (see Appendix (A). Additionally, these studies do not frame their results in terms of spiked
covariance models, thereby missing the clear connection to the broader literature on learning in
2

---

high dimensional statistics. In contrast, we study the actual gradient descent algorithm applied to the maximum likelihood objective, and we rigorously demonstrate that RBMs achieve the optimal weak recovery threshold of the spiked covariance model. Recent works [Bachtis et al. 2024 Harsh al., 2020] study the early training dynamics of RBMs in a similar setting (large dimension, few hidden units) and offer valuable heuristic insights into GD dynamics over time. Their analysis is
non-rigorous, whereas our results provide exact asymptotics, including the characterization of saddle points; they also do not connect to multi-index models, AMP or the spiked covariance model.
Approximate Message Passing (AMP) has become a tool for the rigorous analysis of high-dimensional statistical inference and machine learning. It provides sharp asymptotics of both Bayesian inference and empirical risk minimization
wide range of models, including spiked matrices and tensors [Donoho et al.; [2099] ( Javanmard and Montanari, 2013, Montanari and Richard 2014 Lesieur et al.) 6017,Cellntann
al. 2021] Allaui et al. [023]] In this work, we use AMP as proof technique to analyze the asymptotics of RBMs, both in the context of empirical risk minimization and in the study of gradient descent dynamics. This leverages on many recent progresses (Ceennaano et al.) 2020). Fan
2021]AAlaoii
[2022), Gerbelot et al. 2022 2024). Note that while variants of AMP have been used in the context of RBM training in prior works e.g... [Gabrié et al. 2015 Tramel et al. 2018) - were employed for sampling from the posterior distribution over fixed weights, rather than for directly training the
weights. This stands in contrast to our approach, where AMP is used to analyze and characterize the actual learning dynamics of RBMs under empirical risk minimization.
Multi-inder models have been the subject of extensive recent work; see, for example, [Abbe et al. 2023 Damian et al. 2023 Bietti et al., [023 Troiani et al. [2024] and references therein. Spiked covariance models have also been studied in detail from multiple perspectives, including information-
theoretic limits (Lelarge and Miolane 2017 Miolane| 2017 El Alaoui et al. [2020), energy landscape
analysis [Arous et al. 2019). and spectral methods [Baik et al. 2005].
Notations - We use the bold uppercase of a letter to denote a matrix, its bold lowercase to denote the corresponding row vectors, and its lowercase denote element. For example, use X E IRax to denote the data, Ty E R2d to denote the f--th data point, and Tyz to denote the i-th th component of the μ-th data point. We use uppercase letters to denote random variables and bold uppercase letters to denote vectors of random variables. We use || to denote the L norm, || ||F to denote the Frobenius norm and || ||r to denote the L, norm.
2 Settings
A Restricted Boltzmann Machine (RBM) learns an underlying distribution from n samples of d- dimensional (usually binary) data X E R We will consider RBM with d visible and & hidden units represented by the following probability distribution
Wh- o u+t d.. (k)
dP(v, h)) Z(W,0,
where visible and hidden units are e E Rdd h E RR learnable parameters are the biases b E TR* is the normalization factor (the partition
E IRd and the weights W E ddck and Z Z(W, w, 0, b) function)
z(W, (.W.))) = d (P, (h) eo Wh+ 0 w+b"
(2)
The scaling 1/vd is added to keep the energy per data point of order in the large-dimensional limit. Pe (over Rd) and Ph. (over R$) represent the prior distributions of visible and hidden units, respectively.
RBMs are most commonly trained by maximizing the likelihood (marginalized over the hidden units) of the training set, which means that the weight matrix selected in way maximize
II
/ (P) e do "I Wh+ Ja TT xx, +b +bT,, hy
L(W, 0. = Z(W, 0, b)n
1=1
Here Z(W, 0, b) is the normalization not depend on the training parameters W. O.b.
Note that the factor Pa (T),)) is dropped because it does
We will consider the limit d + oo and n = ad, with a fixed sampling rate a = + and fixed number of units A= (())
3

---

3 Equivalent effective objective in high-dimension
Our first result is that the arguably complicated likelihood of the RBM is asymptotically equivalent, in high-ding -igh--imnnsson and with any finite number of hidden units, to that of an effective, simpler model. Interestingly, this result holds for any data (not only Gaussian ones).
We assume that the RBM satisfies the following common assumption:
Assumption 1. P. is factorizable (i.e,P((v)) (((s)) distribution with a bounded support, zero mean and unil variance. Pn is a bounded distribution.
We expect that the bounded assumption and unit variance purely technical and can be relaxed, e.g., to sub- Gaussian. However, the simplification of the log-likelihood in Theorem Trqquirss the prior of the visible units P. to have mean, which is acceptable as we can train the biases.
Theorem 1. Under Assumption
| we have
d lim ğ
log L(W, 0, - log L(W, 0,b,) -0
(4)
where
n log (e,,eWWWW, 0) = Σ M is the effective log-likelihood function, with 7n R x xR - R defined
w
xmbb) 1172 ( w w. J ST 0, 1
T
nn
Du
Vn
1=1
(5)
T/ (IW, To. b) = log / (P) 'o (Voze (T
Vaxo
(6)
and 12 kxk x R
R x R + R defined as
T2 (2(Qu (Qw: Qwo Qo b) = log dPh((h))) "T bt(h" ( hwhhth Qwe-Qoll
(7)
The limit in (4 holds for any sequence X (d) Ruxd, and W E dR O(d) RR b(d) RR
with [ (d) (1((2) (((d)) bounded.
(d)
The proof of Theorem I is presented in Appendix B.I where we also discuss visible units with non-zero mean. Theorem maps RBMs to (5). an unsupervised version of the multi-index model for which the likelihood function depends only on k = @(1) projections of the weights on the high- dimensional data, i.e., on (w- ==) see e.g.. (Troiani et al. 2024). The model has a non-separable regularization term 7/2. which only depends on the type of the hidden units. The analysis of the multi-index model with such a penalty 7/2 poses technical challenge that we resolve in this paper.
Gradients and expectations One can further interpret the simplified model through its gradient, which is what matters for training. For simplicity, we consider biasless RBMs here. See Appendix B.3 for more details. The gradient of (5) reads
a
Vw log 2 [(W, 0,
Σ #=1
Vm //n) @ x a (V
(8)
where we denote Q(W) == W W E R&xk This is particularly interesting when contrasted with the original gradient used standard training techniques. Indeed, the gradient of the original RBM model (3) can be written as the difference between the so-called clamped average (.) (where the visible units are fixed by the dataset and the hidden units are sampled conditionally) and the model average (') Decelle and Furtlehner 2021
Vw log L(W, 0, = Σ h T)D
(he' model- Vd
n
In the effective model, while the first (clamped) term- which trivial to compute conpute-remains, remains, the second term (which priori requires high-ddmensional integration in dimensions) is replaced by
1 Vd (hx (hxT)) (1hh ) W.
V log C(w, 0,b)
(10)

---

This is drastic simplification that arises in the dinge-dimessional limit, at least when the number of hidden units remains moderate. In fact, the average (hh') "ah"), ir can be computed exactly even with a moderately large number of hidden units (e.g., around 20). The key point is that we have replaced challenging high-dimensional sampling problem with much simpler one lower dimension-namelyy in the hidden space.
Training with the equivalent objective - Before turning to our theoretical analysis, we note that the aforementioned equivalence can also be used in practice, which is of independent interest. We illustrate this on a number of toy problems in Appendix [ where we show that it is possible to train an RBM using the simplified effective objective and obtain results comparable to those achieved with standard training methods. This highlights not only the practical relevance of our analysis, but also the potential of the effective model to serve an alternative to traditional training.
4 Spiked covariance model
Thanks to the equivalence with the effective model, we are now in a position to present a set of mathematical results that enable to transfer insights and techniques developed for multi-index models, and shallow supervised architectures to the study of RBMs' learning. For this we must model the imput data. The canonical model of high-dimensional data for unsupervised learning the spiked covariance model Johnstone [000]]. where n samples of d-dimensional data are generated as follows:
X= 1 UWWW"")" + R
(11)
Vd
where U E Ruxr W _ddx are hidden signals, and A E gx is diagonal, representing the AN 1) represent the noise. We further suppose that hidden 4td
signal-to-noise ratio. {Zi 1n.d
sid
J=z=1 ~
spikes are sampled from {u; ] Ji=1 Pa and {wi itd Pw.. where Pu; Pu are some distributions over R". We will assume that r= ((1) is fixed when n, d go to infinity. Our results also apply to a slightly more general data model with non-linearity and non-Gaussian noise. See Appendix C.I As the spiked covariance model is the simplest unsupervised model, any good unsupervised method for the data from the model has be able recover in some way the latent structure, i.e., the variables U and W" For a special case we can map the spiked covariance model to a teacher RBM. Consider the spiked covariance model (T]) with A AI. The distribution of X conditioned on W reads
1
[(X = 22T
EU exp
X
U vd
X2
Ev- 11 1=1 exp
+
I U na w
U W
aii)
2
2d
a,1=1
1=1
a=1
(12)
Suppose that 1/ Ei= wh ~ 0, i.c., teacher weights are approximately orthogonal, and that who E ([1,1)} Then we have PXX W*) ~ mh P(x,, W*), where
("e,:"")= == z(W")
B exp
|
+
Σ a,1=1
I Una Was
(13)
2
Meanwhile, for the (teacher) RBM we have P(v|W*)= = remove the biases and use V* to represent the weights of the (teacher) RBM. This is consistent with the conditional distribution of RBMs analyzed in Huang and Toyoizumi [2016). Huang (0177] Hou
Z(W"] Eye Ja" W by ( where we
P.(v)
ct al. [2019), Alemanno et al. 2023 Thériault et al. [2024), Manzan and Tantari 2024
(v(v) (W"
E A whh
PoolWW)
(14)
where the additional parameter 3 denotes the inverse temperature of the (teacher) RBM.
Therefore, we can map (3) to 14h through the mapping Tys u - v, h, 3 and dP(v) x e =l Thus, spiked covariance model with Bernoulli priors can be regarded as teacher RBM
5

---

Algorithm AMP-RBM
Require: Initialization U - - 0, - Zz E Rdxk and damping Ç E [0, 1) for 1 = 1, .T do
W -((Z,, Q Ct-1) E Raxk B₁ n Ei=
of (2 (2/ Q') BR
Y -XW' - Bi E Ruxk
Vn
U = g(Y B.) E Baxk C₁ = -, -
By By,
(4/) REXE
z I X T -'WWC, E ERaxk.
Q |+1 CQ¹ t
+ - (V (Q)Vn(Q(WW))) BR
end for
with orthogonal teacher weights, Bernoulli hidden units, and Gaussian visible units, where À can be understood the inverse temperature, i.e., the strength of the teacher features. However, emphasize that none the existing literature concerning the teacher-student RBMs considers the practical training scheme (i.e., maximizing the log-likelihood), See discussions in Appendix
The large-dimensional limit of the data model corresponds to an RBM with a large number d of visible units, &o- = (11) hidden units learning from number of samples proportional to the dimension n ad, and the samples have r = (11) features. Note that we do not require & = r to account for the overparameterized and underparameterizee schemes.
Main theorems and technical results
Now consider synthetic spiked data X as defined in and the optimization of
max log ((W) == max W
Σ m1 [ may (QT2(Q(W))
(15)
W
for general choice of 71 and 7/2- including the ones defined in 6 and but with all parameters except the first set to zero. We drop the biases 0, for simplicity, because it is straightforward to modify our results to include them.
AMP-RBM- We first present AMP-RBM practical algorithm optimize 15 While it is common to use AMP for supervised generalized linear regression [Donoho et al. 2009 Javanmard and Montanari 2013), ,, the novelty is for spiked data, and its rigorous analysis. Other new aspects are the spiked structure of the input data, and the penalty term 7/2- To deal with 1/2. introduce the Lagrange multiplier decouple the joint optimization over Q and W, which enables alternating optimization. The new optimization problem
variant of this algorithm train the unsupervised RBM
(2 W Vn) mn + Q (e WTW W d
min max
Q W.O
#=1
thus becomes separable w.r.t. W. We can write an AMP algorithm to optimize it for fixed Q Q and then update Q accordingly. This gives AMP-RBM (Algorithm []. Technically it is variant of the AMP in Montanari and Venkataramanan 2021 with the Lagrange multiplier Q to be the main modification.
In AMM. choose the denoisers to be separable and
f(x', Q Cr-)) arg min Q w (c +1 wot.::ttaCCCCCC.ttt. (16)
- (2Q² + C.-1) 2"
g(y'B = B, (h' )²²), nt' = arg min
a - n (h) + ; (h ( B. (h -2) (17)
h

---

Q Ct-1) R and similarly for g. Moreover, Vr2 R - B is the derivative of 7/2 R - R w.r.t. its argument. The interest of this analysis lies in Theorem 2 the fixed points of AMP-RBM are exactly the stationary points of the optimization problem (15). which is proven in Appendix C.3 In Appendix D we show that these and conjecture that this is true in general.
By separability we mean that [f(z", Q' CC-I))e := f(z
match the global optimum for l =
Theorem 2. Suppose that n, 122 and g are continuously differentiable. Let W be the value of W the fixed point of AMP-RBM. Then we have
1 W log ((W) Σ V -wwVnaaaaaaWww)) = 0,
a
(18)
where Vnp2: Bkxk Bakkk and Vm R R denote the derivatives of d and 1/2-
AMP-RBM follows family of general AMP iterations described in Appendix The most attractive property of the AMP family is that there low-dimensional, deterministic recursion called the state evolution (SE) that can track its performance:
M, = a- WE + E/" Q, C.-IW
Σ. = a. - ( + " Qu (LW)((MW + +E G,
Q, = a.,, B, = a /M + + G.
(19)
M,+1 = [[g(M,U + E,G, BU
Σ = R[g(M,U- + E,G. B.) + E,G, B.)
2 = CÔ' +
-1-='''+++ (1- C.:EEVs(M.U E,G,
where M., M,, E,, Er, Cr, Q E BAxk and r == Van B is the effective signal- noise ratio. M1 is determined by the initialization. The expectation is w.r.t. independent random
variables U, W. G R sampled from U [1r]
Pu. W [1>] Pw.. [G.] sid N(O, 1), and U. = Wa 0 for a >> r, where U [ar]] W [1rr] refer to the first r elements of U.W. VS R x R Axk x R & + Rix& refers to the derivatives of f w.r. its first argument, and similarly for g.
We have the following theorem formally describing how AMP-RBM is tracked by its SE. is special case of the SE of general AMP iteration proven in Appendix C.2
Theorem 3. Suppose that f. g and Vnp are Lipschitz continuous, uniformly at (B., C. 2, H and further assume that the initialization satisfies {=t,.... = ädd M,W + 2 G. Then for any
(T) Peo b), the following 3 holds almost surely for 2
lim d-000
(ww w = (W,
E. Q C.-1)))
(20)
quite straightffrward extend Theorem 3 to the spectral initialization as in Montanari and Venkataramanan [02T Theorem 5]. We emphasize that AMP-RBM is indeed practical algorithm and it empirically works well for both the spectral initialization and the random initialization. For spectral initialization, the SE (Theorem 3 still holds. However, for random initialization, the correlation between the signal and the estimation might keep zero until O(log d) iterations [Li et al. 2023), while the SE only holds for (11) iterations.
An important performance criterion concerning the spiked covariance model is the SNR which the algorithm begins to obtain a non-zero correlation with the signal, which is referred to as the weak recovery threshold Troiani et al. 2024 For the weak recovery threshold, we can consider
'f c) is uniformly Lipschitz at co if there is an open neighborhood of co and a constant L such that ((,c) is L- LLpischhtzz for any e E U and [fx c1) f(z, ez)l & L(1 + ||x]])]ec e2| for any e1, E U. Se-pseudo-Lipschiee
function order 2, satisfying (=1)) - ((=2)) S C1 æ2 [[[1 (1+ + || ||m2|l) for some constant C 2 O.
A similar result also holds for U. See Theorem
7

---

1.0
0.8
average overlap
0.8
31
overlap
0.6
0.6
52
0.4
0.4
Z2
Bayes optimal
0.2
0.2
AMP-RBM
GD
0.0
0.0
0.5
1.0
1.5
2.0
2.5
iteration
2,A 1.412 so the overlap is 2 x 2 matrix containing Ç11, Ç12, S21, {22. Lines denote the state evolution. Right: The performance of AMP-RBM, GD (over (15) and the Bayes optimality Lesicur al. (2017) for
Figure 1: Left: Iteration curves of AMP-RBM. r
and = di 0.5A), where AMP-RBM RMP and GD use random initialization. The dashed blue line represents the BBP transition. The purple and yellow lines represent the SE of AMP-RBM and GD, which almost overlap. We use the Rademacher prior and n 8000, d = 4000.
the linearization of AMP-RBM around For close to O, we have a am (a0) Re 3 x, and thus gly', B,) (B, -
Moreover, around W 0 have Q ~ L and thus f(= Q, C,-1)
-2-1)- In
this case, AMP-RBM becomes equivalent to the power method, so its weak recovery threshold is exactly the celebrated BBP threshold (Baik et al. 2005], below which it is information theoretically impossible to distinguish the signals from the noise [Deshpande and Montanari [014]). Thus AMP- RBM as well RBMs (because Theorem Sugggests that their fixed points match) are in this sense optimal in detecting the signals. To see this, we can assume M, << Ex << 1, and expand the state evolution
M, aa +
M, = -BB + 1 M, E++1 1,)
(21)
Σ, a
(B. (B 1,)-1,
which gives M t+1 E M +11 = T Σ, M., Therefore, 0 is stable fixed point of AMP-RBM and only of
a.4 max $
(22)
The transition point is just standard BBP transition Amax =a 1/4 Note that all the above analysis does not assume A r. so the weak recovery threshold remains the same when the number of hidden units does not match the number of signals, which is common in practice. This is in sharp contrast with the results Thériault et al. [2024] Manzan Tantari [2024), which essentially use different loss function (in the zero temperature limit) and suggest the system is in the spin glass phase.
Our numerics are presented in Figure where we measure the overlap between W and the AMP- RBM algorithm output. The left side of Figure [ verifies Theorem 3 and the right side of Figure ] verifies that the weak recovery threshold of AMP-RBM matches the BBP transition. See Appendix T. for more experiments, including degenerate eigenvalues and more comparisons with other algorithms.
Asymptotics of the likelihood extremizers AMP-RBM also be utilized proof technique to obtain an asymptotic description of the stationary points of (15) under further assumption.
Assumption 2. AMP-RBM converges its fixed point (i.e., the stationary point of (5)) uniformly, that there exists W (d) lim (d) such that
lim lim [I (d)l 0, do0 d
(23)
and this holds for any output of Algorithm 7
While Assumption 2 might seem artificial, in Appendix we will show that actually it comes from a more essential condition (Assumption called the replicon stability condition or de Almeida- Thouless condition (de Almeida and Thouless 1978), which characterizes the complexity of land- scapes, the landscape is well behaved the replicon stability condition holds. Assumption 2 (te convergence of AMP-RBB RBM) is also verified by the numerics in Figure]

---

Now in Theorem we characterize the asymptotic property of the stationary point W.
Theorem 4. Under Assumptions 2 and assuming that is uniformly Lipschitz at B,, we have lima-sso IIVdV log (d))l) = O, where the asymptotic stationary point (() satisfies
lim
(w (IWWW,(MMMM W E. G, Coc)..
(24)
Here Coc oim Co M == lim M, Ex = lim En and Q lim Q2 well-defined matrices.
Specifically, choosing (ww wb.) = (w)) wi we can measure how much the stationary points proved Appendix C.4 by combining Theorem and Theorem 3 In Appendix [ we will prove that for the special case k = 1, Theorem 4 also describes the global optimum. We conjecture that this true in general, but our proof technique, that relies on the Gordon mini-max theorem [Gordon 1988 Thrampoulidis et al. 2013 Vilucchio et al.) 2025]. notably difficult to adapt to larger values of k. An interesting corollary is that there exists a stationary point where different units align with different signals, even when the number of hidden units different from the number of signals.
W overlap with the features W Theorem
Corollary 1. Under the conditions in Theorem f and further assuming that Pus Pas Ph are factor- izable and symmetric, there exists asymptolic stationary point with all matrices in Theorem diagonal.
Corollary I is proved in Appendix C.5 It suggests that the stationary points it specified. the weights of different hidden units are orthogonal. For the overparameterized scheme, & units of the RBM are aligned with & independent signals, and the other k weight vectors pure noise. For the underparameterized scheme, & units the RBM are still aligned with & independent signals, randomly chosen out of independent signals. This outperforms SVD, which cannot distinguish different signals. See Appendix F.2 for the training dynamics of RBMs concerning this point.
However, algorithms might not converge to the stationary points specified by Corollary I It is the interaction between the signal prior and 1)1 that determines how much the hidden units align with the signals. Inspired by the global optimality of rank-1 case proved in Appendix [ we conjecture that the stationary points specified by Corollary arre actually global minima, which is reachable by informed initialization of AMP-RBM. but uninformed algorithms might not necessarily find it. Numerical evidence can be found in Appendix
Asymptotic analysis of the gradient descent dynamics- Finally, provide the asymptotics of GD for (15), sometimes referred to as DMFT (dynamic mean-field theory) [Maimbourg et al.
2016 Roy et al. 2019 Mignacco al., 2020 Mignacco and Urbani 2022 Gerbelot al. [202]] While contrastive divergence is preferred to GD in practice, we believe that they have qualitatively similar performances ccnntrastive divergence essentially approximation of GD which is
also validated in Appendix on real datasets. GD over (5) reads
E
W
++1 = W'
+ K Σ Vm (z) [=. / / aWVn2(Q(W"))
(25)
with &. the learning rate. Its asymptotics can be described by the following low dimensional iteration.
C11
A sequence of k-dimensional random variables (U,,Y, W., Z.h22 are defined as
Ca
Ú. f((Y, Y............................... \1) (Ý,," Y, (M1,'" M.UU +N(00, Σx),
(26)
W. e+1 = 9r+1 (2 2.-1.".. ... 21),
0.2
10
15
where
Figure Iteration curves GD, where lines denote its asymptotics. The same set- ting as Figure
(27)
... 2.) = (N1."..,N))) +N(00, S2.)

---

and
M, a E[,, WT, [Ele a L. T Wil, B Ū,}-
T
(28)
_ N41 E(Ü 101++111 UJr
1 and [Ecl are given by initialization w Wo. We note that M,, N₂ E R and Ee, S2 E lxxxxixt, The functions ft,9241 12xxt + R are rather involved and are defined an iterative way, so we put their definitions in Appendix C.6
The following theorem gives the asymptotics GD, which proven in Appendix C.6
Theorem 5. Assume that Vmn, Vnz are Lipschitz continuous. Then, for any PL(2) function vb, the following holds almost surely for to 0:
lim
(w, ) (W W.).
(29)
Moreover, we further assume that GD converges to W uniformly as in Assumption 2 we have
lim ā Σ (ww,, in.)) = lim (W W, W.] d-+00
(30)
to
i=1
almost surely, where the limits on both sides are well defined.
Theorem is illustrated in Figure Similar the linearization AMP-RBM, linearization of GD yields the same weak recovery threshold because both of them reduces to the power methods. This is demonstrated empirically in Figure Figure a suggests that GD converges to a similar point as AMP-RBM. Some preliminary analysis of GD dynamics is presents in Appendix F2
Acknowledgement
We would like to thank CECAM at EPFL for organising a workshop where Gianluca Manzan presented his work Manzan and Tantari (024] that inspired our work. We would also like thank Remi Monasson for insightful discussions. We acknowledge funding from the Swiss National Science Foundation grants SNSF SMArtNet (grant number 212049), OperaGOST (grant number 200021
200390) and DSGIANGO (grant number 225837).
References
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference Learning Theory, pages 2552-2623. PMLR, 2023.
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke, Sampling from meen-fieel Gibbs measures via diffusion processes. arXiv preprint arxiv:2310.08912. 2023.
Francesco Alemanno, Luca Camanzi, Gianluca Manzan, and Daniele Tantari. Hopfield model with planted patterns: A teacher-student self-supervised leamning model. Applied Mathematics and Computation, 458: 18825,, 2023.
Gerard Ben Arous, Song Mei, Andrea Montanari, and Mihai Nica. The landscape of the spiked tensor model. Communications on Pure and Applied Mathematics, (2(11):2282 -2300 2019.
Dimitrios Bachtis, Giulio Biroli, Aurélien Decelle, and Beatriz Seoane. Cascade of phase transitions in the training of energy-based models. arXiv preprint arXiv:2405. 14689, 2024.
Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Annals of Probability, pages 1643-1697, 2005.
Adriano Barra, Alberto Bernacchia, Enrica Santucci, and Pierluigi Contucci. On the equivalence of Hopfield networks and Boltzmann machines. Neural Networks, 34:1-9, 2012.
10

---

Adriano Barra, Giuseppe Genovese, Peter Sollich, and Daniele Tantari. Phase diagram of restricted Boltzmann machines and generalized Hopfield networks with arbitrary priors. Physical Review E. 97(2):022300, 2018.
Alberto Bietti, Joan Bruna, and Loucas Pillaud- Vivien. On learning Gaussian multi-ine indexx models with gradient flow. arXiv preprint arXiv:2310. 19793, 2023.
Giuseppe Carleo and Matthias Troyer. Solving the quantum many- body problem with artificial neural networks. Science, 355(6325):602 606, 2017.
Michael Celentano, Andrea Montanari, and Yuchen Wu. The estimation error of general first order methods. In Conference on Learning Theory, pages 1078- 1 141. PMLR, 2020.
Michael Celentano, Chen Cheng, and Andrea Montanari. The high- disensimnnsi asymptotics of first order methods with random data. arXiv preprint /2.:7//2..077,, 2021.
Wei Kuo Chen and Wai-Kit Lam. Universality of approximate message passing algorithms. Electronic Journal of Probability, 26:36, 2021.
Alex Damian, Eshaan Nichani, Rong Ge, and Jason D Lee. Smoothing the landscape boosts the signal for SGD: Optimal sample complexity for learning single index models. Advances Neural Information Processing Systems, 36:752-784, 2023.
Jairo RL de Almeida and David J Thouless. Stability of the Sherrington Kirkpatrick solution of spin glass model. Journal of Physics A: Mathematical and General, 11(5):983, 1978.
Aurélien Decelle and Cyril Furtlehner. Gaussian-spherical restricted of Physies A: Mathematical and Theoretical, 53(18):184002, 2020.
restricced Boltzmann machines. Journal
Aurelien Decelle and Cyril Furtlchner. Restricted Boltzmann machine: Recent advances and mean- field theory. Chinese Physics B, 30(4):040202, 2021.
Aurélien Decelle, Giancarlo Fissore, and Cyril Furtlehner. Spectral dynamics of learning in restricted Boltzmann machines. Europhysics Letters, 1 11966),0001, 2017.
Aurélien Decelle, Giancarlo Fissore, and Cyril Furtlehner. Thermodynamics of restricted Boltzmann machines and related learning dynamics. Journal of Statistical Physics, 172: 1626 2018
Yash Deshpande and Andrea Montanari. Informattoo-tthoorrtiaaall optimal sparse pca. In 2014 IEEE International Symposium on Information Theory, pages 2197-2201. IEEE, 2014.
David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed
sensing. Proceedings of the National Acudemy of Sciences, 106(45): 106(45):18914-10 18914-1899, 2009.
Ahmed El Alaoui, Florent Krzakala, and Michael Jordan. Fundamental limits of detection in the spiked Wigner model. The Annals of Statistics, 48(2):863-885, 2020.
Melikasadat Emami, Mojtaba Sahraee-Ardakan Parthe Pandit, Sundeep Rangan, and Alyson Fletcher. Generalization error generalized linear models in high dimensions. In International Conference Machine Learning, pages 2892-2901. PMLR, 2020.
Zhou Fan. Approximate message passing algorithms for rotationally invariant matrices. The Annals of Statistics, 50(1):197-224, 2022.
Marylou Gabrié, Eric W Tramel, and Florent Krzakala. Training restricted Boltzmann machine via the Moouless-Anderson-PPl Palmer free energy. Advances in neural information processing systems, 28, 2015.
Giuseppe Genovese and Daniele Tantari. Legendre equivalences of spherical Boltzmann machines. Journal of Physics A: Mathematical and Theoretical, 53(9):094001, 2020.
Cedric Gerbelot, Alia Abbara, and Florent Krzakala. Asymptotic errors for teacher-student convex generalized linear models (or: How to prove kabashima's 's replica formula). IEEE Transactions on Information Theory, 824--1884 2022.

---

Cedric Gerbelot, Emanuele Troiani, Francesca Mignacco, Florent Krzakala, and Lenka Zdeborova. Rigorous dynamical mean-field theory for stochastic gradient descent methods. SIAM Journal on Mathematics of Data Science, 6(2):400-427, 2024.
Y. Gordon, On milman's s inequality and random subspaces which escape through a mesh in R", In Joram Lindenstrauss and Vitali D. Milman, editors, Geometric Aspects of Functional Analysis, pages 84-106, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg. ISBN 978-3-540-39235-
Alice Guionnet, Justin Ko, Florent Krzakala, Pierre Mergny, and Lenka Zdeborová. Spectral phase transitions in non-linear Wigner spiked models. arXiv preprint arXiv:2310. 14055, 2023.
Moshir Harsh, Jérôme Tubiana, Simona Cocco, and Rémi Monasson. 'place-cell' emergence and learning of invariant data with restricted Boltzmann machines: breaking and dynamical restoration of continuous symmetries in the weight space. Journal of Physics A: Mathematical and Theoretical, 53(17):174002, 2020.
Geoffrey E Hinton.
Training products of experts by minimizing contrastive divergence. Neural computation, 14(8):1771-1800 2002.
Geoffrey E Hinton. A practical guide training restricted Boltzmann machines. In Neural Networks: Tricks of the Trade: Second Edition, pages 599-619. Springer, 2012.
Tianqi Hou, KY Michael Wong, and Haiping Huang. Minimal model of permutation symmetry in unsupervised learning. Journal of Physics A: Mathematical and Theoretical, 52(41):414001, 2019.
Xintao Hu, Heng Huang. Bo Peng, Junwei Han, Nian Liu, Jinglei Lv, Lei Guo, Christine Guo, and Tianming Liu. Latent source mining in fmri via restricted Boltzmann machine. Human brain mapping, 39(6):2368-2333 2018.
Haiping Huang. Statistical mechanics of unsupervised feature learning in a restricted Boltzmann machine with binary synapses. Journal of Statistical Mechanics: Theory and Experiment, 2017(5): 053302, 2017.
Haiping Huang and Taro Toyoizumi. Unsupervised feature learning from finite data by message passing: discontinuous versus continuous phase transition. Physical Review E, 94(6), 2016.
Adel Javanmard and Andrea Montanari. State evolution for general approximate message passing algorithms, with applications to spatial coupling. Information and Inference: A Journal of the IMA, 2(2):115-144, 2013.
Tiefeng Jiang. The limiting distributions of eigenvalues of sample correlation matrices. Sankhyā: The Indian Journal of Statistics, pages 35-48, 2004.
lain M Johnstone. On the distribution of the largest eigenvalue in principal components analysis. The Annals of statistics, 29(2):295-321 2001.
Ryo Karakida, Masato Okada, and Shun-ichi Amari. Dynamical analysis of contrastive divergence learning: Restricted Boltzmann machines with Gaussian visible units. Neural Networks, 79:78-87 87, 2016.
Mario Krenn, Jonas Landgraf, Thomas Foesel, and Florian Marquardt. Artificial intelligence and machine learning for quantum technologies. Physical Review A, 107(1)010101, 2023.
Mare Lelarge and Léo Miolane. Fundamental limits of symmetric low-rank matrix estimation. In Conference on Learning Theory, pages 1397-1301. PMLR, 2017.
Thibault Lesicur, Florent Krzakala, and Lenka Zdeborová. Constrained low-rank matrix estimation: Phase transitions, approximate message passing and applications. Journal of Statistical Mechanics: Theory and Experiment, 201 (0)000)37340,, 2017.
Gen Li, Wei Fan, and Yuting Wei. Approximate message passing from random initialization with applications synchronization. Proceedings of the National Academy of Sciences, 120(31): c2302930120, 2023.
12

---

Thibaud Maimbourg, Jorge Kurchan, and Francesco Zamponi. Solution of the dynamics of liquids in the bureedimenssinn limit. Physical review letters, 116(1):11990, 2016.
Gianluca Manzan and Daniele Tantari. The effect of priors on learning with restricted Boltzmann machines. arXiv preprint arXiv:2412.02623, 2024.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension free bounds and kernel limit. In Conference on learning theory, pages PMLR, 2019.
Roger G Melko, Giuseppe Carleo, Juan Carrasquilla, and J Ignacio Cirac. Restricted Boltzmann machines in quantum physics. Nature Physics, 15())8887-892, 2019.
Pierre Mergny, Justin Ko, Florent Krzakala, and Lenka Zdeborová. Fundamental limits of non-linear low-rank matrix estimation. arXiv preprint arXiv:2403.04234, 2024.
Marc Mézard. Mcan-field message-passing equations in the Hopfield model and its generalizations. Physical Review E. 95(2):22111,,
Francesca Mignacco and Pierfrancesco Urbani. The effective noise of stochastic gradient descent.
Journal of Statistical Mechanics: Theory and Experiment, 2022(8):083405, 2022.
Francesca Mignacco, Florent Krzakala, Pierfrancesco Urbani, and I Lenka Zdeborová. Dynamical mean-field theory for stochastic gradient descent Gaussian mixture classification. Advances in Neural Information Processing Systems, 33:9540-9553 2020.
Léo Miolane. Fundamental limits low-rank matrix estimation: the non-symmetric case. arXiv preprint 0rXiv:1702.00473: 2017.
Andrea Montanari and Emile Richard. statistical model for tensor pea. Advances in neural information processing systems, 27, 2014.
Andrea Montanari and Ramji Venkataramanan. Estimation of low-rank matrices via approximate message passing. The Annals of Statistics, 49(1), 2021.
Faruck Morcos, Andrea Pagnani, Bryan Lunt, Arianna Bertolino, Debora S Marks, Chris Sander, Riccardo Zecehina, José N Onuchic, Terence Hwa, and Martin Weigt. Direct-coupling analysis of residue coevolution captures native contacts across many protein families. Proceedings of the National Academy of Sciences, 108(49):E1293-EL E1301, 2011.
Anna Paola Muntoni, Andrea Pagnani, Martin Weigt, and Francesco Zamponi. adabmdca: adaptive Boltzmann machine learning for biological sequences. BMC bioinformatics, 22:1-19, 2021.
Jannes Nys, Zakari Denis, and Giuseppe Carleo. Real-time quantum dynamics of thermal states with neural thermofields. Physical Review B, 109(23):235122) 2024.
Parthe Pandit, Mojtaba Sahrace-Ardakee Sundeep Rangan, Philip Schniter, and Alyson K Fletcher. Inference with deep generative priors in high dimensions. IEEE Journal on Selected Areas in Information Theory, 1(1):336-347, 2020.
Farzad Pourkamali, Jean Barbier, and Nicolas Macris. Matrix inference in growing rank regimes. IEEE Transactions on Information Theory, 2024.
Felix Roy, Giulio Biroli, Guy Bunin, and Chiara Cammarota. Numerical implementatiinn of dynamical mean field theory for disordered systems: Application to the Lotka- Volterra model of ecosystems. Journal of Physics A: Mathematical and Theoretical, 48848))48 2019.
David Saad and Sara Solla. On-line learning in soft committee machines. Physical Review E,, 52 (4):4225, 1995.
Ruslan Salakhutdinoy and Geoffrey Hinton. Deep Boltzmann machines. In Artificial intelligence and statistics, pages 448-455. PMLR, 2009.
13

---

Ruslan Salakhutdinov, Andriy Mnih, and Geoffrey Hinton. Restricted Boltzmann machines for collaborative filtering. In Proceedings of the 24th international conference on Machine learning. pages 791-798, 2007.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-76)) 2018.
Robin Thériault, Francesco Tosello, and Daniele Tantari. Modelling structured data learning with restricted Boltzmann machines in the teacher-student setting. arXiv preprint arXiv:2410.16150, 2024.
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory, pages 1683-1709. PMLR, 2015.
Eric W Tramel, Marylou Gabrié, Andre Manoel, Francesco Caltagirone, and Florent Krzakala. Deterministic and generalized framework for unsupervised learning with restricted Boltzmann machines. Physical Review X, 8(4):041006, 2018.
Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborová, Brumo Loureiro, and Florent Krzakala. Fundamental limits of weak learnability in high-dimensional multi-index models. arXiv preprint arXiv:2405. 154800 2024.
Matteo Vilucchio, Yatin Dandi, Cedric Gerbelot, and Florent Krzakala. Asymptotics of non-convex generalized linear models in high-dimensions: A proof of the replica formula. arXiv preprint arXiv:2502.20003, 2025.
Yizhou Xu, Antoine Maillard, Lenka Zdeborová, and Florent Krzakala. Fundamental limits of matrix sensing: Exact asymptotics, universality, and applications. arXiv preprint (xXiv:2503.14220 2025.
Xinyi Zhong, Tianhao Wang, and Zhou Fan. Approximate message passing for orthogonally invariant ensembles: Multivariate non- con-liieasstie and spectral initialization. Information and Inference: Journal of the IMA, 13(3)iaae0024 2024.
A Additional literature review on the teacher-student setting
In many physics papers (Huang and Toyoizumi 2016 and Tantari 2024], the weights W are sampled from the posterior of the student RBM
Huang 2017
Thériault et al.) 2024 Manzan
S0 wh
P(W = 2(X) (r
(31)
where 3 represents the inverse temperature of the student RBM and 2(X) is the normalization factor. Their settings differ from the maximal likelihood training scheme used practice. When = 3 (see (14). it is the Bayesian estimation, equivalent to the Bayesian optimal performance presented in Section 5 For example, Thériault et al.
2024 points out that Bayes optimal students can learn teachers in one-to-one pattern for high SNR (3 3 large) but not for small SNR, which they call the permutation symmetry breaking phenomenon. This is consistent with our numerics in Appendix F.1 The paramanneti-too-erronnnettt transition in Manzan and Tantari 2024 also reproduces the
BBP transition.
While they also analyze the teacher-student RBM model with 3 * 8 need to emphasize + oo is not equivalent to maximizing the empirical likelihood p(=,,\W")) in this paper and in practice. Actually, by 31 + do maximizes the term in the exponent >"
1 x a consequence, Thériault et al. 20244, Manzan and Tantari (2024) predict that at zero temperature (3 + oo), the system is in the spin glass phase and it is statistically intractable to infer the planted signal (W"), while we show that the weak recovery threshold of the student RBM trained with
Wh h instead. As
likelihood maximization always matches the BBP transition (22)
14

---

B Simplification of RBMs log-likelihood
B.1 Proof of Theorem 1
Proof. For the following, we will prove a related result
lim V log L(W, 0,b) V Vw log L(W 0, b2b))l = 0,
(32)
d-000
which is useful to find the stationary points of log C(W.0,b) (e.g.,for Theorem 4h. The scaling appropriate because V w. www log ((,, 00,b)l @(vd).
According to
3 we have
log L(W, 00,b) = log IT μ=1 (PPh(hp)) ttta What to a 0+6 hp
(33)
Wht J O4b (t) "hh
n log
The first term is exactly 7/- We then take derivative of the log-likelihood. We can expand the derivative of the second term of 33 using
a Owa.
dP dP:ove da vch w.+ Ja 2a
(P:(
whhae vere un J2..
vd
( 1
/dPo(ts)
Usha
+ oo (hT, w. + +0
d3/2 (h" T w. + 0,)3) (0,+0
(34)
Vd
d ha T wi + 0i) + +0 +0( (= (h wi + 0;)²
d3/2
e w.+0)) T +0
(0) + ||w,
Owai
d3/2
For the second line we exchange the derivative and the integral because the integrand is over bounded domain (Assumption) D and continuously differentiable. For the third line we use the Taylor's expansion
Lu w.. =14 (w:h² wi + v,0,)/Vd+ O((vh" w. 2/0,)2/d)
and that o; is bounded according to Assumption For the fourth line we use f (w) 0 and f (P,)) = 1. For the last line we use the Taylor's expansion
1.TT.-0))77 + (hT w, 0,)3 O(h" w; 0,)*
and that bounded according to Assumption]
Thus we have
a (P)(()))Pooo) wh+ Lo
/
awat
(35)
i
dPh(h)et EL wh =0
Dwai
15

---

where we use the fact that Pe is factorizable (Assumption I Theorem Moreover, we have
and the boundedness assumption in
/ (PP((H)dPP(MDEEa Wh+ Www Jot
Z(W, 0.
{ dPh(hi)ccTO /
dP "2 wit0.)
/ /T_ faPi(M)cNT
1+ Va 1///20(/ " w: ws+ +,) + 0/ (h (TTT: w0 0.)2
1
2d
(110113 (W]33)
13/2
f (h) w. +h + o(1).
(36)
where for the last line, integrate over Us and + (h" w, 0,)2 vs e w.+t,))/22 The higher order terms can be bounded under the bounded assumptions (Assumption
(36) directly proves (4, because
notice that the first term of 33 remains the same, and the
second term is n log Z (W, 0, b), which is equal to n(1222 + o(1) by 36
136 also gives
W log / (w) Wh+ t Toth
Vwii (
W
W
W
0. 0
0
d
d
vo vi wi+ vr
a
1 w W. w o 0
d
7 Owat
Z(W.0,M
a,1=1
k,d
(u.)e u u wit 12
d (h) (n +0,
= d
Owai
aw..
Z(W b)
J Di (h w. +. + Tb
a
= o(1),
(37)
where we use (35 and 36). Similarly, we have
/ (P.(o))e to o wit n.0.
00;
ʃ (Pp(
1
1/ j (h w. + 03) o 63/2
(
1
(0 -1100,13))
(38)
Vd"
i + (t' w;+1;)²
1 d3/2
(0² 11wxi13))
a0;
where analogous obtain
34)
Taylor's expansions and integrate over v. Analogously
37
/ (P)(())dPP(D)eet TTh+ Wh+ o 0th B
lim d
Vo log
(39)
Von2 2 w W. - WTwTr 0, o0
0 =
We also have
Øb / (PP wht w o
(40)
ab. / ( +1))
16

---

and thus
/ (P)((h)dPo())eet Wh+ v2
lim d
Vo log
(41)
W 0 T 0 0)
w W.
=0.
We prove 32
by combining 37 (39 and
41
L
B.2
Visible units with nonzero mean
When P. has a nonzero mean e, 36) gives
/ dPi aa E o(h' " na Ex (h" +,, o(1).
z (W)
(42)
The gradients can be dealt with similarly to (34) and 35). which leads to the following corollary. Corollary 2. Under the conditions in Theorem but when P. has mean C, we have
lim Vdll w.o.va log L(W, 0, b) V w.o.vab log L(W 0,b)]l 0,
(43)
where
log L(W 0) = Σ
T
W.
0.b T
vn
1=1
n log / /aPh(t)) exx exp
h
hbb++
(h.
w; + 0,) + 2d
1 (h w Wh + 2h W 0 + 0 0)
Vd
i=1
(44)
In this case, we must have E wi E 0 =
(Vd). because otherwise the second term in
44
much larger than first term. We cannot directly apply Theorem 4 because under Theorem have Ei= Wt Ei= 0g θ (Va), and thus the va² Σi (h we 0,) term in (4
cannot
be overlooked. One option is to consider the constrained optimization problem
Σ
1
I
Vn x T..6)
1872 (2 W. w, 1 W 0, 0 0,
max E.
m
Ei
=0,6
d
#=1
(45)
which we leave the future work.
B.3 Gradients of the simplified log-likelihood
The gradient of the log-likelihood w.r.t the weights read
(P) e. J Wh+tTh
Vw log Ž(W, 0, =
#=1 Vd (h)a t2 ( Whtt67
(46)
I (h)(hh) W ho Jen b+ Qwh+2h Qwo+Qol/2 d b+(h Qw h+hh Qwot
where we denote Qw 1/ w W. WWQQw= == T. 0, Q, 100 0. This can be rewritten as
Vw log L( 0j =
hax D a(hh T ' W TT
(47)
where we denote
(f(h)) J (h) Whh
(48)
j'dP, (h))hh))) F0o Wh
17

---

and
(fhh)) H = [ (()) Qh/2
(49)
(dPa,hhee Qh/2
Note that the latter comes from a simple quadratic model with the interaction matrix Q(W) WT W instead of the original model
(d) h)e Ja Wh+ J2 uT
(f model
(50)
f ( (h)evv" Wh+ u4bb
which suggests that in high dimensions, only the pairwise interaction of hidden units matters.
Similarly, also have
Ve Colog((W,0,p) 0,
Σ (
==1
(51)
VB log L(W 0,,
Σ
(h) a(h)
All the gradients above take the form of contrastive divergence.
C Proofs in Section 5
C.1 Generalization of the data model
All results in Section 5 apply to the following data model
X F (J/U'A(W)) + +2) EF((Z E Raxd
(52)
under Assumption where F is general element wise non-liearity and {Zg) nnd sid noise.
lif==1 P. is the
Assumption 3.
(i) P2 has distribution pz with stretched exponential tail
(ii) F E C such that F E (Hzz) and sup [F < cc. Moreover, 01(F) # 0, where (1(F) FzF' (2) for Z Ps the information coefficient. We also assume that do (o(F2) - 2 = 1 i.e. the data are well normalized, where
= =
(iii) Pu, Pa are bounded.
Assumption Jensures that the data are generated from an effective linear spiked covariance model. It is mainly technical and might be relaxed. See Ass.msssuptiion (H2), (f3) in Guionnet et al. [2023 and Hypothesis 2.1 in Mergny et al. (2024).
More specifically, (52) asymptotically equivalent to because of the following lemma.
Lemma 1. Under Assumption
we have
2 vali U''(WW) + +E,
(53)
n
where Ž is matrix with iid, centered elements with unit variance and E is the error matrix which vanishes EE| = -1/21 almost surely.
Its proof follows from Guionnet et al. 2023 Lemma 5.1], which we present in the following.
Proof. We Taylor expand X around Z, which gives
vn X,J = (F(Z)) - EF(ZZ))) + Va
F(Zz))(uz)) Awj + n3/2 F/
F" (Gi)((()) Awz)), (54)
Li.. there exists a, such that for every M 0, 1. M) Ce cM
-cM
18

---

where Siz E iZg - Va (u;) Awzl. Ziz + 1
va ( Awžll. Therefore, we can define
2 = (F - BF(Z))
(55)
to be the effective noise and
E = va n -
Awz + n3/2 F (G;) (G))))))))
(56)
to be the error matrix. Note that we have E[2,]] = by Assumption ii. We can bound ||]] by
E
-
EF (2))
[iiag (x) (+) ( (+))la
(57)
n.d
(())) Awz)²
3/2
where Diag(u (nng(u" (10) E Ruxn Diag(w w (K3) E Baxd denote the diagonal matrices containing the k th column of U and W We use the fact that the L norm always smaller than the Frobenius norm.
(x)(()))))))) are bounded by Assumption 3 and that Vx (F Z) EF (Z) is a matrix having iid, centered elements with finite forth moments by Assumption It is well known that the largest singular value of such matrices almost surely converges (see e.g. Jiang (0044). The second term is -1/2) because each term in the sum is bounded by Assumption This finishes the proof.
The first term (n (2-12/2 because [Diag(u (())))
C.2 General AMP Iterations
In this section we present a general version of the Approximate Message Passing (AMP) algorithm Montanari and Venkataramanan 2021] (and a variant of the AMP in Zhong al. 2024 for spiked covariance models, defined as the iterations
Y = 1 XW Vn
Σ B.U E B D'=I((Y', f.(Y",''-1, ,.. Y E') E Baxk
(58)
Z' = X
U
CRW E Rack wit ge+1 Z Z'-1 .... FI, E Bdxk
Vn
where Onsager coefficients Bi, Cu E Rxc are given by
Of n dz (z)) 2/. E"), C141,1
1 8gtt1 n Σ
BuslE
By (1 8 1-1
4/ F*)
(59)
for i = 1,... I. E' F' are generic side information of finite dimensions. Its SE is given by sequence of k-dimensional random variables (Ü,, Y,, W., ZeJe21 defined follows
Ú, f(( L ........ Ê)
(60)
W +1 = gi+1 (Ze, Z.-1, F),
W
where
(Ý Y, = (M, M. + NN (O,,E.),
(61)
(Z 2,) (.. +
+0,,
and
M, = a E|W, WTT, Edl a E W s].
(62)
Ñ EiÜ ++ UJr, 12411y EU? ا,₁ where r yaAd (F) Rixk M and [EN]1 are given by initialization. We note that M., N. E B and Σ, Ω Rx The following theorem suggests that the iterations converge to the SE.
19

---

Theorem 6. Under Assumption 3 or for F(x) = and further assuming that
(i) the iterations are initialized with W Wo independent of X, having finite moments of all orders,
(ii) E", F are of finite dimensions and almost surely converge to É., "F'.
(iii) ft. are separable, continuously differentiable and uniformly Lipschitz at E' F w.r.t.
......),,, Y " iZ',z'' ...,, ...'...... ),
(Y', (Y","" ",,""-,...
then for any PL(2) function th the following holds almost surely for 2 0:
d
lim
(ww wj." .. ",, u. uz ... uu y ... ......... ,,,
d-
(63)
(W W1.". We U1,"" U .,. Y E,,... ,Z,)].
Theorem in the main text is special case of Theorem 6
Theorem 6 is very similar to [aan| 2022 Theorem 3.4] and [Zhong al. 2024 Theorem 2.3], and
the only difference to deal with the non-linearity and the side information, so we only provide its sketch.
By Lemmal we only need to show that 588 aymptotically equivalent to
Y = XWW
B, e Ra U' = f((Y', y .... Y E.EE
(64)
1 = x U²
U
......... C. w' e Rick w = 9141(Z'' (Z', z .... 21, 21, F) E Rdxt
where X = + U
because standard AMP results [Zhong et al, 2024 together
with the universality results (Chen and Lam 2021 give its SE in Theorem 6
In fact we can replace E', F' with E, F because of the almost sure convergence and the uniform Lipsehitz property. See Pandit al. (2200) for a similar argument. Moreover, as the error E has
vanishing norm, we can inductively show that J X in the iteration (58) can be replaced by X with Vn
O(n-1/2) error. See Mergny [2024] for similar argument. This finishes the proof of Theorem 6
C.3 Proof of Theorem
Proof. We first prove that B, and C₁ are always symmetric by induction. Suppose that Ct-1 is symmetric (which holds at t = 1). We define the following Moreau envelop
u Q' w + 1 1e' - CD -w)
mn)
F C.-1) min w
(65)
By the property of the Moreau envelop, we have
Then v.F(z', C.-))
+ C1-1f(z', Q C.-1)).
(66)
vzf(z', Q' Ct-1)) = viF('', Q', C.-1) symmetric, and thus B, is symmetric. Similarly we can show that C, is symmetric.
(67)
Now denote the fixed point values of U². W Y Z B C. Q' to be Ú W, Y, C, respectively. At the fixed point of AMP-RBM we have
1 Vn
Y
XW ÚB
(68)
x Ú WC
=
n
20

---

According to the definition of f and 9, we have
(C +C+Q11 Q) z = 0, a V B + yn)) + it2 = 0, / = 1,2, ,,
(69)
,
where we use the first-order conditions of (16), (17) and fact that and C' are symmetric. Taking the first equality of (68) into the second equality of (69), we have
a V'm W W//n) + ūn =0 Taking it into the second equality of (88, and using the first equality of (69). we have
(70)
Vm (2 W //////in 8/V =- -WC wQ.
(71)
Moreover, at the fixed point we have Q Vn²(Q((W)) by the last line of Algorithm 1 which thus gives (8)..
C.4 Proof of Theorem
Proof. By the triangle inequality, we have
(w w; - El f(M.W + 3. C1-1))l
d
1b( [w w))
Σ
(wwi i
(72)
d i=1
(w w)! (W (MM f(M.W >1/²,, Q. C.-1))]
d i=1
For the second term, Theorem
3
indicates that
lim
v (wt w
E ((W E. Q. C--i)) =0
(73)
d=+00
almost surely. For the first term, by the pseudo-Lipschitz property of t we have
(w) wi) ā Σ (ww, w
d
(1 + 2 |w + |w/|| + || [|) will
i=1
(74)
C
C
(1 + 2 / uz 1D/
will +
|w
w0
d 1=1
i=1
1 d
d |
C
d
cC
Σ [1 + 2||w,|1| + (|:
11
+
w
d
d
d
i=1
Taking d + oo and then t + co, by Assumption
we have
lim lim 1 d0
(ww w.) ā
1
Σ sw wx))
=0.
(75)
Therefore we have almost surely
lim lim t-+00 do
v (wo w.)
E(v(W, ((M.W + ", C.-1))]
=0. (76)
21

---

By EEmami et al. 2020 Lemma 1] we have
d
(w) w..) lim B, + E. Q C1-1))]
lim
(77)
almost surely and the limits on both sides exist.
Finally let us verify that the limit of M, exists. By Theorem B we have
lim Mr lim lim ( (w] E-000 5-00 d
lim 2.(w)) (wi (ww ()= d'+c0
(78)
almost surely, where for the first equality we use Theorem c and for the second equality we use Assumption to replace 2 with 2;. By similar arguments above we have
lim (wi 2.) lim B M.W G))
(79)
almost surely, which suggests that the limit on the right side of (78) exists, and thus lim4-xo M exists. In a similar way we can show that the limits of C₁2 Eg, Q, exist.
direct combination of (32 and Theorem 2 suggests that lim |Iv log (dW(l) = 0 at the stationary point. Then by (79) we finish the proof.
C.5 Proof of Corollary
Proof. We only need to iteratively prove that all matrices 19 are diagonal. Assuming that M. E,, Qu Ct-1 are diagonal, which holds at initialization, we first have
[f W V Q. C.-1) =
Q C.-)) = 0, (80)
for 1 < i i j S h and thus M, is a diagonal matrix, where [[[,) 0 because Pa. is symmetric.
Moreover, we have
2 = a BB G, δ. C. C..)) E 12 Q. C.- 0, (81)
1 isi k. so E and Q are diagonal, where (M, W₁ + v E Q. C,-1)] = 0 because Pa. is symmetric and f(, Q C.-1) is an odd function. As f(: Q C.-1) is separable, B, is diagonal.
When PA is separable and symmetric, 7h is an odd function, and thus g(,, B,) is an odd function. Sim- ilarly, M E, C, are diagonal. Finally, as Q, is diagonal and Ps. is separable and symmetric, Vr (T)) is diagonal, so Q, is diagonal, which finishes the proof.
C.6 Proof of Theorem
We now provide detailed definition of the functions Je.9.41 91+1 TR R2* follows. We define
[-1
7 - Σ BrÜ
(82)
Re+1(2e, 2. = C₁ W., W. Q.).
1=1
where Ü, should be regarded function of Y, i, Y i-1, y, as defined in (26). and similarly
for W. :. f.g are separable functions defined by f(y) = Vn(y) I2* and g(z, w, Q) io + x(= aQi E & for y, z, i R Here Q, = E(Vr((((W.)) E R and Onsager coefficients Ba, Cu E kgi are given by
Bi-1 =a E[0,g.+1 (Z., (Z,, ........ ZD), C₁ Bj. Y Y...... YY), (83)
22

---

for i = 1, it, where 0.fi : R - B denotes the partial derivative of ft w.r.t. Y, and 0.t++ Bixt Bixk denotes the partial derivative of De+1 w.r.t Z;. The derivatives can be calculated recursively
O.fi(Y , .Y)= Vf(Y" Σ
BiaUp (ou + Σ Bija, K.)). (84)
t-1
0,g
11) - 6n 22 +
=
Wa,
1-1
i-1
Σ
Cijör((Zz
Σ
Cra W. (2), 21) (85)
+
-=it1
02g(Z'
+ Cia W. as W w.)og' (2,-1, 11).
where Vf: _ + R**k denotes the derivative of f. and 01g, 02g lgkx2 k denotes the derivatives 9 w.r.. its first and second variable.
We can notice that (25) can be rewritten as
y 1 XW's BRak Ú' D'=j(Y') E Rnnk Q² Vnz(Q((W))) BAx Vn
(86)
z' X E TRan W = =0' w' Q') E Rd
1
Then suffices to map 86) to a general AMP iteration as follows
XW
Σ BaÜ 0' -'=
8)) Q (n2(Q(WW))
Vn
(87)
x
Σ
C w W 9 1 Z 1-1
Z1),
which is a special case of 588
Therefore, the first part of Theorem 5
simply follows from Theorem omit its proof.
6 The second part of Theorem
5 the same as Theorem
D From stationary points to global optimum
In this section, we will generalize the results of Vilucchio et al. 2025 to the spiked covariance model with non-separable constraints. We will show that for a special case, the global optimum among the stationary points we describe in Theorem 4 The idea is that Theorem provides an upper bound of the minimum, and we can find matching lower bound by Gordon's 's Gaussian comparison inequality [Gordon 1988). Specifically, we will consider the data model with one spike and Gaussian noise, i.e.,
X
u (w))T + Z E Raxd vd
(88)
where {ut ~ Pa. fwt pd optimization problem
~ P... and
~ N'O, 1). We will consider the following
Ad inf L(w) weRd
||
(89)
Σ m (v22T
inf weRd
722
Wis
as special case of 15
with k = We change some scalings for notational convenience. Although
15 only requires = 2, we find that it is more convenient to state the general result for any 0.
23

---

Remark 1. It is easy to modify our results to include the biases of RBMs. However. the restrictions == and Gaussian Z cannot be easily generalized as they are required by the Gordon's Gaussian comparison inequality (Lemma We expect that this is a purely technical problem and can be resolved the futre.
Our first assumption concerning 89 is the following.
almost surely for some Assumption 4. The global minimum w of (89) satisfies |||/|1 à ||
b > O.
Assumption Jactually requires that ?n grows much slower than 7/2. We can justify it by the following example.
Example. We can consider an RBM with Bernoulli hidden units. In this case, we have m) (z)
1 log cosh( /ax) and 72(w) = w² As 1h (x) grows almost linearly for large for any > 0, we have
1
1 d'
1 Vn
1 2-7cOmaa + A) 2)122
Vn x. w
Xw
(90)
for 2/w|1 12
M and some M > O, where Amoz represents the largest eigenvalue of 1 Z. By the standard concentration results for Wishart matrices (see e.g., et al. 2023 Proposition A.1 we have Amax < M' almost surely for some M' > 0 and all d. Therefore, we almost surely have
((w) 2 7 <M') >0
(91)
for 1 /1|0|1 > M by choosing < 1. M As [()) = 0, Assumption
4 holds for b == M.
Our main result, Theorem 7 provides an exact description of the global minimum of 89 doing so, we need to introduce some notation. We first define the potential function
Before
((,....P.,,KPP....)) = RT + aEMM =m (AmU* + +GG)= + EE,, ((al-p)+d()))
(vw + +kH)
2
1 (v²
(v²p+ + vm x9 op,
2x
(92)
where the expectation is w.r.t. independent random variables G, NO 1), P., W Pa and we define p == E[(. We also use the following notation to represent the Moreau envelope
Ma)(#) inf yEB
f(v)
2T (v x²)
(93)
for some function f and scalar т. We define the corresponding minimizer as
(z)(2)= E arg inf yER
f(y) + (v - xx)²
1
(94)
27
Finally, we define the set
S = (m, a. P. R, 2.t. = sup inf ((..G, k.w.P.P.S
(95)
There are two additional assumptions.
Assumption 5. Pu, Pa are sub-Gaussia Gaussiansnnn is (T)(2). 1)2 is PI(2) w.r.t its first variable and continuous w.r.t. its second variable. Moreover, there exists (m, q. p. R,,,D, &, Φ) E S such that we can choose (as the minimizer might not be unique) Pam and P (0)(-))(())) be Lipsehitz continuous, uniformly at (p, f, R))
Assumption (Replicon Stability). Under Assumption (m, 4, R. U, 2) also satisfies
- where the expectation is w.r.t. W Pw, U Pu and G. ~ 11,,
aE P' (2wr
R E
H
27
(P's
( (AMUU* +GG -1) 27
< 1, (96)
8
24

---

Note that under Assumption 5 the derivatives of the proximal operators are well-defined almost everywhere. While Assumption [ is mainly technical, Assumption is essential and related to the inherent difficulty of the optimization problem, which needs to be verified numerically. See discussions in Vilucchio et al. 2025]. Now we present our main results in this section, which give sharp asymptotics for the global minimum of (89)
Theorem 7. Under Assumptions t0
(i) We almost surely have
lim = d00
sup inf E(m, P.
(97)
(ii) For any (2) function 1/,
(s)
sup inf (mm. p.x..P.aS..mm
(98)
( (uw + kH) )
+sR W
is differentiable at s 0, then we almost surely have
lim Σ + (w,, wi) d
(s) ==0
(99)
ds
where is the global minimum of (89 and the expectation w.t.t W Pw and H ~ NO, 1).
Note that the second part implies that E is regular enough such that we can interchange the derivative and the sup inf, we should have
Σ se (w) wy) = Esp W", "V",Pt (f(0w++
lim d
(100)
which is reminiscent of Theorem
As in Vilucchio et al., 2025 Section D.IJ, Theorem 7 results from combination of the following two lemmas for lower and upper bounds. The lower bound is obtained via Gordon's Gaussian comparison inequality, and the upper bound is obtained via a variant of Algorithm
Lemma 2. Under Assumptions
4 and for any & 0,
Plim inf Aa 2 A E] =1 d
(101)
Lemma 3. Under Assumptions to there exists an algorithm that outputs w', which converges uniformly (as in Assumption 2). satisfying
bb (w w)) Eeb ( Jy",Pag Pt ((OWW+HHH))
+ +HH))
lim lim d0000
(102)
for any PL(2) function vb and
lim lim L(w0) = A. 1-000 d-o0c
(103)
D.1
Lower bound: proof of Lemma
We first lower bound the objective via Gordon's Gaussian comparison inequality.
Lemma 4 (Gordon's 'ss Gaussian comparison inequality [Gordon 1988). Lei Z E Boxd have iid standard Gaussian elements, g E R" h Rd also have iid standard Gaussian elements. For compact sets Sg n Sw [dd and any continuous function i S, x Sw. define
C(Z) min max u Zw + 16( (( u)
(104)
uES
25

---

and
h( = min max || Tu ||u/|2h T w + (bw, u). wESw WES,
(105)
Then for any c E R, we have
PIC(Z) S d S 2l( h) sc.
(106)
Now we can reformulate the optimization problem towards (104) by introducing Lagrange multipliers
w.r.t.
va Xu and p:
wil
We have
w
Aa: = inf 7 7
Σ
72
Wii
i=1
1
1
inf sup w.HhP f.o
d
vdl
Zw
+
(w ) w - -y
(107)
n
d Σ 122 (wi,p) ① (0)
1
| 1
Σ
m (y/)
d
Now apply Lemma to obtain P[A. S S 21 I cl (we will argue below that under Assumption 4 everythhng is almost surely bounded, so we can consider optimization over compact sets), where
A (u (1w0||g T f-1lf( w) 5 +
Aa: inf sup p.u.yy o.f Vd3
(108)
1
n2 (w;, p) (p--lluy ||/|11 =10l111F))
nh (Va)
d
d
As the objective is linear in f. we can keep = ||flI/ Vd fixed and optimize over the direction of f. which gives
1
X u" ['(w"") Tw 2 g
Aa inf sup p.y.
xh w +
Vd K
y
6.x d
Vd
(109)
|w|l
m (Bn) +
m22 (wi, p) -
d
We further introduce Lagrange multipliers w.r.t. := (w=") and y= Ja ||x||| objective, which gives
to simplify the
Aa : inf sup
xh w
1
||Amu + + - -/1
Σ
m (m +
Σ
(na(w,,
m.g.U. u.B.R.
Vd"
d i=1
p=1
+ xww)) - op +
m / (w0))
)Tao")uul
u
x
1²2
w
w
2
(110)
26

---

Then we interchange sup and inf to obtain a lower bound and use the inequality
|||||
> min, 2 -
I|
which gives
27
Aa 2 sup
inf
KT
||mm" +9g --g-yl uyl1
1
n
m (B))) + vm
2 =x0²²
M. d y y, m.p... M.P
2
2rd
+
w v(w") www -kh
+
1
Σ
(na(ws, p) + (ww)) -op
d
i=1
KT
1 n
(Hive) nhts))
sup
inf 7.p.q.pp
+
Mr Mn (Amu + +q9u)
M (m(00()))00))
2
d p=1
1 vm
V|w + kh|
2 24 op.
2dx
(111)
where we use the definition of the Moreau envelope. We denote the right side as x inf Em P.P. T, X: Φ), and thus Ea(m, E (m,, 4, P3 T, K, x) 6) almost surely, which follows from the law of large numbers because the Moreau envelopes are pseudo- Deesch-ippchitz of the same order as 7h and 1/2 [Vilucchio al. 2025 Lemma 5].
T, K, の)
going to show that the sequence of minimizers of {Ea) is almost surely bounded in order to interchange sup inf and the limit. By Assumption 4 we have that p, < b almost surely bounded. By the Cauchy-Schwarz inequality, S [g + p) is almost surely bounded. By the arguments after Assumption 4 we have that àlly/l? almost surely bounded. By (I07). we have that f Epm1 v/i (y,), and thus f11ff1 I J - Tn (1 + (y almost surely bounded, where Ly, is the pseudo-Lipschite constant of 171 Thus x almost surely bounded.
Now
Next, because
1 (uw + xhhi) S (2((0,4) 4) + x
1 1 + kh
M ml):)))
(112)
d
2dx
1=1
Ea goes to -00 for m = T U. + oc, uniformly in d, so x. v and & are almost surely bounded. Finally, as
lim Σ au + (9,) = inf 1
y ā Σ (vw) 2 inf y
Σ Ia (1+ (1+.w)llbx++mmdd (113)
is almost surely bounded (as ||/y/l (2 is almost surely bounded), have that is almost surely bounded. Thus we can assume that we optimize over (m, K, E S, where is compact set.
Moreover, by the exponential concentration of sub- Gaussian variables u", w and Gaussian variables g. h. we have that 111 11,="|13 1 || 11 is almost surely bounded by the Borel- Cantelli Lemma. Therefore, by the pseudo-
property of the Moreau envolopes, we have that Em q. T, K, v4 X. σ) is almost surely equicontinuous in Š (according to the Arzela-Ascoli theorem), and thus it converges to {mm, 9. P. X) almost surely uniformly in S, which gives lim sup inf Ed(m, q.P, T, U, X, )) sup inf E(m, T,K, K. X. Φ) d- P.x.N. p.m...55.mm00 F.m.0.
(114)
m.x.n. T.m.p.p
surely. supuxx...
almost
We finish the proof of Lemma m...p Em q. P. T, K, X, Φ) and Lemma
2
by
using As
N
D.2 Upper bound: proof of Lemma
We will show that the following variant of Algorithm I Can give the upper bound.
y' Xw' b,u0-1 R², u' fx R",
vn
(115)
Vn = x "n. - -20011 E RRd w = g²())) E Rd
27

---

with Onsager coefficients given by
1 a "Eo)()
b n
EPY))) C+1
(116)
n μ=1
and denoisers given by
(()): Vak 88
(P m (I) x), (x) vaP ( (0)())))
(117)
It is essentially Algorithm 1 at the fixed point. Lemma 3 thus follows from the following lemma.
Lemma 5. we run (115) with initialization w ( w
& h) and by = 0. where h is an iid
X
standard Gaussian vector, then w' /a satisfies Lemma
Proof. By Theorem
we can write the SE of (115) as
(Y,,- ; Yt) = (M M. ,M) +N(00, E.),
(Z,, Z,) =
+N((0,
(118)
U. = (Yi), W. = (Z,
where
Mj = Va- w [Ed, = -
(119)
N₂ = VaXEiU,U"), [2l = E(U,U,)
Equivalently we write it as
M. AE WN--1 + / 1 H)
Va
(120)
EgJu a (N- ( H))
N; = VOXEL + UU*) [i]et = B[( + v (Er)
By comparing with the stationary points of (92
- ( (ow + RH) )}
02 m = E
W ((a(-)))00))
0x: ② = E
P
(DW* + RH)
(121)
R
U (P im (AmiU** + (G) > - q
Om Xa EE
x2
(P Oxiut" + &G) - Amn QG)) 21
0,
R² =
42
and the definition of f",g", we have
1 Mr Am, Erlu g2, N:
2²
(122)
x"
X
for any / 2 1. Other three stationary point equations of 92 will be useful later
(ow + ((w-++++1) =
0 : + == HP HP (12((-)))+0)))
0,: X4 a a G (P (mmt* +QC) - xmU - -GG)
(123)
(Pront
(F + Rl)) )
0, : p = E
28

---

To obtain these stationary point equations, we use the identities
OMrs(a) -- P=)((² Oz
aMr((z) (2-Prs(=))* (M(rs+og)(z) ((P ((S+gg) (=))
27
(124)
and interchange the derivative and expectation under Assumption 5 With slight abuse of notation, &
we denote M == M2 Xmn N == N₂ x¹ Σ == E.lu = q² and ? == [Rce
We further
x
denote
lim 1 y1- = 2( -C,), lim 1 J 2 = 2( Ct). d000 7
(125)
d=00
Then by (18)) we have
C E
= Blg (NW* + VOL1 + VI -(- (NW + / + / - Cr-
C. = -[2ele,c11 = EMF" + VC,22 -R-CZZ) + VCiz + V G(22),
(126)
where Z1. 1 Z Zz. Z,2 Zy are iid standard Gaussian variable. By the same argument as [Vilucchio ct al. 2025 Lemma 33, we have
dc, C. S a ((NW" + VEZ,) oc, & B((f")(MU)) + 9l
(127)
Therefore, under Assumption the iteration 126
globally converges to its fixed point, i.e.,
oom C. = E, lilmmm,. C = S2 which gives
lim lim - |gy/ 3y 112 O, lim lim to0 d+o
_ 21 112a-2"" 2' 112 =0
(128)
t+000 d n
Now we are going to prove that lime-+00 lo ((w²) A almost surely. The objective reads
d
| ar/2d
m
(1/2 + b
+
n22
(129)
#=1
By the law of large numbers and the pseudo- property of m/ T22 we have
d
w
1|
1 (Ta00
( + -1
1
- + R =1111) - =)))))
[2w-
lim do
112
Va
ar/2d
= Em
x
1=1
= Erp (P
(o w + H .0)
(130)
and
lim b. 1 EE( + +G)]
1 78
E G (AmU* +
(131)
Va
almost surely, where we use the Stein's 's lemma and
113 Thus
lim I Σ m (v%, bee()) oF (A +G d0000
1 Tn f*mmUU++ +
Va k
(132)
a (P +ANU++GG))
By the pseudo-Lipschire property of m/, have
Im (1/s beut m (1/ + beu()))
7
(133)
1
Lm (1+ + 2/1//1 16 + 1b ((bell - + 0
d
1=1
29

---

for d + 0o and then t do by 128 Therefore, we have
w²
alnm (P (n (mU**+ (P (PrraC-A)HOO) (= + +R(f) .D)
lim lim L
1-000 d0000
Vo
(134)
The optimum of (92 reads
At
aBmm (P Em (nU + +Q)) + +a & (Ptn (nt + QG) (fU + QG))2
A
(m
+ Enp2
P+ (+(m2(-))+00))
(oW*+RRl
.4]
+
X
P (2((((i)+
1 x (DW +RH
(DW 10W=+Ril +RHI)
(0 (12p x+) )+ im
2 2X9.
1
2
2x
(135)
where we use the identity
(z)((() f(Prs() + (P (P)(()(x) xx)
(136)
2r
By using 121 and
123
obtain
+ (iH1) .0)
A= aEn (P mm (MU (G)) + Enz
P (4om(-))+00
(137)
We finish the proof by combining it with 134
E Experiments on Fashion MNIST
We verify Theorem 1 on Fashion MNIST in Figure We choose Bernoulli hidden units and Rademacher visible units with trainable biases to satisfy Assumption We choose to use hidden units to exactly compute (7). For GD-equiv (GD over the simplified loss (5), we obtain the weights of RBMs by using the Adam optimizer to maximize (5). To train RBMs with contrastive divergence
(CD), we follow the standard implementation Hinton 2012 Specifically, we update the weights through
wit = wht + va x ((agha) (x.ha)H),
(138)
where is is the learning rate,
(w.he) D = nt
1
Σ ppalipa
(139)
1
and (Dgha) и is obtained through cycle MCMC starting from the data. For both GD-equiv and CD. choose batchsize 50 and run for 20 epochs the training set. The learning rate is chosen 0.1 Vd. The initial weights are Gaussian. We present the reconstruction performance of 10 images randomly chosen from the test set, where we occlude half of the images or add random salt-and-pepper noise.
We compare how RBMs with weights obtained by GD-equiv and CD reconstruct half-occluded images and noisy images in Figure Specifically, the RBM first samples the hidden units based on the occluded or noisy image and then samples the visible units to generate the reconstructed image. To better reconstruct occluded images, RBM takes the reconstructed image to replace the occluded part and iterates several times. Figure 3 suggests that RBMs trained with GD on the equivalent objective (5) can reconstruct the original images well standard RBMs. The small difference in the quality of the reconstruction should be attributed to the approximation error.
Experiments on synthetic data
F1 Comparison between different algorithms
For the experiments on the spiked covariance model in Section 5 we set d = 4000, n 8000 and report the results and standard errors averaged over 10 runs. We choose P, and P., to be per, where
30

---

GD-equiv CD original
GD-equiv CD original
Figure 3: Reconstruction of occluded (Upper) and noisy (Lower) Fashion MNIST figures by RBMs trained with CD and GD. The RBMs have 10 hidden units.
P(x) = (6(z + 1) + 8(x - 1) is the Rademacher distribution. In this case, we have
(x) log cosh( / /az),
(140)
and g(v', B,) is given by the solution of
(Bng
+ + + 0.
(141)
Va
We measure the overlap Stz :=
[0, 1] between the j-th signal w E Rd and the weight
we
vector wi Rdd of each unit for standard RBMs. We also measure the Bayes optimal overlap [Lesieur cet al. 2017), and the overlap obtained by AMP-RBM (Algorithm I]. GD (25). For both AMP-RBM and GD, 7 is calculated exactly by averaging all 20 possibilities. The overlap can be predicted by the state evolution via
E W + E. D...Q.C.... Cx)),W,))
Ei B W + E./2 Q C. 11)
(142)
In this section, we also compare our algorithms with RBMs trained by CD, where both the hidden and visible units chosen be Rademacher units without biases. The iteration is provided in Figure which qualitatively similar to that of GD in Figure]] T but CD) converges much slower. In this section we consider the degenerate case Ad better compare different algorithms, because it is generally harder and SVD cannot distinguish signals in the degenerate subspace.
For the iteration curves in the left side of Figure I and Figure 4 we use the informed initialization to better demonstrate the state evolution. For other figures, we only consider the random initialization (i...,M, 0) for more realistic comparison, and we will use the Adam optimizer optimize (5) to obtain better convergence.
The comparison between standard RBMs (trained with CD) and other methods for k >>>>> is given case, where the y axis corresponds to the average overlap Ç : 1 {(max[[[1, (21) max((12, {22)). In this case, the SVD can only
in F The left panel of Figure considers consieess the r
31

---

0.4
overlap
61
0.2
{2
22
22
0.0
10
20
30
40
iteration
Figure Iteration
The setting the same as Figure]
1.0
1.0
0.8
0.8
overlap
0.6
overlap
0.6
Bayes optimal SVD
Bayes optimal
0.4
0.4
SVD
AMP-RBM
AMP-RBM
GD
0.2
GD
RBM
RBM
0.0
0.0
0.75
1.00
1.25
1.50
1.75
2.00
0.75
1.00
1.25
1.50
1.75
2.00
SNR
SNR
Figure 5: Comparision between standard RBMs (trained with CD) and other methods rork=== (Left). k- 10 (Right), Rademacher prior. The red line represents the overlap of the Bayes optimal estimation. The purple lines represent the asymptotics of stationary points (Theorem 4 The yellow lines represent the asymptotics of the fixed points of DMFT (Theorem which overlap with the purple lines. Note that the red,
yellow and purple lines are all for rank-1. The green lines represent the asymptotics of SVD. Dashed blue lines represent the BBP threshold.
find the two-dimensional subspace but not the signal. The results of SVD converge to a uniform distribution over the subspace [Montanari and Venkataramanan 2021], which gives the green curve Ç = max 2v 1-a/A4 0). The right panel of Figure considers the A: = 10 case, and the green T
line is obtained by numerically averaging over ten-dimensional Haar distribution. AMP-RBM might fail converge for k 10 due to numerical difficulties solving (17). and we filter these failed iterations with negative objective values. The red, purple, and yellow curves are asymptotic rank-1 I predictions. As noted after Corollary [[] we can assume the overlap matrix to diagonal to find the convergent point, the rank-1 asymptotics actually locate one of the possible saddle points, though other saddle points may also exist.
In Figure 55 AMP-RBM and GD show significant advantages over SVD especially for rank- 10, because SVD cannot distinguish the signals. AMP-RBM and GD perform similarly to the rank- case, as predicted by Corollary [ The right side of Figure 3 considers the r k 10 case, where gap between SVD and Bayes optimality larger, while the performances of AMP-RBM and GD are similar for large SNRs. For small SNRs, however, there is larger gap between rank-r AMP-REM/GD and rank-1 AMP-REM/GD around À when r gets larger, suggesting that the landscape becomes
complex, and GD converges stationary points different than the one specified by Corollary [ The gap between AMP-RBM//H and RBM also gets larger for small noise and large rank, possibly due to the eтror in Monte Carlo sampling.
Finally, we note that the Bayes optimal overlap in terms the rank-1 case, and thus there is larger gap between the Bayes optimal overlap and other algorithms for r = k 10. In fact this gap also exists for various kinds of AMP algorithms [Lesieur et al.) 2017 Montanari and Venkataramanan
2021 Pourkamali et al.] 2024 We present the performances of different AMP algorithms in Figure 6 analogously to Figure 5 AMP denotes the algorithm Lesieur et al.) [017] and decimation AMP
denotes the algorithm in Pourkamali et al. [2024), which is conjectured to be optimal in terms of
32

---

1.0
1.00
0.8
0.75
overlap
Bayes optimal AMP (random init.)
overlap
0.6
Bayes optimal
0.50
0.4
(random init.)
AMP (spectral init.)
AMP (spectral init.)
0.2
SVD
decimation
decimation
0.00
0.0
0.75
1.00
1.25
1.50
1.75
2.00
0.75
1.00
1.25
1.50
1.75 2.00
SNR
SNR
Figure 6: The performance of AMP and decimation AMP. Left: 7 = k
Right: r = 10.
1.0
Bayes optimal
AMP SE
0.8
SVD
0.8
SVD
GD
GD
overlap
0.6
AMP-RBM
overlap
0.6
AMP-RBM
0.4
RBM
0.4
REM
0.2
0.2
0.0
0.6
0.8
1.0
1.2
1.4
0.75
1.00
1.25
1.50
1.75
2.00
SNR
SNR
Figure 7: Comparision between the standard RBM (trained by CD) and other methods for r 1. Left: Rademacher hidden units and Aemoulli-Gaussian weights. Right: Bemoulli- Hemoulli-Rademachee hidden units and Gaussian weights. The lines represent the same thing as those in Figure
estimating U ("W"" (rather than estimaing W*). Besides random initialization, also try to initialize AMP with leading singular vectors (spectral initialization). We note that the Bayes optimal AMP algorithm in Montanari and Venkataramanan [202T] cannot be extended the degenerate Figure 6 suggests that the performance AMP (with random initialization) has high variance, because might fail to recover all signals together. On average, its performance is similar SVD.
Moreover, AMP with spectral initialization and the decimation AMP [Pourkamali et al. 2024 can reach the rank-1 Bayes optimal overlap for large SNRs but not for small SNRs, similar Figure I which suggests that it might be fundamentally difficult to distinguish different signals for small SNR. similar phenomenon is found previous physics-based analysis of RBMs (Hou et al.) 2019 Thériault et al.) 2024). where it is called permutation symmetric breaking. This suggests that we are able to perfectly distinguish different signals only for high SNRs.
In Figure 7 we present some experiments with sparse priors. For both cases, the sparsity is 0.9. Figure suggests that GD and AMP-RBM still converge well to its SE, but RBM does not.
F.2 Learning dynamics of RBMs
We first consider the case where different signals have different SNRs. The results of et al. 2023 suggest that from random initialization. AMP weakly recovers signal of SNR À at time O logd (for a sufficiently small). Therefore, we can expect that RBMs recover these signals sequentially. which leads series of emergence phenomenon, as demonstrated on the left side of Figure g Note that this reproduces the results in Bachtis et al. [202],, which is called a "cascade of phase transitions".. we further assume that the r-th signal has an SNR X, X-r, we expect that the iteration = X" log d, signals are recovered sufficiently and other signals are not weakly recovered.
This gives a power-law scaling
log d
L:=
Σ k=
X
x
(143)
2-1
33

---

1.6
6:
0.8
1.205
0.0
RSM croor
0.0
0.5
0.2
3.205
0.0
0.0
0.0 100
100
Figure 8: Left: RBMs (trained by CD) Iearn three signals sequentially, leading to a stairwise loss (A 2, 2.5, 3, 2). The solid red line denotes the effective loss Σ A, miny |ne, w 11 and dashed red lines denote the effective loss min; |m w || for cach signal, where we normalize them to [0, 1] for better visualization. The blue line denotes the error of RBMs (trained with CD), which does not go zero because
considering model with strong noise. Middle and Right: overlap between weights and signals, and overlap between (overparaneterization) and The weights of RBM align well
weights, an RBM with r with the signals, and remain orthogonal to each other.
where the effective loss T. evaluates the total strength of the unrecovered signals.
The case where some signals share the same SNR is more challenging, as the naive SVD cannot distinguish these signals. In Figures 5 and g we test the performance of RBMs in this setting, where we find that the stationary points indicated by Corollary I are dominant for random initialization when the SNR is large enough. To the dynamics, by CD) under the random initialization in the middle and right part Figure 8 for 2, = 3, which shows that RBMs could learn all components of the signal effectively. Moreover, during iteration, different hidden units gradually get aligned with the signal and disaligned with each other.
plot the iteration curve of standard RBMs (trained
To understand this effect and understand how the alignment changes during iteration, we can observe that w T Qu in (16) works effective regularization term that makes the weights of different hidden units more disaligned with each other. In fact, suppose that Pa separable and symmetric, we have
(Q2 J dh, (h.)) Quh (ut.
(144)
which is positive when Qig > and negative when Qij < O. Therefore, the regularization term w Qu in (16) makes the overlap between w, and wy smaller when the overlap is positive, and makes the overlap larger when negative, and thus makes w, and w, more disaligned. On the other hand, the alignment effect comes from the m (h) term, which encourages the hidden units to align with the signals.
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: Our main contribution and scope to connect RBMs with multi-index models (Section B), spiked covariance model (Section 4 and give nigh-dimensional asymptotics (Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes].
Justification: For example, we explicitly suggest that the global optimum holds only for rank-1 case, and we only conjecture it to be true in general. Moreover, we explicitly discuss after Corollary that algorithms might not able to find the stationary points it specifies.
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 or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 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 fairesss.
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 acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play 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
35

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theorems are clearly stated with full assumptions, and the proofs are given
in Appendix C
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 in 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 provide short proof sketch to 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 of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer:[Yee
Justification:
We implement the algorithm exactly according to the description in Algorithm and provide full details about the experiments in Appendix B
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 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a 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) If the contribution is primarily new algorithm, the paper should make it 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) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
36

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We include our codes in the supplementary material, and will release them upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for 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
Codeeuomi ssinnoolicyy 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.
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 omitted from the script and why.
At submission time, 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer:
[Yes]
Justification:
We disclose all hyperparameters of experiments.
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, or 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:
We average the results over 10 runs and provide the errorbars.
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, or 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, or overall with given experimental conditions).
37

---

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 one 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 not to show in tables figures symmetric error bars that would yield results that are out of range (ega.,negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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 reproduce the experiments?
Question:
Answer: [Yes]
Justification: Personal computers are sufficient for all our experiments.
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 compute 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 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
We closely follows the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in 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: There is no socictal impact of the work performed.
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.
38

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 out 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses 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 not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [Yes]
Justification: We only use the popular Fashion MNIST dataset.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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 use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
39

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is 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. Crowdsoureing and research with human subjects
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 details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 the main paper.
According the NeurIPS Code of Ethics, 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
Question:
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
40

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Our paper does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
41


Reviews:
[{"review_id": "zGU4asfswB", "reviewer": "Reviewer_MNio", "summary": "This work studies RBM in the limit where the input space has large dimensionality while the number of hidden units remains fixed. The authors connect RBM training objective to a form equivalent to a multi-index model with non-separable regularization. This reduction enables them to use established analytical tools from the study of multi-index models—such as Approximate Message Passing (AMP) and its state evolution, as well as the analysis of Gradient Descent (GD) via dynamical mean-field theory—to investigate RBM training dynamics. They derive rigorous asymptotic results for RBM training on data generated by the spiked covariance model, which serves as a prototypical example of structure amenable to unsupervised learning. In particular, they show that the RBM achieves the optimal computational weak recovery threshold, corresponding to the BBP transition in the spiked model.", "questions": "If possible, it would be interesting to provide more results on the GD part: (i) can the authors provide at least heuristic arguments for the the weak recovery threshold of GD backing up the empirical results of Fig (1) ? (ii) can the authors provide an analysis of the GD dynamics  ? \n\nIn \"related works\" the discussion of Bachtis et al, and Harsch et al should be improved. These works provided a heuristic analysis of the GD dynamics as a function of training time - the sentence \"Their analysis is non-rigorous, whereas our results provide exact asymptotics, including the characterization of saddle points\" seems to imply that this work contains a more complete analysis of GD dynamics, which is not the case.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: Establishing the connection with multi-index model, and applying AMP to study RBM in the asymptotic limit of large dimensionality, obtaining asymptotic results for data generate by spiked covariance model.\n\nWeaknesses: the part of the analysis of GD is weak. The asymptotic DMFT eqs are derived and proven but no analysis, even a heuristic one, is provided. The work of Bachtis et al, and Harsch et al provide such analysis in a non-rigorous setting.", "was_revised": true, "final_justification": "I stand by my initial review + the authors replied satisfactorily. I give a 5 and not a 6 because although interesting, it is not at a ground-breaking level.", "rebuttal": "Thank you for the detailed and constructive feedback. We address the raised concerns as follows:\n\n* *Can the authors provide at least heuristic arguments for the the weak recovery threshold of GD backing up the empirical results of Fig (1)*\n\nYes, we note in L320 that a linearization of GD dynamics can be carried out analogously to the linearization of AMP-RBM. This yields an effective update rule equivalent to the power method, suggesting that the weak recovery threshold remains unchanged. We will clarify this point in the main text by including this heuristic argument.\n\n* *Can the authors provide an analysis of the GD dynamics ?*\n\nRegarding the GD dynamics, except the weak recovery threshold, we also provide a preliminary analysis in Appendix F.2, where we recover the sequence of emergence phenomena observed in Bachtis et al. Additionally, we offer an intuitive explanation in the same appendix for why the learned weights become disaligned during training. This aligns qualitatively with the repulsion effect between place/receptive fields observed in Harsch et al. A more detailed and quantitative analysis of the GD dynamics remains an important direction for future work, and we will explicitly mention this in the revised manuscript.\n\n* *In \"related works\" the discussion of Bachtis et al, and Harsch et al should be improved. These works provided a heuristic analysis of the GD dynamics as a function of training time - the sentence \"Their analysis is non-rigorous, whereas our results provide exact asymptotics, including the characterization of saddle points\" seems to imply that this work contains a more complete analysis of GD dynamics, which is not the case.*\n\nThank you for your suggestion. We will revise the discussion of related works to better acknowledge the contributions of Bachtis et al. and Harsch et al. In particular, we will clarify that while our work provides exact asymptotics and characterizations of saddle points, their analyses offer valuable heuristic insights into GD dynamics over time, which complement our results rather than compete with them."}, {"review_id": "dvQlDHYJga", "reviewer": "Reviewer_KcNC", "summary": "The paper considers RBM in the asymptotic limit where the input dimension goes to infinity but the number of hidden units remain finite, and proves that the RBM training objective is equivalent to that of an unsupervised multi-index model with a non-separable penalty in this regime. The paper then proceeds to apply and extend established mathematical techniques for the multi-index model to analyze the asymptotic behavior of RBM trained on the spiked covariance data, and derived closed-form equations describing the gradient-descent dynamics of RBM.", "questions": "1. The paper suggests around line 80-84 that statistical physics approaches is closer to Bayesian sampling and considers the full posterior. However, isn't their approaches equivalent to maximum likelihood when taking the temperature to 0 limit?\n2. In section 4, when comparing the spiked covariance model to an RBM teacher, you need to assume U is binary and W is approximately orthogonal, these are additional assumptions on the spiked covariance model that you don’t need for the following theoretical results, is that correct? If my understanding is correct, maybe you should be more explicit about it in this section.\n3. Some numerical results are present in the Appendix but not explicitly referred to in the main text. For example, when discussing the convergence of different AMP algorithms in line 295-299, it is maybe useful to point to Appendix F.1 where you showed numerical results comparing the performance of AMP with random initializations or more informed initialization schemes. \n4. What are the actual distributions P_u and P_w used in your numerics? Do their forms affect the convergence of AMP-RBM?\n5. I am a bit confused about the results showing overlap vs. SNR (or lambda) in the main text vs. the appendix. Just to confirm my understanding, in the main text you showed results with r=k=2, and the lines are SE corresponding to Eq. 19, which should hold irrespective of Theorem 4 and the k=r=1 assumption. In the appendix you stated that the lines are for rank-1, which I suppose refer to k=r=1, where the line now corresponds to Theorem 4, which assumes the convergence of AMP-RBM, is this correct? What would SE look like for k=r=10?\n6. This may be a broad and less relevant question. This paper proposes potential simplification of the gradient of the log-likelihood in the asymptotic limit, could you perhaps discuss whether the results may provide any insights to score-based diffusion models, a very different type of generative model that is more commonly used in recent applications, and also considers approximating the gradient of the log-likelihood of data?\nAnd some typos...\n7. Line 115, the biases should be theta and b? \n8. Line 117, isn’t the energy term order 1 after adding the 1/sqrt(d) normalization, so should be ‘intensive’ instead of ‘extensive’? \n9. In the appendix, there should no longer be integrating over v in the second line of Eq 35.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: \nThe paper presents theoretical results on the sharp asymptotics of RBM. The connection established between the RBM and the unsupervised multi-index model is general and does not rely on specific data assumptions, this connection enables simplified approximations of the log-likelihood and its gradient, and could potentially be used to accelerate training, as the authors pointed out. For more precise theoretical calculations, the authors then model the inputs as a spiked covariance model, and derived the AMP iterations and its corresponding deterministic SE, and derived the asymptotics of GD dynamics. Combined with thorough numerical validation and empirical results, this paper provides rigorous theoretical understanding of the learning dynamics of RBM. The paper is also clear and well-written. \nOverall, while the paper is still limited by its data assumptions (see weaknesses), it presents elegant and accurate theoretical results for the RBM and verified them numerically, extending mathematical results in supervised learning to a type of unsupervised generative model. \n\nWeaknesses:\nAs mentioned earlier, the main theoretical result of this paper relies on the data assumption, i.e., the spiked covariance data model, which is a relatively simple model for unsupervised learning. The authors did not discuss how their results may provide insights for data beyond this restrictive assumption. I believe the paper would largely benefit from some numerical experiments showing that behavior on some benchmark datasets for unsupervised learning can be also (perhaps qualitatively) captured by the theory. For example, the authors already showed results verifying theorem 1 in the appendix using Fashion-MNIST, is it possible to approximate Fashion-MNIST using a spiked-covariance model and show comparison between AMP-RBM and GD on this data?  \nAlso, the main technical contribution of this paper is 1) proposing the analogy between RBM and the multi-index model in the asymptotic limit 2) deriving the AMP equations and analyzing GD dynamics of RBM in the asymptotic limit and under the spiked-covariance data assumption. While the first point is novel and insightful, the second point largely build on existing work on multi-index models, and the major theoretical advancement is the extension to coupled regularization. The extension itself is relatively straightforward technically as the number of hidden units is finite. While this is not necessarily a weakness, I do think that because the technical advancement is relatively straightforward, there should be more emphasis on how the new theoretical result on RBM can provide new insights. For example, the paper would benefit from a discussion highlighting properties predicted by the RBM theory that are not in the multi-index model. \nThe paper could also benefit from a conclusion/summary section to discuss the potential impact and possible extensions of the work.", "was_revised": true, "final_justification": "The rebuttal solved my questions and I believe the paper should be accepted with detailed revision, incorporating the points raised by both me and other reviewers.", "rebuttal": "Thank you for the detailed feedback. We will address both the weaknesses and the questions below.\n\n* *As mentioned earlier, the main theoretical result of this paper relies on the data assumption, i.e., the spiked covariance data model, which is a relatively simple model for unsupervised learning. The authors did not discuss how their results may provide insights for data beyond this restrictive assumption. I believe the paper would largely benefit from some numerical experiments showing that behavior on some benchmark datasets for unsupervised learning can be also (perhaps qualitatively) captured by the theory. For example, the authors already showed results verifying theorem 1 in the appendix using Fashion-MNIST, is it possible to approximate Fashion-MNIST using a spiked-covariance model and show comparison between AMP-RBM and GD on this data?*\n\nWe appreciate the suggestion and agree that extending beyond the spiked covariance model is important. Most of our theoretical results (Theorems 2-5) do rely on this assumption, but we emphasize that the connection between RBMs and multi-index models holds for more general cases (Theorem 1), which paves the way for future generalizations.\n\nIn Appendix F.2, we provide a preliminary analysis of GD dynamics under the spiked covariance model, including the cascade of emergence phenomena and the repulsion effect between hidden units, which have also been observed in Bachtis et al. and Harsch et al. for real data. These results support the relevance of our theory.\n\nHowever, approximating Fashion-MNIST with a spiked covariance model is challenging: AMP-RBM does not converge reliably, and DMFT becomes invalid. We will clarify these limitations and highlight extending the theory to more realistic data as a promising direction for future work.\n\n* *Also, the main technical contribution of this paper is 1) proposing the analogy between RBM and the multi-index model in the asymptotic limit 2) deriving the AMP equations and analyzing GD dynamics of RBM in the asymptotic limit and under the spiked-covariance data assumption. While the first point is novel and insightful, the second point largely build on existing work on multi-index models, and the major theoretical advancement is the extension to coupled regularization. The extension itself is relatively straightforward technically as the number of hidden units is finite. While this is not necessarily a weakness, I do think that because the technical advancement is relatively straightforward, there should be more emphasis on how the new theoretical result on RBM can provide new insights. For example, the paper would benefit from a discussion highlighting properties predicted by the RBM theory that are not in the multi-index model. The paper could also benefit from a conclusion/summary section to discuss the potential impact and possible extensions of the work.*\n\nWhile our analysis builds on prior work on multi-index models, we emphasize that the unsupervised version considered here is itself novel. Previous analyses largely focused on supervised settings, whereas our work extends the framework to the unsupervised case—leading to significantly different phenomena, such as distinct weak recovery thresholds.\n\nMoreover, in Appendix F.2, we show that the RBM model captures dynamics like the cascade of emergence and hidden unit repulsion, similar to findings in Bachtis et al. and Harsch et al., but absent in standard multi-index models. We agree that identifying more such insights is a promising direction, and we will highlight this part as well as the broader implications and potential extensions.\n\n* *The paper suggests around line 80-84 that statistical physics approaches is closer to Bayesian sampling and considers the full posterior. However, isn't their approaches equivalent to maximum likelihood when taking the temperature to 0 limit?*\n\nThank you for pointing this out. As clarified in Appendix A (L511–516), the zero-temperature limit of statistical physics approaches does not recover maximum likelihood, but instead maximizes a different objective. We will clarify this more explicitly in the main text.\n\n* *In section 4, when comparing the spiked covariance model to an RBM teacher, you need to assume U is binary and W is approximately orthogonal, these are additional assumptions on the spiked covariance model that you don’t need for the following theoretical results, is that correct? If my understanding is correct, maybe you should be more explicit about it in this section.*\n\nYour understanding is correct. The reduction of the spiked covariance model to a teacher RBM requires assuming binary U and approximately orthogonal W, but these assumptions are only used in this illustrative comparison—not in our theoretical results. We will make this distinction clearer in Section 4.\n\n* *Some numerical results are present in the Appendix but not explicitly referred to in the main text. For example, when discussing the convergence of different AMP algorithms in line 295-299, it is maybe useful to point to Appendix F.1 where you showed numerical results comparing the performance of AMP with random initializations or more informed initialization schemes.*\n\nThank you for the helpful suggestion. We will revise the main text to explicitly refer to Appendix F.1, where we provide numerical results showing how the convergence behavior of AMP depends on initialization, in line with the discussion around Corollary 1.\n\n* *What are the actual distributions P_u and P_w used in your numerics? Do their forms affect the convergence of AMP-RBM?*\n\nAs stated at the beginning of Appendix F.1, we use the Rademacher prior in our main experiments. We have also tested other distributions, including Gaussian–Bernoulli and sparse Rademacher priors. While the convergence speed of AMP-RBM varies across priors, we observe that it consistently converges to the correct fixed point at large SNR, similar to Figure 5. We will add these additional experiments and clarify this point in the Appendix.\n\n* *I am a bit confused about the results showing overlap vs. SNR (or lambda) in the main text vs. the appendix. Just to confirm my understanding, in the main text you showed results with r=k=2, and the lines are SE corresponding to Eq. 19, which should hold irrespective of Theorem 4 and the k=r=1 assumption. In the appendix you stated that the lines are for rank-1, which I suppose refer to k=r=1, where the line now corresponds to Theorem 4, which assumes the convergence of AMP-RBM, is this correct? What would SE look like for k=r=10?*\n\nYour understanding is correct. In Figures 1, 2, and 4, we present results for k = r = 2, where the lines show the SE predictions from Eq. (19), which holds independently of Theorem 4. \n\nFor k = r = 10, the SE would involve a 10*10 overlap matrix, which is numerically difficult to compute. However, as noted after Corollary 1, we can assume the overlap matrix to be diagonal to find the convergent point, allowing us to reduce the SE to a scalar fixed-point equation similar to the rank-1 case. This simplification enables us to locate one of the possible saddle points of AMP-RBM, though other saddle points may also exist.\n\n* *This may be a broad and less relevant question. This paper proposes potential simplification of the gradient of the log-likelihood in the asymptotic limit, could you perhaps discuss whether the results may provide any insights to score-based diffusion models, a very different type of generative model that is more commonly used in recent applications, and also considers approximating the gradient of the log-likelihood of data?*\n\nThis is an insightful comment. While the objective of score-based diffusion models differs from that of RBMs, and our approximation of the log-likelihood gradient does not directly apply, we believe similar simplifications could emerge in high-dimensional settings. In fact, vanilla diffusion models have been analyzed for high dimensional problems and linked to AMP methods (see e.g. Posterior Sampling in High Dimension via Diffusion Processes by Montanari and Wu). Extending such analyses to score-based diffusion models is a promising research direction, and we will briefly mention this connection in the revised manuscript.\n\n* *Line 115, the biases should be theta and b?*\n\nYes. We will correct this typo.\n\n* *Line 117, isn’t the energy term order 1 after adding the 1/sqrt(d) normalization, so should be ‘intensive’ instead of ‘extensive’?*\n\nThank you for the observation. You're correct that the exponent in Eq. (2) is of order 1—it represents the energy per data point. In this context, we use “intensive” to mean that the energy scales linearly with the number of data points n, i.e., the total energy is of order n. We will clarify this wording in the revised manuscript to avoid confusion.\n\n* *In the appendix, there should no longer be integrating over v in the second line of Eq 35.*\n\nYes. We will correct this typo."}, {"review_id": "XeP7Induii", "reviewer": "Reviewer_qSCD", "summary": "This work considers Restricted Boltzmann Machines (RBMs) in the classic high-dimensional limit of growing input dimension and a growing number of data points (asymptotically proportional) and contributes to the analysis of RBMs in this setting. First, a simplified form of the log-likelihood function is derived in this asymptotic setting (Theorem 1), complemented by corresponding forms of the gradient and some classic further simplifications. This is then used together with the classic Spiked Covariance Model to analyse Approximate Message Passing (AMP) on the RBM (which in turn forms a new approach to train RBMs), in particular, the gradient of the simplified log-likelihood at the AMP fixed point (Theorem 2) and the convergence behaviour of AMP under certain initializations (Theorem 3). Furthermore, again using AMP, an asymptotic characterization of stationary points of the log-likelihood are provided (in Theorem 4) and a result on the convergence behaviour of gradient descent (Theorem 5), which is complemented by numerical experiments on synthetic data and Fashion MNIST. The main results are complemented by generalizations (e.g., a more general AMP algorithm) and a result on the global optimum and the AMP fixed point for a simplified variant of the Spiked Covariance Model under standard assumptions.", "questions": "**Question 1** Related to Theorem 1  \nThe following aspects are relevant for *Clarity*, *Quality*, *Significance*, and *Rating*\n\nQ1.1 Lack of precision  \nFor example, Equ (4) can only hold if \n$d,n\\rightarrow\\infty$ simultaneously with \n$n/d\\rightarrow \\alpha$, cf. L123. \nI guess the setup is the following. \nLet $(n_l)_l$ and $(d_l)_l$  be two nondecreasing, unbounded sequences of integers such that \n$\\frac{n_l}{d_l} \\rightarrow \\alpha$ for $l\\rightarrow\\infty$. Furthermore, let $X(l)\\in\\mathbb{R}^{n_l \\times d_l},\\ldots,\\theta(l)\\in\\mathbb{R}^{d_l},b(l)\\in\\mathbb{R}^k$ \nbe such that the conditions in L143 hold. Then for $l\\rightarrow \\infty$, we have\n$\\frac{1}{d_l}|\\log \\mathcal{L}(W(l),\\theta(l),b(l)) - \\log\\tilde{\\mathcal{L}}(W(l),\\theta(l),b(l))| \\rightarrow 0$.\n\nThat this is the intended setup is indicated by LL142, where $b(n)$ and $b(d)$ appear (this is also confusing due to two different parametrizations).\n\nA similar issue appears in (20), (23), (24), (29), (30), Lemma 1 (in (52), cf. the corresponding comment), and (61).\n\nQ1.2 Proof strategy for Theorem 1  \nIn L519, it is stated that \"For the following we will prove a stronger result\". But how does Theorem 1 follow from (32)? In particular, (32) involves the gradient of the likelihood, whereas (4) concerns the likelihood itself. The connection between the two is not clear at all.\n\nFurthermore, the term involving $\\eta_1$ in (5) seems plausible (after doing a brief, elementary calculation), but it is not clear at all how the form of $\\eta_2$ appears.\n\nQ1.3 Equ (39)  \nHow exactly does it follow from (38)? It seems to be a rather lengthy computation.\nSimilarly for equ (40) and (41).\n\nQ1.4 L523, \"The first term is exactly $\\eta_1$\"  \nThis does not seem to be the case. $\\alpha$ is defined as the limit of $n/d$ for $n,d\\rightarrow\\infty$, but in (33) (using $\\frac{1}{\\sqrt{d}}=\\sqrt{\\frac{n}{d}}\\frac{1}{\\sqrt{n}}$) only $n/d$ appears, but not its limit. Furthermore, (33) considers the likelihood from (3), not its gradient, so how does this help to show (32)?\n\nQ1.5 Equ (34)  \n* First line: What happened to $P_h(h)$ from (33)?\n* Second line: Where is the second term in the sum inside the exponential inside the integral?\n* Third line: How does this follow?\n* Fifth line: How does this follow? Where does the exponential come from?\n\nQ1.6 Equ (35)  \nWhere does the $P_v$ in (35) come from? It has been integrated out in (34)\n\nQ1.7 Equ (38)  \nHow does the second equality follow? Where does the exponential come from?\n\n**Question 2** Related to Theorem 2  \nThe following aspects are relevant for *Clarity* and *Quality*\n\nQ2.1 Equ (17)  \nHow is it ensured that $B_t^{-1}$ is invertible?\nDoes the minimum in the definition $\\tilde{h}^t$ exist? Is it unique? If it is not unique, which minimizer is chosen?\n\nQ2.2 Assumptions  \n$\\eta_1$ and $\\eta_2$ are defined in Theorem 1 analytically, so these functions are either continuously differentiable or not. So are they continuously differentiable or not? And where exactly is this used in the proof of Theorem 2? It seems that only their differentiability is used (to define $\\nabla \\eta_1$, $\\nabla \\eta_2$).\n\nQ2.3 Theorem 2, \"at the fixed point\"  \nDoes a fixed point always exist, and if so, is it unique? This is not discussed, and no reference is given.\n\nQ2.4 Equ (18)  \nWhere does $\\alpha$ come from? Using the definition of $Q(W)$ from L153, there should be $1/d$ instead.\n\n**Question 3** Related to Theorem 3  \nThe following aspects are relevant for *Clarity*, *Quality* and *Significance*\n\nQ3.1 Choice of $\\psi$  \nWhat would be an interesting PL(2) function $\\psi$ in this context? \nIs the choice in L279 in the context of Theorem 4 the only relevant one?\n\nQ3.2 Limit notion  \nAnd what can be inferred from the Cesaro convergence (26)? In other words, which statements about the behaviour of the RBM in the asymptotic setting can be given using this limit notion?\n\nQ3.3 Extension  \nDoes a similar result like Theorem 3 hold also for the $u_i^\\ast$?\n\n**Question 4** Additional questions related to (significant) technical details  \nThe following aspects are relevant for *Clarity*, *Quality* and *Rating*\n\nQ4.1 Equ (3)  \nWhere is the $dP_v(v)$ term? Is it just assumed that it equals 1? If not, which adjustments are needed for the remaining developments?\n\nQ4.2 LL209  \n\"We deal with the term $\\eta_2$ by viewing it as a set of constraints and introducing Lagrange multipliers to fix them\"\nThis is unclear and requires further elaboration. In particular, $\\eta_2$ is just an additive term in the objective function of the optimization problem, so in which sense is it a constraint?\nFurthermore, What is meant by \"to fix them\"? In general, a Lagrangian formulation is a relaxation, and one needs conditions to enforce equivalence.\n\nQ4.3 Equ (73)  \nHow does this follow from Theorem 3? \n\nQ4.4 LL627  \nHow exactly does the zero convergence stated in line L627 follow from Theorem 2? The latter does not involve the diverging factor $\\sqrt{d}$, and since Theorem 2 does not provide any convergence rate, it is not clear that the convergence is fast enough to overcome the growth of $\\sqrt{d}$.\n\nQ4.5 Equ (82)  \n* L653, \"Then it suffices to map (81) to a general AMP iteration as the following\"\n\tWhich general AMP iteration? The one in (56), (57)?\n* Theorem 5 uses $t\\geq 0$, but some subexpressions are in (82) are not defined for $t=0$.\n* Something seems to be off with the mapping to the general AMP iteration. (25) can indeed be rewritten as (81), however, it is not clear how to get from (81) to (82). In particular, when plugging in the various quantities in (82), $\\hat{W}^t$, $\\overset{\\circ}{W^t}$ etc get mixed up. More details need to be provided on how to perform this mapping.", "limitations": "In general yes. However, while the setting used is classic, its inherent limitations should be briefly stated.\n* Apart from Theorem 1, mostly a synthetic data setup is considered, which might be unrealistic from a practical perspective.\n* This work considers a particular asymptotic setting. While interesting, it is still an approximation, and since no convergence rates are given, it is unclear when this approximation can be considered sufficiently accurate.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "This work contains a thorough theoretical investigation of RBMs in a classic asymptotic setting, with a particular focus on AMP and gradient descent, both under the Spiked Covariance Model. This is a relevant and active area, and the aim of the authors to provide a rigorous analysis (instead of using heuristics) makes the work particularly relevant. Furthermore, the proposed AMP algorithm in the asymptotic setting might be of independent interest as a new training approach to RBMs.\n\nAs clearly stated in the manuscript, using AMP to analyse RBMs is not new, and essentially all of the techniques used are established (though might be relatively recent, for example the developments in Section D), though making everything rigorous would still constitute a very relevant contribution.\n\nUnfortunately, the work suffers from many missing details and imprecisions, cf. the detailed comments and suggestions below and the questions, in addition to typos and some language problems. Since the explicitly stated goal of the present work is to provide a rigorous asymptotic analysis, the imprecisions and missing details are a major problem, and indeed quite a few steps and results were difficult to check for the present reviewer. If these problems are addressed and resolved (which would require a careful revision of the manuscript), this work can be a very interesting and promising contribution to the analysis of RBMs, with potentially considerable follow up work.\n\n**Detailed comments and suggestions**  \nL10\nLanguage, \"via the dynamical mean-field theory\" is probably more common\n\nL11, 13\nLanguage, \"RBMs\" is probably better in terms of grammar\n\nL14\nAbbreviation BBP not introduced (in contrast to all other abbreviations in the abstract)\n\nL20\nPotentially ambigous sentence: Not state of the art for image generation anymore, but for other tasks? Made add an \"for example\"\n\nL36\nGrammar, \"yields\"\n\nL38\nLanguage, a connecting word is missing\n\nL59\nUnclear, does \"mathematically\" refer her to general analytical techniques (including formal derivations), or rigorous results?\n\nL64\n\"BBP threshold\" has not been introduced yet. In fact, the first reference regarding this is given only in L249.\n\nL107\nTypo, \"Spiked\"\n\nSection 2\nThere are some imprecisions / missing details\n* What are $\\theta$ and $\\beta$? These quantities are never introduced\n* How exactly is the data $X$ used? After its introduction in L113 it is never explicitly mentioned anymore. I guess it enters (3) via $x_\\mu$, the rows of $X$ according to the convention at the end of the section.\n\nL113\nSomething is wrong here (superfluous \"using\"?)\n\nLL115\nSomething is wrong here. $W$, $\\theta$, $b$ appear to be trainable parameters, $v$ and $h$ are data ($v$ visible, $h$ hidden)\n\nL118\nWhy is \"prior\" in quotes? \n\nL118\nMaybe add \", respectively.\" at the end for clarity\n\nEqu (3)\n* Is $Z^n(W,\\theta,b)$ actually the quantity from (2) raised to the $n$-th power? If so, maybe use $Z(W,\\theta,b)^n$ instead to avoid confusion.\n* I strongly suggest to use $h$ instead of $h_\\mu$ since this is a free variable (it is integrated over), so using an index can lead to confusion.\n\nEqu (3)\nMaybe use a different symbol than $\\mu$ for the running index. Since you work a lot with probability distributions, and $\\mu$ is one of the standard symbols for probability measures, this might lead to confusion.\n\nL124-126\nMaybe include examples to illustrate these conventions.\nFurthermore, I strongly recommend to introduce these conventions before they are used for example in Equ (3).\n\nAssumption 1\n* Is separability an established terminology in the present context? Because technically, this just means that the random variables $v_1,\\ldots,v_d$, where $v \\sim P_v$, are independent (the density w.r.t. Lebesgue measure of their law factorizes)\n* What is meant by \"a bounded distribution\"? Bounded support? The density is a bounded function? Or do you mean by \"distribution\" any density w.r.t. Lebesgue measure, leading to a (nonnegative) measure that is not necessarily a probability measure?\n\nEqu (6)\nIncompatible dimensions (wrong use of transpose). The first argument of $\\eta_1$ in (5) needs $W^\\top x_\\mu$, not $x_\\mu^\\top W$\n\nL147\nInconsistent use of commas, \"i.e.\" and \"i.e.,\", \"e.g.\" and \"e.g.,\". The remainder of the manuscript should also be checked for this issue.\n\nL148\nGrammar, missing article\n\nEqu (8)\nWhere exactly is the proof of this result?\n\nL154-157\nA reference should be given for this.\n\nEqu (9), (10)\nThe redefinition of the symbols on the lefthand side in these equations is potentially confusing, maybe choose different symbols.\n\nL155, 157\nWhile the notation $\\langle\\cdot\\rangle$ is very common in statistical physics, it rarely appears in statistics and (theory of) machine learning, so it should be briefly introduced somewhere.\n\nL181\nWording, something is wrong here. Maybe \"slightly generalized\"?\n\nEqu (12) \nWhich matrix norm is used here?\n\nL187, \"then we have\"\nBetter to use $\\approx$ instead of $=$\n\nL197\nWording. Maybe \"the teacher-student setting\"?\n\nL204\nTypo, duplication of \"now\"\n\nL204\nThis can be made a bit more precise, e.g., \"following the spiked covariance model (11)\".\n\nEqu (15)\nTechnically, $\\eta_1$ and $\\eta_2$ with just one argument are not defined (I guess it corresponds to $\\eta_1,\\eta_2$ from Theorem 1 with the remaining arguments set to zero)\n\nEqu (15)\nMinor remark: Optimization problems are usually formulated with $\\max$, and $\\mathrm{argmax}$ is only used when one defines a solution to it.\n\nL205\nWording, \"direct\" is not appropriate here. Similarly in L237\n\nLL206, \"While it is common to use AMP for supervised generalized linear regression\"\nReference?\n\nL209\n* Grammar, use singular \"aspect is\", or \"Other new aspects\"\n* Typo, \"penalty\"\n\nL210\nTechnically, the following display is not the new loss, but rather an optimization problem with the new loss.\n\nLL212\nConfusing. Is Algorithm 1 already \"AMP-RBM\", or is the latter a specific instance of the former?\n\nAlgorithm 1\nOn which AMP variant is Algorithm 1 based? It is not the one from Montanari and Venkataramanan, 2021 (e.g., there is an additional \"damping term\" here)\n\nL213\nGrammar, \"the denoisers\"\n\nL219\nGrammar, missing \"that\"\n\nL220\nWording, better to use \"Let ... be the\"\n\nFigure 1, caption\nTypo, \"initialization\"\n\nL228\nThe notation $U_{[1:r]}$, $W_{[1:r]}$ is not defined. Furthermore, what does $[G]_1^k$ mean?\n\nTheorem 3 / Footnote 1, \"Lipschitz continuous, uniformly at\"\nThis terminology is not quite standard, so it might be better to defined it explicitly in Theorem 3.\n\nLL244\nA reference regarding the weak recovery threshold should be added here.\n\nLL251, \"AMP-RBM as well as RBM (because their fixed points match)\"\nWhere exactly does this follow from?\n\nL275\nInconsistent use of cases, \"Assumptions\".\nSame issue in L287.\n\nCorollary 1\nWhat does \"can be diagonal\" exactly mean?\n\nL282\nTypo, \"techniques\"\n\nL289\nIt would be nice to provide a pointer to Section C.5 with the proof of Corollary 1 for the reader's convenience.\n\nL303\nGrammar, \"preferred to\"\n\nEqu (25)\nHow exactly is this equation related to what came before?\n\nL317, \"converges to $\\hat{W}$ uniformly,\"\nUniformly w.r.t. what?\n\nL319\nWording, better to use something like \"corroborated\" or \"illustrated\" instead of \"verified\"\n\nReferences\nThe reference entries should be carefully checked, upper / lower case use is inconsistent with the main text (e.g., boltzmann instead of Boltzmann in Salakhutdinov et al '07)\n\nL502 \nThe inverse temperature $\\beta$ is not introduced yet, the paragraph needs to be adapted accordingly.\n\nL503\nMissing comma\n\nL505\nWhat is $\\beta^\\ast$? I guess it refers to L192\n\nL512\nMissing comma\n\nL512\n\"maximizes... instead\" Reference / derivation?\n\nL514, \"impossible for inference\"\nLanguage, something is wrong here\n\nL514-516\nMaybe refer to the location of this result in the main text\n\nL519\nMissing comma, or use \"the following\"\n\nL522\nWhere are the arguments $\\theta$, $b$?\n\nL523, \"the derivative of the second term\"\nSecond term of what?\n\nEqu (35)\nThis uses the separability from Assumption 1. This should be made explicit.\n\nEqu (36)\n$\\mathcal{Z}$ not defined\nHow does the last line follow?\n\nL529, \"(36) also directly proves (4).\"\nHow? (4) does not involve any derivative.\n\nL535\nGrammar and Language\n\nL536, \"The gradients can be dealt with in a similar way\"\nWhat exactly does this mean?\n\nL547\nMissing comma\n\nL552\nTypo\n\nAssumption 3\nIs this assumption new? Or has it been used in the literature before? It is not clear what the relation to the references in LL560 is.\n\nL555\nWhat is $\\|\\mathcal{F''}\\|$? Supremum norm? Measurable essential supremum?\n\nEqu (5)\nInconsistent / undefined notation. I guess $\\mathcal{F}^{1}=\\mathcal{F}'$.\n\nL557\nWording. Better to write something like \"i.e., the data are well-normalized\"\n\nL559\nLanguage\n\nL564\nWhat exactly is meant by \"normalized\" here? That the matrix is normalized?\n\nL564\nWhat is \"the error matrix\"?\n\nEqu (52)\nThere is an imprecision here. In general, $n/d\\not=\\alpha$, only $n/d\\rightarrow\\alpha$, cf. also the comments and questions regarding Theorem 1.\n\nL570\nHow exactly does $\\mathbb{E}[\\tilde Z_{ij}]=1$ follow from Assumption 3 (presumably last part of (ii))?\n\nL572\nInappropriate notation. I guess $L^2$ refers to the supremum norm (the $\\ell_2$ norm for a matrix space would be the Frobenius norm).\n\nSection C.2\n* The AMP variant outlined here is not the one from Montanari and Venkataramanan, 2021, Supplement Section J, since here the full history of the iterates are considered in the denoising functions. On which AMP scheme is this section based? It seems to be (a variant of) Zhong et al '24, Section 2.2\n* Inconsistent notation for Onsager coefficients (subscript with and without comma)\n\nEqu (56) and Equ (57)\n$F^t$, $E^t$ in (56) and $F$, $E$ in (57 are not defined. I guess these are generic side information, cf. Zhong et al '24, Section 2.2\n\nTheorem 6\n* The AMP variant and the setup is sufficiently different from Zhong et al '24 to require a full proof.\n* The wording of this result could be improved.\n\nL592\nGrammar, use plural\n\nL604\nTypo, \"Lipschitz\"\n\nEqu (64)\nSome details on how to derive the second equation should be given. I guess the argument is as follows: By definition, $h_t$ is a stationary point of the objective function in the minimization in (17), so the gradient of this objective function at $h_t$ is zero, and it can be rearranged for the latter, and in can be plugged in the update rule for $U^t$ in Algorithm 1. Finally, the update rule can be rearranged for $h_t$, and this expression is plugged in as the argument for the derivative of $\\eta_1$.\n\nL614, \"Moreover, at the fixed point we have...\"\nHow? I guess it follows from the last line of Algorithm 1.\n\nL625, \"which suggests that the limit in (73) exists\"\nImprecise. Does the preceding constitute a rigorous proof or not?\nSimilar issue in L627\n\nEqu (74)\nMissing closing bracket\n\nEqu (76)\nSuperfluous opening bracket. Furthermore, the multiplicative factor needs to be $\\alpha^{-1}$\n\nL653, \"as the following\"\nWording, I guess what is meant is \"as follows\"\n\nL641\nWording\n\nL673-679\nPutting this part into an Example environment would improve readability.\n\nL681, \"we need to give some notations\"\nWording, better to use something like \"we need to introduce some notation\"\n\nL696, \"Now we present our main results,\"\nProblematic formulation since this is part of the supplementary part and only briefly mentioned in the main text. Maybe use \"main results in this section\" or something similar.\n\nEqu (96)\nWhat is $A$? I guess it is supposed to be $\\mathcal{A}$, similar to $\\mathcal{A}^\\ast$ in (8) in Viluchio et al '25\n\nLL712\nWhat exactly is meant by uniformly here?\n\n(102), second line\nSomething is wrong here. I guess in the second term in the sum a $w$ is missing (and indeed it appears in (103))\n\nL726\nWhy can Lemma 4 be used here? It requires minimization / maximization over compact sets.\n\nL727\nWhat is the resulting direction of $f$, and how does (104) then follow from it? More precisely, how does the second term in the first line of (104) follow in this way?\n\n(105)\n$\\phi$ is not included in the min / max anymore\n\nL734-736\nHow exactly does this follow from the (strong) law of large numbers?\n\nL740 Typo\n\nLL753\nHow exactly does this follow?\n\nLL793\nTerminology, \"contrastive divergence\"\n\n(137)\nProblematic notation. $\\zeta_{ij}$ is already defined, (137) is just an estimation based on SE. Maybe use $\\hat\\zeta_{ij}$ instead.\n\nL827\nTypo, \"realistic\"\n\nFigure 4\nWhat are the \"error bars\"? Standard deviation?\n\nLL835, \"AMP-RBM might fail to converge for k= 10,\"\nWhy?\n\nL851, \"corresponding to Figure 5\"\nI guess it means something like \"with the same setting\" or \"analogously\"\n\nL858, \"decimation AMP\"\nWhat exactly is this?", "was_revised": true, "final_justification": "As stated in the initial review, the present manuscript forms a solid contribution to a relevant and active field of machine learning. While the submission contains quite a few issues (primarily typos and imprecisions), the authors have been able to address all of my major concerns, cf. Questions 1-4. For these reasons, I recommend acceptance and raise my overall score to 5. However, I would like to emphasize that this evaluation assumes that the authors implement all the discussed changes.", "rebuttal": "Thank you very much for your careful reading. We will carefully revise the manuscript to improve the language, notations and add references according to your suggestions. Due to the length limit of the rebuttal, we focus below on addressing the main issues. Please let us know if there are any remaining unclear points.\n\nQ1.1. **Lack of precision**: There are indeed some typos in Theorem 1. We should regard everything as a function of $d$ with $d\\to\\infty$, and thus we should write $X(d),W(d),\\theta(d),b(d)$ etc. Moreover, although it is possible to consider $n(d)/d\\to\\alpha$, we decide to define $n(d)=\\alpha d$ with a constant $\\alpha$ to avoid unnecessary techinical difficulties.\n\nQ1.2. **Proof strategy for Theorem 1**: We cannot directly obtain eq.(4) from eq.(32). Eq.(4) is obtained by combining eqs.(33) and (36). The first term of $logL$ remains the same, and the second term is $logZ$, which is equal to $\\eta_2+o(1)$ by eq.(36). We prove eq.(32) because it is useful later. See Q1.5 for the calculation of $\\eta_2$.\n\nQ1.3. **eq.(39)**: In eq.(39), when we take derivative w.r.t. $\\theta$, the denominator is $Z(W)$, and we can use eq.(36). The nominator is eq.(38). The right side of eq.(38) divided by the right side of eq.(36) is exactly the derivative of $\\eta_2$ w.r.t. $\\theta$, which gives eq.(39). eqs. (40) and (41) are similar.\n\nQ1.4. **L523**: We decide to directly define $n(d)=\\alpha d$, and then it follows. Then we take the derivatives of eq.(33), which is eq.(34), and thus we can prove eq.(32) which only concerns the derivatives of eq.(33).\n\nQ1.5. **eq.(34)**: In eq.(34) we do not consider the integral over $P_h$, and we add this integral back in eq.(35) and exchange the integral and derivative. There is a typo in the second line. We should have the $v_i\\theta_i$ term. The third line comes from Taylor’s expansion: $e^{(v_ih^Tw_i+v_i\\theta_i)/\\sqrt{d}}=1+(v_ih^Tw_i+v_i\\theta_i)/\\sqrt{d}$+higher order terms. For the fifth line, we also use the Taylor’s expansion $e^{(h^Tw_i+\\theta_i)^2/2d}=1+(h^Tw_i+\\theta_i)^2/2d$+higher order terms.\n\nQ1.6. **eq.(35)**: It is a typo. There should not be the integral over P_v.\n\nQ1.7. **eq.(38)**: The right side of eq.(38) is obtained by first integrating over $P_v$ and then using $e^{(h^Tw_i+\\theta_i)^2/2d}=1+(h^Tw_i+\\theta_i)^2/2d+$higher order terms.\n\nQ2.1. **eq.(17)**: If $B_t$ is not invertible, the algorithm fails. Theorem 2 is based on an implicit assumption that AMP-RBM has a fixed point, and then $B_t$ is invertible at that point. In terms of the minimizer, it might not be unique, and we can choose any one as long as f,g are Lipchitz continuous (required by Theorem 3). We make this explicit in L688-690.\n\nQ2.2. **$\\eta_1$ and $\\eta_2$**: $\\eta_1$ and $\\eta_2$ defined in Theorem 1 are continuously differentiable, but our results in Section 5 hold for more general $\\eta_1$ and $\\eta_2$. It is true that the differentiability is only used to define their derivatives and to obtain the property of the minimum in eq.(17).\n\nQ2.3. **fixed point in Theorem 2**: A fixed point might not exist and might not be unique. The existence of a (stable) fixed point is related to the replicon stability condition (L269-273). There might be more than one fixed point (L295-299).\n\nQ2.4. **eq.(18)**: Notice that in eq.(15) it is $n\\eta_2$, so after taking derivatives it becomes $n/d=\\alpha$.\n\nQ3.1. **choise of $\\psi$**: Except the choice in L279 (the overlap), we can also choose $\\psi$ to be the L1 or L2 distances between $W^t$ and $W^\\*$.\n\nQ3.2. **Limit notion**: The convergence (24) can e.g. give the overlap, L1 or L2 distances between RBM’s saddle points $\\hat{W}$ and the signal $W^\\*$ by choosing different $\\psi$.\n\nQ3.3. **Extension of Theorem 3**: We can write a similar arguments for $u^\\*$. See eq.(61).\n\nQ4.1. **eq.(3)**: Eq.(3) is the standard definition of RBMs' likelihood. Note that the visible units are actually the data $X$, so there should be a $P_v(x)$ term. We drop this term because it does not depend on the training parameters (L121-122).\n\nQ4.2. **L209**: Our original phrasing was imprecise. To clarify: we introduce the Lagrange multiplier to decouple the joint optimization over $Q$ and $W$ and enable alternating optimization.\n\nQ4.3: **eq.(73)**: By the definition of $M_t$ and the Stein’s lemma, we have $M_t=E[Z^tW^\\*]/E[(W^\\*)^2]$. By eq.(61) we have $E[Z^tW^\\*]=\\sum_iz_i^t(w_i^\\*)^T/d$. Finally we can replace $z_i^t$ with $\\hat{z}_i$ by Assumption 2. By eq.(74) the limit on the right side of eq.(73) exists, and thus the limit on the left side of eq.(73) exists.\n\nQ4.4. **L627**: There is a typo in eqs.(32) and (42). It should be $\\sqrt{d}$ rather than $1/\\sqrt{d}$ (eqs.(37) and (39) are correct). Theorem 2 suggests that $\\nabla\\log\\tilde{L}(\\hat{W}(d))=0$ for any $d$, and thus eq.(32) gives the desired results. \n\nQ4.5. **eq.(82)**: Yes, one can find that eq.(81) is indeed a special case of the general AMP eq.(56). Moreover, one can verify that eqs.(81) and (82) are equivalent using the definition eq.(77). Notice that there is no $\\mathring{W}$ and $\\mathring{Z}$ in eqs.(81)-(82)! When we take eq.(77) into eq.(81), we only have $\\tilde{W}$ and $\\tilde{Z}$ as the arguments.\n\nThe following are additional questions in the weakness part:\n\n1. **L115**: There is a typo. $\\theta, \\beta$ are the learnable biases and $v,h$ are visible and hidden units.\n\n2. **L118**: $P_v$ and $P_h$ are called the “priors”, because the real joint distribution of v,h is given by eq.(1).\n\n3. **Assumption 1**: We will say that $P_v$ is a factorizable distribution with a bounded support.\n\n4. **eq.(8)**: It is exactly the gradient of eq.(5) if we set the biases to 0.\n\n5. **eq.(12)**: $||.||$ should be $||.||_F$.\n\n6. **eq.(15)**: We will add the definition of $\\eta_1,\\eta_2$ with one argument (i.e. eqs. (6),(7) with other arguments set to 0), and replace argmax with max.\n\n7. **Algorithm 1**: We refer to Algorithm 1 as \"AMP-RBM\". While inspired by Montanari and Venkataramanan (2021), our key modification is the introduction of the Lagrange multiplier $\\hat{Q}$. The proof in Appendix C primarily builds on Fan (2022) to handle memory terms, which is necessary for analyzing GD dynamics (Theorem 5). However, Algorithm 1 itself can be analyzed within the simpler framework of Montanari and Venkataramanan (2021).\n\n8. **L228**: We define $U_{[1:r]}$ to be the first $r$ elements of $U$. $[G_i]_{i=1}^k$ are iid Gaussian (i.e. G is a Gaussian random vector).\n\n9. **L251**: Theorem 2 suggests that the fixed points of AMP-RBM and RBM match.\n\n10. **Corollary 1**: We will state that when we initialize the SE (eq.(19)) with diagonal overlaps, then it remains diagonal. Thus, if it converges, the matrices in Theorem 4 (e.g. $\\bar{C}_\\infty$, $M\\_\\infty$) are diagonal.\n\n11. **eq.(25)**: It is the GD over $log\\tilde{L}$, which comes from eq.(8).\n\n12. **L317 and L712**: “uniform convergence” means the same thing as Assumption 2.\n\n13. **L502-505**: $\\beta$ is defined in eq.(31), which we will move to the beginning. We will also mentioned that $beta^*$ is defined in eq.(14).\n\n14. **L512**: By eq.(31), the posterior of $W$ concentrates around the maximizer of $\\sum_\\mu x_\\mu^TWh$ when $\\beta$ goes to infinity.\n\n15. **L514**: Previous literature predicts that the system is in the spin glass phase and it is statistically intractable to infer the planted signal $W^\\*$. We will refer to the weak recovery threshold in eq.(22).\n\n16. **L522**: There is a typo. It should be $log L(W,\\theta,\\beta)$.\n\n17. **L523**: it should be \"the second term of eq.(34)\".\n\n18. **eq.(36)**: It should be $Z$ rather than $\\mathcal{Z}$, which is defined in eq.(2). For the last line, we integrate over $v_i$, and use $1+(h^Tw_i+\\theta_i)^2/2d\\approx e^{(h^Tw_i+\\theta_i)^2/2d}$.\n\n19. **L536**: It means that the gradient of logL can be dealt with similarly to eqs.(34-35) when $P_v$ has non-zero mean.\n\n20: **Assumption 3**: Assumption 3 is from Assumptions (H2),(H3) in Guionnet et al'23 and Hypothesis 2.1 in Mergny et al'24. We refer to these literatures for potential generalization.\n\n21: **L555**: |F’’| means the supremum of F’’, and indeed $F^{(1)}=F’$.\n\n22: **L564**: “normalized” means that each element has unit variance. We call $E$ “the error matrix” because it vanishes in high dimensions, and thus the data $X$ look like spikes plus iid matrix $\\tilde{Z}$.\n\n23. **L570**: We obtain $E[\\tilde{Z}_{ij}^2]=1$ from eq.(53), using $\\theta_0(F^2)-\\theta_0(F)^2=1$ (Assumption 3(ii)).\n\n24: **L572**: We refer to the $L^2$ norm of a matrix rather than the Frobenius norm.\n\n25: **Section C.2**: The AMP here can be regarded as a variant of Zhong et al’24. Following their notations, we add a comma in the subscript if necessary, e.g., we write $C_{ti}$ and $C_{t+1,i}$. $E^t$ and $F^t$ are generic side information of finite dimensions, which almost surely converges to $E,F$. Theorem 6 is close to Zhong et al’ 24. The main difference is to include the non-linearity F, which is dealt with in Mergny et al'24. Another difference is to generalize the side information from E,F to E^t, F^t, which is quite straight forward.\n\n26. **L727**: In eq.(103) we optimize over f with fixed $||f||=\\kappa\\sqrt{d}$. Thus $c^Tf$ reaches its maximum $||c||\\kappa\\sqrt{d}$ when $f=\\kappa\\sqrt{d}c/||c||$, which gives the second term of eq.(104).\n\n27: **eq.(105)**: There should be a supreme over $\\phi$.\n\n28: **L734-736**: By definition, $\\epsilon_d$ is the sum of means of independent random variables, which converges almost surely by the law of large numbers.\n\n29. **L753**: Because a family of pseudo-Lipschitz continuous functions on a bounded domain is necessarily equicontinuous (by the Arzelà-Ascoli theorem).\n\n30. **Figure 4**: Error bars represent the standard deviation over 10 runs.\n\n31. **L835**: The optimization problem eq,(17) becomes difficult to solve for k=10, and might suffer from numerical instability.\n\n32. **L858**: Decimation AMP refers to the AMP algorithm in Pourkamali et al.'24 (L852)."}]

Author rebuttal:

Meta-review: The paper considers RBM in the asymptotic limit where the input dimension goes to infinity but the number of hidden units remain finite. The authors then prove that the RBM training objective is equivalent to that of an unsupervised multi-index model with a non-separable penalty in this regime and  proceed by applying techniques for the multi-index model to analyze the asymptotic behavior of RBM trained on the spiked covariance data, and deriving closed-form equations describing the gradient-descent dynamics of RBMs

During the rebuttal the authors answered  satisfactorily to all concerns the reviewers had and the reviewers agreed that the paper should be acceptad with detailed revision, incorporating all points raised by the reviewers.
Decision: Accept (poster)