affil0affil0affiliationtext: _The Abdus Salam International Center for
Theoretical Physics, Trieste, Italy_

# Fundamental limits of overparametrized
shallow neural networks for supervised learning

Francesco Camilli  Daria Tieplova and Jean Barbier

###### Abstract

We carry out an information-theoretical analysis of a two-layer neural network
trained from input-output pairs generated by a teacher network with matching
architecture, in overparametrized regimes. Our results come in the form of
bounds relating $i)$ the mutual information between training data and network
weights, or $ii)$ the Bayes-optimal generalization error, to the same
quantities but for a simpler (generalized) linear model for which explicit
expressions are rigorously known. Our bounds, which are expressed in terms of
the number of training samples, input dimension and number of hidden units,
thus yield fundamental performance limits for any neural network (and actually
any learning procedure) trained from limited data generated according to our
two-layer teacher neural network model. The proof relies on rigorous tools
from spin glasses and is guided by “Gaussian equivalence principles” lying at
the core of numerous recent analyses of neural networks. With respect to the
existing literature, which is either non-rigorous or restricted to the case of
the learning of the readout weights only, our results are information-
theoretic (i.e. are not specific to any learning algorithm) and, importantly,
cover a setting where _all_ the network parameters are trained.

††footnotetext<EMAIL_ADDRESS>
##  1 Introduction

Artificial neural networks (NNs) are universal approximators [1, 2, 3] with
remarkable abilities for supervised learning tasks such as regression or
classification. In particular, modern deep neural networks, originally
inspired by multilayer perceptrons [4, 5, 6, 7, 8], achieve exceptional
performance in image classification or speech recognition [9] just to name a
few examples. However, despite the important activity revolving around them,
their theoretical understanding remains rather poor.

One reason for the lack of strong theoretical guarantees for realistic NN
models is related to the complex interplay between at least three aspects,
whose individual effects are hard to single out: their architecture, the
structure inherent to the data sets on which they are trained, as well as the
algorithms and optimization procedures used to do so. It is therefore of
crucial interest to tackle well defined theoretical models which are rich
enough to capture some of the features of real NNs while remaining
theoretically tractable. In this work, we propose to analyse a teacher-student
set-up from a Bayesian-optimal perspective, with random input data and
dependent responses generated according to a rule based on a teacher NN. This
setting has the advantage to disentangle the aforementioned three components
of NN learning by allowing us to mostly focus on how the _architecture_ of the
NN used for learning (and data generation), and how the amount of accessible
data, influence the prediction performance. More precisely, we are going to
show that when learning a complex rule linking _unstructured_ inputs to
responses in the _information-theoretic optimal way_ , and this in an
_overparametrized regime_ , then an explicit characterization of the
prediction capabilities of the NN is possible. Our results being of an
information-theoretic nature, they will not depend on a specific learning
procedure. Moreover because the inputs will be structure-less, the conclusions
drawn will essentially capture architecture-dependent features of the
learning; in the present case, the effect of overparametrization.

A key challenge one has to face when analysing NNs is the presence of non-
linear activation functions, whose role is essential for the network
expressivity. Models with linear activations cannot capture non-linearities,
but they serve as a starting point for deeper understanding [10]. The case of
a narrow hidden layer was already studied more than thirty years ago [11, 12,
13] and more recently in [14]. However, in the more challenging regimes where
_all layers are large and of comparable sizes_ it was observed (for instance
in [15, 16, 17, 18, 19]) that certain NNs models behave like finely tuned
linear models regardless of the activation type, given sufficient regularity.
From this observations, a whole set of “Gaussian equivalence principles”
(GEPs) have emerged as valuable tools for handling non-linear activations in
both rigorous and more heuristic approaches. GEPs leverage a well-known fact
in high-dimensional probability: suitably rescaled low-dimensional projections
of high-dimensional vectors with weakly correlated components exhibit Gaussian
behavior. Classical results [20, 21] and recent developments [22, 23] support
the validity of GEPs in various high-dimensional inference contexts, such as
in the description of certain observables for shallow neural networks [17, 18,
19].

However, the extent to which GEPs apply to the _information-theoretic study of
NNs where all weights are learned_ remains uncertain. Certain scaling regimes
relating the number of data samples and network weights must cause GEPs to
break down, as NNs do not always behave like linear models [24]. This paper
aims to bridge this gap by means of rigorous mathematical physics techniques
developed in the study of spin glasses. We demonstrate the existence of a
scaling regime for two-layer networks where GEPs are rigorously applicable,
with the number of data playing a central role. As a result, we establish the
information-theoretical equivalence between a two-layer NN and a generalized
linear model, that hence share the same optimal generalization error.

#### Notations

Bold notations are reserved for vectors and matrices. By default a vector
${\mathbf{x}}$ is a column vector, and its transpose
${\mathbf{x}}^{\intercal}$ is therefore a row vector. Thus the usual $L_{2}$
norm $\|{\mathbf{x}}\|^{2}={\mathbf{x}}^{\intercal}{\mathbf{x}}$ and
${\mathbf{x}}{\mathbf{x}}^{\intercal}$ is a rank-one projector.
$\mathbb{E}_{A}$ is an expectation with respect to the random variable $A$;
$\mathbb{E}$ is an expectation with respect to all random variables entering
the ensuing expression. For a function $F$ of one argument we denote
$F^{\prime}$ its derivative. Notations like $i\leq N$ always implicitly assume
that the index $i$ starts at $1$. We often compactly write
$\mathbb{E}(\cdots)^{2}=\mathbb{E}[(\cdots)^{2}]\geq(\mathbb{E}(\cdots))^{2}=\mathbb{E}^{2}(\cdots)$
and similarly for other functions, we denote equivalently
$\mathbb{E}[f(\cdots)]$ and $\mathbb{E}f(\cdots)$. For any functions $f$ and
$g$, $f=O(g)$ means that there exists a constant $K$ such that $|f|\leq K|g|$;
in other words we simply denote $O(g):=O(|g|)$ where in the r.h.s. we use the
standard big O notation. Hence, taken for instance a Gaussian r.v.
$Z\sim\mathcal{N}(0,1)$, $f=O(Z)$ does _not_ imply $\mathbb{E}f=0$, but rather
$|\mathbb{E}f|\leq\mathbb{E}|f|\leq K\mathbb{E}|Z|$.

#### Acknowledgements

The authors were funded by the European Union (ERC, CHORAL, project number
101039794). Views and opinions expressed are however those of the author only
and do not necessarily reflect those of the European Union or the European
Research Council. Neither the European Union nor the granting authority can be
held responsible for them. We wish to thank Marco Mondelli for suggesting
meaningful references, and Rosalba Pacelli and Pietro Rotondo for fruitful
clarifications on [10, 25].

##  2 Setting and main results

###  2.1 Bayesian-optimal learning of a shallow network in the teacher-student
set-up

We consider supervised learning with a Bayesian two-layer neural network in a
teacher-student setup, with matched architecture for teacher (i.e., data-
generating) and student (i.e., trained) models. To be precise, let the dataset
be $\mathcal{D}_{n}=\\{({\mathbf{X}}_{\mu},Y_{\mu})\\}_{\mu=1}^{n}$, with
inputs ${\mathbf{X}}_{\mu}\in\mathbb{R}^{d}$ and responses
$Y_{\mu}\in\mathbb{R}$. The $Y_{\mu}$ could also be taken from
$\mathbb{R}^{K}$ with $K$ independent of $d,p,n$ without much changes. The
teacher network generates the responses according to the following rule:

$\displaystyle
Y_{\mu}=f\Big{(}\frac{{\mathbf{a}}^{*\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{{\mathbf{W}}^{*}{\mathbf{X}}_{\mu}}{\sqrt{d}}\Big{)};{\mathbf{A}}_{\mu}\Big{)}+\sqrt{\Delta}Z_{\mu}\,.$
(1)

Here, ${\mathbf{a}}^{*}\in\mathbb{R}^{p}$ and
${\mathbf{W}}^{*}\in\mathbb{R}^{p\times d}$. The readout function $f$ can
include stochasticity, modeled through its second argument
${\mathbf{A}}_{\mu}$ which are independent and identically distributed
(i.i.d.) random variables in $\mathbb{R}^{k}$ with $k$ fixed, whose common
distribution is denoted by $P_{A}$. Whenever it is not specified, real
functions are applied component-wise to vectors, such as the non linearities
$f,\varphi$. We assume the following regularity hypotheses:

A1)

The activation function $\varphi:\mathbb{R}\mapsto\mathbb{R},\,\varphi\in
C^{3}$ is $c$-Lipschitz for some absolute constant $c$, is an odd function,
and has bounded second and third derivatives.

A2)

The readout function $f$ as well as its first and second derivatives are
$P_{A}$-almost surely bounded.

We draw the independent inputs
${\mathbf{X}}_{\mu}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
iid}}}}{{\sim}}}\mathcal{N}(0,I_{d})$ from the standard Gaussian measure.
Furthermore, Gaussian label noise
$Z_{\mu}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
iid}}}}{{\sim}}}\mathcal{N}(0,1)$ is added in (1), whose variance is tuned by
$\Delta>0$. Introducing the output kernel

$\displaystyle P_{\rm out}(y\mid x):=\int
P_{A}(d{\mathbf{A}})\frac{1}{\sqrt{2\pi\Delta}}\exp\Big{(}-\frac{1}{2\Delta}(y-f(x;{\mathbf{A}}))^{2}\Big{)}\,,$
(2)

once can see that the random outputs are generated independently,
conditionally on the teacher parameters
${\boldsymbol{\theta}}^{*}=({\mathbf{a}}^{*},{\mathbf{W}}^{*})$ and the
inputs, as

$\displaystyle Y_{\mu}\sim P_{\rm
out}\Big{(}\cdot\mid\frac{{\mathbf{a}}^{*\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{{\mathbf{W}}^{*}{\mathbf{X}}_{\mu}}{\sqrt{d}}\Big{)}\Big{)}\,.$
(3)

The probability distribution for the weights of the teacher network are drawn
from a centered Gaussian factorized prior distribution. Taking them with
different variances is possible but it does not add much to the result, so we
consider them all equal to one for our purposes:
$a_{i}^{*},W_{ij}^{*}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
iid}}}}{{\sim}}}\mathcal{N}(0,1)$. The same Gaussian law is used as prior
distribution for the Bayesian student neural network model. In empirical risk
minimization, a Gaussian prior would induce a $L^{2}$ norm regularization for
the weights.

In this paper we will instead deal with Bayesian learning in the so-called
_Bayes-optimal setting_ , which is the proper framework to quantify the
fundamental performance limits of neural networks. Concretely, the Bayes-
optimal scenario corresponds to a realizable matched setting where the student
network has exactly the same architecture as the teacher network used to
generate the responses in the data $\mathcal{D}_{n}$. The analysis in this
setting therefore yields the best information-theoretically achievable
student’s generalization performance whenever optimally trained, namely, when
using Bayesian learning based on the posterior distribution of the student’s
parameters. As a consequence,

> _our results lay down fundamental upper bounds for the performance of any
> neural networks, Bayesian or not, trained in any possible manner (including
> empirical risk minimization rather than Bayesian learning) or, more
> generally, for any learning procedure for the supervised task at hand.
> Moreover, both the readout and internal hidden layer are trained, with a
> number of hidden units that can grow proportionally to the input dimension._

To the best of our knowledge, this is the first rigorous result of this kind
in this challenging scaling regime.

More formally, a student network is said to be Bayes-optimal if it employs the
same output kernel $P_{\rm out}$ as used by the teacher network, or
equivalently same number of layers and layers widths, readout $f$ and
activation $\varphi$, label noise variance $\Delta$, as well as same prior law
for its weights. Bayes-optimal learning is then based on the Bayes posterior
of the network parameters ${\boldsymbol{\theta}}=({\mathbf{a}},{\mathbf{W}})$
which reads

$\displaystyle
dP({\boldsymbol{\theta}}\mid\mathcal{D}_{n})=\frac{1}{\mathcal{Z}(\mathcal{D}_{n})}\prod_{\mu=1}^{n}P_{\rm
out}\Big{(}Y_{\mu}\mid\frac{{\mathbf{a}}^{\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{{\mathbf{W}}{\mathbf{X}}_{\mu}}{\sqrt{d}}\Big{)}\Big{)}D{\boldsymbol{\theta}}$
(4)

where for brevity

$\displaystyle
D{\boldsymbol{\theta}}:=\prod_{i=1}^{p}\frac{da_{i}}{\sqrt{2\pi}}e^{-\frac{a_{i}^{2}}{2}}\prod_{i=1}^{p}\prod_{j=1}^{d}\frac{dW_{ij}}{\sqrt{2\pi}}e^{-\frac{W_{ij}^{2}}{2}}=:D{\mathbf{a}}D{\mathbf{W}}\,.$
(5)

We will often use the notation $D$ for densities of objects whose entries are
i.i.d. standard Gaussian variables. The normalization of the posterior
distribution will be referred to as _partition function_ :

$\displaystyle\mathcal{Z}(\mathcal{D}_{n}):=\int
D{\boldsymbol{\theta}}\exp\Big{(}\sum_{\mu=1}^{n}u_{Y_{\mu}}(s_{\mu})\Big{)}$
(6)

where we have introduced the two further definitions $u_{y}(x)=\log P_{\rm
out}(y\mid x)$ and

$\displaystyle
s_{\mu}:=\frac{{\mathbf{a}}^{\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{{\mathbf{W}}{\mathbf{X}}_{\mu}}{\sqrt{d}}\Big{)}\,,\quad
S_{\mu}:=\frac{{\mathbf{a}}^{*\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{{\mathbf{W}}^{*}{\mathbf{X}}_{\mu}}{\sqrt{d}}\Big{)}\,.$
(7)

Note that the partition function is random through the randomness of the
dataset $\mathcal{D}_{n}$. Then, (optimal) Bayesian learning means that the
predictor $\hat{Y}_{\rm Bayes}({\mathbf{X}}_{\rm new})$ of the response
associated with a fresh input test sample corresponds to the mean of the Bayes
posterior distribution of the response given the training data:

$\displaystyle\hat{Y}_{\rm Bayes}({\mathbf{X}}_{\rm new}):=\mathbb{E}[Y_{\rm
new}\mid\mathcal{D}_{n},{\mathbf{X}}_{\rm new}]=\int dY\,Y\,P_{\rm
out}\Big{(}Y\mid\frac{{\mathbf{a}}^{\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{{\mathbf{W}}{\mathbf{X}}_{\rm
new}}{\sqrt{d}}\Big{)}\Big{)}dP({\boldsymbol{\theta}}\mid\mathcal{D}_{n})\,.$
(8)

We will sometimes employ the language of statistical mechanics. In particular
we interpret the posterior distribution as a Boltzmann-Gibbs measure over
degrees of freedom which are the network weights. We shall denote the
expectations w.r.t. the posterior with the so-called Gibbs brackets
$\langle\cdot\rangle$. For future convenience we introduce also its replicated
version: for a function $g$ dependent of $k$ copies
$({\boldsymbol{\theta}}_{b})_{b\leq k}$ of the parameters,

$\displaystyle\langle g\rangle^{\otimes
k}:=\frac{1}{\mathcal{Z}(\mathcal{D}_{n})^{k}}\int\prod_{b=1}^{k}D{\boldsymbol{\theta}}_{b}\prod_{\mu=1}^{n}P_{\rm
out}\Big{(}Y_{\mu}\mid\frac{{\mathbf{a}}^{\intercal}_{b}}{\sqrt{p}}\varphi\Big{(}\frac{{\mathbf{W}}_{b}{\mathbf{X}}_{\mu}}{\sqrt{d}}\Big{)}\Big{)}\,g(({\boldsymbol{\theta}}_{b})_{b\leq
k})\,,$ (9)

that, with a slight abuse of notation, will still be denoted by
$\langle\cdot\rangle$. From the above definition we see that the replicated
Boltzmann-Gibbs measure is factorized for a given realization of the dataset,
interpreted as quenched randomness in the analogy with spin glasses [26].
Hence, _replicas_ , namely i.i.d. samples from the posterior measure, are
independent conditionally on $\mathcal{D}_{n}$. However, when computing so-
called quenched averages $\mathbb{E}\langle\cdot\rangle$ a further expectation
$\mathbb{E}$ is taken w.r.t. the quenched data which couples the replicas.

One of the main object of interest is the _free entropy_ (i.e., log-partition
function) per sample, which is nothing else than minus the Shannon entropy
$H(\mathcal{D}_{n})$ of the data distribution per sample:

$\displaystyle\bar{f}_{n}:=\frac{1}{n}\mathbb{E}\log\mathcal{Z}(\mathcal{D}_{n})=-\frac{1}{n}H(\mathcal{D}_{n})\,,$
(10)

where the expectation $\mathbb{E}$ is w.r.t. to the training data
$\mathcal{D}_{n}=\\{({\mathbf{X}}_{\mu},Y_{\mu})\\}_{\mu=1}^{n}$. The
normalization by $n$ is natural given that the number of terms in the “energy”
defined by the exponent in (6) is precisely $n$. The data has a joint law that
can be written in terms of the output kernel

$\displaystyle dP(\mathcal{D}_{n})$
$\displaystyle=\prod_{\mu=1}^{n}\Big{(}\prod_{j=1}^{d}\frac{dX_{\mu
j}}{\sqrt{2\pi}}e^{-\frac{X_{\mu
j}^{2}}{2}}\Big{)}dY_{\mu}\,\mathbb{E}_{{\mathbf{a}}^{*},{\mathbf{W}}^{*}}\prod_{\mu=1}^{n}P_{\rm
out}(Y_{\mu}\mid S_{\mu})$
$\displaystyle=:\prod_{\mu=1}^{n}D{\mathbf{X}}_{\mu}dY_{\mu}\,\mathbb{E}_{{\mathbf{a}}^{*},{\mathbf{W}}^{*}}\exp\Big{(}\sum_{\mu=1}^{n}u_{Y_{\mu}}(S_{\mu})\Big{)}\,.$
(11)

Two observations are in order. First, the samples, indexed by $\mu$, are not
independent because the responses were all drawn from the teacher, even though
the ${\mathbf{X}}_{\mu}$’s are independently generated. Second, except for the
presence of differentials on the quenched variables this expression is very
similar to the partition function (6). This is due to the Bayes-optimality of
the student network and has some pragmatic consequences, such as the Nishimori
identities which will be key for the proof, see Appendix A.

Finally, note that for the sake of simplicity we did not include trainable
biases in the definition of our NN model. However, we believe that adding them
would not change much to our analysis as long as, like the other trainable
parameters, they are Gaussian distributed and the student network is again
Bayes-optimal and uses same architecture and number of parameters as the
teacher model.

###  2.2 An information-theoretically equivalent generalized linear model

We now introduce an another model known as generalized linear model (GLM) [6,
7, 8], which can be represented as a one layer neural network and which is
thus a generalization of the classical perceptron [4, 5]. One particular
instance of the GLM turns out to be deeply connected to the setting with
shallow networks introduced in the previous section. In this model the
responses are generated independently conditionally on the inputs as

$\displaystyle
Y_{\mu}^{\circ}=f\Big{(}\rho\frac{{\mathbf{v}}^{*\intercal}{\mathbf{X}}_{\mu}}{\sqrt{d}}+\sqrt{\epsilon}\xi_{\mu}^{*}\,;\,{\mathbf{A}}_{\mu}\Big{)}+\sqrt{\Delta}Z_{\mu}\,,\quad\text{or}\quad
Y_{\mu}^{\circ}\sim P_{\rm
out}\Big{(}\cdot\mid\rho\frac{{\mathbf{v}}^{*\intercal}{\mathbf{X}}_{\mu}}{\sqrt{d}}+\sqrt{\epsilon}\xi_{\mu}^{*}\Big{)}$
(12)

where ${\mathbf{v}}^{*}=(v_{j}^{*})_{j\leq d}\in\mathbb{R}^{d}$,
$v_{j}^{*}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
iid}}}}{{\sim}}}\mathcal{N}(0,1)$,
$\xi_{\mu}^{*}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
iid}}}}{{\sim}}}\mathcal{N}(0,1)$ all independently and the rest is as before.
With respect to the two-layer neural network, the non-linearity brought by the
middle layer has been replaced by a linear model with an additional effective
Gaussian noise $\xi^{*}_{\mu}$. $\rho$ and $\epsilon\geq 0$ are two real
parameters that will be specified later. This connection between the Bayes-
optimal learning of neural networks and this GLM was recently conjectured in
[27] based on the replica method and the application of Gaussian equivalences.
Our results vindicate their conjecture but for different scaling regimes
relating the diverging parameters $d,p,n$. We are going to further comment on
this point later on.

