Benjamin Aubin

Antoine Maillard

Jean Barbier

Florent Krzakala

Nicolas Macris

Lenka Zdeborová

Jean Barbier ⊗♦

The committee machine: Computational to statistical gaps in learning a two-layers neural network

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

While the traditional approach to learning and generalization follows the Vapnik-Cervenokis [START_REF] Vapnik | Statistical learning theory[END_REF] and Rademacher [START_REF] Bartlett | Rademacher and gaussian complexities: Risk bounds and structural results[END_REF] worst-case type bounds, there has been a considerable body of theoretical work on calculating the generalization ability of neural networks for data arising from a probabilistic model within the framework of statistical mechanics [START_REF] Seung | Statistical mechanics of learning from examples[END_REF][START_REF] Watkin | The statistical mechanics of learning a rule[END_REF][START_REF] Monasson | Learning and generalization theories of large committee-machines[END_REF][START_REF] Monasson | Weight space structure and internal representations: a direct approach to learning and generalization in multilayer neural networks[END_REF][START_REF] Engel | Statistical Mechanics of Learning[END_REF]. In the wake of the need to understand the e ectiveness of neural networks and also the limitations of the classical approaches [START_REF] Zhang | Understanding deep learning requires rethinking generalization[END_REF], it is of interest to revisit the results that have emerged thanks to the physics perspective. This direction is currently experiencing a strong revival, see e.g. [START_REF] Chaudhari | Entropy-sgd: Biasing gradient descent into wide valleys[END_REF][START_REF] Martin | Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior[END_REF][START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF][START_REF] Baity-Jesi | Comparing dynamics: Deep neural networks versus glassy systems[END_REF].

Of particular interest is the so-called teacher-student approach, where labels are generated by feeding i.i.d. random samples to a neural network architecture (the teacher) and are then presented to another neural network (the student) that is trained using these data. Early studies computed the information theoretic limitations of the supervised learning abilities of the teacher weights by a student who is given m independent n-dimensional examples with α = m/n = Θ(1) (i.e. scales as an order 1 constant) and n → ∞ [START_REF] Seung | Statistical mechanics of learning from examples[END_REF][START_REF] Watkin | The statistical mechanics of learning a rule[END_REF][START_REF] Engel | Statistical Mechanics of Learning[END_REF]. These works relied on non-rigorous heuristic approaches, such as the replica and cavity methods [START_REF] Mézard | Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications[END_REF][START_REF] Mézard | Information, physics, and computation[END_REF]. Additionally no provably e cient algorithm was provided to achieve the predicted learning abilities, and it was thus di cult to test those predictions, or to assess the computational di culty 1 .

Recent developments in statistical estimation and information theory -in particular of approximate message passing algorithms (AMP) [START_REF] Donoho | Message-passing algorithms for compressed sensing[END_REF][START_REF] Rangan | Generalized approximate message passing for estimation with random linear mixing[END_REF][START_REF] Bayati | The dynamics of message passing on dense graphs, with applications to compressed sensing[END_REF][START_REF] Javanmard | State evolution for general approximate message passing algorithms, with applications to spatial coupling[END_REF], and a rigorous proof of the replica formula for the optimal generalization error [START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF]-allowed to settle these two missing points for single-layer neural networks (i.e. without any hidden variables). In the present paper, we leverage on these works, and provide rigorous asymptotic predictions and corresponding message passing algorithm for a class of two-layers networks.

Summary of contributions and related works

While our results hold for a rather large class of non-linear activation functions, we illustrate our ndings on a case considered most commonly in the early literature: The committee machine. This is possibly the simplest version of a two-layers neural network where all the weights in the second layer are xed to unity. Denoting Y µ the label associated with a n-dimensional sample X µ , and W * il the weight connecting the i-th coordinate of the input to the l-th node of the hidden layer, it is de ned by:

Y µ = sign K l=1 sign n i=1 X µi W * il . (1)
We concentrate here on the teacher-student scenario: The teacher generates i.i.d. data samples with i.i.d. Gaussian coordinates X µi ∼ N (0, 1), then she generates the associated labels Y µ using a committee machine as in [START_REF] Vapnik | Statistical learning theory[END_REF], with i.i.d. weights W * il unknown to the student (in the proof section we will consider the more general case of a distribution for the weights of the form n i=1 P 0 ({W * il } K l=1 ), but in practice we consider the fully separable case). The student is then given the m input-output pairs (Y µ , X µ ) m µ=1 and she knows the distribution P 0 used to generate W * il . The goal of the student is to learn the weights W * il from the available examples (Y µ , X µ ) m µ=1 in order to reach the smallest possible generalization error (i.e. to be able to predict the label the teacher would generate for a new sample not present in the training set).

There have been several studies of this model within the non-rigorous statistical physics approach in the limit where α = m/n = Θ(1), K = Θ(1) and n → ∞ [START_REF] Schwarze | Learning a rule in a multilayer neural network[END_REF][START_REF] Schwarze | Generalization in a large committee machine[END_REF][START_REF] Schwarze | Generalization in fully connected committee machines[END_REF][START_REF] Mato | Generalization properties of multilayered neural networks[END_REF][START_REF] Monasson | Weight space structure and internal representations: a direct approach to learning and generalization in multilayer neural networks[END_REF][START_REF] Engel | Statistical Mechanics of Learning[END_REF]. A particularly interesting result in the teacher-student setting is the specialization of hidden neurons (see sec. 12.6 of [START_REF] Engel | Statistical Mechanics of Learning[END_REF], or [START_REF] Saad | On-line learning in soft committee machines[END_REF] in the context of online learning): For α < α spec (where α spec is a certain critical value of the sample complexity), the permutational symmetry between hidden neurons remains conserved even after an optimal learning, and the learned weights of each of the hidden neurons are identical. For α > α spec , however, this symmetry gets broken as each of the hidden units correlates strongly with one of the hidden units of the teacher. Another remarkable result is the calculation of the optimal generalization error as a function of α.

Our rst contribution consists in a proof of the replica formula conjectured in the statistical physics literature, using the adaptive interpolation method of [START_REF] Barbier | The adaptive interpolation method: A simple scheme to prove replica formulas in bayesian inference[END_REF][START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF], that allows to put several of these results on a rm rigorous basis. Our second contribution is the design of AMP-type of algorithm that is able to achieve the optimal learning error in the above limit of large dimensions for a wide range of parameters. The study of AMP -that is widely believed to be optimal between all polynomial algorithms in the above setting [START_REF] Donoho | Accurate prediction of phase transitions in compressed sensing via a connection to minimax denoising[END_REF][START_REF] Zdeborová | Statistical physics of inference: thresholds and algorithms[END_REF][START_REF] Deshpande | Finding hidden cliques of size \sqrt {N/e} n/e in nearly linear time[END_REF][START_REF] Bandeira | Notes on computational-to-statistical gaps: predictions using statistical physics[END_REF]unveils, in the case of the committee machine with a larger number of hidden neurons, the existence a large hard phase in which learning is information-theoretically possible, leading to a good generalization error decaying asymptotically as 1.25K/α (in the α = Θ(K) regime), but where AMP fails and provide only a poor generalization that does not decay when increasing α. This strongly suggests that no e cient algorithm exists in this hard region and therefore there is a computational gap in learning in such neural networks. In other problems where a hard phase was identi ed, its study boosted the development of algorithms that are able to match the predicted thresholds and we anticipate this will translate to the present model.

Main technical results

A general model

While in the illustration of our results we shall focus on the model [START_REF] Vapnik | Statistical learning theory[END_REF], all our formulas are valid for a broader class of models: Given m input samples (X µi ) m,n µ,i=1 , we denote W * il the teacher-weight connecting the i-th input (i.e. visible unit) to the l-th node of the hidden layer. For a generic function ϕ out : R K × R → R one can formally write the output as

Y µ = ϕ out 1 √ n n i=1 X µi W * il K l=1 , A µ or Y µ ∼ P out • 1 √ n n i=1 X µi W * il K l=1 , (2)
where (A µ ) m µ=1 are i.i.d. real valued random variables with known distribution P A , that form the probabilistic part of the model, generally accounting for noise. For deterministic models the second argument is simply absent (or is a Dirac mass). We can view alternatively (2) as a channel where the transition kernel P out is directly related to ϕ out . As discussed above, we focus on the teacher-student scenario where the teacher generates Gaussian i.i.d. X µi ∼ N (0, 1), and i.i.d. weights W * il ∼ P 0 . The student then learns W * from the data (Y µ , X µ ) m µ=1 by computing marginal means of the posterior probability distribution [START_REF] Chaudhari | Entropy-sgd: Biasing gradient descent into wide valleys[END_REF]. Di erent scenarii t into this general framework. Among those, the committee machine is obtained when choosing ϕ out (h) = sign( K l=1 sign(h l )). Another model is given by the parity machine, when ϕ out (h) = K l=1 sign(h l ), see e.g. [START_REF] Engel | Statistical Mechanics of Learning[END_REF], and we discuss this example further in appendix H. A number of layers beyond two has also been considered, see [START_REF] Mato | Generalization properties of multilayered neural networks[END_REF]. Other activation functions can be used, and many more problems can be described, e.g. compressed pooling [START_REF] Alaoui | Decoding from pooled data: Sharp information-theoretic bounds[END_REF][START_REF] Alaoui | Decoding from pooled data: Phase transitions of message passing[END_REF] or multi-vector compressed sensing [START_REF] Zhu | Performance limits for noisy multimeasurement vector problems[END_REF].

Two auxiliary inference problems

Denote S K the nite dimensional vector space of K × K matrices, S + K the convex and compact set of semi-de nite positive K × K matrices, S ++ K for positive de nite K × K matrices, and

∀ N ∈ S + K we set S + K (N ) ≡ {M ∈ S + K s.t. N -M ∈ S + K }.

Stating our results requires introducing two simpler auxiliary K-dimensional estimation problems:

• Input Gaussian channel: The rst one consists in retrieving a K-dimensional input vector W 0 ∼ P 0 from the output of a Gaussian vector channel with K-dimensional observations

Y 0 = R 1/2 W 0 + Z 0 (3)
with Z 0 ∼ N (0, I K×K ) and the "channel gain" matrix R ∈ S + K . The associated posterior distribution on w = {w l } K l=1 is

P (w|Y 0 ) = 1 Z P 0 P 0 (w)e Y 0 R 1/2 w-1 2 w Rw , (4)
and the associated free entropy (or minus free energy) is given by the expectation over Y 0 of the log-partition function

ψ P 0 (R) ≡ E ln Z P 0 = E ln R K dP 0 (w)e Y 0 R 1/2 w-1 2 w Rw (5)
and involves K dimensional integrals.

• Output channel: The second problem considers K-dimensional i.i.d. vectors V, U * ∼ N (0, I K×K ) where V is considered to be known and one has to retrieve U * from a scalar observation obtained as

Y 0 ∼ P out (•|q 1/2 V + (ρ -q) 1/2 U * ) (6)
where the second moment matrix ρ ≡ E[W 0 W 0 ] is in S + K (W 0 ∼ P 0 ) and the so-called "overlap matrix" q is in S + K (ρ). The associated posterior is

P (u| Y 0 , V ) = 1 Z Pout e -1 2 u u (2π) K/2 P out Y 0 |q 1/2 V + (ρ -q) 1/2 u , (7)
and the free entropy reads this time

Ψ Pout (q; ρ) ≡ E ln Z Pout = E ln R K K i=1 du i e -1 2 u u (2π) K/2 P out Y 0 |q 1/2 V + (ρ -q) 1/2 u (8)
(with the expectation over Y 0 and V ) and also involves K dimensional integrals.

The free entropy

The central object of study leading to the optimal learning and generalization errors in the present setting is the posterior distribution of the weights:

P ({w il } n,K i,l=1 | {Y µ , X µi } m,n µ,i=1 ) = 1 Z n n i=1 P 0 ({w il } K l=1 ) m µ=1 P out Y µ 1 √ n n i=1 X µi w il K l=1 , (9)
where the normalization factor is nothing else than a partition function, i.e. the integral of the numerator over {w il } n,K i,l=1 . The expected2 free entropy is by de nition

f n ≡ 1 n E ln Z n = 1 n E ln n i=1 dP 0 ({w il } K l=1 ) m µ=1 P out Y µ 1 √ n n i=1 X µi w il K l=1 . (10)
The replica formula gives an explicit (conjectural) expression of f n in the high-dimensional limit n, m → ∞ with α = m/n xed. We discuss in the supplementary material (appendices sec. C) how the heuristic replica method [START_REF] Mézard | Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications[END_REF][START_REF] Mézard | Information, physics, and computation[END_REF] yields the formula. This computation was rst performed, to the best of our knowledge, by [START_REF] Schwarze | Learning a rule in a multilayer neural network[END_REF] in the case of the committee machine. Our rst contribution is a rigourous proof of the corresponding free entropy formula using an interpolation method [START_REF] Guerra | Broken replica symmetry bounds in the mean eld spin glass model[END_REF][START_REF] Talagrand | Spin glasses: a challenge for mathematicians: cavity and mean eld models[END_REF][START_REF] Barbier | The adaptive interpolation method: A simple scheme to prove replica formulas in bayesian inference[END_REF]. In order to formulate our rigorous results, we add a (arbitrarily small) Gaussian term Z µ √ ∆ to the rst expression of the model [START_REF] Bartlett | Rademacher and gaussian complexities: Risk bounds and structural results[END_REF], where ∆ > 0, Z µ ∼ N (0, 1), so that the channel kernel is (u ∈ R K )

