On the robustness of noisy solutions in non-convex neural networks Enrico M. Malatesta,1, 2 Alessandra Passalacqua,1 and Riccardo Zecchina1, 2
arXiv:2607.27000v1 [cond-mat.dis-nn] 29 Jul 2026
1
Department of Computing Sciences, Bocconi University, Milano, Italy 2 Bocconi Institute for Data Science and Analytics (BIDSA)
Optimization in non-convex neural network models is strongly influenced by the geometry of the solution space: sparse, isolated, point-like clusters are typically algorithmically inaccessible, whereas wide and flat regions can be found efficiently despite being relatively rare. At zero temperature this picture has been formalized in binary perceptrons through the overlap gap property (OGP), which limits algorithmic access to configurations with zero training error above a critical constraint density αOGP . Here we extend this description to finite temperature, where a positive training error is allowed and statistically penalized. We first show that the frozen one-step replica-symmetry-breaking solution, dominating the zero temperature equilibrium measure, survives at any finite temperature. We furthermore derive a general criterion, based on the smoothness of the single-pattern Gibbs weight near the decision boundary, that determines when a finite-temperature relaxation of the loss removes freezing. We then extend the OGP construction to finite temperature and show that dense, algorithmically accessible regions of finite-energy configurations persist beyond αOGP , up to a threshold αOGP (ϵ) that grows with the allowed training error ϵ. Finally, in the teacher-student setting, we show that these wide, finite-energy regions still retain good generalization. Using a finite energy message-passing algorithm, we demonstrate numerically that thermal noise enables effective generalization in the regime of constraint densities where both recovering the teacher and finding a zero temperature solution are computationally hard.
I.
INTRODUCTION
Over the last decade, numerous studies at the intersection of statistical physics and machine learning showed how the local geometry of the energy landscape of neural networks can be exploited to guide their optimization, and consequently improve their performance, despite the practical difficulty of navigating highly non-convex spaces [1–3]. The robust ensemble formalism was introduced in the study of non-convex neural networks, to prove the existence of atypical, but algorithmically accessible and well-generalizing, wide and flat regions at zero training error, as opposed to inaccessible isolated, point-like solutions, and algorithms designed to search for these regions turned out to be successful. At the same time, mathematicians have introduced the rigorous theoretical framework of the overlap gap property (OGP): whenever the near-optimal solutions of a problem lie in small, or even point-like, disconnected clusters, these become unreachable to a broad class of optimization algorithms [4]. The general formulation of the OGP theory makes it applicable to some well-known problems in statistical physics of complex systems [5], random graph theory [6] and simple neural network models [7]. This body of work, however, has almost exclusively been developed at zero temperature, where learning is phrased as a constraint satisfaction problem (CSP): a configuration has nonzero weight in the partition function only if it fits every training point correctly. A partial exception is offered by studies that relax the requirement by introducing a stability margin in the classification constraint, which enlarges the space of solutions of the CSP while remaining at zero temperature [8]; even so, both settings ultimately demand exact satisfaction of a fixed number of constraints. This is a demanding requirement, at odds with how learning is typically carried out in practice, where a nonzero training error is common - and can even improve generalization and robustness to noise, in contrast to overfitting. A prominent example is offered by large language models, which are extremely heavy to train, so that compute-optimal training generally stops before convergence, and a nonzero training loss is the rule rather than the exception [9, 10]. In this work we extend the study of the geometry of the configuration space to finite temperature, where imperfect classification is allowed but statistically penalized. We consider the paradigmatic case of binary perceptrons, either storing random patterns or learning a classification rule from a teacher. The simplicity of the architecture allows a tractable analytical study, and yet the discreteness of the weights renders the solution space non-convex, endowing it with the rich geometrical structure that motivates our study. Models are introduced in Section II, each being defined through its Hamiltonian. For each model, we will consider two classes of optimal and near-optimal weights in the energy landscape, corresponding to equilibrium and out-of-equilibrium configurations. The equilibrium ones are those typically encountered when sampling from the Gibbs measure with the standard error counting loss, at temperature T . At zero temperature, these are known to be organized in a frozen one-step replica-symmetry-breaking (1RSB) structure [11, 12], decomposed into exponentially many geometrically isolated, point-like clusters [7, 13]. The second class consists of atypical, out-of equilibrium configurations, obtained by biasing the measure to favor regions with large local entropy, that are invisible to the equilibrium analysis, but visible to common optimization algorithms because of their geometrical accessibility.
2 In Sec. III we start our discussion from the typical equilibrium configurations. We ask whether raising the temperature is sufficient to dynamically unfreeze the landscape, and show that it is not: the frozen structure persists at every finite temperature, in agreement with the dynamical field theory analysis of [14]. We show that the dynamical temperature diverges in the thermodynamic limit. We identify the general mechanism responsible for freezing, related to the roughness of the Gibbs weight in the equilibrium measure: some modifications of the Hamiltonian can change the structure of the landscape, allowing the emergence of clusters even at the typical level. Then, in Sec. IV, considering again the standard error-counting loss function, we move to the study of atypical dense regions of solutions. At zero temperature, these exist for constraint densities α smaller than a threshold αOGP , and are algorithmically reachable (up to a small gap) [2]. We show that the onset of the overlap gap property can be followed in temperature: dense flat regions still exist as thermal noise is injected, but they exist up to a threshold αOGP (ϵ) that grows with the allowed energy ϵ. Our approach is based on the replica method [15] and it gives results that are compatible with the previous analytical estimates [7, 16, 17]. We probe the accessibility of the near-optimal clusters numerically, with a message passing algorithm naturally devised to converge towards finite-energy flat regions in the energy landscape, even beyond the zero-temperature OGP threshold. Finally, in Sec. V, we focus on the teacher-student setting and test the generalization performance of the finite-energy wide clusters, showing that the thermal noise in training error does not obstruct learning. On the contrary: beyond the zero-temperature OGP threshold, restricting the search to exact-fit configurations can create an algorithmic obstruction, whereas accessible finite-error dense regions may still generalize well. This suggests that it is beneficial to shape optimization algorithms to search for wide regions rather than isolated global minima, even when the former carry finite energy. II.
MODELS AND FINITE-TEMPERATURE ENSEMBLES
We consider a class of binary perceptrons models having with N Ising weights w ∈ {−1, +1}N , trained on datasets comprising P = αN random patterns divided into two classes. The input vectors have independent standard Gaussian entries, xµi ∼ N (0, 1), and we denote by N
1 X hµ (w) = √ wi xµi N i=1
(1)
the local field associated with the pattern µ. The quantity sµ (w) = y µ hµ (w),
(2)
is the stability of the input xµ , where y µ = ±1 is the binary label associated to the input pattern. In the case of the asymmetric binary perceptron (ABP), the perceptron is said to classify the pattern xµ correctly whenever sµ (w) > 0. We will call w a solution of the ABP problem if sµ (w) > 0 for any µ ∈ [P ]. In the following we shall consider two classical ways of generating the labels. In the storage setting the labels y µ = ±1 are independent Rademacher random variables. Since the distribution of the patterns is symmetric, the labels can then be gauged away and one may set y µ = 1 for all µ without loss of generality. In this setting, one can focus on the optimization task, by which we mean finding student configurations w that achieve zero training error, at constraint density α. In the teacher-student problem, instead, the labels are generated by a planted binary teacher w⋆ ∈ {−1, +1}N via ! N X 1 µ y µ = sign √ wi⋆ xi . (3) N i=1 In the teacher-student setting, our main focus will be again the optimization task. This has to be distinguished from the inference task, where one is interested in inferring the planted signal [18, 19]. The teacher-student setting also allows to PN study the generalization capability of the network. In particular, the teacher-student overlap r(w, w⋆ ) = N1 i=1 wi wi⋆ determines the generalization error of the student through ϵg (r) =
1 arccos r, π
(4)
which is the probability that the student and the teacher disagree on a previously unseen Gaussian input. Both the storage and teacher-student settings have been studied extensively in the statistical mechanics literature, see [1, 8, 11, 13, 18–22].
3 While our main focus is the optimization problem, it is also useful to consider configurations with a finite training error. To this end, we introduce a Gibbs measure over the weight configurations, where each pattern contributes through a single-pattern Boltzmann factor K. The Gibbs partition function is X
ZD (β) =
αN Y
K (sµ (w)) ,
(5)
w∈{±1}N µ=1
where the dependence on the inverse temperature (β) is encoded in K. In the zero-temperature limit, suitable choices of K recover the hard-constraint optimization problem discussed above. The quenched free entropy density associated to the partition function is: 1 ED log ZD (β). N →∞ N
ϕ(β) = lim
The model we will focus on in this paper is the ABP, with single Gibbs weight given by KABP (s) = e−βΘ(−s) = e−β + 1 − e−β Θ(s).
(6)
(7)
In the zero-temperature limit, the measure is uniform on zero-error solutions whenever such solutions exist, while at positive temperature it also assigns weight e−β to each violated constraint. Equivalently, this corresponds to weighting configurations w according to a Gibbs distribution having as energy a loss function LD ZD (β) =
X
e
−βLD (w)
,
LD (w) =
w
αN X
Θ (−sµ (w)) .
(8)
µ=1
which counts the number of misclassified training patterns. The same formalism is generic and can be used also to study other models. For example, similar results that we will present for the ABP will be valid for the symmetric binary perceptron (SBP) [7, 12] as well and will be discussed in the appendices. In the SBP with margin κ > 0 the labels play no role and the constraint requires the local field to lie inside a window of width 2κ: |sµ (w)| = |hµ (w)| ≤ κ. The single-pattern Gibbs weight corresponding to an error counting loss function is therefore KSBP (s) = e−βΘ(|s|−κ) = e−β + 1 − e−β Θ(κ − |s|).
(9)
(10)
Other choices of K may impose the same hard constraint in the limit β → ∞, but they can lead to different finitetemperature physics. This point is central for the discussion of the next section. The free entropy in equation (6) can be computed using the replica method [15]. The derivations using a ReplicaSymmetric (RS) or a 1-step Replica Symmetry Breaking (1RSB) Ansatz are standard in the statistical physics literature and the detailed derivations are reported for convenience of the reader in Appendix A. III.
DYNAMICAL TEMPERATURE AND FREEZING
At zero temperature the equilibrium measure of the ABP and SBP equipped, respectively, with the Gibbs weight (7) and (10) is known to be described by a frozen one-step replica-symmetry-breaking (1RSB) structure [12, 13, 23– 25]. In this picture the Gibbs measure decomposes into exponentially many clusters which are separated by extensive Hamming distances, while each individual cluster is point-like. In replica notation this means that the intra-state overlap between pairs of solutions is q1 = 1,
(11)
whereas the inter-state overlap q0 remains strictly smaller than q1 . In the SBP, the symmetry w 7→ −w further implies q0 = 0, i.e. the point-like clusters are orthogonal. A natural question is whether this frozen structure is exclusively a zero-temperature property, or whether it persists when positive training error configurations are assigned finite Gibbs weight. More generally, we ask how this equilibrium picture depends on the specific choice of the finite-temperature single-pattern Gibbs weight K. We can answer those questions by computing the so-called dynamical temperature Td . This is defined as the largest temperature
4 below which the 1RSB saddle-point equations admit a non-trivial solution with the Parisi block parameter m = 1 and q1 > q0 [26]. If, in addition, one has q1 = 1, then for T < Td the corresponding 1RSB phase is frozen. For the error-counting single-pattern weights KABP and KSBP , the computation reported in Appendix B shows that, for every fixed α > 0 and every inverse temperature β > 0, the m = 1 1RSB equations admit a non-trivial frozen solution. Therefore, the dynamical temperature diverges in the thermodynamic limit. In other words, the equilibrium measure is dynamically glassy at every finite temperature. This result is in agreement with what Horner found for the ABP in the storage setting using dynamical field theory techniques [14]. At finite N , the singular solution q1 = 1 is rounded by the discreteness of the configuration space. Using the natural finite-size cutoff 1 − q1 ≃
1 , N
(12)
one obtains the scaling with N of the dynamical temperature (B14): N 1/4 . Td ≃ √ log N
(13)
The mechanism leading to this result is quite general, and clarifies which features of the finite-temperature Gibbs weight are responsible for freezing. As detailed in Appendix B 2, the 1RSB saddle point equations involve the function Z (14) H(x, y) = Dz K(x + yz) , √ 2 where Dz = √dz e−z /2 and y = 1 − q1 . The limit q1 → 1 therefore corresponds to the limit y → 0. Possible 2π singularities in this limit can only come from the decision boundaries, namely from the points where the zerotemperature constraint changes value and where K may be non-smooth. We denote such a boundary by b. For example, in the ABP one has b = 0, while in the SBP with margin κ the boundaries are b = ±κ. A crucial quantity controlling the onset of freezing is the boundary layer term 2
Z BK (b, y) ≡ y
du
[∂x H(b + yu, y)] . H(b + yu, y)
(15)
In particular, if BK (b, y) → ∞
as
y → 0,
(16)
we argue in Appendix B 2 that the solution space is frozen. Conversely, if BK (b, y) remains finite, or vanishes, as y → 0, then the frozen phase is absent. In that case a non-trivial 1RSB solution with q1 < 1 may still appear, which does not describe point-like clusters. We illustrate below such criterion on three types of single-pattern weights K shown in Fig. 1 that have been considered in the literature. 1. Jump discontinuity. Consider a single pattern Gibbs weight that has a jump discontinuity at the decision boundary. KABP and KSBP given in (7) and (10) fall in this class: for any β > 0, they are discontinuous at the decision boundary, namely at the origin for the ABP and at ±κ for the SBP. As we show in B 2, this is responsible for the divergence of BK when y → 0 BK (b, y) ≃
C(β) , y
(17)
where C(β) is a positive constant for every β > 0, and vanishes only at β = 0. This is the reason why the frozen solution dominates the Gibbs measure at all finite temperatures. 2. Horner’s weight. A different finite-temperature continuation has been considered first by Horner [14] and more recently in [27] in the case of the ABP. This is obtained by replacing the error-counting loss by a soft penalty for violated constraints γ
K(s) = e−β(−s) Θ(−s) ;
(18)
see the left panel of Figure 1 for a plot. We are considering here for simplicity the case of the ABP, but the considerations we are making can be extended to any model. Note that for γ = 0 equation (18) reduces to the
5 (s)
(s)
3.0
1.0 γ=0
2.5
γ = 0.5
0.8
2.0
γ=1 0.6
γ=2 1.5 γ=0
0.4
γ = 0.5
1.0
γ=1 0.2
-2
γ=2
0.5
s
-1
1
2
-2
-1
s 1
2
γ
Figure 1. Plot of the single pattern Gibbs weight. Left: K(s) = e−β(−s) Θ(−s) for β = 2 and γ = 0, 0.5, 1, 2. This form of the single pattern weight has been in considered by Horner [14] for integer values of γ. Right: K(s) = sγ Θ(s) considered in [28] for the same values of γ as in the left panel. In both the left and right plot, K has a jump discontinuity at the decision boundary b = 0 for γ = 0, which induces freezing. In left plot the discontinuity is recovered also in the large β limit.
error-counting weight in (7), so we should expect freezing. For γ > 0 and β < ∞, the Gibbs weight (18) is instead continuous at the decision boundary. In this case the boundary layer term scales as BK (b, y) ∼ y 2γ−1 .
(19)
when y → 0. Hence freezing is expected when γ < 1/2, while for γ > 1/2 the boundary layer is not singular enough to produce a frozen solution. A dynamical transition to a non-frozen phase may still be present at a finite temperature (and indeed it occurs, see [14]). Finally, since in the limit β → ∞ one has K(s) → Θ(s), the frozen solution is restored at zero temperature. 3. Logarithmic potential. Another class consists of Gibbs weights that vanish as a power law when the decision boundary is approached from within the feasible region. For example, consider: K(s) = sγ Θ(s)
(20)
This should be distinguished from the soft-penalty form in Eq. (18), which smooths the cost of violated constraints. Here, instead, the weight suppresses configurations that satisfy the constraint only marginally, assigning larger weight to configurations deeper inside the feasible region. Equivalently, this choice induces, within the feasible region, a logarithmic potential V (s) = − log K(s) = −γ log s, which penalizes small positive stabilities and favors configurations farther from the decision boundary [28]. In this case one can show that the boundary layer term BK behaves as BK (b, y) ∼ y γ−1 .
(21)
Therefore the frozen solution is expected for γ < 1, while it is absent for γ > 1. This picture has also been observed in [28] using a Franz-Parisi potential approach.
IV.
THE OVERLAP GAP PROPERTY
The frozen equilibrium picture described in the previous section does not by itself imply that the problem of finding configurations w with a given energy level is algorithmically hard. The reason is that efficient algorithms do not need to sample from the equilibrium Gibbs measure. They may instead operate out of equilibrium, following atypical trajectories in configuration space and exploiting regions that are exponentially subdominant in the equilibrium measure. This distinction is particularly important in the case of the binary perceptron with error counting loss (7) which, as pointed out in the previous section, has a frozen landscape at any finite temperature and positive constraint density. In the past decade, the statistical-physics literature has shown that message-passing algorithms, especially when combined with reinforcement or with local-entropy biases, can efficiently find solutions and improve the algorithmic
6 thresholds of many different constraint satisfaction problems, ranging from the K-SAT and perceptron model [29–31], to the graph coloring problem [32–34]. In [1] it has been conjectured that algorithmic success is associated with the existence of dense regions of solutions which, despite being rare and invisible to the equilibrium measure, are basins of attraction much larger than typical equilibrium states. A recent theoretical explanation for this effectiveness was that imposing local entropy biases could delay the dynamical transition [33, 34], with random hypergraph bicoloring constituting a notable exception [35]. This physical picture has recently been reformulated, in the mathematical literature, through the framework of the overlap gap property (OGP). OGP is a geometric obstruction in the space of near-optimal configurations. Such a topological obstruction has been used to explain algorithmic barriers in random optimization problems [6] and, more recently, in perceptron-type models [4, 7, 36]. Informally, m-OGP holds when relevant m-tuples of configurations, organize into separated regions: they can be mutually close or mutually far, but there is an entire interval of intermediate overlaps in which no such configurations can be found. This gap provides an obstruction to broad classes of so-called stable algorithms, namely algorithms whose outputs remain close, with high probability and under a common random seed, when applied to sufficiently close or correlated instances of the random problem. Here we study the OGP by considering m real replicas, or clones, of the system constrained to have fixed mutual overlap. We limit ourselves here for simplicity to the ABP with the error counting loss (7) but the technical derivations presented in Appendix A 2 are general. For m ≥ 2 and q1 ∈ [−1, 1] the cloned partition function is defined as ! m N X Y Y 1 X a b −βLD (wa ) e Zm,D (q1 ; β) = δ q1 − w w . (22) N i=1 i i a m a=1 {w }a=1
1≤a<b≤m
The corresponding quenched free entropy per clone is ϕm (q1 ; β) = lim
1
N →∞ N m
(23)
ED ln Zm,D (q1 ; β).
This quantity can be computed with the replica method. At the RS level, the result can be found simply by imposing a 1RSB structure on the equilibrium measure (8) and treating both m and q1 as external parameters rather than variational ones [37, 38], see Appendix A 2. At zero temperature, Zm,D (q1 ; ∞) counts m-tuples of solutions at mutual overlap q1 . Thus, if for α larger than a certain threshold αm (q1 ) one has (24)
ϕm (q1 ; ∞) < 0,
then with high probability no such m-tuple exists. The onset of the m-OGP threshold is therefore obtained by finding the minimal value of the constraint density α for which a forbidden interval of overlaps (24) starts being non-empty: (25)
αOGP (m) = min αm (q1 ) q1
This threshold can be determined equivalently by the conditions [36] (26a) (26b)
ϕm (q1 ; ∞) = 0, ∂q1 ϕm (q1 ; ∞) = 0.
At finite temperature the cloned partition function no longer counts configurations of zero training error. Rather, it weights configurations proportionally to their Boltzmann weight, at inverse temperature β. The entropy sm (q1 ; β), i.e. the log-number of configurations that dominate the measure, can be found by a Legendre transform of the free entropy: (27)
sm (q1 ; β) = ϕm (q1 ; β) + βαϵm (q1 ; β) , where 1 ∂ϕm (q1 ; β) ϵm (q1 ; β) = − = ED α ∂β
*
m 1 X LD (wa ) αN m a=1
+ (28) D
represents the average training error per pattern of the m clones sampled from the constrained Gibbs measure induced by (22). The finite-temperature OGP threshold is therefore defined by the solution of the system of equations sm (q1 ; β) = 0, ∂q1 sm (q1 ; β) = 0.
(29a) (29b)
7
0.0100 0.0075 0.0050 0.0025 0.0000
0.08
1.22
0.96
0.97
0.98
0.99
1.00
0.04
OGP
entropy s(q1)
0.06
1.24
0.02 0.00 0.02 0.60
1.18
= 1.15 = 1.18 = 1.19 = 1.2 = 1.25 0.65
1.20
= 3.5 = 4.0 = 5.0 = 10.0
1.16 0.70
0.75
0.80 overlap q1
0.85
0.90
0.95
1.00
2
3
4
5
6 m
7
8
9
10
Figure 2. Emergence of the OGP at finite temperature in the ABP, teacher-student setting. The left panel depicts the entropy sm (q1 ; β) for m = 2 and β = 5.0, versus the overlap between the two clones q1 . For these values of m and β, the OGP threshold is αOGP ≃ 1.950 and q1OGP ≃ 0.988. Notice how, for α > αOGP , there is an entire interval of q1 ’s for which the entropy is negative, meaning that, with high probability at large N , couples of configurations satisfying the energy constraint exists at either small or very large overlaps, with an entirely forbidden interval of intermediate Hamming distances. The inset shows a zoom of the large q1 region. Right: αOGP vs m, for different values of β. The change in monotonicity that occurs at large m is unphysical, and conjectured to be due to the RS Ansatz for the computation of the quenched free entropy; however, at higher temperatures the change of slope becomes progressively weaker.
0.006
training error m
0.005
Temperature T
0.007
0.004
1.2
1.3
1.4
0.8 0.6 0.4 0.2 0.0
0.003 0.002 0.001 0.000 1.150
m=2 m=3 m=4 1.175
1.200
1.225
1.250 1.275 constraint density
1.300
1.325
1.350
Figure 3. OGP thresholds in the training error vs α plane. For each training error, the Overlap Gap Property holds for α > minm αOGP (m). The inset plot shows the same OGP thresholds but in the α − T plane.
The left panel of Figure 2 shows the entropy sm (q1 ; β) for m = 2 and a positive temperature, as a function of the overlap between pairs of solutions q1 , for different values of α. The entropy is a non-monotonic function of q1 . As α is increased, the entropy curves shift downward. The OGP threshold is identified as the smallest value of α at which a forbidden interval of overlaps appears, namely when the minimum of the entropy curve as a function of q1 first touches zero. The right panel of Figure 2 shows αOGP as a function of m. For all the values of β we have plotted, αOGP (m) is a non-monotonic function of m. The OGP threshold αOGP (m), is however expected to be a non-increasing function of m. Indeed, if for a given value of α there exist m configurations w1 , . . . , wm satisfying the prescribed single-replica energy constraint and the required pairwise overlap constraints, then any subset of m′ < m among them automatically satisfies the same conditions. Hence the existence of an admissible m-tuple implies the existence of an admissible m′ -tuple if m′ < m. Consequently, increasing m can only make the constrained replicated problem in (22) harder to satisfy, and the OGP threshold is expected to be non-increasing: αOGP (m) ≤ αOGP (m′ )
for
m′ < m .
(30)
8 The non-monotonic dependence on m observed in the RS computation is therefore unphysical, and should be interpreted as an artefact of the RS Ansatz for the replicated constrained problem. The same phenomenon was already observed at zero temperature for both the ABP, SBP and in related models [7, 36, 39]. At finite temperature the artefact persists, but it becomes progressively less pronounced. More precisely, let m⋆ = argmin αOGP (m) m
(31)
denote the value of m beyond which the RS estimate of the OGP threshold starts increasing. We observe that m⋆ shifts to larger values as the temperature is increased, indicating that the onset of the unphysical non-monotone regime is delayed. Some additional figures for the SBP showing a similar phenomenology are reported in Appendix A 2. Notice that the corresponding constrained density threshold αOGP = min αOGP (m) m
(32)
is an upper bound to the appearance of an overlap gapped phase. Determining the exact value of the OGP threshold requires a more refined replica ansatz capable of eliminating the unphysical non-monotonic dependence of αOGP (m) on m. Figure 3 summarizes the finite-temperature OGP threshold in the ABP, in the teacher-student setting. The plot shows, as a function of the constraint density α, the training error ϵm at which the OGP first appears for several values of m. Equivalently, the curve separates, for any value of α, a large training error region, which it is expected to be algorithmically accessible, from a low training error region, where we expect algorithmic hardness because of the presence of an overlap gap. In the right panel of Figure 4 we show similar OGP curves in the storage case. In the limit ϵ → 0 (or correspondingly β → ∞), we find in the teacher-student setting αOGP ≃ 1.154, that is the zero-temperature threshold previously found in [1]. In the storage setting we similarly find αOGP ≃ 0.784 [36] which is compatible to the results found in [1, 22] using different approaches. Algorithm 1 Fixed-temperature reinforced AMP targ Input: patterns {xµ , y µ }P , reinforcement parameter ρ, maximum µ=1 , inverse temperature β, target training error ϵ number of iterations tmax . Initialize: AMP local fields ht=0 ∈ RN , marginal magnetization at=0 ∈ RN , energetic channel g t=0 ∈ RP , initial reinforcement ρ0 = 0, and wbest ← sign(a0 ). for t = 1, . . . , tmax do Perform one rAMP update: (ht , at , g t ) ← rAMPstep ht−1 , at−1 , g t−1 ; ρt−1 , β . See Algorithm 2 for the explicit update. (33)
Update the reinforcement: ρt ← 1 − (1 − ρ)t .
(34)
wt ← sign(at ).
(35)
Construct the binary estimator: t
if ϵ(w ) < ϵ(wbest ) then wbest ← wt . end if if ϵ(wt ) ≤ ϵtarg then return success, wt . end if end for return failure, wbest .
A.
Numerical simulations
We now compare the finite-temperature OGP thresholds with the performance of an explicit algorithmic search for low-energy configurations. For a given value of the constraint density α = P/N , we look for binary configurations with empirical training error ϵ(w) =
P 1 X yµ Θ − √ w · xµ P µ=1 N
(36)
1.0
0.025
0.8
0.020
0.6
0.015
training error
success probability
9
0.4 0.2 0.0
targ = 0.0 targ = 0.005 targ = 0.01 targ = 0.015 targ = 0.02 targ = 0.025
0.70
0.010 0.005
m=2 m=3 m=4 rAMP
0.000 0.75
0.80 0.85 constraint density
0.90
0.95
0.75
0.80
0.85 0.90 constraint density
0.95
1.00
Figure 4. OGP vs rAMP algorithm in the ABP, storage setting. Left panel: probability of finding a configuration with target training error ϵtarg vs α using the rAMP algorithm at fixed temperature as given in 1. Here we have used N = 8000 and we have averaged the results over 60 samples. The dashed lines represent sigmoidal fits to the data. Right panel: phase diagram. The red points represent the performance achieved by rAMP at finite temperature and for N = 8000 and averaged over 60 samples. For each point we have optimized the reinforcement parameter ρ and the inverse temperature β in order to achieve the highest value of the constraint density possible. The green, blue, and yellow curves denote the boundaries marking the presence of m-OGP for m = 2, 3, and 4, respectively.
smaller than a prescribed threshold ϵtarg . Our starting point is Approximate Message Passing (AMP) applied to the finite-temperature Gibbs measure. At fixed inverse temperature β, AMP gives an estimate to the one-site marginal magnetizations ai = ⟨wi ⟩β ,
(37)
where ⟨•⟩β denotes the average over the Gibbs measure at finite temperature. Equivalently, it computes the local fields hi such that ai = tanh hi . A binary candidate configuration is then obtained by w⋆ = sign(a).
(38)
However, the standard AMP algorithm does not necessarily produce strongly polarized magnetizations ai . This implies that the binary estimator in equation (38) may not correspond to a low-error configuration. To turn the AMP marginals into an actual binary assignment with low training error, we use the reinforced AMP (rAMP) algorithm [29, 30]. The idea of reinforcement is to add a self-aligning contribution to the AMP field update, which progressively polarizes the local fields and drives the magnetizations ai towards the vertices of the hypercube. More precisely, if hti,AMP denotes the usual AMP update at iteration t (see equation (C3d) in the Appendix for its expression), we replace it by adding a memory term ρt−1 ht−1 : i hti = hti,AMP + ρt−1 ht−1 . i
(39)
Usually the reinforcement strength ρt is set to zero at time t = 0 and increased during the dynamics. We have used a schedule of the type ρt = 1 − (1 − ρ)t ,
(40)
where ρ controls the rate at which reinforcement is switched on. If ρ = 0 one has ρt = 0 for all t, and the algorithm reduces to standard AMP. The complete procedure is summarized in Algorithm 1, and detailed in Appendix C. At each iteration we perform one rAMP update at the current value of β, construct the binary estimator wt = sign(at ), and measure its training error. The run is declared successful if ϵ(wt ) ≤ ϵtarg before the maximal number of iterations is reached. We also record the smallest training error encountered along the trajectory. The left panel of Figure 4 shows the empirical success probability as a function of α for several values of the target training error, in the storage setting and for N = 8000. For each ϵtarg , the success probability has a sharp drop as α is increased. As expected, allowing a larger training error shifts this algorithmic transition to larger values of α: low-energy states with positive error remain accessible in a range of densities where exact solutions are no
10 0.28 0.27 0.26
0.35 generalization error
generalization error
0.40
m=2.0, =1.3 T=0.0 T=0.2 T=0.3 T=0.4
0.25
=1.3 typical 1RSB m=3.0 q1=0.98 bayes
0.30
0.25
0.24 0.20
0.23 0.65
0.70
0.75
0.80 0.85 overlap q1
0.90
0.95
1.00
0.15 0.0
0.2
0.4
temperature T
0.6
0.8
1.0
Figure 5. Left panel: generalization of a clone drawn from the constrained measure with m = 2 (22) versus the mutual clone overlap q1 , for several values of the inverse temperature β. Here we set α = 1.3, corresponding to a constraint density in the hard region; the qualitative behavior, however, is unchanged for other values of α. The plot shows that for each inverse temperature there exists an overlap q1⋆ with minimal generalization error. Right panel: the red line represents the generalization of a clone drawn from the constrained measure with m = 3 and q1 = 0.98 versus the temperature. We also display the typical generalization error (blue curve, obtained from the uncloned Gibbs measure (8)) and the Bayesian generalization error (green) for comparison. In both panels, the dashed segments of the curves correspond to unphysical branches with negative entropy.
longer found by the algorithm. For each target training error the algorithmic transition can be estimated by fitting the data to a sigmoid and finding the point where the success probability is 1/2. In the right panel of Fig. 4 we summarize the same data in a phase diagram. The red points show the best rAMP algorithmic threshold for each considered target training error ϵtarg . Those points have been obtained by tuning the rAMP hyperparameters, namely the reinforcement ρ and the inverse temperature β, see Appendix C for additional details. When ϵtarg = 0, we set β = ∞ and the procedure reduces to the standard zero temperature rAMP algorithm [29]. Those points are to be compared to the OGP thresholds which we present for m = 2, 3 and 4. The rAMP algorithm qualitatively follows the trend of the OGP thresholds.
V.
FOLLOWING WIDE MINIMA IN TEMPERATURE IN THE TEACHER–STUDENT FRAMEWORK
We now turn to the teacher–student setting and investigate the generalization properties of finite-energy configurations that can be targeted by algorithms. As shown in the previous section, the wide and flat region of zero training error solutions fractures once α exceeds αOGP ≃ 1.154 due to the presence of OGP in the space of solutions. Nevertheless, robust dense configurations continue to exist at positive training error and may, in principle, be targeted by algorithms operating at finite temperature. In this section, we study the question of whether those regions at finite training error retain good generalization properties. We first show analytical evidence that such configurations have rather good generalization and then provide numerical evidence that these regions are also algorithmically accessible. Our analytical approach is based on a comparison between two classes of estimators. The first consists of typical students sampled from the Gibbs measure in Eq. (8). As discussed above, this measure is dominated by isolated frozen configurations, which may have a nonzero overlap with the teacher but are not expected to be efficiently accessible to stable algorithms. The second class is obtained from the constrained m-clone measure introduced in Eq. (22), in which m students are constrained to have mutual overlap q1 . By forcing several configurations to remain close to one another, this measure favors regions with large local entropy and therefore provides a proxy for wide and flat portions of the landscape. The left panel of Figure 5 shows the generalization error of a clone drawn from the constrained measure as a function of the imposed mutual overlap q1 . At fixed α and β, the dependence on q1 is non-monotonic. For small q1 , the clones are too far apart to identify a coherent local structure, whereas the limit q1 → 1 approaches an isolated configuration. Between these two limits, the generalization error reaches a minimum at an optimal overlap q1⋆ . The same analysis can be repeated at finite temperature. Increasing the temperature generally worsens generalization, as expected, but the degradation is gradual. Wide regions can therefore be continuously followed from zero to positive temperature while retaining a generalization error substantially smaller than that of typical configurations. Searching for robust configurations with low, but nonzero, training error therefore does not immediately compromise their alignment with the teacher. This behavior is shown more directly in the right panel of Fig. 5, where we compare
11
(B)
(C)
training error
(A)
w*
w*
configuration space
0.5
w*
configuration space
EASY (OPTIMIZATION)
configuration space
EASY (INFERENCE)
HARD
generalization error
0.4
0.3
0.2
0.1
0.0 0.0
typical 1RSB m=3.0 q1=0.9 bayesian zeroT rAMP temperature rAMP 0.2
0.4
(A) 0.6
(B) 0.8 1.0 constraint density
OGP
(C) IT
1.4
(D) AMP
1.6
1.8
Figure 6. Schematic phase diagram of the binary teacher–student perceptron. The upper panels illustrate the structure of the training error landscape in the different regimes, while the lower panel shows the corresponding generalization error as a function of the constraint density α. For α < αOGP ≃ 1.154, a wide minimum of zero-training error solutions distinct from the teacher w⋆ coexists with smaller, isolated clusters of solutions. The wide minimum is easily accessible to local algorithms (such as the zero temperature rAMP [29], black stars in the bottom panel), whereas the isolated clusters are not. This makes the task of optimization, i.e. of finding a zero training error configuration easy (phase A in the diagram). Nevertheless, exact inference remains information-theoretically impossible below αIT ≃ 1.249. For α > αOGP , the wide minimum moves to positive training error and therefore no longer contains solutions. In the regime αOGP < α < αIT (phase B), zero-training error configurations distinct from the teacher survive only in isolated clusters separated by an overlap gap and are thus inaccessible to stable algorithms. For αIT < α < αAMP ≃ 1.492 (phase C), the only zero-training error configuration is the teacher, which nevertheless remains algorithmically inaccessible. However, the wide minimum of configurations at positive training error can still be targeted by the finite temperature rAMP algorithm described in 1 (fuchsia stars) and retain good generalization capabilities. Finally, for α > αAMP (phase D), the teacher can be efficiently recovered. We also show in the bottom panel the generalization error of typical (isolated) solutions (blue), of a clone drawn from the constrained measure (22) with m = 3 and q1 = 0.9 (red). The green curve represents the Bayesian error i.e. the error of the barycenter over all typical solutions. The dashed parts of the curves correspond to an unphysical negative entropy.
the optimal generalization error of the constrained clones with that of a typical Gibbs configuration and with the Bayesian estimator associated with the barycenter of the Gibbs measure. Over the temperature range shown, the constrained-clone estimator continues to outperform a typical isolated configuration. We now place this result in the phase diagram of the binary teacher–student perceptron and examine whether these informative wide regions are also algorithmically accessible. Figure 6 summarizes the resulting picture. For α < αOGP ≃ 1.154, a wide minimum containing zero-training error configurations coexists with smaller, isolated clusters. The wide minimum is accessible to local algorithms, whereas the isolated clusters are not. Once α exceeds αOGP , the wide minimum moves to positive training error. In the interval αOGP < α < αIT ≃ 1.249, exact solutions distinct from the teacher survive only in isolated clusters separated by an overlap gap. For αIT < α < αAMP ≃ 1.492, the teacher is the only zero-training error configuration in the large N limit, but it remains inaccessible to stable algorithms. Nevertheless, the finite-training error continuation of the wide minimum persists throughout this hard
12 region. The finite-temperature rAMP algorithm introduced in the previous section is able to target this positive-energy wide region, as shown by the fuchsia symbols in Fig. 6. The figure therefore combines two complementary conclusions: the analytical calculation of Figure 5 shows that wide finite-energy configurations retain favorable generalization properties, while the numerical results of Fig. 6 show that such configurations can be reached algorithmically beyond the zero-temperature OGP threshold. Finally, for α > αAMP , the teacher itself becomes efficiently recoverable. Finite temperature thus plays a dual role. It relaxes the exact-fitting constraint and restores access to a wide basin in the hard phase, while preserving much of the statistical information carried by the corresponding zero-temperature dense region.
VI.
CONCLUSIONS
We studied the finite-temperature geometry of the solution space of binary perceptron models, extending the zerotemperature picture of frozen 1RSB structure and the overlap gap property to the regime where imperfect classification is allowed and statistically weighted. We found that the equilibrium measure remains dynamically frozen at every finite temperature, and traced this to a discontinuity of the single-pattern Gibbs weight at the decision boundary. Smoothing the Gibbs weight, as in Horner’s construction [14], removes the frozen solution at any positive temperature, while using the log-potential on constraints satisfied with high margin, as in [28], removes freezing down to zero temperature. At the level of atypical dense regions, we showed that the OGP threshold can be continuously followed in temperature, growing as αOGP (T ), consistent with the intuition that tolerating errors makes room for more constraints - a trend qualitatively reproduced by a finite-temperature message-passing algorithm. In the teacher-student setting, these finite-energy dense regions remain informative about the planted signal, and thermal noise extends the range of constraint densities over which good generalization is algorithmically achievable, even when exact recovery of the teacher is information theoretically impossible. An open question for future work is whether these finite-temperature wide minima are responsible for the information-theoretic hardness of exact inference in the regime αIT < α < αAMP . It also remains to be understood whether, for α > αAMP , the teacher becomes embedded within such wide finite-energy minima, thereby explaining the empirical success of replicated or annealed search strategies. Acknowledgements. We thank Gianmarco Perrupato for interesting discussions.
[1] C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, and R. Zecchina, Phys. Rev. Lett. 115, 128101 (2015). [2] C. Baldassi, C. Borgs, J. T. Chayes, A. Ingrosso, C. Lucibello, L. Saglietti, and R. Zecchina, Proceedings of the National Academy of Sciences 113, E7655 (2016), https://www.pnas.org/doi/pdf/10.1073/pnas.1608103113. [3] P. Chaudhari, A. Choromanska, S. Soatto, Y. LeCun, C. Baldassi, C. Borgs, J. Chayes, L. Sagun, and R. Zecchina, Journal of Statistical Mechanics: Theory and Experiment 2019, 124018 (2019). [4] D. Gamarnik, Proceedings of the National Academy of Sciences (2021), 10.1073/pnas.2108492118. [5] D. Gamarnik and A. Jagannath, The Annals of Probability 49, pp. 180 (2021). [6] D. Gamarnik and M. Sudan, The Annals of Probability 45, 2353 (2017). [7] D. Gamarnik, E. C. Kizildag, W. Perkins, and C. Xu, in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (2022) pp. 576–587. [8] C. Baldassi, E. M. Malatesta, G. Perugini, and R. Zecchina, Phys. Rev. E 108, 024310 (2023). [9] J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, J. Wu, and D. Amodei, ArXiv abs/2001.08361 (2020). [10] J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. de Las Casas, L. A. Hendricks, J. Welbl, A. Clark, T. Hennigan, E. Noland, K. Millican, G. van den Driessche, B. Damoc, A. Guy, S. Osindero, K. Simonyan, E. Elsen, O. Vinyals, J. W. Rae, and L. Sifre, in Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22 (Curran Associates Inc., Red Hook, NY, USA, 2022). [11] W. Krauth and M. Mézard, Journal de Physique (1989), 10.1051/jphys:0198900500200305700. [12] B. Aubin, W. Perkins, and L. Zdeborová, Journal of Physics A: Mathematical and Theoretical 52, 294003 (2019). [13] H. Huang and Y. Kabashima, Physical Review E (2014), 10.1103/physreve.90.052813. [14] H. Horner, Zeitschrift für Physik B Condensed Matter 86, 291 (1992). [15] M. Mézard, G. Parisi, and M. A. Virasoro, Spin glass theory and beyond (World Scientific, Singapore, 1987). [16] M. Stojnic, arXiv preprint arXiv:2601.10628 (2026). [17] M. Stojnic, arXiv preprint arXiv:2604.19712 (2026). [18] G. Györgyi, Phys. Rev. A 41, 7097(R) (1990). [19] E. Gardner and B. Derrida, Journal of Physics A: Mathematical and General 22, 1983 (1989).
13 [20] E. Gardner and B. Derrida, Journal of Physics A: Mathematical and General (1988), 10.1088/0305-4470/21/1/031. [21] M. Opper and D. Haussler, Phys. Rev. Lett. 66, 2677 (1991). [22] C. Baldassi, C. Lauditi, E. M. Malatesta, G. Perugini, and R. Zecchina, Phys. Rev. Lett. 127, 278301 (2021). [23] W. Perkins and C. Xu, Random Structures & Algorithms 64, 856 (2024). [24] D. Barbier, A. El Alaoui, F. Krzakala, and L. Zdeborová, Journal of Physics A: Mathematical and Theoretical 57, 195202 (2024). [25] D. Barbier, SciPost Phys. 18, 115 (2025). [26] T. R. Kirkpatrick and D. Thirumalai, Phys. Rev. Lett. 58, 2091 (1987). [27] G. Catania, A. Decelle, and B. Seoane, Physical Review E (2024), 10.1103/physreve.109.065313. [28] D. Straziota, E. Demyanenko, C. Baldassi, and C. Lucibello, in Advances in Neural Information Processing Systems, Vol. 38, edited by D. Belgrave, C. Zhang, H. Lin, R. Pascanu, P. Koniusz, M. Ghassemi, and N. Chen (Curran Associates, Inc., 2025) pp. 111927–111966. [29] A. Braunstein and R. Zecchina, Physical Review Letters 96 (2006), 10.1103/physrevlett.96.030201. [30] C. Baldassi and A. Braunstein, Journal of Statistical Mechanics: Theory and Experiment 2015 (2015), 10.1088/17425468/2015/08/p08008. [31] D. Barbier, arXiv preprint arXiv:2505.20954 (2025). [32] M. C. Angelini and F. Ricci-Tersenghi, Phys. Rev. X 13, 021011 (2023). [33] L. Budzynski, F. Ricci-Tersenghi, and G. Semerjian, Journal of Statistical Mechanics: Theory and Experiment 2019, 023302 (2019). [34] L. Budzynski and G. Semerjian, Journal of Statistical Mechanics: Theory and Experiment 2020, 103406 (2020). [35] M. C. Angelini, L. Budzynski, and F. Ricci-Tersenghi, Phys. Rev. E 112, 064117 (2025). [36] M. Benedetti, A. Bogdanov, E. M. Malatesta, M. Mézard, G. Perrupato, A. Rosen, N. I. Schwartzbach, and R. Zecchina, Journal of Statistical Mechanics: Theory and Experiment 2025, 123303 (2025). [37] R. Monasson, Phys. Rev. Lett. 75, 2847 (1995). [38] C. Baldassi, F. Pittorino, and R. Zecchina, Proceedings of the National Academy of Sciences 117, 161 (2020), https://www.pnas.org/doi/pdf/10.1073/pnas.1908636117. [39] M. Benedetti, A. Bogdanov, E. M. Malatesta, M. Mézard, G. Perrupato, A. Rosen, N. I. Schwartzbach, and R. Zecchina, Phys. Rev. X 16, 021051 (2026). [40] E. M. Malatesta, arXiv preprint arXiv:2309.09240 (2023). [41] G. Parisi, Physics Letters A 73, 203 (1979). [42] R. Monasson, Phys. Rev. Lett. 75, 2847 (1995). [43] M. Mézard and A. Montanari, Information, Physics, and Computation (Oxford University Press, 2009).
APPENDICES
Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A The free entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 RS Ansatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1RSB Ansatz and entropy of the m-cloned system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B Computation of the dynamical temperature. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 The frozen 1RSB solution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 General criterion for freezing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C Detail of the message passing algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Approximate Message Passing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 AMP + reinforcement (rAMP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D Additional figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13 13 14 15 17 18 20 22 22 24 25
Appendix A: The free entropy
The quenched average in the definition of the free entropy in equation (6) of the main text can be performed introducing n virtual replicas of the system and using the replica trick: n ⟨ZD ⟩D − 1 . N →∞ n→0 nN
ϕ = lim lim
After standard manipulations, one finds the general expression for the replicated partition function: Z Y Y n ⟨ZD ⟩D = dqab dq̂ab dra dr̂a eN S(q,q̂,r,r̂) , a<b
a
(A1)
(A2)
14 where qab and ra physically represent the student-student overlap matrix and the teacher-student overlap – when a teacher is present, ra > 0, see Table I – respectively [40]. The function S is decomposed into an entropic GS and an energetic term GE as: S(q, q̂, r, r̂) = GS (q, q̂, r, r̂) + αGE (q, r) , P X X a b P a 1 1X GS (q, q̂, r, r̂) = − qab q̂ab − ra r̂a + ln e 2 a̸=b q̂ab w w + a r̂a w , 2 a a̸=b {wa =±1} Z Y Y P P P 1 ν̂ 2 dua dûa dνdν̂ GE (q, r) = ln K (sign(ν)ua ) ei a ua ûa +iν ν̂− 2 ab qab ûa ûb − 2 −ν̂ a ûa ra . 2π a 2π a
(A3a) (A3b) (A3c)
The free entropy ϕ can be computed by solving the following extremization problem ϕ = lim extrq,q̂,r,r̂ n→0
S(q, q̂, r, r̂) . n
(A4)
Note how the energetic term depends on the generic Gibbs weight K; see Eqs. (7), (10) in the main text. We keep the discussion general, but for clarity of the reader, Table I contains a summary of how to specify the equations for the model considered in this paper (ABP/SBP) and setting (storage/teacher-student). SBP (with margin κ > 0) KSBP r = r̂ = 0
ABP (storage) KABP r = r̂ = 0
ABP (teacher-student) KABP r = r⋆ , r̂ = r̂⋆
Table I. Recipe for each model, to be inserted in Eq. (A3). The single-pattern Gibbs weight for the ABP and SBP models, KABP and KSBP , are defined in Eqs. (7) and (10), respectively.
1.
RS Ansatz
We consider here the standard replica symmetric (RS) assumption on the student overlap matrix and its conjugate qab = δab + (1 − δab )q q̂ab = (1 − δab )q̂ ; moreover we impose for the teacher-student overlaps ra = r r̂a = r̂ . A standard computation gives the free entropy (A4): RS S RS (q, q̂, r, r̂) = GSRS (q, q̂, r, r̂) + αGE (q, r) , Z p q̂ GSRS (q, q̂, r, r̂) = − (1 − q) − r̂r + Dz ln 2 cosh q̂z + r̂ , 2 ! Z √ p rz RS GE (q, r) = 2 Dz H − p ln H qz, 1 − q , q − r2
(A5a) (A5b) (A5c)
where Z H(x, y) =
Dz K(x + yz) .
(A6)
In particular for the ABP and SBP with standard training error loss function one has H(x, y) = e−β + (1 − e−β )H∞ (x, y) ,
(A7a)
15
0.006
0.06
0.010
0.08
0.004
0.005
0.002 0.000
0.04
0.96
0.98
1.00
0.96
0.02
0.02
SBP (m=2) = 1.65 = 1.69 = 1.7 = 1.71 = 1.8
0.02 0.5
0.7
0.8
q1
0.9
0.98
0.99
1.00
ABP (m=4) = 0.75 = 0.77 = 0.78 = 0.79 = 0.81
0.00 0.6
0.97
0.04
(q1)
(q1)
0.94
0.00
0.000
0.06
0.002
1.0
0.5
0.6
0.7
q1
0.8
0.9
1.0
Figure 7. Left panel: SBP: ϕm (q1 ) for κ = 1, m = 2, β → ∞ for different values of α. At α ≃ 1.700, the minimum of the free entropy reaches zero, marking the OGP threshold, see Table II. Right panel: ABP: ϕm (q1 ) for m = 4 and β → ∞. Our OGP threshold estimate for the ABP is αOGP ≃ 0.784, see Figure 8.
where H∞ (x, y) depends on the particular model we consider: ABP H∞ (x, y) = H SBP H∞ (x, y) =
x − y
X s=±1
being H(x) =
R∞ x
Dh = 12 Erfc
izing the function S
RS
x √ 2
sH
(A8a)
,
−sκ + x y
(A8b)
,
. The thermodynamic free entropy is computed at the values of q, q̂, r, r̂ extrem-
: (A9)
ϕRS = extrq,q̂,r,r̂ S RS (q, q̂, r, r̂) . In the SBP the equilibrium value of the overlap is q = q̂ = 0 by symmetry1 .
2.
1RSB Ansatz and entropy of the m-cloned system
A more refined parameterization of the student overlap matrix qab is in general needed to compute the equilibrium value of the free entropy [41]. We consider here a 1-step replica symmetry breaking (1RSB) Ansatz which consists in imposing (n,m)
(n,1)
qab = q0 + (q1 − q0 )Iab + (1 − q1 )Iab ( (n,m) (n,1) q̂0 + (q̂1 − q̂0 )Iab + (1 − q̂1 )Iab q̂ab = 0 (n,m)
(A10a) a ̸= b a=b
(A10b)
where Iab is the (a, b) element of a block matrix of size n × n whose diagonal blocks have size m × m and contain all ones and outside of them the matrix is composed of zeros. We leave unchanged the Ansatz over the teacher-student overlaps.
1 The same argument for the SBP applies for the parameter q
0 in the 1RSB computation.
16
1.90
SBP = 2.5 = 4.0 = 5.0 = inf
1.85
ABP = 3.5 = 4.0 = 5.0 = inf
0.88 0.86
OGP
OGP
1.80 1.75
0.82
1.70 1.65
0.84
0.80
2
3
4
5
6 m
7
8
9
0.78
10
2
3
4
5
6 m
7
8
9
10
Figure 8. αOGP as a function of m for the SBP with κ = 1 and ABP (right panel). At larger temperatures, the curves become less unphysical as the increasing part of the curves become less pronounced. Therefore the RS approximation we made on the on the cloned free entropy in equation (23) becomes less dramatic.
The corresponding free entropy is given by: (A11a)
ϕ1RSB = extrq0 ,q̂0 ,q1 ,q̂1 ,r,r̂,m S 1RSB (q0 , q̂0 , q1 , q̂1 , r, r̂, m) S
1RSB
1RSB = GS1RSB + αGE
Z
Z
(A11b) m p p Dz1 2 cosh q̂0 z0 + q̂1 − q̂0 z1 + r̂ (A11c)
m 1 q̂1 (1 − q1 ) + (q0 q̂0 − q1 q̂1 ) − r̂r + Dz0 ln 2 2 m ! Z Z √ p √ 2 rz0 1RSB GE = q0 z0 + q1 − q0 z1 , 1 − q1 Dz0 H − p ln Dz1 Hm m q0 − r2 GS1RSB = −
(A11d)
where H is defined in (A7a). Note also that this expression can be used to find the entropy density of m-clones of the model constrained to be at a given overlap q1 as in equation (23) [42]. Indeed, notice that in this case the m replicas are “real”, and n virtual replicas of the cloned system are introduced, so that n should be replaced with nm in the previous formulas (A10). Moreover one should not optimize over both m and q1 , as they are treated as external parameters. Mathematically, we have: 1RSB ϕm (q1 ) = extrq0 ,q̂0 ,q̂1 ,r,r̂ GS1RSB + αGE .
(A12)
Figure 7 shows exemplary curves for the SBP and ABP as a function of the overlap q1 . As described in the main text, the m-OGP threshold at zero temperature can be found by solving (26): ϕm (q1 ) = 0 , ∂q1 ϕm (q1 ) = 0 . Similar conditions hold for αOGP threshold at β > 0, see Eqs. (29). Figure 8 shows αOGP as a function of m for the SBP and ABP in the storage setting and for different values of the inverse temperature β. Note that if m′ > m one should have αOGP (m′ ) < αOGP (m), by the very definition of OGP. The increasing part of those curves are therefore clearly nonphysical [36]. It can be verified that such points are also characterized by a negative complexity Σ < 0. We have summarized in table II the OGP threshold we have obtained for the SBP with κ = 1 at zero temperature, and we compare them with the rigorous annealed bound established in [7].
17 m 2 3 4 5
(sbp)
RS estimate of αOGP (m) 1.7001 1.6664 1.6578 1.6593
Annealed bound [7] 1.71 1.667 – –
Table II. OGP threshold for the symmetric binary perceptron with κ = 1: comparison between the RS estimate and the rigorous first moment bounds of Ref. [7]. Our RS estimates of the OGP thresholds are consistent with the ones reported in [16, 17] obtained using another analytical machinery.
Appendix B: Computation of the dynamical temperature
We carry out here the computation of the dynamical temperature Td . The computation is general for both the storage and teacher-student settings. In order to find out Td , we need to expand the 1RSB free entropy functional S 1RSB given in (A11b) around m = 1 [26]. At zeroth order we simply get the RS free entropy (A5), with q = q0 and q̂ = q̂0 . The first order correction is: S 1RSB (q0 , q̂0 , q1 , q̂1 , r, r̂) = S RS (q0 , q̂0 , r, r̂) + (m − 1)ϕ̃(q0 , q̂0 , q1 , q̂1 , r, r̂) + O (m − 1)2 , (B1) where the function ϕ̃ is defined as ϕ̃ =
∂S 1RSB ∂GS ∂GE = +α , ∂m m=1 ∂m m=1 ∂m m=1
(B2)
and it is given by q̂1 ϕ̃(q0 , q̂0 , q1 , q̂1 , r, r̂) = −S RS (q0 , q̂0 , r, r̂) − rr̂ + q0 q̂0 − (1 + q1 ) + IS (q̂0 , q̂1 , r̂) + αIE (q0 , q1 , r) (B3a) 2 R √ √ √ √ Z q̂1 −q̂0 Dz1 cosh q̂0 z0 + q̂1 − q̂0 z1 + r̂ ln 2 cosh q̂0 z0 + q̂1 − q̂0 z1 + r̂ √ (B3b) Dz0 IS = e− 2 cosh( q̂0 z0 + r̂) !R √ √ √ √ √ √ Z Dz1 H q0 z0 + q1 − q0 z1 , 1 − q1 ln H q0 z0 + q1 − q0 z1 , 1 − q1 rz0 IE = 2 Dz0 H − p (B3c) √ √ H q0 z0 , 1 − q0 q0 − r 2 We recall that equilibrium values of the parameters q0 , qˆ0 , q1 , qˆ1 , r, r̂ are those that extremize S 1RSB . Notice that q0 , q̂0 , r, r̂ in the m → 1 limit need to solve the saddle point equations for the RS free entropy (A5), while q1 and q̂1 can be found by extremizing ϕ̃ only. In summary one has to solve the following saddle point equations: ∂q̂0 S RS (q0 , q̂0 , r, r̂) = 0 ,
(B4a)
∂q0 S
RS
(q0 , q̂0 , r, r̂) = 0 ,
(B4b)
∂r̂ S
RS
(q0 , q̂0 , r, r̂) = 0 ,
(B4c)
∂r S
RS
(q0 , q̂0 , r, r̂) = 0 ,
(B4d)
∂q̂1 ϕ̃(q0 , q̂0 , q1 , q̂1 , r, r̂) = 0
(B4e)
∂q1 ϕ̃(q0 , q̂0 , q1 , q̂1 , r, r̂) = 0 .
(B4f)
The dynamical temperature Td (α) for a fixed value of α is defined as the largest temperature for which a solution with q1 > q0 appears. This can be found numerically as follows. First we numerically solve the first four equations above, respectively for q0 , q̂0 , r and r̂. Then consider the last two equations in (B4). Using the property of the Kernel (A6) ∂y H(x, y) = y∂x2 H(x, y) and an integration by parts they read R √ √ √ √ Z Dz1 sinh q̂0 z0 + q̂1 − q̂0 z1 + r̂ tanh q̂0 z0 + q̂1 − q̂0 z1 + r̂ ∂ ϕ̃ q1 1 − q̂1 −q̂0 2 √ =− + e Dz0 (B5) 0= ∂ q̂1 2 2 cosh( q̂0 z0 + r̂) 2 √ √ √ Z Z 2H − √ rz0 2 q0 −r ∂x H q0 z0 + q1 − q0 z1 , 1 − q1 ∂ ϕ̃ q̂1 α Dz1 =− + Dz0 0= (B6) √ √ √ √ √ ∂q1 2 2 H q0 z0 , 1 − q0 H q0 z0 + q1 − q0 z1 , 1 − q1
18
Figure 9. Left: ∂q̂1 ϕ̃ for the ABP in the storage case (where r = r̂ = 0) as a function of q1 , for α = 0.7 and different values of β. The solutions of the SPE are the zeros of this function. There is always a zero in q1 = q0 (the value of q0 depends on α and β) corresponding to the RS solution. For any β > 0, another non-trivial solution of the saddle point equation is found in q1 = 1. Right: ABP in the storage setting. The panel presents ϕ̃ as a function of q1 , for α = 0.7 and different values of β: its derivative vanishes at q1 = 1.
Via equation (B6) one expresses q̂1 in terms of q1 and inserts it in equation (B5). One then plots ∂q̂1 ϕ̃ as a function of q1 . This function will have at any temperature a root when q1 = q0 corresponding to the RS solution; this is also the only one when T > Td (α). At Td (α), ∂q̂1 ϕ̃ develops a new root at a value q1 > q0 . The dynamical temperature depends heavily on the nature of the factor K which enters into the definition of H(x, y), see (A6). In the following subsection we will specialize to the case of the ABP and SBP constraints and with the standard training error loss, counting the number of unsatisfied constraints. We show that whenever β = 1/T > 0, the saddle point equations admit the solution q1 = 1. This can be observed in Figure 9, where we plot ∂q̂1 ϕ̃ as a function of q1 (for the ABP in the storage case, where one furthermore has r = r̂ = 0). This means that in the perceptron model the dynamical temperature always diverges in the large N limit. The solution q1 = 1 corresponds to the so called frozen 1RSB scenario already found in [13] from the zerotemperature static analysis and is consistent with the results found by Horner [14] in the storage case, which were derived using dynamical mean-field theory. We will also discuss how to avoid this frozen phase by changing the expression of the energy function.
1.
The frozen 1RSB solution
We specialize here the computation to the ABP for simplicity. Equation (B6) solved for q̂1 then reads: √ 2 √ rz 0 q0 z0 + q1 −q0 z1 Z Z 2H − √ √ G q0 −r 2 (1 − e−β )2 1−q1 Dz1 , Dz0 q̂1 = α √ √ √ √ √ 1 − q1 H q0 z0 , 1 − q0 H q0 z0 + q1 − q0 z1 , 1 − q1
(B7)
where G(x) denotes the standard Gaussian density function. Substituting (B7) in (B5), we have ∂∂q̂ϕ̃1 as a function of q1 only. We want to show that for any β > 0, this derivative vanishes in the limit q1 = 1. To do so, take q1 = 1 − ϵ .
(B8)
19 Then, we compute q̂1 from (B7), as a function of ϵ ≃ 0: √ 2 √ rz0 q0 z0 + 1−q0 z1 √ Z Z 2H − √ G −β 2 2 q −r (1 − e ) ϵ 0 Dz1 Dz0 q̂1 ≃ α √ √ √ √ √ ϵ H q0 z0 , 1 − q0 H q0 z0 + 1 − q0 z1 , ϵ rz0 √ √ Z √ Z 2H − 2 q0 −r 2 q0 z0 (1 − e−β )2 ϵ G (u) √ ≃α Dz0 G √ du √ √ ϵ H (u, 1) 1 − q0 1 − q0 H q0 z0 , 1 − q0 =
C(q0 , r, α, β) √ , ϵ
where √ q0 z0 rz0 √ Z Z 2H − G √1−q 2 −β 2 2 0 q0 −r G (u) (1 − e ) Dz0 du . C(q0 , r, α, β) = α √ √ √ H (u, 1) 1 − q0 H q0 z0 , 1 − q0
(B9)
Notice that C(q0 , r, α, β) > 0 when β > 0 and 0 if β = 0. For small β, we can use H(x, y)−1 ≃ 1 + O(β), so that C(q0 , r, α, β) = c(α, q0 ) β 2 + O β 3 . (B10) Then, we consider the saddle point equation (B5). Rewrite it as a self-consistent equation: q1 = f (q̂1 (q1 )) ,
(B11)
where f (q̂1 ) is given by the right-hand-side of (B5): √ √ √ √ Z q̂1 −q̂0 cosh q̂0 z0 + q̂1 − q̂0 z1 + r̂ − [cosh q̂0 z0 + q̂1 − q̂0 z1 + r̂ ]−1 √ f (q̂1 ) = e− 2 Dz0 Dz1 cosh( q̂0 z0 + r̂) and q̂1 (q1 ) is given by (B7). We want to show that f (q̂1 (q1 )) → 1 in the limit q1 → 1, satisfying a consistency relation. We have: r 3/4 Z p q̂ −q̂ q̂1 −q̂0 π ϵ1/4 Du ϵ C − 12 0 √ f √ ≃e e 2 cosh( q̂0 u + r̂) − + o 1/2 2C ϵ C 3/2 cosh( q̂0 u + r̂) (B12) r π − 2C√ϵ ϵ1/4 , ≃1− e 2 C 1/2 R∞ having used −∞ dx cosh(x)−1 = π. Since for ϵ → 0 one has f → 1 when C > 0, we have shown that the frozen solution q1 = 1 is always a solution for any β > 0. So βd = 0 in the thermodynamic limit. Finally, one can also compute the behavior of βd as ϵ → 0, by solving (B11) for small β: r π − 2cβ√2ϵ ϵ1/4 1−ϵ=1− e 2 c1/2 β In the small ϵ limit, βd vanishes as: 1/4
βd ∼ ϵ
s 1 ln ϵ
(B13)
Setting ϵ ≃ N1 (B8), this heuristically identifies the scaling of βd with N: p βd ∼
ln (N ) . N 1/4
(B14)
We point out that this result does not depend on r and r̂, and that the exact same scaling is found for the SBP, where we have a further simplification due to the fact that q0 = q̂0 = 0.
20 2.
General criterion for freezing
The previous computation for the ABP shows that the existence of the frozen solution is controlled by the behaviour of the energetic saddle-point equation (B6): 2 √ √ √ Z Z 2H − √ rz0 2 q0 −r ∂x H q0 z0 + q1 − q0 z1 , 1 − q1 Dz1 q̂1 = α Dz0 √ √ √ √ √ H q0 z0 , 1 − q0 H q0 z0 + q1 − q0 z1 , 1 − q1 (B15) rz 0 √ Z Z √ 2 2H − √ q0 −r 2 ∂x H x, 1 − q1 x − q0 z0 dx √ √ = α Dz0 G √ √ √ q1 − q0 q1 − q0 H q0 z0 , 1 − q0 H x, 1 − q1 The entropic saddle-point equation, instead, is independent of the particular energetic factor. It can be written as (B16)
q1 = f (q̂1 ), and, for q̂1 → ∞, one has as shown in (B12) r f (q̂1 ) = 1 −
π −1/2 −q̂1 /2 q̂ e [1 + o(1)] , 2 1
(B17)
Therefore the frozen solution q1 = 1 can be obtained only if the energetic equation sends q̂1 to infinity when q1 → 1. The singularity of (B15) is entirely determined by the small-y behaviour of 2
[∂x H(x, y)] , H(x, y)
y=
(B18)
p 1 − q1
In order to make this statement more explicit, let us go back to the definition of the kernel Z H(x, y) = Dz K(x + yz),
(B19)
where K is the single-pattern Boltzmann factor, Cf. Eqs. (7), (10). Thus H(x, y) is a Gaussian smoothing of K on a scale y. If K is smooth around a point x, then ∂x H(x, y) remains finite as y → 0. Singular contributions can only arise close to points where K is non-smooth. This usually happens near the decision boundaries of the constraints. Let b be such a decision boundary point. In the x integral appearing in (B15), the Gaussian density multiplying (∂x H)2 /H is smooth on the scale y. Therefore, close to b, one can set x = b + yu,
(B20)
dx = y du.
The whole question is then reduced to the scaling with y of the boundary layer term: 2
Z BK (b, y) ≡ y
du
[∂x H(b + yu, y)] . H(b + yu, y)
(B21)
If this quantity diverges as y → 0, then q̂1 → ∞. Since the entropic equation satisfies (B17), this implies that the frozen solution q1 = 1 is present. If instead (B21) stays finite, or vanishes, the energetic equation does not force q̂1 → ∞, and the frozen solution at q1 = 1 is absent. We now discuss the possible behaviors of K at a boundary. • Jump discontinuity. Suppose that, close to b, the Boltzmann factor has a finite jump: K(s) = K− + ∆K Θ(s − b),
∆K ̸= 0.
(B22)
This is the case for both (7) and (10) for b = 0 and b = ±κ respectively. Then, using (B19) and setting x = b + yu, Z H(b + yu, y) = K− + ∆K Dz Θ(u + z). (B23)
21 Thus H(b + yu, y) is of order one inside the boundary layer. On the other hand, Z ∆K G(u). ∂x H(b + yu, y) = ∆K Dz δ(b + yu + yz − b) = y
(B24)
Therefore (∆K)2 BK (b, y) ≃ y
Z du
G(u)2 R . K− + ∆K Dz Θ(u + z)
(B25)
Hence a jump produces the divergence BK (b, y) = O
1 1 =O √ y 1 − q1
(B26)
This is precisely the mechanism found in the ABP/SBP computation done in the previous subsection. Indeed for the ABP: K− = e−β , ∆K = 1 − e−β and b = 0. • Vanishing power at the boundary. Suppose instead that the Boltzmann factor vanishes continuously at the boundary as K(s) ≃ A(s − b)γ Θ(s − b),
A, γ > 0.
see the right panel of Figure 1. Then Z Z H(b + yu, y) = Dz K(b + y(u + z)) ≃ Ay γ Dz (u + z)γ Θ(u + z) ≡ Ay γ Fγ (u) where Fγ (u) =
R
(B27)
(B28)
Dz (u + z)γ Θ(u + z). We therefore have ∂x H(b + yu, y) ≃ Ay γ−1 Fγ′ (u).
(B29)
Fγ′ (u)2 . Fγ (u)
(B30)
Therefore BK (b, y) ≃ y
γ−1
Z du
Consequently, if γ < 1, q̂1 diverges and one has the frozen solution q1 = 1, whereas if γ > 1 the frozen solution is lost. The case γ = 1 is marginal. This criterion also explains why the logarithmic potential studied in [28], which falls in this category, can remove freezing. • Continuous non-zero value at the boundary. Another possibility for the behavior of the kernel near the boundary point is the following K(s) = K0 + A(b − s)γ Θ(b − s) ,
K0 > 0.
(B31)
In this case H(b + yu, y) = K0 + O(y γ ),
(B32)
∂x H(b + yu, y) = O(y γ−1 ).
(B33)
BK (b, y) ∼ y 2γ−1 .
(B34)
while
Hence
Therefore, for ordinary integer powers γ > 1/2, there is no divergent boundary contribution. This category includes the single pattern Gibbs weight γ γ γ K(s) = e−β(−s) Θ(−s) = e−β(−s) + 1 − e−β(−s) Θ(s) (B35)
22 studied by Horner [14] and by [27], who focused on positive integers values of γ; see also the left panel of Figure 1 for a plot. At finite β this factor is continuous at s = 0: K(0− ) = K(0+ ) = 1.
(B36)
K(s) = 1 − β(−s)γ Θ(−s) + · · · .
(B37)
Close to the boundary,
This is of the form (B31) with K0 = 1, A = −β. For the usual integer cases γ ≥ 1, the boundary contribution does not diverge. Hence, at finite β, the energetic saddle equation does not force q̂1 → ∞ as q1 → 1, and the frozen solution disappears. A dynamical transition may still occur, but at a finite temperature and with q1 < 1 at the transition. At zero temperature, however, as K(s) → Θ(s), the jump is restored, and the freezing mechanism reappears. Appendix C: Detail of the message passing algorithms
In this section, we provide details of the message passing algorithm used in the main text to search for minimal error configurations in the ABP. We start from a short review of the AMP algorithm, then we move to the description of AMP+reinforcement. 1.
Approximate Message Passing
Consider the Gibbs measure induced by the partition function (5): QP µ µ=1 K (s (w)) . pD (w) = ZD
(C1)
The Approximate Message Passing (AMP) algorithm provides an iterative approximation to the local marginals of the measure (C1). AMP is obtained from the BeliefPPropagation (BP) equations using a Gaussian approximation which parametrizes the one site marginals mi (wi ) = w\i pD (w) in terms of its mean ai and variance bi . Being the weights binary in our setting, the one site mean X ai = mi (wi ) wi ≡ ⟨wi ⟩β (C2) wi =±1
completely determines also the variance of the one site marginal via bi = 1 − a2i . Starting at t = 0 from a random guess for the one site marginals at=0 and initializing randomly the P dimensional vector gµt=0 the AMP algorithm i consists in the following update equations: Vµt =
N X (xµ )2 h i
i=1
Mµt =
N
1 − at−1 i
2 i
(C3a)
,
N X xµ √ i at−1 − Vµt gµt−1 , i N i=1
(C3b) (C3c)
gµt = gE (y µ , Mµt , Vµt ; β) , hti =
P X µ=1
xµi
√
N
gE (y µ , Mµt , Vµt ; β) − at−1 i
ati = tanh(hti ) ,
P X µ=1
(xµi )2 N
∂M gE (y µ , Mµt , Vµt ; β) ,
(C3d) (C3e)
which are iterated for t = 1, . . . , tmax or until convergence. The function gE is called the energetic channel and depends in general on the detail of the model. For example in the case of ABP with error counting loss function it reads: yM −β −β √ gE (y, M, V ; β) = ∂M log e + 1 − e H − , (C4) V
23
0.5
0.5
0.4
0.4 0.3
= 6.0 AMP
0.4
0.3 0.2
0.2
0.0 0.2
0.4 0.6 constraint density
0.8
1.0
0.2
0.0
0.0 0.0
0.3
0.1
0.1
0.1
= 3.0 AMP
0.5
overlap q
0.6
overlap q
overlap q
0.6
= AMP
0.7
0.0
0.2
0.4 0.6 constraint density
0.8
1.0
0.0
0.2
0.4
0.6 0.8 1.0 constraint density
1.2
1.4
Figure 10. The AMP algorithm was tested at different values of temperature, corresponding to β = ∞, β = 6.0, β = 3.0 (left to right). The plots present the typical RS overlap q as a function of the constraint density α: experimental points (blue) were obtained with N = 1000 and averaged over 20 samples, and they agree with the theoretical RS curve (red).
where we remind that H(x) ≡ 12 Erfc √x2 . When AMP converges, it can be used to compute on a single sample other observables that are computed via the replica method. For example the overlap between two students sampled from (C1) can be written in terms of the one-site magnetizations as: N N 1 X 1 X 2 qN = ⟨wi ⟩β ⟨wi ⟩β = a . N i=1 N i=1 i
(C5)
In the large N limit, this can be proved to converge to the replica method RS order parameter q [43]. As a check of the reliability of our algorithm at finite temperature we confirmed this by running a few experiments, as reported in Figure 10.
Algorithm 2 One AMP+reinforcement update function rAMPstep(ht−1 , at−1 , g t−1 ; ρt−1 , β) Compute the variances Vµt ←
N 2 h X 2 i (xµ i) 1 − at−1 , i N i=1
µ = 1, . . . , P.
(C6)
N X xµ √ i at−1 − Vµt gµt−1 , i N i=1
µ = 1, . . . , P.
(C7)
Compute the Onsager-corrected means Mµt ← Update the energetic messages gµt ← gE (y µ , Mµt , Vµt ; β),
µ = 1, . . . , P.
(C8)
Update the fields
hti ←
P P 2 X X xµ (xµ i) √ i gµt − at−1 ∂M gE (y µ , Mµt , Vµt ; β) + ρt−1 ht−1 , i i N N µ=1 µ=1
i = 1, . . . , N.
(C9)
Update the magnetizations ati ← tanh(hti ), t
t
t
return (h , a , g ). end function
i = 1, . . . , N.
(C10)
24
Figure 11. ABP, storage setting. Training-error trajectories of rAMP for N = 1000, α = 0.9, reinforcement rate ρ = 10−4 , and different inverse temperatures β. All curves use the same dataset and initialization. The dashed horizontal line marks the target training error ϵtarg = 0.025. Among the values considered, only β = 4 reaches the target within 104 iterations.
2.
AMP + reinforcement (rAMP)
The reinforcement AMP algorithm (rAMP) [29] is a modification of the AMP iteration designed to turn the soft marginal information computed by AMP into an actual binary configuration. Standard AMP estimates the local magnetizations ai ≃ ⟨wi ⟩ of the Gibbs measure, but these magnetizations need not be close to ±1. The role of reinforcement is to progressively polarize the local fields, so that the magnetizations become closer to the vertices of the hypercube and the configuration given by wi = sign(ai )
(C11)
can be used as a candidate low-error assignment. Operationally, reinforcement is implemented by adding to the AMP field update a term proportional to the previous local field, hti = hti,AMP + ρt−1 ht−1 , i
(C12)
where hti,AMP denotes the standard AMP update, see (C3d). The parameter ρt is increased during the dynamics according to a reinforcement schedule. In the experiments reported in the main text we use ρt = 1 − (1 − ρ)t ,
(C13)
where ρ controls the speed at which the reinforcement is switched on. For small ρ and early times, ρt ≃ ρt, while at longer times the reinforcement strength approaches one. Setting ρ = 0 gives ρt = 0 for all t, and one recovers the standard AMP iteration. The explicit one-step rAMP update is given in Algorithm 2. The fixed-temperature reinforced dynamics, obtained by iterating this update at fixed β, is summarized in Algorithm 1 in the main text. We show in Figure 11 the behavior of the rAMP algorithm for fixed reinforcement rate and several values of β for α = 0.9 and N = 1000 in the storage setting of the ABP. Notice that the β = ∞ trajectory stops before reaching the maximum number of iterations, because the rAMP produces diverging updates. This is expected as for α > 0.784 it is hard to find solutions, and in addition for α greater than the SAT/UNSAT threshold αS = 0.833 solutions do not exist at all in the large N limit [11]. Decreasing the value of β allows to search for configurations having a certain positive value of the training error. Moreover, the resulting AMP updates are less singular and the local marginals are initially less polarized, which makes the subsequent reinforcement dynamics more stable. If one continues decreasing β but maintaining fixed the reinforcement rate ρ, the trajectory tends to stabilize at a higher training error value before exploring lower training error configurations at a larger number of iterations. The figure therefore shows that for each fixed reinforcement rate, there exists an optimal value of β that allows to probe the lowest achievable training error configurations. We also tested a temperature-annealing schedule. However, this introduces some additional hyperparameters: the starting temperature β0 , the temperature increment or cooling rate ∆β and the frequency of increment ∆it . Those new hyperparameters need to be tuned optimally together with the reinforcement schedule. Overall, we found no substantial improvement from incorporating temperature annealing.
25 Appendix D: Additional figures
0.315
0.2450
= , =1.0 m=2.0 m=3.0
0.310
= , =1.3 m=2.0 m=3.0
0.2425
generalization error
generalization error
0.2400 0.305 0.300 0.295
0.2375 0.2350 0.2325 0.2300
0.290
0.2275
0.285
0.6
0.7
0.8 overlap q1
0.9
0.2250
1.0
0.75
0.80
0.85 overlap q1
0.90
0.95
1.00
Figure 12. Generalization error as a function of the overlap q1 between the clones, for m = 2 and m = 3, and β = ∞. The left picture corresponds to the easy phase of Figure 6 (α = 1.0), while the right figure to the hard phase (α = 1.3) and all its points are characterized by a negative entropy. Clusters of m = 3 clones can achieve a better generalization, if the hyperparameter q1 is tuned conveniently.
0.1
0.27
0.26 generalization error
Entropy s(r)
0.0 0.1 0.2 =1.3 =10.0 =7.0 =5.0 =4.0
0.3 0.4
m=3.0, =1.3 T=0.0 T=0.2 T=0.3 T=0.4
0.0
0.2
0.4
overlap r
0.6
0.8
1.0
0.25
0.24
0.23 0.70
0.75
0.80
0.85 overlap q1
0.90
0.95
1.00
Figure 13. Left: the picture shows the entropy of the RS solution, as a function of the teacher-student overlap r(w, w⋆ ), in the hard phase (α = 1.3). The entropy increases with temperature, as expected. The same happens with solution of the 3-cloned system: the right picture shows the generalization error of a solution in the cluster, as a function of the mutual overlap q1 , similarly to Figure 5. The dashed parts of the curve signal a negative entropy.