All the above construction can be repeated for the generalized linear model.
From now on, quantities characterized by a ∘ superscript will refer to the
GLM. For starters, we denote the dataset generated through (12) by
$\mathcal{D}_{n}^{\circ}:=\\{({\mathbf{X}}_{\mu},Y_{\mu}^{\circ})\\}_{\mu=1}^{n}$.
Let

$s_{\mu}^{\circ}=\rho\frac{{\mathbf{v}}^{\intercal}{\mathbf{X}}_{\mu}}{\sqrt{d}}+\sqrt{\epsilon}\xi_{\mu}\,,\qquad
S_{\mu}^{\circ}=\rho\frac{{\mathbf{v}}^{*\intercal}{\mathbf{X}}_{\mu}}{\sqrt{d}}+\sqrt{\epsilon}\xi_{\mu}^{*}$

and $D{\boldsymbol{\xi}}=\prod_{\mu}D\xi_{\mu}$. The expectation under the GLM
posterior of any bounded test function $g$ of $k$ “replicas” (i.e.,
conditionally on the data i.i.d. copies)
$({\mathbf{v}}_{b},{\boldsymbol{\xi}}_{b})_{b\leq k}$ reads

$\displaystyle\langle g\rangle^{\circ\,\otimes
k}:=\frac{1}{\mathcal{Z}^{\circ}(\mathcal{D}_{n}^{\circ})^{k}}\int\prod_{b=1}^{k}D{\mathbf{v}}_{b}D{\boldsymbol{\xi}}_{b}\prod_{\mu=1}^{n}P_{\rm
out}\Big{(}Y_{\mu}^{\circ}\mid\rho\frac{{\mathbf{v}}^{\intercal}_{b}{\mathbf{X}}_{\mu}}{\sqrt{d}}+\sqrt{\epsilon}\xi_{b\mu}\Big{)}\,g(({\mathbf{v}}_{b},{\boldsymbol{\xi}}_{b})_{b\leq
k})\,,$ (13)

with $\mathcal{Z}^{\circ}(\mathcal{D}_{n}^{\circ})$ the GLM posterior
normalization. As before, the free entropy reads

$\displaystyle\bar{f}_{n}^{\circ}:=\frac{1}{n}\mathbb{E}\log\mathcal{Z}^{\circ}(\mathcal{D}_{n}^{\circ})=\frac{1}{n}\mathbb{E}\log\int
D{\mathbf{v}}D{\boldsymbol{\xi}}\exp\Big{(}\sum_{\mu=1}^{n}u_{Y_{\mu}^{\circ}}(s_{\mu}^{\circ})\Big{)}\,.$
(14)

Finally, we write the distribution of the dataset, that is used for the
quenched average in the above formula:

$\displaystyle dP(\mathcal{D}_{n}^{\circ})$
$\displaystyle=\prod_{\mu=1}^{n}\Big{(}\prod_{j=1}^{d}\frac{dX_{\mu
j}}{\sqrt{2\pi}}e^{-\frac{X_{\mu
j}^{2}}{2}}\Big{)}dY_{\mu}^{\circ}\,\mathbb{E}_{{\mathbf{v}}^{*},{\boldsymbol{\xi}}^{*}}\prod_{\mu=1}^{n}P_{\rm
out}(Y_{\mu}^{\circ}\mid S^{\circ}_{\mu})$
$\displaystyle=:\prod_{\mu=1}^{n}D{\mathbf{X}}_{\mu}dY_{\mu}\,\mathbb{E}_{{\mathbf{v}}^{*},{\boldsymbol{\xi}}^{*}}\exp\Big{(}\sum_{\mu=1}^{n}u_{Y^{\circ}_{\mu}}(S^{\circ}_{\mu})\Big{)}$
(15)

and the optimal Bayesian predictor is

$\displaystyle\hat{Y}^{\circ}_{\rm Bayes}({\mathbf{X}}_{\rm
new}):=\mathbb{E}[Y^{\circ}_{\rm
new}\mid\mathcal{D}^{\circ}_{n},{\mathbf{X}}_{\rm new}]=\int dY\,Y\,P_{\rm
out}\Big{(}Y\mid\rho\frac{{\mathbf{v}}^{\intercal}{\mathbf{X}}_{\rm
new}}{\sqrt{d}}+\sqrt{\epsilon}\xi_{\mu}\Big{)}dP({\mathbf{v}},{\boldsymbol{\xi}}\mid\mathcal{D}^{\circ}_{n})\,.$
(16)

###  2.3 Results

Our first theorem concerns the equivalence between the Bayes-optimal learning
of the neural network and GLM models at the level of free entropy. Letting
$Z\sim\mathcal{N}(0,1)$ we denote
$\mathbb{E}_{\mathcal{N}(0,1)}g:=\mathbb{E}g(Z)$.

######  Theorem 1 (Free entropy equivalence).

Let

$\displaystyle\rho:=\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{\prime}\quad\text{and}\quad\epsilon^{2}:=\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}-\rho^{2}\,,$
(17)

and suppose Bayesian-optimal learning of a shallow network in the teacher-
student set-up and Bayesian-optimal learning of a shallow network in the
teacher-student set-up hold. Then

$\displaystyle|\bar{f}_{n}-\bar{f}^{\circ}_{n}|=O\Big{(}\sqrt{\Big{(}1+\frac{n}{d}\Big{)}\Big{(}\frac{n}{p}+\frac{n}{d^{3/2}}+\frac{1}{\sqrt{d}}\Big{)}}\Big{)}\,.$
(18)

From the previous statement we can identify the scaling regime for which the
equivalence holds, namely, when the right hand side of (18) goes to $0$. From
now on we shall denote by

$\widetilde{\lim}\,g_{d,p,n}:=\lim_{i\to\infty}\,g_{d_{i},p_{i},n_{i}}$

where $(d_{i},p_{i},n_{i})_{i}$ is any sequence of triplets of integers such
that

$\displaystyle\lim_{i\to\infty}\Big{(}1+\frac{n_{i}}{d_{i}}\Big{)}\Big{(}\frac{n_{i}}{p_{i}}+\frac{n_{i}}{d_{i}^{3/2}}+\frac{1}{\sqrt{d}_{i}}\Big{)}=0\,.$
(19)

As a corollary we have the matching of the mutual informations between the
dataset $\mathcal{D}_{n}$ and the network weights in the same limit. For the
two-layer neural network the mutual information is related to the free entropy
through the following expression ($H$ is the Shannon entropy)

$\displaystyle\frac{1}{n}I_{n}({\boldsymbol{\theta}}^{*};\mathcal{D}_{n})=\frac{1}{n}H(\mathcal{D}_{n})-\frac{1}{n}H(\mathcal{D}_{n}\mid{\boldsymbol{\theta}}^{*})=-\bar{f}_{n}+\mathbb{E}\log
P_{\rm
out}\Big{(}Y_{1}\mid\frac{{\mathbf{a}}^{*\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{{\mathbf{W}}^{*}{\mathbf{X}}_{1}}{\sqrt{d}}\Big{)}\Big{)}\,,$
(20)

whereas for the equivalent GLM we have

$\displaystyle\begin{split}\frac{1}{n}I_{n}^{\circ}({\boldsymbol{\theta}}^{\circ*};\mathcal{D}_{n}^{\circ})&=-\bar{f}^{\circ}_{n}+\mathbb{E}\log
P_{\rm
out}\Big{(}Y_{1}\mid\rho\frac{{\mathbf{v}}^{*\intercal}{\mathbf{X}}_{1}}{\sqrt{d}}+\sqrt{\epsilon}\xi_{1}^{*}\Big{)}\,.\end{split}$
(21)

Considering that the teacher weights and inputs are Gaussian we have in law

$\displaystyle\frac{{\mathbf{a}}^{*\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{{\mathbf{W}}^{*}{\mathbf{X}}_{1}}{\sqrt{d}}\Big{)}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
D}}}}{{=}}}Z\sqrt{\frac{1}{p}\Big{\|}\varphi\Big{(}\frac{{\mathbf{W}}^{*}{\mathbf{X}}_{1}}{\sqrt{d}}\Big{)}\Big{\|}^{2}}$
(22)

with $Z\sim\mathcal{N}(0,1)$ and $\|\cdot\|$ is the standard $L^{2}$ norm for
vectors. Therefore, it is clear that the randomness in ${\mathbf{W}}^{*}$ and
${\mathbf{X}}_{1}$ will disappear in the limit. A similar equality holds for
the GLM:

$\displaystyle\rho\frac{{\mathbf{v}}^{*\intercal}{\mathbf{X}}_{1}}{\sqrt{d}}+\sqrt{\epsilon}\xi_{1}^{*}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
D}}}}{{=}}}Z\sqrt{\rho^{2}\frac{\|{\mathbf{X}}_{1}\|^{2}}{d}+\epsilon}\,.$
(23)

Our goal is now to show that the arguments under square root both tend to
$\rho^{2}+\epsilon=\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}$ in the limit, and
that we can plug this result inside the last terms in (20) and (21), with a
control on the error we make. To this end, define

$\displaystyle
S_{d}(t)=\sqrt{t\rho^{2}\Big{(}\frac{\|{\mathbf{X}}_{1}\|^{2}}{d}-1\Big{)}+\epsilon+\rho^{2}}\,,\quad\text{or}\quad
S_{d}(t)=\sqrt{t\Big{(}\frac{1}{p}\Big{\|}\varphi\Big{(}\frac{{\mathbf{W}}^{*}{\mathbf{X}}_{1}}{\sqrt{d}}\Big{)}\Big{\|}^{2}-\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}\Big{)}+\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}}$
(24)

and

$\displaystyle\Psi(t):=\mathbb{E}\int dYP_{\rm out}(Y\mid ZS_{d}(t))\log
P_{\rm out}(Y\mid ZS_{d}(t))\,.$ (25)

Using the properties later described in Lemma 4 and the definition of $P_{\rm
out}$ in (2), under assumptions (Bayesian-optimal learning of a shallow
network in the teacher-student set-up-(Bayesian-optimal learning of a shallow
network in the teacher-student set-up one can readily verify that

$\displaystyle|\dot{\Psi}(t)|\leq C(f)\mathbb{E}|Z||\dot{S}_{d}(t)|\,,$ (26)

where $C(f)$ is a constant depending on $f$. From this bound, by the
fundamental theorem of integral calculus, we have

$\displaystyle|\Psi(1)-\Psi(0)|\leq
C(f)\int_{0}^{1}dt\,\mathbb{E}|\dot{S}_{d}(t)|\leq
C(f)\begin{cases}\frac{\mathbb{E}|\|\varphi({\mathbf{W}}^{*}{\mathbf{X}}_{1}/{\sqrt{d}})\|^{2}/p-\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}|}{\sqrt{\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}}}\quad&\text{for
the 2-layer NN}\\\
\rho^{2}\frac{\mathbb{E}|\|{\mathbf{X}}_{1}\|^{2}/d-1|}{\sqrt{\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}}}\quad&\text{for
the GLM}\end{cases}\,.$ (27)

The remainder for the two-layer NN is $O(p^{-1/2}+d^{-1/4})$ whereas for the
GLM we have $O(d^{-1/2})$. Finally, thanks to the previous argument

$\displaystyle\frac{1}{n}I_{n}({\boldsymbol{\theta}}^{*};\mathcal{D}_{n})$
$\displaystyle=-\bar{f}_{n}+\Psi(\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2})+O(p^{-1/2}+d^{-1/4})\,,$
(28)
$\displaystyle\frac{1}{n}I_{n}^{\circ}({\boldsymbol{\theta}}^{\circ*};\mathcal{D}_{n}^{\circ})$
$\displaystyle=-\bar{f}_{n}^{\circ}+\Psi(\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2})+O(d^{-1/2})\,,$
(29)

where

$\displaystyle\Psi(\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}):=\Psi(0)=\mathbb{E}\int
dYP_{\rm out}(Y\mid Z\sqrt{\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}})\log
P_{\rm out}(Y\mid Z\sqrt{\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}})\,.$ (30)

Hence, we have just proved the information theoretical equivalence:

######  Corollary 2 (Mutual information equivalence).

Under the same hypothesis of Theorem 1 the following holds:

$\displaystyle\Big{|}\frac{1}{n}I_{n}({\boldsymbol{\theta}}^{*};\mathcal{D}_{n})-\frac{1}{n}I_{n}^{\circ}({\boldsymbol{\theta}}^{\circ*};\mathcal{D}_{n}^{\circ})\Big{|}=O\Big{(}\sqrt{\Big{(}1+\frac{n}{d}\Big{)}\Big{(}\frac{n}{p}+\frac{n}{d^{3/2}}+\frac{1}{\sqrt{d}}\Big{)}}\Big{)}\,.$
(31)

The performance of the neural network is quantified using the generalization
error on test data using the square loss. The Bayes-optimal generalization
error thus reads

$\displaystyle\mathcal{E}_{n}:=\mathbb{E}\big{(}Y_{\rm new}-\mathbb{E}[Y_{\rm
new}\mid\mathcal{D}_{n},{\mathbf{X}}_{\rm new}]\big{)}^{2}\,.$ (32)

The outer expectation is intended w.r.t. the training data set and the test
sample which is generated independently from the training data according to
the same teacher model. The GLM Bayes-optimal generalization error
$\mathcal{E}^{\circ}_{n}$ is defined similarly but considering the GLM
teacher-student setting described in the previous section.

As a consequence of the proof technique of Theorem 1 it is possible to show
the following equivalence at the level of the generalization error, proven in
Section 5.

######  Theorem 3 (Generalization error equivalence).

Under the same hypothesis of Theorem 1 the following holds:

$\displaystyle\widetilde{\lim}\,|\mathcal{E}_{n}-\mathcal{E}^{\circ}_{n}|=0\,,$
(33)

i.e., the shallow neural network and noisy GLM settings lead to the same
Bayes-optimal generalization error in any high-dimensional limit such that
(19) holds.

Our results combined with those of [8] for the GLM provide explicit rigorous
formulas for the mutual information and Bayes-optimal generalization error for
the Bayesian neural network studied in this paper.

A remark is in order. The previous theorem states that the Bayes-optimal
generalization error of a two-layer NN, which is trained on the dataset
$\mathcal{D}_{n}$ generated by a teacher two-layer NN with same architecture,
equals that of a noisy GLM trained on the dataset $\mathcal{D}_{n}^{\circ}$
generated by a matched teacher GLM. However, we cannot deduce from this that
the two-layer NN trained using the GLM teacher dataset
$\mathcal{D}_{n}^{\circ}$, or viceversa, achieves the Bayes-optimal
generalization error. It would be interesting to investigate this aspect in
the future.

###  2.4 Related works

Figure 1: *

(1)

Figure 2: *

(2)

Figure 3: *

(3)

Figure 4: *

(4)

Figure 5: *

(5)

Figure 6: *

(6)

Figure 7: Standard neural network architectures analyzed in the literature,
classified according to how scale their layers widths (large diverging layers
are depicted with many neurons, those which are much smaller or of fixed size
have one or two neurons), and whether the internal weights are trainable (red
edges) or completely fixed and not trained (blue edges). (1) represents a
_generalized linear model_ (also called _perceptron_), (2) corresponds to
committee machines, with large input size and small (finite) hidden layer; (3)
and (4) are examples of mean field regime, where the input size is small while
the hidden layer is large; in particular model (4) corresponds to the _random
feature model_ ; (5) and (6) represent the challenging linear-width regimes.
Our results cover, e.g., models belonging to the regimes (6), and (3) when
$p\gg d\gg n\gg 1$.

There exist by now a whole zoology of theoretical models for NNs studied in
the literature and it becomes increasingly challenging to cover them whole. We
provide here a partial classification of the main models divided according to
how scale their internal widths compared to the inputs dimension, and whether
the internal weights are trainable or not, see Figure 7. For each class we
provide a selection of relevant references without trying to be exhaustive.

#### Perceptrons and committee machines

The perceptron (and its generalization, i.e., the GLM) are linear classifiers
with a non-linear readout. Committee machines can be viewed as two-layer
neural networks with a narrow hidden layer and a single neuron output layer.
These models have been studied in teacher-student set-ups and with online
learning since the nineties [28, 31, 12, 11, 32, 33, 34, 35, 36, 8, 14, 29,
30, 17, 18]. Despite their rich phenomenology with a so-called specialization
phase transition where the model realizes the in-put-output rule is non-
linear, these machines cannot capture the features of realistic data: they
project high-dimensional data in a comparatively too low-dimensional space.
The relevant regime for these models is $n,d\to\infty$ with
$n/d\to\alpha\in(0,\infty)$ and $p=O(1)$. Despite the fact that all the
weights among layers have to be learnt, w.r.t. our setting, the middle layer
remains finite while the input dimension and number of data points diverge
together. Note that, at first sight, it might be surprising that our result
does not imply equivalence when $p$ is finite. However, for any $p>1$ such
equivalences are not expected because a committee machine with two or more
hidden units is not, in general, a linear classifier and can represent more
complex non-linear relations. On the contrary, GEP-type of results are
expected to provide reductions towards (generalized) linear models.

#### Mean-field regime

In the series of works [37, 42, 43, 44, 45, 46, 47, 48, 49, 38, 39, 40, 41]
the authors study the stochastic gradient descent (SGD) dynamics of multilayer
neural networks. In contrast with the committee machine, here also the hidden
layer can diverge in size (see [47]). This projection of a relatively low-
dimensional signal into a very high-dimensional space has a regularizing
property on the risk landscape. In particular, it causes the merging of
possible multiple minima of the finite $p$ risk. SGD is then able to reach a
near optimum with controllable guarantees.

However, mean-field analyses of SGD dynamics differ from the information-
theoretical one. Indeed, SGD produces a “one-shot estimator”, which is in
general outperformed by the Bayes-optimal one. Also, online learning is
generally considered while our analysis consider (optimal) learning from a
large fixed data set. Furthermore, for the information-theoretical equivalence
in Theorem (1) to be valid, we need to control the size of the training set
w.r.t. the network size, and in principle we can send both $d,p\to\infty$ with
$d/p$ finite, as long as the training set is not too big ($n\ll p$).

#### Frozen hidden weights: neural tangent kernel, random features and lazy
training

Neural tangent kernel (NTK) [50] is a linearization of, say, a two-layer
neural network, which reduces its training to a linear regression on the
readout weights. As specified in [47], NTK describes well the neural network
performance at the initial stage of learning using SGD when the network
weights are virtually frozen around their initialization. In a similar
fashion, in random feature models and lazy training regimes [51, 61, 62, 63,
64, 65, 66, 67, 68, 52, 53, 16, 54, 55, 56, 57, 58, 59, 60] the internal
weights of the network are quenched, i.e., fixed once and for all. Other
results [69, 70, 71, 72, 73, 74] show that large-width NNs with purely random
weights behave as gaussian processes. Finally, recent works based on random
matrix theory consider linear-width NNs but again under the assumption that
only the last layer is learned, while internal ones are random [75, 76, 77,
78, 79, 80].