P out (y|u) = 1 √ 2π∆ R dP A (a)e -1 2∆ (y-ϕ(u,a)) 2 . ( 11
)
Theorem 3.1 (Replica formula). Suppose (H1): The prior P 0 has bounded support in R K ; (H2): The activation ϕ out : R K × R → R is a bounded C 2 function with bounded rst and second derivatives w.r.t. its rst argument (in R K -space); and (H3): For all µ = 1, . . . , m and i = 1, . . . , n we have X µi ∼ N (0, 1). Then for the model (2) with kernel [START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF], the m, n → ∞ limit of the free entropy in the regime α = m/n = Θ(1), K = Θ(1) is:

lim n→∞ f n ≡ lim n→∞ 1 n E ln Z n = sup R∈S + K inf q∈S + K (ρ) ψ P 0 (R) + αΨ Pout (q; ρ) - 1 2 Tr(Rq) , (12)
where Ψ Pout (q; ρ) and ψ P 0 (R) are the free entropies of simpler K-dimensional estimation problems ( 4) and [START_REF] Engel | Statistical Mechanics of Learning[END_REF].

This theorem extends the recent progress for generalized linear models of [START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF], which includes the case K = 1 of the present contribution, to the phenomenologically richer case of two-layers problems such as the committee machine. The proof sketch based on an adaptive interpolation method recently developed in [START_REF] Barbier | The adaptive interpolation method: A simple scheme to prove replica formulas in bayesian inference[END_REF] is outlined and the details can be found in the appendices sec. A. Note that, following similar approximation arguments as in [START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF], the hypothesis (H1) can be relaxed to the existence of the second moment of the prior; thus covering the Gaussian case, (H2) can be dropped (and thus include model (1) and its sign(•) activation) and (H3) extended to weight matrices with i.i.d. entries of zero mean, unit variance and nite third moment.

Learning the teacher weights and optimal generalization error

A classical result in Bayesian estimation is that the estimator Ŵ that minimizes the mean-square error with the ground-truth W * is given by the expected mean of the posterior distribution. Denoting q * the extremizer in the replica formula [START_REF] Baity-Jesi | Comparing dynamics: Deep neural networks versus glassy systems[END_REF], we expect from the replica method that in the limit n → ∞, m/n → α, with high probablity Ŵ W * /n → q * . We refer to proposition 5.2 and to the proof in appendices sec. A for the precise statement, that remains rigorously valid only in the presence of an additional (possibly in nitesimal) side-information. From the overlap matrix q * , one can compute the Bayes optimal generalization error when the student tries to classify a new, yet unseen, sample X new . The estimator of the new label Ŷnew that minimizes the mean-square error with the true label is given by computing the posterior mean of ϕ out (X new W ) (X new is a row vector). Given the new sample, the optimal generalization error is then

1 2 E E W |Y,X ϕ out (X new W )|Y, X -ϕ out (X new W * ) 2 ---→ n→∞ g (q * ) ( 13
)
where W is distributed according to the posterior measure (9) (note that this Bayes-optimal computation di ers from the so-called Gibbs estimator by a factor 2, see appendix sec. D). In particular, when the data X is drawn from the standard Gaussian distribution on R m×n , and is thus rotationally invariant, it follows that this error only depends on W W * , which converges to q * , and a direct algebraic computation gives a lengtly but explicit formula for g (q * ), as shown in the appendices.

Approximate message passing, and its state evolution

Our next result is based on an adaptation of a popular algorithm to solve random instances of generalized linear models, the AMP algorithm [START_REF] Donoho | Message-passing algorithms for compressed sensing[END_REF][START_REF] Rangan | Generalized approximate message passing for estimation with random linear mixing[END_REF], for the case of the committee machine and models described by [START_REF] Bartlett | Rademacher and gaussian complexities: Risk bounds and structural results[END_REF].

The AMP algorithm can be obtained as a Taylor expansion of loopy belief-propagation (as shown in appendices G.2) and also originate in earlier statistical physics works [START_REF] Thouless | Solution of'solvable model of a spin glass[END_REF][START_REF] Mézard | The space of interactions in neural networks: Gardner's computation with the cavity method[END_REF][START_REF] Opper | Mean eld approach to bayes learning in feed-forward neural networks[END_REF][START_REF] Kabashima | Inference from correlated patterns: a uni ed theory for perceptron learning and linear vector channels[END_REF][START_REF] Baldassi | E cient supervised learning in networks with binary synapses[END_REF][START_REF] Zdeborová | Statistical physics of inference: thresholds and algorithms[END_REF]. It is conjectured to perform the best among all polynomial algorithms in the framework of these models. It thus gives us a tool to evaluate both the intrinsic algorithmic hardness of the learning and the performance of existing algorithms with respect to the optimal one in this model.

The AMP algorithm is summarized by its pseudo-code in Algorithm 1, where the update functions g out , ∂ ω g out , f W and f C are related, again, to the two auxiliary problems (4) and [START_REF] Engel | Statistical Mechanics of Learning[END_REF]. The functions f W (Σ, T ) and f C (Σ, T ) are the mean and variance under the measure of the posterior (4) when R = Σ -1 and Y 0 = Σ 1/2 T , while g out (ω µ , Y µ , V µ ) is given by the expected mean of V -1/2 u under the posterior [START_REF] Engel | Statistical Mechanics of Learning[END_REF] using Y 0 = Y µ , ρq = V µ and q 1/2 V = ω µ (see appendix G.1 for more details). After convergence, Ŵ estimates the weights of the teacher-neural network. The label of a sample X new not seen in the training set is estimated by the AMP algorithm as

Y t new = dy K l=1 dz l yP out (y|{z l } K l=1 )N (z; ω t new , V t new ) , (14)
where ω t new = n i=1 X new,i Ŵ t i is the mean of the normally distributed variable z ∈ R K , and V t new = ρ-q t AMP Algorithm 1 Approximate Message Passing for the committee machine Input: vector Y ∈ R m and matrix X ∈ R m×n : Initialize: Ŵi , g out,µ ∈ R K and Ĉi , ∂ ω g out,µ ∈ S + K for 1 ≤ i ≤ n and 1 ≤ µ ≤ m at t = 0. repeat Update of the mean ω µ ∈ R K and covariance V µ ∈ S + K :

ω t µ = n i=1 X µi Ŵ t i -X 2 µi Σ t-1 i -1 Ĉt i Σ t-1 i g t-1 out,µ V t µ = n i=1 X 2 µi Ĉt i Update of g out,µ ∈ R K and ∂ ω g out,µ ∈ S + K : g t out,µ = g out (ω t µ , Y µ , V t µ ) ∂ ω g t out,µ = ∂ ω g out (ω t µ , Y µ , V t µ ) Update of the mean T i ∈ R K and covariance Σ i ∈ S + K : T t i = Σ t i m µ=1 X µi g t out,µ -X 2 µi ∂ ω g t out,µ Ŵ t i Σ t i = - m µ=1 X 2 µi ∂ ω g t out,µ -1
Update of the estimated marginals Ŵi ∈ R K and Ĉi ∈ S + K :

Ŵ t+1 i = f W (Σ t i , T t i ) Ĉt+1 i = f C (Σ t i , T t i ) t = t + 1 until Convergence on Ŵ , Ĉ. Output: Ŵ and Ĉ.
is the K × K covariance matrix (see below for the de nition of q t AMP ). We provide a demo of the algorithm on github [START_REF] Aubin | AMP implementation of the committee machine[END_REF].

AMP is particularly interesting because its performance can be tracked rigorously, again in the asymptotic limit when n → ∞, via a procedure known as state evolution (a rigorous version of the cavity method in physics [START_REF] Mézard | Information, physics, and computation[END_REF]), see [START_REF] Javanmard | State evolution for general approximate message passing algorithms, with applications to spatial coupling[END_REF]. State evolution tracks the value of the overlap between the hidden ground truth W * and the AMP estimate Ŵt , de ned as q t AMP ≡ ( Ŵ t ) W * /n via:

q t+1 AMP = 2 ∂ψ P 0 ∂R (R t AMP ) , R t+1 AMP = 2α ∂Ψ Pout ∂q (q t AMP ; ρ) . (15)
The xed points of these equations correspond to the critical points of the replica free entropy [START_REF] Baity-Jesi | Comparing dynamics: Deep neural networks versus glassy systems[END_REF].

4 From two to more hidden neurons, and the specialization phase transition

Two neurons

Let us now discuss how the above results can be used to study the optimal learning in the simplest non-trivial case of a two-layers neural network with two hidden neurons, i.e. when model ( 1) is simply

Y µ = sign sign n i=1 X µi W * i1 + sign n i=1 X µi W * i2 , (16)
with the convention that sign(0) = 0. We remind that the input-data-matrix X has i.i.d. N (0, 1) entries, and the teacher-weights W * used to generate the labels Y are taken i.i.d. from P 0 . In Fig. 1 we plot the optimal generalization error as a function of the sample complexity α = m/n. In the left panel the weights are Gaussian (for both the teacher and the student), while in the center panel they are binary/Rademacher (recall that (H3) in Theorem 3.1 can be relaxed to include this case, see [START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF]). The full line is obtained from the xed point of the state evolution (SE) of the AMP algorithm [START_REF] Donoho | Message-passing algorithms for compressed sensing[END_REF], corresponding to the extremizer of the replica free entropy [START_REF] Baity-Jesi | Comparing dynamics: Deep neural networks versus glassy systems[END_REF]. The points are results of the AMP algorithm run till convergence averaged over 10 instances of size n = 10 4 . As expected we observe excellent agreement between the SE and AMP.

In both left and center panels of Fig. 1 we observe the so-called specialization phase transition. Indeed [START_REF] Donoho | Message-passing algorithms for compressed sensing[END_REF] has two types of xed points: A non-specialized xed point where every element of the K × K order parameter q is the same (so that both hidden neurons learn the same function) and a specialized xed point where the diagonal elements of the order parameter are di erent from the non-diagonal ones. We checked for other types of xed points for K = 2 (one where the two diagonal elements are not the same), but have not found any. In terms of weight-learning, this means for the non-specialized xed point that the estimators for both W 1 and W 2 are the same, whereas in the specialized xed point the estimators of the weights corresponding to the two hidden neurons are di erent, and that the network " gured out" that the data are better described by a non-linearly separable model. The specialized xed point is associated with lower error that the non-specialized one (as one can see in Fig. 1). The existence of this phase transition was discussed in statistical physics literature on the committee machine, see e.g. [START_REF] Schwarze | Generalization in a large committee machine[END_REF][START_REF] Saad | On-line learning in soft committee machines[END_REF].

For Gaussian weights (Fig. 1 left), the specialization phase transition arises continuously at α G spec (K = 2)

2.04. This means that for α < α G spec (K = 2) the number of samples is too small, and the neural network is not able to learn that two di erent teacher-vectors W 1 and W 2 were used to generate the observed labels. For α > α G spec (K = 2), however, it is able to distinguish the two di erent weight-vectors and the generalization error decreases fast to low values (see Fig. 1). For completeness we remind that in the case of K = 1 corresponding to single-layer neural network no such specialization transition exists. We show (see appendices sec. F) that it is absent also in multi-layer neural networks as long as the activations remain linear. The non-linearity of the activation function is therefore an essential ingredient in order to observe a specialization phase transition.

The center part of Fig. 1 depicts the xed point reached by the state evolution of AMP for the case of binary weights. We observe two phase transitions in the performance of AMP in this case: (a) the specialization phase transition at α B spec (K = 2) 1.58, and for slightly larger sample complexity a transition towards perfect generalization (beyond which the generalization error is asymptotically zero) at α B perf (K = 2) 1.99. The binary case with K = 2 di ers from the Gaussian one in the fact that perfect generalization is achievable at nite α. While the specialization transition is continuous here, the error has a discontinuity at the transition of perfect generalization. This discontinuity is associated with the 1st order phase transition (in the physics nomenclature), leading to a gap between algorithmic (AMP in our case) performance and information-theoretically optimal performance reachable by exponential algorithms. To quantify the optimal performance we need to evaluate the global optimizer of the replica free entropy (not the local optimizer reached by the state evolution). In doing so that we get that information theoretically there is a single discontinuous phase transition towards perfect generalization at α B IT (K = 2) 1.54. While the information-theoretic and specialization phase transitions were identi ed in the physics literature on the committee machine [START_REF] Schwarze | Generalization in a large committee machine[END_REF][START_REF] Schwarze | Generalization in fully connected committee machines[END_REF][START_REF] Seung | Statistical mechanics of learning from examples[END_REF][START_REF] Watkin | The statistical mechanics of learning a rule[END_REF], the gap between the information-theoretic performance and the performance of AMP -that is conjectured to be optimal among polynomial algorithms-was not yet discussed in the context of this model. Indeed, even its understanding in simpler models than those discussed here, such as the single layer case, is more recent [START_REF] Donoho | Message-passing algorithms for compressed sensing[END_REF][START_REF] Zdeborová | Statistical physics of inference: thresholds and algorithms[END_REF][START_REF] Donoho | Accurate prediction of phase transitions in compressed sensing via a connection to minimax denoising[END_REF].

More is di erent

It becomes more di cult to study the replica formula for larger values of K as it involves (at least) Kdimensional integrals. Quite interestingly, it is possible to work out the solution of the replica formula in the large K limit. It is indeed natural to look for solutions of the replica formula, as suggested in [START_REF] Schwarze | Learning a rule in a multilayer neural network[END_REF], of the form q = q d I K×K + (q a /K)1 K 1 K , with the unit vector 1 K = (1) K l=1 . Since both q and ρ are assumed to be Overlap q

