Introduction
Parametrized quantum circuits are the workhorse of near-term quantum machine learning [1 , 2 , 3 , 4 , 5 ] . Their predictions are expectation values of quantum observables on the output of the circuit, which admit a Fourier representation in terms of trigonometric polynomials in the rotation angles used in the circuit, with frequencies set by the spectra of the gate generators [6 , 7 ] . This oscillatory response to the trainable parameters, a direct consequence of unitary rotations followed by a projective measurement, is usually regarded as a source of expressivity. For the capacity to store random input-label associations, the role of the oscillation is known for a minimal quantum perceptron: a higher readout oscillation frequency λ \lambda λ increases the storage capacity [8 ] . Its effect on learning from data is much less understood: generalization bounds for quantum models [9 , 10 , 11 ] are worst-case statements, while the statistical mechanics of learning has shown that typical learning curves of even the simplest networks can be qualitatively different [12 , 13 , 14 , 15 , 16 ] .
Here we address the question of rule inference , in the teacher-student scenario in which a student perceptron must reproduce the labels of a teacher of identical architecture from P = α N P=\alpha N P = α N examples, where N N N is the dimensionality of the data. We find that the same frequency that enlarges the storage capacity has the opposite effect on learning: (i) the initial alignment with the teacher is exponentially suppressed in λ 2 \lambda^2 λ 2 ; (ii) for λ > λ c ≃ 1.944 \lambda>\lambda_c\simeq1.944 λ > λ c ≃ 1.944 learning occurs through a first-order transition; (iii) the transition load grows only logarithmically with λ \lambda λ , whereas a weakly aligned metastable phase survives up to loads ∼ e λ 2 / λ 4 \sim e^{\lambda^2}/\lambda^4 ∼ e λ 2 / λ 4 , opening a wide region that is expected to be hard for efficient inference algorithms; (iv) the asymptotic learning curve is nonetheless λ \lambda λ independent.
Model
The input register consists of N N N qubits prepared in ∣ x ⟩ = ∣ x 1 ⟩ ⊗ ⋯ ⊗ ∣ x N ⟩ |x\rangle=|x_1\rangle\otimes\cdots\otimes|x_N\rangle ∣ x ⟩ = ∣ x 1 ⟩ ⊗ ⋯ ⊗ ∣ x N ⟩ , where x ∈ { ± 1 } N x\in\{ \pm1\}^N x ∈ { ± 1 } N , so that σ z ( j ) ∣ x ⟩ = x j ∣ x ⟩ \sigma_z^{(j)}|x\rangle=x_j|x\rangle σ z ( j ) ∣ x ⟩ = x j ∣ x ⟩ . The readout qubit is prepared in ∣ + 1 ⟩ |+1\rangle ∣ + 1 ⟩ ; see Figure 1 (a). The trainable gate
Figure 1. (a) Quantum perceptron: basis-encoded input, trainable gate (1) , and σ x \sigma_x σ x readout. (b) Readout (2) (gray), square-wave classifier s λ s_\lambda s λ (orange, λ = 3 \lambda= 3 λ = 3 ), classical perceptron sgn ( h ) \operatorname{sgn}(h) sgn ( h ) (dashed black), and the Gaussian distribution of the fields h h h (shaded).
U λ ( w ) = exp ( − i 2 λ w ^ ⋅ σ z ⊗ σ x ( o u t ) ) , w ^ = w ∥ w ∥ , (1) U_\lambda(\mathbf{w})=\exp\left(-\frac{\mathrm{i}}{2}\lambda\widehat{\mathbf{w}}\cdot\boldsymbol{\sigma}_z\otimes\sigma_x^{(\mathrm{out})}\right),\qquad\widehat{\mathbf{w}}=\frac{\mathbf{w}}{\lVert\mathbf{w}\rVert}, \tag*{(1)} U λ ( w ) = exp ( − 2 i λ w ⋅ σ z ⊗ σ x ( out ) ) , w = ∥ w ∥ w , (1)
acts on the input and readout register, jointly prepared in ∣ x ⟩ ⟨ x ∣ ⊗ ∣ + 1 ⟩ ⟨ + 1 ∣ |x\rangle\langle x|\otimes|+1\rangle\langle+1| ∣ x ⟩ ⟨ x ∣ ⊗ ∣ + 1 ⟩ ⟨ + 1∣ , as a rotation of the readout register by the angle λ w ^ ⋅ x \lambda\widehat{\mathbf{w}}\cdot\mathbf{x} λ w ⋅ x . Then, the expectation value of measuring σ x ( o u t ) \sigma_x^{(\mathrm{out})} σ x ( out ) is (Appendix A)
f λ ( x , w ) = Tr [ ( U λ ( w ) ∣ x ⟩ ⟨ x ∣ ⊗ ∣ + 1 ⟩ ⟨ + 1 ∣ U λ ( w ) † ) I ⊗ σ x ( o u t ) ] = sin ( λ w ⋅ x ∥ w ∥ ) . (2) f_\lambda(\mathbf{x},\mathbf{w})=\operatorname{Tr}\left[(U_\lambda(\mathbf{w})|x\rangle\langle x|\otimes|+1\rangle\langle+1|U_\lambda(\mathbf{w})^\dagger)\mathbb{I}\otimes\sigma_x^{(\mathrm{out})}\right]
=\sin\left(\lambda\frac{\mathbf{w}\cdot\mathbf{x}}{\lVert\mathbf{w}\rVert}\right). \tag*{(2)} f λ ( x , w ) = Tr [ ( U λ ( w ) ∣ x ⟩ ⟨ x ∣ ⊗ ∣ + 1 ⟩ ⟨ + 1∣ U λ ( w ) † ) I ⊗ σ x ( out ) ] = sin ( λ ∥ w ∥ w ⋅ x ) . (2)
Since the readout depends only on the direction of w \mathbf{w} w , we fix the redundant radial degree of freedom by imposing ∥ w ∥ 2 = N \lVert w\rVert^2 = N ∥ w ∥ 2 = N . For delocalized weights and independent Rademacher inputs, the local field h = w ⋅ x / N h = w \cdot x/\sqrt{N} h = w ⋅ x / N is of order one. We define the classifier
s λ ( h ) : = sgn ( sin ( λ h ) ) (3) s_\lambda(h) := \operatorname{sgn}(\sin(\lambda h)) \tag*{(3)} s λ ( h ) := sgn ( sin ( λh )) (3)
in terms of the local field h = w ⋅ x / N h = w \cdot x/\sqrt{N} h = w ⋅ x / N . The decision boundaries are given by the parallel hyperplanes h = k π / λ h = k\pi/\lambda h = k π / λ , k ∈ Z k \in\mathbb{Z} k ∈ Z , so that λ \lambda λ fixes their density as seen by the O ( 1 ) O(1) O ( 1 ) fields (see Figure 1 (b)), and λ → 0 + \lambda\to0^+ λ → 0 + recovers the classical perceptron sgn ( h ) \operatorname{sgn}(h) sgn ( h ) . We assume the ability to estimate expectation values with no errors, i.e., we neglect shot noise associated to finite-sampling. Note that the circuit does not generate entanglement on basis inputs and is classically simulable: The effects investigated below therefore stem solely from the periodic structure of the quantum readout, not from some inherently quantum property.
Teacher-student setting
We formulate learning in the teacher–student framework, which provides a controlled setting for studying how examples constrain an unknown classification rule [15 , 16 ] . A teacher generates the training labels, and the student has access to the labeled examples but not to the teacher’s parameters. The question is how much these examples reveal about the underlying rule, and whether this information allows the student to predict labels on previously unseen inputs.
In our model, the teacher weight vector w ∗ w^* w ∗ is drawn uniformly from the sphere ∥ w ∗ ∥ 2 = N \lVert w^*\rVert^2 = N ∥ w ∗ ∥ 2 = N . Independently of the teacher, we draw P P P inputs x μ x^\mu x μ whose entries are independent and take the values ± 1 \pm1 ± 1 with equal probability. The corresponding labels are generated according to
ξ μ = s λ ( w ∗ ⋅ x μ N ) , μ = 1 , … , P . (4) \xi^\mu= s_\lambda\left(\frac{w^* \cdot x^\mu}{\sqrt{N}}\right), \qquad\mu= 1,\ldots,P. \tag*{(4)} ξ μ = s λ ( N w ∗ ⋅ x μ ) , μ = 1 , … , P . (4)
We write X = ( x 1 , … , x P ) X = (x^1,\ldots,x^P) X = ( x 1 , … , x P ) and ξ = ( ξ 1 , … , ξ P ) \xi= (\xi^1,\ldots,\xi^P) ξ = ( ξ 1 , … , ξ P ) for the training inputs and labels and with T P = { ( x μ , ξ μ ) } μ = 1 P \mathcal{T}_P = \{(x^\mu,\xi^\mu)\}_{\mu=1}^P T P = {( x μ , ξ μ ) } μ = 1 P the whole training set.
For a given training set, every weight vector that reproduces all observed labels remains a possible explanation of the data. These compatible weights form the version space of the student, that is assumed to use the same classification rule and the same spherical prior as the teacher. Thus:
V ( T P ) = { w ∣ ∥ w ∥ 2 = N , s λ ( w ⋅ x μ N ) = ξ μ for all μ } . (5) \mathcal{V}(\mathcal{T}_P) = \left\{w \mid\lVert w\rVert^2 = N,\ s_\lambda\left(\frac{w \cdot x^\mu}{\sqrt{N}}\right) = \xi^\mu\ \text{for all }\mu\right\}. \tag*{(5)} V ( T P ) = { w ∣ ∥ w ∥ 2 = N , s λ ( N w ⋅ x μ ) = ξ μ for all μ } . (5)
An incompatible weight vector has zero likelihood, while every compatible vector has likelihood one. Bayes’ rule therefore restricts the prior to the version space and normalizes the resulting measure. If d μ ( w ) \mathrm{d}\mu(w) d μ ( w ) denotes the normalized uniform measure on the sphere, the posterior distribution is (Appendix B)
d μ T P ( w ) = 1 V ( T P ) ( w ) V N ( T P ) d μ ( w ) , (6) \mathrm{d}\mu_{\mathcal{T}_P}(w) = \frac{\mathbf{1}_{\mathcal{V}(\mathcal{T}_P)}(w)}{V_N(\mathcal{T}_P)}\,\mathrm{d}\mu(w), \tag*{(6)} d μ T P ( w ) = V N ( T P ) 1 V ( T P ) ( w ) d μ ( w ) , (6)
where 1 A \mathbf{1}_A 1 A denotes the indicator function of the set A A A (1 A ( w ) = 1 \mathbf{1}_A(w) = 1 1 A ( w ) = 1 if w ∈ A w \in A w ∈ A and zero otherwise) and
V N ( T P ) = ∫ V ( T P ) d μ ( w ) (7) V_N(\mathcal{T}_P) = \int_{\mathcal{V}(\mathcal{T}_P)} \mathrm{d}\mu(w) \tag*{(7)} V N ( T P ) = ∫ V ( T P ) d μ ( w ) (7)
is the volume of the version space, also called Gardner volume : The fraction of the original weight space that remains compatible with the training set [17 , 18 , 19 , 20 ] . Thus, sampling the posterior amounts to drawing a student uniformly from the compatible weights; we refer to such a posterior sample as a Gibbs student .
The prior and labeling rule used for inference match those that generated the data, which is the setting commonly called Bayes-optimal inference [21 ] . Its connection to statistical mechanics is expressed by the Nishimori condition , often described as being on the Nishimori line [22 , 23 ] . The relevant consequence here can be understood directly from Bayes’ rule. That is, conditioned on the observed training set, the unknown teacher has exactly the same distribution as a posterior-sampled student. The teacher and independent posterior samples can therefore be exchanged in statistical averages. This property underlies the Nishimori identities used below.
The Gardner volume also has a direct probabilistic interpretation. Before the teacher weights are known, the probability of observing the complete label sequence ξ \xi ξ at fixed inputs X X X is obtained by integrating the teacher prior over all weights that produce those labels. Consequently, V N ( T P ) = P ( ξ ∣ X ) V_N(\mathcal{T}_P) = \mathbb{P}(\xi\mid X) V N ( T P ) = P ( ξ ∣ X ) . In Bayesian terminology, this probability is the evidence (Appendix B). The same quantity therefore measures both the fraction of compatible weights and the probability assigned to the observed labels.
To characterize its behavior at large N N N , we consider the quenched entropy density , obtained by computing the logarithm of the volume for each fixed training set and then averaging over the teacher and inputs. The evidence interpretation gives E [ ln V N ] = − H ( ξ ∣ X ) \mathbb{E}[\ln V_N] = -H(\xi\mid X) E [ ln V N ] = − H ( ξ ∣ X ) , the conditional (Shannon) entropy of ξ \xi ξ given X X X . Moreover, the labels are completely determined by the teacher and inputs, so H ( ξ ∣ w ∗ , X ) = 0 H(\xi\mid w^*, X) = 0 H ( ξ ∣ w ∗ , X ) = 0 . Hence, the conditional entropy H ( ξ ∣ X ) H(\xi\mid X) H ( ξ ∣ X ) equals the conditional mutual information I ( w ∗ ; ξ ∣ X ) I(w^*; \xi\mid X) I ( w ∗ ; ξ ∣ X ) , and, in the limit N , P → ∞ N, P \to\infty N , P → ∞ at fixed training load α = P / N \alpha= P/N α = P / N ,
ϕ ( α , λ ) : = lim N → ∞ 1 N E [ ln V N ] = − lim N → ∞ 1 N I ( w ∗ ; ξ ∣ X ) , (8) \phi(\alpha,\lambda) := \lim_{N\to\infty} \frac{1}{N}\mathbb{E}[\ln V_N]
= -\lim_{N\to\infty} \frac{1}{N}I(w^*;\xi\mid X), \tag*{(8)} ϕ ( α , λ ) := N → ∞ lim N 1 E [ ln V N ] = − N → ∞ lim N 1 I ( w ∗ ; ξ ∣ X ) , (8)
provided the limit exists. Thus, − ϕ -\phi − ϕ measures the information about the teacher supplied by the labels per weight. Since each binary label conveys at most ln 2 \ln2 ln 2 nats of information, this immediately yields
− α ln 2 ≤ ϕ ≤ 0. (9) -\alpha\ln2 \le\phi\le0. \tag*{(9)} − α ln 2 ≤ ϕ ≤ 0. (9)
Replica-symmetric solution
We evaluate ϕ \phi ϕ with the replica method, in which the pattern average reduces to an average over Gaussian local fields whose covariance is the replica overlap matrix, and we impose replica symmetry (RS) together with the Nishimori identity, which equates the teacher-student and student-student overlaps (Appendices B1 and B3). The resulting RS prediction is
ϕ R S ( α , λ ) = max 0 ≤ r < 1 F λ ( r ; α ) (10) \phi_{\mathrm{RS}}(\alpha,\lambda) = \max_{0\le r<1}\mathcal{F}_{\lambda}(r;\alpha) \tag*{(10)} ϕ RS ( α , λ ) = 0 ≤ r < 1 max F λ ( r ; α ) (10)
with
F λ ( r ; α ) = 1 2 ln ( 1 − r ) + r 2 − α E t ∼ N ( 0 , 1 ) H 2 ( ψ λ ( r , t ) ) . (11) \mathcal{F}_{\lambda}(r;\alpha) = \frac{1}{2}\ln(1-r) + \frac{r}{2} - \alpha\mathbb{E}_{t\sim\mathcal{N}(0,1)}H_2(\psi_{\lambda}(r,t)). \tag*{(11)} F λ ( r ; α ) = 2 1 ln ( 1 − r ) + 2 r − α E t ∼ N ( 0 , 1 ) H 2 ( ψ λ ( r , t )) . (11)
Throughout the paper, ln \ln ln denotes the natural logarithm; we will use φ ( x ) = e − x 2 / 2 / 2 π \varphi(x) = e^{-x^2/2}/\sqrt{2\pi} φ ( x ) = e − x 2 /2 / 2 π and Φ ( x ) = ∫ − ∞ x φ ( u ) d u \Phi(x) = \int_{-\infty}^{x}\varphi(u)\,\mathrm{d}u Φ ( x ) = ∫ − ∞ x φ ( u ) d u for the standard normal probability density and the cumulative distribution function, respectively; we will use D t = φ ( t ) d t \mathop{\mathrm{D}}t = \varphi(t)\,\mathrm{d}t D t = φ ( t ) d t for the standard Gaussian integration measure. The function H 2 ( p ) = − p ln p − ( 1 − p ) ln ( 1 − p ) H_2(p) = -p\ln p - (1-p)\ln(1-p) H 2 ( p ) = − p ln p − ( 1 − p ) ln ( 1 − p ) denotes the binary entropy in nats, while N ( μ , v ) \mathcal{N}(\mu,v) N ( μ , v ) will be reserved for a normal distribution with mean μ \mu μ and variance v v v .
The function ψ λ ( r , t ) \psi_{\lambda}(r,t) ψ λ ( r , t ) appearing in (11) is defined by
ψ λ ( r , t ) = P z ∼ N ( 0 , 1 ) [ sin λ ( r t + 1 − r z ) > 0 ] ; (12) \psi_{\lambda}(r,t) = \mathbb{P}_{z\sim\mathcal{N}(0,1)}\left[\sin\lambda\left(\sqrt{r}\,t+\sqrt{1-r}\,z\right)>0\right]; \tag*{(12)} ψ λ ( r , t ) = P z ∼ N ( 0 , 1 ) [ sin λ ( r t + 1 − r z ) > 0 ] ; (12)
it is the probability that a student with an overlap r = w ⋅ w ∗ / N r = w\cdot w^*/N r = w ⋅ w ∗ / N with the teacher outputs + 1 +1 + 1 , given the Gaussian mode t t t it shares with the teacher. The maximizer r ⋆ r_\star r ⋆ of (10) , whenever it exists and is unique, is the RS prediction for the typical teacher-student overlap. The corresponding generalization error, defined as the error of a Gibbs student on a fresh input, is (see Appendix D)
ε λ ( r ) = 2 E t ∼ N ( 0 , 1 ) [ ψ λ ( 1 − ψ λ ) ] = 1 2 − 8 π 2 ∑ m , n = 0 ∞ sinh ( λ 2 r ( 2 m + 1 ) ( 2 n + 1 ) ) ( 2 m + 1 ) ( 2 n + 1 ) × e − λ 2 ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) / 2 , (13) \varepsilon_{\lambda}(r) = 2\mathbb{E}_{t\sim\mathcal{N}(0,1)}[\psi_{\lambda}(1-\psi_{\lambda})]
= \frac{1}{2}-\frac{8}{\pi^2}\sum_{m,n=0}^{\infty}\frac{\sinh\left(\lambda^2 r(2m+1)(2n+1)\right)}{(2m+1)(2n+1)}
\times e^{-\lambda^2\left((2m+1)^2+(2n+1)^2\right)/2}, \tag*{(13)} ε λ ( r ) = 2 E t ∼ N ( 0 , 1 ) [ ψ λ ( 1 − ψ λ )] = 2 1 − π 2 8 m , n = 0 ∑ ∞ ( 2 m + 1 ) ( 2 n + 1 ) sinh ( λ 2 r ( 2 m + 1 ) ( 2 n + 1 ) ) × e − λ 2 ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) /2 , (13)
which reduces to arccos ( r ) / π \arccos(r)/\pi arccos ( r ) / π for λ → 0 + \lambda\to0^+ λ → 0 + and to 1 / 2 1/2 1/2 for λ → ∞ \lambda\to\infty λ → ∞ at fixed r < 1 r<1 r < 1 , with exponentially small corrections that we bound explicitly in Appendix D. Equations (11) and (12) coincide with the Bayes-optimal formula for generalized linear models with Gaussian prior and deterministic channel y = s λ ( z ) y=s_{\lambda}(z) y = s λ ( z ) [24 ] , rigorously established there for Gaussian inputs and regular channels; for the present Rademacher inputs and discontinuous channel it rests on the standard replica assumptions detailed in Appendices B1 and B3.
Because the Gaussian-smoothed square wave obeys a heat equation, the stationarity condition can be recast in the simple form (Appendix § 1.12 ),
∂ r F λ = 2 J λ ( r ) ( α − α λ ( r ) ) , (14) \partial_r\mathcal{F}_{\lambda}=2\mathcal{J}_{\lambda}(r)(\alpha-\alpha_{\lambda}(r)), \tag*{(14)} ∂ r F λ = 2 J λ ( r ) ( α − α λ ( r )) , (14)
α λ ( r ) = r 4 ( 1 − r ) J λ ( r ) , (15) \alpha_{\lambda}(r)=\frac{r}{4(1-r)\mathcal{J}_{\lambda}(r)}, \tag*{(15)} α λ ( r ) = 4 ( 1 − r ) J λ ( r ) r , (15)
where
J λ ( r ) = λ 2 4 E t ∼ N ( 0 , 1 ) [ ( ∂ t ψ λ ) 2 ψ λ ( 1 − ψ λ ) ] > 0 (16) \mathcal{J}_{\lambda}(r)=\frac{\lambda^2}{4}\mathbb{E}_{t\sim\mathcal{N}(0,1)}\left[\frac{(\partial_t\psi_{\lambda})^2}{\psi_{\lambda}(1-\psi_{\lambda})}\right]>0 \tag*{(16)} J λ ( r ) = 4 λ 2 E t ∼ N ( 0 , 1 ) [ ψ λ ( 1 − ψ λ ) ( ∂ t ψ λ ) 2 ] > 0 (16)
is λ 2 / 4 \lambda^2/4 λ 2 /4 times the averaged Bernoulli Fisher information with respect to the mean phase θ = λ r t \theta=\lambda\sqrt{r}\,t θ = λ r t . At fixed λ \lambda λ and training load α \alpha α , the stationary overlaps are the solutions of α λ ( r ) = α \alpha_{\lambda}(r)=\alpha α λ ( r ) = α . At each such point,
∂ r 2 F λ ( r ; α ) = − 2 J λ ( r ) α λ ′ ( r ) . \partial_r^2\mathcal{F}_{\lambda}(r;\alpha)=-2\mathcal{J}_{\lambda}(r)\alpha_{\lambda}'(r). ∂ r 2 F λ ( r ; α ) = − 2 J λ ( r ) α λ ′ ( r ) .
Since J λ ( r ) > 0 \mathcal{J}_{\lambda}(r)>0 J λ ( r ) > 0 , solutions with α λ ′ ( r ) > 0 \alpha_{\lambda}'(r)>0 α λ ′ ( r ) > 0 are local maxima of F λ \mathcal{F}_{\lambda} F λ , whereas those with α λ ′ ( r ) < 0 \alpha_{\lambda}'(r)<0 α λ ′ ( r ) < 0 are local minima. The stationary curve α = α λ ( r ) \alpha=\alpha_{\lambda}(r) α = α λ ( r ) also governs the fixed points of Bayes-optimal generalized approximate message passing (GAMP) [21 , 25 , 26 ] , an iterative inference algorithm that we use to numerically test the RS predictions for the stationary overlaps (Appendix F).
Results
Suppressed linear signal. —For small loads, r ⋆ = 4 κ λ 2 α + O ( α 2 ) r_\star= 4\kappa_{\lambda}^2\alpha+O(\alpha^2) r ⋆ = 4 κ λ 2 α + O ( α 2 ) with
κ λ = 1 2 E z [ z s λ ( z ) ] = 2 λ π ∑ k ≥ 0 e − λ 2 ( 2 k + 1 ) 2 / 2 . (17) \kappa_{\lambda}=\frac{1}{2}\mathbb{E}_{z}[z\,s_{\lambda}(z)] = \frac{2\lambda}{\pi}\sum_{k\ge0}e^{-\lambda^2(2k+1)^2/2}. \tag*{(17)} κ λ = 2 1 E z [ z s λ ( z )] = π 2 λ k ≥ 0 ∑ e − λ 2 ( 2 k + 1 ) 2 /2 . (17)
The classical value r ⋆ ≃ 2 α / π r_\star\simeq2\alpha/\pi r ⋆ ≃ 2 α / π is recovered for λ → 0 + \lambda\to0^+ λ → 0 + , whereas 4 κ λ 2 ≃ ( 16 / π 2 ) λ 2 e − λ 2 4\kappa_{\lambda}^2\simeq(16/\pi^2)\lambda^2e^{-\lambda^2} 4 κ λ 2 ≃ ( 16/ π 2 ) λ 2 e − λ 2 for λ ≫ 1 \lambda\gg1 λ ≫ 1 ; each label is almost a fair coin for a student with r ≈ 0 r\approx0 r ≈ 0 and carries a nearly full bit, but only an exponentially small linear signal about w ∗ w^\ast w ∗ . More generally, at any fixed α \alpha α the RS maximizer satisfies r ⋆ → 0 r_\star\to0 r ⋆ → 0 and ϵ g → 1 / 2 \epsilon_g\to1/2 ϵ g → 1/2 as λ → ∞ \lambda\to\infty λ → ∞ , − ϕ R S → α ln 2 -\phi_{\rm RS}\to\alpha\ln2 − ϕ RS → α ln 2 (Appendix D). The labels become maximally informative, yet a typical student learns nothing.
First-order learning transition. —Figure 2 shows the equilibrium learning curves. For small λ \lambda λ , α λ ( r ) \alpha_\lambda(r) α λ ( r ) is monotonic and r ⋆ r_\star r ⋆ grows smoothly. At
Figure 2. Equilibrium RS learning curves. (a) Teacher-student overlap r ⋆ r_\star r ⋆ and (b) Gibbs error ϵ g = ϵ λ ( r ⋆ ) \epsilon_g=\epsilon_\lambda(r_\star) ϵ g = ϵ λ ( r ⋆ ) versus α \alpha α . For λ > λ c \lambda>\lambda_c λ > λ c the curves jump at α e q ( λ ) \alpha_{\rm eq}(\lambda) α eq ( λ ) (open circles: one-sided limits; dotted: jump). Thin dashed lines: metastable branches for λ = 3 \lambda=3 λ = 3 . Inset: α ϵ g \alpha\epsilon_g α ϵ g , approaching the λ \lambda λ -independent value 2 / ( π C H ) ≃ 0.625 2/(\sqrt{\pi}C_H)\simeq0.625 2/ ( π C H ) ≃ 0.625 (dashed).
( λ c , α c , r c ) ≃ ( 1.94359 , 1.98100 , 0.5819 ) , (18) (\lambda_c,\alpha_c,r_c)\simeq(1.94359,1.98100,0.5819), \tag*{(18)} ( λ c , α c , r c ) ≃ ( 1.94359 , 1.98100 , 0.5819 ) , (18)
where α λ ′ ( r ) = α λ ′ ′ ( r ) = 0 \alpha_\lambda'(r)=\alpha_\lambda''(r)=0 α λ ′ ( r ) = α λ ′′ ( r ) = 0 , the curve develops an inflection point, and for λ > λ c \lambda>\lambda_c λ > λ c it becomes S-shaped (Figure 3 ). Two folds, the spinodals α s p − ( λ ) < α s p + ( λ ) \alpha_{\rm sp}^-(\lambda)<\alpha_{\rm sp}^+(\lambda) α sp − ( λ ) < α sp + ( λ ) , delimit a load interval with two local maxima of F λ \mathcal{F}_\lambda F λ : A weakly aligned one, continuing the small-α \alpha α branch, and a strongly aligned one. Their free entropies cross at the coexistence load α e q ( λ ) \alpha_{\rm eq}(\lambda) α eq ( λ ) , where the equilibrium overlap and error jump. For instance, at λ = 3 \lambda=3 λ = 3 one finds α e q = 3.2125 \alpha_{\rm eq}=3.2125 α eq = 3.2125 , with r ⋆ r_\star r ⋆ jumping from 0.0058 0.0058 0.0058 to 0.9684 0.9684 0.9684 and ϵ g \epsilon_g ϵ g from 0.49999 0.49999 0.49999 to 0.1915 0.1915 0.1915 . We prove in Appendix § 1.12 that, whenever two nondegenerate global maxima coexist, ϕ R S \phi_{\rm RS} ϕ RS
Figure 3. Stationary points of F λ \mathcal{F}_\lambda F λ at λ = 2.2 \lambda=2.2 λ = 2.2 , i.e., the curve α = α λ ( r ) \alpha=\alpha_\lambda(r) α = α λ ( r ) of Eq. (14). Diamonds: spinodals; dashed vertical line: equilibrium jump at α e q = 2.3639 \alpha_{\rm eq}=2.3639 α eq = 2.3639 . Inset: F λ ( r ) − max r F λ \mathcal{F}_\lambda(r)-\max_r\mathcal{F}_\lambda F λ ( r ) − max r F λ at α = 2.28 \alpha=2.28 α = 2.28 (light blue), α e q \alpha_{\rm eq} α eq (black), and 2.70 2.70 2.70 (red).
is continuous and its load derivative jumps by
Δ ∂ α ϕ R S = E t ∼ N ( 0 , 1 ) [ H 2 ( ψ λ ( r − , t ) ) − H 2 ( ψ λ ( r + , t ) ) ] > 0. (19) \Delta\partial_\alpha\phi_{\rm RS}=\mathbb{E}_{t\sim\mathcal{N}(0,1)}\left[H_2(\psi_\lambda(r_-,t))-H_2(\psi_\lambda(r_+,t))\right]>0. \tag*{(19)} Δ ∂ α ϕ RS = E t ∼ N ( 0 , 1 ) [ H 2 ( ψ λ ( r − , t )) − H 2 ( ψ λ ( r + , t )) ] > 0. (19)
By the chain rule of mutual information, − ∂ α ϕ -\partial_\alpha\phi − ∂ α ϕ gives the predictive entropy of a fresh label, whose RS prediction is − ∂ α ϕ R S -\partial_\alpha\phi_{\rm RS} − ∂ α ϕ RS at α e q \alpha_{\rm eq} α eq the predictive uncertainty drops discontinuously, by 0.260 0.260 0.260 nats at λ = 2.2 \lambda=2.2 λ = 2.2 and 0.387 0.387 0.387 nats at λ = 3 \lambda=3 λ = 3 . This is the analog, for continuous weights and a periodic readout, of the first-order transition to perfect generalization of the Ising perceptron [12 , 13 ] ; in the classical spherical perceptron learning is always smooth [16 ] . Selecting the global maximum is essential. Indeed, following a single stationary solution by continuation in α \alpha α would retain a near-chance error well beyond α e q \alpha_{\rm eq} α eq .
Metastability and algorithms. —Figure 3 shows the RS stationary branches. We notice that the observed metastability has an algorithmic counterpart. Indeed, in the interval α e q < α < α s p + \alpha_{\rm eq}<\alpha<\alpha_{\rm sp}^+ α eq < α < α sp + , the strongly aligned solution is thermodynamically dominant, while GAMP from an uninformed initialization remains on the weakly aligned metastable branch. This gap between equilibrium and message-passing performance is characteristic of a “hard” phase in Bayesian inference [21 , 27 ] . The numerical GAMP comparison and its dependence on initialization are discussed in Appendix F (see Appendix § 1.14 for the numerical results).
Scaling of the thresholds. —The phase diagram in Figure 4 reveals three different large-λ \lambda λ behaviors, which we derive analytically in Appendix D. On the weakly aligned branch, r = O ( λ − 2 ) r=O(\lambda^{-2}) r = O ( λ − 2 ) and only the first Fourier harmonic of ψ λ \psi_\lambda ψ λ survives, giving J λ ( r ) ≃ ( 4 λ 2 / π 2 ) e − λ 2 cosh ( λ 2 r ) \mathcal{J}_\lambda(r)\simeq(4\lambda^2/\pi^2)e^{-\lambda^2}\cosh(\lambda^2r) J λ ( r ) ≃ ( 4 λ 2 / π 2 ) e − λ 2 cosh ( λ 2 r ) . The fold of α λ ( r ) \alpha_\lambda(r) α λ ( r ) is then at λ 2 r = x 0 \lambda^2r=x_0 λ 2 r = x 0 , with x 0 tanh x 0 = x_0\tanh x_0= x 0 tanh x 0 = 1, and
Figure 4. RS phase diagram. Coexistence line α e q ( λ ) \alpha_{\mathrm{eq}}(\lambda) α eq ( λ ) (solid), spinodals α s p ± ( λ ) \alpha_{\mathrm{sp}}^{\pm}(\lambda) α sp ± ( λ ) , and critical endpoint (18) . Shading: aligned-phase metastability (blue) and hard phase α e q < α < α s p + \alpha_{\mathrm{eq}} < \alpha< \alpha_{\mathrm{sp}}^{+} α eq < α < α sp + (orange). Dotted: large-λ \lambda λ asymptotics (20) and (21) , and α s p − ( ∞ ) ≃ 2.647 \alpha_{\mathrm{sp}}^{-}(\infty) \simeq2.647 α sp − ( ∞ ) ≃ 2.647 .
α s p + ≃ π 2 16 x 0 cosh x 0 e λ 2 λ 4 ≃ 0.409 e λ 2 λ 4 , (20) \alpha_{\mathrm{sp}}^{+} \simeq\frac{\pi^2}{16}\frac{x_0}{\cosh x_0}\frac{e^{\lambda^2}}{\lambda^4} \simeq0.409\frac{e^{\lambda^2}}{\lambda^4}, \tag*{(20)} α sp + ≃ 16 π 2 cosh x 0 x 0 λ 4 e λ 2 ≃ 0.409 λ 4 e λ 2 , (20)
with relative corrections O ( λ − 2 ) O(\lambda^{-2}) O ( λ − 2 ) . On the aligned branch, each fringe h = k π / λ h = k\pi/\lambda h = k π / λ acts as a classical perceptron boundary of width ( 1 − r ) / r \sqrt{(1-r)/r} ( 1 − r ) / r in the variable t t t . Summing the boundary layers yields F λ ( + ) ≃ − ln ( α C H Θ λ ) − 1 2 \mathcal{F}^{(+)}_\lambda\simeq-\ln(\alpha C_H\Theta_\lambda)-\frac{1}{2} F λ ( + ) ≃ − ln ( α C H Θ λ ) − 2 1 , with C H = ∫ R H 2 [ Φ ( x ) ] d x ≃ 1.8064 C_H = \int_{\mathbb{R}} H_2[\Phi(x)]\,\mathrm{d}x \simeq1.8064 C H = ∫ R H 2 [ Φ ( x )] d x ≃ 1.8064 (Φ \Phi Φ is the cumulative distribution function of the standard normal distribution) and Θ λ = ∑ k ∈ Z φ ( k π / λ ) → λ / π \Theta_\lambda= \sum_{k\in\mathbb{Z}}\varphi(k\pi/\lambda) \to\lambda/\pi Θ λ = ∑ k ∈ Z φ ( k π / λ ) → λ / π (φ \varphi φ the normal density). Equating it with the weakly aligned value F λ ( − ) ≃ − α ln 2 \mathcal{F}^{(-)}_\lambda\simeq-\alpha\ln2 F λ ( − ) ≃ − α ln 2 gives
α e q ln 2 − ln α e q ≃ ln λ + ln C H π + 1 2 , (21) \alpha_{\mathrm{eq}}\ln2-\ln\alpha_{\mathrm{eq}}\simeq\ln\lambda+\ln\frac{C_H}{\pi}+\frac{1}{2}, \tag*{(21)} α eq ln 2 − ln α eq ≃ ln λ + ln π C H + 2 1 , (21)
i.e., α e q ≃ log 2 λ + log 2 log 2 λ \alpha_{\mathrm{eq}}\simeq\log_2\lambda+\log_2\log_2\lambda α eq ≃ log 2 λ + log 2 log 2 λ , which reproduces the exact coexistence line within 1.3% at λ = 3 \lambda=3 λ = 3 and 0.2% at λ = 5 \lambda=5 λ = 5 . Finally, the aligned branch appears at α s p − → 2.647 \alpha_{\mathrm{sp}}^{-}\to2.647 α sp − → 2.647 . The logarithmic law has a simple information-theoretic reading: To generalize, the student must localize the teacher within one fringe, which costs ≃ ln λ \simeq\ln\lambda ≃ ln λ nats per weight, while each label provides at most ln 2 \ln2 ln 2 . Statistically, a high frequency is thus cheap. Algorithmically it is not, i.e., the linear signal (17) that guides an uninformed learner is ∝ e − λ 2 \propto e^{-\lambda^2} ∝ e − λ 2 , so the hard phase widens super-exponentially in λ \lambda λ . This mirrors, in a proportional high-dimensional limit and at fixed frequency, the cryptographic hardness of learning periodic neurons whose frequency grows with dimension [28 , 29 ] , and it complements the overlap-gap analysis of the square-wave perceptron with binary weights and Gaussian inputs [30 , 31 ] .
Universal asymptotics and fragmented version space
Once the aligned phase is reached, the boundary-layer solution gives ϵ g ≃ 2 / ( π C H α ) ≃ 0.625 / α \epsilon_g \simeq2/(\sqrt{\pi}\,C_H\alpha) \simeq0.625/\alpha ϵ g ≃ 2/ ( π C H α ) ≃ 0.625/ α for every λ \lambda λ [inset of Figure 2 (b)], the classical Gibbs-learning law [14 , 16 ] . The frequency enters only through Θ λ \Theta_\lambda Θ λ , which rescales 1 − r ⋆ 1-r_\star 1 − r ⋆ and shifts the mutual information by ln [ 2 π Θ λ ] \ln[\sqrt{2\pi}\,\Theta_\lambda] ln [ 2 π Θ λ ] , but leaves the error unchanged. Hence, more fringes make each label more informative about w ⋆ w^\star w ⋆ and, in the same proportion, more fragile to misalignment. The version space also has a markedly nonclassical geometry. Since a field can move between two fringes of equal label only by crossing a fringe of opposite label, V \mathcal{V} V is the disjoint union of cells labeled by the fringe index k μ k_\mu k μ of every field, whereas for λ → 0 + \lambda\to0^{+} λ → 0 + it is convex. Any continuous zero-training-error dynamics is confined to its initial cell; accordingly, samplers started at the teacher remain in the teacher’s cell and overestimate r ⋆ r_\star r ⋆ (Appendix § 1.15 ).
Discussions
The periodic measurement response of a quantum perceptron has opposite consequences for storage and for learning. It increases the number of random patterns that can be stored [8 ] , but it turns generalization into a first-order transition, delays its onset logarithmically in the frequency, and makes it algorithmically hard over a range of loads that grows as e λ 2 / λ 4 e^{\lambda^2}/\lambda^4 e λ 2 / λ 4 , while leaving the asymptotic error unchanged. Since the output of any parametrized circuit is a trigonometric polynomial whose frequencies are fixed by the architecture [6 ] , and data re-uploading increases them [7 ] , we expect analogous transitions whenever high-frequency components dominate a quantum model’s decision function. Therefore, the spectrum that boosts expressivity also sets the sample and computational complexity of learning. Open problems include a proof of the RS formula for binary inputs and discontinuous channels, the effect of finite-shot readout and of prior or model mismatch, and the analysis of training algorithms on the fragmented version space.
Acknowledgments
G.G. is partially supported by INFN through the project “QUANTUM”, by the Italian National Group of Mathematical Physics (GNFM-INDaM), and by the University of Bari through the 2023-UNBACLE-0245516 grant. M.G. acknowledges financial support from the European Union under ERC Advanced Grant TATypic, Project No. 101142236. Views and opinions expressed are those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency.
Circuit and classical reduction
Here we derive the sinusoidal expectation value of the readout observable in (2) , and show how its sign yields the periodic classifier defined in (3) . We also establish the absence of input–output entanglement for basis-encoded inputs, and explain the model’s classical reduction under the assumption of exact expectation values.
We denote by ∣ ± 1 ⟩ \lvert\pm1\rangle ∣ ± 1 ⟩ the eigenstates of σ z \sigma_z σ z with eigenvalues ± 1 \pm1 ± 1 , respectively. The input x ∈ { ± 1 } N \boldsymbol{x} \in\{\pm1\}^{N} x ∈ { ± 1 } N is basis encoded into ∣ x ⟩ = ∣ x 1 ⟩ ⊗ ⋯ ⊗ ∣ x N ⟩ \lvert x\rangle= \lvert x_1\rangle\otimes\cdots\otimes\lvert x_N\rangle ∣ x ⟩ = ∣ x 1 ⟩ ⊗ ⋯ ⊗ ∣ x N ⟩ , where σ z ( j ) ∣ x j ⟩ = x j ∣ x j ⟩ \sigma_z^{(j)}\lvert x_j\rangle= x_j\lvert x_j\rangle σ z ( j ) ∣ x j ⟩ = x j ∣ x j ⟩ ; the readout qubit is prepared in the σ z \sigma_z σ z eigenstate ∣ + 1 ⟩ \lvert+1\rangle ∣ + 1 ⟩ with eigenvalue + 1 +1 + 1 . The trainable gate is
U λ ( w ) = exp ( − i 2 λ w ^ ⋅ σ z ⊗ σ y ( o u t ) ) , w ^ ⋅ σ z = ∑ j = 1 N w j ∥ w ∥ σ z ( j ) , (22) U_\lambda(\boldsymbol{w}) = \exp\left(-\frac{\mathrm{i}}{2}\lambda\widehat{\boldsymbol{w}}\cdot\boldsymbol{\sigma}_z \otimes\sigma_y^{(\mathrm{out})}\right), \qquad\widehat{\boldsymbol{w}}\cdot\boldsymbol{\sigma}_z = \sum_{j=1}^{N}\frac{w_j}{\lVert\boldsymbol{w}\rVert}\sigma_z^{(j)}, \tag*{(22)} U λ ( w ) = exp ( − 2 i λ w ⋅ σ z ⊗ σ y ( out ) ) , w ⋅ σ z = j = 1 ∑ N ∥ w ∥ w j σ z ( j ) , (22)
with λ > 0 \lambda> 0 λ > 0 a fixed architectural parameter. Since ∣ x ⟩ \lvert x\rangle ∣ x ⟩ is a joint eigenvector of the σ z ( j ) \sigma_z^{(j)} σ z ( j ) , the gate rotates the readout by θ = λ w ⋅ x / ∥ w ∥ \theta= \lambda\boldsymbol{w}\cdot\boldsymbol{x}/\lVert\boldsymbol{w}\rVert θ = λ w ⋅ x / ∥ w ∥ , giving
U λ ( w ) ∣ x ⟩ ⊗ ∣ + 1 ⟩ = ∣ x ⟩ ⊗ e − i θ σ y ( o u t ) / 2 ∣ + 1 ⟩ = ∣ x ⟩ ⊗ ( cos ( θ / 2 ) ∣ + 1 ⟩ + sin ( θ / 2 ) ∣ − 1 ⟩ ) . (23) U_\lambda(\boldsymbol{w})\lvert x\rangle\otimes\lvert+1\rangle= \lvert x\rangle\otimes e^{-\mathrm{i}\theta\sigma_y^{(\mathrm{out})}/2}\lvert+1\rangle= \lvert x\rangle\otimes\left(\cos(\theta/2)\lvert+1\rangle+ \sin(\theta/2)\lvert-1\rangle\right). \tag*{(23)} U λ ( w ) ∣ x ⟩ ⊗ ∣ + 1 ⟩ = ∣ x ⟩ ⊗ e − i θ σ y ( out ) /2 ∣ + 1 ⟩ = ∣ x ⟩ ⊗ ( cos ( θ /2 ) ∣ + 1 ⟩ + sin ( θ /2 ) ∣ − 1 ⟩ ) . (23)
The expectation value of σ x ( o u t ) \sigma_x^{(\mathrm{out})} σ x ( out ) is therefore 2 cos ( θ / 2 ) sin ( θ / 2 ) = sin θ 2\cos(\theta/2)\sin(\theta/2)=\sin\theta 2 cos ( θ /2 ) sin ( θ /2 ) = sin θ , as in Eq. (2) . The unitary depends only on the direction of w \boldsymbol{w} w ; we fix the redundant radial degree of freedom by ∥ w ∥ = N \lVert\boldsymbol{w}\rVert=\sqrt{N} ∥ w ∥ = N , so that θ = λ h \theta=\lambda h θ = λh with h = w ⋅ x / N = O ( 1 ) h=\boldsymbol{w}\cdot\boldsymbol{x}/\sqrt{N}=O(1) h = w ⋅ x / N = O ( 1 ) . The binary classifier is
g w ( x ) = s λ ( w ⋅ x N ) , s λ ( h ) = sgn ( sin ( λ h ) ) , (24) g_{\boldsymbol{w}}(\boldsymbol{x})=s_\lambda\left(\frac{\boldsymbol{w}\cdot\boldsymbol{x}}{\sqrt{N}}\right), \qquad s_\lambda(h)=\operatorname{sgn}(\sin(\lambda h)), \tag*{(24)} g w ( x ) = s λ ( N w ⋅ x ) , s λ ( h ) = sgn ( sin ( λh )) , (24)
whose value on the measure-zero set sin ( λ h ) = 0 \sin(\lambda h)=0 sin ( λh ) = 0 is irrelevant below.
Three features of generic variational classifiers are retained: classical data are mapped to quantum states, trainable parameters enter a unitary, and the prediction is a thresholded single-qubit expectation value [4 , 5 ] . The Fourier structure of parametrized expectation values [6 ] collapses here to the single mode sin ( λ w ^ ⋅ x ) \sin(\lambda\widehat{\boldsymbol{w}}\cdot\boldsymbol{x}) sin ( λ w ⋅ x ) , whose sign changes on the parallel hyperplanes w ^ ⋅ x = k π / λ \widehat{\boldsymbol{w}}\cdot\boldsymbol{x}=k\pi/\lambda w ⋅ x = k π / λ , k ∈ Z k\in\mathbb{Z} k ∈ Z . Conversely, for basis inputs the circuit generates no input–output entanglement, all input generators commute, and exact expectation values (no shot noise) are assumed. The effects discussed in the main text are therefore properties of the periodic measurement response, not of entanglement or of a quantum computational advantage.
Teacher-student setting, evidence and generalization
We formulate here the learning process in the teacher–student framework [16 ] , focusing on the “generalization” (probability of error made by student on fresh inputs).
The weights are drawn from the uniform measure on S N − 1 ( N ) : = { w ∈ R N : ∥ w ∥ = N } \mathbb{S}^{N-1}(\sqrt{N}):=\{\boldsymbol{w}\in\mathbb{R}^{N}:\lVert\boldsymbol{w}\rVert=\sqrt{N}\} S N − 1 ( N ) := { w ∈ R N : ∥ w ∥ = N } ,
d μ ( w ) = 1 Z N d N w δ ( ∥ w ∥ 2 − N ) , Z N = π N / 2 N N / 2 − 1 Γ ( N / 2 ) . (25) \mathrm{d}\mu(\boldsymbol{w})=\frac{1}{Z_N}\,\mathrm{d}^{N}w\,\delta(\lVert\boldsymbol{w}\rVert^2-N), \qquad Z_N=\frac{\pi^{N/2}N^{N/2-1}}{\Gamma(N/2)}. \tag*{(25)} d μ ( w ) = Z N 1 d N w δ (∥ w ∥ 2 − N ) , Z N = Γ ( N /2 ) π N /2 N N /2 − 1 . (25)
A teacher w ∗ ∼ μ \boldsymbol{w}^{*}\sim\mu w ∗ ∼ μ is drawn once; the inputs X = ( x 1 , … , x P ) X=(\boldsymbol{x}^{1},\ldots,\boldsymbol{x}^{P}) X = ( x 1 , … , x P ) have i.i.d. Rademacher entries, i.e. P ( x i μ = ± 1 ) = 1 / 2 \mathbb{P}(x_i^\mu=\pm1)=1/2 P ( x i μ = ± 1 ) = 1/2 ; the labels are generated according to the teacher as ξ μ = g w ∗ ( x μ ) \xi^\mu=g_{\boldsymbol{w}^{*}}(\boldsymbol{x}^\mu) ξ μ = g w ∗ ( x μ ) and we denote with T P = { ( x μ , ξ μ ) } μ = 1 P \mathcal{T}_P=\{(\boldsymbol{x}^\mu,\xi^\mu)\}_{\mu=1}^{P} T P = {( x μ , ξ μ ) } μ = 1 P the corresponding training set. We consider the thermodynamic limit N , P → ∞ N,P\to\infty N , P → ∞ with α = P / N \alpha=P/N α = P / N fixed. The version space V ( T P ) = { w : g w ( x μ ) = ξ μ for all μ } \mathcal{V}(\mathcal{T}_P)=\{\boldsymbol{w}:g_{\boldsymbol{w}}(\boldsymbol{x}^\mu)=\xi^\mu\ \text{for all }\mu\} V ( T P ) = { w : g w ( x μ ) = ξ μ for all μ } of weights compatible with the training set has (Gardner) volume [17 , 18 , 19 ]
V N ( T P ) = ∫ d μ ( w ) ∏ μ = 1 P 1 { g w ( x μ ) = ξ μ } , (26) V_N(\mathcal{T}_P)=\int\mathrm{d}\mu(\boldsymbol{w})\prod_{\mu=1}^{P}\mathbb{1}\{g_{\boldsymbol{w}}(\boldsymbol{x}^\mu)=\xi^\mu\}, \tag*{(26)} V N ( T P ) = ∫ d μ ( w ) μ = 1 ∏ P 1 { g w ( x μ ) = ξ μ } , (26)
which is strictly positive almost surely, since a neighbourhood of the teacher is compatible. The uniform measure over the set of weights compatible with the training set is given by
d μ T P ( w ) = d μ ( w ) V N ( T P ) ∏ μ = 1 P 1 { g w ( x μ ) = ξ μ } . (27) \mathrm{d}\mu_{\mathcal{T}_P}(\boldsymbol{w})=\frac{\mathrm{d}\mu(\boldsymbol{w})}{V_N(\mathcal{T}_P)}\prod_{\mu=1}^{P}\mathbb{1}\{g_{\boldsymbol{w}}(\boldsymbol{x}^\mu)=\xi^\mu\}. \tag*{(27)} d μ T P ( w ) = V N ( T P ) d μ ( w ) μ = 1 ∏ P 1 { g w ( x μ ) = ξ μ } . (27)
The quenched entropy density is
ϕ ( α , λ ) = lim N → ∞ 1 N E ln V N (28) \phi(\alpha,\lambda)=\lim_{N\to\infty}\frac{1}{N}\mathbb{E}\ln V_N \tag*{(28)} ϕ ( α , λ ) = N → ∞ lim N 1 E ln V N (28)
(assuming the limit exists).
For fixed weights, let R N ( w , w ∗ ) = P x [ g w ( x ) ≠ g w ∗ ( x ) ] \mathcal{R}_N(w,w^\ast)=\mathbb{P}_x[g_w(x)\ne g_{w^\ast}(x)] R N ( w , w ∗ ) = P x [ g w ( x ) = g w ∗ ( x )] and r N = w ⋅ w ∗ / N r_N=w\cdot w^\ast/N r N = w ⋅ w ∗ / N . If r N → r r_N\to r r N → r and both vectors are delocalized, max j ∣ w j ∣ / N → 0 \max_j|w_j|/\sqrt{N}\to0 max j ∣ w j ∣/ N → 0 and max j ∣ w j ∗ ∣ / N → 0 \max_j|w_j^\ast|/\sqrt{N}\to0 max j ∣ w j ∗ ∣/ N → 0 , the joint central limit theorem (see Section B 1, equation (B13)) gives R N → ϵ λ ( r ) \mathcal{R}_N\to\epsilon_\lambda(r) R N → ϵ λ ( r ) , with
ϵ λ ( r ) = P [ s λ ( U ) ≠ s λ ( V ) ] , ( U , V ) centered Gaussian , E U 2 = E V 2 = 1 , E U V = r . (29) \epsilon_\lambda(r)=\mathbb{P}\left[s_\lambda(U)\ne s_\lambda(V)\right],\qquad(U,V)\text{ centered Gaussian},\ \mathbb{E}U^2=\mathbb{E}V^2=1,\ \mathbb{E}UV=r. \tag*{(29)} ϵ λ ( r ) = P [ s λ ( U ) = s λ ( V ) ] , ( U , V ) centered Gaussian , E U 2 = E V 2 = 1 , E U V = r . (29)
Delocalization holds with probability tending to one under μ \mu μ , and also for samples from μ T P \mu_{\mathrm{TP}} μ TP after averaging over the planted data (see subsection B 3). The risk of a student sampled from μ T P \mu_{\mathrm{TP}} μ TP is therefore
ϵ g , N = ∫ d μ T P ( w ) R N ( w , w ∗ ) = ∫ − 1 1 ϵ λ ( r ) d ν T P , w ∗ ( r ) + o ( 1 ) , (30) \epsilon_{g,N}=\int\mathrm{d}\mu_{\mathrm{TP}}(w)\,\mathcal{R}_N(w,w^\ast)=\int_{-1}^{1}\epsilon_\lambda(r)\,\mathrm{d}\nu_{\mathrm{TP},w^\ast}(r)+o(1), \tag*{(30)} ϵ g , N = ∫ d μ TP ( w ) R N ( w , w ∗ ) = ∫ − 1 1 ϵ λ ( r ) d ν TP , w ∗ ( r ) + o ( 1 ) , (30)
where ν T P , w ∗ \nu_{\mathrm{TP},w^\ast} ν TP , w ∗ is the push-forward of μ T P \mu_{\mathrm{TP}} μ TP under w ↦ w ⋅ w ∗ / N w\mapsto w\cdot w^\ast/N w ↦ w ⋅ w ∗ / N . If this overlap measure concentrates on r ⋆ ( α , λ ) r_\star(\alpha,\lambda) r ⋆ ( α , λ ) , then ϵ g = ϵ λ ( r ⋆ ) \epsilon_g=\epsilon_\lambda(r_\star) ϵ g = ϵ λ ( r ⋆ ) . At a coexistence point the limiting overlap measure may have two atoms whose weights are not fixed by the leading-order free entropy; we then report both one-sided limits.
Replica calculation
Here, we evaluate the expectation of the Gardner volume in the thermodynamic limit with the replica method, in which the pattern average reduces to an average over Gaussian local fields whose covariance is the replica overlap matrix. We impose replica symmetry (RS).
We use the replica method, consisting of starting from the identity
E ln V N = lim n → 0 1 n ln E V N n , (31) \mathbb{E}\ln V_N=\lim_{n\to0}\frac{1}{n}\ln\mathbb{E}V_N^n, \tag*{(31)} E ln V N = n → 0 lim n 1 ln E V N n , (31)
compute E V N n \mathbb{E}V_N^n E V N n for integer n n n , take N → ∞ N\to\infty N → ∞ at fixed α \alpha α , and use the result obtained as an analytic continuation to n → 0 n\to0 n → 0 . Regarding the teacher as replica 0, W 0 = w ∗ \mathbf{W}^0=w^\ast W 0 = w ∗ , W a = w a \mathbf{W}^a=w^a W a = w a (a = 1 , … , n a=1,\ldots,n a = 1 , … , n ), independence over patterns gives
E V N n = ∫ ∏ a = 0 n d μ ( W a ) [ A N , λ ( W ) ] P , (32) \mathbb{E}V_N^n=\int\prod_{a=0}^{n}\mathrm{d}\mu(\mathbf{W}^a)\,[\mathcal{A}_{N,\lambda}(\mathbf{W})]^P, \tag*{(32)} E V N n = ∫ a = 0 ∏ n d μ ( W a ) [ A N , λ ( W ) ] P , (32)
where
A N , λ ( W ) = E x ∏ a = 1 n Θ ( sin ( λ h 0 ) sin ( λ h a ) ) , h a = h ( W a , x ) = W a ⋅ x N . (33) \mathcal{A}_{N,\lambda}(\mathbf{W})=\mathbb{E}_x\prod_{a=1}^{n}\Theta\bigl(\sin(\lambda h_0)\sin(\lambda h_a)\bigr),\qquad h_a=h(\mathbf{W}^a,x)=\frac{\mathbf{W}^a\cdot x}{\sqrt{N}}. \tag*{(33)} A N , λ ( W ) = E x a = 1 ∏ n Θ ( sin ( λ h 0 ) sin ( λ h a ) ) , h a = h ( W a , x ) = N W a ⋅ x . (33)
The N N N components of the pattern x x x enter into A N , λ ( W ) \mathcal{A}_{N,\lambda}(\mathbf{W}) A N , λ ( W ) only through the n + 1 n+1 n + 1 “local fields” h = ( h 0 , h 1 , … , h n ) h=(h_0,h_1,\ldots,h_n) h = ( h 0 , h 1 , … , h n ) . For fixed weight vectors, the random pattern induces a joint distribution of the field vector which can be formally written in the form
ρ N ( h ∣ W ) : = E x ∏ a = 0 n δ ( h a − W a ⋅ x N ) , (34) \rho_N(h\mid\mathbf{W}):=\mathbb{E}_x\prod_{a=0}^{n}\delta\left(h_a-\frac{\mathbf{W}^a\cdot x}{\sqrt{N}}\right), \tag*{(34)} ρ N ( h ∣ W ) := E x a = 0 ∏ n δ ( h a − N W a ⋅ x ) , (34)
with equality to be understood in the distributional sense. The single-pattern contribution A N , λ ( W ) \mathcal{A}_{N,\lambda}(\mathbf{W}) A N , λ ( W ) in equation (B9) can then be rewritten exactly as
A N , λ ( W ) = ∫ R n + 1 d h ρ N ( h ∣ W ) ∏ a = 1 n Θ ( sin ( λ h 0 ) sin ( λ h a ) ) . (35) \mathcal{A}_{N,\lambda}(\mathbf{W})=\int_{\mathbb{R}^{n+1}}\mathrm{d}h\,\rho_N(h\mid\mathbf{W})\prod_{a=1}^{n}\Theta\bigl(\sin(\lambda h_0)\sin(\lambda h_a)\bigr). \tag*{(35)} A N , λ ( W ) = ∫ R n + 1 d h ρ N ( h ∣ W ) a = 1 ∏ n Θ ( sin ( λ h 0 ) sin ( λ h a ) ) . (35)
A standard computation (see Section C) shows that in the high-dimensional limit N → ∞ N\to\infty N → ∞ , ρ N ( h ∣ W ) \rho_N(h\mid\mathbf{W}) ρ N ( h ∣ W ) converges to a centered Gaussian distribution with a correlation matrix given by the overlap (or Gram) matrix
Q a b : = W a ⋅ W b N , a , b = 0 , 1 , … , n . (36) Q_{ab}:=\frac{\mathbf{W}^a\cdot\mathbf{W}^b}{N},\qquad a,b=0,1,\ldots,n. \tag*{(36)} Q ab := N W a ⋅ W b , a , b = 0 , 1 , … , n . (36)
Therefore
A N , λ ( W ) → Z n , λ ( Q ) = ∫ d γ Q ( h ) ∏ a = 1 n Θ ( sin ( λ h 0 ) sin ( λ h a ) ) , (37) \mathcal{A}_{N,\lambda}(\mathbf{W}) \to\mathcal{Z}_{n,\lambda}(Q) = \int\mathrm{d}\gamma_Q(h) \prod_{a=1}^{n} \Theta(\sin(\lambda h_0)\sin(\lambda h_a)), \tag*{(37)} A N , λ ( W ) → Z n , λ ( Q ) = ∫ d γ Q ( h ) a = 1 ∏ n Θ ( sin ( λ h 0 ) sin ( λ h a )) , (37)
with
d γ Q ( h ) : = exp ( − 1 2 h T Q − 1 h ) ( 2 π ) ( n + 1 ) / 2 ( det Q ) 1 / 2 d h . (38) \mathrm{d}\gamma_Q(h) := \frac{\exp\left(-\frac{1}{2}h^{\mathsf{T}}Q^{-1}h\right)}{(2\pi)^{(n+1)/2}(\det Q)^{1/2}}\mathrm{d}h. \tag*{(38)} d γ Q ( h ) := ( 2 π ) ( n + 1 ) /2 ( det Q ) 1/2 exp ( − 2 1 h T Q − 1 h ) d h . (38)
The resulting integrand depends on the weights only through their overlaps. We can therefore organize the integration by grouping all configurations that realize the same matrix Q Q Q . Their normalized volume is described by the geometric density
J N ( Q ) : = ∫ ∏ a = 0 n d μ ( W a ) ∏ 0 ≤ a < b ≤ n δ ( Q a b − W a ⋅ W b N ) . \mathcal{J}_N(Q) := \int\prod_{a=0}^{n}\mathrm{d}\mu(\mathbf{W}^a)\prod_{0\leq a<b\leq n}\delta\left(Q_{ab}-\frac{\mathbf{W}^a\cdot\mathbf{W}^b}{N}\right). J N ( Q ) := ∫ a = 0 ∏ n d μ ( W a ) 0 ≤ a < b ≤ n ∏ δ ( Q ab − N W a ⋅ W b ) .
This is the probability density of the overlap matrix under the product spherical measure. Only off-diagonal constraints appear in the product of delta functions, since the spherical measures already impose Q a a = 1 Q_{aa}=1 Q aa = 1 . Consequently,
E V N n ≡ ∫ Q d Q J N ( Q ) [ Z n , λ ( Q ) ] α N . \mathbb{E}V_N^n \equiv\int_{\mathcal{Q}}\mathrm{d}Q\,\mathcal{J}_N(Q)\left[\mathcal{Z}_{n,\lambda}(Q)\right]^{\alpha N}. E V N n ≡ ∫ Q d Q J N ( Q ) [ Z n , λ ( Q ) ] α N .
The standard Gram-matrix integration formula [32 Appendix B] gives, for Q > 0 Q>0 Q > 0 ,
J N ( Q ) = C N , n ( det Q ) ( N − n − 2 ) / 2 , \mathcal{J}_N(Q)=C_{N,n}(\det Q)^{(N-n-2)/2}, J N ( Q ) = C N , n ( det Q ) ( N − n − 2 ) /2 ,
where C N , n C_{N,n} C N , n is independent of Q Q Q and ln C N , n = O ( ln N ) \ln C_{N,n}=O(\ln N) ln C N , n = O ( ln N ) at fixed n n n . Thus at the leading contribution in the exponential rate:
1 N ln ( J N ( Q ) [ Z n , λ ( Q ) ] α N ) = 1 2 ln det Q + α ln Z n , λ ( Q ) + o ( 1 ) , (39) \frac{1}{N}\ln\left(\mathcal{J}_N(Q)\left[\mathcal{Z}_{n,\lambda}(Q)\right]^{\alpha N}\right)=\frac{1}{2}\ln\det Q+\alpha\ln\mathcal{Z}_{n,\lambda}(Q)+o(1), \tag*{(39)} N 1 ln ( J N ( Q ) [ Z n , λ ( Q ) ] α N ) = 2 1 ln det Q + α ln Z n , λ ( Q ) + o ( 1 ) , (39)
for each fixed positive-definite Q Q Q . Then a saddle-point approximation selects the largest exponential rate over the admissible overlap matrices, giving formally
lim N → ∞ 1 N ln E V N n = sup Q ≥ 0 , Q a a = 1 ( 1 2 ln det Q + α ln Z n , λ ( Q ) ) . (40) \lim_{N\to\infty}\frac{1}{N}\ln\mathbb{E}V_N^n=\sup_{\substack{Q\geq0,\,Q_{aa}=1}}\left(\frac{1}{2}\ln\det Q+\alpha\ln\mathcal{Z}_{n,\lambda}(Q)\right). \tag*{(40)} N → ∞ lim N 1 ln E V N n = Q ≥ 0 , Q aa = 1 sup ( 2 1 ln det Q + α ln Z n , λ ( Q ) ) . (40)
Replica-Symmetric ansatz
In this section, we specialize the search of the saddle point (B16) to the replica symmetric subspace, that is, we put all the student-student overlaps equal to q q q and all the teacher-student overlaps equal to r r r : ( Q R S ) 0 a = r (Q_{\mathrm{RS}})_{0a}=r ( Q RS ) 0 a = r and ( Q R S ) a b = q (Q_{\mathrm{RS}})_{ab}=q ( Q RS ) ab = q for 1 ≤ a < b ≤ n 1\leq a<b\leq n 1 ≤ a < b ≤ n . Using a Schur complement decomposition, the determinant is given by
det Q R S = ( 1 − q ) n − 1 ( 1 + ( n − 1 ) q − n r 2 ) = ( 1 − q ) n ( 1 + n q − r 2 1 − q ) , (41) \det Q_{\mathrm{RS}}=(1-q)^{n-1}\left(1+(n-1)q-nr^2\right)=(1-q)^n\left(1+n\frac{q-r^2}{1-q}\right), \tag*{(41)} det Q RS = ( 1 − q ) n − 1 ( 1 + ( n − 1 ) q − n r 2 ) = ( 1 − q ) n ( 1 + n 1 − q q − r 2 ) , (41)
and, in the limit n → 0 n\to0 n → 0 :
1 2 n ln det Q R S = 1 2 ln ( 1 − q ) + 1 2 q − r 2 1 − q + O ( n ) . (42) \frac{1}{2n}\ln\det Q_{\mathrm{RS}}=\frac{1}{2}\ln(1-q)+\frac{1}{2}\frac{q-r^2}{1-q}+O(n). \tag*{(42)} 2 n 1 ln det Q RS = 2 1 ln ( 1 − q ) + 2 1 1 − q q − r 2 + O ( n ) . (42)
For the pattern term, the identity Θ ( sin λ h 0 sin λ h a ) = Θ ( sin λ h 0 ) Θ ( sin λ h a ) + Θ ( − sin λ h 0 ) Θ ( − sin λ h a ) \Theta(\sin\lambda h_0\sin\lambda h_a)=\Theta(\sin\lambda h_0)\Theta(\sin\lambda h_a)+\Theta(-\sin\lambda h_0)\Theta(-\sin\lambda h_a) Θ ( sin λ h 0 sin λ h a ) = Θ ( sin λ h 0 ) Θ ( sin λ h a ) + Θ ( − sin λ h 0 ) Θ ( − sin λ h a ) and the invariance of γ Q \gamma_Q γ Q under h ↦ − h h\mapsto-h h ↦ − h give
Z n , λ = 2 ∫ d γ Q Θ ( sin λ h 0 ) ∏ a ≥ 1 Θ ( sin λ h a ) . (43) \mathcal{Z}_{n,\lambda}=2\int\mathrm{d}\gamma_Q\,\Theta(\sin\lambda h_0)\prod_{a\geq1}\Theta(\sin\lambda h_a). \tag*{(43)} Z n , λ = 2 ∫ d γ Q Θ ( sin λ h 0 ) a ≥ 1 ∏ Θ ( sin λ h a ) . (43)
For 0 < q < 1 0<q<1 0 < q < 1 and r 2 ≤ q r^2\leq q r 2 ≤ q , the Gaussian fields h \boldsymbol{h} h with correlation matrix Q R S Q_{\mathrm{RS}} Q RS admit the representation
h 0 = r q t + 1 − r 2 q y , h a = q t + 1 − q z a , t , y , z a i.i.d. N ( 0 , 1 ) , (44) h_0=\frac{r}{\sqrt{q}}t+\sqrt{1-\frac{r^2}{q}}\,y,\qquad h_a=\sqrt{q}\,t+\sqrt{1-q}\,z_a,\qquad t,y,z_a\ \text{i.i.d.}\ \mathcal{N}(0,1), \tag*{(44)} h 0 = q r t + 1 − q r 2 y , h a = q t + 1 − q z a , t , y , z a i.i.d. N ( 0 , 1 ) , (44)
whose explicit derivation is given in Appendix C 2. There we decompose the RS covariance matrix, remove the residual coupling between replicas with an auxiliary Gaussian variable, and rotate the two shared modes to obtain the single common variable t t t . Conditionally on t t t , all fields are independent, and
Z n , λ ( q , r ) = 2 ∫ D t χ λ ( q , r , t ) ψ λ ( q , t ) n , ψ λ ( q , t ) = p λ ( q t , 1 − q ) , χ λ ( q , r , t ) = p λ ( r t q , 1 − r 2 q ) , (45) Z_{n,\lambda}(q,r)=2\int\mathcal{D}t\,\chi_\lambda(q,r,t)\,\psi_\lambda(q,t)^n,\qquad\psi_\lambda(q,t)=p_\lambda\left(\sqrt{q}t,1-q\right),\qquad\chi_\lambda(q,r,t)=p_\lambda\left(\frac{rt}{\sqrt{q}},1-\frac{r^2}{q}\right), \tag*{(45)} Z n , λ ( q , r ) = 2 ∫ D t χ λ ( q , r , t ) ψ λ ( q , t ) n , ψ λ ( q , t ) = p λ ( q t , 1 − q ) , χ λ ( q , r , t ) = p λ ( q r t , 1 − q r 2 ) , (45)
in terms of the Gaussian-smoothed square wave. Its probabilistic definition applies for v ≥ 0 v\geq0 v ≥ 0 , while the series below requires v > 0 v>0 v > 0 :
p λ ( μ , v ) = E z ∼ N ( 0 , 1 ) Θ [ sin λ ( μ + v z ) ] = 1 2 + 2 π ∑ k = 0 ∞ sin ( ( 2 k + 1 ) λ μ ) 2 k + 1 e − ( 2 k + 1 ) 2 λ 2 v / 2 ( v > 0 ) . (46) p_\lambda(\mu,v)=\mathbb{E}_{z\sim\mathcal{N}(0,1)}\Theta\left[\sin\lambda\left(\mu+\sqrt{v}z\right)\right]=\frac{1}{2}+\frac{2}{\pi}\sum_{k=0}^{\infty}\frac{\sin\left((2k+1)\lambda\mu\right)}{2k+1}e^{-(2k+1)^2\lambda^2v/2}\qquad(v>0). \tag*{(46)} p λ ( μ , v ) = E z ∼ N ( 0 , 1 ) Θ [ sin λ ( μ + v z ) ] = 2 1 + π 2 k = 0 ∑ ∞ 2 k + 1 sin ( ( 2 k + 1 ) λ μ ) e − ( 2 k + 1 ) 2 λ 2 v /2 ( v > 0 ) . (46)
At q = r 2 > 0 q=r^2>0 q = r 2 > 0 , the teacher probability is evaluated with p λ ( μ , 0 ) = Θ ( sin λ μ ) p_\lambda(\mu,0)=\Theta(\sin\lambda\mu) p λ ( μ , 0 ) = Θ ( sin λ μ ) . The case q = r = 0 q=r=0 q = r = 0 is evaluated directly, since all fields are then independent and Z n , λ ( 0 , 0 ) = 2 − n Z_{n,\lambda}(0,0)=2^{-n} Z n , λ ( 0 , 0 ) = 2 − n . The series follows from the Fourier expansion of Θ ( sin x ) \Theta(\sin x) Θ ( sin x ) and E sin ( a ( μ + v z ) ) = sin ( a μ ) e − a 2 v / 2 \mathbb{E}\sin(a(\mu+\sqrt{v}z))=\sin(a\mu)e^{-a^2v/2} E sin ( a ( μ + v z )) = sin ( a μ ) e − a 2 v /2 ; it converges absolutely and uniformly in μ \mu μ for v > 0 v>0 v > 0 . Using ∫ D t χ λ = 1 / 2 \int\mathcal{D}t\,\chi_\lambda=1/2 ∫ D t χ λ = 1/2 (from p λ ( − μ , v ) = 1 − p λ ( μ , v ) p_\lambda(-\mu,v)=1-p_\lambda(\mu,v) p λ ( − μ , v ) = 1 − p λ ( μ , v ) ) and ψ n = 1 + n ln ψ + O ( n 2 ) \psi^n=1+n\ln\psi+O(n^2) ψ n = 1 + n ln ψ + O ( n 2 ) ,
ϕ R S ( α , λ ) = extr 0 ≤ r 2 ≤ q < 1 K λ ( q , r ; α ) , K λ ( q , r ; α ) = 1 2 ln ( 1 − q ) + q − r 2 2 ( 1 − q ) + 2 α ∫ D t χ λ ( q , r , t ) ln ψ λ ( q , t ) . (47) \phi_{\mathrm{RS}}(\alpha,\lambda)=\underset{0\leq r^2\leq q<1}{\operatorname{extr}}\ \mathcal{K}_\lambda(q,r;\alpha),\qquad\mathcal{K}_\lambda(q,r;\alpha)=\frac{1}{2}\ln(1-q)+\frac{q-r^2}{2(1-q)}+2\alpha\int\mathcal{D}t\,\chi_\lambda(q,r,t)\ln\psi_\lambda(q,t). \tag*{(47)} ϕ RS ( α , λ ) = 0 ≤ r 2 ≤ q < 1 extr K λ ( q , r ; α ) , K λ ( q , r ; α ) = 2 1 ln ( 1 − q ) + 2 ( 1 − q ) q − r 2 + 2 α ∫ D t χ λ ( q , r , t ) ln ψ λ ( q , t ) . (47)
The measure μ T P \mu_{\mathcal{T}_P} μ T P defined in Eq. (27) was introduced as the uniform measure on the version space. We now explain its Bayesian interpretation and derive the identities used in the RS reduction and in the information-theoretic interpretation of the learning curves. The Bayesian identities below are exact at finite N N N ; the additional assumptions needed to pass to the RS description will be stated separately.
Likelihood, evidence and posterior. The spherical measure μ \mu μ is the prior : it describes the teacher weights before any labels are observed. The inputs X X X are independent of the teacher. To distinguish a possible label sequence from the random labels ξ = ( ξ 1 , … , ξ P ) \boldsymbol{\xi}=(\xi^1,\ldots,\xi^P) ξ = ( ξ 1 , … , ξ P ) , let η ∈ { ± 1 } P \boldsymbol{\eta}\in\{\pm1\}^P η ∈ { ± 1 } P and write
T P ( X , η ) : = { ( x μ , η μ ) } μ = 1 P . (48) \mathcal{T}_P(X,\boldsymbol{\eta}):=\{(x^\mu,\eta^\mu)\}_{\mu=1}^{P}. \tag*{(48)} T P ( X , η ) := {( x μ , η μ ) } μ = 1 P . (48)
Thus the observed training set is T P = T P ( X , ξ ) \mathcal{T}_P=\mathcal{T}_P(X,\boldsymbol{\xi}) T P = T P ( X , ξ ) . Given a candidate teacher w \boldsymbol{w} w , the probability of the label sequence η \boldsymbol{\eta} η , called its likelihood , is
P ( ξ = η ∣ X , w ∗ = w ) = ∏ μ = 1 P 1 { g w ( x μ ) = η μ } . (49) \mathbb{P}(\boldsymbol{\xi}=\boldsymbol{\eta}\mid X,\boldsymbol{w}^*=\boldsymbol{w})=\prod_{\mu=1}^{P}\mathbf{1}\{g_{\boldsymbol{w}}(x^\mu)=\eta^\mu\}. \tag*{(49)} P ( ξ = η ∣ X , w ∗ = w ) = μ = 1 ∏ P 1 { g w ( x μ ) = η μ } . (49)
It equals one when all labels are reproduced and zero otherwise, because the labeling rule is deterministic. Integrating over the teacher prior gives the probability of those labels at fixed inputs:
P ( ξ = η ∣ X ) = ∫ d μ ( w ) ∏ μ = 1 P 1 { g w ( x μ ) = η μ } = V N ( T P ( X , η ) ) . (50) \mathbb{P}(\boldsymbol{\xi}=\boldsymbol{\eta}\mid X)=\int d\mu(\boldsymbol{w})\prod_{\mu=1}^{P}\mathbf{1}\{g_{\boldsymbol{w}}(x^\mu)=\eta^\mu\}=V_N\bigl(\mathcal{T}_P(X,\boldsymbol{\eta})\bigr). \tag*{(50)} P ( ξ = η ∣ X ) = ∫ d μ ( w ) μ = 1 ∏ P 1 { g w ( x μ ) = η μ } = V N ( T P ( X , η ) ) . (50)
This marginal probability is the evidence . The same Gardner volume therefore measures both the fraction of compatible weights and the probability assigned to the observed label sequence under the uniform prior on the teacher weights.
Bayes’ rule gives the conditional distribution of the teacher after observing T P \mathcal{T}_P T P . For every measurable subset A A A of the weight sphere,
P ( w ∗ ∈ A ∣ T P ) = 1 V N ( T P ) ∫ A d μ ( w ) ∏ μ = 1 P 1 { g w ( x μ ) = ξ μ } = μ T P ( A ) . (51) \mathbb{P}(\boldsymbol{w}^*\in A\mid\mathcal{T}_P)=\frac{1}{V_N(\mathcal{T}_P)}\int_A d\mu(\boldsymbol{w})\prod_{\mu=1}^{P}\mathbf{1}\{g_{\boldsymbol{w}}(x^\mu)=\xi^\mu\}=\mu_{\mathcal{T}_P}(A). \tag*{(51)} P ( w ∗ ∈ A ∣ T P ) = V N ( T P ) 1 ∫ A d μ ( w ) μ = 1 ∏ P 1 { g w ( x μ ) = ξ μ } = μ T P ( A ) . (51)
Thus the posterior is exactly the already defined measure μ T P \mu_{T_P} μ T P , the measure defining the version space, and a student sampled from this measure is what has been called a Gibbs student . In this inference model the student then uses the same prior and likelihood that generated the data, and this matched setting is called Bayes-optimal inference . The Nishimori identity is a consequence of this matched setting [21 , 22 , 23 ] , and its relevant content here is the equality of conditional distributions in (B27). We illustrate the consequences of this identity in the following.
For a fixed training set, let w 1 , … , w k w^1,\ldots,w^k w 1 , … , w k be independent samples from μ T P \mu_{T_P} μ T P . We denote their conditional average by brackets:
⟨ O ( w 1 , … , w k ) ⟩ T P : = ∫ ∏ a = 1 k d μ T P ( w a ) O ( w 1 , … , w k ) . (52) \left\langle O(w^1,\ldots,w^k)\right\rangle_{T_P}:=\int\prod_{a=1}^{k}\mathrm{d}\mu_{T_P}(w^a)\,O(w^1,\ldots,w^k). \tag*{(52)} ⟨ O ( w 1 , … , w k ) ⟩ T P := ∫ a = 1 ∏ k d μ T P ( w a ) O ( w 1 , … , w k ) . (52)
If the observable also contains w ∗ w^* w ∗ , the brackets integrate only the student variables, keeping the teacher fixed. A further expectation can be taken on this quantity, which we denote by E \mathbb{E} E , when we want to take averages over the teacher and the training inputs, with the labels generated by the teacher. For quantities depending only on T P T_P T P , this is equivalently the average E T P \mathbb{E}_{T_P} E T P over training sets.
By Eq. (51) , conditioned on T P T_P T P the teacher also has law μ T P \mu_{T_P} μ T P . It is conditionally independent of the students sampled from μ T P \mu_{T_P} μ T P , so their joint conditional law is the product of k + 1 k+1 k + 1 copies of μ T P \mu_{T_P} μ T P . The teacher can therefore be exchanged with an additional posterior sample. For every bounded observable O O O , this gives the Nishimori identity
E ⟨ O ( w ∗ , w 1 , … , w k ; T P ) ⟩ T P = E T P ⟨ O ( w k + 1 , w 1 , … , w k ; T P ) ⟩ T P . (53) \mathbb{E}\left\langle O(w^*,w^1,\ldots,w^k;T_P)\right\rangle_{T_P}=\mathbb{E}_{T_P}\left\langle O(w^{k+1},w^1,\ldots,w^k;T_P)\right\rangle_{T_P}. \tag*{(53)} E ⟨ O ( w ∗ , w 1 , … , w k ; T P ) ⟩ T P = E T P ⟨ O ( w k + 1 , w 1 , … , w k ; T P ) ⟩ T P . (53)
Indeed, conditioning the left-hand side on T P T_P T P integrates the teacher against μ T P \mu_{T_P} μ T P as well; renaming that integration variable w k + 1 w^{k+1} w k + 1 gives the right-hand side.
Choosing any bounded function f f f of the overlap gives
E ⟨ f ( w ∗ ⋅ w 1 N ) ⟩ T P = E ⟨ f ( w 2 ⋅ w 1 N ) ⟩ T P . (54) \mathbb{E}\left\langle f\left(\frac{w^*\cdot w^1}{N}\right)\right\rangle_{T_P}=\mathbb{E}\left\langle f\left(\frac{w^2\cdot w^1}{N}\right)\right\rangle_{T_P}. \tag*{(54)} E ⟨ f ( N w ∗ ⋅ w 1 ) ⟩ T P = E ⟨ f ( N w 2 ⋅ w 1 ) ⟩ T P . (54)
Hence the teacher–student and student–student overlaps have the same disorder-averaged distribution. However, this does not assert equality of the overlaps for individual weight vectors. Moreover, conditional independence of two posterior samples gives
1 N E ⟨ w ∗ ⋅ ⟨ w ⟩ T P ⟩ T P = 1 N E ⟨ w 1 ⋅ w 2 ⟩ T P = 1 N E ∥ ⟨ w ⟩ T P ∥ 2 ≥ 0 , (55) \frac{1}{N}\mathbb{E}\left\langle w^*\cdot\langle w\rangle_{T_P}\right\rangle_{T_P}=\frac{1}{N}\mathbb{E}\langle w^1\cdot w^2\rangle_{T_P}=\frac{1}{N}\mathbb{E}\left\|\langle w\rangle_{T_P}\right\|^2\ge0, \tag*{(55)} N 1 E ⟨ w ∗ ⋅ ⟨ w ⟩ T P ⟩ T P = N 1 E ⟨ w 1 ⋅ w 2 ⟩ T P = N 1 E ∥ ⟨ w ⟩ T P ∥ 2 ≥ 0 , (55)
where ⟨ w ⟩ T P = ∫ d μ T P ( w ) w \langle w\rangle_{T_P}=\int\mathrm{d}\mu_{T_P}(w)\,w ⟨ w ⟩ T P = ∫ d μ T P ( w ) w is the posterior mean. If the two overlaps concentrate on deterministic values r r r and q q q , as assumed in the RS description, Eqs. (54) and (55) imply r = q ≥ 0 r=q\ge0 r = q ≥ 0 . However, the identity itself does not establish overlap concentration, uniqueness of an equilibrium overlap, or stability against replica-symmetry breaking. Equation (B31) also explains the relation between the averaged posterior-mean and posterior-sample overlaps used in Appendix F. Since ∥ w ∗ ∥ 2 = N \lVert w^*\rVert^2=N ∥ w ∗ ∥ 2 = N , it gives
1 N E ∥ w ∗ − ⟨ w ⟩ T P ∥ 2 = 1 − 1 N E ∥ ⟨ w ⟩ T P ∥ 2 . (56) \frac{1}{N}\mathbb{E}\left\|w^*-\langle w\rangle_{T_P}\right\|^2=1-\frac{1}{N}\mathbb{E}\left\|\langle w\rangle_{T_P}\right\|^2. \tag*{(56)} N 1 E ∥ w ∗ − ⟨ w ⟩ T P ∥ 2 = 1 − N 1 E ∥ ⟨ w ⟩ T P ∥ 2 . (56)
A second consequence, obtained by averaging Eq. (51) , is
E T P μ T P ( A ) = μ ( A ) (57) \mathbb{E}_{T_P}\mu_{T_P}(A)=\mu(A) \tag*{(57)} E T P μ T P ( A ) = μ ( A ) (57)
for every measurable set A A A independent of the data. Thus, after averaging over training sets, a posterior sample has the original spherical law. In particular, the delocalization property of the spherical weights also holds for posterior samples in the planted ensemble. Together with the joint Gaussian limit in Appendix C, this justifies the use of ϵ λ ( r ) \epsilon_\lambda(r) ϵ λ ( r ) in Eq. (30) ; its remainder vanishes in probability and in mean absolute value over the teacher and training data. The conditional exchangeability also explains why the teacher is a typical posterior sample, as used in Appendix § 1.15 .
Reduction of the RS potential. We now apply q = r q=r q = r to the RS functional K λ ( q , r ; α ) \mathcal{K}_\lambda(q,r;\alpha) K λ ( q , r ; α ) of Eq. (47) . For 0 < q < 1 0<q<1 0 < q < 1 , the definitions in Eq. (45) give
χ λ ( q , q , t ) = ψ λ ( q , t ) , ∂ r χ λ ( q , r , t ) ∣ r = q = 2 ∂ q ψ λ ( q , t ) , ∂ q χ λ ( q , r , t ) ∣ r = q = − ∂ q ψ λ ( q , t ) . (58) \chi_\lambda(q,q,t)=\psi_\lambda(q,t),\qquad\left.\partial_r\chi_\lambda(q,r,t)\right|_{r=q}=2\partial_q\psi_\lambda(q,t),\qquad\left.\partial_q\chi_\lambda(q,r,t)\right|_{r=q}=-\partial_q\psi_\lambda(q,t). \tag*{(58)} χ λ ( q , q , t ) = ψ λ ( q , t ) , ∂ r χ λ ( q , r , t ) ∣ r = q = 2 ∂ q ψ λ ( q , t ) , ∂ q χ λ ( q , r , t ) ∣ r = q = − ∂ q ψ λ ( q , t ) . (58)
The partial derivatives are taken before setting r = q r=q r = q . For example,
∂ q ψ λ ( q , t ) = t 2 q ∂ u p λ ( q t , 1 − q ) − ∂ v p λ ( q t , 1 − q ) . (59) \partial_q\psi_\lambda(q,t)=\frac{t}{2\sqrt{q}}\partial_u p_\lambda(\sqrt{q}t,1-q)-\partial_v p_\lambda(\sqrt{q}t,1-q). \tag*{(59)} ∂ q ψ λ ( q , t ) = 2 q t ∂ u p λ ( q t , 1 − q ) − ∂ v p λ ( q t , 1 − q ) . (59)
and differentiating the two arguments of χ λ \chi_\lambda χ λ gives Eq. (58) . The symmetry ψ λ ( q , − t ) = 1 − ψ λ ( q , t ) \psi_\lambda(q,-t)=1-\psi_\lambda(q,t) ψ λ ( q , − t ) = 1 − ψ λ ( q , t ) implies
∫ D t ψ λ ( q , t ) = 1 2 , ∫ D t ∂ q ψ λ ( q , t ) = 0. (60) \int Dt\,\psi_\lambda(q,t)=\frac{1}{2},\qquad\int Dt\,\partial_q\psi_\lambda(q,t)=0. \tag*{(60)} ∫ D t ψ λ ( q , t ) = 2 1 , ∫ D t ∂ q ψ λ ( q , t ) = 0. (60)
Consequently,
∂ r K λ ( q , r ; α ) ∣ r = q = − q 1 − q + 4 α ∫ D t ∂ q ψ λ ( q , t ) ln ψ λ ( q , t ) , \left.\partial_r K_\lambda(q,r;\alpha)\right|_{r=q}=-\frac{q}{1-q}+4\alpha\int Dt\,\partial_q\psi_\lambda(q,t)\ln\psi_\lambda(q,t), ∂ r K λ ( q , r ; α ) ∣ r = q = − 1 − q q + 4 α ∫ D t ∂ q ψ λ ( q , t ) ln ψ λ ( q , t ) ,
∂ q K λ ( q , r ; α ) ∣ r = q = − 1 2 ∂ r K λ ( q , r ; α ) ∣ r = q . (61) \left.\partial_q K_\lambda(q,r;\alpha)\right|_{r=q}=-\frac{1}{2}\left.\partial_r K_\lambda(q,r;\alpha)\right|_{r=q}. \tag*{(61)} ∂ q K λ ( q , r ; α ) ∣ r = q = − 2 1 ∂ r K λ ( q , r ; α ) ∣ r = q . (61)
Thus both stationarity equations reduce to the same condition. Writing the common overlap as r r r , it reads
r 1 − r = 4 α ∫ D t ∂ r ψ λ ( r , t ) ln ψ λ ( r , t ) . (62) \frac{r}{1-r}=4\alpha\int Dt\,\partial_r\psi_\lambda(r,t)\ln\psi_\lambda(r,t). \tag*{(62)} 1 − r r = 4 α ∫ D t ∂ r ψ λ ( r , t ) ln ψ λ ( r , t ) . (62)
This is also the stationarity condition of F λ ( r ; α ) = K λ ( r , r ; α ) F_\lambda(r;\alpha)=K_\lambda(r,r;\alpha) F λ ( r ; α ) = K λ ( r , r ; α ) , because its derivative is the sum of the two partial derivatives in Eq. (61) . Explicitly,
F λ ( r ; α ) = 1 2 ln ( 1 − r ) + r 2 + 2 α I λ ( r ) , F_\lambda(r;\alpha)=\frac{1}{2}\ln(1-r)+\frac{r}{2}+2\alpha I_\lambda(r), F λ ( r ; α ) = 2 1 ln ( 1 − r ) + 2 r + 2 α I λ ( r ) ,
I λ ( r ) = ∫ D t ψ λ ( r , t ) ln ψ λ ( r , t ) = − 1 2 ∫ D t H 2 ( ψ λ ( r , t ) ) , (63) I_\lambda(r)=\int Dt\,\psi_\lambda(r,t)\ln\psi_\lambda(r,t)=-\frac{1}{2}\int Dt\,H_2(\psi_\lambda(r,t)), \tag*{(63)} I λ ( r ) = ∫ D t ψ λ ( r , t ) ln ψ λ ( r , t ) = − 2 1 ∫ D t H 2 ( ψ λ ( r , t )) , (63)
where H 2 ( p ) = − p ln p − ( 1 − p ) ln ( 1 − p ) H_2(p)=-p\ln p-(1-p)\ln(1-p) H 2 ( p ) = − p ln p − ( 1 − p ) ln ( 1 − p ) , and the last equality again uses the symmetry under t ↦ − t t\mapsto-t t ↦ − t . This is Eq. (11) . Within the RS variational prescription, equilibrium is selected by the global maximum,
ϕ R S ( α , λ ) = max 0 ≤ r < 1 F λ ( r ; α ) , r ⋆ ∈ arg max 0 ≤ r < 1 F λ ( r ; α ) , (64) \phi_{\mathrm{RS}}(\alpha,\lambda)=\max_{0\le r<1}F_\lambda(r;\alpha),\qquad r_\star\in\arg\max_{0\le r<1}F_\lambda(r;\alpha), \tag*{(64)} ϕ RS ( α , λ ) = 0 ≤ r < 1 max F λ ( r ; α ) , r ⋆ ∈ arg 0 ≤ r < 1 max F λ ( r ; α ) , (64)
not by continuation of a stationary root. This prescription and the replica calculation remain distinct from the exact finite-N N N Nishimori identity. Since F λ ( 0 ; α ) = − α ln 2 F_\lambda(0;\alpha)=-\alpha\ln2 F λ ( 0 ; α ) = − α ln 2 , the geometric term is nonpositive and H 2 ≥ 0 H_2\ge0 H 2 ≥ 0 , the RS result satisfies − α ln 2 ≤ ϕ R S ≤ 0 -\alpha\ln2\le\phi_{\mathrm{RS}}\le0 − α ln 2 ≤ ϕ RS ≤ 0 .
Information carried by the training labels. For discrete labels, the conditional Shannon entropy is the average uncertainty about the label sequence when the inputs are known. Using natural logarithms, it is measured in nats. By Eq. (50) ,
H ( ξ ∣ X ) = − E X ∑ η ∈ { ± 1 } P P ( T P ( X , η ) ) ln V N ( T P ( X , η ) ) = − E ln V N ( T P ) . (65) H(\xi\mid X)=-\mathbb{E}_X\sum_{\eta\in\{\pm1\}^P}P(\mathcal{T}_P(X,\eta))\ln V_N(\mathcal{T}_P(X,\eta))
=-\mathbb{E}\ln V_N(\mathcal{T}_P). \tag*{(65)} H ( ξ ∣ X ) = − E X η ∈ { ± 1 } P ∑ P ( T P ( X , η )) ln V N ( T P ( X , η )) = − E ln V N ( T P ) . (65)
The second equality averages the log-volume over the labels actually generated by the teacher, with their conditional probabilities from Eq. (50) .
The conditional mutual information measures how much observing the labels reveals about the teacher when X X X is known. Its entropy identity is
I ( w ∗ ; ξ ∣ X ) = H ( ξ ∣ X ) − H ( ξ ∣ w ∗ , X ) = H ( ξ ∣ X ) , (66) I(w^\ast;\xi\mid X)=H(\xi\mid X)-H(\xi\mid w^\ast,X)=H(\xi\mid X), \tag*{(66)} I ( w ∗ ; ξ ∣ X ) = H ( ξ ∣ X ) − H ( ξ ∣ w ∗ , X ) = H ( ξ ∣ X ) , (66)
because the labels are determined by ( w ∗ , X ) (w^\ast,X) ( w ∗ , X ) . Introducing the finite-size counterpart of Eq. (28) ,
ϕ N , P ( λ ) : = 1 N E ln V N ( T P ) = − 1 N H ( ξ ∣ X ) = − 1 N I ( w ∗ ; ξ ∣ X ) , (67) \phi_{N,P}(\lambda):=\frac{1}{N}\mathbb{E}\ln V_N(\mathcal{T}_P)=-\frac{1}{N}H(\xi\mid X)=-\frac{1}{N}I(w^\ast;\xi\mid X), \tag*{(67)} ϕ N , P ( λ ) := N 1 E ln V N ( T P ) = − N 1 H ( ξ ∣ X ) = − N 1 I ( w ∗ ; ξ ∣ X ) , (67)
we obtain, in the proportional limit P / N → α P/N\to\alpha P / N → α ,
ϕ ( α , λ ) = − lim N → ∞ P / N → α 1 N I ( w ∗ ; ξ ∣ X ) , − α ln 2 ≤ ϕ ( α , λ ) ≤ 0 , ϕ ( 0 , λ ) = 0 , (68) \phi(\alpha,\lambda)=-\lim_{\substack{N\to\infty\\P/N\to\alpha}}\frac{1}{N}I(w^\ast;\xi\mid X),\qquad-\alpha\ln2\le\phi(\alpha,\lambda)\le0,\qquad\phi(0,\lambda)=0, \tag*{(68)} ϕ ( α , λ ) = − N → ∞ P / N → α lim N 1 I ( w ∗ ; ξ ∣ X ) , − α ln 2 ≤ ϕ ( α , λ ) ≤ 0 , ϕ ( 0 , λ ) = 0 , (68)
assuming the limit exists. The bounds follow from 0 ≤ I ( w ∗ ; ξ ∣ X ) ≤ P ln 2 0\le I(w^\ast;\xi\mid X)\le P\ln2 0 ≤ I ( w ∗ ; ξ ∣ X ) ≤ P ln 2 , since each binary label carries at most ln 2 \ln2 ln 2 nats. Thus − ϕ -\phi − ϕ measures the information about the teacher supplied by the labels per weight. The nonpositivity of ϕ \phi ϕ is consistent with its definition as the logarithm of a normalized volume; the associated Shannon entropy and mutual information are nonnegative.
Prediction of a fresh label and Gibbs generalization. Let x P + 1 \boldsymbol{x}^{P+1} x P + 1 be a fresh input, independent of the teacher and of the training inputs, and let ξ P + 1 = g w ∗ ( x P + 1 ) \xi^{P+1}=g_{\boldsymbol{w}^{*}}(\boldsymbol{x}^{P+1}) ξ P + 1 = g w ∗ ( x P + 1 ) be its teacher-generated label. The posterior predictive probability of a positive label is
π T P ( x ) : = ∫ d μ T P ( w ) 1 { g w ( x ) = + 1 } , P ( ξ P + 1 = + 1 ∣ T P , x P + 1 ) = π T P ( x P + 1 ) . (69) \pi_{\mathcal{T}_{P}}(\boldsymbol{x}):=\int\mathrm{d}\mu_{\mathcal{T}_{P}}(\boldsymbol{w})\,\mathbf{1}\{g_{\boldsymbol{w}}(\boldsymbol{x})=+1\},\qquad\mathbb{P}(\xi^{P+1}=+1\mid\mathcal{T}_{P},\boldsymbol{x}^{P+1})=\pi_{\mathcal{T}_{P}}(\boldsymbol{x}^{P+1}). \tag*{(69)} π T P ( x ) := ∫ d μ T P ( w ) 1 { g w ( x ) = + 1 } , P ( ξ P + 1 = + 1 ∣ T P , x P + 1 ) = π T P ( x P + 1 ) . (69)
Here π T P \pi_{\mathcal{T}_{P}} π T P depends on the actual training set; it is distinct from the scalar Gaussian probability ψ λ \psi_{\lambda} ψ λ used in the RS calculation. Its average binary entropy gives the uncertainty about the fresh label:
H ( ξ P + 1 ∣ T P , x P + 1 ) = E T P , x P + 1 H 2 ( π T P ( x P + 1 ) ) . (70) H(\xi^{P+1}\mid\mathcal{T}_{P},\boldsymbol{x}^{P+1})=\mathbb{E}_{\mathcal{T}_{P},\boldsymbol{x}^{P+1}}H_{2}\bigl(\pi_{\mathcal{T}_{P}}(\boldsymbol{x}^{P+1})\bigr). \tag*{(70)} H ( ξ P + 1 ∣ T P , x P + 1 ) = E T P , x P + 1 H 2 ( π T P ( x P + 1 ) ) . (70)
This conditional entropy already includes the average over the variables after the conditioning bar; it is a number, rather than an entropy for one fixed training set.
The chain rule makes its relation to the information gained from one more example explicit:
I ( w ∗ ; ( ξ , ξ P + 1 ) ∣ X , x P + 1 ) − I ( w ∗ ; ξ ∣ X ) = I ( w ∗ ; ξ P + 1 ∣ T P , x P + 1 ) = H ( ξ P + 1 ∣ T P , x P + 1 ) . (71) I(\boldsymbol{w}^{*};(\boldsymbol{\xi},\xi^{P+1})\mid X,\boldsymbol{x}^{P+1})-I(\boldsymbol{w}^{*};\boldsymbol{\xi}\mid X)=I(\boldsymbol{w}^{*};\xi^{P+1}\mid\mathcal{T}_{P},\boldsymbol{x}^{P+1})=H(\xi^{P+1}\mid\mathcal{T}_{P},\boldsymbol{x}^{P+1}). \tag*{(71)} I ( w ∗ ; ( ξ , ξ P + 1 ) ∣ X , x P + 1 ) − I ( w ∗ ; ξ ∣ X ) = I ( w ∗ ; ξ P + 1 ∣ T P , x P + 1 ) = H ( ξ P + 1 ∣ T P , x P + 1 ) . (71)
In the first equality, independence of x P + 1 \boldsymbol{x}^{P+1} x P + 1 means that conditioning additionally on this input does not change the information in the first P P P labels. In the second, the fresh label is determined once the teacher and its input are known. Combining Eq. (71) with Eq. (67) gives the exact finite-size increment
− N [ ϕ N , P + 1 ( λ ) − ϕ N , P ( λ ) ] = H ( ξ P + 1 ∣ T P , x P + 1 ) . (72) -N\left[\phi_{N,P+1}(\lambda)-\phi_{N,P}(\lambda)\right]=H(\xi^{P+1}\mid\mathcal{T}_{P},\boldsymbol{x}^{P+1}). \tag*{(72)} − N [ ϕ N , P + 1 ( λ ) − ϕ N , P ( λ ) ] = H ( ξ P + 1 ∣ T P , x P + 1 ) . (72)
To pass from this increment to a derivative, note that conditioning on another training example can only reduce the average predictive entropy. Exchangeability of fresh examples therefore gives
H ( ξ P + 2 ∣ T P + 1 , x P + 2 ) ≤ H ( ξ P + 2 ∣ T P , x P + 2 ) = H ( ξ P + 1 ∣ T P , x P + 1 ) . (73) \begin{aligned}
H(\xi^{P+2}\mid\mathcal{T}_{P+1},\boldsymbol{x}^{P+2})\le H(\xi^{P+2}\mid\mathcal{T}_{P},\boldsymbol{x}^{P+2}) \\
&=H(\xi^{P+1}\mid\mathcal{T}_{P},\boldsymbol{x}^{P+1}). \tag*{(73)}
\end{aligned} H ( ξ P + 2 ∣ T P + 1 , x P + 2 ) ≤ H ( ξ P + 2 ∣ T P , x P + 2 ) = H ( ξ P + 1 ∣ T P , x P + 1 ) . (73)
Consequently, the piecewise-linear interpolation of ϕ N , P ( λ ) \phi_{N,P}(\lambda) ϕ N , P ( λ ) in the load P / N P/N P / N is convex. At every differentiability point α > 0 \alpha>0 α > 0 of its limiting function, the slopes converge to the limiting derivative: each slope is bounded between the neighboring secant slopes, whose limits approach that derivative. Thus
− ∂ α ϕ ( α , λ ) = lim N → ∞ P / N → α H ( ξ P + 1 ∣ T P , x P + 1 ) . (74) -\partial_{\alpha}\phi(\alpha,\lambda)=\lim_{\substack{N\to\infty\\P/N\to\alpha}}H(\xi^{P+1}\mid\mathcal{T}_{P},\boldsymbol{x}^{P+1}). \tag*{(74)} − ∂ α ϕ ( α , λ ) = N → ∞ P / N → α lim H ( ξ P + 1 ∣ T P , x P + 1 ) . (74)
This is the predictive-entropy interpretation used in the main text.
For the RS prediction, differentiating the maximizing value in Eq. (64) along a smooth equilibrium branch gives
− ∂ α ϕ R S ( α , λ ) = ∫ D t H 2 ( ψ λ ( r ⋆ ( α , λ ) , t ) ) . (75) -\partial_{\alpha}\phi_{\mathrm{RS}}(\alpha,\lambda)=\int\mathcal{D}t\,H_{2}\bigl(\psi_{\lambda}(r_{\star}(\alpha,\lambda),t)\bigr). \tag*{(75)} − ∂ α ϕ RS ( α , λ ) = ∫ D t H 2 ( ψ λ ( r ⋆ ( α , λ ) , t ) ) . (75)
The derivative through r ⋆ r_{\star} r ⋆ vanishes by stationarity. At coexistence, the two one-sided derivatives are evaluated at the corresponding maximizing overlaps. Their difference gives the RS prediction for the drop in predictive uncertainty discussed in Appendix § 1.12 . Equations (B43) and (B50) concern the exact model, whereas Eq. (75) is its replica-symmetric prediction.
Finally, conditioned on T P \mathcal{T}_{P} T P and a fresh input, the teacher and a Gibbs student give independent labels, each positive with probability π T P ( x ) \pi_{\mathcal{T}_{P}}(\boldsymbol{x}) π T P ( x ) . Their disagreement probability is therefore 2 π T P ( x ) [ 1 − π T P ( x ) ] 2\pi_{\mathcal{T}_{P}}(\boldsymbol{x})[1-\pi_{\mathcal{T}_{P}}(\boldsymbol{x})] 2 π T P ( x ) [ 1 − π T P ( x )] , so
E ϵ g , N = 2 E T P , x P + 1 [ π T P ( x P + 1 ) ( 1 − π T P ( x P + 1 ) ) ] . (76) \mathbb{E}\epsilon_{g,N}=2\mathbb{E}_{\mathcal{T}_{P},\boldsymbol{x}^{P+1}}\left[\pi_{\mathcal{T}_{P}}(\boldsymbol{x}^{P+1})\left(1-\pi_{\mathcal{T}_{P}}(\boldsymbol{x}^{P+1})\right)\right]. \tag*{(76)} E ϵ g , N = 2 E T P , x P + 1 [ π T P ( x P + 1 ) ( 1 − π T P ( x P + 1 ) ) ] . (76)
This is the error of a single posterior sample, averaged over the planted data. The Bayes-optimal classifier for binary classification instead chooses the more probable label and has conditional error min { π T P ( x ) , 1 − π T P ( x ) } \min\{\pi_{\mathcal{T}_{P}}(\boldsymbol{x}),1-\pi_{\mathcal{T}_{P}}(\boldsymbol{x})\} min { π T P ( x ) , 1 − π T P ( x )} . Thus the matched Bayesian setting does not identify the Gibbs error with the error of the posterior majority vote; the learning curves in this paper concern the former.
Remark 1 (Relation to generalized linear models). For a Gaussian prior N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) on the weights, the Bayes-optimal replica formula for generalized linear models [24 ] contains the prior contribution inf r ^ ≥ 0 { 1 2 [ r ^ − ln ( 1 + r ^ ) ] − 1 2 r ^ r } \inf_{\hat r\geq0}\left\{\frac{1}{2}[\hat r-\ln(1+\hat r)]-\frac{1}{2}\hat r r\right\} inf r ^ ≥ 0 { 2 1 [ r ^ − ln ( 1 + r ^ )] − 2 1 r ^ r } . For 0 ≤ r < 1 0\leq r<1 0 ≤ r < 1 , the minimum is attained at r ^ = r / ( 1 − r ) \hat r=r/(1-r) r ^ = r / ( 1 − r ) and equals 1 2 [ ln ( 1 − r ) + r ] \frac{1}{2}[\ln(1-r)+r] 2 1 [ ln ( 1 − r ) + r ] . The channel term for y = s λ ( z ) y=s_{\lambda}(z) y = s λ ( z ) equals 2 λ χ λ ( r ) 2\lambda\chi_{\lambda}(r) 2 λ χ λ ( r ) . Hence Eq. (63) coincides with that formula, which is a theorem for Gaussian inputs under regularity assumptions on the channel [24 ] . The deterministic, discontinuous channel s λ s_{\lambda} s λ and the Rademacher inputs used here are not directly covered.
Joint distribution of the local fields
Gaussian limit of the local fields
The convergence of ρ N ( h ∣ W ) \rho_N(h|\mathbf{W}) ρ N ( h ∣ W ) to the Gaussian measure (B14) is pretty standard in the literature [15 , 16 ] . We present here for completeness a self-sufficient re-derivation. Fix the number n n n of replicas and a sequence of weight vectors whose overlap matrices converge to Q \mathbf{Q} Q . Write H a ( x ∣ W ) = W a ⋅ x / N H_a(\mathbf{x} \mid\mathbf{W}) = \mathbf{W}^a \cdot\mathbf{x}/\sqrt{N} H a ( x ∣ W ) = W a ⋅ x / N for the random local fields. Let us consider the characteristic function
φ N ( k ∣ W ) : = ∫ d h e i k ⋅ h ρ N ( h ∣ W ) , (77) \varphi_N(\mathbf{k}|\mathbf{W}) := \int\mathrm{d}h\, e^{i\mathbf{k}\cdot\mathbf{h}}\rho_N(\mathbf{h}|\mathbf{W}), \tag*{(77)} φ N ( k ∣ W ) := ∫ d h e i k ⋅ h ρ N ( h ∣ W ) , (77)
which can be computed explicitly using (B10):
φ N ( k ∣ W ) = E x ∫ R n + 1 d h e i k ⋅ h ∏ a = 0 n δ ( h a − H a ( x ∣ W ) ) = E x e i k ⋅ H ( x ∣ W ) = E x exp ( i N ∑ j = 1 N x j ∑ a = 0 n k a W j a ) = ∏ j = 1 N cos ( 1 N ∑ a = 0 n k a W j a ) . (78) \begin{aligned}
\varphi_N(\mathbf{k}|\mathbf{W}) &= \mathbb{E}_{\mathbf{x}}\int_{\mathbb{R}^{n+1}}\mathrm{d}h\,e^{i\mathbf{k}\cdot\mathbf{h}}\prod_{a=0}^{n}\delta\left(h_a-H_a(\mathbf{x}|\mathbf{W})\right) \\
&= \mathbb{E}_{\mathbf{x}}e^{i\mathbf{k}\cdot\mathbf{H}(\mathbf{x}|\mathbf{W})}
= \mathbb{E}_{\mathbf{x}}\exp\left(\frac{i}{\sqrt{N}}\sum_{j=1}^{N}x_j\sum_{a=0}^{n}k_aW_j^a\right) \\
&= \prod_{j=1}^{N}\cos\left(\frac{1}{\sqrt{N}}\sum_{a=0}^{n}k_aW_j^a\right). \tag*{(78)}
\end{aligned} φ N ( k ∣ W ) = E x ∫ R n + 1 d h e i k ⋅ h a = 0 ∏ n δ ( h a − H a ( x ∣ W ) ) = E x e i k ⋅ H ( x ∣ W ) = E x exp ( N i j = 1 ∑ N x j a = 0 ∑ n k a W j a ) = j = 1 ∏ N cos ( N 1 a = 0 ∑ n k a W j a ) . (78)
Then the induced distribution of the local fields can be obtained with a Fourier inversion:
ρ N ( h ∣ W ) = ∫ R n + 1 d k ( 2 π ) n + 1 e − i k ⋅ h φ N ( k ∣ W ) . (79) \rho_N(\mathbf{h} \mid\mathbf{W}) = \int_{\mathbb{R}^{n+1}}\frac{\mathrm{d}\mathbf{k}}{(2\pi)^{n+1}}e^{-i\mathbf{k}\cdot\mathbf{h}}\varphi_N(\mathbf{k}|\mathbf{W}). \tag*{(79)} ρ N ( h ∣ W ) = ∫ R n + 1 ( 2 π ) n + 1 d k e − i k ⋅ h φ N ( k ∣ W ) . (79)
The high-dimensional limit N → ∞ N \to\infty N → ∞ is easily performed on the level of the characteristic function. In fact, using log cos y = − y 2 / 2 + O ( y 4 ) \log\cos y=-y^2/2+O(y^4) log cos y = − y 2 /2 + O ( y 4 ) yields
log φ N ( k ∣ W ) = − 1 2 N ∑ j = 1 N ( ∑ a = 0 n k a W j a ) 2 + o ( 1 ) = − 1 2 ∑ a , b = 0 n k a Q a b k b + o ( 1 ) . (80) \begin{aligned}
\log\varphi_N(\mathbf{k}|\mathbf{W}) &= -\frac{1}{2N}\sum_{j=1}^{N}\left(\sum_{a=0}^{n}k_aW_j^a\right)^2+o(1) \\
&= -\frac{1}{2}\sum_{a,b=0}^{n}k_aQ_{ab}k_b+o(1). \tag*{(80)}
\end{aligned} log φ N ( k ∣ W ) = − 2 N 1 j = 1 ∑ N ( a = 0 ∑ n k a W j a ) 2 + o ( 1 ) = − 2 1 a , b = 0 ∑ n k a Q ab k b + o ( 1 ) . (80)
The remainder vanishes under the condition that no individual coordinate carries a macroscopic fraction of the norm, i.e.
max 1 ≤ j ≤ N ∣ W j a ∣ N ⟶ 0 as N → ∞ , for every a = 0 , … , n . (81) \max_{1\leq j\leq N}\frac{|W_j^a|}{\sqrt{N}}\longrightarrow0\quad\text{as }N\to\infty,\quad\text{for every }a=0,\ldots,n. \tag*{(81)} 1 ≤ j ≤ N max N ∣ W j a ∣ ⟶ 0 as N → ∞ , for every a = 0 , … , n . (81)
This holds with overwhelming probability for a fixed number of vectors drawn from the spherical measure. We therefore obtain
φ N ( k ) ⟶ exp ( − 1 2 k T Q k ) . (82) \varphi_N(\mathbf{k})\longrightarrow\exp\left(-\frac{1}{2}\mathbf{k}^{\mathsf{T}}\mathbf{Q}\mathbf{k}\right). \tag*{(82)} φ N ( k ) ⟶ exp ( − 2 1 k T Qk ) . (82)
Lévy’s continuity theorem therefore gives weak convergence of the field distributions:
ρ N ( h ∣ W ) d h ⟶ d γ Q ( h ) , as N → ∞ . (83) \rho_N(\mathbf{h} \mid\mathbf{W})\,\mathrm{d}\mathbf{h}\longrightarrow\mathrm{d}\gamma_{\mathbf{Q}}(\mathbf{h}),\quad\text{as }N\to\infty. \tag*{(83)} ρ N ( h ∣ W ) d h ⟶ d γ Q ( h ) , as N → ∞. (83)
For positive-definite Q \mathbf{Q} Q , Fourier inversion of the limiting characteristic function gives the density in Eq. (38) . For singular Q \mathbf{Q} Q , the limiting Gaussian law is still defined by its characteristic function. The convergence is understood in the sense of measures, rather than pointwise convergence of densities: at finite N N N , the Rademacher patterns produce a discrete field distribution. The discontinuities of the one-pattern integrand lie on the hyperplanes h a = k π / λ h_a=k\pi/\lambda h a = k π / λ . Each has zero probability under the limiting Gaussian law because every field has unit variance. Thus weak convergence also implies the convergence of the pattern average in Eq. (37) .
Gaussian decomposition under replica symmetry
We now derive explicitly the representation (B20) used to evaluate the one-pattern contribution in Appendix B 2. We work with the limiting Gaussian fields and assume 0 ≤ r 2 ≤ q < 1 0 \le r^2 \le q < 1 0 ≤ r 2 ≤ q < 1 , the domain in which the decomposition below uses real Gaussian variables. The replica-symmetric covariance matrix is
Q R S = ( 1 r 1 n T r 1 n ( 1 − q ) I n + q 1 n 1 n T ) (84) Q_{\mathrm{RS}} =
\begin{pmatrix}
1 & r\mathbf{1}_n^{\mathsf{T}} \\
r\mathbf{1}_n & (1-q)\mathbb{I}_n + q\mathbf{1}_n\mathbf{1}_n^{\mathsf{T}}
\end{pmatrix} \tag*{(84)} Q RS = ( 1 r 1 n r 1 n T ( 1 − q ) I n + q 1 n 1 n T ) (84)
where 1 n = ( 1 , … , 1 ) T \mathbf{1}_n=(1,\ldots,1)^{\mathsf{T}} 1 n = ( 1 , … , 1 ) T and I n \mathbb{I}_n I n is the n × n n \times n n × n identity matrix. To tackle the correlations between the student replicas and the teacher, note that this matrix can be viewed as the sum of three contributions:
Q R S = v 0 v 0 T + v c v c T + ( 1 − q ) Π s , (85) Q_{\mathrm{RS}} = v_0v_0^{\mathsf{T}} + v_cv_c^{\mathsf{T}} + (1-q)\Pi_{\mathrm{s}}, \tag*{(85)} Q RS = v 0 v 0 T + v c v c T + ( 1 − q ) Π s , (85)
with
v 0 = ( 1 r 1 n ) , v c = ( 0 q − r 2 1 n ) , Π s = ( 0 0 0 I n ) . (86) v_0 =
\begin{pmatrix}
1 \\
r\mathbf{1}_n
\end{pmatrix},
\qquad
v_c =
\begin{pmatrix}
0 \\
\sqrt{q-r^2}\mathbf{1}_n
\end{pmatrix},
\qquad
\Pi_{\mathrm{s}} =
\begin{pmatrix}
0 & 0 \\
0 & \mathbb{I}_n
\end{pmatrix}. \tag*{(86)} v 0 = ( 1 r 1 n ) , v c = ( 0 q − r 2 1 n ) , Π s = ( 0 0 0 I n ) . (86)
The three terms have the following interpretation: the first produces the teacher field and the part of every student field correlated with it; the second is an additional fluctuation shared by all student replicas which is not accounted for by their common correlation with the teacher; the last contains the independent fluctuations specific to each replica. In particular, when q > r 2 q > r^2 q > r 2 , the rank-one contribution v c v c T v_cv_c^{\mathsf{T}} v c v c T couples the student fields even after conditioning on the teacher field h 0 h_0 h 0 .
Indeed, the conditional mean and covariance of the student fields are
E [ h a ∣ h 0 ] = r h 0 , Cov ( h a , h b ∣ h 0 ) = ( 1 − q ) δ a b + q − r 2 , a , b = 1 , … , n . (87) \mathbb{E}[h_a \mid h_0] = rh_0,\qquad
\operatorname{Cov}(h_a,h_b \mid h_0) = (1-q)\delta_{ab} + q-r^2,\qquad a,b=1,\ldots,n. \tag*{(87)} E [ h a ∣ h 0 ] = r h 0 , Cov ( h a , h b ∣ h 0 ) = ( 1 − q ) δ ab + q − r 2 , a , b = 1 , … , n . (87)
Thus their conditional characteristic function, with k = ( k 1 , … , k n ) \boldsymbol{k}=(k_1,\ldots,k_n) k = ( k 1 , … , k n ) , is
ρ ^ R S ( k ∣ h 0 ) : = E [ exp ( i ∑ a = 1 n k a h a ) ∣ h 0 ] = exp ( i r h 0 ∑ a = 1 n k a − 1 − q 2 ∑ a = 1 n k a 2 − q − r 2 2 ( ∑ a = 1 n k a ) 2 ) . (88) \widehat{\rho}_{\mathrm{RS}}(\boldsymbol{k}\mid h_0)
:= \mathbb{E}\left[\left.\exp\left(\mathrm{i}\sum_{a=1}^{n}k_ah_a\right)\right|h_0\right]
= \exp\left(\mathrm{i}rh_0\sum_{a=1}^{n}k_a-\frac{1-q}{2}\sum_{a=1}^{n}k_a^2-\frac{q-r^2}{2}\left(\sum_{a=1}^{n}k_a\right)^2\right). \tag*{(88)} ρ RS ( k ∣ h 0 ) := E [ exp ( i a = 1 ∑ n k a h a ) h 0 ] = exp i r h 0 a = 1 ∑ n k a − 2 1 − q a = 1 ∑ n k a 2 − 2 q − r 2 ( a = 1 ∑ n k a ) 2 . (88)
The residual coupling occurs through the single collective coordinate ∑ a = 1 n k a \sum_{a=1}^{n}k_a ∑ a = 1 n k a . It can be removed at the cost of introducing an auxiliary normal random variable via the Hubbard–Stratonovich identity
e − c X 2 / 2 = ∫ D τ e i c τ X , c ≥ 0 , D τ = e − τ 2 / 2 2 π d τ . (89) \mathrm{e}^{-cX^2/2}=\int\mathcal{D}\tau\,\mathrm{e}^{\mathrm{i}\sqrt{c}\,\tau X},\qquad c\ge0,\qquad\mathcal{D}\tau=\frac{\mathrm{e}^{-\tau^2/2}}{\sqrt{2\pi}}\,\mathrm{d}\tau. \tag*{(89)} e − c X 2 /2 = ∫ D τ e i c τ X , c ≥ 0 , D τ = 2 π e − τ 2 /2 d τ . (89)
Applying this identity with c = q − r 2 c=q-r^2 c = q − r 2 yields
ρ ^ R S ( k ∣ h 0 ) = ∫ D τ ∏ a = 1 n exp [ i k a ( r h 0 + q − r 2 τ ) − 1 − q 2 k a 2 ] . (90) \widehat{\rho}_{\mathrm{RS}}(\boldsymbol{k}\mid h_0)
=\int\mathcal{D}\tau\prod_{a=1}^{n}\exp\left[\mathrm{i}k_a\left(rh_0+\sqrt{q-r^2}\,\tau\right)-\frac{1-q}{2}k_a^2\right]. \tag*{(90)} ρ RS ( k ∣ h 0 ) = ∫ D τ a = 1 ∏ n exp [ i k a ( r h 0 + q − r 2 τ ) − 2 1 − q k a 2 ] . (90)
Each factor is the characteristic function of a Gaussian variable with mean r h 0 + q − r 2 τ rh_0+\sqrt{q-r^2}\,\tau r h 0 + q − r 2 τ and variance 1 − q 1-q 1 − q . Fourier inversion therefore gives the conditional density
ρ R S ( h 1 , … , h n ∣ h 0 ) = ∫ D τ ∏ a = 1 n 1 2 π ( 1 − q ) exp ( − ( h a − r h 0 − q − r 2 τ ) 2 2 ( 1 − q ) ) . (91) \rho_{\mathrm{RS}}(h_1,\ldots,h_n\mid h_0)
=\int\mathcal{D}\tau\prod_{a=1}^{n}\frac{1}{\sqrt{2\pi(1-q)}}\exp\left(-\frac{\left(h_a-rh_0-\sqrt{q-r^2}\,\tau\right)^2}{2(1-q)}\right). \tag*{(91)} ρ RS ( h 1 , … , h n ∣ h 0 ) = ∫ D τ a = 1 ∏ n 2 π ( 1 − q ) 1 exp − 2 ( 1 − q ) ( h a − r h 0 − q − r 2 τ ) 2 . (91)
This shows that the student fields are independent conditionally on both h 0 h_0 h 0 and the auxiliary variable τ \tau τ . Equivalently, we can introduce independent standard Gaussians h 0 h_0 h 0 , τ \tau τ , z 1 , … , z n z_1,\ldots,z_n z 1 , … , z n , each with law N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) , and represent the student fields as
h a = r h 0 + q − r 2 τ + 1 − q z a , a = 1 , … , n . (92) h_a = rh_0+\sqrt{q-r^2}\,\tau+\sqrt{1-q}\,z_a,\qquad a=1,\ldots,n. \tag*{(92)} h a = r h 0 + q − r 2 τ + 1 − q z a , a = 1 , … , n . (92)
To use this decomposition in the pattern contribution, recall that all student labels must agree with the teacher label. Separating the two possible labels gives, away from the zero-probability decision boundaries,
∏ a = 1 n Θ ( sin ( λ h 0 ) sin ( λ h a ) ) = Θ ( sin ( λ h 0 ) ) ∏ a = 1 n Θ ( sin ( λ h a ) ) + Θ ( − sin ( λ h 0 ) ) ∏ a = 1 n Θ ( − sin ( λ h a ) ) . (93) \prod_{a=1}^{n}\Theta\bigl(\sin(\lambda h_0)\sin(\lambda h_a)\bigr)
=
\Theta\bigl(\sin(\lambda h_0)\bigr)\prod_{a=1}^{n}\Theta\bigl(\sin(\lambda h_a)\bigr)
+\Theta\bigl(-\sin(\lambda h_0)\bigr)\prod_{a=1}^{n}\Theta\bigl(-\sin(\lambda h_a)\bigr). \tag*{(93)} a = 1 ∏ n Θ ( sin ( λ h 0 ) sin ( λ h a ) ) = Θ ( sin ( λ h 0 ) ) a = 1 ∏ n Θ ( sin ( λ h a ) ) + Θ ( − sin ( λ h 0 ) ) a = 1 ∏ n Θ ( − sin ( λ h a ) ) . (93)
The centered Gaussian measure is invariant under simultaneous sign reversal ( h 0 , … , h n ) ↦ ( − h 0 , … , − h n ) (h_0,\ldots,h_n)\mapsto(-h_0,\ldots,-h_n) ( h 0 , … , h n ) ↦ ( − h 0 , … , − h n ) , so the two terms have equal integrals. Consequently,
Z n , λ ( q , r ) = 2 ∫ d γ Q R S ( h ) Θ ( sin ( λ h 0 ) ) ∏ a = 1 n Θ ( sin ( λ h a ) ) . (94) Z_{n,\lambda}(q,r)=2\int\mathrm{d}\gamma_{\mathrm{QRS}}(\boldsymbol{h})\,\Theta(\sin(\lambda h_0))\prod_{a=1}^{n}\Theta(\sin(\lambda h_a)). \tag*{(94)} Z n , λ ( q , r ) = 2 ∫ d γ QRS ( h ) Θ ( sin ( λ h 0 )) a = 1 ∏ n Θ ( sin ( λ h a )) . (94)
Using Eq. (92) , this becomes
Z n , λ ( q , r ) = 2 ∫ D h 0 D τ Θ ( sin ( λ h 0 ) ) [ ∫ D z Θ ( sin ( λ ( r h 0 + q − r 2 τ + 1 − q z ) ) ) ] n . (95) Z_{n,\lambda}(q,r)=2\int\mathcal{D}h_0\,\mathcal{D}\tau\,\Theta(\sin(\lambda h_0))\left[\int\mathcal{D}z\,\Theta\left(\sin\left(\lambda\left(rh_0+\sqrt{q-r^2}\tau+\sqrt{1-q}z\right)\right)\right)\right]^n. \tag*{(95)} Z n , λ ( q , r ) = 2 ∫ D h 0 D τ Θ ( sin ( λ h 0 )) [ ∫ D z Θ ( sin ( λ ( r h 0 + q − r 2 τ + 1 − q z ) ) ) ] n . (95)
The power n n n appears because the replicas become independent once the two common variables h 0 h_0 h 0 and τ \tau τ are fixed. The common part of every student field is r h 0 + q − r 2 τ rh_0+\sqrt{q-r^2}\tau r h 0 + q − r 2 τ , whose variance is
E [ ( r h 0 + q − r 2 τ ) 2 ] = r 2 + ( q − r 2 ) = q . (96) \mathbb{E}\left[(rh_0+\sqrt{q-r^2}\tau)^2\right]=r^2+(q-r^2)=q. \tag*{(96)} E [ ( r h 0 + q − r 2 τ ) 2 ] = r 2 + ( q − r 2 ) = q . (96)
For q > 0 q>0 q > 0 , normalize this common mode by defining q t = r h 0 + q − r 2 τ \sqrt{q}t=rh_0+\sqrt{q-r^2}\tau q t = r h 0 + q − r 2 τ . To complete the change of variables, introduce the orthogonal Gaussian mode y y y through
\begin{pmatrix}t\\y\end{pmatrix}=
\begin{pmatrix}
r/\sqrt{q} & \sqrt{q-r^2}/\sqrt{q}\\
\sqrt{q-r^2}/\sqrt{q} & -r/\sqrt{q}
\end{pmatrix}
\begin{pmatrix}h_0\\\tau\end{pmatrix}. \tag*{(97)}\end{pmatrix}
The matrix is orthogonal, so t t t and y y y are again independent N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) variables, and D h 0 D τ = D t D y \mathcal{D}h_0\,\mathcal{D}\tau=\mathcal{D}t\,\mathcal{D}y D h 0 D τ = D t D y . Inverting the transformation gives
h 0 = r t q + 1 − r 2 q y , h a = q t + 1 − q z a . (98) h_0=\frac{rt}{\sqrt{q}}+\sqrt{1-\frac{r^2}{q}}\,y,\qquad h_a=\sqrt{q}t+\sqrt{1-q}\,z_a. \tag*{(98)} h 0 = q r t + 1 − q r 2 y , h a = q t + 1 − q z a . (98)
This is Eq. (44) . It is especially convenient because, conditionally on the single common variable t t t , the teacher field and all the student fields are mutually independent. In these variables Eq. (95) reads
Z n , λ ( q , r ) = 2 ∫ D t ∫ D y Θ ( sin ( λ ( r t q + 1 − r 2 q y ) ) ) [ ∫ D z Θ ( sin ( λ ( q t + 1 − q z ) ) ) ] n . (99) Z_{n,\lambda}(q,r)=2\int\mathcal{D}t\int\mathcal{D}y\,\Theta\left(\sin\left(\lambda\left(\frac{rt}{\sqrt{q}}+\sqrt{1-\frac{r^2}{q}}\,y\right)\right)\right)\left[\int\mathcal{D}z\,\Theta\left(\sin\left(\lambda\left(\sqrt{q}t+\sqrt{1-q}z\right)\right)\right)\right]^n. \tag*{(99)} Z n , λ ( q , r ) = 2 ∫ D t ∫ D y Θ ( sin ( λ ( q r t + 1 − q r 2 y ) ) ) [ ∫ D z Θ ( sin ( λ ( q t + 1 − q z ) ) ) ] n . (99)
The integrals over y y y and z z z are precisely the Gaussian convolutions defined in Eq. (46) :
χ λ ( q , r , t ) = p λ ( r t q , 1 − r 2 q ) , ψ λ ( q , t ) = p λ ( q t , 1 − q ) . (100) \chi_\lambda(q,r,t)=p_\lambda\left(\frac{rt}{\sqrt{q}},1-\frac{r^2}{q}\right),\qquad\psi_\lambda(q,t)=p_\lambda(\sqrt{q}t,1-q). \tag*{(100)} χ λ ( q , r , t ) = p λ ( q r t , 1 − q r 2 ) , ψ λ ( q , t ) = p λ ( q t , 1 − q ) . (100)
Thus χ λ \chi_\lambda χ λ is the probability of a positive teacher label conditioned on t t t , and ψ λ \psi_\lambda ψ λ is the corresponding probability for each student replica. We recover Eq. (45) :
Z n , λ ( q , r ) = 2 ∫ D t χ λ ( q , r , t ) ψ λ ( q , t ) n . (101) Z_{n,\lambda}(q,r)=2\int\mathcal{D}t\,\chi_\lambda(q,r,t)\psi_\lambda(q,t)^n. \tag*{(101)} Z n , λ ( q , r ) = 2 ∫ D t χ λ ( q , r , t ) ψ λ ( q , t ) n . (101)
When q = r 2 > 0 q=r^2>0 q = r 2 > 0 , the teacher has no residual fluctuation at fixed t t t ; the expression for χ λ \chi_\lambda χ λ is then understood using p λ ( μ , 0 ) = Θ ( sin λ μ ) p_\lambda(\mu,0)=\Theta(\sin\lambda\mu) p λ ( μ , 0 ) = Θ ( sin λ μ ) . At q = 0 q=0 q = 0 the condition r 2 ≤ q r^2\le q r 2 ≤ q forces r = 0 r=0 r = 0 . All original fields are then independent, and the pattern factor is directly Z n , λ ( 0 , 0 ) = 2 − n Z_{n,\lambda}(0,0)=2^{-n} Z n , λ ( 0 , 0 ) = 2 − n , without introducing the normalized common mode t t t .
Generalization error and asymptotic analysis
We first discuss the small- and large-frequency limits of the reduced RS potential, then derive the generalization error and its asymptotic bounds. Finally, we analyze the response at small load and the stationary branches at large frequency or large load, using the stationarity and Fisher-information representations derived in Appendix § 1.12 .
Classical limit λ → 0 + \lambda\to0^+ λ → 0 +
For z ≠ 0 z \ne0 z = 0 and 0 < λ < π / ∣ z ∣ 0 < \lambda< \pi/|z| 0 < λ < π /∣ z ∣ , Θ ( sin λ z ) = Θ ( z ) \Theta(\sin\lambda z) = \Theta(z) Θ ( sin λ z ) = Θ ( z ) . Dominated convergence therefore gives, for v > 0 v > 0 v > 0 ,
lim λ → 0 + p λ ( μ , v ) = E Z ∼ N ( μ , v ) [ Θ ( Z ) ] = Φ ( μ v ) , (102) \lim_{\lambda\to0^+} p_\lambda(\mu,v) = \mathbb{E}_{Z \sim\mathcal{N}(\mu,v)}[\Theta(Z)] = \Phi\left(\frac{\mu}{\sqrt{v}}\right), \tag*{(102)} λ → 0 + lim p λ ( μ , v ) = E Z ∼ N ( μ , v ) [ Θ ( Z )] = Φ ( v μ ) , (102)
where, as in Appendix A,
Φ ( x ) = ∫ − ∞ x D z = 1 2 ( 1 + erf ( x 2 ) ) (103) \Phi(x) = \int_{-\infty}^{x} \mathcal{D}z = \frac{1}{2}\left(1+\operatorname{erf}\left(\frac{x}{\sqrt{2}}\right)\right) \tag*{(103)} Φ ( x ) = ∫ − ∞ x D z = 2 1 ( 1 + erf ( 2 x ) ) (103)
is the standard normal distribution cumulative function. For v = 0 v = 0 v = 0 and μ ≠ 0 \mu\ne0 μ = 0 , the limit is Θ ( μ ) \Theta(\mu) Θ ( μ ) . For fixed 0 ≤ r < 1 0 \le r < 1 0 ≤ r < 1 , Eq. (102) gives
lim λ → 0 + ψ λ ( r , t ) = Φ ( r 1 − r t ) . (104) \lim_{\lambda\to0^+} \psi_\lambda(r,t) = \Phi\left(\sqrt{\frac{r}{1-r}}\,t\right). \tag*{(104)} λ → 0 + lim ψ λ ( r , t ) = Φ ( 1 − r r t ) . (104)
Consequently, the integrand in the replica-symmetric potential (B39) converges pointwise to the one corresponding to the classical spherical teacher–student perceptron. Since the binary entropy satisfies 0 ≤ H 2 ( p ) ≤ ln 2 0 \le H_2(p) \le\ln2 0 ≤ H 2 ( p ) ≤ ln 2 , dominated convergence also applies to the t t t -integral. Thus, for fixed r < 1 r < 1 r < 1 and finite α \alpha α ,
lim λ → 0 + F λ ( r ; α ) = 1 2 ln ( 1 − r ) + r 2 − α ∫ D t H 2 [ Φ ( r 1 − r t ) ] , (105) \lim_{\lambda\to0^+} \mathcal{F}_\lambda(r;\alpha) = \frac{1}{2}\ln(1-r) + \frac{r}{2} - \alpha\int\mathcal{D}t\, H_2\left[\Phi\left(\sqrt{\frac{r}{1-r}}\,t\right)\right], \tag*{(105)} λ → 0 + lim F λ ( r ; α ) = 2 1 ln ( 1 − r ) + 2 r − α ∫ D t H 2 [ Φ ( 1 − r r t ) ] , (105)
which is the standard RS free entropy functional of the spherical teacher–student perceptron [14 , 16 ] . In this limit, the linear-response coefficient defined in Eq. (155) satisfies κ λ → ( 2 π ) − 1 / 2 \kappa_\lambda\to(2\pi)^{-1/2} κ λ → ( 2 π ) − 1/2 .
Large-frequency limit λ → ∞ \lambda\to\infty λ → ∞
Proposition 1. For every 0 ≤ r < 1 0 \le r < 1 0 ≤ r < 1 and λ > 0 \lambda> 0 λ > 0 ,
∣ ψ λ ( r , t ) − 1 2 ∣ ≤ 1 2 λ π 2 ( 1 − r ) . (106) \left|\psi_\lambda(r,t) - \frac{1}{2}\right| \le\frac{1}{2\lambda}\sqrt{\frac{\pi}{2(1-r)}}. \tag*{(106)} ψ λ ( r , t ) − 2 1 ≤ 2 λ 1 2 ( 1 − r ) π . (106) In particular, for every fixed r < 1 r < 1 r < 1 ,
lim λ → ∞ ψ λ ( r , t ) = 1 2 (107) \lim_{\lambda\to\infty} \psi_\lambda(r,t) = \frac{1}{2} \tag*{(107)} λ → ∞ lim ψ λ ( r , t ) = 2 1 (107) uniformly in t ∈ R t \in\mathbb{R} t ∈ R . The convergence is also uniform in ( r , t ) ∈ [ 0 , r ˉ ] × R (r,t) \in[0,\bar r] \times\mathbb{R} ( r , t ) ∈ [ 0 , r ˉ ] × R for every $\bar r < 1.
Proof. The estimate follows from an integration by parts. From the definition of ψ λ \psi_\lambda ψ λ ,
ψ λ ( r , t ) − 1 2 = 1 2 π ( 1 − r ) ∫ R d x exp ( − ( x − r t ) 2 2 ( 1 − r ) ) Θ ( sin λ x ) − 1 2 = 1 2 π ( 1 − r ) ∫ R d x exp ( − ( x − r t ) 2 2 ( 1 − r ) ) g ( λ x ) , (108) \begin{aligned}
\psi_\lambda(r,t) - \frac{1}{2}
&= \frac{1}{\sqrt{2\pi(1-r)}}\int_{\mathbb{R}} \mathrm{d}x\,\exp\left(-\frac{(x-\sqrt{r}t)^2}{2(1-r)}\right)\Theta(\sin\lambda x)-\frac{1}{2}\\
&= \frac{1}{\sqrt{2\pi(1-r)}}\int_{\mathbb{R}} \mathrm{d}x\,\exp\left(-\frac{(x-\sqrt{r}t)^2}{2(1-r)}\right)g(\lambda x), \tag*{(108)}
\end{aligned} ψ λ ( r , t ) − 2 1 = 2 π ( 1 − r ) 1 ∫ R d x exp ( − 2 ( 1 − r ) ( x − r t ) 2 ) Θ ( sin λ x ) − 2 1 = 2 π ( 1 − r ) 1 ∫ R d x exp ( − 2 ( 1 − r ) ( x − r t ) 2 ) g ( λ x ) , (108)
where we used the Gaussian normalization to bring 1 / 2 1/2 1/2 inside the integral and introduced the centered square wave g ( x ) = Θ ( sin x ) − 1 / 2 g(x) = \Theta(\sin x)-1/2 g ( x ) = Θ ( sin x ) − 1/2 .
Since g g g has zero average over a period, it has a bounded periodic primitive. Specifically, we choose
G ~ ( x ) = { x 2 − π 4 , 0 ≤ x ≤ π , 3 π 4 − x 2 , π ≤ x ≤ 2 π , (109) \widetilde{G}(x) =
\begin{cases}
\frac{x}{2}-\frac{\pi}{4}, & 0 \le x \le\pi,\\
\frac{3\pi}{4}-\frac{x}{2}, & \pi\le x \le2\pi,
\end{cases} \tag*{(109)} G ( x ) = { 2 x − 4 π , 4 3 π − 2 x , 0 ≤ x ≤ π , π ≤ x ≤ 2 π , (109)
extended periodically outside [ 0 , 2 π ] [0,2\pi] [ 0 , 2 π ] . This is the triangular primitive ∫ 0 x g ( u ) d u \int_0^x g(u)\,\mathrm{d}u ∫ 0 x g ( u ) d u shifted by − π / 4 -\pi/4 − π /4 , so that it has zero mean and ∥ G ~ ∥ ∞ = π / 4 \|\widetilde{G}\|_\infty=\pi/4 ∥ G ∥ ∞ = π /4 . Since
g ( λ x ) = 1 λ d d x G ~ ( λ x ) (110) g(\lambda x)=\frac{1}{\lambda}\frac{\mathrm{d}}{\mathrm{d}x}\widetilde{G}(\lambda x) \tag*{(110)} g ( λ x ) = λ 1 d x d G ( λ x ) (110)
almost everywhere, integration by parts gives
ψ λ ( r , t ) − 1 2 = 1 λ 2 π ( 1 − r ) ∫ R d x x − r t 1 − r exp ( − ( x − r t ) 2 2 ( 1 − r ) ) G ~ ( λ x ) . (111) \psi_\lambda(r,t)-\frac{1}{2}=\frac{1}{\lambda\sqrt{2\pi(1-r)}}\int_{\mathbb{R}}\mathrm{d}x\,\frac{x-\sqrt{r}t}{1-r}\exp\left(-\frac{(x-\sqrt{r}t)^2}{2(1-r)}\right)\widetilde{G}(\lambda x). \tag*{(111)} ψ λ ( r , t ) − 2 1 = λ 2 π ( 1 − r ) 1 ∫ R d x 1 − r x − r t exp ( − 2 ( 1 − r ) ( x − r t ) 2 ) G ( λ x ) . (111)
The boundary term vanishes because G ~ \widetilde{G} G is bounded and the Gaussian factor tends to zero. Therefore
∣ ψ λ ( r , t ) − 1 2 ∣ ≤ ∥ G ~ ∥ ∞ λ ( 1 − r ) 1 2 π ( 1 − r ) ∫ R d x ∣ x − r t ∣ exp ( − ( x − r t ) 2 2 ( 1 − r ) ) = π 4 λ ( 1 − r ) 2 ( 1 − r ) π = 1 2 λ π 2 ( 1 − r ) . (112) \begin{aligned}
\left|\psi_\lambda(r,t)-\frac{1}{2}\right|\leq\frac{\|\widetilde{G}\|_\infty}{\lambda(1-r)}\frac{1}{\sqrt{2\pi(1-r)}}\int_{\mathbb{R}}\mathrm{d}x\,|x-\sqrt{r}t|\exp\left(-\frac{(x-\sqrt{r}t)^2}{2(1-r)}\right) \\
&=\frac{\pi}{4\lambda(1-r)}\sqrt{\frac{2(1-r)}{\pi}}=\frac{1}{2\lambda}\sqrt{\frac{\pi}{2(1-r)}}. \tag*{(112)}
\end{aligned} ψ λ ( r , t ) − 2 1 ≤ λ ( 1 − r ) ∥ G ∥ ∞ 2 π ( 1 − r ) 1 ∫ R d x ∣ x − r t ∣ exp ( − 2 ( 1 − r ) ( x − r t ) 2 ) = 4 λ ( 1 − r ) π π 2 ( 1 − r ) = 2 λ 1 2 ( 1 − r ) π . (112)
This proves Eq. (106) . The right-hand side is independent of t t t and tends to zero uniformly for 0 ≤ r ≤ r ‾ < 1 0\leq r\leq\overline{r}<1 0 ≤ r ≤ r < 1 . ■
Proposition 2 (Large frequency at fixed load). Let r ⋆ ( α , λ ) r_\star(\alpha,\lambda) r ⋆ ( α , λ ) denote any maximizer of F λ ( r ; α ) F_\lambda(r;\alpha) F λ ( r ; α ) in Eq. (63) . Then, for every fixed finite α ≥ 0 \alpha\geq0 α ≥ 0 ,
r ⋆ ( α , λ ) ⟶ 0 , ϕ R S ( α , λ ) ⟶ − α ln 2 , ε λ ( r ⋆ ( α , λ ) ) ⟶ 1 2 as λ → ∞ . (113) r_\star(\alpha,\lambda)\longrightarrow0,\qquad\phi_{\mathrm{RS}}(\alpha,\lambda)\longrightarrow-\alpha\ln2,\qquad\varepsilon_\lambda(r_\star(\alpha,\lambda))\longrightarrow\frac{1}{2}\quad\text{as }\lambda\to\infty. \tag*{(113)} r ⋆ ( α , λ ) ⟶ 0 , ϕ RS ( α , λ ) ⟶ − α ln 2 , ε λ ( r ⋆ ( α , λ )) ⟶ 2 1 as λ → ∞. (113) The limiting RS potential has the unique maximizer r = 0 r=0 r = 0 ; hence the limit of r ⋆ r_\star r ⋆ is independent of the choice of maximizer at finite λ \lambda λ .
Proof. We need uniform convergence on an interval containing all maximizers. The first step is therefore to prove that the maximizers stay bounded away from 1 1 1 uniformly in λ \lambda λ . Recall that the pattern contribution to F λ F_\lambda F λ is nonpositive, since H 2 ≥ 0 H_2\geq0 H 2 ≥ 0 . Hence, for every r ∈ [ 0 , 1 ) r\in[0,1) r ∈ [ 0 , 1 ) ,
F λ ( r ; α ) ≤ 1 2 [ ln ( 1 − r ) + r ] . (114) F_\lambda(r;\alpha)\leq\frac{1}{2}\left[\ln(1-r)+r\right]. \tag*{(114)} F λ ( r ; α ) ≤ 2 1 [ ln ( 1 − r ) + r ] . (114)
If r ⋆ r_\star r ⋆ is a maximizer, then F λ ( r ⋆ ; α ) ≥ F λ ( 0 ; α ) = − α ln 2 F_\lambda(r_\star;\alpha)\geq F_\lambda(0;\alpha)=-\alpha\ln2 F λ ( r ⋆ ; α ) ≥ F λ ( 0 ; α ) = − α ln 2 , and therefore
− α ln 2 ≤ 1 2 [ ln ( 1 − r ⋆ ) + r ⋆ ] ≤ 1 2 [ 1 + ln ( 1 − r ⋆ ) ] . (115) -\alpha\ln2\leq\frac{1}{2}\left[\ln(1-r_\star)+r_\star\right]\leq\frac{1}{2}\left[1+\ln(1-r_\star)\right]. \tag*{(115)} − α ln 2 ≤ 2 1 [ ln ( 1 − r ⋆ ) + r ⋆ ] ≤ 2 1 [ 1 + ln ( 1 − r ⋆ ) ] . (115)
Thus every maximizer satisfies
1 − r ⋆ ≥ δ α , δ α : = exp [ − 1 − 2 α ln 2 ] = e − 1 2 − 2 α > 0. (116) 1-r_\star\geq\delta_\alpha,\qquad\delta_\alpha:=\exp[-1-2\alpha\ln2]=e^{-1}2^{-2\alpha}>0. \tag*{(116)} 1 − r ⋆ ≥ δ α , δ α := exp [ − 1 − 2 α ln 2 ] = e − 1 2 − 2 α > 0. (116)
For fixed finite α \alpha α , all maximizers are therefore confined to the compact interval [ 0 , 1 − δ α ] [0,1-\delta_\alpha] [ 0 , 1 − δ α ] , independently of λ \lambda λ . Continuity of F λ F_\lambda F λ on this interval and its divergence to − ∞ -\infty − ∞ as r → 1 r\to1 r → 1 also ensure that a maximizer exists.
On this interval, Proposition 1 implies that ψ λ → 1 / 2 \psi_\lambda\to1/2 ψ λ → 1/2 uniformly in both r r r and t t t . By continuity of H 2 H_2 H 2 at 1 / 2 1/2 1/2 , and since ∫ D t = 1 \int Dt=1 ∫ D t = 1 , the potential F λ ( r ; α ) F_\lambda(r;\alpha) F λ ( r ; α ) converges uniformly to
F ∞ ( r ; α ) = 1 2 [ ln ( 1 − r ) + r ] − α ln 2. (117) F_\infty(r;\alpha)=\frac{1}{2}\left[\ln(1-r)+r\right]-\alpha\ln2. \tag*{(117)} F ∞ ( r ; α ) = 2 1 [ ln ( 1 − r ) + r ] − α ln 2. (117)
The limiting functional has the unique maximizer r = 0 r=0 r = 0 , since ln ( 1 − r ) + r ≤ 0 \ln(1-r)+r\leq0 ln ( 1 − r ) + r ≤ 0 , with equality only at r = 0 r=0 r = 0 .
To see explicitly why the maximizers converge, fix any 0 < η < 1 − δ α 0<\eta<1-\delta_\alpha 0 < η < 1 − δ α . For r ≥ η r\geq\eta r ≥ η in the compact interval,
F ∞ ( 0 ; α ) − F ∞ ( r ; α ) ≥ − 1 2 [ ln ( 1 − η ) + η ] > 0. (118) F_\infty(0;\alpha)-F_\infty(r;\alpha)\geq-\frac{1}{2}\left[\ln(1-\eta)+\eta\right]>0. \tag*{(118)} F ∞ ( 0 ; α ) − F ∞ ( r ; α ) ≥ − 2 1 [ ln ( 1 − η ) + η ] > 0. (118)
Once the uniform difference between F λ F_\lambda F λ and F ∞ F_\infty F ∞ is smaller than half this positive gap, no such r r r can maximize F λ F_\lambda F λ . Since η \eta η can be arbitrarily small, r ⋆ ( α , λ ) → 0 r_\star(\alpha,\lambda)\to0 r ⋆ ( α , λ ) → 0 . Moreover,
∣ max 0 ≤ r ≤ 1 − δ α F λ ( r ; α ) − max 0 ≤ r ≤ 1 − δ α F ∞ ( r ; α ) ∣ ≤ sup 0 ≤ r ≤ 1 − δ α ∣ F λ ( r ; α ) − F ∞ ( r ; α ) ∣ ⟶ 0 , (119) \left|\max_{0\leq r\leq1-\delta_\alpha}F_\lambda(r;\alpha)-\max_{0\leq r\leq1-\delta_\alpha}F_\infty(r;\alpha)\right|\leq\sup_{0\leq r\leq1-\delta_\alpha}|F_\lambda(r;\alpha)-F_\infty(r;\alpha)|\longrightarrow0, \tag*{(119)} 0 ≤ r ≤ 1 − δ α max F λ ( r ; α ) − 0 ≤ r ≤ 1 − δ α max F ∞ ( r ; α ) ≤ 0 ≤ r ≤ 1 − δ α sup ∣ F λ ( r ; α ) − F ∞ ( r ; α ) ∣ ⟶ 0 , (119)
which proves ϕ R S → − α ln 2 \phi_{\mathrm{RS}} \to-\alpha\ln2 ϕ RS → − α ln 2 .
Finally, the error bound (D36), proved below, applies uniformly on the same compact interval. In particular,
0 ≤ 1 2 − ε λ ( r ⋆ ) ≤ 4 π 2 e − λ 2 δ α ( 1 − e − 4 λ 2 δ α ) 2 ⟶ 0. (120) 0 \le\frac{1}{2}-\varepsilon_\lambda(r_\star) \le\frac{4}{\pi^2}\frac{e^{-\lambda^2\delta_\alpha}}{\left(1-e^{-4\lambda^2\delta_\alpha}\right)^2} \longrightarrow0. \tag*{(120)} 0 ≤ 2 1 − ε λ ( r ⋆ ) ≤ π 2 4 ( 1 − e − 4 λ 2 δ α ) 2 e − λ 2 δ α ⟶ 0. (120)
This justifies evaluating the large-frequency limit at the λ \lambda λ -dependent equilibrium overlap. ■
Generalization error
Proposition 3. For 0 ≤ r < 1 0 \le r < 1 0 ≤ r < 1 and λ > 0 \lambda> 0 λ > 0 , the function ε λ ( r ) \varepsilon_\lambda(r) ε λ ( r ) defined by Eq. (29) has the equivalent representation
ε λ ( r ) = 2 ∫ D t ψ λ ( r , t ) ( 1 − ψ λ ( r , t ) ) , (121) \varepsilon_\lambda(r) = 2\int\mathcal{D}t\,\psi_\lambda(r,t)\left(1-\psi_\lambda(r,t)\right), \tag*{(121)} ε λ ( r ) = 2 ∫ D t ψ λ ( r , t ) ( 1 − ψ λ ( r , t ) ) , (121) and admits the absolutely convergent series representation
ε λ ( r ) = 1 2 − 8 π 2 ∑ m , n = 0 ∞ sinh ( λ 2 r ( 2 m + 1 ) ( 2 n + 1 ) ) ( 2 m + 1 ) ( 2 n + 1 ) exp ( − λ 2 2 ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) ) . (122) \varepsilon_\lambda(r) = \frac{1}{2} - \frac{8}{\pi^2}\sum_{m,n=0}^{\infty}\frac{\sinh\left(\lambda^2 r(2m+1)(2n+1)\right)}{(2m+1)(2n+1)}\exp\left(-\frac{\lambda^2}{2}\left((2m+1)^2+(2n+1)^2\right)\right). \tag*{(122)} ε λ ( r ) = 2 1 − π 2 8 m , n = 0 ∑ ∞ ( 2 m + 1 ) ( 2 n + 1 ) sinh ( λ 2 r ( 2 m + 1 ) ( 2 n + 1 ) ) exp ( − 2 λ 2 ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) ) . (122)
Proof. By Eq. (29) ,
ε λ ( r ) = P ( s λ ( U ) ≠ s λ ( V ) ) , (123) \varepsilon_\lambda(r) = \mathbb{P}\left(s_\lambda(U) \ne s_\lambda(V)\right), \tag*{(123)} ε λ ( r ) = P ( s λ ( U ) = s λ ( V ) ) , (123)
where we may take
U = Z , V = r Z + 1 − r 2 Y , (124) U=Z,\qquad V=rZ+\sqrt{1-r^2}\,Y, \tag*{(124)} U = Z , V = r Z + 1 − r 2 Y , (124)
with Y , Z Y,Z Y , Z independent N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) variables. These are centered and jointly Gaussian fields with
E [ U 2 ] = E [ V 2 ] = 1 , E [ U V ] = r . (125) \mathbb{E}[U^2]=\mathbb{E}[V^2]=1,\qquad\mathbb{E}[UV]=r. \tag*{(125)} E [ U 2 ] = E [ V 2 ] = 1 , E [ U V ] = r . (125)
For 0 ≤ r < 1 0 \le r < 1 0 ≤ r < 1 , the same Gaussian pair can be represented more conveniently as
U = r T + 1 − r Y , V = r T + 1 − r Z , (126) U=\sqrt{r}\,T+\sqrt{1-r}\,Y,\qquad V=\sqrt{r}\,T+\sqrt{1-r}\,Z, \tag*{(126)} U = r T + 1 − r Y , V = r T + 1 − r Z , (126)
where T , Y , Z T,Y,Z T , Y , Z are independent N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) variables. This is the two-field form of the decomposition in Appendix C 2, on the line q = r q=r q = r . The advantage of Eq. (126) is that, conditioned on T = t T=t T = t , the two fields are independent and identically distributed according to N ( r t , 1 − r ) \mathcal{N}(\sqrt{r}t,1-r) N ( r t , 1 − r ) . Hence, by the definition of ψ λ \psi_\lambda ψ λ in Eq. (12) ,
P ( s λ ( U ) = + 1 ∣ T = t ) = P ( s λ ( V ) = + 1 ∣ T = t ) = ψ λ ( r , t ) . (127) \mathbb{P}(s_\lambda(U)=+1\mid T=t)=\mathbb{P}(s_\lambda(V)=+1\mid T=t)=\psi_\lambda(r,t). \tag*{(127)} P ( s λ ( U ) = + 1 ∣ T = t ) = P ( s λ ( V ) = + 1 ∣ T = t ) = ψ λ ( r , t ) . (127)
The zeros of sin ( λ U ) \sin(\lambda U) sin ( λ U ) have zero Gaussian probability, so the conditional probability that the two classifiers disagree is
P ( s λ ( U ) ≠ s λ ( V ) ∣ T = t ) = ψ λ ( r , t ) ( 1 − ψ λ ( r , t ) ) + ( 1 − ψ λ ( r , t ) ) ψ λ ( r , t ) = 2 ψ λ ( r , t ) ( 1 − ψ λ ( r , t ) ) . (128) \begin{aligned}
\mathbb{P}(s_\lambda(U)\ne s_\lambda(V)\mid T=t)
&=\psi_\lambda(r,t)(1-\psi_\lambda(r,t))+(1-\psi_\lambda(r,t))\psi_\lambda(r,t)\\
&=2\psi_\lambda(r,t)(1-\psi_\lambda(r,t)). \tag*{(128)}
\end{aligned} P ( s λ ( U ) = s λ ( V ) ∣ T = t ) = ψ λ ( r , t ) ( 1 − ψ λ ( r , t )) + ( 1 − ψ λ ( r , t )) ψ λ ( r , t ) = 2 ψ λ ( r , t ) ( 1 − ψ λ ( r , t )) . (128)
Averaging over t t t proves Eq. (121) .
We next derive the series representation. Since s λ ( U ) s_\lambda(U) s λ ( U ) and s λ ( V ) s_\lambda(V) s λ ( V ) take values in { − 1 , + 1 } \{-1,+1\} { − 1 , + 1 } almost surely,
ε λ ( r ) = 1 2 ( 1 − C λ ( r ) ) , C λ ( r ) : = E [ s λ ( U ) s λ ( V ) ] . (129) \varepsilon_\lambda(r)=\frac{1}{2}\left(1-C_\lambda(r)\right),\qquad C_\lambda(r):=\mathbb{E}[s_\lambda(U)s_\lambda(V)]. \tag*{(129)} ε λ ( r ) = 2 1 ( 1 − C λ ( r ) ) , C λ ( r ) := E [ s λ ( U ) s λ ( V )] . (129)
Conditional independence in Eq. (126) gives
C λ ( r ) = ∫ D t ( 2 ψ λ ( r , t ) − 1 ) 2 , ε λ ( r ) = 1 2 − 2 ∫ D t ( ψ λ ( r , t ) − 1 2 ) 2 . (130) C_\lambda(r)=\int\mathcal{D}t\,\left(2\psi_\lambda(r,t)-1\right)^2,\qquad\varepsilon_\lambda(r)=\frac{1}{2}-2\int\mathcal{D}t\,\left(\psi_\lambda(r,t)-\frac{1}{2}\right)^2. \tag*{(130)} C λ ( r ) = ∫ D t ( 2 ψ λ ( r , t ) − 1 ) 2 , ε λ ( r ) = 2 1 − 2 ∫ D t ( ψ λ ( r , t ) − 2 1 ) 2 . (130)
We use the Fourier series after Gaussian smoothing, so that the interchange of the series and the integral is justified explicitly. Equation (B22) yields
ψ λ ( r , t ) − 1 2 = 2 π ∑ m = 0 ∞ sin ( ( 2 m + 1 ) λ r t ) 2 m + 1 exp ( − 1 2 λ 2 ( 2 m + 1 ) 2 ( 1 − r ) ) . (131) \psi_{\lambda}(r,t)-\frac{1}{2}=\frac{2}{\pi}\sum_{m=0}^{\infty}\frac{\sin\left((2m+1)\lambda\sqrt{r}t\right)}{2m+1}\exp\left(-\frac{1}{2}\lambda^2(2m+1)^2(1-r)\right). \tag*{(131)} ψ λ ( r , t ) − 2 1 = π 2 m = 0 ∑ ∞ 2 m + 1 sin ( ( 2 m + 1 ) λ r t ) exp ( − 2 1 λ 2 ( 2 m + 1 ) 2 ( 1 − r ) ) . (131)
For r < 1 r<1 r < 1 , the absolute value of each term is bounded independently of t t t by a summable Gaussian sequence. The series therefore converges absolutely and uniformly in t t t , and its square is an absolutely and uniformly convergent double series. Since ∫ D t = 1 \int Dt=1 ∫ D t = 1 , this double series can be integrated term by term in Eq. (130) .
For real A A A , B B B , the Gaussian characteristic function ∫ D t e i A t = e − A 2 / 2 \int Dt e^{iAt}=e^{-A^2/2} ∫ D t e i A t = e − A 2 /2 and trigonometric identities give
∫ D t sin ( A t ) sin ( B t ) = 1 2 ∫ D t ( cos ( ( A − B ) t ) − cos ( ( A + B ) t ) ) = 1 2 ( e − ( A − B ) 2 / 2 − e − ( A + B ) 2 / 2 ) = e − ( A 2 + B 2 ) / 2 sinh ( A B ) . (132) \begin{aligned}
\int Dt\sin(At)\sin(Bt)
&=\frac{1}{2}\int Dt\left(\cos((A-B)t)-\cos((A+B)t)\right)\\
&=\frac{1}{2}\left(e^{-(A-B)^2/2}-e^{-(A+B)^2/2}\right)=e^{-(A^2+B^2)/2}\sinh(AB). \tag*{(132)}
\end{aligned} ∫ D t sin ( A t ) sin ( B t ) = 2 1 ∫ D t ( cos (( A − B ) t ) − cos (( A + B ) t ) ) = 2 1 ( e − ( A − B ) 2 /2 − e − ( A + B ) 2 /2 ) = e − ( A 2 + B 2 ) /2 sinh ( A B ) . (132)
Taking A = ( 2 m + 1 ) λ r A=(2m+1)\lambda\sqrt{r} A = ( 2 m + 1 ) λ r and B = ( 2 n + 1 ) λ r B=(2n+1)\lambda\sqrt{r} B = ( 2 n + 1 ) λ r and combining this Gaussian factor with the smoothing factors in Eq. (131) gives Eq. (122) .
To verify absolute convergence of the resulting expression explicitly, use sinh x ≤ 1 2 e x \sinh x\le\frac{1}{2}e^x sinh x ≤ 2 1 e x for x ≥ 0 x\ge0 x ≥ 0 and 2 ( 2 m + 1 ) ( 2 n + 1 ) ≤ ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 2(2m+1)(2n+1)\le(2m+1)^2+(2n+1)^2 2 ( 2 m + 1 ) ( 2 n + 1 ) ≤ ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 . With c = λ 2 ( 1 − r ) / 2 > 0 c=\lambda^2(1-r)/2>0 c = λ 2 ( 1 − r ) /2 > 0 , these imply
0 ≤ sinh ( λ 2 r ( 2 m + 1 ) ( 2 n + 1 ) ) exp ( − λ 2 2 ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) ) ≤ 1 2 exp ( − c ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) ) . (133) \begin{aligned}
0&\le\sinh\left(\lambda^2r(2m+1)(2n+1)\right)\exp\left(-\frac{\lambda^2}{2}\left((2m+1)^2+(2n+1)^2\right)\right)\\
&\le\frac{1}{2}\exp\left(-c\left((2m+1)^2+(2n+1)^2\right)\right). \tag*{(133)}
\end{aligned} 0 ≤ sinh ( λ 2 r ( 2 m + 1 ) ( 2 n + 1 ) ) exp ( − 2 λ 2 ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) ) ≤ 2 1 exp ( − c ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) ) . (133)
Consequently, the absolute values of the summands are bounded by a summable double sequence:
∑ m , n = 0 ∞ e − c ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) 2 ( 2 m + 1 ) ( 2 n + 1 ) = 1 2 ( ∑ m = 0 ∞ e − c ( 2 m + 1 ) 2 2 m + 1 ) 2 < ∞ . (134) \sum_{m,n=0}^{\infty}\frac{e^{-c((2m+1)^2+(2n+1)^2)}}{2(2m+1)(2n+1)}
=\frac{1}{2}\left(\sum_{m=0}^{\infty}\frac{e^{-c(2m+1)^2}}{2m+1}\right)^2<\infty. \tag*{(134)} m , n = 0 ∑ ∞ 2 ( 2 m + 1 ) ( 2 n + 1 ) e − c (( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) = 2 1 ( m = 0 ∑ ∞ 2 m + 1 e − c ( 2 m + 1 ) 2 ) 2 < ∞. (134)
Proposition 4. Let ε λ ( r ) \varepsilon_{\lambda}(r) ε λ ( r ) be the generalization error defined in Eq. (29) , with $0\le r\le 1.
In the small-frequency limit,
lim λ → 0 + ε λ ( r ) = 1 π arccos r . (135) \lim_{\lambda\to0^+}\varepsilon_{\lambda}(r)=\frac{1}{\pi}\arccos r. \tag*{(135)} λ → 0 + lim ε λ ( r ) = π 1 arccos r . (135) More precisely, for every λ > 0 \lambda>0 λ > 0 ,
∣ ε λ ( r ) − 1 π arccos r ∣ ≤ 4 ( 1 − Φ ( π λ ) ) ≤ 4 λ π 2 π exp ( − π 2 2 λ 2 ) , (136) \left|\varepsilon_{\lambda}(r)-\frac{1}{\pi}\arccos r\right|\le4\left(1-\Phi\left(\frac{\pi}{\lambda}\right)\right)\le\frac{4\lambda}{\pi\sqrt{2\pi}}\exp\left(-\frac{\pi^2}{2\lambda^2}\right), \tag*{(136)} ε λ ( r ) − π 1 arccos r ≤ 4 ( 1 − Φ ( λ π ) ) ≤ π 2 π 4 λ exp ( − 2 λ 2 π 2 ) , (136) uniformly for r ∈ [ 0 , 1 ] r\in[0,1] r ∈ [ 0 , 1 ] .
For every 0 ≤ r < 1 0\le r<1 0 ≤ r < 1 and λ > 0 \lambda>0 λ > 0 ,
4 π 2 e − λ 2 ( 1 − r ) ( 1 − e − 2 λ 2 r ) ≤ 1 2 − ε λ ( r ) ≤ 4 π 2 e − λ 2 ( 1 − r ) ( 1 − e − 4 λ 2 ( 1 − r ) ) 2 . (137) \frac{4}{\pi^2}e^{-\lambda^2(1-r)}\left(1-e^{-2\lambda^2r}\right)\le\frac{1}{2}-\varepsilon_{\lambda}(r)\le\frac{4}{\pi^2}\frac{e^{-\lambda^2(1-r)}}{\left(1-e^{-4\lambda^2(1-r)}\right)^2}. \tag*{(137)} π 2 4 e − λ 2 ( 1 − r ) ( 1 − e − 2 λ 2 r ) ≤ 2 1 − ε λ ( r ) ≤ π 2 4 ( 1 − e − 4 λ 2 ( 1 − r ) ) 2 e − λ 2 ( 1 − r ) . (137) Therefore, for each fixed 0 ≤ r < 1 0\le r<1 0 ≤ r < 1 ,
lim λ → ∞ ε λ ( r ) = 1 2 , (138) \lim_{\lambda\to\infty}\varepsilon_{\lambda}(r)=\frac{1}{2}, \tag*{(138)} λ → ∞ lim ε λ ( r ) = 2 1 , (138) and the leading correction for fixed 0 < r < 1 0<r<1 0 < r < 1 is
1 2 − ε λ ( r ) ∼ 4 π 2 e − λ 2 ( 1 − r ) , λ → ∞ . (139) \frac{1}{2}-\varepsilon_{\lambda}(r)\sim\frac{4}{\pi^2}e^{-\lambda^2(1-r)},\qquad\lambda\to\infty. \tag*{(139)} 2 1 − ε λ ( r ) ∼ π 2 4 e − λ 2 ( 1 − r ) , λ → ∞. (139) At r = 0 r=0 r = 0 one has ε λ ( 0 ) = 1 / 2 \varepsilon_{\lambda}(0)=1/2 ε λ ( 0 ) = 1/2 for every λ > 0 \lambda>0 λ > 0 , whereas at r = 1 r=1 r = 1 one has ε λ ( 1 ) = 0 \varepsilon_{\lambda}(1)=0 ε λ ( 1 ) = 0 . In particular, the large-λ \lambda λ limit is not uniform as r → 1 r\to1 r → 1 .
Proof. We begin with the small-λ \lambda λ regime. Let ( U , V ) (U,V) ( U , V ) be the Gaussian pair in Eq. (124) and set
a λ = π λ . (140) a_{\lambda}=\frac{\pi}{\lambda}. \tag*{(140)} a λ = λ π . (140)
For ∣ x ∣ < a λ |x|<a_{\lambda} ∣ x ∣ < a λ , one has s λ ( x ) = sgn [ sin ( λ x ) ] = sgn x s_{\lambda}(x)=\operatorname{sgn}[\sin(\lambda x)]=\operatorname{sgn}x s λ ( x ) = sgn [ sin ( λ x )] = sgn x . Consequently, on the event { ∣ U ∣ < a λ , ∣ V ∣ < a λ } \{|U|<a_{\lambda},\,|V|<a_{\lambda}\} { ∣ U ∣ < a λ , ∣ V ∣ < a λ } , the oscillatory classifier has exactly the same disagreement indicator as the classical perceptron:
1 { s λ ( U ) ≠ s λ ( V ) } = 1 { U V < 0 } if ∣ U ∣ < a λ and ∣ V ∣ < a λ , (141) \mathbf{1}\{s_{\lambda}(U)\ne s_{\lambda}(V)\}=\mathbf{1}\{UV<0\}\quad\text{if }|U|<a_{\lambda}\text{ and }|V|<a_{\lambda}, \tag*{(141)} 1 { s λ ( U ) = s λ ( V )} = 1 { U V < 0 } if ∣ U ∣ < a λ and ∣ V ∣ < a λ , (141)
apart from the zero-probability event U V = 0 UV=0 U V = 0 . The classical disagreement probability is
P ( U V < 0 ) = 1 π arccos r . (142) \mathbb{P}(UV<0)=\frac{1}{\pi}\arccos r. \tag*{(142)} P ( U V < 0 ) = π 1 arccos r . (142)
Indeed, writing r = cos ϑ r=\cos\vartheta r = cos ϑ in Eq. (124) , the two signs are determined by projections of the isotropic Gaussian vector ( Z , Y ) (Z,Y) ( Z , Y ) onto directions separated by the angle ϑ \vartheta ϑ . They disagree in two angular sectors of total opening 2 ϑ 2\vartheta 2 ϑ , giving probability ϑ / π \vartheta/\pi ϑ / π .
The two disagreement events can therefore differ only if at least one field leaves ( − a λ , a λ ) (-a_{\lambda},a_{\lambda}) ( − a λ , a λ ) . Taking expectations of the indicators and using the union bound gives
∣ ε λ ( r ) − 1 π arccos r ∣ ≤ P ( ∣ U ∣ ≥ a λ or ∣ V ∣ ≥ a λ ) ≤ P ( ∣ U ∣ ≥ a λ ) + P ( ∣ V ∣ ≥ a λ ) = 4 ( 1 − Φ ( a λ ) ) . (143) \begin{aligned}
\left|\varepsilon_{\lambda}(r)-\frac{1}{\pi}\arccos r\right|&\le\mathbb{P}(|U|\ge a_{\lambda}\text{ or }|V|\ge a_{\lambda})\\
&\le\mathbb{P}(|U|\ge a_{\lambda})+\mathbb{P}(|V|\ge a_{\lambda})\\
&=4\left(1-\Phi(a_{\lambda})\right). \tag*{(143)}
\end{aligned} ε λ ( r ) − π 1 arccos r ≤ P ( ∣ U ∣ ≥ a λ or ∣ V ∣ ≥ a λ ) ≤ P ( ∣ U ∣ ≥ a λ ) + P ( ∣ V ∣ ≥ a λ ) = 4 ( 1 − Φ ( a λ ) ) . (143)
Here each field has the standard normal marginal, so
P ( ∣ U ∣ ≥ a λ ) = P ( U ≥ a λ ) + P ( U ≤ − a λ ) = 2 [ 1 − Φ ( a λ ) ] , (144) \mathbb{P}(|U|\ge a_{\lambda})=\mathbb{P}(U\ge a_{\lambda})+\mathbb{P}(U\le-a_{\lambda})=2[1-\Phi(a_{\lambda})], \tag*{(144)} P ( ∣ U ∣ ≥ a λ ) = P ( U ≥ a λ ) + P ( U ≤ − a λ ) = 2 [ 1 − Φ ( a λ )] , (144)
and similarly for V V V , independently of their correlation. Finally, the Gaussian tail bound
1 − Φ ( x ) ≤ 1 x 2 π e − x 2 / 2 , x > 0 , (145) 1-\Phi(x)\le\frac{1}{x\sqrt{2\pi}}e^{-x^{2}/2},\qquad x>0, \tag*{(145)} 1 − Φ ( x ) ≤ x 2 π 1 e − x 2 /2 , x > 0 , (145)
gives the second inequality in Eq. (136) and proves uniform convergence on r ∈ [ 0 , 1 ] r\in[0,1] r ∈ [ 0 , 1 ] .
We now turn to the large-λ \lambda λ regime. By Proposition 3,
1 2 − ε λ ( r ) = 8 π 2 ∑ m , n = 0 ∞ sinh ( λ 2 r ( 2 m + 1 ) ( 2 n + 1 ) ) ( 2 m + 1 ) ( 2 n + 1 ) exp ( − λ 2 2 ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) ) . (146) \frac{1}{2}-\varepsilon_{\lambda}(r)=\frac{8}{\pi^{2}}\sum_{m,n=0}^{\infty}\frac{\sinh\left(\lambda^{2}r(2m+1)(2n+1)\right)}{(2m+1)(2n+1)}\exp\left(-\frac{\lambda^{2}}{2}\left((2m+1)^{2}+(2n+1)^{2}\right)\right). \tag*{(146)} 2 1 − ε λ ( r ) = π 2 8 m , n = 0 ∑ ∞ ( 2 m + 1 ) ( 2 n + 1 ) sinh ( λ 2 r ( 2 m + 1 ) ( 2 n + 1 ) ) exp ( − 2 λ 2 ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) ) . (146)
For r ≥ 0 r\ge0 r ≥ 0 , every term is nonnegative. Retaining only the term m = n = 0 m=n=0 m = n = 0 gives
1 2 − ε λ ( r ) ≥ 8 π 2 e − λ 2 sinh ( λ 2 r ) = 4 π 2 e − λ 2 ( 1 − r ) ( 1 − e − 2 λ 2 r ) . (147) \frac{1}{2}-\varepsilon_{\lambda}(r)\ge\frac{8}{\pi^{2}}e^{-\lambda^{2}}\sinh(\lambda^{2}r)=\frac{4}{\pi^{2}}e^{-\lambda^{2}(1-r)}\left(1-e^{-2\lambda^{2}r}\right). \tag*{(147)} 2 1 − ε λ ( r ) ≥ π 2 8 e − λ 2 sinh ( λ 2 r ) = π 2 4 e − λ 2 ( 1 − r ) ( 1 − e − 2 λ 2 r ) . (147)
For the upper bound, using sinh x ≤ 1 2 e x \sinh x\le\frac{1}{2}e^{x} sinh x ≤ 2 1 e x for x ≥ 0 x\ge0 x ≥ 0 yields
1 2 − ε λ ( r ) ≤ 4 π 2 ∑ m , n = 0 ∞ exp ( − λ 2 2 ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 − 2 r ( 2 m + 1 ) ( 2 n + 1 ) ) ) ( 2 m + 1 ) ( 2 n + 1 ) . (148) \frac{1}{2}-\varepsilon_{\lambda}(r)\le\frac{4}{\pi^{2}}\sum_{m,n=0}^{\infty}\frac{\exp\left(-\frac{\lambda^{2}}{2}\left((2m+1)^{2}+(2n+1)^{2}-2r(2m+1)(2n+1)\right)\right)}{(2m+1)(2n+1)}. \tag*{(148)} 2 1 − ε λ ( r ) ≤ π 2 4 m , n = 0 ∑ ∞ ( 2 m + 1 ) ( 2 n + 1 ) exp ( − 2 λ 2 ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 − 2 r ( 2 m + 1 ) ( 2 n + 1 ) ) ) . (148)
Since
( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 − 2 r ( 2 m + 1 ) ( 2 n + 1 ) = ( 1 − r ) ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) + 4 r ( m − n ) 2 ≥ ( 1 − r ) ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) , (149) \begin{aligned}
(2m+1)^{2}+(2n+1)^{2}-2r(2m+1)(2n+1)&=(1-r)\left((2m+1)^{2}+(2n+1)^{2}\right)+4r(m-n)^{2}\\
&\ge(1-r)\left((2m+1)^{2}+(2n+1)^{2}\right), \tag*{(149)}
\end{aligned} ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 − 2 r ( 2 m + 1 ) ( 2 n + 1 ) = ( 1 − r ) ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) + 4 r ( m − n ) 2 ≥ ( 1 − r ) ( ( 2 m + 1 ) 2 + ( 2 n + 1 ) 2 ) , (149)
we obtain the factorized bound
1 2 − ε λ ( r ) ≤ 4 π 2 ( ∑ k = 0 ∞ e − λ 2 ( 1 − r ) ( 2 k + 1 ) 2 / 2 2 k + 1 ) 2 . (150) \frac{1}{2}-\varepsilon_{\lambda}(r)\le\frac{4}{\pi^{2}}\left(\sum_{k=0}^{\infty}\frac{e^{-\lambda^{2}(1-r)(2k+1)^{2}/2}}{2k+1}\right)^{2}. \tag*{(150)} 2 1 − ε λ ( r ) ≤ π 2 4 ( k = 0 ∑ ∞ 2 k + 1 e − λ 2 ( 1 − r ) ( 2 k + 1 ) 2 /2 ) 2 . (150)
Set c = λ 2 ( 1 − r ) / 2 > 0 c=\lambda^2(1-r)/2>0 c = λ 2 ( 1 − r ) /2 > 0 . The inequalities
( 2 k + 1 ) 2 ≥ 1 + 8 k , 1 2 k + 1 ≤ 1 , k = 0 , 1 , … , (151) (2k+1)^2 \ge1+8k,\qquad\frac{1}{2k+1}\le1,\qquad k=0,1,\ldots, \tag*{(151)} ( 2 k + 1 ) 2 ≥ 1 + 8 k , 2 k + 1 1 ≤ 1 , k = 0 , 1 , … , (151)
give
∑ k = 0 ∞ e − c ( 2 k + 1 ) 2 2 k + 1 ≤ e − c ∑ k = 0 ∞ e − 8 c k = e − c 1 − e − 8 c . (152) \sum_{k=0}^{\infty}\frac{e^{-c(2k+1)^2}}{2k+1}\le e^{-c}\sum_{k=0}^{\infty}e^{-8ck}=\frac{e^{-c}}{1-e^{-8c}}. \tag*{(152)} k = 0 ∑ ∞ 2 k + 1 e − c ( 2 k + 1 ) 2 ≤ e − c k = 0 ∑ ∞ e − 8 c k = 1 − e − 8 c e − c . (152)
Substituting this into Eq. (D49) yields
1 2 − ε λ ( r ) ≤ 4 π 2 e − λ 2 ( 1 − r ) ( 1 − e − 4 λ 2 ( 1 − r ) ) 2 , (153) \frac{1}{2}-\varepsilon_\lambda(r)\le\frac{4}{\pi^2}\frac{e^{-\lambda^2(1-r)}}{\left(1-e^{-4\lambda^2(1-r)}\right)^2}, \tag*{(153)} 2 1 − ε λ ( r ) ≤ π 2 4 ( 1 − e − 4 λ 2 ( 1 − r ) ) 2 e − λ 2 ( 1 − r ) , (153)
which completes the proof of Eq. (D36). For each fixed r < 1 r<1 r < 1 , the upper bound tends to zero as λ → ∞ \lambda\to\infty λ → ∞ , proving Eq. (D37).
If in addition r > 0 r>0 r > 0 , division of Eq. (D36) by the common leading term gives
1 − e − 2 λ 2 r ≤ 1 2 − ε λ ( r ) 4 π 2 e − λ 2 ( 1 − r ) ≤ 1 ( 1 − e − 4 λ 2 ( 1 − r ) ) 2 . (154) 1-e^{-2\lambda^2r}\le\frac{\frac{1}{2}-\varepsilon_\lambda(r)}{\frac{4}{\pi^2}e^{-\lambda^2(1-r)}}\le\frac{1}{\left(1-e^{-4\lambda^2(1-r)}\right)^2}. \tag*{(154)} 1 − e − 2 λ 2 r ≤ π 2 4 e − λ 2 ( 1 − r ) 2 1 − ε λ ( r ) ≤ ( 1 − e − 4 λ 2 ( 1 − r ) ) 2 1 . (154)
Both bounds converge to one, which proves Eq. (D38).
Finally, when r = 0 r=0 r = 0 , U U U and V V V are independent and the square-wave outputs are unbiased, so ε λ ( 0 ) = 1 / 2 \varepsilon_\lambda(0)=1/2 ε λ ( 0 ) = 1/2 . When r = 1 r=1 r = 1 , U = V U=V U = V almost surely and ε λ ( 1 ) = 0 \varepsilon_\lambda(1)=0 ε λ ( 1 ) = 0 . More generally, ε λ ( r ) → 0 \varepsilon_\lambda(r)\to0 ε λ ( r ) → 0 as r → 1 r\to1 r → 1 at each fixed λ \lambda λ : under the coupling (D23), V → U V\to U V → U almost surely, and the classifier is continuous at U U U with probability one. Thus the limit (D37) cannot be uniform up to r = 1 r=1 r = 1 . ■
Linear response at small load
Differentiating Eq. (B22) at μ = 0 \mu=0 μ = 0 , v = 1 v=1 v = 1 ,
κ λ : = ∂ μ p λ ( μ , v ) ∣ μ = 0 , v = 1 = 1 2 E z [ z s λ ( z ) ] = 2 λ π ∑ k ≥ 0 e − ( 2 k + 1 ) 2 λ 2 / 2 = ∑ m ∈ Z ( − 1 ) m φ ( m π λ ) , (155) \kappa_\lambda:=\left.\partial_\mu p_\lambda(\mu,v)\right|_{\mu=0,v=1}=\frac{1}{2}\mathbb{E}_z\left[z\,s_\lambda(z)\right]=\frac{2\lambda}{\pi}\sum_{k\ge0}e^{-(2k+1)^2\lambda^2/2}=\sum_{m\in\mathbb{Z}}(-1)^m\varphi\left(\frac{m\pi}{\lambda}\right), \tag*{(155)} κ λ := ∂ μ p λ ( μ , v ) ∣ μ = 0 , v = 1 = 2 1 E z [ z s λ ( z ) ] = π 2 λ k ≥ 0 ∑ e − ( 2 k + 1 ) 2 λ 2 /2 = m ∈ Z ∑ ( − 1 ) m φ ( λ mπ ) , (155)
where the second equality is by Stein’s Lemma and the last by Poisson summation. From J λ ( 0 + ) = κ λ 2 J_\lambda(0+)=\kappa_\lambda^2 J λ ( 0 + ) = κ λ 2 and Eq. (E3), α λ ( r ) = r / ( 4 κ λ 2 ) + O ( r 2 ) \alpha_\lambda(r)=r/(4\kappa_\lambda^2)+O(r^2) α λ ( r ) = r / ( 4 κ λ 2 ) + O ( r 2 ) , hence
r ⋆ = 4 κ λ 2 α + O ( α 2 ) , ϕ R S = − α ln 2 + 4 κ λ 2 α 2 + O ( α 3 ) . (156) r_\star=4\kappa_\lambda^2\alpha+O(\alpha^2),\qquad\phi_{\mathrm{RS}}=-\alpha\ln2+4\kappa_\lambda^2\alpha^2+O(\alpha^3). \tag*{(156)} r ⋆ = 4 κ λ 2 α + O ( α 2 ) , ϕ RS = − α ln 2 + 4 κ λ 2 α 2 + O ( α 3 ) . (156)
The same value follows exactly for P = O ( 1 ) P=O(1) P = O ( 1 ) patterns: the posterior mean is ⟨ w ⟩ ≃ ∑ μ x μ E [ h ∣ s λ ( h ) = ξ μ ] / N \langle w\rangle\simeq\sum_\mu x^\mu\mathbb{E}[h\mid s_\lambda(h)=\xi^\mu]/\sqrt{N} ⟨ w ⟩ ≃ ∑ μ x μ E [ h ∣ s λ ( h ) = ξ μ ] / N and E [ h ∣ s λ ( h ) = ± 1 ] = ± 2 κ λ \mathbb{E}[h\mid s_\lambda(h)=\pm1]=\pm2\kappa_\lambda E [ h ∣ s λ ( h ) = ± 1 ] = ± 2 κ λ . For λ → 0 + \lambda\to0^+ λ → 0 + , 4 κ λ 2 → 2 / π 4\kappa_\lambda^2\to2/\pi 4 κ λ 2 → 2/ π ; for λ ≫ 1 \lambda\gg1 λ ≫ 1 , 4 κ λ 2 = ( 16 / π 2 ) λ 2 e − λ 2 [ 1 + O ( e − 4 λ 2 ) ] 4\kappa_\lambda^2=(16/\pi^2)\lambda^2e^{-\lambda^2}[1+O(e^{-4\lambda^2})] 4 κ λ 2 = ( 16/ π 2 ) λ 2 e − λ 2 [ 1 + O ( e − 4 λ 2 )] . At λ = 3 \lambda=3 λ = 3 and α = 4 \alpha=4 α = 4 this gives an overlap value of ≃ 0.00717 \simeq0.00717 ≃ 0.00717 , in agreement with the numerical maximizer of the weakly aligned branch. At this load that branch is metastable: the equilibrium maximizer r ⋆ r_\star r ⋆ instead lies on the strongly aligned branch.
Upper spinodal
On the weakly aligned branch r = O ( λ − 2 ) r=O(\lambda^{-2}) r = O ( λ − 2 ) . For r ≤ r ˉ < 1 r\le\bar r<1 r ≤ r ˉ < 1 and λ → ∞ \lambda\to\infty λ → ∞ , Eq. (B22) gives p λ − 1 2 = 2 π sin θ e − λ 2 ( 1 − r ) / 2 ( 1 + O ( e − 4 λ 2 ( 1 − r ) ) ) p_\lambda-\frac{1}{2}=\frac{2}{\pi}\sin\theta\,e^{-\lambda^2(1-r)/2}(1+O(e^{-4\lambda^2(1-r)})) p λ − 2 1 = π 2 sin θ e − λ 2 ( 1 − r ) /2 ( 1 + O ( e − 4 λ 2 ( 1 − r ) )) with θ = λ r t \theta=\lambda\sqrt{r}\,t θ = λ r t , so p ( 1 − p ) = 1 4 + O ( e − λ 2 ( 1 − r ) ) p(1-p)=\frac{1}{4}+O(e^{-\lambda^2(1-r)}) p ( 1 − p ) = 4 1 + O ( e − λ 2 ( 1 − r ) ) and, from Eq. (E2) with E t ∼ N ( 0 , 1 ) cos 2 ( λ r t ) = 1 2 ( 1 + e − 2 λ 2 r ) \mathbb{E}_{t\sim\mathcal{N}(0,1)}\cos^2(\lambda\sqrt{r}\,t)=\frac{1}{2}(1+e^{-2\lambda^2r}) E t ∼ N ( 0 , 1 ) cos 2 ( λ r t ) = 2 1 ( 1 + e − 2 λ 2 r ) ,
J λ ( r ) = 4 λ 2 π 2 e − λ 2 cosh ( λ 2 r ) ( 1 + O ( e − λ 2 ( 1 − r ) ) ) , α λ ( r ) = π 2 16 e λ 2 λ 4 x ( 1 − x / λ 2 ) cosh x ( 1 + O ( e − λ 2 ( 1 − r ) ) ) , x = λ 2 r . (157) J_\lambda(r)=\frac{4\lambda^2}{\pi^2}e^{-\lambda^2}\cosh(\lambda^2r)\left(1+O(e^{-\lambda^2(1-r)})\right),\qquad\alpha_\lambda(r)=\frac{\pi^2}{16}\frac{e^{\lambda^2}}{\lambda^4}\frac{x}{(1-x/\lambda^2)\cosh x}\left(1+O(e^{-\lambda^2(1-r)})\right),\qquad x=\lambda^2r. \tag*{(157)} J λ ( r ) = π 2 4 λ 2 e − λ 2 cosh ( λ 2 r ) ( 1 + O ( e − λ 2 ( 1 − r ) ) ) , α λ ( r ) = 16 π 2 λ 4 e λ 2 ( 1 − x / λ 2 ) cosh x x ( 1 + O ( e − λ 2 ( 1 − r ) ) ) , x = λ 2 r . (157)
The first fold (local maximum of α λ \alpha_\lambda α λ ) is at x = x 0 + O ( λ − 2 ) x=x_0+O(\lambda^{-2}) x = x 0 + O ( λ − 2 ) with x 0 tanh x 0 = 1 x_0\tanh x_0=1 x 0 tanh x 0 = 1 , x 0 = 1.19968 x_0=1.19968 x 0 = 1.19968 , which gives
α s p + ( λ ) = C + e λ 2 λ 4 ( 1 + O ( λ − 2 ) ) , C + = π 2 16 x 0 cosh x 0 = 0.40881. (158) \alpha_{\mathrm{sp}}^+(\lambda)=C_+\frac{e^{\lambda^2}}{\lambda^4}\left(1+O(\lambda^{-2})\right),\qquad C_+=\frac{\pi^2}{16}\frac{x_0}{\cosh x_0}=0.40881. \tag*{(158)} α sp + ( λ ) = C + λ 4 e λ 2 ( 1 + O ( λ − 2 ) ) , C + = 16 π 2 cosh x 0 x 0 = 0.40881. (158)
Aligned branch: boundary layers and universal error
For fixed λ \lambda λ and r → 1 r \to1 r → 1 , the smoothing width λ 1 − r \lambda\sqrt{1-r} λ 1 − r of p λ p_{\lambda} p λ vanishes. As a function of t t t , ψ λ ( r , t ) \psi_{\lambda}(r,t) ψ λ ( r , t ) is then exponentially close to 0 or 1 except in layers of width w = ( 1 − r ) / r w = \sqrt{(1-r)/r} w = ( 1 − r ) / r around the fringes t k = k π / ( λ r ) t_k = k\pi/(\lambda\sqrt{r}) t k = k π / ( λ r ) , where ψ λ ≃ Φ ( ± ( t − t k ) / w ) \psi_{\lambda} \simeq\Phi(\pm(t-t_k)/w) ψ λ ≃ Φ ( ± ( t − t k ) / w ) with alternating signs. Summing the layers with weights φ ( t k ) \varphi(t_k) φ ( t k ) ,
E t ∼ N ( 0 , 1 ) H 2 ( ψ λ ) = C H Θ λ w ( 1 + o ( 1 ) ) , ϵ λ ( r ) = 2 π Θ λ w ( 1 + o ( 1 ) ) , \mathbb{E}_{t\sim\mathcal{N}(0,1)}H_2(\psi_{\lambda}) = C_H\Theta_{\lambda}w(1+o(1)), \qquad\epsilon_{\lambda}(r) = \frac{2}{\sqrt{\pi}}\Theta_{\lambda}w(1+o(1)), E t ∼ N ( 0 , 1 ) H 2 ( ψ λ ) = C H Θ λ w ( 1 + o ( 1 )) , ϵ λ ( r ) = π 2 Θ λ w ( 1 + o ( 1 )) ,
C H = ∫ R H 2 [ Φ ( x ) ] d x = 1.80639 , Θ λ = ∑ k ∈ Z φ ( k π λ ) , (159) C_H = \int_{\mathbb{R}} H_2[\Phi(x)]\,\mathrm{d}x = 1.80639, \qquad\Theta_{\lambda} = \sum_{k\in\mathbb{Z}}\varphi\left(\frac{k\pi}{\lambda}\right), \tag*{(159)} C H = ∫ R H 2 [ Φ ( x )] d x = 1.80639 , Θ λ = k ∈ Z ∑ φ ( λ k π ) , (159)
where we used ∫ R 2 Φ ( 1 − Φ ) d x = 2 / π \int_{\mathbb{R}}2\Phi(1-\Phi)\,\mathrm{d}x = 2/\sqrt{\pi} ∫ R 2Φ ( 1 − Φ ) d x = 2/ π . Note that Θ λ → φ ( 0 ) \Theta_{\lambda} \to\varphi(0) Θ λ → φ ( 0 ) for λ → 0 + \lambda\to0^{+} λ → 0 + (a single boundary) and Θ λ = λ π ( 1 + 2 ∑ j ≥ 1 e − 2 j 2 λ 2 ) \Theta_{\lambda} = \frac{\lambda}{\pi}\left(1+2\sum_{j\geq1}e^{-2j^{2}\lambda^{2}}\right) Θ λ = π λ ( 1 + 2 ∑ j ≥ 1 e − 2 j 2 λ 2 ) by Poisson summation. With 1 2 ln ( 1 − r ) + r 2 = ln w + 1 2 + o ( 1 ) \frac{1}{2}\ln(1-r)+\frac{r}{2}=\ln w+\frac{1}{2}+o(1) 2 1 ln ( 1 − r ) + 2 r = ln w + 2 1 + o ( 1 ) , the reduced potential becomes F λ ≃ ln w + 1 2 − α C H Θ λ w \mathcal{F}_{\lambda}\simeq\ln w+\frac{1}{2}-\alpha C_H\Theta_{\lambda}w F λ ≃ ln w + 2 1 − α C H Θ λ w , maximized at w ⋆ = 1 / ( α C H Θ λ ) w_{\star}=1/(\alpha C_H\Theta_{\lambda}) w ⋆ = 1/ ( α C H Θ λ ) :
F λ ( + ) ( α ) ≃ − ln ( α C H Θ λ ) − 1 2 , 1 − r ⋆ ≃ 1 ( α C H Θ λ ) 2 , ϵ g ≃ 2 π C H 1 α = 0.62466 α . (160) \mathcal{F}_{\lambda}^{(+)}(\alpha)\simeq-\ln(\alpha C_H\Theta_{\lambda})-\frac{1}{2}, \qquad1-r_{\star}\simeq\frac{1}{(\alpha C_H\Theta_{\lambda})^{2}}, \qquad\epsilon_g\simeq\frac{2}{\sqrt{\pi}C_H}\frac{1}{\alpha}=\frac{0.62466}{\alpha}. \tag*{(160)} F λ ( + ) ( α ) ≃ − ln ( α C H Θ λ ) − 2 1 , 1 − r ⋆ ≃ ( α C H Θ λ ) 2 1 , ϵ g ≃ π C H 2 α 1 = α 0.62466 . (160)
The approximation requires w ⋆ w_{\star} w ⋆ to be small compared with the fringe spacing, α C H Θ λ ≫ max ( 1 , λ / π ) \alpha C_H\Theta_{\lambda}\gg\max(1,\lambda/\pi) α C H Θ λ ≫ max ( 1 , λ / π ) . The error is λ \lambda λ independent and coincides with the classical Gibbs-learning law of the spherical perceptron [14 , 16 ] . As a check, at λ = 3 \lambda=3 λ = 3 , α = 4 \alpha=4 α = 4 Eq. (160) gives F ( + ) ≃ − 2.4315 \mathcal{F}^{(+)}\simeq-2.4315 F ( + ) ≃ − 2.4315 versus the exact − 2.44171 -2.44171 − 2.44171 , and α ϵ g \alpha\epsilon_g α ϵ g at α = 50 \alpha=50 α = 50 equals 0.6243, 0.6245 and 0.6246 for λ → 0 + \lambda\to0^{+} λ → 0 + , 2 and 3.
Coexistence line at large frequency
For λ ≫ 1 \lambda\gg1 λ ≫ 1 , F λ ( − ) = − α ln 2 + O ( α λ 2 λ 4 e − 2 λ 2 ) \mathcal{F}_{\lambda}^{(-)}=-\alpha\ln2+O(\alpha\lambda^{2}\lambda^{4}e^{-2\lambda^{2}}) F λ ( − ) = − α ln 2 + O ( α λ 2 λ 4 e − 2 λ 2 ) and Θ λ ≃ λ / π \Theta_{\lambda}\simeq\lambda/\pi Θ λ ≃ λ / π . Equating with Eq. (160) ,
α e q ln 2 − ln α e q = ln λ + c 0 + o ( 1 ) , c 0 = ln C H π + 1 2 = − 0.05340 , (161) \alpha_{\rm eq}\ln2-\ln\alpha_{\rm eq}=\ln\lambda+c_0+o(1), \qquad c_0=\ln\frac{C_H}{\pi}+\frac{1}{2}=-0.05340, \tag*{(161)} α eq ln 2 − ln α eq = ln λ + c 0 + o ( 1 ) , c 0 = ln π C H + 2 1 = − 0.05340 , (161)
so that α e q = log 2 λ + log 2 log 2 λ + O ( 1 ) \alpha_{\rm eq}=\log_2\lambda+\log_2\log_2\lambda+O(1) α eq = log 2 λ + log 2 log 2 λ + O ( 1 ) . Table I compares Eqs. (158) and (161) with the numerical solution.
Table I. Large-frequency asymptotics versus the numerical RS solution. α e q a s y \alpha_{\rm eq}^{\rm asy} α eq asy solves Eq. (161) without the o ( 1 ) o(1) o ( 1 ) term; α s p + , a s y = C + e λ 2 / λ 4 \alpha_{\rm sp}^{+,{\rm asy}} = C_{+}e^{\lambda^{2}}/\lambda^{4} α sp + , asy = C + e λ 2 / λ 4 .
Lower spinodal at large frequency
At fixed s = λ 2 ( 1 − r ) s=\lambda^2(1-r) s = λ 2 ( 1 − r ) and λ → ∞ \lambda\to\infty λ → ∞ , the phase θ = λ r t \theta=\lambda\sqrt{r}\,t θ = λ r t is equidistributed modulo 2 π 2\pi 2 π , and F λ = − ln λ + 1 2 ln s − α ln 2 + α D ( s ) + o ( 1 ) \mathcal{F}_{\lambda}=-\ln\lambda+\frac{1}{2}\ln s-\alpha\ln2+\alpha D(s)+o(1) F λ = − ln λ + 2 1 ln s − α ln 2 + α D ( s ) + o ( 1 ) with
D ( s ) = ln 2 − 1 2 π ∫ 0 2 π H 2 [ p ˉ ( θ , s ) ] d θ , p ˉ ( θ , s ) = P z [ sin ( θ + s z ) > 0 ] , (162) D(s)=\ln2-\frac{1}{2\pi}\int_{0}^{2\pi}H_2[\bar p(\theta,s)]\,\mathrm{d}\theta, \qquad\bar p(\theta,s)=\mathbb{P}_{z}\left[\sin(\theta+\sqrt{s}\,z)>0\right], \tag*{(162)} D ( s ) = ln 2 − 2 π 1 ∫ 0 2 π H 2 [ p ˉ ( θ , s )] d θ , p ˉ ( θ , s ) = P z [ sin ( θ + s z ) > 0 ] , (162)
the information carried by one label in the aligned phase. The aligned branch is stationary at α = − 1 / [ 2 s D ′ ( s ) ] \alpha=-1/[2sD'(s)] α = − 1/ [ 2 s D ′ ( s )] , whose minimum over s s s gives α s p − ( ∞ ) = 2.6466 \alpha_{\rm sp}^{-}(\infty)=2.6466 α sp − ( ∞ ) = 2.6466 (at s = 0.713 s=0.713 s = 0.713 ). The finite-λ \lambda λ values α s p − = 2.422 \alpha_{\rm sp}^{-}=2.422 α sp − = 2.422 , 2.485, 2.524, 2.569 at λ = 3 \lambda=3 λ = 3 , 3.5, 4, 5 approach it from below.
Structure of the reduced potential
Here, we investigate the structure of the reduced potential, showing that it satisfies a heat equation and admits a Fisher-information representation. We further derive the conditions for the occurrence of first-order transitions within the RS framework.
Proposition 5 (Heat equation). p λ p_\lambda p λ is smooth on R × ( 0 , ∞ ) \mathbb{R} \times(0,\infty) R × ( 0 , ∞ ) and ∂ v p λ = 1 2 ∂ μ 2 p λ \partial_v p_\lambda= \frac{1}{2}\partial_\mu^2 p_\lambda ∂ v p λ = 2 1 ∂ μ 2 p λ . Consequently, for 0 < r < 1 0 < r < 1 0 < r < 1 ,
2 r ∂ r ψ λ ( r , t ) = t ∂ t ψ λ ( r , t ) − ∂ t 2 ψ λ ( r , t ) . (163) 2r\,\partial_r\psi_\lambda(r,t)=t\,\partial_t\psi_\lambda(r,t)-\partial_t^2\psi_\lambda(r,t). \tag*{(163)} 2 r ∂ r ψ λ ( r , t ) = t ∂ t ψ λ ( r , t ) − ∂ t 2 ψ λ ( r , t ) . (163)
Proof. p λ ( μ , v ) = ∫ d x G v ( x − μ ) Θ ( sin λ x ) p_\lambda(\mu,v)=\int\mathrm{d}x\,G_v(x-\mu)\Theta(\sin\lambda x) p λ ( μ , v ) = ∫ d x G v ( x − μ ) Θ ( sin λ x ) with G v G_v G v the heat kernel, which satisfies ∂ v G v = 1 2 ∂ x 2 G v \partial_vG_v=\frac{1}{2}\partial_x^2G_v ∂ v G v = 2 1 ∂ x 2 G v ; derivatives can be taken on the kernel because Θ ( sin λ x ) \Theta(\sin\lambda x) Θ ( sin λ x ) is bounded. With ψ λ = p λ ( r t , 1 − r ) \psi_\lambda=p_\lambda(\sqrt{r}\,t,1-r) ψ λ = p λ ( r t , 1 − r ) : ∂ r ψ λ = t 2 r ∂ μ p λ − ∂ v p λ = t 2 r ∂ μ p λ − 1 2 ∂ μ 2 p λ \partial_r\psi_\lambda=\frac{t}{2\sqrt{r}}\partial_\mu p_\lambda-\partial_vp_\lambda=\frac{t}{2\sqrt{r}}\partial_\mu p_\lambda-\frac{1}{2}\partial_\mu^2p_\lambda ∂ r ψ λ = 2 r t ∂ μ p λ − ∂ v p λ = 2 r t ∂ μ p λ − 2 1 ∂ μ 2 p λ , ∂ t ψ λ = r ∂ μ p λ \partial_t\psi_\lambda=\sqrt{r}\,\partial_\mu p_\lambda ∂ t ψ λ = r ∂ μ p λ , ∂ t 2 ψ λ = r ∂ μ 2 p λ \partial_t^2\psi_\lambda=r\,\partial_\mu^2p_\lambda ∂ t 2 ψ λ = r ∂ μ 2 p λ . ■
Proposition 6 (Fisher-information representation). For 0 < r < 1 0<r<1 0 < r < 1 ,
J λ ( r ) : = I λ ′ ( r ) = 1 4 r ∫ D t ( ∂ t ψ λ ( r , t ) ) 2 ψ λ ( 1 − ψ λ ) = λ 2 4 E t ∼ N ( 0 , 1 ) [ ( ∂ θ p ) 2 p ( 1 − p ) ] p = p λ ( θ / λ , 1 − r ) , θ = λ r t > 0. (164) \mathcal{J}_\lambda(r):=\mathcal{I}_\lambda'(r)=\frac{1}{4r}\int\mathcal{D}t\,\frac{(\partial_t\psi_\lambda(r,t))^2}{\psi_\lambda(1-\psi_\lambda)}=\frac{\lambda^2}{4}\mathbb{E}_{t\sim\mathcal{N}(0,1)}\left[\frac{(\partial_\theta p)^2}{p(1-p)}\right]_{p=p_\lambda(\theta/\lambda,1-r),\ \theta=\lambda\sqrt{r}\,t}>0. \tag*{(164)} J λ ( r ) := I λ ′ ( r ) = 4 r 1 ∫ D t ψ λ ( 1 − ψ λ ) ( ∂ t ψ λ ( r , t ) ) 2 = 4 λ 2 E t ∼ N ( 0 , 1 ) [ p ( 1 − p ) ( ∂ θ p ) 2 ] p = p λ ( θ / λ , 1 − r ) , θ = λ r t > 0. (164) In particular J λ \mathcal{J}_\lambda J λ is strictly increasing and E t ∼ N ( 0 , 1 ) H 2 ( ψ λ ( r , t ) ) \mathbb{E}_{t\sim\mathcal{N}(0,1)}H_2(\psi_\lambda(r,t)) E t ∼ N ( 0 , 1 ) H 2 ( ψ λ ( r , t )) strictly decreasing in r r r . Moreover J λ ( 0 + ) = κ λ 2 \mathcal{J}_\lambda(0^+)=\kappa_\lambda^2 J λ ( 0 + ) = κ λ 2 with κ λ \kappa_\lambda κ λ given in Eq. (155) .
Proof. Since ∫ D t ∂ r ψ λ = ∂ r 1 2 = 0 \int\mathcal{D}t\,\partial_r\psi_\lambda=\partial_r\frac{1}{2}=0 ∫ D t ∂ r ψ λ = ∂ r 2 1 = 0 , I λ ′ = ∫ D t ∂ r ψ λ ln ψ λ \mathcal{I}_\lambda'=\int\mathcal{D}t\,\partial_r\psi_\lambda\ln\psi_\lambda I λ ′ = ∫ D t ∂ r ψ λ ln ψ λ . Insert Eq. (163) and use Gaussian integration by parts in the form ∫ D t ( t f ′ − f ′ ′ ) g = ∫ D t f ′ g ′ \int\mathcal{D}t\,(tf'-f'')g=\int\mathcal{D}t\,f'g' ∫ D t ( t f ′ − f ′′ ) g = ∫ D t f ′ g ′ with f = ψ λ f=\psi_\lambda f = ψ λ , g = ln ψ λ g=\ln\psi_\lambda g = ln ψ λ (boundary terms vanish because ψ λ \psi_\lambda ψ λ and its derivatives are bounded away from the singularities of the logarithm for r < 1 r<1 r < 1 ): I λ ′ = 1 2 r ∫ D t ( ∂ t ψ λ ) 2 / ψ λ \mathcal{I}_\lambda'=\frac{1}{2r}\int\mathcal{D}t\,(\partial_t\psi_\lambda)^2/\psi_\lambda I λ ′ = 2 r 1 ∫ D t ( ∂ t ψ λ ) 2 / ψ λ . The symmetry ψ λ ( r , − t ) = 1 − ψ λ ( r , t ) \psi_\lambda(r,-t)=1-\psi_\lambda(r,t) ψ λ ( r , − t ) = 1 − ψ λ ( r , t ) implies that ( ∂ t ψ λ ) 2 (\partial_t\psi_\lambda)^2 ( ∂ t ψ λ ) 2 is even, so the same integral equals 1 2 r ∫ D t ( ∂ t ψ λ ) 2 / ( 1 − ψ λ ) \frac{1}{2r}\int\mathcal{D}t\,(\partial_t\psi_\lambda)^2/(1-\psi_\lambda) 2 r 1 ∫ D t ( ∂ t ψ λ ) 2 / ( 1 − ψ λ ) ; averaging the two forms gives Eq. (164) . The second form follows from ∂ t = λ r ∂ θ \partial_t=\lambda\sqrt{r}\,\partial_\theta ∂ t = λ r ∂ θ . The small-r r r limit follows from ∂ t ψ λ → r ∂ μ p λ ( 0 , 1 ) = r κ λ \partial_t\psi_\lambda\to\sqrt{r}\,\partial_\mu p_\lambda(0,1)=\sqrt{r}\,\kappa_\lambda ∂ t ψ λ → r ∂ μ p λ ( 0 , 1 ) = r κ λ and ψ λ → 1 / 2 \psi_\lambda\to1/2 ψ λ → 1/2 . ■
Since ∂ r 1 2 ( ln ( 1 − r ) + r ) = − r / ( 2 ( 1 − r ) ) \partial_r\frac{1}{2}(\ln(1-r)+r)=-r/(2(1-r)) ∂ r 2 1 ( ln ( 1 − r ) + r ) = − r / ( 2 ( 1 − r )) ,
∂ r F λ ( r ; α ) = 2 J λ ( r ) ( α − α λ ( r ) ) , α λ ( r ) = r 4 ( 1 − r ) J λ ( r ) , ∂ r 2 F λ ∣ α = α λ ( r ) = − 2 J λ ( r ) α λ ′ ( r ) . (165) \partial_r\mathcal{F}_\lambda(r;\alpha)=2\mathcal{J}_\lambda(r)(\alpha-\alpha_\lambda(r)),\qquad\alpha_\lambda(r)=\frac{r}{4(1-r)\mathcal{J}_\lambda(r)},\qquad\left.\partial_r^2\mathcal{F}_\lambda\right|_{\alpha=\alpha_\lambda(r)}=-2\mathcal{J}_\lambda(r)\alpha_\lambda'(r). \tag*{(165)} ∂ r F λ ( r ; α ) = 2 J λ ( r ) ( α − α λ ( r )) , α λ ( r ) = 4 ( 1 − r ) J λ ( r ) r , ∂ r 2 F λ α = α λ ( r ) = − 2 J λ ( r ) α λ ′ ( r ) . (165)
Every interior stationary point lies on the curve α = α λ ( r ) \alpha=\alpha_\lambda(r) α = α λ ( r ) ; increasing (decreasing) portions are local maxima (minima). Since ∂ r F λ ( 0 + ) = 2 α κ λ 2 > 0 \partial_r\mathcal{F}_\lambda(0^+)=2\alpha\kappa_\lambda^2>0 ∂ r F λ ( 0 + ) = 2 α κ λ 2 > 0 , the boundary r = 0 r=0 r = 0 is never a maximizer for α > 0 \alpha>0 α > 0 . A critical endpoint of a line of first-order transitions occurs where the two folds α λ ′ ( r ) = 0 \alpha_\lambda'(r)=0 α λ ′ ( r ) = 0 merge, α λ ′ = α λ ′ ′ = 0 \alpha_\lambda'=\alpha_\lambda''=0 α λ ′ = α λ ′′ = 0 .
Theorem 1 (First-order transition in the RS theory). Fix λ > 0 \lambda>0 λ > 0 and suppose that at α e q \alpha_{\mathrm{eq}} α eq the function F λ ( ⋅ ; α e q ) \mathcal{F}_\lambda(\cdot;\alpha_{\mathrm{eq}}) F λ ( ⋅ ; α eq ) has exactly two global maximizers 0 < r − < r + < 1 0<r_-<r_+<1 0 < r − < r + < 1 , both nondegenerate (∂ r 2 F λ < 0 \partial_r^2\mathcal{F}_\lambda<0 ∂ r 2 F λ < 0 ). Then the two maxima continue smoothly as r ± ( α ) r_\pm(\alpha) r ± ( α ) near α e q \alpha_{\mathrm{eq}} α eq , the low (high) overlap maximum is the global one for α < α e q \alpha<\alpha_{\mathrm{eq}} α < α eq (α > α e q \alpha>\alpha_{\mathrm{eq}} α > α eq ) close to α e q \alpha_{\mathrm{eq}} α eq , the equilibrium overlap jumps by r + − r − > 0 r_+-r_->0 r + − r − > 0 , and
∂ α ϕ R S ∣ α e q + − ∂ α ϕ R S ∣ α e q − = 2 ( J λ ( r + ) − J λ ( r − ) ) = E t ∼ N ( 0 , 1 ) H 2 ( ψ λ ( r − , t ) ) − E t ∼ N ( 0 , 1 ) H 2 ( ψ λ ( r + , t ) ) > 0 , (166) \left.\partial_\alpha\phi_{\mathrm{RS}}\right|_{\alpha_{\mathrm{eq}}^+}-\left.\partial_\alpha\phi_{\mathrm{RS}}\right|_{\alpha_{\mathrm{eq}}^-}=2(\mathcal{J}_\lambda(r_+)-\mathcal{J}_\lambda(r_-))=\mathbb{E}_{t\sim\mathcal{N}(0,1)}H_2(\psi_\lambda(r_-,t))-\mathbb{E}_{t\sim\mathcal{N}(0,1)}H_2(\psi_\lambda(r_+,t))>0, \tag*{(166)} ∂ α ϕ RS ∣ α eq + − ∂ α ϕ RS ∣ α eq − = 2 ( J λ ( r + ) − J λ ( r − )) = E t ∼ N ( 0 , 1 ) H 2 ( ψ λ ( r − , t )) − E t ∼ N ( 0 , 1 ) H 2 ( ψ λ ( r + , t )) > 0 , (166) while ϕ R S \phi_{\mathrm{RS}} ϕ RS is continuous.
Proof. The implicit function theorem gives smooth branches r ± ( α ) r_\pm(\alpha) r ± ( α ) . Let Δ F ( α ) = F λ ( r + ( α ) ; α ) − F λ ( r − ( α ) ; α ) \Delta\mathcal{F}(\alpha)=\mathcal{F}_\lambda(r_+(\alpha);\alpha)-\mathcal{F}_\lambda(r_-(\alpha);\alpha) Δ F ( α ) = F λ ( r + ( α ) ; α ) − F λ ( r − ( α ) ; α ) . By stationarity, Δ F ′ ( α ) = ∂ α F λ ( r + ; α ) − ∂ α F λ ( r − ; α ) = 2 ( J λ ( r + ) − J λ ( r − ) ) > 0 \Delta\mathcal{F}'(\alpha)=\partial_\alpha\mathcal{F}_\lambda(r_+;\alpha)-\partial_\alpha\mathcal{F}_\lambda(r_-;\alpha)=2(\mathcal{J}_\lambda(r_+)-\mathcal{J}_\lambda(r_-))>0 Δ F ′ ( α ) = ∂ α F λ ( r + ; α ) − ∂ α F λ ( r − ; α ) = 2 ( J λ ( r + ) − J λ ( r − )) > 0 by Proposition 6. Hence Δ F < 0 \Delta\mathcal{F}<0 Δ F < 0 just below and > 0 >0 > 0 just above α e q \alpha_{\mathrm{eq}} α eq , so each global maximizer is global at each α \alpha α , continuity excludes other branches nearby. Along each smooth branch d d α ϕ R S = ∂ α F λ = 2 J λ ( r ⋆ ) \frac{\mathrm{d}}{\mathrm{d}\alpha}\phi_{\mathrm{RS}}=\partial_\alpha\mathcal{F}_\lambda=2\mathcal{J}_\lambda(r_\star) d α d ϕ RS = ∂ α F λ = 2 J λ ( r ⋆ ) , which gives Eq. (166) . ■
By Eq. (74) , Eq. (166) is a discontinuous drop of the predictive entropy of a fresh label. Stability here refers to the scalar RS potential; it is not a stability analysis against replica-symmetry breaking.
Message passing
We discuss here the Bayes-optimal generalized approximate message passing (GAMP) method [21 , 25 , 26 ] adapting it to our setting.
The GAMP algorithm relies on a factorized weight prior, an output likelihood, and a dense random input matrix with independent, centered entries of order N − 1 / 2 N^{-1/2} N − 1/2 . In particular, with this last assumption, each local field — defined from the random input matrix — is a sum of many weak contributions and, within the message-passing approximation, admits a Gaussian approximation at large N N N , reducing the output-message calculations to one-dimensional integrals.
For the case considered in this work, the random input matrix is F μ i = x i μ / N F_{\mu i}=x_i^\mu/\sqrt{N} F μ i = x i μ / N , and the output channel is P o u t ( ξ ∣ h ) = 1 { s λ ( h ) = ξ } P_{\mathrm{out}}(\xi\mid h)=\mathbf{1}\{s_\lambda(h)=\xi\} P out ( ξ ∣ h ) = 1 { s λ ( h ) = ξ } .
Remark 2. Note that the GAMP algorithm uses independent N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) weight priors. This differs from the spherical prior of our model, at finite N N N . Hence, our comparison rests on their common reduced RS potential, as explained in Remark 1 of Appendix B3. In particular, the state evolution we derive below is the matched large-system description used in this comparison. Its application to our Rademacher inputs and discontinuous channel carries the qualifications discussed in Appendices B1 and B3.
For a Gaussian field prediction of mean ω \omega ω and variance V V V , define
Z ξ ( ω , V ) : = ∫ d h N ( h ; ω , V ) P o u t ( ξ ∣ h ) , g o u t ( ω , V , ξ ) : = ∂ ω ln Z ξ ( ω , V ) . (167) Z_\xi(\omega,V):=\int dh\,\mathcal{N}(h;\omega,V)P_{\mathrm{out}}(\xi\mid h),\qquad g_{\mathrm{out}}(\omega,V,\xi):=\partial_\omega\ln Z_\xi(\omega,V). \tag*{(167)} Z ξ ( ω , V ) := ∫ d h N ( h ; ω , V ) P out ( ξ ∣ h ) , g out ( ω , V , ξ ) := ∂ ω ln Z ξ ( ω , V ) . (167)
In the model we consider, Z + 1 = p λ ( ω , V ) Z_{+1}=p_\lambda(\omega,V) Z + 1 = p λ ( ω , V ) and Z − 1 = 1 − p λ ( ω , V ) Z_{-1}=1-p_\lambda(\omega,V) Z − 1 = 1 − p λ ( ω , V ) , with p λ p_\lambda p λ defined in (B22). Thus, Z ξ Z_\xi Z ξ is the probability assigned to the observed label under the Gaussian field prediction. The quantity V g o u t Vg_{\mathrm{out}} V g out is the change in its mean after conditioning on that label. Let w ^ i k \widehat{w}_i^k w i k and v i k v_i^k v i k be the estimated mean and variance of weight i i i at iteration k k k , respectively. The undamped updates then give
V μ k = ∑ i F μ i 2 v i k , ω μ k = ∑ i F μ i w ^ i k − V μ k g μ k − 1 , (168) V_\mu^k=\sum_i F_{\mu i}^2v_i^k,\qquad\omega_\mu^k=\sum_i F_{\mu i}\widehat{w}_i^k-V_\mu^kg_\mu^{k-1}, \tag*{(168)} V μ k = i ∑ F μ i 2 v i k , ω μ k = i ∑ F μ i w i k − V μ k g μ k − 1 , (168)
where the term subtracted in ω μ k \omega_\mu^k ω μ k takes into account the so-called Onsager correction . After the update, we can then recompute g μ k = g o u t ( ω μ k , V μ k , ξ μ ) g_\mu^k=g_{\mathrm{out}}(\omega_\mu^k,V_\mu^k,\xi^\mu) g μ k = g out ( ω μ k , V μ k , ξ μ ) and a μ k = − ∂ ω g o u t ( ω μ k , V μ k , ξ μ ) a_\mu^k=-\partial_\omega g_{\mathrm{out}}(\omega_\mu^k,V_\mu^k,\xi^\mu) a μ k = − ∂ ω g out ( ω μ k , V μ k , ξ μ ) . The observation messages yield a quadratic approximation to the effective log-likelihood of each weight, with B i k B_i^k B i k and A i k A_i^k A i k controlling its linear and quadratic terms, respectively. Combining it with the standard Gaussian prior gives
A i k = ∑ μ F μ i 2 a μ k , B i k = ∑ μ F μ i g μ k , A_i^k=\sum_\mu F_{\mu i}^2a_\mu^k,\qquad B_i^k=\sum_\mu F_{\mu i}g_\mu^k, A i k = μ ∑ F μ i 2 a μ k , B i k = μ ∑ F μ i g μ k ,
w ^ i k + 1 = A i k w ^ i k + B i k 1 + A i k , v i k + 1 = 1 1 + A i k . (169) \widehat{w}_i^{k+1}=\frac{A_i^k\widehat{w}_i^k+B_i^k}{1+A_i^k},\qquad v_i^{k+1}=\frac{1}{1+A_i^k}. \tag*{(169)} w i k + 1 = 1 + A i k A i k w i k + B i k , v i k + 1 = 1 + A i k 1 . (169)
The uninformed initialization corresponds to w ^ 0 = 0 \widehat{w}^0=0 w 0 = 0 , v i 0 = 1 v_i^0=1 v i 0 = 1 , and g μ − 1 = 0 g_\mu^{-1}=0 g μ − 1 = 0 . The finite-N N N implementation damps these updates; numerical details are given in Appendix § 1.14 .
State evolution describes the typical behavior of these vector updates as N , P → ∞ N,P\to\infty N , P → ∞ at fixed α = P / N \alpha=P/N α = P / N . On the matched Bayes-optimal trajectory, the limiting teacher overlap and squared norm agree, i.e.,
m k = lim N → ∞ w ^ k ⋅ w ∗ N , q k = lim N → ∞ ∥ w ^ k ∥ 2 N , m k = q k = : r k . (170) m_k=\lim_{N\to\infty}\frac{\widehat{w}^k\cdot w^*}{N},\qquad q_k=\lim_{N\to\infty}\frac{\lVert\widehat{w}^k\rVert^2}{N},\qquad m_k=q_k=:r_k. \tag*{(170)} m k = N → ∞ lim N w k ⋅ w ∗ , q k = N → ∞ lim N ∥ w k ∥ 2 , m k = q k =: r k . (170)
The associated mean squared error per weight is 1 − r k 1-r_k 1 − r k . The effective teacher field conditional on its prediction is h ∗ ∣ ω ∼ N ( ω , 1 − r k ) h^*\mid\omega\sim\mathcal{N}(\omega,1-r_k) h ∗ ∣ ω ∼ N ( ω , 1 − r k ) , with ω = r k t \omega=\sqrt{r_k}t ω = r k t and t ∼ N ( 0 , 1 ) t\sim\mathcal{N}(0,1) t ∼ N ( 0 , 1 ) . Hence P ( ξ = + 1 ∣ t ) = ψ λ ( r k , t ) \mathbb{P}(\xi=+1\mid t)=\psi_\lambda(r_k,t) P ( ξ = + 1 ∣ t ) = ψ λ ( r k , t ) . Writing p = p λ ( ω , V ) p=p_\lambda(\omega,V) p = p λ ( ω , V ) , averaging the two possible label values gives E ξ ∣ ω [ g o u t 2 ] = ( ∂ ω p ) 2 / [ p ( 1 − p ) ] \mathbb{E}_{\xi|\omega}[g_{\mathrm{out}}^2]=(\partial_\omega p)^2/[p(1-p)] E ξ ∣ ω [ g out 2 ] = ( ∂ ω p ) 2 / [ p ( 1 − p )] , the same value being achieved also by the average curvature E ξ ∣ ω [ a ] \mathbb{E}_{\xi|\omega}[a] E ξ ∣ ω [ a ] . Since F μ i 2 = 1 / N F_{\mu i}^2=1/N F μ i 2 = 1/ N , the coefficient A i k A_i^k A i k is independent of the weight index i i i and converges in the large-system limit to
A k = α E [ g o u t 2 ] = α E t [ [ ∂ ω p λ ( r k t , 1 − r k ) ] 2 ψ λ ( r k , t ) [ 1 − ψ λ ( r k , t ) ] ] = 4 α J ( r k ) . (171) A_k=\alpha\mathbb{E}[g_{\mathrm{out}}^2]=\alpha\mathbb{E}_t\left[\frac{\left[\partial_\omega p_\lambda(\sqrt{r_k}t,1-r_k)\right]^2}{\psi_\lambda(r_k,t)\left[1-\psi_\lambda(r_k,t)\right]}\right]=4\alpha\mathcal{J}(r_k). \tag*{(171)} A k = α E [ g out 2 ] = α E t [ ψ λ ( r k , t ) [ 1 − ψ λ ( r k , t ) ] [ ∂ ω p λ ( r k t , 1 − r k ) ] 2 ] = 4 α J ( r k ) . (171)
where the last equality is the Fisher-information identity (E2).
Let now R i k = w ^ i k + B i k A i k R_i^k=\widehat{w}_i^k+\frac{B_i^k}{A_i^k} R i k = w i k + A i k B i k denote the center of the effective Gaussian likelihood for weight i i i , obtained by combining the observation messages at iteration k k k . In the matched large-system description, the joint statistics of w i ∗ w_i^* w i ∗ and R i k R_i^k R i k are represented by the scalar model R = W ∗ + Z A k R=W^*+\frac{Z}{\sqrt{A_k}} R = W ∗ + A k Z , where W ∗ W^* W ∗ represents a typical teacher-weight component, W ∗ W^* W ∗ and Z Z Z are independent standard Gaussian variables, and A k A_k A k is the limiting value of A i k A_i^k A i k . Thus, R R R acts as a noisy observation of the teacher weight, with noise variance 1 / A k 1/A_k 1/ A k . Combining the corresponding Gaussian likelihood with the standard Gaussian prior gives the posterior mean and variance used in the next weight update, i.e.,
W ^ n e w = A k 1 + A k R = A k 1 + A k W ∗ + A k 1 + A k Z , E [ W ∗ W ^ ] = E [ ( W ^ n e w ) 2 ] = A k 1 + A k . (172) \widehat{W}^{\mathrm{new}}=\frac{A_k}{1+A_k}R=\frac{A_k}{1+A_k}W^*+\frac{\sqrt{A_k}}{1+A_k}Z,\qquad\mathbb{E}[W^*\widehat{W}]=\mathbb{E}[(\widehat{W}^{\mathrm{new}})^2]=\frac{A_k}{1+A_k}. \tag*{(172)} W new = 1 + A k A k R = 1 + A k A k W ∗ + 1 + A k A k Z , E [ W ∗ W ] = E [( W new ) 2 ] = 1 + A k A k . (172)
From this, recalling the definition of r k r_k r k in (F4), and taking into account (F5) and (F6), one can then derive the overlap recurrence relation
r k + 1 = T α , λ ( r k ) : = 4 α J λ ( r k ) 1 + 4 α J λ ( r k ) . (173) r_{k+1}=T_{\alpha,\lambda}(r_k):=\frac{4\alpha J_\lambda(r_k)}{1+4\alpha J_\lambda(r_k)}. \tag*{(173)} r k + 1 = T α , λ ( r k ) := 1 + 4 α J λ ( r k ) 4 α J λ ( r k ) . (173)
To connect this recurrence relation to the RS calculation, set S λ ( r ) : = E t H 2 [ ψ λ ( r , t ) ] S_\lambda(r):=\mathbb{E}_{t}H_2[\psi_\lambda(r,t)] S λ ( r ) := E t H 2 [ ψ λ ( r , t )] . The heat equation (E1) and Gaussian integration by parts give S λ ′ ( r ) = − 1 2 E t [ ( ∂ t ψ λ ) 2 ψ λ ( 1 − ψ λ ) ] = − 2 J λ ( r ) S'_\lambda(r)=-\frac{1}{2}\mathbb{E}_{t}\left[\frac{(\partial_t\psi_\lambda)^2}{\psi_\lambda(1-\psi_\lambda)}\right]=-2J_\lambda(r) S λ ′ ( r ) = − 2 1 E t [ ψ λ ( 1 − ψ λ ) ( ∂ t ψ λ ) 2 ] = − 2 J λ ( r ) , and ∂ r F λ ( r ; α ) = − 1 2 ( 1 − r ) 2 + 2 α J λ ( r ) \partial_rF_\lambda(r;\alpha)=-\frac{1}{2(1-r)^2}+2\alpha J_\lambda(r) ∂ r F λ ( r ; α ) = − 2 ( 1 − r ) 2 1 + 2 α J λ ( r ) . Thus the RS saddle-point equation is precisely the fixed-point condition for (F7), that is,
∂ r F λ ( r ; α ) = 0 ⟺ r 1 − r = 4 α J λ ( r ) ⟺ r = T α , λ ( r ) . (174) \partial_rF_\lambda(r;\alpha)=0\quad\Longleftrightarrow\quad\frac{r}{1-r}=4\alpha J_\lambda(r)\quad\Longleftrightarrow\quad r=T_{\alpha,\lambda}(r). \tag*{(174)} ∂ r F λ ( r ; α ) = 0 ⟺ 1 − r r = 4 α J λ ( r ) ⟺ r = T α , λ ( r ) . (174)
The same self-consistency equation therefore governs the RS stationary overlaps and the fixed points of matched GAMP state evolution. Their comparison concerns macroscopic order parameters: GAMP estimates posterior means, whereas the Gibbs generalization error in (13) refers to posterior samples. The Nishimori identities identify the averaged teacher–mean and replica overlaps; with the assumed overlap concentration, these yield the common scalar parameter r r r .
The selection of a solution remains essential. RS equilibrium maximizes F λ F_\lambda F λ , while GAMP converges to an attracting fixed point accessible from its initialization. At a fixed point, local attraction requires ∣ T α , λ ′ ( r ) ∣ < 1 \lvert T'_{\alpha,\lambda}(r)\rvert<1 ∣ T α , λ ′ ( r )∣ < 1 , and
T α , λ ′ ( r ) = 4 α ( 1 − r ) 2 J λ ′ ( r ) , ∂ r 2 F λ ( r ; α ) = T α , λ ′ ( r ) − 1 2 ( 1 − r ) 2 . (175) T'_{\alpha,\lambda}(r)=4\alpha(1-r)^2J'_\lambda(r),\qquad\partial_r^2F_\lambda(r;\alpha)=\frac{T'_{\alpha,\lambda}(r)-1}{2(1-r)^2}. \tag*{(175)} T α , λ ′ ( r ) = 4 α ( 1 − r ) 2 J λ ′ ( r ) , ∂ r 2 F λ ( r ; α ) = 2 ( 1 − r ) 2 T α , λ ′ ( r ) − 1 . (175)
Where J λ ′ ( r ) ≥ 0 J'_\lambda(r)\geq0 J λ ′ ( r ) ≥ 0 , a nondegenerate local maximum is attracting and a local minimum is repelling. This includes both equilibrium and metastable maxima in the regime illustrated in Figure 5 b. When the state-evolution map T α , λ T_{\alpha,\lambda} T α , λ is nondecreasing in r r r , iteration from the uninformed initialization r 0 = 0 r_0=0 r 0 = 0 converges to its smallest fixed point, explaining why an uninformed start follows the weak branch while that branch exists. This monotonicity is verified numerically in the investigated range 0.5 ≤ λ ≤ 4 0.5\leq\lambda\leq4 0.5 ≤ λ ≤ 4 . For λ > λ c \lambda>\lambda_c λ > λ c , the coexistence interval contains three stationary overlaps r w < r u < r s r_{\mathrm{w}}<r_{\mathrm{u}}<r_{\mathrm{s}} r w < r u < r s , that is, weak and strong local maxima, separated by an unstable local minimum. The strong maximum and the intermediate minimum appear together at the lower spinodal α s p − \alpha_{\mathrm{sp}}^- α sp − . At α e q \alpha_{\mathrm{eq}} α eq , the two maxima have equal height and exchange their equilibrium preference. The weak maximum survives until α s p + \alpha_{\mathrm{sp}}^+ α sp + , where it merges with the intermediate minimum. The expected branch selection is summarized in Table II .
Table II. Expected branch selection in the first-order regime within the scalar state-evolution description. An informed start is placed sufficiently close to the strong attractor whenever it exists. In the two middle intervals an intermediate unstable stationary point is also present. The open intervals exclude coexistence and the spinodals. Finite-N N N and finite-time effects can modify the apparent switching loads.
Figure 5. (a) Equilibrium RS overlaps and GAMP estimates at N = 4000 N = 4000 N = 4000 . Filled circles and open squares denote uninformed and informed initializations, respectively. Dotted vertical segments mark equilibrium jumps; dashed curves show metastable branches for λ = 3 \lambda= 3 λ = 3 . (b) Stationary branches at λ = 2.2 \lambda= 2.2 λ = 2.2 : Equilibrium (solid orange), metastable (dashed orange), and unstable (dotted gray). Diamonds mark spinodals; the vertical dashed line marks coexistence. Inset: F λ − max r F λ \mathcal{F}_{\lambda} - \max_{r}\mathcal{F}_{\lambda} F λ − max r F λ at α = 2.28 \alpha= 2.28 α = 2.28 (light blue), α e q \alpha_{\mathrm{eq}} α eq (black), and 2.70 2.70 2.70 (red).
The two numerical protocols — i.e., informed and uninformed — use the same GAMP updates. The uninformed start supplies no information about the teacher direction. The informed start, w ^ 0 = 0.995 w ∗ \widehat{w}^{\,0}=\sqrt{0.995}\,w^* w 0 = 0.995 w ∗ with v i 0 = 0.005 v_i^0=0.005 v i 0 = 0.005 , supplies teacher information to test the existence and stability of the strong attractor. This diagnostic initialization need not satisfy the matched scalar identity m k = q k m_k = q_k m k = q k at finite iterations. The measured finite-N N N overlap is m = w ⋅ w ∗ ^ / N m = \hat{\boldsymbol{w} \cdot\boldsymbol{w}^{*}}/N m = w ⋅ w ∗ ^ / N . Figure 3 makes the table clear at λ = 2.2 \lambda= 2.2 λ = 2.2 , where α s p − ≃ 2.18717 \alpha_{\mathrm{sp}}^{-} \simeq2.18717 α sp − ≃ 2.18717 , α e q ≃ 2.36387 \alpha_{\mathrm{eq}} \simeq2.36387 α eq ≃ 2.36387 , and α s p + ≃ 3.04040 \alpha_{\mathrm{sp}}^{+} \simeq3.04040 α sp + ≃ 3.04040 . The solid orange curve denotes the equilibrium maximum, the dashed orange curve the metastable maximum, and the dotted gray curve the intermediate minimum. Diamonds mark the spinodals and the vertical dashed line marks coexistence. Filled circles from uninformed GAMP follow the weak branch beyond α e q \alpha_{\mathrm{eq}} α eq and leave it near α s p + \alpha_{\mathrm{sp}}^{+} α sp + ; open squares from informed GAMP follow the strong branch down to α s p − \alpha_{\mathrm{sp}}^{-} α sp − . For example, at λ = 2.2 \lambda= 2.2 λ = 2.2 and α = 2.5 \alpha= 2.5 α = 2.5 , state evolution has a weakly aligned fixed point at r w ≃ 0.17960 r_{\mathrm{w}} \simeq0.17960 r w ≃ 0.17960 and a strongly aligned fixed point at r s ≃ 0.90083 r_{\mathrm{s}} \simeq0.90083 r s ≃ 0.90083 . The RS equilibrium selects the strongly aligned solution, whereas GAMP from an uninformed initialization converges to the weakly aligned one. Thus α e q < α < α s p + \alpha_{\mathrm{eq}} < \alpha< \alpha_{\mathrm{sp}}^{+} α eq < α < α sp + is the interval where the equilibrium improvement is inaccessible to this uninformed iteration. Figure 5 a extends this comparison to several readout frequencies. At λ = 1 \lambda= 1 λ = 1 , GAMP follows the smooth equilibrium RS curve, whereas at λ = 2.2 \lambda= 2.2 λ = 2.2 and 3 3 3 its behavior depends on initialization. Specifically, informed runs track the strongly aligned branch when it exists, while uninformed runs remain weakly aligned beyond coexistence. For λ = 3 \lambda= 3 λ = 3 , this persistence extends throughout the displayed load range above α e q \alpha_{\mathrm{eq}} α eq .
Numerical methods and validation
We describe hereafter the numerical methods used to evaluate the RS functionals, select the physical branch, and treat coexistence and critical points. We additionally present the implementation and validation of Bayes-optimal GAMP.
All averages over t t t are computed exactly in the phase variable: θ = λ r t \theta= \lambda\sqrt{r}\,t θ = λ r t modulo 2 π 2\pi 2 π has the wrapped-normal density with standard deviation λ r \lambda\sqrt{r} λ r , evaluated by direct image sums (small width) or its Fourier series (large width). Using ψ ( θ ) + ψ ( − θ ) = 1 − ψ ( θ ) \psi(\theta) + \psi(-\theta) = 1 - \psi(\theta) ψ ( θ ) + ψ ( − θ ) = 1 − ψ ( θ ) and ψ ( π − θ ) = ψ ( θ ) \psi(\pi- \theta) = \psi(\theta) ψ ( π − θ ) = ψ ( θ ) , the integrands H 2 ( ψ ) H_2(\psi) H 2 ( ψ ) , ψ ( 1 − ψ ) \psi(1-\psi) ψ ( 1 − ψ ) and ( ∂ θ ψ ) 2 / [ ψ ( 1 − ψ ) ] (\partial_{\theta}\psi)^2/[\psi(1-\psi)] ( ∂ θ ψ ) 2 / [ ψ ( 1 − ψ )] reduce to [ 0 , π / 2 ] [0,\pi/2] [ 0 , π /2 ] , where they are integrated by composite Gauss-Legendre quadrature (order 24) on a mesh graded geometrically toward the fringe θ = 0 \theta= 0 θ = 0 at the scale min ( λ r , λ 1 − r ) \min(\lambda\sqrt{r},\lambda\sqrt{1-r}) min ( λ r , λ 1 − r ) . The smoothed square wave is evaluated as a sum of Gaussian interval probabilities ∑ k Φ [ θ + σ ∈ ( 2 k π , ( 2 k + 1 ) π ) ] \sum_k \Phi[\theta+\sigma\in(2k\pi,(2k+1)\pi)] ∑ k Φ [ θ + σ ∈ ( 2 k π , ( 2 k + 1 ) π )] , computing each difference of normal distribution functions on the side of the tail to avoid cancellation; 1 − ψ 1-\psi 1 − ψ is computed as an independent sum. The classical limit uses ψ = Φ ( r / ( 1 − r ) t ) \psi= \Phi\bigl(\sqrt{r/(1-r)}\,t\bigr) ψ = Φ ( r / ( 1 − r ) t ) with an analogous graded mesh.
Checks. (a) The quadrature for ε λ \varepsilon_{\lambda} ε λ agrees with the double series (D21) to ≤ 2 × 10 − 16 \leq2 \times10^{-16} ≤ 2 × 1 0 − 16 for λ ∈ { 0.5 , 1 , 2 , 3 } \lambda\in\{0.5,1,2,3\} λ ∈ { 0.5 , 1 , 2 , 3 } , r ∈ { 0.05 , 0.3 , 0.7 , 0.95 } r \in\{0.05,0.3,0.7,0.95\} r ∈ { 0.05 , 0.3 , 0.7 , 0.95 } . (b) J λ \mathcal{J}_{\lambda} J λ from Eq. (164) agrees with a centered finite difference of I λ \mathcal{I}_{\lambda} I λ to ≤ 10 − 9 \leq10^{-9} ≤ 1 0 − 9 relative accuracy, including r = 0.99 r = 0.99 r = 0.99 . (c) A Monte Carlo estimate of Eq. (29) with 2 × 10 6 2 \times10^{6} 2 × 1 0 6 samples agrees within its statistical error. (d) J λ ( 0 + ) = κ λ 2 \mathcal{J}_{\lambda}(0^{+}) = \kappa_{\lambda}^{2} J λ ( 0 + ) = κ λ 2 and the classical limit are reproduced. (e) The bounds of Propositions 4 and 1 hold on a grid λ ∈ [ 0.3 , 4 ] \lambda\in[0.3,4] λ ∈ [ 0.3 , 4 ] , r ∈ [ 0 , 0.99 ] r \in[0,0.99] r ∈ [ 0 , 0.99 ] .
For each λ \lambda λ we tabulate α λ ( r ) \alpha_{\lambda}(r) α λ ( r ) on a grid in u = − ln ( 1 − r ) ∈ [ 10 − 6 , 16 ] u=-\ln(1-r) \in[10^{-6},16] u = − ln ( 1 − r ) ∈ [ 1 0 − 6 , 16 ] (about 1700 points, dense near u = 0 u=0 u = 0 ), locate its folds by bounded optimization, and identify the increasing portions (maxima of F λ \mathcal{F}_{\lambda} F λ ). For given α \alpha α , each maximum is obtained by solving α λ ( r ) = α \alpha_{\lambda}(r)=\alpha α λ ( r ) = α on each increasing portion with Brent’s method, and the equilibrium is the one with the largest F λ \mathcal{F}_{\lambda} F λ . The coexistence load is the root of F λ ( r + ( α ) ; α ) − F λ ( r − ( α ) ; α ) \mathcal{F}_{\lambda}(r_{+}(\alpha);\alpha)-\mathcal{F}_{\lambda}(r_{-}(\alpha);\alpha) F λ ( r + ( α ) ; α ) − F λ ( r − ( α ) ; α ) in ( α s p − , α s p + ) (\alpha_{\mathrm{sp}}^{-},\alpha_{\mathrm{sp}}^{+}) ( α sp − , α sp + ) . The critical endpoint is the root in λ \lambda λ of min r ∂ u α λ \min_{r}\partial_{u}\alpha_{\lambda} min r ∂ u α λ . Results are in Table III; all values agree to the displayed digits with an independent implementation based on Gaussian interval sums and direct maximization of F λ \mathcal{F}_{\lambda} F λ on a grid.
We run Bayes-optimal GAMP [21 , 26 ] with Gaussian prior, Rademacher inputs F μ i = x i μ / N F_{\mu i}=x_i^{\mu}/\sqrt{N} F μ i = x i μ / N , and output function g o u t ( ω , V , y ) = ∂ ω ln Z y g_{\mathrm{out}}(\omega,V,y)=\partial_{\omega}\ln Z_y g out ( ω , V , y ) = ∂ ω ln Z y , Z + 1 = p λ ( ω , V ) Z_{+1}=p_{\lambda}(\omega,V) Z + 1 = p λ ( ω , V ) , Z − 1 = 1 − p λ ( ω , V ) Z_{-1}=1-p_{\lambda}(\omega,V) Z − 1 = 1 − p λ ( ω , V ) , evaluated with Gaussian interval sums together with ∂ ω g o u t \partial_{\omega}g_{\mathrm{out}} ∂ ω g out . Iterates are damped (factor 0.6), and runs stop when the rms change of the estimate is below 2 × 10 − 6 2 \times10^{-6} 2 × 1 0 − 6 or after 800 iterations. The uninformed initialization is w ^ = 0 \hat{w}=0 w ^ = 0 , unit variances; the informed one is w ^ = 0.995 w ∗ \hat{w}=\sqrt{0.995}\,w^{*} w ^ = 0.995 w ∗ with variances 0.005. We use N = 4000 N=4000 N = 4000 , λ ∈ { 1 , 2.2 , 3 } \lambda\in\{1,2.2,3\} λ ∈ { 1 , 2.2 , 3 } , and two independent instances per point; the overlap is m = w ^ ⋅ w ∗ / N m=\hat{w}\cdot w^{*}/N m = w ^ ⋅ w ∗ / N . Near the spinodals convergence is slow (critical slowing down) and the displayed values carry larger finite-time errors.
Fragmentation of the version space
In this last Section, we examine how the geometry of the version space evolves as the frequency parameter is varied. For each pattern let k μ ∈ Z k_{\mu} \in\mathbb{Z} k μ ∈ Z be the fringe index of the student field, h μ ∈ ( k μ π / λ , ( k μ + 1 ) π / λ ) h_{\mu} \in(k_{\mu}\pi/\lambda,(k_{\mu}+1)\pi/\lambda) h μ ∈ ( k μ π / λ , ( k μ + 1 ) π / λ ) ; the label is ( − 1 ) k μ (-1)^{k_{\mu}} ( − 1 ) k μ . The version space is the disjoint union
V = ⋃ k : ( − 1 ) k μ = ξ μ ∀ μ C k , C k = { w : w ⋅ x μ N ∈ ( k μ π λ , ( k μ + 1 ) π λ ) ∀ μ } . (176) \mathcal{V}=\bigcup_{\boldsymbol{k}:(-1)^{k_{\mu}}=\xi_{\mu}\mathrel{\forall}\mu}\mathcal{C}_{\boldsymbol{k}},\qquad\mathcal{C}_{\boldsymbol{k}}=\left\{w:\frac{w\cdot x^{\mu}}{\sqrt{N}}\in\left(\frac{k_{\mu}\pi}{\lambda},\frac{(k_{\mu}+1)\pi}{\lambda}\right)\ \mathrel{\forall}\mu\right\}. \tag*{(176)} V = k : ( − 1 ) k μ = ξ μ ∀ μ ⋃ C k , C k = { w : N w ⋅ x μ ∈ ( λ k μ π , λ ( k μ + 1 ) π ) ∀ μ } . (176)
A continuous path in V \mathcal{V} V cannot change any k μ k_{\mu} k μ , because h μ h_{\mu} h μ would have to cross a fringe of opposite label; hence every connected component of V \mathcal{V} V lies in a single cell. In the classical regime λ < π / N \lambda<\pi/\sqrt{N} λ < π / N , where ∣ h μ ∣ ≤ N < π / λ \lvert h_{\mu}\rvert\leq\sqrt{N}<\pi/\lambda ∣ h μ ∣ ≤ N < π / λ , only k μ ∈ { 0 , − 1 } k_{\mu}\in\{0,-1\} k μ ∈ { 0 , − 1 } occur and V \mathcal{V} V is the intersection of the sphere with a convex cone. Any dynamical system that evolves continuously at zero training error (gradient flows, Langevin or billiard dynamics restricted to V \mathcal{V} V ) is confined to its initial cell.
This has a practical consequence for finite-size checks. By the Nishimori property the teacher is a typical posterior sample, but a sampler started at the teacher and moving continuously samples only the teacher’s cell. We compared, at N = 60 N=60 N = 60 , α = 0.3 \alpha=0.3 α = 0.3 , λ = 2.2 \lambda=2.2 λ = 2.2 (ten instances), an exact great-circle hit-and-run sampler, which jumps between cells, with a reflective (billiard) sampler that is exact within a cell. The former gives an average overlap ⟨ r ⟩ \langle r\rangle ⟨ r ⟩ consistent with the RS/linear-response value 4 κ λ 2 α = 0.019 4\kappa_{\lambda}^{2}\alpha=0.019 4 κ λ 2 α = 0.019 up to finite-size fluctuations, whereas the latter overestimates it by an order of magnitude (see Table IV). Local samplers initialized at the teacher are therefore not suitable to test the equilibrium predictions; GAMP, which does not move within V \mathcal{V} V , is used instead.
Table IV. Numerically resolved RS transitions. Subscripts − - − and + + + denote the one-sided limits at α e q \alpha_{\mathrm{eq}} α eq . The critical endpoint is ( λ c , α c , r c ) = ( 1.94359 , 1.98100 , 0.58191 ) (\lambda_c,\alpha_c,r_c)=(1.94359,1.98100,0.58191) ( λ c , α c , r c ) = ( 1.94359 , 1.98100 , 0.58191 ) with ϵ λ ( r c ) = 0.41750 \epsilon_{\lambda}(r_c)=0.41750 ϵ λ ( r c ) = 0.41750 .
Table IV (PDF p. 27). Average teacher-student overlap at N = 60 N=60 N = 60 , P = 18 P=18 P = 18 (α = 0.3 \alpha=0.3 α = 0.3 ), λ = 2.2 \lambda=2.2 λ = 2.2 , over ten instances (mean ± \pm ± standard error).
References