Even though some of the above results, and more recently [19], extend to
extensive width input and hidden layers, as well as extensive number of data,
i.e. $d,p,n\to\infty$ with $d,p,n$ all proportional, they hold in a setting
that is fundamentally different from ours. In fact, we address the learning of
_all_ the parameters in the network, considering all of them as _annealed_
variables, from a statistical mechanics perspective. Moreover, it is worth
stressing again that we study the Bayes-optimal generalization error, and not
the one coming from ERM. In this regard, it was shown in [81] that ERM with
hinge or logistic losses can reach generalization errors that are close to
Bayes-optimal in GLMs. In addition, as long as a suitable (though not convex)
loss is taken into account, ERM can yield Bayes-optimal performances. However,
this holds for GLMs, which have no hidden layer and thus only $p$ parameters
to be learnt.

#### Linear-width regimes

A line of recent works [10, 25, 27] deals with the full training of the
network as we do here. [10] in particular carries out a thorough study for
linear neural networks. In [27], instead, the authors conjecture the Bayes-
optimal limits in the extensive width and data regime $d,p,n\to\infty$ all
proportionally. Their computations are based on a combination of the heuristic
replica method from spin glasses and a Gaussian equivalence principle, that
allows to treat the non-linear activations in an efficient way. Despite GEPs
have been proved rigorously in other contexts (for instance [18, 19]), it is
not obvious that they are directly applicable to the extensive width and data
regime when the full training of the network is carried out. Indeed, it this
not clear to us whether our proof can be extended to the whole regime
considered in [27]; in particular, we cannot assess whether the equivalence
results provided in the next section do hold in the fully proportional regime
where $d=\Theta(n)$ and large (this is allowed by our bounds) _and_
$p=\Theta(n)$ (which is instead prevented by our bounds) as considered [27],
in spite that we cannot prove it at the moment.

Gaussian equivalence principles are also present in random matrix theory
literature [82, 83, 84, 75] and find applications in the study of random
features models.

#### Estimation in multi-layer generalized linear models

Finally, we emphasize the difference between the learning problem considered
in our work and the inference problem discussed in [85], later extended in
[86], where the authors consider the task of reconstructing a vector from
observations obtained from a multi-layer GLM with fixed, known, weight
matrices. We believe that the proof of the concentration of the free entropy
in [86], which was a bottleneck for GLM extensions to the multi-layer setting
initiated in [85], can be adapted to our learning problem, yielding the Bayes-
optimal generalization error GLM reduction for a deep network.

##  3 Proof of Theorem 1

###  3.1 The interpolating model

Our proof is based on the interpolation method, introduced in the seminal
papers [87, 88]. This method is a very effective tool whenever a comparison
between two high dimensional models is needed. The idea is that of introducing
an interpolating model, for any $t\in[0,1]$, that at its ends $t=0$ and $t=1$
matches the two models to be compared. In analogy with [8], we shall
interpolate at the level of the variables $s_{\mu}$, $S_{\mu}$:

$\displaystyle S_{t\mu}$
$\displaystyle:=\sqrt{1-t}\frac{\mathbf{a}^{*\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}}\Big{)}+\sqrt{t}\rho\frac{\mathbf{v}^{*\intercal}\mathbf{X}_{\mu}}{\sqrt{d}}+\sqrt{t\epsilon}\xi_{\mu}^{*}\,,$
(34) $\displaystyle s_{t\mu}$
$\displaystyle:=\sqrt{1-t}\frac{\mathbf{a}^{\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{\mathbf{W}\mathbf{X}_{\mu}}{\sqrt{d}}\Big{)}+\sqrt{t}\rho\frac{\mathbf{v}^{\intercal}\mathbf{X}_{\mu}}{\sqrt{d}}+\sqrt{t\epsilon}\xi_{\mu}\,.$
(35)

We thus introduce an interpolating teacher and interpolating student, such
that the second is Bayes-optimal for any $t\in[0,1]$. This allows us to use
the so-called Nishimori identities of Appendix A uniformly in $t$.

The interpolating teacher network shall produce the $\mu=1,\ldots,n$
conditionally indpendent responses

$\displaystyle Y_{t\mu}\sim P_{\rm out}(\cdot\mid S_{t\mu})\,,$ (36)

where the output kernel is unchanged since it depends only on $f$. Posterior
means now read

$\displaystyle\langle g\rangle_{t}:=\dfrac{1}{\mathcal{Z}_{t}}\int
D\mathbf{a}D\mathbf{W}D\mathbf{v}D{\boldsymbol{\xi}}\exp\Big{[}\sum_{\mu=1}^{n}u_{Y_{t\mu}}(s_{t\mu})\Big{]}g$
(37)

for any observable $g$ depending on
${\mathbf{a}},{\mathbf{W}},{\mathbf{v}},{\boldsymbol{\xi}}$, where

$\displaystyle\mathcal{Z}_{t}=\int
D\mathbf{a}D\mathbf{W}D\mathbf{v}D{\boldsymbol{\xi}}\exp\Big{[}\sum_{\mu=1}^{n}u_{Y_{\mu}}(s_{t\mu})\Big{]}\,.$
(38)

In the following we drop the subscript $t$ to keep the notation light and
simply use $\langle\cdot\rangle$. We also introduce the compact notation

$\displaystyle\mathbb{E}_{(t)}(\cdot):=\mathbb{E}_{{\mathbf{a}}^{*}}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}(\cdot)=\mathbb{E}_{{\mathbf{a}}^{*}}\mathbb{E}_{\mathbf{W}^{*},\mathbf{v}^{*},{\boldsymbol{\xi}}^{*},\\{\mathbf{X}_{\mu}\\}}\int\prod_{\mu=1}^{n}dY_{t\mu}e^{u_{Y_{t\mu}}(S_{t\mu})}(\cdot)\,.$
(39)

The free entropy of this interpolating model is thus

$\displaystyle\bar{f}_{n}(t):=\frac{1}{n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\,,$
(40)

whence it can be verified that

$\displaystyle\bar{f}_{n}(0)=\bar{f}_{n}\,,\quad\bar{f}_{n}(1)=\bar{f}_{n}^{\circ}\,.$
(41)

Due to the identity
$\bar{f}_{n}(1)-\bar{f}_{n}(0)=\int_{0}^{1}\frac{d}{dt}{\bar{f}}_{n}(t)dt$, a
sufficient condition to prove our Theorem 1 is to show that
$\frac{d}{dt}{\bar{f}}_{n}(t)$ is uniformly bounded by the same order as in
the statement. A direct computation shows

$\displaystyle\begin{split}\frac{d}{dt}{\bar{f}}_{n}(t)=-A_{1}+A_{2}+A_{3}+B\end{split}$
(42)

where

$\displaystyle
A_{1}:=\frac{1}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}u^{\prime}_{Y_{t\mu}}(S_{t\mu})\frac{\mathbf{a}^{*\intercal}}{\sqrt{(1-t)p}}\varphi\Big{(}\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}}\Big{)}\,,$
(43) $\displaystyle
A_{2}:=\frac{1}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}u^{\prime}_{Y_{t\mu}}(S_{t\mu})\rho\frac{\mathbf{v}^{*\intercal}\mathbf{X}_{\mu}}{\sqrt{td}}\,,$
(44) $\displaystyle
A_{3}:=\frac{1}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}u^{\prime}_{Y_{t\mu}}(S_{t\mu})\sqrt{\frac{\epsilon}{t}}\xi_{\mu}^{*}\,,$
(45) $\displaystyle
B:=\frac{1}{n}\mathbb{E}_{(t)}\Big{\langle}\sum_{\mu=1}^{n}u^{\prime}_{Y_{t\mu}}(s_{t\mu})\frac{ds_{t\mu}}{dt}\Big{\rangle}\,.$
(46)

We will control each term individually. For that we will need a number of
Lemmas wich we provide now.

###  3.2 Lemmata

We collect here some Lemmas that shall be used intensively in the following.
For the convenience we postpone proofs to the Appendix.

######  Lemma 4 (Properties of $P_{\rm out}$).

Recall the definition $u_{y}(x):=\log P_{\rm out}(y\mid x)$. We denote
$u^{\prime}_{y}(x):=\partial_{x}u_{y}(x)$. Furthermore, let

$\displaystyle
U_{\mu\nu}:=\delta_{\mu\nu}u^{\prime\prime}_{Y_{t\mu}}(S_{t\mu})+u^{\prime}_{Y_{t\mu}}(S_{t\mu})u^{\prime}_{Y_{t\nu}}(S_{t\nu})\,.$
(47)

Under Assumptions (Bayesian-optimal learning of a shallow network in the
teacher-student set-up and (Bayesian-optimal learning of a shallow network in
the teacher-student set-up the following statements hold:

$\displaystyle\mathbb{E}[u^{\prime}_{Y_{t\mu}}(S_{t\mu})\mid
S_{t\mu}]=\mathbb{E}[U_{\mu\nu}\mid S_{t\mu},S_{t\nu}]=0\,,$ (48)
$\displaystyle\mathbb{E}[(u^{\prime}_{Y_{t\mu}}(S_{t\mu}))^{2}\mid
S_{t\mu}]\,,\,\mathbb{E}[U_{\mu\nu}^{2}\mid S_{t\mu},S_{t\nu}]\leq C(f)\,,$
(49)

for a positive constant $C(f)$ depending solely on the readout function.

######  Remark 1.

It is worth to point out a simple observation that for $\mu=\nu$ we have
$U_{\mu\mu}=P^{\prime\prime}_{\rm out}(Y_{t\mu}\mid S_{t\mu})/P_{\rm
out}(Y_{t\mu})$, where

$P^{\prime}_{\rm out}(y\mid x):=\partial_{x}P_{\rm out}(y\mid x)\,,\qquad
P^{\prime\prime}_{\rm out}(y\mid x):=\partial_{x}\partial_{x}P_{\rm out}(y\mid
x)\,,$

from what immediately follows

$\displaystyle\mathbb{E}\Big{[}\Big{(}\frac{P^{\prime\prime}_{\rm
out}(Y_{t\mu}\mid S_{t\mu})}{P_{\rm out}(Y_{t\mu}\mid
S_{t\mu})}\Big{)}^{2}\mid S_{t\mu}\Big{]}\leq C(f)\,.$ (50)

The following lemma will play a crucial role, and it contains all the
approximations due to the law of large numbers. We introduce here a convenient
notation for the pre-activations:

$\displaystyle\boldsymbol{\alpha}_{\mu}:=\frac{{\mathbf{W}}^{*}{\mathbf{X}}_{\mu}}{\sqrt{d}}\,.$
(51)

Hence, conditionally on the inputs $({\mathbf{X}}_{\mu})_{\mu\leq n}$, the
$\boldsymbol{\alpha}$’s have covariance

$\displaystyle\frac{1}{p}\mathbb{E}[\boldsymbol{\alpha}_{\mu}^{\intercal}\boldsymbol{\alpha}_{\nu}\mid{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}]:=\frac{1}{p}\mathbb{E}_{{\mathbf{W}}^{*}}\frac{({\mathbf{W}}^{*}{\mathbf{X}}_{\mu})^{\intercal}}{\sqrt{d}}\frac{{\mathbf{W}}^{*}{\mathbf{X}}_{\nu}}{\sqrt{d}}=\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\,.$
(52)

######  Lemma 5 (Approximations).

Let $\tilde{\varphi}$ be either $\varphi$ or the identity function. Under
assumptions (Bayesian-optimal learning of a shallow network in the teacher-
student set-up and (Bayesian-optimal learning of a shallow network in the
teacher-student set-up the following estimates hold for any choice of
$\mu,\nu\leq n$:

$\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu
i})=\rho+O\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}\,,$ (53)
$\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu
i})=\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}+O\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}\,,$
(54) $\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi(\alpha_{\mu
i})\tilde{\varphi}(\alpha_{\nu
i})=\rho\mathbb{E}_{\mathcal{N}(0,1)}\tilde{\varphi}^{\prime}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}\Big{)}+O\Big{(}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}^{2}\Big{)}+O\Big{(}\frac{({\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu})^{2}}{\|{\mathbf{X}}_{\nu}\|^{2}d}\Big{)}\,,$
(55) $\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu
i})\varphi^{\prime}(\alpha_{\nu
i})=\rho^{2}+O\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}\,,$
(56) $\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu
i})\tilde{\varphi}^{2}(\alpha_{\nu
i})=\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}\mathbb{E}_{\mathcal{N}(0,1)}\tilde{\varphi}^{2}+O\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}\,.$
(57)

The final key ingredient is the concentration of the free entropy, that we
prove in Section 4.

######  Theorem 6 (Free entropy concentration).

Under assumptions (Bayesian-optimal learning of a shallow network in the
teacher-student set-up and (Bayesian-optimal learning of a shallow network in
the teacher-student set-up there exists a non-negative constant $C(f,\varphi)$
such that

$\displaystyle\mathbb{E}_{\mathbf{a}^{*}}\mathbb{V}_{\setminus{\mathbf{a}}^{*}}\Big{(}\dfrac{1}{n}\log\mathcal{Z}_{t}\Big{)}=\mathbb{E}\Big{(}\dfrac{1}{n}\log\mathcal{Z}_{t}-\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\dfrac{1}{n}\log\mathcal{Z}_{t}\Big{)}^{2}\leq
C(f,\varphi)\Big{(}\dfrac{1}{d}+\dfrac{1}{n}\Big{)}\,.$ (58)

###  3.3 Proof of Theorem 1

We split the proof of Theorem 1 into different Lemmas for the sake of
readability. If not differently specified, all the following Lemmas hold under
the same hypotheses of Theorem 1. The first one concerns the $B$ contribution
to the derivative of the free entropy (42).

######  Lemma 7 ($B$ term).

$B=0$.

###### Proof.

The random variable inside the brackets in (46) is a function of the data
$Y_{t\mu}$ and of a sample from the posterior through $s_{t\mu}$. Hence we can
use the Nishimori identities to get rid of the brackets, replacing $s_{t\mu}$
with the ground truth version $S_{t\mu}$ (from now on we denote with an upper
dot $\dot{S}:=\frac{dS}{dt}$ the $t$-derivative):

$\displaystyle
B=\frac{1}{n}\mathbb{E}_{(t)}\sum_{\mu=1}^{n}u^{\prime}_{Y_{t\mu}}(S_{t\mu})\dot{S}_{t\mu}=\frac{1}{n}\sum_{\mu=1}^{n}\mathbb{E}_{(t)}\Big{[}\mathbb{E}_{(t)}[u^{\prime}_{Y_{t\mu}}(S_{t\mu})\mid
S_{t\mu}]\dot{S}_{t\mu}\Big{]}$ (59)

where we used the tower rule for expectations. The latter is identically zero
thanks to Lemma 4. ∎

We split $A_{1}$ into two other contributions $A_{1}=A_{11}+A_{12}$ where

$\displaystyle
A_{11}:=\frac{1}{2n\sqrt{1-t}}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}u^{\prime}_{Y_{t\mu}}(S_{t\mu})\Big{(}\frac{\mathbf{a}^{*\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}}\Big{)}-\frac{{\rho}\mathbf{a}^{*\intercal}\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{pd}}\Big{)}\,,$
(60) $\displaystyle
A_{12}:=\frac{1}{2n\sqrt{1-t}}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}u^{\prime}_{Y_{t\mu}}(S_{t\mu})\frac{{\rho}\mathbf{a}^{*\intercal}\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{pd}}\,.$
(61)

Let us simplify these terms by Gaussian integration by parts. In $A_{12}$,
integrating by parts w.r.t. $\mathbf{W}^{*}$ yields

$\displaystyle A_{12}$
$\displaystyle=\frac{{\rho}}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu,\nu=1}^{n}U_{\mu\nu}\frac{\mathbf{a}^{*\intercal}\big{(}\mathbf{a}^{*}\circ\varphi^{\prime}\big{(}\frac{\mathbf{W}^{*}\mathbf{X}_{\nu}}{\sqrt{d}}\big{)}\big{)}}{p}\frac{\mathbf{X}_{\mu}^{\intercal}\mathbf{X}_{\nu}}{d}$
(62)

with $U_{\mu\nu}$ defined in Lemma 4 and $\circ$ denotes the entry-wise
(Hadamard) product. Concerning $A_{11}$, because of the non-linearity, we can
only integrate by parts w.r.t. $\mathbf{a}^{*}$ and obtain

$\displaystyle\begin{split}A_{11}&=\frac{1}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu,\nu=1}^{n}U_{\mu\nu}\Big{[}\frac{\varphi(\boldsymbol{\alpha}_{\mu})^{\intercal}\varphi(\boldsymbol{\alpha}_{\nu})-\rho\boldsymbol{\alpha}_{\mu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\nu})}{p}\Big{]}\,.\end{split}$
(63)

The off-diagonal $\mu\neq\nu$ and diagonal terms in the previous equations
play two very different roles, and they shall be treated separately in the
following.

######  Lemma 8 (Off-diagonal part of $A_{11}$).

The following holds:

$\begin{split}A_{11}^{\rm
off}:=\frac{1}{n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu\neq\nu}U_{\mu\nu}\Big{[}\frac{\varphi(\boldsymbol{\alpha}_{\mu})^{\intercal}\varphi(\boldsymbol{\alpha}_{\nu})-\rho\boldsymbol{\alpha}_{\mu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\nu})}{p}\Big{]}=O\Big{(}\sqrt{\Big{(}1+\frac{n}{d}\Big{)}\Big{(}\frac{n}{p}+\frac{n}{d^{3/2}}\Big{)}}\Big{)}\,.\end{split}$
(64)

###### Proof.

Let us start noticing that, for any smooth function
$F(\boldsymbol{\alpha}_{\mu},\boldsymbol{\alpha}_{\nu})$ we have

$\displaystyle\begin{split}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}U_{\mu\nu}F(\boldsymbol{\alpha}_{\mu},\boldsymbol{\alpha}_{\nu})=\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\big{[}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}[U_{\mu\nu}\mid\mathbf{W}^{*},{\mathbf{v}}^{*},\boldsymbol{\xi}^{*},\mathbf{X}]F(\boldsymbol{\alpha}_{\mu},\boldsymbol{\alpha}_{\nu})\big{]}=0\end{split}$
(65)

thanks to Lemma 4. As a consequence, with ${\mathbf{a}}^{*}$ fixed, we can
modify $A_{11}^{\rm off}$ as follows without changing its value:

$\displaystyle A_{11}^{\rm
off}=\mathbb{E}_{\setminus{\mathbf{a}}^{*}}(f_{n}-\mathbb{E}_{\setminus{\mathbf{a}}^{*}}f_{n})\sum_{\mu\neq\nu}U_{\mu\nu}\Big{[}\frac{\varphi(\boldsymbol{\alpha}_{\mu})^{\intercal}\varphi(\boldsymbol{\alpha}_{\nu})-{\rho}\boldsymbol{\alpha}_{\mu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\nu})}{p}\Big{]}$
(66)

with $f_{n}:=\log\mathcal{Z}_{t}/{n}$. In the following we shall simply write
$u^{\prime}_{\mu}$ in place of $u^{\prime}_{Y_{t\mu}}(S_{t\mu})$, and
$\boldsymbol{\varphi}_{\mu}$ instead of $\varphi(\boldsymbol{\alpha}_{\mu})$
for brevity. We are now in position to use Cauchy-Schwartz’s identity:

$\displaystyle(A_{11}^{\rm
off})^{2}\leq\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]\sum_{\mu\neq\nu}\sum_{\lambda\neq\eta}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}U_{\mu\nu}U_{\lambda\eta}\Big{[}\frac{\boldsymbol{\varphi}_{\mu}^{\intercal}\boldsymbol{\varphi}_{\nu}-{\rho}\boldsymbol{\alpha}_{\mu}^{\intercal}\boldsymbol{\varphi}_{\nu}}{p}\Big{]}\Big{[}\frac{\boldsymbol{\varphi}_{\lambda}^{\intercal}\boldsymbol{\varphi}_{\eta}-{\rho}\boldsymbol{\alpha}_{\lambda}^{\intercal}\boldsymbol{\varphi}_{\eta}}{p}\Big{]}\,.$
(67)