AMP q 00 AMP q 01 SE q 00 SE q 01 SE ǫ g (α) AMP ǫ g (α)
Specialization Spinodal 1 st order transition Figure 1: Value of the order parameter and the optimal generalization error for a committee machine with two hidden neurons with Gaussian weights (left), binary/Rademacher weights (center), and for Gaussian weights in the large number of hidden units limit (right). These are shown as a function of the ratio α = m/n between the number of samples m and the dimensionality n. Lines are obtained from the state evolution equations (dominating solution is shown in full line), data-points from the AMP algorithm (see implementation and demo on github [START_REF] Aubin | AMP implementation of the committee machine[END_REF]) averaged over 10 instances of the problem of size n = 10 4 . q 00 and q 01 denote respectively diagonal and o -diagonal overlaps, and their value is to be read on the labels on the far-right of the gure.

positive, this scaling implies (see appendices sec. E) that 0 ≤ q d ≤ 1 and 0 ≤ q a + q d ≤ 1, as it should. We also detail the corresponding expansion for the teacher-student scenario with Gaussian weights. Only the information-theoretically reachable generalization error was computed [START_REF] Schwarze | Learning a rule in a multilayer neural network[END_REF], thus we concentrated on the analysis of performance of AMP by tracking the state evolution equations. In doing so, we unveil a large computational gap.

In the right plot of Fig. 1 we show the xed point values of the two overlaps q 00 = q d + q a /K and q 01 = q a /K and the resulting generalization error. As discussed in [START_REF] Schwarze | Learning a rule in a multilayer neural network[END_REF] it can be written in a closed form as g = π -1 arccos [2 (q a + arcsin q d ) /π]. The specialization transition arises for α = Θ(K) so we de ne α ≡ α/K. The specialization is now a rst order phase transition, meaning that the specialization xed point rst appears at α G spinodal 7.17 but the free entropy global extremizer remains the one of the non-specialized xed point until α G spec 7.65. This has interesting implications for the optimal generalization error that gets towards a plateau of value ε plateau 0.28 for α < α G spec and then jumps discontinuously down to reach a decay aymptotically as 1.25/ α.

AMP is conjectured to be optimal among all polynomial algorithms (in the considered limit) and thus analyzing its state evolution sheds light on possible computational-to-statistical gaps that come hand in hand with rst order phase transitions. In the regime of α = Θ(K) for large K the non-specialized xed point is always stable implying that AMP will not be able to give a lower generalization error than ε plateau . Analyzing the replica formula for large K in more details in sec. E.1 of the appendices, we concluded that AMP will not reach the optimal generalization for any α < Θ(K 2 ). This implies a rather sizable gap between the performance that can be reached information-theoretically and the one reachable tractably. Such large computational gaps have been previously identi ed in a range of inference problems -most famously in the planted clique problem [START_REF] Deshpande | Finding hidden cliques of size \sqrt {N/e} n/e in nearly linear time[END_REF]-but the committee machine is the rst model of a multi-layer neural network with realistic non-linearities (the parity machine is another example but use a very peculiar non-linearity) that presents such large gap.

Sketch of proof of Theorem 3.1

In order to avoid confusions we denote K-dimensional column vectors by underlined letters. In particular we set

W * i = (W * il ) K l=1 , w * i = (w * il ) K l=1 . For µ = 1, . . . m, let V µ , U * µ be K-dimensional vectors with i.i.d. N (0, 1) components. Let t ∈ [0, 1]
be an interpolation parameter. De ne the K-dimensional vector:

S t,µ ≡ 1 -t/n n i=1 X µi W * i + t 0 q(v)dv 1/2 V µ + t 0 (ρ -q(v))dv 1/2 U * µ ( 17
)
in which q(v) ∈ S ++ K (ρ) is a matrix valued interpolation path to be "adapted" later on. We will interpolate towards two auxiliary problems related to those discussed in sec. 3:

Y t,µ ∼ P out ( • | S t,µ ) , 1 ≤ µ ≤ m, Y t,i = √ tR 1/2 W * i + Z i , 1 ≤ i ≤ n, (18)
where Z i is (for each i) a K-vector with i.i.d. N (0, 1) components, and Y t,i is a K-vector as well. We recall that in our notation the * -variables have to be retrieved, while the other random variables are assumed to be known. De ne now s t,µ by the expression of S t,µ but with w i replacing W * i and u µ replacing U * µ (it thus depends on the full matrix w = (w il ) n,K i=1,l=1 ). For t ∈ [0, 1] we now introduce the interpolating posterior:

P t (w, u | Y, Y , X, V ) = 1 Z n (t) n i=1 P 0 (w i ) m µ=1 P out (Y t,µ | s t,µ ) n i=1 e -1 2 Y t,i - √ tR 1/2 w i 2 2 (19)
with Z n (t) the normalization factor equal to the numerator integrated over all components of w and u. The average free entropy at time t is by de nition

f n (t) ≡ 1 n E ln Z n (t). (20)
One easily veri es that

f n (0) = f n -K 2 , f n (1) = ψ P 0 (R) + m n Ψ Pout ( 1 0 q(t)dt; ρ) -1 2 Tr(Rρ) -K 2 . (21)
We will relate these two extreme values through the fundamental theorem of calculus

f n (0) = f n (1) - 1 0 df n (t) dt . ( 22
)
The next step is to compute the free entropy variation along the interpolation path (see appendices sec. A):

Proposition 5.1 (Free entropy variation). Denote byn,t the (Gibbs) expectation w.r.t. the interpolating posterior [START_REF] Schwarze | Learning a rule in a multilayer neural network[END_REF]. Set u y (x) ≡ln P out (y|x). For all t ∈ [0, 1]

df n (t) dt = - 1 2 E Tr 1 n m µ=1 ∇u Yt,µ (s t,µ )∇u Yt,µ (S t,µ ) -R Q -q(t) n,t (23)
+ 1 2 Tr(R(q(t) -ρ)) + o n (1) , ( 24
)
where ∇ is the K-dimensional gradient with respect to the argument of u Yt,µ (•), and

o n (1) → 0 in the n, m → ∞ limit uniformly in t ∈ [0, 1], Q ll ≡ n i=1 W * il w il /n is a K ×K overlap matrix .
A crucial step of the adaptive interpolation method is to show that the overlap matrix entries concentrate. In order to do this we must introduce a "small" perturbation of the interpolating problem by adding to the system a small K-dimensional Gaussian "side channel"

Y i = 1/2 W * i + Z i (25)
with ∈ S ++ K , Z i ∼ N (0, I K×K ). Note that 1/2 is a matrix square root. With this extra channel the posterior ( 19) must be multiplied by n i=1 exp(-Y i -1/2 w i 2 2 /2). The corresponding average free entropy and Gibbs expectation are denoted f n, andn,t, . An easy argument shows that

|f n, (t) -f n (t)| ≤ F S 2 K 2 (26)
for all t ∈ [0, 1], where S > 0 such that the support of P 0 is included in the sphere of radius S and M 2 F denotes the Frobenius norm. This small perturbation forces the overlap to concentrate around its mean (see appendices sec. A for more details):

Proposition 5.2 (Overlap concentration). There exists a sequence of matrices

S ++ K ( n ) n≥1 → (0) (the all-zeros matrix) s.t. lim n→∞ 1 0 dt E Q -E Q n,t, n 2 F n,t, n = 0 . ( 27
)
Note that since ( n ) n≥1 converges to (0), as claimed before f n, n (t) and f n (t) have the same limit (provided it exists). The adaptive choice of the interpolation path is based on the following:

Proposition 5.3 (Optimal interpolation path). For all R ∈ S + K the matrix di erential equation q(t) = E Q n,t, n admits a unique solution q (R) n (t) in S + K (ρ) and the mapping R ∈ S + K → 1 0 q (R) n (v)dv is continuous.
Proof: To prove this proposition one rst notes that E Q n,t, n is a matrix-valued function of (t, t 0 q(v)dv) ∈ R × S K . So we have to solve a rst order di erential equation in the nite dimensional vector space S K of K × K matrices. It is then not di cult to verify that E Q n,t, n is a bounded C 1 function of ( t 0 q(v)dv, R), and thus the proposition follows from a direct application of the parametric Cauchy-Lipschitz theorem. Since E Q n,t, n and ρ -E Q n,t, n are positive matrices (see appendices sec. A for the argument) we also have q(t) ∈ S + K (ρ) which ends the proof. Now de ne

f RS (q, R) ≡ ψ P 0 (R) + αΨ out (q; ρ) -Tr(Rq)/2 (28)
and call it the replica symmetric (RS) potential; this is nothing else than the function in the bracket appearing in the replica formula [START_REF] Baity-Jesi | Comparing dynamics: Deep neural networks versus glassy systems[END_REF]. Using the optimal interpolating function of Proposition 5.3 allows to relate this RS potential and free entropy f n . Indeed by Cauchy-Schwarz the square of the r.h.s. of ( 23) is bounded by

1 0 dt E 1 n m µ=1 ∇u Yt,µ (s t,µ )∇u Yt,µ (S t,µ ) -R 2 F n,t, n × 1 0 dt E Q -q (R) n (t) 2 F n,t, n .
We claim that this upper bound equals o n (1). Indeed: (a) the rst factor is bounded (independently of t) because we supposed that P out is generated by [START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF] with assumptions (H1), (H2), (H3) (see appendices sec. A for a proof) and; (b) the second factor goes to 0 when n, m → ∞ by an application of Proposition 5.2 and Proposition 5.3. Putting this result together with ( 21), [START_REF] Mato | Generalization properties of multilayered neural networks[END_REF] and Proposition 5.1 we arrive at:

Proposition 5.4 (Fundamental identity). Let (R n ) n≥1 ∈ (S + K ) N be a bounded sequence. For each n ∈ N, let q (Rn) n be the unique solution of the matrix di erential equation q(t) = E Q n,t, n . Then

f n = f RS 1 0 q (Rn) n (v)dv, R n + o n (1). ( 29
)
End of proof of Theorem 3.1: First, from the proposition 5.4 we trivially deduce the lower bound:

lim inf n→∞ f n ≥ sup R∈S + K inf q∈S + K (ρ) f RS (q, R). (30)
We now turn our attention to the upper bound. Let P = 2α ∇Ψ Pout (ρ; ρ) 2 I where I is the

K × K identity matrix. The mapping R ∈ S + K → 1 0 q (R) n (v)dv is continuous, consequently the map R → 2α∇Ψ Pout ( 1 0 q (R) n (t)dt; ρ) from S + K (P ) → S + K (P )
= 2α∇Ψ Pout ( 1 0 q (R * n ) n (t)dt; ρ). Proposition 5.4 then implies f n = f RS 1 0 q (R * n ) n (t)dt, R * n + o n (1). (31)
We now remark that

f RS 1 0 q (R * n ) n (t)dt, R * n = inf q∈S + K (ρ) f RS (q, R * n ). (32)
Indeed, the function g R * n : q ∈ S + K (ρ) → f RS (q, R * n ) ∈ R can be shown to be convex (appendices sec. A) and its q-derivative is ∇g

R * n (q) = α∇Ψ Pout (q) -R * n /2. Since ∇g R * n ( 1 0 q (R * n ) n
(t)dt) = 0 by de nition of R * n , and S + K (ρ) is convex and compact, the minimum of g R * n is necessarily achieved at

1 0 q (R * n ) n (t)dt. Therefore f n = inf q∈S + K (ρ) f RS (q, R * n ) + o n (1) ≤ sup R∈S + K inf q∈S + K (ρ) f RS (q, R) + o n (1) (33)
and thus

lim sup n→∞ f n ≤ sup R∈S + K inf q∈S + K (ρ) f RS (q, R) (34)
which concludes the proof when combined with the lower bound above.

Perspectives

In this paper we revisit a model of two-layers neural network known as the committee machine in the teacherstudent scenario that allows for explicit evaluation of the optimal learning errors. While this model has been discussed in early statistical physics literature using the non-rigorous replica method, we show here how these statements can be put on a mathematically rigorous basis, building on recent progress in proving the replica formulas.

Another contribution is the design of an approximate message passing algorithm (see [START_REF] Aubin | AMP implementation of the committee machine[END_REF] for a python implementation on GitHub) that e ciently achieves the Bayes-optimal learning error in the limit of large dimensions for a range of parameters out of the so-called hard phase that is associated with a rst order phase transition appearing in the model.

Finally, in the case of the committee machine with a large number of hidden neurons we identify a large hard phase in which learning is possible information-theoretically but not e ciently. Similar large computational gaps have been previously identi ed in many problems and we believe that its identi cation in a multi-layer neural network model makes it a very interesting candidate for further mathematical studies of the energy landscape in deep learning [START_REF] Sagun | Explorations on high dimensional landscapes[END_REF][START_REF] Baity-Jesi | Comparing dynamics: Deep neural networks versus glassy systems[END_REF]. Note that in other problems where such a hard phase was identi ed, its study boosted the development of algorithms that are able to match the predicted threshold. We anticipate this will also be the case for the present model.

In this paper we focused on a two-layers neural network, but we note that the analysis and algorithm can be readily extended to a multi-layer setting, see [START_REF] Mato | Generalization properties of multilayered neural networks[END_REF], as long as the total number of hidden neurons stays of order one while the dimension of the data and the number of samples both grow at the same rate.

There are many possible extensions of the present work, which we hope will motivate revisiting the statistical physics approach to learning neural networks. An important open case, for instance, is the one where the number of samples per dimension α = Θ(1) and also the size of the hidden layer per dimension K/n = Θ(1) as n → ∞, while in this paper we treated the case α = Θ(1), K/n → 0 as n → ∞. This other scaling where K/n = Θ(1) is challenging even for the non-rigorous replica method.