Note that when all the four Greek indices are different from one another we
get the highest combinatorial factor of $O(n^{4})$. However, using the
conditional independence of the responses and Lemma 4, the expectation sets
them to $0$. Hence, the only contributions from the double sums come from
$\mu=\lambda$ and $\nu=\eta$, or $\mu=\eta$ and $\nu=\lambda$, which gives
twice the same quantity. Thus

$\displaystyle(A_{11}^{\rm
off})^{2}\leq\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]\frac{2}{p^{2}}\sum_{\mu\neq\nu}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}(u^{\prime}_{\mu}u^{\prime}_{\nu})^{2}\sum_{i,j=1}^{p}\big{[}\varphi_{\mu
i}\varphi_{\nu i}\varphi_{\mu j}\varphi_{\nu j}-2{\rho}\alpha_{\mu
i}\varphi_{\nu i}\varphi_{\mu j}\varphi_{\nu j}+\rho^{2}\alpha_{\mu
i}\varphi_{\nu i}\alpha_{\mu j}\varphi_{\nu j}\big{]}\,.$ (68)

The double sum on $i,j$ comes from the square of a scalar product. Lemma 4
then allows to bound $\mathbb{E}[U_{\mu\nu}^{2}\mid S_{t\mu},S_{t\nu}]$ by a
constant.

Let us treat the off-diagonal terms ($i\neq j$) first. We call Lemma 5, in
particular (55), to simplify the first term in (68):

$\displaystyle\begin{split}&\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\sum_{i\neq
j,1}^{p}\varphi({\alpha}_{\mu i})\varphi({\alpha}_{\nu
i})\varphi({\alpha}_{\mu j})\varphi({\alpha}_{\nu
j})=p(p-1)\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}}\big{(}\mathbb{E}_{{\mathbf{W}}^{*}}[\varphi({\alpha}_{\mu
1})\varphi({\alpha}_{\nu 1})]\big{)}^{2}\\\
&=p(p-1)\mathbb{E}\Big{[}\rho^{4}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{)}^{2}+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}^{2}\Big{)}+O\Big{(}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{)}^{2}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}+O\Big{(}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{)}^{2}\Big{(}\frac{\|{\mathbf{X}}_{\nu}\|^{2}}{d}-1\Big{)}\Big{)}\Big{]}\,.\end{split}$
(69)

The first term in the square brackets corresponds to the square of the leading
term in (55) with $\tilde{\varphi}=\varphi$. The other two terms are obtained
as cross products between the leading term in (55) and the remainders.

Exploiting the fact that the norm of a Gaussian vector concentrates with
exponential speed, i.e.,

$\displaystyle\mathbb{P}\Big{(}\Big{|}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{|}\geq
h\Big{)}\leq\exp\Big{(}-\frac{dLh^{2}}{2}\Big{)}\,,\quad L>0\,,\forall h>0\,,$
(70)

one can conclude that

$\displaystyle\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\sum_{i\neq
j,1}^{p}\varphi({\alpha}_{\mu i})\varphi({\alpha}_{\nu
i})\varphi({\alpha}_{\mu j})\varphi({\alpha}_{\nu
j})=p(p-1)\Big{[}\frac{\rho^{4}}{d}+O\Big{(}\frac{1}{d^{3/2}}\Big{)}\Big{]}\,.$
(71)

We now turn to the second term of (68): using again a Gaussian integration by
part for the second equality below followed by Lemma 5 we get

$\displaystyle\begin{split}{\rho}\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}}\mathbb{E}_{{\mathbf{W}}^{*}}&\sum_{i\neq
j}^{p}\alpha_{\mu i}\varphi_{\nu i}\varphi_{\mu j}\varphi_{\nu
j}={\rho}p(p-1)\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}}\mathbb{E}_{{\mathbf{W}}^{*}}[\alpha_{\mu
1}\varphi_{\nu 1}]\mathbb{E}_{{\mathbf{W}}^{*}}[\varphi_{\mu 1}\varphi_{\nu
1}]\\\
&={\rho}p(p-1)\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\mathbb{E}_{{\mathbf{W}}^{*}}[\varphi^{\prime}_{\nu
1}]\mathbb{E}_{{\mathbf{W}}^{*}}[\varphi_{\mu 1}\varphi_{\nu 1}]\\\
&=p(p-1)\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}}\Big{[}\rho^{2}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}\Big{)}\Big{]}\\\
&\qquad\times\Big{[}\rho^{2}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}+O\Big{(}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}^{2}\Big{)}+O\Big{(}\frac{({\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu})^{2}}{\|{\mathbf{X}}_{\nu}\|^{2}d}\Big{)}+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}\Big{)}\Big{]}\end{split}$
(72)

which shows that

$\displaystyle\rho\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}}\mathbb{E}_{{\mathbf{W}}^{*}}$
$\displaystyle\sum_{i\neq j}^{p}\alpha_{\mu i}\varphi_{\nu i}\varphi_{\mu
j}\varphi_{\nu
j}=p(p-1)\Big{[}\frac{\rho^{4}}{d}+O\Big{(}\frac{1}{d^{3/2}}\Big{)}\Big{]}\,.$
(73)

Finally, for what concerns the off-diagonal terms $i\neq j$, we deal with the
last term of (68):

$\displaystyle\rho^{2}\sum_{i\neq
j}^{p}\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}}\alpha_{\mu
i}\varphi_{\nu i}\alpha_{\mu j}\varphi_{\nu j}$
$\displaystyle=\rho^{2}p(p-1)\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}}\mathbb{E}_{{\mathbf{W}}^{*}}[\alpha_{\mu
1}\varphi_{\nu 1}]\mathbb{E}_{{\mathbf{W}}^{*}}[\alpha_{\mu 1}\varphi_{\nu
1}]$
$\displaystyle=p(p-1)\rho^{2}\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{)}^{2}\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}_{\mu
1}\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}_{\nu 1}$
$\displaystyle=p(p-1)\Big{[}\frac{\rho^{4}}{d}+O\Big{(}\frac{1}{d^{3/2}}\Big{)}\Big{]}$
(74)

where we used integration by parts and the approximation Lemma 5. From this
computation we see that, remarkably, the leading orders of the off-diagonal
terms $i\neq j$ in (68) cancel each other, leaving the more convenient rate
$O(1/d^{3/2})$. More precisely, there exists an absolute constant $K$ such
that

$\displaystyle(A_{11}^{\rm
off})^{2}\leq\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]\frac{2K}{p^{2}}\sum_{\mu\neq\nu}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\Big{\\{}\sum_{i=1}^{p}\big{[}\varphi^{2}_{\mu
i}\varphi^{2}_{\nu i}-2{\rho}\alpha_{\mu i}\varphi^{2}_{\nu i}\varphi_{\mu
i}+\rho^{2}\alpha_{\mu i}^{2}\varphi_{\nu
i}^{2}\big{]}+O\Big{(}\frac{p^{2}}{d^{3/2}}\Big{)}\Big{\\}}\,.$ (75)

From the previous bound we see that we cannot hope that the same cancellation
occurs in the diagonal terms $i=j$. Using again the results from Lemma 5 one
can show that

$\displaystyle(A_{11}^{\rm
off})^{2}\leq\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]\frac{2K}{p^{2}}\sum_{\mu\neq\nu}\Big{[}O(p)+O\Big{(}\frac{p^{2}}{d^{3/2}}\Big{)}\Big{]}\,.$
(76)

The statement is thus proved after we take care of the remaining expectation
over ${\mathbf{a}}^{*}$ using Theorem 6:

$\displaystyle|\mathbb{E}_{{\mathbf{a}}^{*}}A_{11}^{\rm
off}|\leq\mathbb{E}_{{\mathbf{a}}^{*}}\sqrt{{(A_{11}^{\rm
off})^{2}}}\leq\sqrt{\mathbb{E}_{{\mathbf{a}}^{*}}\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]O\Big{(}\frac{n^{2}}{p}+\frac{n^{2}}{d^{3/2}}\Big{)}}=O\Big{(}\sqrt{\frac{n}{p}+\frac{n}{d^{3/2}}+\frac{n^{2}}{dp}+\frac{n^{2}}{d^{5/2}}}\Big{)}\,.$
(77)

∎

######  Remark 2.

The previous result is telling us that the number of data points $n$ can grow
as fast as $o(d^{3/2})$ with the size of the input layer, but has to be much
smaller than $p$, the size of the hidden layer. Furthermore, treating the
difference
$\varphi(\boldsymbol{\alpha}_{\mu})^{\intercal}\varphi(\boldsymbol{\alpha}_{\nu})-{\rho}\boldsymbol{\alpha}_{\mu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\nu})$
altogether is fundamental to obtain the scaling $n^{2}{d^{-3/2}}$ instead of
$n^{2}d^{-1}$. We also stress that the pre-activations
$\boldsymbol{\alpha}_{\mu}$ in the hidden layer have correlations among them
that scale as $d^{-1/2}$. If $d$ is not big enough they cannot be considered
weakly correlated.

From Lemma 8 we thus infer that

$\displaystyle A_{11}$
$\displaystyle=\frac{1}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}\frac{P_{\rm
out}^{\prime\prime}(Y_{t\mu}\mid S_{t\mu})}{P_{\rm out}(Y_{t\mu}\mid
S_{t\mu})}\Big{[}\frac{\|\varphi(\boldsymbol{\alpha}_{\mu})\|^{2}-{\rho}\boldsymbol{\alpha}_{\mu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\mu})}{p}\Big{]}+O\Big{(}\sqrt{\Big{(}1+\frac{n}{d}\Big{)}\Big{(}\frac{n}{p}+\frac{n}{d^{3/2}}\Big{)}}\Big{)}\,.$
(78)

For the term $A_{3}$ we use integration by parts with respect to the variables
Gaussian $\xi_{\mu}^{*}$:

$\displaystyle
A_{3}=\frac{\epsilon}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}\Big{(}(u^{\prime}_{Y_{t\mu}}(S_{t\mu}))^{2}+u^{\prime\prime}_{Y_{t\mu}}(S_{t\mu})\Big{)}=\frac{\epsilon}{2d}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}\dfrac{P^{\prime\prime}_{\rm
out}(Y_{t\mu}\mid S_{t\mu})}{P_{\rm out}(Y_{t\mu}\mid S_{t\mu})}\,.$ (79)

Hence

$A_{3}-A_{11}=\frac{1}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}\dfrac{P^{\prime\prime}_{\rm
out}(Y_{t\mu}\mid S_{t\mu})}{P_{\rm out}(Y_{t\mu}\mid
S_{t\mu})}\Big{[}\epsilon-\frac{\|\varphi(\boldsymbol{\alpha}_{\mu})\|^{2}-{\rho}\boldsymbol{\alpha}_{\mu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\mu})}{p}\Big{]}+O\Big{(}\sqrt{\Big{(}1+\frac{n}{d}\Big{)}\Big{(}\frac{n}{p}+\frac{n}{d^{3/2}}\Big{)}}\Big{)}\,.$
(80)

######  Lemma 9 ($A_{3}-A_{11}^{\rm diag}$ term).

The following asymptotics holds:

$\displaystyle A_{3}-A_{11}^{\rm
diag}:=\frac{1}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}\dfrac{P^{\prime\prime}_{\rm
out}(Y_{t\mu}\mid S_{t\mu})}{P_{\rm out}(Y_{t\mu}\mid
S_{t\mu})}\Big{[}\epsilon-\frac{\|\varphi(\boldsymbol{\alpha}_{\mu})\|^{2}-{\rho}\boldsymbol{\alpha}_{\mu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\mu})}{p}\Big{]}=O\Big{(}\sqrt{\Big{(}\frac{n}{d}+1\Big{)}\Big{(}\frac{1}{p}+\frac{1}{\sqrt{d}}\Big{)}}\Big{)}\,.$
(81)

###### Proof.

Define

$\displaystyle
C:=\frac{1}{n}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\log\mathcal{Z}_{t}\sum_{\mu=1}^{n}\frac{P^{\prime\prime}_{\rm
out}(Y_{t\mu}\mid S_{t\mu})}{P_{\rm out}(Y_{t\mu}\mid
S_{t\mu})}\Big{[}\epsilon-\frac{\|\varphi(\boldsymbol{\alpha}_{\mu})\|^{2}-\rho\boldsymbol{\alpha}_{\mu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\mu})}{p}\Big{]}\,.$
(82)

First, thanks to Lemma 4

$\displaystyle\begin{split}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\Big{[}\frac{P^{\prime\prime}_{\rm
out}(Y_{t\mu}\mid S_{t\mu})}{P_{\rm out}(Y_{t\mu}\mid
S_{t\mu})}\mid{\mathbf{W}}^{*},{\mathbf{v}}^{*},{\mathbf{X}}_{\mu},\xi^{*}_{\mu}\Big{]}=0\,,\end{split}$
(83)

and this allows us to center the $f_{n}=\log\mathcal{Z}_{t}/n$ with its mean
without changing the value of $C$. After using Cauchy-Schwartz we have

$\displaystyle\begin{split}C^{2}&\leq\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]\sum_{\mu,\nu=1}^{n}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\Big{[}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\Big{[}\frac{P^{\prime\prime}_{\rm
out}(Y_{t\mu}\mid S_{t\mu})}{P_{\rm out}(Y_{t\mu}\mid
S_{t\mu})}\frac{P^{\prime\prime}_{\rm out}(Y_{t\nu}\mid S_{t\nu})}{P_{\rm
out}(Y_{t\nu}\mid
S_{t\nu})}\mid{\mathbf{W}}^{*},{\mathbf{v}}^{*},{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu},\xi^{*}_{\mu},\xi^{*}_{\nu}\Big{]}\\\
&\qquad\times\Big{(}\epsilon-\frac{\|\varphi(\boldsymbol{\alpha}_{\mu})\|^{2}-\rho\boldsymbol{\alpha}_{\mu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\mu})}{p}\Big{)}\Big{(}\epsilon-\frac{\|\varphi(\boldsymbol{\alpha}_{\nu})\|^{2}-\rho\boldsymbol{\alpha}_{\nu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\nu})}{p}\Big{)}\Big{]}\,.\end{split}$
(84)

Thanks to the observation in (83), only the diagonal terms $\mu=\nu$ will
survive in the double sum on the r.h.s. of the previous inequality.
Furthermore recall (50). Hence the bound on $C^{2}$ becomes

$\displaystyle\begin{split}C^{2}&\leq\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]C(f)n\mathbb{E}_{{\mathbf{X}}_{1},{\mathbf{W}}^{*}}\Big{(}\epsilon-\frac{\|\varphi(\boldsymbol{\alpha}_{1})\|^{2}-\rho\boldsymbol{\alpha}_{1}^{\intercal}\varphi(\boldsymbol{\alpha}_{1})}{p}\Big{)}^{2}\,.\end{split}$
(85)

Following an integration by part and Lemma 5 we have

$\displaystyle\begin{split}\mathbb{E}_{{\mathbf{W}}^{*}}\alpha_{1i}\varphi(\alpha_{1i})&=\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{1i})\frac{\|{\mathbf{X}}_{1}\|^{2}}{d}=\frac{\|{\mathbf{X}}_{1}\|^{2}}{d}\Big{(}\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{\prime}+O\Big{(}\frac{\|{\mathbf{X}}_{1}\|^{2}}{d}-1\Big{)}\Big{)}\\\
&=\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{\prime}+O\Big{(}\frac{\|{\mathbf{X}}_{1}\|^{2}}{d}-1\Big{)}\,.\end{split}$
(86)

From this and the approximation Lemma it follows that (letting
$\mathbb{E}^{2}(\cdots)=(\mathbb{E}(\cdots))^{2}$)

$\displaystyle\mathbb{E}_{{\mathbf{X}}_{1}}\mathbb{E}_{{\mathbf{W}}*}\Big{[}\frac{\|\varphi(\boldsymbol{\alpha}_{1})\|^{2}-\rho\boldsymbol{\alpha}_{1}^{\intercal}\varphi(\boldsymbol{\alpha}_{1})}{p}\Big{]}$
$\displaystyle=\mathbb{E}_{\mathcal{{N}}(0,1)}\varphi^{2}-\mathbb{E}^{2}_{\mathcal{{N}}(0,1)}\varphi^{\prime}+O\Big{(}\mathbb{E}_{{\mathbf{X}}_{1}}\Big{|}\frac{\|{\mathbf{X}}_{1}\|^{2}}{d}-1\Big{|}\Big{)}$
$\displaystyle=\epsilon+O(d^{-1/2})\,,$ (87)
$\displaystyle\mathbb{E}_{{\mathbf{X}}_{1}}\mathbb{E}_{{\mathbf{W}}*}\Big{[}\frac{\|\varphi(\boldsymbol{\alpha}_{1})\|^{2}-\rho\boldsymbol{\alpha}_{1}^{\intercal}\varphi(\boldsymbol{\alpha}_{1})}{p}\Big{]}^{2}$
$\displaystyle=\frac{1}{p}\mathbb{E}_{{\mathbf{X}}_{1}}\mathbb{E}_{{\mathbf{W}}^{*}}\big{(}\varphi^{4}(\alpha_{11})-2\rho\varphi^{3}(\alpha_{11})\alpha_{11}+\rho^{2}\alpha_{11}^{2}\varphi^{2}(\alpha_{11})\big{)}$
$\displaystyle+\frac{p-1}{p}\mathbb{E}_{{\mathbf{X}}_{1}}\big{(}\mathbb{E}_{{\mathbf{W}}^{*}}^{2}\varphi^{2}(\alpha_{11})-2\rho\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{11})\mathbb{E}_{{\mathbf{W}}^{*}}\varphi(\alpha_{11})\alpha_{11}+\rho^{2}\mathbb{E}_{{\mathbf{W}}^{*}}^{2}\varphi(\alpha_{11})\alpha_{11}\big{)}$
$\displaystyle=\epsilon^{2}+O(p^{-1})+O(d^{-1/2})\,.$ (88)

Hence, we finally have

$\displaystyle\begin{split}\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{W}}^{*}}\Big{(}\epsilon-\frac{\|\varphi(\boldsymbol{\alpha}_{\mu})\|^{2}-\rho\boldsymbol{\alpha}_{\mu}^{\intercal}\varphi(\boldsymbol{\alpha}_{\mu})}{p}\Big{)}^{2}=O(p^{-1})+O(d^{-1/2})\,.\end{split}$
(89)

Plugging this and the bound in Theorem 6 into the inequality for $C^{2}$ we
readily get the statement. ∎

Now the remaining goal is to prove that $A_{2}-A_{12}\to 0$. Using integration
by parts in $A_{2}$ w.r.t. ${\mathbf{v}}^{*}$ we obtain

$\displaystyle\begin{split}A_{2}=\frac{\rho^{2}}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu,\nu=1}^{n}U_{\mu\nu}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\,.\end{split}$
(90)

Recall also formula (62) for $A_{12}$.

######  Lemma 10 ($A_{12}-A_{2}$ term).

The following asymptotics holds:

$\displaystyle
A_{12}-A_{2}=\frac{\rho}{2n}\mathbb{E}_{(t)}\log\mathcal{Z}_{t}\sum_{\mu,\nu=1}^{n}U_{\mu\nu}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{[}\frac{\mathbf{a}^{*\intercal}(\mathbf{a}^{*}\circ\varphi^{\prime}(\boldsymbol{\alpha}_{\nu}))}{p}-{\rho}\Big{]}=O\Big{(}\sqrt{\Big{(}1+\frac{n}{d}\Big{)}\Big{(}\frac{n}{dp}+\frac{n}{d^{3/2}}\Big{)}}\Big{)}\,.$
(91)

###### Proof.

Conditional on ${\mathbf{a}}^{*}$ define

$\displaystyle
C:=\frac{1}{n}\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\log\mathcal{Z}_{t}\sum_{\mu,\nu=1}^{n}U_{\mu\nu}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{[}\frac{\mathbf{a}^{*\intercal}(\mathbf{a}^{*}\circ\varphi^{\prime}(\boldsymbol{\alpha}_{\nu}))}{p}-{\rho}\Big{]}\,.$
(92)

As before, thanks to Lemma 4, we can center the random variable
$\log\mathcal{Z}_{t}$ with its expectation
$\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\log\mathcal{Z}_{t}$, without affecting
$C$. We can thus use Cauchy-Schwartz’s inequality, obtaining

$\displaystyle
C^{2}\leq\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\sum_{\mu,\nu=1}^{n}\sum_{\lambda,\eta=1}^{n}U_{\mu\nu}U_{\lambda\eta}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{[}\frac{\mathbf{a}^{*\intercal}(\mathbf{a}^{*}\circ\varphi^{\prime}(\boldsymbol{\alpha}_{\nu}))}{p}-{\rho}\Big{]}\frac{{\mathbf{X}}_{\lambda}^{\intercal}{\mathbf{X}}_{\eta}}{d}\Big{[}\frac{\mathbf{a}^{*\intercal}(\mathbf{a}^{*}\circ\varphi^{\prime}(\boldsymbol{\alpha}_{\eta}))}{p}-{\rho}\Big{]}$
(93)

for a given ${\mathbf{a}}^{*}$. Thanks again to Lemma 4 the only terms that
survive in the above quadruple sum are those with $\mu=\nu=\lambda=\eta$, and
$\mu\neq\nu$, $\lambda\neq\eta$ but with $\mu=\lambda$, $\nu=\eta$ or vice
versa. Up to constants everything can be summed up as follows:

$\displaystyle C^{2}\leq
K\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]\mathbb{E}_{\setminus{\mathbf{a}}^{*}}\sum_{\mu,\nu=1}^{n}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{)}^{2}\Big{[}\frac{\mathbf{a}^{*\intercal}(\mathbf{a}^{*}\circ\varphi^{\prime}(\boldsymbol{\alpha}_{\nu}))}{p}-{\rho}\Big{]}^{2}$
(94)

where we used again Lemma 4. Now, expanding the square and computing the
${\mathbf{W}}^{*}$ average of $\varphi^{\prime}$ via Lemma (5) we readily get

$\displaystyle C^{2}\leq
K^{\prime}\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]\sum_{\mu,\nu=1}^{n}\mathbb{E}_{{\mathbf{X}}_{\mu},{\mathbf{X}}_{\nu}}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{)}^{2}\Big{[}\Big{(}\frac{\|{\mathbf{a}}^{*}\|^{2}}{p}-1\Big{)}^{2}+O\Big{(}\frac{\|{\mathbf{X}}_{\nu}\|^{2}}{d}-1\Big{)}\Big{(}\frac{\|{\mathbf{a}}^{*}\|^{4}}{p^{2}}+\frac{\|{\mathbf{a}}^{*}\|^{2}}{p}\Big{)}\Big{]}$
(95)

where $K^{\prime}$ is a suitable positive constant. Denoting the double sum by
$D$ we have

$\displaystyle|A_{2}-A_{12}|\leq
K^{\prime\prime}\mathbb{E}_{{\mathbf{a}}^{*}}\sqrt{\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]}\sqrt{D}\leq
K^{\prime\prime}\sqrt{\mathbb{E}_{{\mathbf{a}}^{*}}\mathbb{V}_{\setminus{\mathbf{a}}^{*}}[f_{n}]\,\mathbb{E}_{{\mathbf{a}}^{*}}D}=O\Big{(}\sqrt{\Big{(}\frac{1}{n}+\frac{1}{d}\Big{)}\Big{(}\frac{n^{2}}{dp}+\frac{n^{2}}{d^{3/2}}\Big{)}}\Big{)}\,.$
(96)

∎

Putting the results of all the Lemmas in this section together we get that the
time derivative of the interpolating free entropy is bounded by

$\displaystyle\frac{d}{dt}{\bar{f}}_{n}(t)$
$\displaystyle=\underbrace{O\Big{(}\sqrt{\Big{(}1+\frac{n}{d}\Big{)}\Big{(}\frac{n}{p}+\frac{n}{d^{3/2}}\Big{)}}\Big{)}}_{A_{11}^{\rm
off}}+\underbrace{O\Big{(}\sqrt{\Big{(}1+\frac{n}{d}\Big{)}\Big{(}\frac{1}{p}+\frac{1}{\sqrt{d}}\Big{)}}\Big{)}}_{A_{3}-A_{11}^{\rm
diag}}+\underbrace{O\Big{(}\sqrt{\Big{(}1+\frac{n}{d}\Big{)}\Big{(}\frac{n}{dp}+\frac{n}{d^{3/2}}\Big{)}}\Big{)}}_{A_{12}-A_{2}}$
(97)
$\displaystyle=O\Big{(}\sqrt{\Big{(}1+\frac{n}{d}\Big{)}\Big{(}\frac{n}{p}+\frac{n}{d^{3/2}}+\frac{1}{\sqrt{d}}\Big{)}}\Big{)}\,.$
(98)

All the bounds in this section are uniform in $t\in[0,1]$. This finishes the
proof of Theorem 1.

##  4 Concentration of the free entropy

Here we prove that the free entropy of the interpolating model concentrates,
i.e., Theorem 6. To simplify the notations we use $C(f,\varphi)$ for a generic
non-negative constant depending only on $f$ and $\varphi$. We recall that the
partition function is defined as

$\displaystyle\mathcal{Z}_{t}=\int
D\mathbf{a}D\mathbf{v}D\mathbf{W}\prod_{\mu=1}^{n}D\boldsymbol{\xi}_{\mu}\exp\Big{[}\sum_{\mu=1}^{n}\log
P_{\rm out}(Y_{t\mu}|s_{t\mu})\Big{]}\,,$ (99)

where

$\displaystyle Y_{t\mu}$
$\displaystyle=f(S_{t\mu};{\mathbf{A}}_{\mu})+\sqrt{\Delta}Z_{\mu}\,,$ (100)
$\displaystyle S_{t\mu}$
$\displaystyle=\sqrt{1-t}\frac{\mathbf{a}^{*\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}}\Big{)}+\sqrt{t\rho}\frac{\mathbf{v}^{*\intercal}\mathbf{X}_{\mu}}{\sqrt{d}}+\sqrt{t\epsilon}\xi_{\mu}^{*}\,,$
(101) $\displaystyle s_{t\mu}$
$\displaystyle=\sqrt{1-t}\frac{\mathbf{a}^{\intercal}}{\sqrt{p}}\varphi\Big{(}\frac{\mathbf{W}\mathbf{X}_{\mu}}{\sqrt{d}}\Big{)}+\sqrt{t\rho}\frac{\mathbf{v}^{\intercal}\mathbf{X}_{\mu}}{\sqrt{d}}+\sqrt{t\epsilon}\xi_{\mu}\,.$
(102)

We prove Theorem 6 in several steps, first we show concentration with respect
only to $\\{Z_{\mu}\\}_{\mu}$, $\\{\xi^{*}_{\mu}\\}_{\mu}$ and
$\\{\mathbf{X}_{\mu}\\}_{\mu}$ using classical Poincare-Nash inequality, then
with respect to $\\{{\mathbf{A}}_{\mu}\\}_{\mu}$ using the corollary of Efron-
Stein inequality, and then finally with respect to $\mathbf{W}^{*}$ with
${\mathbf{v}}^{*}$. For this we rewrite

$\mathbb{E}\Big{(}\frac{1}{n}\log\mathcal{Z}_{t}-\mathbb{E}_{{\mathbf{v}}^{*},\mathbf{W}^{*},\mathbf{X},\boldsymbol{\xi}^{*},{\mathbf{A}},{\mathbf{Z}}}\frac{1}{n}\log\mathcal{Z}_{t}\Big{)}^{2}=\\\
=\mathbb{E}\Big{(}\frac{1}{n}\log\mathcal{Z}_{t}-\mathbb{E}_{\mathbf{X},\boldsymbol{\xi}^{*},{\mathbf{Z}}}\frac{1}{n}\log\mathcal{Z}_{t}\Big{)}^{2}+\mathbb{E}\Big{(}\frac{1}{n}\mathbb{E}_{\mathbf{X},\boldsymbol{\xi}^{*},{\mathbf{Z}}}\log\mathcal{Z}_{t}-\mathbb{E}_{{\mathbf{A}}}\mathbb{E}_{\mathbf{X},\boldsymbol{\xi}^{*},{\mathbf{Z}}}\frac{1}{n}\log\mathcal{Z}_{t}\Big{)}^{2}+\\\
+\mathbb{E}\Big{(}\mathbb{E}_{\psi}\frac{1}{n}\log\mathcal{Z}_{t}-\mathbb{E}_{\mathbf{v}^{*},\mathbf{W}^{*}}\mathbb{E}_{\psi}\frac{1}{n}\log\mathcal{Z}_{t}\Big{)}^{2}$
(103)

where by $\mathbb{E}_{\psi}$ we denoted the joint expectation with respect to
${\mathbf{Z}}$, $\boldsymbol{\xi}^{*}$, $\mathbf{X}$, and ${\mathbf{A}}$. Also
for brevity, in what follows, by writing ${\mathbf{Z}}$,
$\boldsymbol{\xi}^{*}$, $\mathbf{X}$, and ${\mathbf{A}}$ we mean the sets
$\\{Z_{\mu}\\}_{\mu}$, etc. We recall two classical concentration results,
whose proofs can be found in [89], Chapter 3.

######  Proposition 11 (Poincaré-Nash inequality).

Let $\xi=[\xi_{1},\ldots,\xi_{K}]^{\intercal}$ be a real Gaussian standard
random vector. If $g:\mathbb{R}^{K}\rightarrow\mathbb{R}$ is a continuously
differentiable function, then

$\displaystyle\mathbb{V}g(\xi)\leq\mathbb{E}\|\nabla g(\xi)\|^{2}\,.$ (104)

######  Proposition 12 (Bounded difference).

Let $\xi=[\xi_{1},\ldots,\xi_{K}]^{\intercal}$ be a random vector with i.i.d.
elements taking values in some space $\mathcal{A}$. If function
$g:\mathcal{A}^{K}\rightarrow\mathbb{R}$ satisfies

$\displaystyle\sup_{1\leq i\leq
K}\sup_{x_{1},\ldots,x_{K},x\prime_{i}\in\mathcal{A}}|g(x_{1},\ldots,x_{i},\ldots,x_{K})-g(x_{1},\ldots,x_{i}^{\prime},\ldots,x_{K})|\leq
C$ (105)

for some $C>0$, then

$\displaystyle\mathbb{V}\\{g(\xi)\\}\leq\dfrac{1}{4}KC^{2}.$ (106)

In what follows we will denote $P^{y}(y|x):=\frac{\partial P_{\rm
out}(y|x)}{\partial y}$ and $P^{x}(y|x):=\frac{\partial P_{\rm
out}(y|x)}{\partial x}$.

######  Lemma 13.

There exists a non-negative constant $C(f,\varphi$) such that

$\displaystyle\mathbb{E}\Big{(}\frac{1}{n}\log\mathcal{Z}_{t}-\mathbb{E}_{\mathbf{X},\boldsymbol{\xi}^{*},{\mathbf{Z}}}\frac{1}{n}\log\mathcal{Z}_{t}\Big{)}^{2}\leq\dfrac{C(f,\varphi)}{n}\,.$

###### Proof.

Since $\xi_{\mu}^{*}$, $Z_{\mu}$ and all elements of vectors
$\mathbf{X}_{\mu}$ are jointly independent for all $\mu$, we have thanks to
Proposition 11

$\mathbb{E}\mathbb{V}_{\mathbf{X},\boldsymbol{\xi}^{*},{\mathbf{Z}}}\Big{(}\frac{1}{n}\log\mathcal{Z}_{t}\Big{)}\leq\frac{1}{n^{2}}\mathbb{E}\|\nabla\log\mathcal{Z}_{t}\|^{2}\\\
=\frac{1}{n^{2}}\sum_{\mu=1}^{n}\mathbb{E}\Big{(}\frac{\partial\log\mathcal{Z}_{t}}{\partial\xi^{*}_{\mu}}\Big{)}^{2}+\frac{1}{n^{2}}\sum_{\mu=1}^{n}\sum_{i=1}^{d}\mathbb{E}\Big{(}\frac{\partial\log\mathcal{Z}_{t}}{\partial
X^{i}_{\mu}}\Big{)}^{2}+\frac{1}{n^{2}}\sum_{\mu=1}^{n}\mathbb{E}\Big{(}\frac{\partial\log\mathcal{Z}_{t}}{\partial
Z_{\mu}}\Big{)}^{2}=:I_{1}+I_{2}+I_{3}\,.$

For the sake of brevity we drop index $\rm out$ and write $P_{\mu}=P_{\rm
out}(Y_{t,\mu}|s_{t,\mu})$ in what follows. Gibbs brackets
$\langle\cdot\rangle$ are defined as in (39). After taking derivative in the
first term we obtain

$\displaystyle\Big{|}\frac{\partial\log\mathcal{Z}_{t}}{\partial\xi^{*}_{\mu}}\Big{|}=\Big{|}\Big{\langle}\frac{P_{\mu}^{y}}{P_{\mu}}\Big{\rangle}f^{\prime}(S_{t,\mu};{\mathbf{A}}_{\mu})\sqrt{t\epsilon}\Big{|}\leq
c\sqrt{t\epsilon}C(f)(|Z_{\mu}|^{2}+1)\,.$

Last inequality is due to boundedness of $f^{\prime}$ and Lemma 17. One can
see that the only randomness left is in $Z_{\mu}$. Since it is Gaussian, the
average of polynomial is bounded by some uniform constant $c$. We obtained
that each term in $I_{1}$ is bounded by constant, the number of terms is $n$,
from this it follows immediately that $I_{1}\leq C(f)/n$.

The second type of partial derivative will give us

$\frac{\partial\log\mathcal{Z}_{t}}{\partial
X^{i}_{\mu}}=\Big{\langle}\frac{P_{\mu}^{y}}{P_{\mu}}\Big{\rangle}f^{\prime}(S_{t,\mu};{\mathbf{A}}_{\mu})\Big{(}\sqrt{1-t}\frac{\big{(}\mathbf{a}^{*}\circ\varphi^{\prime}(\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}^{*}\big{)}_{i}}{\sqrt{pd}}+\sqrt{t\rho}\frac{v^{*}_{i}}{\sqrt{d}}\Big{)}\\\
+\Big{\langle}\frac{P_{\mu}^{x}}{P_{\mu}}\frac{\big{(}\mathbf{a}\circ\varphi^{\prime}(\frac{\mathbf{W}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}\big{)}_{i}}{\sqrt{pd}}\Big{\rangle}\sqrt{1-t}+\Big{\langle}\frac{P_{\mu}^{x}}{P_{\mu}}\frac{v_{i}}{\sqrt{d}}\Big{\rangle}\sqrt{t\rho}\,.$

Plugging this into $I_{2}$ and using the simple inequality
$\mathbb{E}(a+b)^{2}\leq 2(\mathbb{E}a^{2}+\mathbb{E}b^{2})$ in order to
square each term of the r.h.s. separately, we notice that it appeared the
terms

$\mathbb{E}\Big{\langle}\frac{P_{\mu}^{x}}{P_{\mu}}\frac{\big{(}\mathbf{a}\circ\varphi^{\prime}(\frac{\mathbf{W}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}\big{)}_{i}}{\sqrt{pd}}\Big{\rangle}^{2}\,,\qquad\mathbb{E}\Big{\langle}\frac{P_{\mu}^{x}}{P_{\mu}}\frac{v_{i}}{\sqrt{d}}\Big{\rangle}^{2}\,,$

which depend only on $Y_{t\mu},S_{t\mu}$ and $s_{t\mu}$. This allow us to use
Nishimori identity by removing the brackets and adding $*$ to ${\mathbf{a}}$,
${\mathbf{W}}$ and ${\mathbf{v}}$. Then evaluating each ratio with $P_{\rm
out}$ using Lemma 17 we get

$\displaystyle
I_{2}\leq\frac{C(f)(1-t)}{n^{2}}\sum_{\mu=1}^{n}\mathbb{E}\Big{(}(|Z_{\mu}|^{2}+1)^{2}\frac{\|\mathbf{a}^{*}\circ\varphi^{\prime}\Big{(}\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}}\Big{)}\mathbf{W}^{*}\|^{2}}{pd}\Big{)}+\dfrac{C(f)t\rho}{n}\mathbb{E}\Big{(}(|Z_{\mu}|^{2}+1)^{2}\dfrac{\|{\mathbf{v}}^{*}\|^{2}}{d}\Big{)}\,.$
(107)

after what we notice that factors $(|Z_{\mu}|^{2}+1)^{2}$ are independent of
others and its expectation can be bounded with positive constant. In the end
we obtain

$\displaystyle
I_{2}\leq\frac{C(f)}{n^{2}}\sum_{\mu=1}^{n}\mathbb{E}\frac{\|\mathbf{a}^{*}\circ\varphi^{\prime}\big{(}\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}}\big{)}\mathbf{W}^{*}\|^{2}}{pd}+\dfrac{C(f)}{n}\,.$
(108)

To finish the proof we notice that when we expand the norm appearing above all
non zero terms will contain only squares, e.g.,
$\mathbb{E}(a^{*}_{i}\varphi^{\prime}_{i}W^{*}_{ij})^{2}$, and so be positive.
This gives as opportunity to bound $\varphi^{\prime}$ with $C(\varphi)$ in
each term and calculate its expectation which is simply $C(\varphi)$. The
number of such terms is exactly $pd$, this gives us simple bound $I_{2}\leq
C(f,\varphi)/n$.

Finally, the derivatives with respect to $Z_{\mu}$ are of the form

$\displaystyle\frac{\partial\log\mathcal{Z}_{t}}{\partial
Z_{\mu}}=\sqrt{\Delta}\Big{\langle}\frac{P^{y}_{\mu}}{P_{\mu}}\Big{\rangle}\,.$
(109)

Similarly to what done above we bound $I_{3}$ with the help of Lemma 17

$\displaystyle I_{3}\leq\frac{C(f)}{n}\,.$ (110)

∎

Next step would be to prove the concentration of function
$\mathbb{E}_{\mathbf{X},{\mathbf{Z}},\boldsymbol{\xi}^{*}}\log\mathcal{Z}_{t}/n$
with respect to ${\mathbf{A}}$ using Proposition 12 while keeping
$\mathbf{W}^{*}$ and $\mathbf{v}^{*}$ fixed.

######  Lemma 14.

There exists a constant $C(f,\varphi)>0$ such that

$\displaystyle\mathbb{E}\Big{(}\frac{1}{n}\mathbb{E}_{\mathbf{X},{\mathbf{Z}},\boldsymbol{\xi}^{*}}\log\mathcal{Z}_{t}-\mathbb{E}_{{\mathbf{A}}}\frac{1}{n}\mathbb{E}_{\mathbf{X},{\mathbf{Z}},\boldsymbol{\xi}^{*}}\log\mathcal{Z}_{t}\Big{)}^{2}\leq\frac{C(f,\varphi)}{n}\,.$
(111)

###### Proof.