A Proof details for Theorem 3.1

We rst state an important property of the Bayesian optimal setting (that is when all hyper-parameters of the problem are assumed to be known), that is used several times, and is often refered to as the Nishimori identity.

Proposition A.1 (Nishimori identity). Let (X, Y ) ∈ R n 1 × R n 2 be
a couple of random variables. Let k ≥ 1 and let X (1) , . . . , X (k) be k i.i.d. samples (given Y ) from the conditional distribution P (X = • |Y ), independently of every other random variables. Let us denotethe expectation operator w.r.t. P (X = • |Y ) and E the expectation w.r.t. (X, Y ). Then, for all continuous bounded function g we have E g(Y, X (1) , . . . , X (k) ) = E g(Y, X (1) , . . . , X (k-1) , X) .

(

) 35
Proof: This is a simple consequence of Bayes formula. It is equivalent to sample the couple (X, Y ) according to its joint distribution or to sample rst Y according to its marginal distribution and then to sample X conditionally to Y from its conditional distribution P (X = • |Y ). Thus the (k + 1)-tuple (Y, X (1) , . . . , X (k) ) is equal in law to (Y, X (1) , . . . , X (k-1) , X). This proves the proposition.

As a rst application of Proposition A.1 we prove the following Lemma which is used in the proof of Proposition 5.3.

Lemma A.2. The matrices ρ, E Q and ρ -E Q are positive de nite, i.e. in S + K . In the application the Gibbs bracket isn,t, .

Proof: The statement for ρ follows from its de nition (in Theorem 3.1). Note for further use that we also have ρ

= 1 n E[W * i (W * i ) ]. Since by de nition Q ll ≡ 1 n n i=1 W * il w il in matrix notation we have Q = 1 n n i=1 W * i w i .
An application of the Nishimori identity shows that

E Q = 1 n n i=1 E W * i w i = 1 n n i=1 E w i w i (36)
which is obviously in S + K . Finally we note that

E(ρ -Q ) = 1 n n i=1 E[W * i (W * i ) ] -E w i w i = 1 n n i=1 E[(W * i -w i )((W * i ) -w i )] (37)
where the last equality is proved by an application of the Nishimori identity again. This last expression is obviously in S + K .

We set up some notations which will shortly be useful. Let u y (x) ≡ln P out (y|x). Here x ∈ R K and y ∈ R. We will denote by ∇u y (x) the K-dimensional gradient w.r.t. x, and ∇∇ u y (x) the K × K matrix of second derivatives (the Hessian) w.r.t. x. Moreover ∇P out (y|x) and ∇∇ P out (y|x) also denote the K dimensional gradient and Hessian w.r.t. x. We will also use the matrix identity

∇∇ u Yµ (x) + ∇u Yµ (x)∇ u Yµ (x) = ∇∇ P out (Y µ |x) P out (Y µ |x) . ( 38
)
Finaly we will use the matrices

w ∈ R n×K , u ∈ R m×K , Y ∈ R m , Y ∈ R n×K , X ∈ R m×n , V ∈ R m×K ,
W * ∈ R n×K and U * ∈ R m×K . Like in sec. 5 we adopt the convention that all underlined vectors are K dimensional. For example u µ , U µ , V µ , Y i are all K-dimensional.

It is convenient to reformulate the expression of the interpolating free entropy f n (t) in the Hamiltonian language. We introduce an interpolating Hamiltonian:

H t (w, u; Y t , Y t , X, V ) ≡ - m µ=1 u Yt,µ (s t,µ ) + 1 2 n i=1 Y i - √ tR 1/2 w i 2 2 . ( 39
)
The average free entropy at time t reads

f n (t) ≡ 1 n E ln R n×K dP 0 (w) R m×K Du e -Ht(w,u;Yt,Y t ,X,V ) (40)
where

Du = m µ=1 K l=1 (2π) -1/2 e - u 2 µl
2 and dP 0 (w) = n i=1 P 0 (w i ) K l=1 dw il . To develop the calculations in the simplest manner it is fruitful to represent the expectations over W * , U, Y, Y explicitly as integrals:

f n (t) = 1 n E X,V dY t dY t dP 0 (W * )DU * e -Ht(W * ,U ;Yt,Y t ,X,V )
× ln dP 0 (w)Du e -Ht(w,u;Yt,Y t ,X,V ) .

We begin with the proof of Proposition 5.1 which we recall for the convenience of the reader.

Proposition A.3 (Free entropy variation). Denote byn,t the (Gibbs) expectation w.r.t. the interpolating posterior in sec. 5. Set u y (x) ≡ln P out (y|x). For all t ∈ [0, 1]

df n (t) dt = - 1 2 E Tr 1 n m µ=1 ∇u Yt,µ (s t,µ )∇u Yt,µ (S t,µ ) -R Q -q(t) n,t + 1 2 Tr(R(q(t) -ρ)) + o n (1) , ( 42
)
where ∇ is the K-dimensional gradient with respect to the argument of u Yt,µ (•), and o n (1) → 0 in the n, m → ∞ limit uniformly in t ∈ [0, 1], and the

K × K overlap matrix Q ll ≡ 1 n n i=1 W * il w il .
Proof: We drop the t index for the measurements Y t , Y t as they are dummy variables. We will rst prove that for all t ∈ (0, 1)

df n (t) dt = - 1 2 E Tr 1 n m µ=1 ∇u Yµ (s t,µ )∇u Yµ (S t,µ ) -R 1 n n i=1 W * i w i -q(t) t + Tr R(q(t) -ρ) 2 - A n 2 , ( 43
)
where

A n = E Tr 1 √ n m µ=1 ∇∇ P out (Y µ |S t,µ ) P out (Y µ |S t,µ ) 1 √ n n i=1 (W * i (W * i ) -ρ) 1 n ln Z n (t) . ( 44
)
Once this is done, we show that A n goes to 0 as n → ∞ uniformly in t ∈ [0, 1] in order to conclude the proof.

The Hamiltonian t-derivative is given by

d dt H t (W * , U * ; Y, Y , X, V ) = - m µ=1 ∇ u Yµ (S t,µ ) dS t,µ dt - 1 2 1 √ t n i=1 (R 1/2 W * i ) (Y i - √ tR 1/2 W * i ) = - m µ=1 Tr dS t,µ dt ∇ u Yµ (S t,µ )] - 1 2 1 √ t n i=1 Tr R 1/2 (Y i - √ tR 1/2 W * i )W * T i (45)
(where we used that R is symmetric). The derivative of the interpolating free entropy thus reads, for 0 < t < 1,

df n (t) dt = - 1 n E d dt H t (W * , U * ; Y, Y , X, V ) ln Z n (t) T 1 - 1 n E H t (w, u; Y, Y , X, V ) t T 2 . ( 46
)
First, we note that T 2 = 0. This is a direct consequence of the Nishimori identity Proposition A.1:

T 2 = 1 n E d dt H t (w, u; Y, Y , X, V ) t = 1 n E d dt H t (W * , U * ; Y, Y , X, V ) = 0 . (47)
We now compute T 1 . This involves matrix derivatives which have to be done carefully. We rst note that the matrix 1 0 q(s)ds ∈ S ++ K and therefore (

1 0 q(s)ds) 1/2 , ( 1 0 q
(s)ds) -1/2 are well de ned. Then,

E Tr dS t,µ dt ∇ u Yµ (S t,µ ) ln Z n (t) = 1 2 E Tr - n i=1 X µi W * i n(1 -t) + d dt t 0 q(s)ds 1/2 V µ + d dt t 0 (ρ -q(s))ds 1/2 U * µ ∇ u Yµ (S t,µ ) ln Z n (t) . ( 48
)
We then compute the rst line of the right-hand side of (48). By Gaussian integration by parts w.r.t. X µi (recall hypothesis (H3)), and using the identity [START_REF] Baldassi | E cient supervised learning in networks with binary synapses[END_REF], we nd after some algebra

1 n(1 -t) E Tr n i=1 X µi W * i ∇ u Yµ (S t,µ ) ln Z n (t) = E Tr 1 n n i=1 W * i W i ∇∇ P out (Y µ |S t,µ ) P out (Y µ |S t,µ ) ln Z n (t) + E Tr 1 n n i=1 W * i w i ∇u Yµ (S t,µ )∇ u Yµ (s t,µ ) t . ( 49
)
Similarly for the second line of the right hand side of (48), we use again Gaussian integrations by parts but this time w.r.t. V µ , U * µ which have i.i.d. N (0, 1) entries. This calculation has to be done carefully with the help of the matrix identity

d dt M (t) = (M (t)) 1/2 d(M (t)) 1/2 dt + d(M (t)) 1/2 dt (M (t)) 1/2 (50)
for any M (t) ∈ S + K , and the cyclicity and linearity of the trace. Applying (50) to M (t) equal to t 0 q(s)ds and t 0 (ρq(s))ds, as well as the identity [START_REF] Baldassi | E cient supervised learning in networks with binary synapses[END_REF], we reach after some algebra

E Tr d dt t 0 q(s)ds 1/2 V µ + d dt t 0 (ρ -q(s))ds 1/2 U * µ ∇ u Yµ (S µ,t ) ln Z n (t) = E Tr ρ ∇∇ P out (Y µ |S µ,t ) P out (Y µ |S µ,t ) ln Z n (t) + E Tr q(t)∇u Yµ (S µ,t )∇ u Yµ (s µ,t ) t . (51)
As seen from ( 45), ( 46) it remains to compute

E[Tr[R 1/2 (Y i - √ tR 1/2 W * i )W * T i ] ln Z n (t)]. Recall that Y i - √ tR 1/2 W * i = Z i ∼ N (0, 1)
. Using an integration by parts leads to

E Tr R 1/2 (Y i - √ tR 1/2 W * T i ) ln Z n (t) = - √ tTr R 1/2 ρ -E W * j w j t . (52)
Finaly the term T 1 is obtained by putting together (48), ( 49), ( 51) and ( 52).

It now remains to check that A n → 0 as n → +∞ uniformly in t ∈ [0, 1]. The proof from [START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF] (Appendix C.2) can easily be adapted so we give here just a few indications for the ease of the reader. First one notices that

E ∇∇ P out (Y µ |S t,µ ) P out (Y µ |S t,µ ) W * , {S t,µ } m µ=1 = dY µ ∇∇ P out (Y µ |S t,µ ) = 0 , (53)
so that by the tower property of the conditional expectation one gets

E Tr 1 √ n m µ=1 ∇∇ P out (Y µ |S t,µ ) P out (Y µ |S t,µ ) 1 √ n n i=1 (W * i (W * i ) -ρ) = 0 (54)
Next, one shows by standard second moment methods that

E[(n -1 ln Z n (t) -f n (t)) 2 ] → 0 as n → +∞ uniformly in t ∈ [0, 1].
Then, using this last fact together with (54), under hypothesis (H1), (H2), (H3) an easy application of the Cauchy-Schwarz inequality implies A n → 0 as n → +∞ uniformly in t ∈ [0, 1]. This ends the proof of formula [START_REF] Barbier | Mutual information and optimality of approximate message-passing in random linear estimation[END_REF] for the free entropy variation.

We now turn to the proof of Proposition 5.2 which we restate here:

Proposition A.4 (Overlap concentration). There exists a sequence of K × K matrices ( n ) n≥1 ∈ S ++ K that converges to the all-zeros matrix (0) such that

lim n→∞ 1 0 dt E Q -E Q n,t, n 2 F n,t, n = 0 . ( 55
)
Proof: Recall the perturbation (or side information channel) added to the posterior. We take a K × K matrix ∈ S ++ K and denote the matrix elements by ll . Recall that we add a K-dimensional Gaussian side channel Y i = 1/2 W * i + Z i with i.i.d. Z il ∼ N (0, 1) (here i = 1, . . . , n and l = 1, . . . , K). Note that here 1/2 is the matrix square root of . This multiplies the posterior by a term

n i=1 e -1 2 Y i -1/2 w i 2 2
(56) or equivalently adds to the Hamiltonian (39) a term (we remark that since and 1/2 are symmetric we have

w i W * i = (W * i ) w i and w i 1/2 Z i = Z i 1/2 w i ) H pert ≡ n i=1 1 2 w i w i -w i W * i -w i 1/2 Z i . (57)
In [START_REF] Barbier | The adaptive interpolation method: A simple scheme to prove replica formulas in bayesian inference[END_REF][START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF] we show how to prove concentration for the case of a scalar side channel and the proof is generic as long as the side channel is added to a generic Hamiltonian (here [START_REF] Aubin | AMP implementation of the committee machine[END_REF]) which comes from a Bayes-optimal inference problem and thus satis es the Nishimori identities in Proposition A.1. The proof here is conceptually similar, except that one has to look at the e ect of the perturbation in all "directions", i.e., with respect to each separate variation of the matrix elements ll = l l . In particular the derivative of the added Hamiltonian with respect to one matrix element, that must remain symmetric, then reads

d d ll H pert ≡ nL ll = 1 2 n i=1 w il w il -w il W * il -w il W * il -2w i d 1/2 d ll Z i . (58)
After some lenghty algebra (similar to [START_REF] Barbier | The adaptive interpolation method: A simple scheme to prove replica formulas in bayesian inference[END_REF], see sec. B of the appendices for the details) using Gaussian integration by parts and the Nishimori identity one obtains the following uctuation identity:

E (L ll -E L ll n,t, n ) 2 n,t, n + C E (L l l -L l l n,t, n ) 2 n,t, n E (L ll -L ll n,t, n ) 2 n,t, n 1/4 ≥ 1 4 E (Q ll -E Q ll n,t, n ) 2 n,t, n + O(K 3 /n) (59)
Therefore, in order to control the overlap uctuations one needs to control those of L ll . Fortunately this can be done. The proof found in [START_REF] Barbier | The adaptive interpolation method: A simple scheme to prove replica formulas in bayesian inference[END_REF] of the following lemma applies verbatim (to all elements L ll independently):

Lemma A.5 (Concentration of L ll ). There exists a sequence of K × K matrices ( n ) n≥1 ∈ S ++ K that converges to the all-zeros matrix (0) such that for all l, l ∈ {1, . . . , K}

lim n→∞ 1 0 dt E (L ll -E L ll n,t, n ) 2 n,t, n = 0. ( 60
)
As a consequence the following statement is also true under the same conditions:

lim n→∞ 1 0 dt E (L ll -L ll n,t, n ) 2 n,t, n = 0. ( 61
)
The concentration of Q ll then follows from the one of L ll as we explain now. From (59) combined with Cauchy-Schwarz we have for some constant C > 0

1 0 dt E (Q ll -E Q ll n,t, n ) 2 n,t, n ≤ 4 1 0 dt E (L ll -E L ll n,t, n ) 2 n,t, n + C 1 0 dt E (L l l -L l l ) 2 1 0 dt E (L ll -L ll ) 2 1/4 + O(K 3 /n). (62)
Taking the limit n → +∞ of this inequality, applying Lemma A.5 and then summing the resulting K 2 = O(1) uctuations, we obtain the claimed result (55).

Lemma A.6 (Boundedness of an overlap uctuation). Under hypothesis (H2) one can nd a constant C(ϕ, K, ∆) < +∞ (independent of n, t, n ) such that for any R n ∈ S + K we have

E 1 n m µ=1 ∇u Yt,µ (s t,µ )∇u Yt,µ (S t,µ ) -R n 2 F n,t, n ≤ 2Tr(R 2 n ) + α 2 C(ϕ, K, ∆). ( 63
)
We note that the constant remains bounded as ∆ → 0 and diverges as K → +∞.

Proof: It is easy to see that for symmetric matrices A, B we have

Tr(A-B) 2 ≤ 2(TrA 2 +TrB 2 ). Therefore E 1 n m µ=1 ∇u Yt,µ (s t,µ )∇u Yt,µ (S t,µ ) -R n 2 F n,t, n ≤ 2Tr(R 2 n ) + 2E Tr 1 n m µ=1 ∇u Yt,µ (s t,µ )∇u Yt,µ (S t,µ ) 2 n,t, n . (64)
In the rest of the argument we bound the second term of the r.h.s. Using the triangle inequality and then Cauchy-Schwarz we obtain

E 1 n m µ=1 ∇u Yt,µ (s t,µ )∇u Yt,µ (S t,µ ) 2 F n,t, n ≤ E 1 n 2 m µ=1 ∇u Yt,µ (s t,µ )∇u Yt,µ (S t,µ ) F 2 n,t, n ≤ E 1 n 2 m µ=1 ∇u Yt,µ (s t,µ ) 2 ∇u Yt,µ (S t,µ ) 2 2 n,t, n . (65)
From the random representation of the transition kernel,

u Yt,µ (s) = ln P out (Y t,µ |x) = ln dP A (a µ ) 1 √ 2π∆ e -1 2∆ (Yt,µ-ϕ(x,aµ)) 2 (66)
and thus

∇u Yt,µ (x) = dP A (a µ )(Y t,µ -ϕ(x, a µ ))∇ϕ(x, a µ )e -1 2∆ (Yt,µ-ϕ(x,aµ)) 2 dP A (a µ )e -1 2∆ (Yt,µ-ϕ(x,aµ)) 2 (67)
where ∇ϕ is the K-dimensional gradient w.r.t. the rst argument x ∈ R K . From the observation model we get

|Y t,µ | ≤ sup |ϕ| + √ ∆|Z µ |
, where the supremum is taken over both arguments of ϕ, and thus we immediately obtain for all s

∈ R K ∇u Yt,µ (x) ≤ (2 sup |ϕ| + √ ∆|Z µ |) sup ∇ϕ . (68)
From ( 68) and (65) we see that it su ces to check that

m 2 n 2 E (2 sup |ϕ| + |Z µ |) 2 (sup ∇ϕ ) 2 2 ≤ C(ϕ, K, ∆)
where C(ϕ, K, ∆) < +∞ is a nite constant depending only on ϕ, K, and ∆. This is easily seen by expanding all squares and using that m/n → α. This ends the proof of Lemma A.6.

Lemma A.7 (Convexity of Ψ Pout ). Recall that Ψ Pout is de ned as the free entropy of the second auxiliary channel [START_REF] Engel | Statistical Mechanics of Learning[END_REF]. More precisely, for q ∈ S + K (ρ), we have:

Ψ Pout (q) ≡ E ln R K dw (2π) K/2 e -1 2 w w P out Y 0 |q 1/2 V + (ρ -q) 1/2 w .
Then Ψ Pout is continuous and convex on S + K (ρ), and twice di erentiable inside S + K (ρ)

Proof: The continuity and di erentiability of Ψ Pout is easy, and exactly similar to the rst part of the proof of Proposition 11 of [START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF]. One can compute the gradient and Hessian matrix of Ψ Pout (q), for q inside S + K (ρ), using Gaussian integration by parts and the Nishimori identity. The calculation is tedious and essentially follows the steps of Proposition 11 of [START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF]. Recall that u Y (x) ≡ ln P out (y|x). We de ne the averagesc as g(w) sc ≡ R K DwP out (ρq) 1/2 w + q 1/2 V g(w)

R K DwP out (ρ -q) 1/2 w + q 1/2 V , (69)
for any continuous bounded function g. One arrives at:

∇Ψ Pout (q) = 1 2 E ∇u Y (ρ -q) 1/2 W * + q 1/2 V ∇u Y (ρ -q) 1/2 w + q 1/2 V sc . (70)
Note that this gradient is actually a matrix of size K × K, as it is a gradient w.r.t. q ∈ R K×K . The Hessian of Ψ Pout w.r.t. q is thus a 4-tensor. One can compute in the same way:

∇ 2 Ψ Pout (q) = 1 2 E ∇ 2 P out (ρ -q) 1/2 w + q 1/2 V P out (ρ -q) 1/2 w + q 1/2 V sc (71) -∇u Y (ρ -q) 1/2 W * + q 1/2 V ∇u Y (ρ -q) 1/2 w + q 1/2 V sc ⊗2 .
In this expression, ⊗2 means the "tensorized square" of a matrix, i.e. for any matrix M of size

K × K, M ⊗2 is a 4-tensor with indices M ⊗2 l 0 l 1 l 2 l 3 = M l 0 l 1 M l 2 l 3 .
From this expression, it is clear that the Hessian of Ψ Pout is always positive, when seen as a matrix with rows and columns in R K×K , and thus Ψ Pout is convex, which ends the proof of Lemma A.7.

B A uctuation identity

In this section we drop the indices in the Gibbs bracket that will simply be written asas these do not play any role in the following analysis. We will relate the uctuations of the object (58) that appears naturally in the problem and for which we can control its uctuation that we recall here,

L ll = 1 2n n i=1 w il w il -w il W * il -w il W * il -2w i d 1/2 d ll Z i ( 72
)
to those of each matrix element of the overlap matrix Q ll = 1 n n i=1 W * il w il , namely we will prove the general uctuation identity:

E (L ll -E L ll ) 2 = E (L l l -E L l l ) 2 = 1 2 E Q ll Q l l -E[ Q ll Q l l ] + 1 4 E Q 2 ll -E[ Q ll ] 2 + O(K 3 /n) = 1 2 E Q ll Q l l -E[ Q ll Q l l ] + 1 4 E Q 2 l l -E[ Q l l ] 2 + O(K 3 /n). ( 73
)
Identity (73) follows from summing the two following identities that we prove next:

E[ L 2 ll ] -E[ L ll 2 ] = 1 4 E Q 2 ll -Q ll + Q l l 2 + Q ll Q l l + 2 n 2 n i,j=1 w il w il w jl w jl + O(K 2 /n), (74)
E[ L ll 2 ] -E[ L ll ] 2 = 1 4 E Q l l 2 + Q ll 2 + Q ll Q l l - 2 n 2 n i,j=1
w il w il w jl w jl

- 1 4 E[ Q l l ] 2 + O(K 3 /n), (75)
From ( 73) we nally derive (59) that we recall here:

E (L ll -E L ll ) 2 + C E (L l l -L l l ) 2 E (L ll -L ll ) 2 1/4 ≥ 1 4 E (Q ll -E Q ll ) 2 + O(K 3 /n) = 1 4 E (Q l l -E Q l l ) 2 + O(K 3 /n) (76)
by showing in the last section of this appendix that for some constant C > 0,

E (Q ll -Q ll ) 2 ≤ C E (L l l -L l l ) 2 1/2 (77)
and similarly for Q l l , which direclty implies by Cauchy-Schwarz that

E Q ll Q l l -E[ Q ll Q l l ] = E (Q ll -Q ll )(Q l l -Q l l ) ≤ E (Q ll -Q ll ) 2 E (Q l l -Q l l ) 2 1/2 ≤ C E (L l l -L l l ) 2 E (L ll -L ll ) 2 1/4 . ( 78
)
The derivation of all these identities is lenghty but do not present any technical di culty, and is a generalization of the proof of the uctuation identity in [START_REF] Barbier | The adaptive interpolation method: A simple scheme to prove replica formulas in bayesian inference[END_REF] which is for the scalar case K = 1.

B.1 Preliminaries

We start with some preliminary computations that will be useful in the derivation of the two above identities. First we compute

E[ L ll ] = E 1 2n n i=1 w il w il -w il W * il -w il W * il -2w i d 1/2 d ll Z i N = E 1 n n i=1 1 2 w il w il -w il w il -w i d 1/2 d ll Z i , (79)
where here we used the Nishimori Proposition A.1 which in this case reads

E[ w il W * il ] = E[ w il w il ]
. Each time we use an identity that is a consequence of Proposition A.1 we write a N on top of the equality (that stands for "Nishimori"). In order to simplify this expression, we show a Gaussian integration by part mechanism that we will use repedately. We want to integrate by part the Gaussian noise in a term of the form (introducing a multiplicative A = A(w i ) term, that does not depend explicitely on the noise, in order to obtain a more general identity that will be useful later on)

E Aw i d 1/2 d ll Z i = K k,k =1 E Aw ik d 1/2 d ll kk Z ik = K k,k =1 E d Aw ik d Z ik d 1/2 d ll kk = K k,k =1 E Aw ik ( 1/2 w i ) k -Aw ik ( 1/2 w i ) k d 1/2 d ll kk = E Aw i d 1/2 d ll 1/2 w i -Aw i d 1/2 d ll 1/2 w i , (80)
where we used the Gaussian integration by part formula (or Stein lemma)

E[Zf (Z)] = E[f (Z)] for Z ∼ N (0, 1)
, together with the fact that the derivative of the perturbing Hamiltonian is