We consider
$h({\mathbf{A}})=\mathbb{E}_{\mathbf{X},{\mathbf{Z}},\boldsymbol{\xi}^{*}}\log\mathcal{Z}_{t}/n$
a function of all the elements ${\mathbf{A}}_{\mu,i}$ of ${\mathbf{A}}_{\mu}$
for $1\leq i\leq k$ and $1\leq\mu\leq n$. We denote by ${\mathbf{A}}^{\prime}$
a vector such that ${\mathbf{A}}^{\prime}_{\mu,i}={\mathbf{A}}_{\mu,i}$ for
$\mu\neq\nu$, $i\neq j$ and ${\mathbf{A}}^{\prime}_{\nu,j}$ is a random
variable with distribution $P_{A}$, independent of all others. According to
Proposition 12 it is sufficient to prove that

$\displaystyle|h({\mathbf{A}}^{\prime})-h({\mathbf{A}})|<\frac{C(f,\varphi)}{n}\,.$
(112)

If we denote by $H$ (and $H^{\prime}$) the Hamiltonian corresponding to
$\mathcal{Z}_{t}$ (and $\mathcal{Z}_{t}$ with ${\mathbf{A}}^{\prime}$) one can
see that

$\displaystyle
h({\mathbf{A}}^{\prime})-h({\mathbf{A}})=\frac{1}{n}\mathbb{E}_{\mathbf{X},{\mathbf{Z}},\boldsymbol{\xi}^{*}}\log\Big{\langle}e^{H-H^{\prime}}\Big{\rangle}_{H}\geq\frac{1}{n}\mathbb{E}_{\mathbf{X},{\mathbf{Z}},\boldsymbol{\xi}^{*}}\Big{\langle}H-H^{\prime}\Big{\rangle}_{H}\,,$
(113)

the last step being true due to Jensen inequality. On the other hand
$h({\mathbf{A}}^{\prime})-h({\mathbf{A}})\leq\mathbb{E}_{\mathbf{X},{\mathbf{Z}},\boldsymbol{\xi}^{*}}\langle
H-H^{\prime}\rangle_{H^{\prime}}/n$. We recall the definition (2) of $P_{\rm
out}(Y_{t\mu},s_{t\mu})$ and similarly we obtain

$\displaystyle
H-H^{\prime}\geq\frac{1}{2\Delta}\Big{\langle}(f(S_{t\nu};{\mathbf{A}}_{\nu}^{\prime})-f(s_{t\nu};\tilde{{\mathbf{A}}})+\sqrt{\Delta}Z_{\nu})^{2}-(f(S_{t\nu};{\mathbf{A}}_{\nu})-f(s_{t\nu};\tilde{{\mathbf{A}}})+\sqrt{\Delta}Z_{\nu})^{2}\Big{\rangle}_{G^{\prime}}$
(114)

and

$\displaystyle
H-H^{\prime}\leq\frac{1}{2\Delta}\Big{\langle}(f(S_{t\nu};{\mathbf{A}}_{\nu}^{\prime})-f(s_{t\nu};\tilde{{\mathbf{A}}})+\sqrt{\Delta}Z_{\nu})^{2}-(f(S_{t\nu};{\mathbf{A}}_{\nu})-f(s_{t\nu};\tilde{{\mathbf{A}}})+\sqrt{\Delta}Z_{\nu})^{2}\Big{\rangle}_{G}\,,$
(115)

where $\langle\cdot\rangle_{G}$ (or with $G^{\prime}$) defined as

$\displaystyle\langle\cdot\rangle_{G}=\dfrac{\int
P_{A}(d\tilde{{\mathbf{A}}})e^{-\frac{1}{2\Delta}(Y_{t\nu}-f(s_{t\nu};\tilde{{\mathbf{A}}}))^{2}}(\cdot)}{\int
P_{A}(d\tilde{{\mathbf{A}}})e^{-\frac{1}{2\Delta}(Y_{t\nu}-f(s_{t\nu};\tilde{{\mathbf{A}}}))^{2}}}$
(116)

or with $Y^{\prime}_{t\nu}$ where ${\mathbf{A}}_{\nu}$ is changed to
${\mathbf{A}}^{\prime}_{\nu}$. Since $f$ is bounded we immediately obtain
$|H-H^{\prime}|\leq C(f)(|Z_{\mu}|^{2}+1)$ and (112). Now, due to the
Proposition 12, the statement of the Lemma is proved.

∎

The last part is to prove the concentration of function
$g=\mathbb{E}_{\psi}\log\mathcal{Z}_{t}/n$ with respect to
$\mathbf{W}^{*},{\mathbf{v}}^{*}$.

######  Lemma 15.

There exists a constant $C(f,\varphi)>0$ such that

$\displaystyle\mathbb{E}(g-\mathbb{E}_{\mathbf{W}^{*},{\mathbf{v}}^{*}}g)^{2}\leq\frac{C(f,\varphi)}{d}\,.$
(117)

###### Proof.

Due to Poincare-Nash inequality we have

$\displaystyle\mathbb{E}(g-\mathbb{E}_{\mathbf{W}^{*},{\mathbf{v}}^{*}}g)^{2}\leq\sum_{i,j}^{p,d}\mathbb{E}\Big{(}\frac{\partial
g}{\partial W^{*}_{ij}}\Big{)}^{2}+\sum_{i}^{d}\mathbb{E}\Big{(}\frac{\partial
g}{\partial v^{*}_{i}}\Big{)}^{2}\,.$ (118)

Let us first deal with the partial derivatives with respect to $W^{*}_{ij}$

$\displaystyle\frac{\partial g}{\partial
W^{*}_{ij}}=\frac{1}{n}\sum_{\mu}^{n}\mathbb{E}_{\psi}\Big{(}\Big{\langle}\frac{P_{\mu}^{y}}{P_{\mu}}\Big{\rangle}f^{\prime}(S_{t\mu},{\mathbf{A}}_{\mu})\frac{\sqrt{1-t}a_{i}^{*}\varphi^{\prime}_{i}X_{\mu}^{j}}{\sqrt{pd}}\Big{)}\,,$
(119)

where
$\varphi^{\prime}_{i}=\varphi^{\prime}(\mathbf{W}^{*}_{i}\mathbf{X}_{\mu}/\sqrt{d})$.
Before integrating by parts with respect to $X_{\mu}^{j}$ let us notice that
in the sum over $\mu$ all terms are the same since we are taking the
expectation over all i.i.d. vectors $\mathbf{X_{\mu}}$, ${\mathbf{A}}_{\mu}$,
$Z_{\mu}$ and $\xi_{\mu}$, it means that we can disregard the sum and just
multiply by $n$ directly. Then we have

$\frac{\partial g}{\partial W^{*}_{ij}}=\mathbb{E}_{\psi}\Big{[}\frac{\partial
S_{t\mu}}{\partial
X^{j}_{\mu}}\frac{\sqrt{1-t}a_{i}^{*}\varphi^{\prime}_{i}}{\sqrt{pd}}\Big{(}-\Big{\langle}\frac{P_{\mu}^{y}}{P_{\mu}}\Big{\rangle}^{2}f^{\prime}(S_{t\mu};{\mathbf{A}}_{\mu})^{2}+\Big{\langle}\frac{P_{\mu}^{yy}}{P_{\mu}}\Big{\rangle}f^{\prime}(S_{t\mu};{\mathbf{A}}_{\mu})^{2}+\Big{\langle}\frac{P_{\mu}^{y}}{P_{\mu}}\Big{\rangle}f^{\prime\prime}(S_{t\mu};{\mathbf{A}}_{\mu})\Big{)}\Big{]}\\\
+\mathbb{E}_{\psi}\Big{[}\frac{\sqrt{1-t}a_{i}^{*}\varphi^{\prime}_{i}}{\sqrt{pd}}\Big{(}-\Big{\langle}\frac{P_{\mu}^{y}}{P_{\mu}}\Big{\rangle}\Big{\langle}\frac{P_{\mu}^{x}}{P_{\mu}}\frac{\partial
s_{t\mu}}{\partial
X^{j}_{\mu}}\Big{\rangle}+\Big{\langle}\frac{P_{\mu}^{yx}}{P_{\mu}}\frac{\partial
s_{t\mu}}{\partial
X^{j}_{\mu}}\Big{\rangle}\Big{)}f^{\prime}(S_{t\mu};{\mathbf{A}}_{\mu})\Big{]}+\mathbb{E}_{\psi}\Big{[}\frac{\sqrt{1-t}a_{i}^{*}\varphi^{\prime\prime}_{i}W^{*}_{ij}}{\sqrt{p}d}f^{\prime}(S_{t\mu};{\mathbf{A}}_{\mu})\Big{]}\,.$
(120)