dH pert d Z ik = -( 1/2 w i ) k , and thus d • d Z ik = • ( 1/2 w i ) k -• ( 1/2 w i ) k . ( 81
)
Now we can write in general (we use w

A (a) (w (b) i ) d 1/2 d ll 1/2 w (c) i = 1 2 A (a) (w (b) i ) d 1/2 d ll 1/2 + 1/2 d 1/2 d ll w (c) i = 1 2 A (a) (w (b) i ) d d ll w (c) i = 1 2 A (a) w (b) il w (c) il = 1 2 A (a) w (b) il w (c) il (82)
where we used the following formula

1/2 d 1/2 d ll + d 1/2 d ll 1/2 = d d ll (83)
and that the matrices are symmetric and thus

d d ll = d d l l
. Thus (80) becomes

E Aw i d 1/2 d ll Z i = 1 2 Aw il w il -Aw il w il = 1 2 Aw il w il -Aw il w il . ( 84
)
Using this (79) becomes

E[ L ll ] = - 1 2n n i=1 E w il w il N = - 1 2n n i=1 E W * il w il = - 1 2 E Q ll = - 1 2 E Q l l . ( 85
)
We will need a further generalization of (84), where now the integration by part is done over three distinct terms (here A, B do not explicitely depend on the noise, only the Gibbs brackets A , B do):

E A B w i d 1/2 d ll Z i = K k,k =1 E A B d w ik d Z ik d 1/2 d ll kk + w ik d A d Z ik B d 1/2 d ll kk + w ik A d B d Z ik d 1/2 d ll kk (81) = K k,k =1 E A B w ik ( 1/2 w i ) k -w ik ( 1/2 w i ) k d 1/2 d ll kk + w ik B A( 1/2 w i ) k -A ( 1/2 w i ) k d 1/2 d ll kk + w ik A B( 1/2 w i ) k -B ( 1/2 w i ) k d 1/2 d ll kk . ( 86
)
Thus, using (82) with A (a) → A (a) B (a ) we obtain after simpli cation

E A B w i d 1/2 d ll Z i = 1 2 E A B w il w il -3 A B w il w il + w il B Aw il + w il A Bw il (87)
and in particular

E A w i d 1/2 d ll Z i = 1 2 E A w il w il -2 A w il w il + w il Aw il . (88)
A last required formula of the same type, derived similarly, is

E A Bw i d 1/2 d ll Z i = 1 2 E A Bw il w il -2 A Bw il w il + Bw il Aw il . ( 89
)
Finally we will need the following overlap identities:

1 n 2 n i,j=1 E w il w jl w ik w jk N = E 1 n n i=1 W * il w ik 1 n n j=1 W * jl w jk = E[ Q lk Q l k ] = E[ Q kl Q k l ], (90) 1 n 2 n i,j=1 E w il w jl w ik w jk N = E 1 n n i=1 W * ik w il 1 n n j=1 W * jk w jl = E[ Q kl Q k l ]. (91)

B.2 Derivation of (74)

We start with the rst identity, namely the "thermal" uctuations. Recall (58). Acting with n -1 d/d ll on both sides of (85) we thus obtain

-E[ L 2 ll -L ll 2 ] + 1 n E dL ll d ll = 1 2n n i=1 E W * il w il L ll -w il L ll . ( 92
)
Computing the derivative of L ll and using -2

(d 1/2 /d ll ) 2 = 1/2 (d 2 1/2 /d 2 ll ) + (d 2 1/2 /d 2 ll ) 1/2 which follows from (83) we nd 1 n E dL ll d ll = 1 n 2 n i=1 E w i d 1/2 d ll 2 w i -w i d 1/2 d ll 2 w i = O(K 2 /n). ( 93
)
Let us compute the term in ( 92):

E W * il w il L ll -w il L ll = 1 n n j=1 E 1 2 W * il w il w jl w jl - 1 2 W * il W * jl w il w jl - 1 2 W * il W * jl w il w jl -W * il w il w j d 1/2 d ll Z j - 1 2 W * il w il w jl w jl + 1 2 W * il W * jl w il w jl + 1 2 W * il W * jl w il w jl + W * il w il w j d 1/2 d ll Z j . ( 94
)
Let us integrate by parts the two terms involving the explicit noise dependence (it is important that this is done before employing the Nishimori identity):

-E W * il w il w j d 1/2 d ll Z j (84) = - 1 2 E W * il w il w jl w jl -W * il w il w jl w jl , (95)
E W * il w il w j d 1/2 d ll Z j (88) = 1 2 E W * il w il w jl w jl -2W * il w il w jl w jl + W * il w il w jl w jl . (96)
Plugging these results in (94), (92) becomes

-E[ L 2 ll -L ll 2 ] = 1 4n 2 n i,j=1 E W * il w il w jl w jl -W * il W * jl w il w jl -W * il W * jl w il w jl -W * il w il w jl w jl -W * il w il w jl w jl -W * il w il w jl w jl + W * il W * jl w il w jl + W * il W * jl w il w jl + W * il w il w jl w jl -2W * il w il w jl w jl + W * il w il w jl w jl } + O(K 2 /n) N = 1 4n 2 n i,j=1
E w il w il w jl w jlw il w jl w il w jlw il w jl w il w jlw il w il w jl w jl + w il w il w jl w jlw il w il w jl w jl + w il w jl w il w jl + w il w jl w il w jl

+ w il w il w jl w jl -2 w il w il w jl w jl + w il w il w jl w jl + O(K 2 /n) = 1 4n 2 n i,j=1
Ew il w jl w il w jlw il w jl w il w jl + 2 w il w jl w il w jl

+ w il w jl w il w jl + w il w jl w il w jl -2 w il w il w jl w jl + O(K 2 /n) = - 1 4n 2 n i,j=1 E w il w jl -w il w jl w il w jl -w il w jl + w il w jl -w il w jl w il w jl -w il w jl + O(K 2 /n) (97)
which is (74) once expressed with the overlaps (90), (91).

B.3 Derivation of (75)

Let us now compute the following term:

E[ L ll 2 ] = 1 4n 2 n i,j=1 E w il w il w jl w jl + w il w jl W * il W * jl + w il w jl W * il W * jl -2 w il w il w jl W * jl -2 w il w il w jl W * jl + 2 w il w jl W * il W * jl + 4 w i d 1/2 d ll Z i w j d 1/2 d ll Z j -4 w jl w jl w i d 1/2 d ll Z i + 4 w jl W * jl w i d 1/2 d ll Z i + 4 w jl W * jl w i d 1/2 d ll Z i . (98)
Now we need to integrate by parts all the noise dependent terms (again, it is necessary that this operation is done before using the Nishimori identity):

-4E w jl w jl w i d 1/2 d ll Z i (88) = -2E w jl w jl w il w il -2 w jl w jl w il w il + w il w jl w jl w il , (99)
4E w jl W * jl w i d 1/2 d ll Z i (88) = 2E W * jl w jl w il w il -2W * jl w jl w il w il + W * jl w il w jl w il , (100)
4E w jl W * jl w i d 1/2 d ll Z i (88) = 2E W * jl w jl w il w il -2W * jl w jl w il w il + W * jl w il w jl w il . (101)
We now tackle the more painful term:

4E w i d 1/2 d ll Z i w j d 1/2 d ll Z j (88) = 2E w j d 1/2 d ll Z j w il w il -2 w il w il + w il w j d 1/2 d ll Z j w il + 2 K k,k =1 K u=1 w ik d 1/2 d ll kk w ju d 1/2 d ll uk δ ji (102)
where the last term comes from the contribution when the two noise variables are equal (i.e. the contribution corresponding to the potential explicit dependence of A in the noise Z i in (88)). Note that this last term (the term with a δ ji ) is O(K 3 /n). Now we again integrate by part w.r.t. the second noise variable the r.h.s. of this last identity term after term:

2E w j d 1/2 d ll Z j w il w il (88)
= E w il w il w jl w jl -2 w il w il w jl w jl + w jl w il w il w jl ,

-4E w j d 1/2 d ll Z j w il w il (103)
= -2E w il w il w jl w jl -3 w il w il w jl w jl + w jl w il w il w jl

+ w jl w il w il w jl , (104)
2E w il w j d 1/2 d ll Z j w il (89)
= E w il w il w jl w jl -2 w il w il w jl w jl + w il w jl w il w jl .

We are now ready to combine all terms in (98). Using the Nishimori identity it yields

E[ L ll 2 ] N = 1 4n 2 n i,j=1
E w il w il w jl w jl + w il w jl w il w jl + w il w jl w il w jl -2 w il w il w jl w jl -2 w il w il w jl w jl + 2 w il w jl w il w jl -2 w jl w jl w il w il -2 w jl w jl w il w il + w il w jl w jl w il + 2 w jl w jl w il w il -2 w jl w jl w il w il + w jl w il w jl w il + 2 w jl w jl w il w il -2 w jl w jl w il w il + w jl w il w jl w il

+       
w il w il w jl w jl -2 w il w il w jl w jl + w jl w il w il w jl -2 w il w il w jl w jl -3 w il w il w jl w jl + w jl w il w il w jl + w jl w il w il w jl w il w il w jl w jl -2 w il w il w jl w jl + w il w jl w il w jl

+ O(K 3 /n) = 1 4n 2 n i,j=1
E w il w jl w il w jl + w il w jl w il w jl

+ w il w jl w il w jl -2 w il w il w jl w jl + O(K 3 /n) = 1 4 E Q l l 2 + Q ll 2 + Q ll Q l l - 2 n 2 n i,j=1 w il w il w jl w jl + O(K 3 /n) (106)
using (90), (91) for the last identity. Combining this with (85) (once squarred) we nally obtain (75).

B.4 Derivation of (77)

First note from (90), (91) that the "thermal uctuation" of the overlaps can be written as

E (Q ll -Q ll ) 2 = E Q 2 ll -E[ Q ll 2 ] = E 1 n 2 n i,j=1
w il w jl w il w jlw il w jl

≤ E 1 n 2 n i,j=1
w il w jl

2 1/2 E 1 n 2 n i,j=1
w il w jlw il w jl

2 1/2 (107)
using Cauchy-Schwarz. Note that the rst term of the r.h.s. of this last identity is bounded. Now the formula (97) for the special case l = l yields

E (L l l -L l l ) 2 = E 1 2n 2 n i,j=1 w il w jl -w il w jl 2 + O(K 2 /n). (108)
Thus we obtain (77).

C Replica calculation

Our goal here is to provide an heuristic derivation of the replica formula of Theorem 3.1 using the replica method, a powerful non-rigorous tool from statistical physics of disordered systems [START_REF] Mézard | Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications[END_REF][START_REF] Mézard | Information, physics, and computation[END_REF]. This computation is necessary to properly "guess" the formula that we then prove using the adaptive interpolation method. The reader interested in the replica approach to neural networks and the commitee machine is invited to look as well to some of the classical papers [41, 35,

The replica trick makes use of the formula, for a random variable x ∈ R n and a strictly positive function f : R n → R:

lim n→∞ 1 n E log f = lim p→0 + lim n→∞ 1 np log Ef p . (109)
Note that the inversion of the two limits here is non-rigorous. Computing the moments Ef p can often be done for integers p ∈ N, and one can conjecture from it its value for every p > 0, before taking the limit p → 0 + in (109) by analytical continuation of the value for integer p.

In our calculation, we will use this formula to compute the free entropy of our system, f ≡ lim n→∞ f n . We will thus need the moments of the partition function, for integer p:

EZ p n = E   R n ×R K dw n i=1 P 0 ({ w il K l=1 m µ=1 P out   Y µ 1 √ n n i=1 X µi w il K l=1     p , = E   p a=1 R n ×R K dw a n i=1 P 0 ({ w a il K l=1 m µ=1 P out   Y µ 1 √ n n i=1 X µi w a il K l=1     .
The outer expectation is done over X µi ∼ N (0, 1), w * and Y . Writing w * as w 0 we have:

EZ p n = E X R m dY p a=0 R n ×R K dw a n i=1 P 0 ({ w a il K l=1 × m µ=1 P out   Y µ 1 √ n n i=1 X µi w a il K l=1   .
To perform the average over X, we notice that, since it is an iid standard Gaussian matrix, then for every a, µ, l, Z a µl ≡ n -1/2 n i=1 X µi w a il follows a Gaussian multivariate distribution, with zero mean. This naturally leads to introduce its covariance tensor, which is equal to:

EZ a µl Z b νl = δ µν Σ al bl = δ µν Q al bl , (110)
Q al bl ≡ 1 n n i=1 w a il w b il . (111)
For every a, b, Q a b ∈ R K×K is the overlap matrix, and Σ is of size size (p + 1)K × (p + 1)K. Introducing δ functions for xing Q, we arrive at :

E [Z(Y ) n ] = (a,r) R dQ ar ar {(a,r);(b,r )} R dQ ar br I prior ({Q ar br }) × I channel ({Q ar br }) , (112) with:
I prior ({Q ar br }) = p a=0 R n×K dw a P 0 (w a )   {(a,l);(b,l )} δ Q al bl - 1 n n i=1 w a il w b il   , (113)
I channel ({Q ar br }) = R m dY p a=0 R m×K
By Fourier expanding the delta functions in I prior , and performing a saddle-point method, one obtains:

lim n→∞ 1 n log E [Z(Y ) p ] = extr Q, Q H(Q, Q) , (115)
in which (recall α ≡ lim n→∞ m/n) :

H(Q, Q) ≡ 1 2 p a=0 l,l Q al al Qal al - 1 2 a =b l,l Q al bl Qal bl + log I + α log J, (116)
in which we de ned:

I ≡ p a=0 R K dw a P 0 (w a ) exp   - 1 2 p a=0 l,l Qal al w a l w a l + 1 2 a =b l,l Qal bl w a l w b l   , (117)
J ≡ R dy p a=0 R K dZ a (2π) K(p+1)/2 P out (y|Z a ) √ det Σ exp   - 1 2 p a,b=0 K l,l =1 Z a l Z b l (Σ -1 ) al bl   . ( 118
)
Our goal is to express H(Q, Q) as an analytical function of p, in order to perform the replica trick. To do so, we will assume that the extremum of H is attained at a point in Q, Q space such that a replica symmetry property is veri ed. More concretely, we assume:

∃Q 0 ∈ R K×K s.t ∀a ∈ [|0, p|] ∀(l, l ) ∈ [|1, K|] 2 Q al al = Q 0 ll , (119)
∃q ∈ R K×K s.t ∀(a < b) ∈ [|0, p|] 2 ∀(l, l ) ∈ [|1, K|] 2 Q al bl = q ll , (120)
and samely for Q0 and q. Note that Q 0 is by de nition a symmetric matrix, while q is also symmetric by our assumption of replica symmetry. Under this ansatz, we obtain:

H(Q 0 , Q0 , q, q) = p + 1 2 Tr[Q 0 Q0 ] - p(p + 1) 2
Tr[q q] + log I + α log J.

Remains now to compute an expression for I and J that is analytical in p, in order to take the limit p → 0 + . This can be done easily, using the identity, for any symmetric positive matrix M ∈ R K×K and any vector

x ∈ R K : exp (x (M/2)x) = R K Dξ exp ξ M 1/2
x , in which Dξ is the standard Gaussian measure on R K . We obtain:

I = R K Dξ R K dw P 0 (w) exp - 1 2 w ( Q0 + q)w + ξ q1/2 w p+1 , (122)
J = R dy R K Dξ R K dZP out y|(Q 0 -q) 1/2 Z + q 1/2 ξ p+1 . (123)
Our assumptions must be consistent in the sense that extr Q, Q lim p→0 + H(Q, Q) = 0 (because EZ 0 n = 1). In the p → 0 + limit, one easily gets J = 1 and I = R K dw P 0 (w) exp -1 2 w Q0 w 0 . This implies that the optimal overlap parameters satisfy Q0 = 0 and Q 0 ll = E P 0 [w l w l ]. In the end, we obtain the nal formula for the free entropy:

f = extr q,q - 1 2 Tr[q q] + I P + αI C , (124)
I P ≡ R K Dξ R K dw 0 P 0 (w 0 ) exp - 1 2 (w 0 ) qw 0 + ξ q1/2 w 0 × log R K dwP 0 (w) exp - 1 2 w qw + ξ q1/2 w , I C ≡ R dy R K Dξ R K DZ 0 P out y|(Q 0 -q) 1/2 Z 0 + q 1/2 ξ × log R K DZP out y|(Q 0 -q) 1/2 Z + q 1/2 ξ .
A known ambiguity of the replica method is that its result is given as an extremum, here over the set S + K (Q 0 ) of positive symmetric matrices, such that (Q 0q) is also a positive matrix. It is easy to show that this form gives back the form given in Theorem 3.1, by assuming that this extremum is realized as a sup q inf q . Note that in the notations of Theorem 3.1, Q 0 is denoted ρ and q is denoted R.

D Generalization error

We detail here two di erent possible de nitions of the generalization error, and how they are related in our system. Recall that we wish to estimate W * from the observation of ϕ out (XW * ). In the following, we denote E for the average over the (quenched) W * and the data X, andfor the Gibbs average over the posterior distribution of W . One can naturally de ne the Gibbs generalization error as:

Gibbs g ≡ 1 2 E W * ,X [ϕ out (XW ) -ϕ out (XW * )] 2 , ( 125
)
and de ne the Bayes-optimal generalization error as:

Bayes g ≡ 1 2 E W * ,X ϕ out (XW ) -ϕ out (XW * ) 2 . ( 126
)
Using the Nishimori identity A.1, one can show that:

Bayes g = 1 2 E X,W * ϕ out (XW * ) 2 + 1 2 E X,W * ϕ out (XW ) 2 -E X,W * ϕ out (XW * ) ϕ out (XW ) , = 1 2 E X,W * ϕ out (XW * ) 2 - 1 2 E X,W * ϕ out (XW * ) ϕ out (XW ) .
Using again the Nishimori identity one can write:

Gibbs g = E X,W * ϕ out (XW * ) 2 -E X,W * ϕ out (XW * ) ϕ out (XW ) ,
which shows that Gibbs g = 2 Bayes g . Note nally that since the distribution of X is rotationally invariant, the quantity E X [ϕ out (XW * ) ϕ out (XW )] only depends on the overlap q ≡ W W * . As the overlap is shown to concentrate under the Gibbs measure by Proposition A.4, and as we expect that the value it concentrates on is the optimum q * of the replica formula (such fact is proven, e.g., for random linear estimation problems in [START_REF] Barbier | Mutual information and optimality of approximate message-passing in random linear estimation[END_REF]), the generalization error can itself be evaluated as a function of q * . Example where is done includes e.g. [START_REF] Opper | Statistical mechanics of generalization[END_REF][START_REF] Seung | Statistical mechanics of learning from examples[END_REF][START_REF] Schwarze | Learning a rule in a multilayer neural network[END_REF][START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF]].

E The large K limit in the committee symmetric setting

We consider the large K limit 3 for a sign activation function, and for di erent priors on the weights. Since the output is a sign, the channel is simply a delta function. We assume a committee symmetric solution, i.e. the matrices q and q (q and R in the notations of Theorem 3.1) are of the type q = q d I K×K + qa R 1 K 1 K , with the unit vector 1 K = (1) K l=1 , and similarly for q. In the large K limit, this scaling of the order parameters is natural. Indeed, assume that the covariance of the prior is Q 0 = I K×K (Q 0 = ρ in the notations of Theorem 3.1). Since both q and (Q 0q) are assumed to be positive matrices, it is easily shown to imply that 0 ≤ q d ≤ 1 and 0 ≤ q a + q d ≤ 1.

E.1 Large K limit for sign activation function

In the following, we consider Q 0 = σ 2 I K×K . We are interested here in computing the leading order term in I C of (124). Note that replacing σ 2 by 1 in this equation only amounts to replacing q by q/σ 2 , so we can assume ρ = 1 without loss of generality. We write I C in (124) as I C = R dy R K Dξ I C (y, ξ) log I C (y, ξ). A simple theoretical physics calculation yields the expression:

I C = R dwd ŵ 2π dudû 2π e iw ŵ+iuû δ y,sign(u) × K l=1 R Dze -i ŵ z √ K e -iû √ K sign z+ 1-qa-q d 1-q d -1 w √ K + 1 √ 1-q d (q 1/2 xi) l .
Denote

λ l ≡ 1 -q a -q d 1 -q d -1 w √ K + 1 √ 1 -q d (q 1/2 ξ) l ,
and for 1 ≤ l ≤ R, one can rewrite the factorized integral in the last expression of I C as:

J l ≡ e - λ 2 l 2 +iλ l ŵ √ K R Dze z(λ l -i ŵ √ K ) e -iû √ K sign[z] ,
and J ≡ K l=1 J l . Using that:

F (α, iβ) ≡ R Dze αz+iβ sign(z) = e α 2 /2 cos β + i sin β Ĥ(α) , (127)
with Ĥ(x) = erf(x/ √ 2), we obtain:

J l = e -1 2K ŵ2 cos û √ K -i sin û √ K Ĥ λ l -i ŵ √ K .
Note that we have λ l = λ l,0 + 1 √ K λ 1 with:

λ l,0 = q d 1 -q d ξ l and λ 1 = 1 -q a -q d 1 -q d -1 w + q a + q d 1 -q d - q d 1 -q d 1 K ξ √ K .
Expanding J l as K → ∞, we obtain:

J l = e -1 2K ŵ2 1 - û2 2K -i Ĥ (λ l,0 ) û √ K -i û(λ 1 -i ŵ) K 2 π e - λ 2 l,0 2 + O(K -3/2 ) .
Then we have J = exp K l=1 ln J l , which yields:

J = e -1 2 ŵ2 exp - û2 2 -iûS 1 -i 2 π û(λ 1 -i ŵ)Γ 0 + 1 2 û2 S 2 + O(K -1/2 ) ,
in which we de ned

w ξ ≡ 1 √ K K l=1 ξ l , Γ 0 ≡ 1 K K l=1 e -1 2 λ 2 l,0 , S 1 ≡ 1 √ K K l=1 Ĥ(λ l,0 ), S 2 ≡ 1 K K l=1 Ĥ(λ l,0 ) 2 .
A detailed calculation actually shows that the calculation of J is true not only up to O(K -1/2 ) but to O(K -1 ). Recall that I(y, ξ) = (4π 2 ) -1 dwd ŵdudûe iw ŵ+iuû δ y,sign(u) × J. One can now readily perform the integration over all variables to obtain:

I(y, ξ) = H   -y S 1 + 2 π w ξ Γ 0 √ q d +qa- √ q d √ 1-q d 1 -S 2 -2 π Γ 2 0 qa 1-q d   + O(K -1 ), ( 128
) in which H(x) ≡ ∞ x Dz = 1 2 (1 -erf(x/ √ 2
)). Note that all quantities w ξ , Γ 0 , S 1 , S 2 only depend on ξ via its empirical measure, which means the integration over ξ ∈ R K is tractable. We compute it in the following, using theoretical physics methods. Basically, denoting

G(w ξ , Γ 0 , S 1 , S 2 ) = H   -y S 1 + 2 π w ξ Γ 0 √ q d +qa- √ q d √ 1-q d 1 -S 2 -2 π Γ 2 0 qa 1-q d   , it amounts to write: R K DξI C (y, ξ) log I C (y, ξ) = dw ξ d ŵξ 2π dΓ 0 d Γ0 2π dS 1 d Ŝ1 2π dS 2 d Ŝ2 2π e iw ŵ+iΓ 0 Γ0 +iS 1 Ŝ1 +iS 2 Ŝ2 G(w ξ , Γ 0 , S 1 , S 2 ) × log G(w ξ , Γ 0 , S 1 , S 2 ) R K Dξe -i ŵw ξ (ξ)-i Γ0 Γ 0 (ξ)-i Ŝ1 S 1 (ξ)-i Ŝ2 S 2 (ξ) + O(K -1 ).
Computing the last integral when K → ∞, and de ning γ ≡ 2 π (q a + arcsin q d ), one reduces this form to the nal expression:

I C = y=±1 R DxH yx γ 1 -γ log H yx γ 1 -γ + O(K -1 ), I C = 2 R DxH x γ 1 -γ log H x γ 1 -γ + O(K -1 ). (129)
Note that the parameter γ is naturally bounded to the interval [0, 1] by the conditions 0 ≤ q d ≤ 1 and 0 ≤ q a + q d ≤ 1.

E.2 The Gaussian prior

The prior part I P of the free entropy (124) is very easy to evaluate in the Gaussian prior setting. We consider a prior with variance ρ = 1 (we can simply rescale q by q/ρ in the nal expression for a nite variance ρ). We obtain:

I P = K 2 qd + 1 2 qa - K -1 2 log(1 + qd ) - 1 2 log (1 + qd + qa ) . (130)

E.3 The xed point equations

From the free entropy (124) and ( 129), (130), one easily obtains the xed point equations (after having extremized over qd and qa ) as (recall α = lim m n ):

∂ qa (I G + αI C ) = 0, (131)
∂ q d (I G + αI C ) = 0, (132)
with

I G ≡ 1 2 [q a + Kq d ] - K -1 2 log 1 1 -q d - 1 2 log 1 1 -q a -q d , I C = 2 R DxH x γ 1 -γ log H x γ 1 -γ ,
and recall that γ ≡ 2 π (q a + arcsin q d ). The xed point equations ( 131), (132) have di erent behaviors depending on the scaling of α with the hidden layer size K. We detail these di erent behaviors in the following.

E.3.1 Regime α = o K→∞ (K)
In this regime (which in particular contains the case in which α stays of order 1 when K → ∞), the xed point equations can be simpli ed as:

q d = 0, q a = 2α(1 -q a ) ∂I C ∂qa . (133)
E.3.2 Regime α = Θ K→∞ (K)
In this regime, we naturally de ne α = αK, with α of order 1. One can show that the xed point equations (131), (132) only admit a solution with the following scaling : q a + q d = 1 -χ K . The xed point equations in terms of χ and q d read:

         γ = 2 π arcsin(q d ) -q d + 1 -χ K = 2 π (arcsin(q d ) -q d + 1) + O(K -1 ), q d = 2(1 -q d ) 1 √ 1-q 2 d -1 α ∂I C ∂qa , χ -1 = 2 α ∂I C ∂qa . (134)
The State Evolution (SE) computation of Figure 1 was performed by solving the xed point equations ( 133), (134) (depending on the regime of α).

The stability of the q d = 0 solution: It is easy to show that (134) always admit a non-specialized solution with q d = 0. This solution stops however to be optimal in terms of the free energy at a nite value of α spec 7.65. However, this solution will remain linearly stable for every α. Actually, one can show that this non-specialized solution will remain linearly stable for α up to order Θ(K 2 ). Indeed, adding the correct time indices to iterate the state evolution xed point equations, we obtain:

q t+1 d = F (q t d , q t a ) 1 + F (q t d , q t a ) , (135)
q t+1 a = G(q t d , q t a ) 1 + F (q t d , q t a ) 1 + F (q t d , q t a )G(q t d , q t a ) , (136)
with F and G de ned as:

F (q t d , q t a ) ≡ 2α K -1 [∂ q d I C -∂ qa I C ] , (137)
G(q t d , q t a ) ≡ 2αK K -1 ∂ qa I C - 1 K ∂ q d I C . (138)
We focusing on the behavior of (135) around q d = 0. Since we have shown that in the K → ∞ limit, the leading order in I C only depends on γ = 1 π (q a +arcsin q d ), one easily computes that for α = o(K 2 ) (the regime in which only the leading order of I C contributes), ∂F ∂q d | q d =0 → K→∞ 0, which means the q d = 0 solution always remains linearly stable. However, assume now that α = Θ(K 2 ). Performing a similar calculation to the one shown in sec. E.1, one can show the following expansion:

I C (q d , q a ) = I (0) C (q d , q a ) + 1 K I (1) C (q d , q a ) + O 1 K 2 .
The term of ∂F ∂q d | q d =0 arising from I

C will thus have a possibly non-zero contribution in the K → ∞ limit, see (137). To summarize, the non-specialized solution always remains linearly stable in the large K limit for α of order smaller than K 2 . This implies that Approximate Message Passing, implemented in such a regime, could not possibly nd the specialized solution in this regime. Note that this range of scaling of α is possibly broader, as one would have to explicitly compute I

C in order to check that ∂F ∂q d | q d =0 = 0. This tedious calculation is left for future work.

E.4 The generalization error at K = 2

In this subsection alone, we go back to the K = 2 case, instead of the K → ∞ limit. From the de nition of the generalization error (see sec. D), one can directly give an explicit expression of this error in the K = 2 case. Recall that the overlap matrix q = q d I K×K + qa K 1 K 1 K with (1 K ) l = 1. For simplicity, we denote sign(x) = σ(x). One obtains:

1 2 -2 Bayes,K=2 g = R 4 Dx σ [σ(x 1 ) + σ(x 2 )] (139)
× σ σ ( q a 2 + q d )x 1 + q a 2 x 2 + x 3 1 - q 2 a 2 -q a q d -q 2 d +σ   q a 2 x 1 + ( q a 2 + q d )x 2 -x 3 q a (q d + qa 2 ) 1 -q 2 a 2 -q a q d -q 2 d + x 4 (1 -q 2 d )(1 -(q a + q d ) 2 ) 1 -q 2 a 2 -q a q d -q 2 d      .
Note that one could possibly simplify this expression by using an appropriate orthogonal transformation on x. These integrals were then computed using Monte-Carlo methods to obtain the generalization error in the left and middle plots of Fig. 1.

E.5 The generalization error at large K

Recall the de nition of the generalization error from sec. D. From the remarks of the section, one can compute it using (125), by noting that Gibbs g = g (q * ), in which q * is the optimal overlap, and where we de ned:

g (q) ≡ 1 2 E X [ϕ out (XW ) -ϕ out (XW * )] 2 .
This quantity indeed only depends on the overlap q = W W * by rotation invariance of the distribution of X.

At large K, one can apply the same expansion used for computing I C in sec. E.1, and obtains after a tedious yet straightforward calculation:

Bayes g = 1 2 Gibbs g = 1 π arccos 2 π (q a + arcsin q d ) + O(K -1 ). ( 140
)
This expression is the one used in the computation of Fig. 1.

F Linear networks show no specialization

An easy yet interesting case is a linear network with identical weights in the second layer and a nal output function σ : R → R, i.e a network in which ϕ out (h) = σ 1 √ K K l=1 h l . For clarity, in this section, we decompose the channel as P out (y|ϕ out (Z)) for Z ∈ R K instead of P out (y|Z). We will compute the channel integral I C of the replica solution (124). For simplicity, we assume that Q 0 = 1 K the identity matrix (i.e w has identity covariance matrix under P 0 ). Note that (124) gives I C as I C = R dy R K DξI C (y, ξ) log I C (y, ξ). One can easily derive:

I C (y, ξ) = e -1 2 ξ (1 K -q) -1 qξ R 2
dudû 2π e iuû P out (y|σ(u)) × R K dZ (2π) K det(1 Kq) e -1 2 Z (1 K -q) -1 Z+Z X(û,xi) , in which we denoted X(û, xi) (1 Kq) -1 q 1/2 ξ -iû √ K 1 K , with the unit vector 1 K = (1) K l=1 . The inner integration over Z can be done, as well as the integration over û:

I C (y, ξ) = 1 1 -1 K 1 K q1 K R du √ 2π P out (y|σ(u)) exp   - u -1 √ K 1 R q 1/2 ξ 2 2 1 -1 K 1 K q1 K    .
So we can formally write the total dependency of I C (y, ξ) on ξ and on q as

I C (y, ξ) = I C y, 1 √ K 1 K q 1/2 ξ, 1 K 1 K q1 K .
Note that we have the following identity, for any xed vector x ∈ R K and smooth real function F :

R K DξF (x ξ) = 1 √ 2πx x R duF (u)e -u 2 2x x . (141)
In the end, if we denote Γ(q)

1 K 1 K q1 K , we have:

I C = R dy 1 2πΓ(q) R dve -v 2 2Γ(q) I C (v, y) log I C (v, y), (142)
I C (v, y) ≡ 1 2π(1 -Γ(q)) R du P out (y|σ(u)) exp -1 2 (1 -Γ(q)) (uv) 2 .

(143)

Note that by hypothesis, both q and 1q are positive matrices, so 0 ≤ Γ(q) ≤ 1. As these equations show, I C only depends on Γ(q) = K -1 l,l q ll . From this one easily sees that extremizing over q implies that the optimal q satis es qll = q/K for some real q. Subsequently, all q ll are also equal to a single value, that we can denote q K . This shows that this network never exhibits a specialized solution.

G Update functions and AMP derivation

AMP can be seen as Taylor expansion of the Loopy Belief Propagation approach [START_REF] Mézard | Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications[END_REF][START_REF] Mézard | Information, physics, and computation[END_REF][START_REF] Wainwright | Graphical models, exponential families, and variational inference[END_REF], similar to the so-called Thouless-Anderson-Palmer equation in spin glass theory [START_REF] Thouless | Solution of'solvable model of a spin glass[END_REF]. While the behaviour of AMP can be rigorously studied [START_REF] Bayati | The dynamics of message passing on dense graphs, with applications to compressed sensing[END_REF][START_REF] Javanmard | State evolution for general approximate message passing algorithms, with applications to spatial coupling[END_REF][START_REF] Bayati | Universality in polytope phase transitions and message passing algorithms[END_REF], it is useful and instructive to see how the derivation can be performed in the framework of Belief Propagation (BP) and the cavity method, as was pioneered in [START_REF] Mézard | The space of interactions in neural networks: Gardner's computation with the cavity method[END_REF][START_REF] Kabashima | Inference from correlated patterns: a uni ed theory for perceptron learning and linear vector channels[END_REF] for the single layer problem. The derivation uses the Generalized AMP notations of [START_REF] Rangan | Generalized approximate message passing for estimation with random linear mixing[END_REF] and follows closely the one of [START_REF] Zdeborová | Statistical physics of inference: thresholds and algorithms[END_REF].

G.1 De nition of the update functions

Let's consider the distributions probabilities Pout and P0 , related up to a normalizing constant, to the problems 4 and 7. We de ne the update functions g out , ∂ ω g out , f W and f C , which will be useful later in the algorithm, as the mean and variance with respect to these distributions:

Gathering all pieces, the message mµ→i can be expressed using de nitions of g out and ∂ ω g out : mµ→i (t, w Using the set of BP equations (144), we can close the set of equations only over {m i→µ } iµ :

m i→µ (t + 1, w i ) = 1 Z i→µ P 0 (w i ) m ν =µ det(A t ν→i ) (2π) K e -1 2 (wi-(A t ν→i ) -1 B t ν→i ) A t ν→i (wi-(A t ν→i ) -1 B t ν→i ) .
In the end, computing the mean and variance of the product of gaussians, the messages are updated using f W and f C : Summary of the Relaxed BP set of equations In the end, Relaxed BP equations are simply the following set of equations:

           Σ t µ→i = m ν =µ A t
                         ω t iµ = n j =i
X µj Ŵj→µ (t)

V t iµ = n j =i (X µj ) 2 Ĉj→µ (t) B t µ→i = X µi g out (ω t iµ , Y µ , V t iµ ) A t µ→i = -X 2 µi ∂ ω g out (ω t iµ , Y µ , V t iµ )                              Σ t µ→i = m ν =µ A t ν→i -1 T t µ→i = Σ t µ→i m ν =µ B t ν→i Ŵi→µ (t + 1) = f W (Σ t µ→i , T t µ→i ) Ĉi→µ (t + 1) = f C (Σ t µ→i , T t µ→i ) (145)

G.2.2 Approximate Message Passing algorithm

On a tree, the missing message is negligible, which allows us to expand the previous Relaxed BP equations (145). We de ne the following estimates and parameters based on the complete set of messages:

         ω t µ = n j=1
X µj Ŵj→µ (t)

V t µ = n j=1
Ĉi→µ (t + 1) = E P0 [ Ŵi→µ Ŵ i→µ ] -E P0 [ Ŵi→µ ]E P0 [ Ŵi→µ ] = E P0 [ Ŵi -X µi E Ŵi -X µi E ] -E P0 [ Ŵi -X µi E]E P0 [ Ŵi -X µi E] = E P0 [ Ŵi Ŵ i ] -E P0 [ Ŵi ]E P0 [ Ŵi ] + O 1 √ n = Ĉi (t + 1) + O 1 √ n

i

  with b, c ∈ {1, 2} to distinguish i.i.d. replicas with product measure -⊗2 if b = c and common one else, and denote A (a) , a ∈ {1, 2, 3, . . .}, to emphasize that A depends on replica w (a) i )

P

  out (Y |Z a )e -m 2 log det Σ-

1 1 Z P 0 P 0

 1100 ; ω, y, V ) ≡ 1 Zout e -1 2 (z-ω) V -1 (z-ω) P out (y|z)g out (ω, y, V ) = Zout ∂Zout ∂ω (ω, y, V ) = V -1 E Pout [zω] ∂ ω g out (ω, y, V ) = V -1 E Pout [(zω)(zω) ] -V -1g out g out              P0 (w; Σ, T ) ≡ (w)e -1 2 (w-T ) Σ -1 (w-T ) f W (Σ, T ) = E P0 [w] f C (Σ, T ) = E P0 [ww ]f W f W G.2 Approximate message passing algorithm G.2.1 Relaxed BP equationsLets consider a set of messages {m i→µ , mµ→i } i=1..n,µ=1..m on the bipartite factor graph corresponding to our problem. Beliefs propagation equations can be formulated as the following[START_REF] Mézard | Information, physics, and computation[END_REF][START_REF] Wainwright | Graphical models, exponential families, and variational inference[END_REF], wherew i = (w il ) l=1..K ∈ R K .            m i→µ (t + 1, w i ) = 1 Z i→µ P 0 (w i ) m k =µ mν→i (t, w i ) mµ→i (t, w i ) = 1 Z µ→i n j =i dw j P out   Y µ | n j=1X µj w j   m j→µ (t, w j )

  is also continuous (∇Ψ Pout denotes the derivative of Ψ Pout w.r.t. its rst argument, and can be shown to be continuous and bounded). By Brouwer's xed-point theorem (since S + K (P ) is convex and compact), there exists a xed point R * n

  2 i ) ∼ 1 Z µ→i 1 + X µi (w i ) g out (ω t iµ , Y µ , V t iµ ) + 1 2 X 2 µi (w i ) g out g out (ω t iµ , Y µ , V t iµ )w i + X iµ g out (ω t iµ , Y µ , V t iµ ) A t µ→i ≡ -X 2 iµ ∂ ω g out (ω t iµ , Y µ , V t iµ )

	1 2	X 2 µi (w i ) ∂ ω g out (ω t iµ , Y µ , V t iµ )w i
	=	1 Z µ→i	1 + (w i ) B t µ→i +	1 2	(w i ) B t µ→i (B t µ→i ) (w i -	1 2	(w i ) A t µ→i w i
	=	det(A t µ→i ) (2π) K exp -	1 2	w i -(A t µ→i ) -1 B t µ→i	A t µ→i w i -(A t µ→i ) -1 B t µ→i
	with the following de nitions of A µ→i and B µ→i :
				   B t µ→i ≡
				 

Note that many of these works study the "tree" committee machine, sometimes called committee machine with non-overlapping elds; we do not study this version here. We chose the version that is more closely related to currently used architectures.

The symbol E will generally denote an expectation over all random variables in the ensuing expression (here {Xµi, Yµ}). Subscripts will be used only when we take partial expectations or if there is an ambiguity.

A similar limit has been derived in the context of coding with sparse superposition codes[START_REF] Barbier | Approximate message-passing decoder and capacity achieving sparse superposition codes[END_REF]. There the large input alphabet limit of the mutual information is considered after the thermodynamc limit n → ∞ corresponding to the large codeword limit in this coding context.

Acknowledgments

This work has been supported by the ERC under the European Union's FP7 Grant Agreement 307087-SPARCS and the European Union's Horizon 2020 Research and Innovation Program 714608-SMiLe, as well as by the French Agence Nationale de la Recherche under grant ANR-17-CE23-0023-01 PAIL. Additional funding is acknowledged by FK from "Chaire de recherche sur les modèles et sciences des données", Fondation CFM pour la Recherche-ENS;

where we absorbed the factor 1 √ n in the element X µi , which are therefor of order O 1 √ n . The term inside P out can be decouple using its K-dimensional Fourrier transform:

From this, (144) becomes:

dw j m j→µ (t, w j ) exp (iξ X µj w j ))

:=I j and we de ne the mean and variance of the messages:

In the limit n → ∞, X µi being of order O 1 √ n , the term I j can be easily expanded and expressed with Ŵ and Ĉ:

And nally using the inverse Fourier transform:

:=H iµ where we de ned:

Again, in the limit n → ∞, the term H iµ can also be expanded:

The AMP algorithm follows naturally the rBP equations (145) using the expanded estimates of the mean and variance ω µ ,V µ ,T i and Σ i . The algorithm is written in pseudo language in Algorithm 1.

H Parity machine for K = 2

Although we mainly focused on the committee machine, another classical two-layers neural network is the parity machine [START_REF] Engel | Statistical Mechanics of Learning[END_REF] and our proof applies to this case as well. While learning is known to be computationally hard for general K, the case K = 2 is special, and in fact can be reformulated as a committee machine, where Overlap q AMP q 00 AMP q 01 SE q 00 SE q 01 SE ǫ g (α) AMP ǫ g (α)

Specialization

Figure 2: Similar plot as in Fig. 1 but for the parity machine with two hidden neurons. Value of the order parameter and the optimal generalization error for a parity machine with two hidden neurons with Gaussian weights (left) and binary/Rademacher weights (right). SE and AMP overlaps are respectively represented in full line and points.

the sign activation function has been replaced by ϕ 1 (z) = 1(z = 0) -1(z = 0):

We have repeated our analysis for the K = 2 parity machine and the phase diagram is summarized in Fig. 2 where we show the generalization error and the elements of the overlap matrix for Gaussian (left) and binary weights (right), with the results of the AMP algorithm (points).

Below the specialization phase transition α < α spec , the symmetry of the output imposes the nonspecialized xed point q 00 = q 01 = 0 to be the only solution, with α G spec (K = 2) 2.48 and α B spec (K = 2) 2.49. Above the specialization transition α spec , the overlap becomes specialized with a non-trivial diagonal term.

Additionally, in the binary case, an information theoretical transition towards a perfect learning occurs at α B IT (K = 2) 2.00, meaning that the perfect generalization xed point (q 00 = 1, q 01 = 0) becomes the global optimizer of the free entropy. It leads to a rst order phase transition of the AMP algorithm which retrieves the perfect generalization phase only at α B perf (K = 2) 3.03. This is similar to what happens in single layer neural networks for the symmetric door activation function, see [START_REF] Barbier | Phase transitions, optimal errors and optimality of message-passing in generalized linear models[END_REF]. Again, these results for the parity machine emphasize a gap between information-theoretical and computational performance.