Due to the Lemma 17 absolute values of ratios of $P$’s are bounded with
$C(f)(|Z_{\mu}|^{2}+1)$. In the first term of expression above one can easily
get rid of $Z_{\mu}$ since
$\mathbb{E}_{\psi}\langle(1+|Z_{\mu}|^{2})\rangle<C$. On the other hand
derivatives of $f$ and $\varphi$, in view of (Bayesian-optimal learning of a
shallow network in the teacher-student set-up, remain bounded with non-
negative constant $C(f,\varphi)$, so combining all above and plugging into
latter expression along with derivatives of $S_{t\mu}$ and $s_{t\mu}$ we
obtain

$\Big{|}\frac{\partial g}{\partial
W^{*}_{ij}}\Big{|}\leq\frac{C(f,\varphi)}{\sqrt{d}}\mathbb{E}_{\psi}\Big{|}\frac{\big{(}\mathbf{a}^{*}\circ\varphi^{\prime}(\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}^{*}\big{)}_{j}}{\sqrt{pd}}\frac{a_{i}^{*}}{\sqrt{p}}\Big{|}+\frac{C(f,\varphi)}{\sqrt{d}}\mathbb{E}_{\psi}\Big{|}\frac{v^{*}_{j}}{\sqrt{d}}\frac{a_{i}^{*}}{\sqrt{p}}\Big{|}\\\
+\frac{C(f,\varphi)}{\sqrt{d}}\mathbb{E}_{\psi}\Big{|}(|Z_{\mu}|^{2}+1)\frac{a_{i}^{*}}{\sqrt{p}}\Big{\langle}\frac{\big{(}\mathbf{a}\circ\varphi^{\prime}(\frac{\mathbf{W}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}\big{)}_{j}}{\sqrt{pd}}\Big{\rangle}\Big{|}+\frac{C(f,\varphi)}{\sqrt{d}}\mathbb{E}_{\psi}\Big{|}(|Z_{\mu}|^{2}+1)\frac{a_{i}^{*}}{\sqrt{p}}\Big{\langle}\frac{v_{j}}{\sqrt{d}}\Big{\rangle}\Big{|}+\frac{C(f,\varphi)}{\sqrt{d}}\mathbb{E}_{\psi}\Big{|}\frac{a_{i}^{*}W^{*}_{ij}}{\sqrt{pd}}\Big{|}\,.$
(121)

After using repeatedly $\mathbb{E}(a+b)^{2}\leq
2\mathbb{E}a^{2}+2\mathbb{E}b^{2}$ along with Jensen inequality one can show

$\sum_{i,j}^{p,d}\mathbb{E}\Big{|}\frac{\partial g}{\partial
W^{*}_{ij}}\Big{|}^{2}\leq\frac{C(f,\varphi)}{d}\Big{(}\mathbb{E}\Big{[}\frac{\|\mathbf{a}^{*}\circ\varphi^{\prime}(\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}^{*}\|^{2}}{pd}\frac{\|{\mathbf{a}}^{*}\|^{2}}{p}\Big{]}\\\
+\mathbb{E}\Big{[}\frac{(|Z_{\mu}|^{2}+1)^{2}\|{\mathbf{a}}^{*}\|^{2}}{p}\Big{\langle}\frac{\|\mathbf{a}\circ\varphi^{\prime}(\frac{\mathbf{W}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}\|^{2}}{pd}\Big{\rangle}\Big{]}+\mathbb{E}\Big{[}\frac{(|Z_{\mu}|^{2}+1)^{2}\|{\mathbf{a}}^{*}\|^{2}}{p}\Big{\langle}\frac{\|{\mathbf{v}}\|^{2}}{d}\Big{\rangle}\Big{]}+2\Big{)}\,.$
(122)

Two terms of the form $\mathbb{E}[b\langle c\rangle]$ we bound by using
Cauchy-Schwartz inequality, Jensen’s inequality and Nishimori identity
consecutively:

$\displaystyle\mathbb{E}[b\langle
c\rangle]\leq\mathbb{E}^{1/2}[b^{2}]\mathbb{E}^{1/2}[\langle
c\rangle^{2}]\leq\mathbb{E}^{1/2}[b^{2}]\mathbb{E}^{1/2}[\langle
c^{2}\rangle]\leq\mathbb{E}^{1/2}[b^{2}]\mathbb{E}^{1/2}[c^{2}]\,.$ (123)

This allows us to rewrite (122) as

$\displaystyle\sum_{i,j}^{p,d}\mathbb{E}\Big{|}\frac{\partial g}{\partial
W^{*}_{ij}}\Big{|}^{2}\leq\frac{C(f,\varphi)}{d}\Big{(}\mathbb{E}^{1/2}\Big{[}\frac{\|\mathbf{a}^{*}\circ\varphi^{\prime}(\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}^{*}\|^{4}}{p^{2}d^{2}}\Big{]}+C\Big{)}\,.$
(124)

What is left is to notice that in
$\mathbb{E}\|\mathbf{a}^{*}\circ\varphi^{\prime}(\mathbf{W}^{*}\mathbf{X}_{\mu}/{\sqrt{d}})\mathbf{W}^{*}\|^{4}/(p^{2}d^{2})$
all non zero terms will have only even powers so we can bound
$\varphi^{\prime}$ with a constant in all of them, which gives immediately

$\displaystyle\sum_{i,j}^{p,d}\mathbb{E}\Big{|}\frac{\partial g}{\partial
W^{*}_{ij}}\Big{|}^{2}\leq\frac{C(f,\varphi)}{d}\,.$ (125)

Now we consider the partial derivative with respect to $v_{i}^{*}$

$\displaystyle\frac{\partial g}{\partial
v^{*}_{i}}=\frac{1}{n}\sum_{\mu}^{n}\mathbb{E}_{\psi}\Big{[}\Big{\langle}\frac{P^{y}_{\mu}}{P_{\mu}}\Big{\rangle}f^{\prime}(S_{t,\mu};{\mathbf{A}}_{\mu})\frac{\sqrt{t\rho}X_{\mu}^{i}}{\sqrt{d}}\Big{]}\,.$
(126)

As in the case with $W_{ij}^{*}$ it is necessary to integrate by parts also
with respect to $X_{\mu}^{i}$ since blind bounds will not give us the desired
order. The result will be very similar to the previous calculation just this
time we don’t have factors $\varphi^{\prime}_{i}$ and $a^{*}_{i}$. After
similar simplification (bounds on ratios of $P$’s, etc.) we obtain

$\Big{|}\frac{\partial g}{\partial
v^{*}_{i}}\Big{|}\leq\frac{C(f,\varphi)}{\sqrt{d}}\mathbb{E}_{\psi}\Big{|}\frac{(\mathbf{a}^{*}\circ\varphi^{\prime}(\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}^{*})_{i}}{\sqrt{pd}}\Big{|}+\frac{C(f,\varphi)}{\sqrt{d}}\mathbb{E}_{\psi}\Big{|}\frac{v^{*}_{i}}{\sqrt{d}}\Big{|}\\\
+\frac{C(f,\varphi)}{\sqrt{d}}\mathbb{E}_{\psi}\Big{|}(|Z_{\mu}|^{2}+1)\Big{\langle}\frac{(\mathbf{a}\circ\varphi^{\prime}(\frac{\mathbf{W}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W})_{i}}{\sqrt{pd}}\Big{\rangle}\Big{|}+\frac{C(f,\varphi)}{\sqrt{d}}\mathbb{E}_{\psi}\Big{|}(|Z_{\mu}|^{2}+1)\Big{\langle}\frac{v_{i}}{\sqrt{d}}\Big{\rangle}\Big{|}\,.$
(127)

Similarly to the previous case it is easy to see that

$\sum_{i}^{d}\mathbb{E}\Big{|}\frac{\partial g}{\partial
v^{*}_{i}}\Big{|}^{2}\leq\frac{C(f,\varphi)}{d}\Big{(}\mathbb{E}\Big{[}\frac{\|\mathbf{a}^{*}\circ\varphi^{\prime}(\frac{\mathbf{W}^{*}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}^{*}\|^{2}}{pd}\Big{]}+\mathbb{E}\Big{[}\frac{\|{\mathbf{v}}^{*}\|^{2}}{d}\Big{]}\\\
+\mathbb{E}\Big{[}(|Z_{\mu}|^{2}+1)^{2}\Big{\langle}\frac{\|\mathbf{a}\circ\varphi^{\prime}(\frac{\mathbf{W}\mathbf{X}_{\mu}}{\sqrt{d}})\mathbf{W}\|^{2}}{pd}\Big{\rangle}\Big{]}+\mathbb{E}\Big{[}(|Z_{\mu}|^{2}+1)^{2}\Big{\langle}\frac{\|{\mathbf{v}}\|^{2}}{d}\Big{\rangle}\Big{]}\Big{)}\,.$
(128)

In order to be able to apply Nishimori identity to the last two terms we have
first to use Cauchy-Shchwarz inequality to separate factors with noise
$Z_{\mu}$ from the Gibbs bracket. Due to the fact that $\varphi^{\prime}$ is
bounded we obtain

$\displaystyle\sum_{i}^{d}\mathbb{E}\Big{|}\frac{\partial g}{\partial
v^{*}_{i}}\Big{|}^{2}\leq\frac{C(f,\varphi)}{d}\,.$ (129)

This combined with (125) finishes the proof. ∎

##  5 Proof of Proposition 3

The proof is implied by that of Theorem 1. We introduce a further set of data
$\tilde{\mathcal{D}}_{n}:=\\{({\mathbf{X}}_{\nu},\tilde{Y}_{\nu})\\}_{n+1\leq\nu\leq
n(1+\varepsilon)}$ with responses

$\displaystyle\tilde{Y}_{\nu}=\sqrt{\lambda}Y^{\prime}_{\nu}+\tilde{Z}^{\prime}_{\nu}\,,\quad
Y^{\prime}_{\nu}\sim P_{\rm out}(\cdot\mid S_{\nu})$ (130)

where $\lambda\geq 0$ and $n+1\leq\nu\leq n(1+\varepsilon)$ for some
$\varepsilon\geq 0$, $\tilde{Z}_{\nu}^{\prime}$ are i.i.d. Gaussian variables
independent of everything else, and where $S_{\nu}$ is defined as in (7) but
for the new inputs, with same teacher as used to generate $\mathcal{D}_{n}$.
We now define a proxy for the Bayes-optimal generalization error given the
original and new data:

$\displaystyle\mathcal{E}_{n}(\lambda,\varepsilon):=\frac{1}{n\varepsilon}\sum_{\nu=n+1}^{n(1+\varepsilon)}\mathbb{E}\big{[}(Y^{\prime}_{\nu}-\mathbb{E}[Y^{\prime}_{\nu}\mid\mathcal{D}_{n}\cup\tilde{\mathcal{D}}_{n}])^{2}\big{]}\,.$
(131)

This would recover the true definition of generalization if we set $\lambda=0$
in it. The quantity $\mathcal{E}_{n}(\lambda,\varepsilon)$ can be obtained
through the I-MMSE relation [90]

$\displaystyle\frac{1}{n}\frac{\partial}{\partial\lambda}I_{n}({\mathbf{Y}}^{\prime};\sqrt{\lambda}{\mathbf{Y}}^{\prime}+{\mathbf{Z}}^{\prime}\mid{\mathbf{Y}},({\mathbf{X}}_{\mu})_{\mu\leq
n(1+\varepsilon)})=\frac{\varepsilon}{2}\mathcal{E}_{n}(\lambda,\varepsilon)\,.$
(132)

Following the general arguments in [8], the mutual information on the l.h.s.
is concave in $\lambda$. Moreover the proof of Theorem 1 can be readily
extended to take into account the additional side information (130): indeed,
the proof is exactly the same as before except that the “channel” (130)
generating the $n\varepsilon$ responses is slightly different than the
original one $P_{\rm out}$. The new channel is equivalent to the original one
once we rescale the readout $f$ by $\sqrt{\lambda}f$ and the noise variance
$\Delta$ as $\lambda\Delta+1$ in (1). This channel still verifies the same
hypotheses. One then just need to keep track of the indices with responses
generated according to the basic model (1) and those from the rescaled channel
(130). In particular, it is possible to show the asymptotic equivalence of the
quantities
$I_{n}({\mathbf{Y}}^{\prime};\sqrt{\lambda}{\mathbf{Y}}^{\prime}+{\mathbf{Z}}^{\prime}\mid{\mathbf{Y}},({\mathbf{X}}_{\mu})_{\mu\leq
n(1+\varepsilon)})/n$ and
$I^{\circ}_{n}({\mathbf{Y}}^{\prime};\sqrt{\lambda}{\mathbf{Y}}^{\prime}+{\mathbf{Z}}^{\prime}\mid{\mathbf{Y}},({\mathbf{X}}_{\mu})_{\mu\leq
n(1+\varepsilon)})/n$, where the second one refers to the equivalent GLM, with
$S_{\nu}^{\circ}=\rho{\mathbf{v}}^{*\intercal}{\mathbf{X}}_{\nu}/{\sqrt{d}}+\sqrt{\epsilon}\xi_{\nu}^{*}$.
Then by concavity one can use Griffiths’ Lemma (see for instance [91, Lemma
IV.6.3]) to exchange the derivative with the limit $n\to\infty$ almost
everywhere:

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\frac{\partial}{\partial\lambda}I_{n}({\mathbf{Y}}^{\prime};\sqrt{\lambda}{\mathbf{Y}}^{\prime}+{\mathbf{Z}}^{\prime}\mid{\mathbf{Y}},({\mathbf{X}}_{\mu})_{\mu\leq
n(1+\varepsilon)})=\frac{\partial}{\partial\lambda}\lim_{n\to\infty}\frac{1}{n}I_{n}^{\circ}({\mathbf{Y}}^{\prime};\sqrt{\lambda}{\mathbf{Y}}^{\prime}+{\mathbf{Z}}^{\prime}\mid{\mathbf{Y}},({\mathbf{X}}_{\mu})_{\mu\leq
n(1+\varepsilon)})\,.$ (133)

The exchange fails when the model on the r.h.s., i.e. the GLM, presents a
phase transition. Then one has to send both $\lambda,\varepsilon\to 0$. The
authors of [8] showed that these limits commute with the $n\to\infty$ limit
for the GLM. So the r.h.s. yields the optimal generalization error for the GLM
proved in [8] that is therefore shared by the Bayesian two-layer neural
network under study.

##  Appendix A Nishimori identity

The Nishimori identities are a very general set of symmetries arising in
inference in the Bayes-optimal setting as a consequence of Bayes rule. They
were initially discovered in the context of the gauge theory of spin glasses
[92], which possess a sub-region of their phase space, called _Nishimori line_
, where the most relevant thermodynamic quantities can be exactly computed,
and we can generally count on replica symmetry, namely the concentration of
order parameters [93].

To introduce them, consider a generic inference problem where a Bayes-optimal
statistician observes ${\mathbf{Y}}$ that is a random function of some ground
truth signal ${\mathbf{X}}^{*}$: ${\mathbf{Y}}\sim P_{Y|X}({\mathbf{X}}^{*})$.
Then the following holds:

######  Proposition 16 (Nishimori identity).

For any bounded function $f$ of the signal ${\mathbf{X}}^{*}$, the data
${\mathbf{Y}}$ and of conditionally i.i.d. samples from the posterior
${\mathbf{x}}^{j}\sim P_{X\mid Y}(\,\cdot\mid{\mathbf{Y}})$, $j=1,2,\ldots,n$,
we have that

$\displaystyle\mathbb{E}\langle
f({\mathbf{Y}},{\mathbf{X}}^{*},{\mathbf{x}}^{2},\ldots,{\mathbf{x}}^{n})\rangle=\mathbb{E}\langle
f({\mathbf{Y}},{\mathbf{x}}^{1},{\mathbf{x}}^{2},\ldots,{\mathbf{x}}^{n})\rangle$
(134)

where the bracket notation $\langle\,\cdot\,\rangle$ is used for the joint
expectation over the posterior samples $({\mathbf{x}}^{j})_{j\leq n}$,
$\mathbb{E}$ is over the signal ${\mathbf{X}}^{*}$ and data ${\mathbf{Y}}$.

###### Proof.

The proof follows directly from Bayes’ rule. An elementary proof can be found
in [94]. ∎

##  Appendix B Proof of Lemma 4

Let us start with proving the auxiliary Lemma where we combine all necessary
bounds concerning derivatives of $P_{\rm out}(y|x)$. In what below $C(f)$ is a
general constant that depends on $f$ and also might depend on $\Delta$. Below,
upper indices represent partial derivatices, e.g., $P_{\rm
out}^{x}(y|x)=\partial_{x}P_{\rm out}(y|x)$ and $P_{\rm
out}^{xx}(y|x)=\partial_{x}\partial_{x}P_{\rm out}(y|x)$.

######  Lemma 17.

Let $y=Y_{t\mu}=f(S_{t\mu};{\mathbf{A}}_{\mu})+\sqrt{\Delta}Z_{\mu}$. Under
assumption (Bayesian-optimal learning of a shallow network in the teacher-
student set-up there exists constant $C(f)$ such that

$\displaystyle\max\Big{\\{}\Big{|}\dfrac{P_{\rm out}^{y}(y|x)}{P_{\rm
out}(y|x)}\Big{|},\Big{|}\dfrac{P_{\rm out}^{x}(y|x)}{P_{\rm
out}(y|x)}\Big{|},\Big{|}\dfrac{P_{\rm out}^{yy}(y|x)}{P_{\rm
out}(y|x)}\Big{|},\Big{|}\dfrac{P_{\rm out}^{yx}(y|x)}{P_{\rm
out}(y|x)}\Big{|},\Big{|}\dfrac{P_{\rm out}^{xx}(y|x)}{P_{\rm
out}(y|x)}\Big{|}\Big{\\}}<C(f)(|Z_{\mu}|^{2}+1)\,.$ (135)

###### Proof.

For convenience we recall here the definition of $P_{\rm out}(y|x)$

$\displaystyle P_{\rm out}(y\mid x)=\int
dP_{A}({\mathbf{A}})\frac{1}{\sqrt{2\pi\Delta}}\exp\Big{(}-\frac{1}{2\Delta}(y-f(x;{\mathbf{A}}))^{2}\Big{)}\,.$
(136)

It is easy to see that the ratio of any of these derivatives of $P_{\rm out}$
with $P_{\rm out}$ can be rewritten using an average

$\displaystyle\langle\cdot\rangle_{{\mathbf{A}}}:=\frac{\int
dP_{A}({\mathbf{A}})(\cdot)e^{-\frac{1}{2\Delta}(y-f(x;{\mathbf{A}}))^{2}}}{\int
dP_{A}({\mathbf{A}})e^{-\frac{1}{2\Delta}(y-f(x;{\mathbf{A}}))^{2}}}\,.$ (137)

After some algebra we get

$\displaystyle\frac{P_{\rm out}^{y}(y|x)}{P_{\rm out}(y|x)}$
$\displaystyle=\Big{\langle}-\frac{1}{\Delta}(y-f(x;{\mathbf{A}}))\Big{\rangle}_{{\mathbf{A}}}\,,$
(138) $\displaystyle\frac{P_{\rm out}^{x}(y|x)}{P_{\rm out}(y|x)}$
$\displaystyle=\Big{\langle}\frac{1}{\Delta}(y-f(x;{\mathbf{A}}))f^{\prime}(x;{\mathbf{A}})\Big{\rangle}_{{\mathbf{A}}}\,,$
(139) $\displaystyle\frac{P_{\rm out}^{yy}(y|x)}{P_{\rm out}(y|x)}$
$\displaystyle=\Big{\langle}\frac{1}{\Delta^{2}}(y-f(x;{\mathbf{A}}))^{2}\Big{\rangle}_{{\mathbf{A}}}-\frac{1}{\Delta}\,,$
(140) $\displaystyle\frac{P_{\rm out}^{yx}(y|x)}{P_{\rm out}(y|x)}$
$\displaystyle=\Big{\langle}-\frac{1}{\Delta^{2}}(y-f(x;{\mathbf{A}}))^{2}f^{\prime}(x;{\mathbf{A}})+\frac{1}{\Delta}f^{\prime}(x;{\mathbf{A}})\Big{\rangle}_{{\mathbf{A}}}\,,$
(141) $\displaystyle\frac{P_{\rm out}^{xx}(y|x)}{P_{\rm out}(y|x)}$
$\displaystyle=\Big{\langle}\Big{(}\frac{1}{\Delta^{2}}(y-f(x;{\mathbf{A}}))^{2}-\frac{1}{\Delta}\Big{)}f^{\prime}(x;{\mathbf{A}})^{2}+\frac{1}{\Delta}(y-f(x;{\mathbf{A}}))f^{\prime\prime}(x;{\mathbf{A}})\Big{\rangle}_{{\mathbf{A}}}\,.$
(142)

Since all expressions have a similar form we will treat only the last one, all
others can be bounded in the same way. We have

$\displaystyle\Big{|}\frac{P_{\rm out}^{xx}(y|x)}{P_{\rm
out}(y|x)}\Big{|}\leq\Big{\langle}\Big{(}\frac{1}{\Delta^{2}}(y-f(x;{\mathbf{A}}))^{2}+\frac{1}{\Delta}\Big{)}f^{\prime}(x;{\mathbf{A}})^{2}\Big{\rangle}_{{\mathbf{A}}}+\Big{\langle}\frac{1}{\Delta}\Big{|}y-f(x;{\mathbf{A}})\Big{|}\Big{|}f^{\prime\prime}(x;{\mathbf{A}})\Big{|}\Big{\rangle}_{{\mathbf{A}}}\,.$
(143)

When $y=f(S_{t\mu};{\mathbf{A}}_{\mu})+\sqrt{\Delta}Z_{\mu}$, since $f$ is
bounded along with its first two derivatives (see Bayesian-optimal learning of
a shallow network in the teacher-student set-up we obtain immediately

$\displaystyle\Big{|}\frac{P_{\rm out}^{xx}(y|x)}{P_{\rm out}(y|x)}\Big{|}\leq
C(f)(|Z_{\mu}|^{2}+1)\,.$ (144)

∎

######  Remark 3.

With such bound one can see that after averaging such ratios (with or without
$\langle\cdot\rangle$ as in (39)) with respect to $Z_{\mu}$, we simply obtain
a uniform bound $C(f)$.

Now let us return to the proof of Lemma 4.

###### Proof of Lemma 4.

By definition one has $\mathbb{E}[u^{\prime}_{Y_{t\mu}}(S_{t\mu})\mid
S_{t\mu}]=\int dyP^{x}_{\rm out}(y\mid S_{t\mu})=0$. For $U_{\mu\nu}$ instead,
we first need to realize that $U_{\mu\mu}=P^{xx}_{\rm out}(Y_{t\mu}\mid
S_{t\mu})/P_{\rm out}(Y_{t\mu}\mid S_{t\mu})$ which implies
$\mathbb{E}[U_{\mu\mu}\mid S_{t\mu}]=\int dyP^{xx}_{\rm out}(y\mid
S_{t\mu})=0$. Concerning the off-diagonal instead, conditionally on
$S_{t\mu},\,S_{t\nu}$ the remaining disorder in the $Y$’s is independent, so
for $\mu\neq\nu$ we have $\mathbb{E}[U_{\mu\nu}\mid S_{t\mu},S_{t\nu}]=\int
dyP^{x}_{\rm out}(y\mid S_{t\mu})\int dy^{\prime}P^{x}_{\rm
out}(y^{\prime}\mid S_{t\nu})=0$. For the boundedness of the derivatives it is
sufficient to notice that

$\displaystyle(u^{\prime}_{Y_{t\mu}}(S_{t\mu}))^{2}=\Big{(}\frac{P^{y}_{\rm
out}(Y_{t\mu}|S_{t\mu})}{P_{\rm out}(Y_{t\mu}|S_{t\mu})}\Big{)}^{2}\leq
C(f)(|Z_{\mu}|^{4}+1)\,,$ (145)

the last inequality being true due to Lemma 17 and the fact that
$Y_{t\mu}=f(S_{t\mu};{\mathbf{A}}_{\mu})+\sqrt{\Delta}Z_{\mu}$. Now it is
immediate that after taking the expectation conditioned on $S_{t\mu}$ we
obtain a bound $C(f)$. In order to deal with the last quantity
$U^{2}_{\mu\nu}$ we rewrite

$\displaystyle U^{2}_{\mu\nu}=\Big{(}\delta_{\mu\nu}\Big{(}\frac{P^{xx}_{\rm
out}(Y_{t\mu}|S_{t\mu})}{P_{\rm
out}(Y_{t\mu}|S_{t\mu})}-\Big{(}\frac{P^{x}_{\rm
out}(Y_{t\mu}|S_{t\mu})}{P_{\rm
out}(Y_{t\mu}|S_{t\mu})}\Big{)}^{2}\Big{)}+\frac{P^{x}_{\rm
out}(Y_{t\mu}|S_{t\mu})}{P_{\rm out}(Y_{t\mu}|S_{t\mu})}\frac{P^{x}_{\rm
out}(Y_{t\nu}|S_{t\nu})}{P_{\rm out}(Y_{t\nu}|S_{t\nu})}\Big{)}^{2}\,.$

With the help of Lemma 17 one can see immediately that $U^{2}_{\mu\nu}\leq
C(f)P(Z_{t\mu},Z_{t\nu})$, where $P$ is some polynomial with even degrees.
Once again, after taking expectation we get a bound by a positive constant
$C(f)$.

∎

##  Appendix C Proof of Lemma 5

For the reader convenience we repeat the statement of the Lemma below.

######  Lemma 18 (Approximations).

Recall $\rho:=\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{\prime}$ and
$\epsilon^{2}:=\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}-\rho^{2}$. Let
$\tilde{\varphi}$ be either $\varphi$ or the identity function. Under
assumptions (Bayesian-optimal learning of a shallow network in the teacher-
student set-up and (Bayesian-optimal learning of a shallow network in the
teacher-student set-up the following estimates hold:

$\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu
i})=\rho+O\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}\,,$ (146)
$\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu
i})=\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}+O\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}\,,$
(147) $\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi(\alpha_{\mu
i})\tilde{\varphi}(\alpha_{\nu
i})=\rho\mathbb{E}_{\mathcal{N}(0,1)}\tilde{\varphi}^{\prime}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}+O\Big{(}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}^{2}\Big{)}+O\Big{(}\frac{({\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu})^{2}}{\|{\mathbf{X}}_{\nu}\|^{2}d}\Big{)}+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}\Big{)}\,,$
(148) $\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu
i})\varphi^{\prime}(\alpha_{\nu
i})=\rho^{2}+O\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}\,,$
(149) $\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu
i})\tilde{\varphi}^{2}(\alpha_{\nu
i})=\mathbb{E}_{\mathcal{N}(0,1)}\varphi^{2}\mathbb{E}_{\mathcal{N}(0,1)}\tilde{\varphi}^{2}+O\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}\,.$
(150)

###### Proof.

Starting from (146), using the fundamental theorem of integral calculus we get

$\displaystyle|\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu
i})-\rho|=|\mathbb{E}\varphi^{\prime}\Big{(}z\sqrt{\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}}\Big{)}-\rho|\leq\int_{0}^{1}ds\mathbb{E}\frac{|z|}{2}\Big{|}\varphi^{\prime\prime}\Big{(}z\sqrt{s\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}+1-s}\Big{)}\Big{|}\frac{\big{|}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\big{|}}{\sqrt{s\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}+1-s}}$
(151)

where the average is only over $z\sim\mathcal{N}(0,1)$. If we use the bound on
the second derivative $\varphi^{\prime\prime}\leq\bar{K}$ we decouple
completely $s$ from $z$ and we can compute both the average
($\mathbb{E}|z|\leq\sqrt{\mathbb{E}z^{2}}=1$) and the integral, obtaining

$\displaystyle|\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu
i})-\rho|\leq\bar{K}\frac{\big{|}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\big{|}}{\frac{\|{\mathbf{X}}_{\mu}\|}{\sqrt{d}}+1}\leq\bar{K}\Big{|}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{|}\,.$
(152)

Let us now focus on (147). In the same spirit as the previous point:

$\displaystyle|\mathbb{E}_{{\mathbf{W}}^{*}}\tilde{\varphi}^{2}(\alpha_{\mu
i})-\mathbb{E}_{\mathcal{N}(0,1)}\tilde{\varphi}^{2}|=|\mathbb{E}\tilde{\varphi}^{2}\Big{(}z\sqrt{\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}}\Big{)}-\mathbb{E}_{\mathcal{N}(0,1)}\tilde{\varphi}^{2}|\leq\bar{K}\int_{0}^{1}ds\mathbb{E}|z\tilde{\varphi}(\cdots)|\frac{\big{|}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\big{|}}{\sqrt{s\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}+1-s}}$
(153)

with $\tilde{\varphi}^{\prime}\leq\bar{K}$ and the argument of
$\tilde{\varphi}$ is $z(s(\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1)+1)^{1/2}$.
Here, before being able to integrate over $s$ we need to bound the expectation
$\mathbb{E}|z\tilde{\varphi}(\cdots)|$. Recall that $\varphi$ is Lipschitz,
thus a simple bound is given by
$|\tilde{\varphi}(\cdots)|\leq\bar{K}|(\cdots)|$ using
$\tilde{\varphi}^{\prime}\leq\bar{K}$ and that $\tilde{\varphi}(0)=0$ as it is
odd. This yields immediately:

$\displaystyle|\mathbb{E}_{{\mathbf{W}}^{*}}\tilde{\varphi}^{2}(\alpha_{\mu
i})-\mathbb{E}_{\mathcal{N}(0,1)}\tilde{\varphi}^{2}|\leq\bar{K}^{2}\Big{|}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{|}\,.$
(154)

Consider now (148). In what follows we drop the $i$-index for brevity. Let

$\alpha_{\mu\perp\nu}:=\alpha_{\mu}-\alpha_{\nu}\frac{\mathbb{E}\alpha_{\mu}\alpha_{\nu}}{\mathbb{E}^{2}\alpha_{\nu}}=\alpha_{\mu}-\alpha_{\nu}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\,,$

that is independent of $\alpha_{\nu}$. Now we expand $\varphi$ around
$\alpha_{\mu\perp\nu}$:

$\displaystyle\begin{split}\mathbb{E}_{{\mathbf{W}}^{*}}\varphi(\alpha_{\mu})\tilde{\varphi}(\alpha_{\nu})&=\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu\perp\nu})\mathbb{E}_{{\mathbf{W}}^{*}}\tilde{\varphi}^{\prime}(\alpha_{\nu})\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{d}+\frac{1}{2}\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime\prime}(p)\tilde{\varphi}(\alpha_{\nu})\alpha_{\nu}^{2}\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}^{2}\,.\end{split}$
(155)

The zero-th order is zero because $\varphi$ is odd, and we have performed
Gaussian integration by parts in the first order. $p$ is a point in between
$\alpha_{\mu\perp\nu}$ and $\alpha_{\nu}$. Now we expand again
$\varphi^{\prime}(\alpha_{\mu\perp\nu})$ around the initial point
$\alpha_{\mu}$:

$\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu\perp\nu})=\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu})-\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime\prime}(p)\alpha_{\nu}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}=\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu})+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}$
(156)

where $p$ has the same meaning as before, and we used
$\varphi^{\prime\prime}\leq\bar{K}$. At this point it suffices to use (146) on
$\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu})$ and
$\mathbb{E}_{{\mathbf{W}}^{*}}\tilde{\varphi}^{\prime}(\alpha_{\nu})$ and the
estimate is proved.

Let us move to (149). As for the previous point, we follow the
orthogonalization procedure:

$\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu})\varphi^{\prime}(\alpha_{\nu})$
$\displaystyle=\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu\perp\nu})\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\nu})+\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime\prime}(p)\varphi^{\prime}(\alpha_{\nu})\alpha_{\nu}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}$
(157)
$\displaystyle=\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu\perp\nu})\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\nu})+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}\,.$
(158)

Now we use (156) and (146) to conclude:

$\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{\prime}(\alpha_{\mu})\varphi^{\prime}(\alpha_{\nu})=\rho^{2}+O\Big{(}\frac{\|{\mathbf{X}}_{\mu}\|^{2}}{d}-1\Big{)}+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}$
(159)

as in the statement.

Now we move to (150). As before, we expand $\varphi^{2}(\alpha_{\mu})$ around
$\alpha_{\mu\perp\nu}$:

$\displaystyle\begin{split}E_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu})\tilde{\varphi}^{2}(\alpha_{\nu})=\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu\perp\nu})\tilde{\varphi}^{2}(\alpha_{\nu})+2\mathbb{E}_{{\mathbf{W}}^{*}}\int_{0}^{1}ds\varphi(\alpha_{\mu,\nu}(s))\varphi^{\prime}(\alpha_{\mu,\nu}(s))\tilde{\varphi}^{2}(\alpha_{\nu})\alpha_{\nu}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\end{split}$
(160)

where
$\alpha_{\mu,\nu}(s)=\alpha_{\mu\perp\nu}+s\alpha_{\nu}{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}/\|{\mathbf{X}}_{\nu}\|^{2}$.
The integral on the r.h.s. can be bounded in different ways. For instance, one
can first integrate the $\alpha_{\nu}$ by part, recalling that
$\alpha_{\mu\perp\nu}$ is independent of it, and then exploit the fact that
both $\varphi$ and $\tilde{\varphi}$ are Lipschitz. This yields the
$O({\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}/\|{\mathbf{X}}_{\nu}\|^{2})$
in the statement.

The leading term
$\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu\perp\nu})\tilde{\varphi}^{2}(\alpha_{\nu})$
can be split into
$\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu\perp\nu})\mathbb{E}_{{\mathbf{W}}^{*}}\tilde{\varphi}^{2}(\alpha_{\nu})$
thanks to the orthogonalization. Expanding $\varphi^{2}(\alpha_{\mu\perp\nu})$
around $\alpha_{\mu}$ we get

$\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu\perp\nu})=\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu})-2\int_{0}^{1}ds\,\mathbb{E}_{{\mathbf{W}}^{*}}\varphi(\alpha_{\mu,\nu}(s))\varphi^{\prime}(\alpha_{\mu,\nu}(s))\alpha_{\nu}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}$
(161)

with $\alpha_{\mu,\nu}(s)$ as above. The integral contributes again with the
same order as the one above, therefore

$\displaystyle\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu})\tilde{\varphi}^{2}(\alpha_{\nu})=\mathbb{E}_{{\mathbf{W}}^{*}}\varphi^{2}(\alpha_{\mu})\mathbb{E}_{{\mathbf{W}}^{*}}\tilde{\varphi}^{2}(\alpha_{\nu})+O\Big{(}\frac{{\mathbf{X}}_{\mu}^{\intercal}{\mathbf{X}}_{\nu}}{\|{\mathbf{X}}_{\nu}\|^{2}}\Big{)}\,.$
(162)

Finally, it only remains to apply (54) to both the factors in the leading
contribution on the r.h.s., which yields the missing remainder
$O({\|{\mathbf{X}}_{\mu}\|^{2}}/{d}-1)$ in the statement.

∎

## References

  * [1] George V. Cybenko “Approximation by superpositions of a sigmoidal function” In _Mathematics of Control, Signals and Systems_ 2, 1989, pp. 303–314
  * [2] Kurt Hornik, Maxwell Stinchcombe and Halbert White “Multilayer feedforward networks are universal approximators” In _Neural Networks_ 2.5, 1989, pp. 359–366 DOI: 10.1016/0893-6080(89)90020-8
  * [3] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu and Liwei Wang “The Expressive Power of Neural Networks: A View from the Width” In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ Red Hook, NY, USA: Curran Associates Inc., 2017, pp. 6232–6240
  * [4] E Gardner and B Derrida “Three unfinished works on the optimal storage capacity of networks”, 1989, pp. 1983 DOI: 10.1088/0305-4470/22/12/004
  * [5] H.. Seung, H. Sompolinsky and N. Tishby “Statistical mechanics of learning from examples” In _Phys. Rev. A_ 45 American Physical Society, 1992, pp. 6056–6091 DOI: 10.1103/PhysRevA.45.6056
  * [6] J.. Nelder and R… Wedderburn “Generalized Linear Models” In _Journal of the Royal Statistical Society. Series A (General)_ 135.3, 1972, pp. 370–384
  * [7] Peter McCullagh “Generalized linear models” In _European Journal of Operational Research_ 16.3, 1984, pp. 285–292 DOI: https://doi.org/10.1016/0377-2217(84)90282-0
  * [8] Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane and Lenka Zdeborová “Optimal errors and phase transitions in high-dimensional generalized linear models” In _Proceedings of the National Academy of Sciences_ 116.12, 2019, pp. 5451–5460
  * [9] Laith Alzubaidi, Jinglan Zhang, Amjad J. Humaidi, Ayad Q. Al-Dujaili, Ye Duan, Omran Al-Shamma, Jesus Santamaría, Mohammed Abdulraheem Fadhel, Muthana Al-Amidie and Laith Farhan “Review of deep learning: concepts, CNN architectures, challenges, applications, future directions” In _Journal of Big Data_ 8, 2021
  * [10] Qianyi Li and Haim Sompolinsky “Statistical Mechanics of Deep Linear Neural Networks: The Backpropagating Kernel Renormalization” In _Phys. Rev. X_ 11 American Physical Society, 2021, pp. 031059 DOI: 10.1103/PhysRevX.11.031059
  * [11] Henry Schwarze and John Hertz “Generalization in a large committee machine” In _Europhysics Letters_ 20.4 IOP Publishing, 1992, pp. 375
  * [12] Henry Schwarze “Learning a rule in a multilayer neural network” In _Journal of Physics A: Mathematical and General_ 26.21 IOP Publishing, 1993, pp. 5781
  * [13] Rémi Monasson and Riccardo Zecchina “Learning and generalization theories of large committee-machines” In _Modern Physics Letters B_ 9.30 World Scientific, 1995, pp. 1887–1897
  * [14] Benjamin Aubin, Antoine Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris and Lenka Zdeborová “The committee machine: Computational to statistical gaps in learning a two-layers neural network” In _Advances in Neural Information Processing Systems_ 31, 2018
  * [15] Trevor Hastie, Andrea Montanari, Saharon Rosset and Ryan Tibshirani “Surprises in high-dimensional ridgeless least squares interpolation” In _The Annals of Statistics_ 50, 2022 DOI: 10.1214/21-AOS2133
  * [16] Song Mei and Andrea Montanari “The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve” In _Communications on Pure and Applied Mathematics_ 75, 2021 DOI: 10.1002/cpa.22008
  * [17] Sebastian Goldt, Marc Mézard, Florent Krzakala and Lenka Zdeborová “Modeling the influence of data structure on learning in neural networks: The hidden manifold model” In _Physical Review X_ 10.4 APS, 2020, pp. 041044
  * [18] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mézard and Lenka Zdeborová “The Gaussian equivalence of generative models for learning with shallow neural networks” In _Mathematical and Scientific Machine Learning_ , 2022, pp. 426–471 PMLR
  * [19] Hong Hu and Yue M Lu “Universality laws for high-dimensional learning with random features” In _IEEE Transactions on Information Theory_ IEEE, 2022
  * [20] Vladimir Nikolaevich Sudakov “Typical distributions of linear functionals in finite-dimensional spaces of higher dimension” In _Doklady Akademii Nauk_ 243.6, 1978, pp. 1402–1405 Russian Academy of Sciences
  * [21] Persi Diaconis and David Freedman “Asymptotics of graphical projection pursuit” In _The annals of statistics_ JSTOR, 1984, pp. 793–815
  * [22] Galen Reeves “Conditional central limit theorems for Gaussian projections” In _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 3045–3049 IEEE
  * [23] Elizabeth Meckes “Approximation of projections of random vectors” In _Journal of Theoretical Probability_ 25 Springer, 2012, pp. 333–352
  * [24] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz and Andrea Montanari “When do neural networks outperform kernel methods?” In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 14820–14830
  * [25] S Ariosto, R Pacelli, M Pastore, F Ginelli, M Gherardi and P Rotondo “Statistical mechanics of deep learning beyond the infinite-width limit” In _arXiv preprint arXiv:2209.04882_ , 2022
  * [26] Marc Mézard, Giorgio Parisi and Miguel Angel Virasoro “Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications” World Scientific Publishing Company, 1987
  * [27] Hugo Cui, Florent Krzakala and Lenka Zdeborová “Optimal Learning of Deep Random Networks of Extensive-width” In _arXiv preprint arXiv:2302.00375_ , 2023
  * [28] Eli Barkai, David Hansel and Haim Sompolinsky “Broken symmetries in multilayered perceptrons” In _Physical Review A_ 45.6 APS, 1992, pp. 4146
  * [29] Carlo Baldassi, Enrico M Malatesta and Riccardo Zecchina “Properties of the geometry of solutions and capacity of multilayer neural networks with rectified linear unit activations” In _Physical review letters_ 123.17 APS, 2019, pp. 170602
  * [30] Sebastian Goldt, Madhu S Advani, Andrew M Saxe, Florent Krzakala and Lenka Zdeborová “Dynamics of stochastic gradient descent for two-layer neural networks in the teacher–student setup” In _Journal of Statistical Mechanics: Theory and Experiment_ 2020.12 IOP Publishing, 2020, pp. 124010
  * [31] A. Engel, H.. Köhler, F. Tschepke, H. Vollmayr and A. Zippelius “Storage capacity and learning algorithms for two-layer neural networks” In _Phys. Rev. A_ 45 American Physical Society, 1992, pp. 7590–7609 DOI: 10.1103/PhysRevA.45.7590
  * [32] Henry Schwarze and John Hertz “Generalization in fully connected committee machines” In _EPL (Europhysics Letters)_ 21.7 IOP Publishing, 1993, pp. 785
  * [33] Rémi Monasson and Riccardo Zecchina “Weight space structure and internal representations: a direct approach to learning and generalization in multilayer neural networks” In _Physical review letters_ 75.12 APS, 1995, pp. 2432
  * [34] David Saad and Sara A. Solla “On-line learning in soft committee machines” In _Phys. Rev. E_ 52 American Physical Society, 1995, pp. 4225–4243 DOI: 10.1103/PhysRevE.52.4225
  * [35] German Mato and Nestor Parga “Generalization properties of multilayered neural networks” In _Journal of Physics A: Mathematical and General_ 25.19 IOP Publishing, 1992, pp. 5047
  * [36] Andreas Engel and Christian Van den Broeck “Statistical mechanics of learning” Cambridge University Press, 2001
  * [37] Atsushi Nitanda and Taiji Suzuki “Stochastic particle gradient descent for infinite ensembles” In _arXiv:1712.05438_ , 2017
  * [38] Diyuan Wu, Vyacheslav Kungurtsev and Marco Mondelli “Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence” In _Trans. Mach. Learn. Res._ 2023, 2022
  * [39] Adel Javanmard, Marco Mondelli and Andrea Montanari “Analysis of a two-layer neural network via displacement convexity” In _Annals of Statistics_ 48, 2020, pp. 3619–3642 DOI: 10.1214/20-AOS1945
  * [40] Alexander Shevchenko, Vyacheslav Kungurtsev and Marco Mondelli “Mean-Field Analysis of Piecewise Linear Solutions for Wide ReLU Networks” In _J. Mach. Learn. Res._ 23.1 JMLR.org, 2022
  * [41] Alexander Shevchenko and Marco Mondelli “Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks” In _Proceedings of the 37th International Conference on Machine Learning_ 119, Proceedings of Machine Learning Research PMLR, 2020, pp. 8773–8784
  * [42] Justin Sirignano and Konstantinos Spiliopoulos “Mean field analysis of neural networks: A central limit theorem” In _Stochastic Processes and their Applications_ 130.3 Elsevier, 2020, pp. 1820–1852
  * [43] Dyego Araújo, Roberto I Oliveira and Daniel Yukimura “A mean-field limit for certain deep neural networks” In _arXiv preprint arXiv:1906.00193_ , 2019
  * [44] Phan-Minh Nguyen “Mean field limit of the learning dynamics of multilayer neural networks” In _arXiv preprint arXiv:1902.02880_ , 2019
  * [45] Phan-Minh Nguyen and Huy Tuan Pham “A rigorous framework for the mean field limit of multilayer neural networks” In _arXiv preprint arXiv:2001.11443_ , 2020
  * [46] Song Mei, Andrea Montanari and Phan-Minh Nguyen “A mean field view of the landscape of two-layer neural networks” In _Proceedings of the National Academy of Sciences_ 115.33, 2018, pp. E7665–E7671 DOI: 10.1073/pnas.1806579115
  * [47] Song Mei, Theodor Misiakiewicz and Andrea Montanari “Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit” In _Conference on Learning Theory_ , 2019, pp. 2388–2464 PMLR
  * [48] Lénaïc Chizat and Francis Bach “On the Global Convergence of Gradient Descent for Over-Parameterized Models Using Optimal Transport” In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18 Montréal, Canada: Curran Associates Inc., 2018, pp. 3040–3050
  * [49] Grant Rotskoff and Eric Vanden-Eijnden “Trainability and Accuracy of Artificial Neural Networks: An Interacting Particle System Approach” In _Communications on Pure and Applied Mathematics_ 75, 2022, pp. 1889–1935 DOI: 10.1002/cpa.22074
  * [50] Arthur Jacot, Franck Gabriel and Clément Hongler “Neural tangent kernel: convergence and generalization in neural networks (invited paper)”, 2021, pp. 6–6 DOI: 10.1145/3406325.3465355
  * [51] Ali Rahimi and Benjamin Recht “Random Features for Large-Scale Kernel Machines” In _Proceedings of the 20th International Conference on Neural Information Processing Systems_ , NIPS’07 Vancouver, British Columbia, Canada: Curran Associates Inc., 2007, pp. 1177–1184
  * [52] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov and Ruosong Wang “On exact computation with an infinitely wide neural net” In _Advances in Neural Information Processing Systems_ 32, 2019
  * [53] Jiaoyang Huang and Horng-Tzer Yau “Dynamics of deep neural networks and neural tangent hierarchy” In _International Conference on Machine Learning_ , 2020, pp. 4542–4551 PMLR
  * [54] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz and Andrea Montanari “Linearized two-layers neural networks in high dimension” In _arXiv preprint arXiv:1904.12191_ , 2019
  * [55] Andrea Montanari and Yiqiao Zhong “The interpolation phase transition in neural networks: Memorization and generalization under lazy training” In _arXiv preprint arXiv:2007.12826_ , 2020
  * [56] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard and Lenka Zdeborová “Generalisation error in learning with random features and the hidden manifold model” In _International Conference on Machine Learning_ , 2020, pp. 3452–3462 PMLR
  * [57] Stéphane d’Ascoli, Maria Refinetti, Giulio Biroli and Florent Krzakala “Double trouble in double descent: Bias and variance (s) in the lazy regime” In _International Conference on Machine Learning_ , 2020, pp. 2280–2290 PMLR
  * [58] Mario Geiger, Leonardo Petrini and Matthieu Wyart “Perspective: A Phase Diagram for Deep Learning unifying Jamming, Feature Learning and Lazy Training” In _arXiv preprint arXiv:2012.15110_ , 2020
  * [59] Oussama Dhifallah and Yue M Lu “A precise performance analysis of learning with random features” In _arXiv preprint arXiv:2008.11904_ , 2020
  * [60] Blake Bordelon, Abdulkadir Canatar and Cengiz Pehlevan “Spectrum dependent learning curves in kernel regression and wide neural networks” In _International Conference on Machine Learning_ , 2020, pp. 1024–1034 PMLR
  * [61] Yuanzhi Li and Yang Yuan “Convergence Analysis of Two-layer Neural Networks with ReLU Activation” In _Advances in Neural Information Processing Systems_ 30, 2017 DOI: 10.5555/3294771.3294828
  * [62] Alessandro Rudi and Lorenzo Rosasco “Generalization Properties of Learning with Random Features” In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ Long Beach, California, USA: Curran Associates Inc., 2017, pp. 3218–3228
  * [63] Francis Bach “On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions” JMLR.org, 2017
  * [64] Yuanzhi Li and Yingyu Liang “Learning overparametrized neural networks via stochastic gradient descent on structured data” In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , 2018, pp. 8168–8177
  * [65] Zeyuan Allen-Zhu, Yuanzhi Li and Zhao Song “A convergence theory for deep learning via over-parameterization” In _International Conference on Machine Learning_ , 2019, pp. 242–252 PMLR
  * [66] Simon S. Du, Xiyu Zhai, Barnabas Poczos and Aarti Singh “Gradient Descent Provably Optimizes Over-parameterized Neural Networks” In _International Conference on Learning Representations_ , 2019 URL: https://openreview.net/forum?id=S1eK3i09YQ
  * [67] Simon Du, Jason Lee, Haochuan Li, Liwei Wang and Xiyu Zhai “Gradient descent finds global minima of deep neural networks” In _International Conference on Machine Learning_ , 2019, pp. 1675–1685 PMLR
  * [68] Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein and Jeffrey Pennington “Wide neural networks of any depth evolve as linear models under gradient descent” In _Journal of Statistical Mechanics: Theory and Experiment_ 2020.12 IOP Publishing, 2020, pp. 124002
  * [69] Radford M Neal “Bayesian learning for neural networks” Springer Science & Business Media, 2012
  * [70] Alexander G de G Matthews, Jiri Hron, Mark Rowland, Richard E Turner and Zoubin Ghahramani “Gaussian Process Behaviour in Wide Deep Neural Networks” In _International Conference on Learning Representations_ , 2018
  * [71] Jaehoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz and Yasaman Bahri “Deep Neural Networks as Gaussian Processes” In _International Conference on Learning Representations_ , 2018 URL: https://openreview.net/forum?id=B1EA-M-0Z
  * [72] Roman Novak, Lechao Xiao, Yasaman Bahri, Jaehoon Lee, Greg Yang, Daniel A. Abolafia, Jeffrey Pennington and Jascha Sohl-dickstein “Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes” In _International Conference on Learning Representations_ , 2019
  * [73] Ronen Eldan, Dan Mikulincer and Tselil Schramm “Non-asymptotic approximations of neural networks by Gaussian processes” In _Proceedings of Thirty Fourth Conference on Learning Theory_ 134, Proceedings of Machine Learning Research PMLR, 2021, pp. 1754–1775 URL: https://proceedings.mlr.press/v134/eldan21a.html
  * [74] Daniele Bracale, Stefano Favaro, Sandra Fortini and Stefano Peluchetti “Large-width functional asymptotics for deep Gaussian neural networks” In _International Conference on Learning Representations_ , 2021 URL: https://openreview.net/forum?id=0aW6lYOYB7d