{'fraction_non_alphanumeric': 0.06638856046579071, 'fraction_numerical': 0.01757869141365695, 'mean_word_length': 3.8326865028029324, 'pattern_counts': {'":': 1, '<': 9, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Information theoretic limits of learning a sparse rule

We consider generalized linear models in regimes where the number of nonzerocomponents of the signal and accessible data points are sublinear with respect to the size of the signal. We prove a variational formula for the asymptotic mutual information per sample when the system size grows to infinity. This result allows us to heuristically derive an expression for the minimum mean-square error (MMSE)of the Bayesian estimator. We then find that, for discrete signals and suitable vanishing scalings of the sparsity and sampling rate, the MMSE displays an all-or-nothing phenomenon, namely, the MMSE sharply jumps from its maximum value to zero at a critical sampling rate. The all-or-nothing phenomenon has recently been proved to occur in high-dimensional linear regression. Our analysis goes beyond the linear case and applies to learning the weights of a perceptron with general activation function in a teacher-student scenario. In particular we discuss an all-or-nothing phenomenon for the generalization error with a sublinear set of training examples.


Introduction
Modern tasks in statistical analysis, signal processing and learning require solving high-dimensional inference problems with a very large number of parameters. This arises in areas as diverse as learning with neural networks [1], high-dimensional regression [2] or compressed sensing [3,4]. In many situations, there appear barriers to what is possible to estimate or learn when the data becomes too scarce or too noisy. Such barriers can be of algorithmic nature, but they can also be intrinsic to the very nature of the problem. A celebrated example is the impossibility of reconstructing a noisy signal when the noise is beyond the so-called Shannon capacity of the communication channel [5]. A large amount of interdisciplinary work has shown that these intrinsic barriers can be understood as static phase transitions (in the sense of physics) when the system size tends to infinity (see [6,7,8]).
When the problem can be formulated as an (optimal) Bayesian inference problem the mathematically rigorous theory of these phase transitions is now quite well developed. Progress initially came from applications of the Guerra-Toninelli interpolation method developed for the Sherrington-Kirkpatrick spin-glass model [9], to coding and communication theory [10,11,12,13,14,15], and more recently to low-rank matrix and tensor estimation [16,17,18,19,20,21,22,23,24], compressive sensing and high-dimensional regression [25,26,27,28], and generalized linear models [29,30]. In particular, for all these problems it has been possible to reduce the asymptotic mutual information to a low-dimensional variational expression, and deduce from its solution relevant error measures (e.g., minimum mean-square and generalization errors). All these works consider the traditional regime of statistical mechanics where the system size goes to infinity while relevant control parameters (such as signal sparsity, sampling rate, or signal-to-noise ratio) are kept fixed.
However, there exist other interesting regimes for which many of the above mentioned problems also display fundamental intrinsic limits akin to phase transitions. Consider for example the problem of compressive sensing. An interesting regime is one where both the number of nonzero components and of samples scale in a sublinear manner as the system size tends to infinity. In this case we would like to identify the phase transition, if there is any, and its nature. This question has first been addressed recently in the framework of compressed sensing for binary Bernoulli signals by [31,32,33]. An all-or-nothing phenomenon is identified, that is, in an appropriate sparse regime, the minimum mean-square error (MMSE) sharply drops from its maximum possible value (no reconstruction) for "too small" sampling rates to zero (perfect reconstruction) for "large enough" sampling rates. The interest of such regime is not limited to estimation problems. It is also relevant from a learning point of view, e.g., it corresponds to learning scenarios where we have access to a high number of features but only a sublinear number of them -unknown to us -are relevant for the learning task at hand. Examples abound where the "bet on sparsity principle" [34,35] is of utmost importance for the interpretability of a high-dimensional model. Let us mention the MNIST handwritten digit database, where each digit can be presented as a 784 = 28 × 28-dimensional binary vector representing the pixels whereas, in effect, the digits live in a space of the order of 10's of dimensions [36,37]. Another example of effective sparsity comes from natural images which are often sparse in a wavelet basis [38]. Then, a fundamental question is "when is it possible to achieve a low estimation or generalization error with a sublinear amount of samples (sublinear with respect to the total number of features)?".
In this contribution we address this question for a mathematically simple, but precise and tractable, setting. We consider generalized linear models in the regime of vanishing sparsity and sample rate, or equivalently, of sublinear number of data samples and nonzero signal components. As explained below these models can be used for estimation as well as learning, and we uncover in the sublinear regime intrinsic statistical barriers to these tasks in the form of sharp phase transitions. These statistical barriers are computed exactly and thus provide precise benchmarks to which algorithmic performance can be compared.
Let us outline the mathematical setting (see Section 2 for more precisions). In a probabilistic setting the unknown signal vector X * ∈ R n has entries drawn independently at random from a distribution P 0,n := ρ n P 0 + (1 − ρ n )δ 0 with P 0 a fixed distribution. The parameter ρ n controls the sparsity of the signal so that X * has k n := nρ n nonzero components on average. We observe the data Y = ϕ ΦX * / √ kn ∈ R mn obtained by first multiplying the signal with a known m n × n random matrix Φ whose entries are independent standard Gaussian random variables, and then applying ϕ component-wise. The number of data points is controlled by the sampling rate α n , i.e., m n := α n n. We consider the regime (ρ n , α n ) → (0, 0) and, especially, the case α n = γρ n | ln ρ n | for which the sharp all-or-nothing phase transition appears as n goes to infinity. Note that both m n and k n scale sublinearly as n → +∞.
The model can be interpreted as either an estimation problem or a learning problem: • In the estimation interpretation, we assume a purely Bayesian (or optimal) setting. We know the model, the activation function ϕ, the prior P 0,n as well as the measurement matrix Φ. Our goal is then to determine what is the lowest reconstruction error that we can achieve, i.e., what is the average minimum mean-square error k −1 n E X * − E[X * |Y , Φ] 2 when n gets large.
• In the learning interpretation, we consider a teacher-student scenario in which a teacher hands out training samples {(Y µ , (Φ µi ) n i=1 )} mn µ=1 to a student. The teacher produces the output label Y µ by feeding the input (Φ µi ) n i=1 to its own one-layer neural network with activation function ϕ and weights X * = (X * i ) n i=1 . The student -who is given the model and the prior -has to learn the weights X * of the teacher one-layer neural network by minimizing the empirical training error of the m n training samples. For example, the binary perceptron corresponds to ϕ = sign and Y µ ∈ {±1}. Of particular interest is the generalization error. Given a new -previously unseen -random pattern Φ new = (Φ new,i ) n i=1 whose true label is Y new (generated by the teacher's neural network), the optimal generalization error is the error made when estimating Y new in a purely Bayesian way: Let us summarize informally our results in the case of Bernoulli signals which form our main interest here, i.e., P 0,n := (1 − ρ n )δ 0 + ρ n δ 1 . We set α n = γρ n | ln ρ n | where γ stays fixed as n → +∞. We first rigorously determine the mutual information m −1 n I(X * ; Y |Φ) in terms of a low-dimensional variational problem, see Theorem 1, which also provides a precise control of the finite size fluctuations. This theorem has interesting consequences which are not made fully rigorous here. Using I-MMSE type formulas [39], we deduce the MMSE and generalization errors from the solution to this variational problem. Our analysis then shows that both errors display an all-or-nothing behaviour as n → +∞, with a sharp transition at a threshold γ = γ c explicitly computed. These findings are illustrated and their significance discussed in Section 3.
In our work the generalized linear model is treated by entirely different methods than the linear model in [31,32]. Importantly, the sparsity regime treated by our method requires the sparsity ρ n to go to zero slower than n −1 /9 , while it has to go to zero faster than n −1 /2 in the results of [32] for the linear case. From this angle, both results complement each other. Our proof technique for Theorem 1 exploits the adaptive interpolation method (see [40,41]) that is a powerful improvement over the Guerra-Toninelli interpolation and allows to prove replica symmetric formulas for Bayesian inference problems. We adapt the analysis of [30] in a non-trivial way in order to consider the new scaling regime of our problem where α n = γρ n | ln ρ n | and ρ n → 0 as n gets large, instead of fixed. We show that the adaptive interpolation can still be carried through, which requires a more refined control of the error terms compared to [30]. It is interesting, and not a priori obvious, that this can be done since this is not the usual statistical mechanics extensive regime. For example, the mutual information has to be normalized by the subextensive quantity m n = O(n). Quite remarkably, with this suitable normalization, the asymptotic mutual information, MMSE and generalization error have a similar form to those famously found in ordinary thermodynamic regimes in physics [42,43,44,45].
In Section 2 we present the setting and state our main rigorous result (Theorem 1) on the mutual information in the sublinear regime. In Section 3 we use the latter result to uncover the all-or-nothing phase transitions for general activation functions. In Section 4 we give an overview of the adaptive interpolation method used to prove Theorem 1. The full proof is given in the supplementary material.
2 Problem setting and results 2.1 Generalized linear estimation of low sparsity signals at low sampling rates Let n ∈ N * and m n := α n n with (α n ) n∈N * a decreasing sequence of positive sampling rates. Let P 0 be a probability distribution with finite second moment iid ∼ P 0,n be the components of a signal vector X * (this is also denoted X * iid ∼ P 0,n ), where P 0,n := ρ n P 0 + (1 − ρ n )δ 0 . (1) The parameter ρ n ∈ (0, 1) controls the sparsity of the signal; the latter being made of k n := ρ n n nonzero components in expectation. We will be interested in low sparsity regimes where k n = O(n). Let k A ∈ N. We consider a measurable function ϕ : R × R k A → R and a probability distribution P A over R k A . The m n data points Y := (Y µ ) mn µ=1 are generated as where is an additive white Gaussian noise (AWGN), ∆ > 0 is the noise variance, and Φ is a m n × n measurement (or data) matrix with independent entries having zero mean and unit variance. Note that the noise (Z µ ) m µ=1 can be considered as part of the model, or as a "regularising noise" needed for the analysis but that can be set arbitrarily small. Typically, and as n gets large, (ΦX * )µ / √ kn = Θ(1). The estimation problem is to recover X * from the knowledge of Y , Φ, ∆, ϕ, P 0,n and P A (the realization of the random stream A itself, if present in the model, is unknown). It will be helpful to think of the measurements as the outputs of a channel: The transition kernel P out admits a transition density with respect to Lebesgue's measure given by: If A is absent of (2) (k A = 0) then the associated integral dP A (a) in (4) disappears. The random variable A represents any source of randomness in the model. For example, the logistic regression P(Y µ = 1) = f ( (ΦX * )µ / √ kn), with f (x) = (1 + e −λx ) −1 , is modeled by considering a teacher that generates i.i.d. uniform numbers A µ ∼ U[0, 1] and then obtains the labels through kn)) with 1(·) the indicator function. Our numerical experiments in Section 3 are for deterministic activations but our main theoretical result Theorem 1 includes this more generic setting.
We have presented the problem from an estimation point of view. In this case, the important quantity to assess the performance of an algorithm estimating X * is the mean-square error. Another point of view is the learning one: each row of the matrix Φ is the input to a one-layer neural network whose weights X * have been sampled independently at random by a teacher. The student is given the input/output pairs (Φ, Y ) as well as the model used by the teacher. The student's role is then to learn the weights. In this case, more than the mean-square error, the important quantity is the generalization error.

Main result
The mutual information I(X * ; Y |Φ) between the signal X * and the data Y given the matrix Φ is the main quantity of interest in our work. Before stating Theorem 1 on the value of this mutual information, we first introduce two scalar denoising models that play a key role.
The first model is an additive Gaussian channel. Let X * ∼ P 0,n be a scalar random variable. We observe Y (r) := √ rX * + Z where r ≥ 0 plays the role of a signal-to-noise ratio (SNR) and the noise Z ∼ N (0, 1) is independent of X * . The mutual information I P0,n (r) := I(X * ; Y (r) ) between the signal of interest X * and Y (r) depends on ρ n through the prior P 0,n , and it reads: The second scalar channel is linked to the transition kernel P out defined by (4). Let V , W * be two independent standard Gaussian random variables. In this scalar estimation problem we want to infer W * from the knowledge of V and the observation Y (q,ρ) ∼ P out (· | √ q V + √ ρ − q W * ) where ρ > 0 and q ∈ [0, ρ]. The conditional mutual information I Pout (q, ρ) := I(W * ; Y (q,ρ) |V ) is: Both I P0,n and I Pout have nice monotonicity, Lipschitzianity and concavity properties that are important for the proof of Theorem 1 (stated below).
We use the mutual informations (5) and (6) to define the (replica-symmetric) potential: Our main result links the extrema of this potential to the mutual information of our original problem. Theorem 1 (Mutual information of the GLM at sublinear sparsity and sampling rate). Suppose that ∆ > 0 and that the following hypotheses hold: (H1) There exists S > 0 such that the support of P 0 is included in [−S, S].
(H2) ϕ is bounded, and its first and second partial derivatives with respect to its first argument exist, are bounded and continuous. They are denoted ∂ x ϕ, ∂ xx ϕ.
Let ρ n = Θ(n −λ ) with λ ∈ [0, 1 /9) and α n = γρ n | ln ρ n | with γ > 0. Then for all n ∈ N * : where C is a polynomial in S, ϕ Hence the asymptotic mutual information is given to leading order by a variational problem. We remark that, because C depends only polynomially on its arguments, it is possible to weaken the assumptions of the theorem with more technical work. For example, one could extend it to distributions P 0 having infinite support but with finite (first few) moments, to unbounded activation functions that do not grow too fast or to some nondifferentiable activation functions. This includes the linear activation ϕ(x) = x, the usual perceptron ϕ(x) = sign(x) and the ReLU ϕ(x) = max(0, x).

The all-or-nothing phenomenon
We now highlight interesting consequences of Theorem 1 for the MMSE of the estimation problem, as well as the generalization error of the learning problem in the teacher-student scenario. Reeves et al. [32] have proved the existence of an all-or-nothing phenomenon for the linear model and here we extend their results in two ways: i) for the estimation error of a generalized linear model, and ii) for the generalization error of a perceptron neural network with general activation function ϕ. Our analysis is based on non-rigorous but analytical arguments which follow from Theorem 1.
We consider signals whose entries are either Bernoulli random variables, i.e., P 0,n := (1 − ρ n )δ 0 + ρ n P 0 with P 0 = δ 1 , or Bernoulli-Rademacher random variables, i.e., P 0,n := (1−ρ n )δ 0 +ρ n P 0 with P 0 = (δ1+δ−1) /2. In both cases E P0 [X 2 ] = 1 (we can always assume the latter by rescaling the noise). We place ourselves in a regime where α n = γρ n | ln ρ n | for some fixed γ > 0 and ρ n → 0 in the highdimensional limit n → +∞. Finally, we denote q * n (γ) := arg min q∈[0,1] sup r≥0 i RS (q, r; α n , ρ n ) the minimizer of the potential of Theorem 1. In this regime and for such signals we will observe an all-or-nothing phenomenon: there exists γ c > 0 such that, in the high-dimensional limit, perfect reconstruction is possible (q * n (γ) → 1) for γ > γ c , while it is impossible to do better than a random guess (q * n (γ) → 0) for γ < γ c . To locate this all-or-nothing phase transition we use the analytical method described in the supplementary material which predicts (H b : x → x| ln x|+(1−x)| ln(1−x)| is the binary entropy, H(P 0 ) is the entropy of P 0 ): Remember that I Pout (0, 1) : The factor γ c is thus fully determined by the activation function and the amount of noise. In Figure 1 we draw γ c for ϕ(x) = x, ϕ(x) = sign(x), ϕ(x) = max(0, x) and noise variance ∆ ∈ [0, 0.5]. The corresponding formulas for γ c are given in Table 1. We see that for ∆ small enough the ReLU activation requires less training samples to learn the sparse rule than the linear one; it is the opposite once ∆ becomes large enough. When ∆ diverges both the linear and sign activations have the asymptote γ c ∼ 2∆ while the ReLU activation has another steeper asymptote γ c ∼ a∆, a ≈ 5.87. Figure 1 also gives the potential (once it has been maximized over r) as a function of q for two different configurations and several sample rates α n = ( γ /γc)α c (ρ n ). We see that the potential is minimized for q close to 0 when γ is less than γ c and close to 1 when γ is greater than γ c . Exactly at γ = γ c , the potential reaches similar level at q = 0 and q = 1. This numerically confirms the heuristic condition used in the supplementary material in order to locate the phase transition. We next discuss what an all-or-nothing phase transition implies for both the minimum mean-square and generalization errors. To study these errors we informally combine Theorem 1 with the I-MMSE identity [39].
MMSE When doing estimation, the MMSE is given by the mean-square error of the Bayesian estimator and we have whenever q * n (γ) is unique: We note that the link (10) between the MMSE and the extremizer of the variational formula for the mutual information in the high-dimensional limit has been proved in a number of cases, e.g., [46,20]. We obtain that as a function of α n /α c (ρ n ) = γ/γ c when n → +∞ the rescaled MMSE (10) equals 1 (i.e., its maximum value E P0 [X 2 ]) for γ < γ c , and equals 0 for γ > γ c .
Generalization error When learning in a (matched) teacher-student scenario, the components of X * correspond to the unknown weights of the teacher's one-layer neural network. The student is given the model and training samples {(Y µ , (Φ µ,i ) n i=1 )} mn µ=1 . Then, the optimal generalization error is the MMSE for predicting the output We thus find that the generalization error also displays an all-or-nothing phenomenon. More precisely, as a function of α n /α c (ρ n ) = γ/γ c , when n → +∞ the generalization error equals ∆ + Var(ϕ(V, A)) for γ < γ c . This is the generalization error corresponding to assigning to the new label the output value averaged over all possible inputs drawn according to the prior, i.e., the dumb label estimator in the Bayesian sense. If instead γ > γ c then it is equal to ∆ + Var(ϕ(V, A)) − Var(E[ϕ(V, A)|V ]) corresponding to the irreducible error due to the noise.
Illustration of the all-or-nothing phenomenon In Figure 2 we draw the MMSE according to (10) for both priors Bernoulli and Bernoulli-Rademacher and the activation functions ϕ(x) = x, ϕ(x) = sign(x), ϕ(x) = max(0, x). The curves are obtained by optimizing the potential i RS (q, r; α n , ρ n ) for different values of α n = ( γ /γc)α c (ρ n ) with γ lying in a region surrounding γ c . The potential is optimized by initializing q ∈ [0, 1] at different values and iterating the following fixed point equation (obtained directly by setting the gradient of the potential to zero): Finally, the fixed point q * yielding the lowest potential sup r≥0 i RS (q * , r; α n , ρ n ) is used to determine the MMSE thanks to (10). In all configurations the MMSE indeed jumps from a value close to 1 to ≈ 0 as γ increases past γ c . As ρ n gets closer to 0, this jump becomes sharper with the MMSE approaching 0 or 1 depending on which side of γ c we are. Note that for the random linear model ϕ(x) = x, the threshold α c (ρ n ) = 2ρn| ln ρn| /ln(1+∆ −1 ) is in agreement with the sample rate n * for which [32] prove that weak recovery is impossible below it while strong recovery is possible above.
In Figure 3 we plot the optimal generalization error for the Bernoulli prior and the same activation functions. The curves are obtained similarly to the ones in Figure 2 but using (11) instead of (10). In all configurations the generalization error jumps from a value close to ∆ + Var(ϕ(V )) to ≈ ∆ as γ increases past γ c (note that the activations are deterministic so there is no A contribution in the error). The value ∆ is as good as the optimal generalization error can get, i.e., it is equal to the noise variance which is the squared error we would get if we were given the true weights X * . Again, the all-or-nothing phase transition gets sharper as ρ n approaches 0.
The all-or-nothing behaviour of the MMSE and generalization error is quite striking. Indeed, in the limit of vanishing sparsity and sampling rate either estimation or learning is as good as it can get or as bad as a random guess. This purely dichotomic behaviour only occurs in the truly sparse limit, and is shown here to be pretty general in the sense that it occurs for a wide variety of activation functions. An important aspect of our results is to provide a definitive statistical benchmark allowing to measure the quality of algorithms with respect to the minimal amount of sparse data needed to estimate or learn. This benchmark is provided by non-trivial formulas (9) for the threshold γ c given for several examples in Table 1. We note that such precise benchmarks are quite rarely obtained in traditional machine learning approaches.
Further remarks Algorithmic aspects are beyond the scope of this paper. However we make a few remarks about generalized approximate message passing algorithms (GAMP) whose state evolution equations, that precisely track their asymptotic performance, are linked to the fixed point equation (12) [47]. The fixed point q alg n (γ) reached by initializing (12) arbitrarily close to q = 0 can be used in (10) and (11) -instead of q * n (γ) -to obtain both the mean-square and generalization errors of GAMP algorithms. These errors are represented with dotted lines in Figures 2 and 3. We observe an algorithmic-to-statistical gap, that is, the dotted lines corresponding to the algorithmic performance do not drop to zero at γ c but at a higher algorithmic threshold. We conjecture that the all-or-nothing behaviour is also generally true at an algorithmic level for GAMP algorithms. This has been shown rigorously for a linear activation [33] but it would be highly desirable to obtain a proof for other activations and derive the corresponding thresholds.

Overview of the proof of Theorem 1
The interested reader will find the proof of Theorem 1 in the supplementary material. In this section we give an outline of the proof and its main ideas. The proof is based on the adaptive interpolation method [40,41] whose main difference with the canonical interpolation method [48,49] is the increased flexibility given to the path followed by the interpolation between its two extremes. The method has been developed separately for symmetric rank-one tensor problems where the spike has i.i.d. components [40,41], and for one-layer GLMs whose input signal has again i.i.d. components [46]. The sparse regime of the problem studied in this contribution differs of the usual scaling for which such techniques have been developed. They have been used in a regime where the number of measurements and sparsity are linear in n as in [46]. Working in the sparse regime requires writing more refined concentration bounds and proving that the key steps of the adaptive interpolation can still be carried through.

Interpolating estimation problem
To simplify the presentation we assume that ∆ = 1 and E X∼P0 [X 2 ] = 1. The proof starts by introducing an interpolating inference problem that depends on a parameter t ∈ [0, 1] and two continuous interpolation functions R 1 , R 2 : [0, 1] → R + with We define for all t ∈ [0, 1] an "interpolating pre-activation": The inference problem at a fixed t is to recover both unknowns X * , W * from the knowledge of V , Φ and the data . The corresponding interpolating mutual information is: 2. Fundamental sum-rule Note that at t = 0 we recover the original problem of interest and i n (0) = I(X * ;Y |Φ) /mn. At the other extreme t = 1, the mutual information can be written in terms of the simple mutual informations I P0,n and I Pout , that is, i n (1) = I P 0,n (R1(1)) /αn + I Pout (R 2 (1), 1). We link the mutual information at both extremes by computing the derivative i n (·) of i n (·) and then using the fundamental identity i n (0) = i n (1) − 1 0 i n (t)dt. It yields the sum-rule: The last term R n is a remainder whose absolute value we want to control in order to get Theorem 1.
3. Controlling the remainder This is done by plugging two different choices of interpolation functions (R 1 , R 2 ) in the sum-rule. One choice yields an upper bound on the difference in the lefthand side of (8), while another yields a lower bound. Each choice of interpolation functions (R 1 , R 2 ) is defined implicitly as the solution to a second order ordinary differential equation. Remarkably, under these two choices, the remainder R n can be controlled using precise concentration results. Table of

with the adaptive interpolation method
Note that it is the same to observe (2) or their rescaled versions 1 √ ∆ ϕ 1 √ kn (ΦX * )µ, Aµ + Zµ. Therefore, up to a rescaling of ϕ by 1 / √ ∆, we will suppose that ∆ = 1 all along the proof of Theorem 1. For a similar reason, we can suppose that EX∼P 0 [X 2 ] = 1.
We prove Lemma 1 in Appendix D.2. By the chain rule for mutual information and the Lipschitzianity of IP 0,n , IP out (see Lemmas 3 and 4 in Appendix C), at t = 1 we have for all ∈ Bn:

A.2 Fundamental sum rule
We want to compare the original model of interest (model at t = 0) to the purely scalar one (t = 1). To do so, we use in, is the derivative of in, (·). Once combined with Lemma 1 and (17), it yields (note that O(sn) = O( sn / √ ρn) since 0 < ρn < 1): From now on let (x, w) ∈ R n × R mn be a pair of random vectors sampled from the joint posterior distribution (15). The angular brackets − n,t, denote an expectations w.r.t. the distribution (15), i.e., g(x, w) n,t, := g(x, w)dP (x, w|Y (t, ) , Y (t, ) , Φ, V ) for every integrable function g. We define the scalar overlap Q : The computation of i n, is found in Appendix D.1. Proposition 1. Suppose that (H1), (H2), (H3) hold and that ∆ = EX∼P 0 [X 2 ] = 1. Further assume that there exist real positive numbers Mα, M ρ/α such that ∀n ∈ N * : αn ≤ Mα and ρn /αn ≤ M ρ/α . Define uy(x) := ln Pout(y|x) and u y (·) its derivative w. where The next key result states that the overlap concentrates on its expectation. This behavior is called replica symmetric in statistical physics. Similar results have been obtained in the spin glass literature [50,51]. In this work we use a formulation taylored to Bayesian inference problems as developed in the context of LDPC codes, random linear estimation [26] and Nishimori symmetric spin glasses [11,14,16].
We prove Proposition 2 in Appendix F. We can now prove the fundamental sum rule.
. Under the assumptions of Proposition 2, we have: The first factor on the right-hand side of this inequality is bounded by a constant that depends polynomially on ϕ ∞, ∂xϕ ∞ 2 Since ∀(t, ) ∈ [0, 1] × Bn : q (t) = E Q n,t, , the second term is in O(Mn) (see Proposition 2). Therefore, by Proposition 1: Note that 1 /ρn √ n = O( √ Mn). Integrating (18) over ∈ Bn and making use of (21) give the result.

A.3 Matching bounds
To prove Theorem 1, we will lower and upper bound I(X * ;Y |Φ) /mn by the same quantity, up to a small error. To do so we will plug two different choices of interpolation functions R1(·, ), R2(·, ) in the sum-rule of Proposition 3. In both cases, the interpolation functions will be the solutions of a second-order ordinary differential equation (ODE). We now describe these ODEs.
2 Remember that r takes its values in [0, αn ρn rmax]. Besides, under (H2), u (38) in Appendix C). The noise Zµ is averaged over thanks to the expectation.
The angular brackets − n,t,R denotes the expectation w.r.t. this posterior. Let r ∈ [0, rmax], F (n) 2 (t, R) := E Q n,t,R and F (n) 1 (t, R) := −2 αn ρn ∂I P out ∂q q=E Q n,t,R ,ρ=1 . We will consider the two following second-order ODEs with initial value ∈ [sn, 2sn] 2 : The next proposition sums up useful properties on the solutions of these two ODEs, i.e., our two kinds of interpolation functions. The proof is given in Appendix G.

B Heuristic derivation of the phase transition
In this section, we analyze the potential function iRS defined in (7) in order to heuristically locate the information theoretic transition in the special case of a prior P0,n := (1 − ρn)δ0 + ρnP0 where P0 is a distribution over a discrete finite set. If we are to witness an all-or-nothing phenomenon then arg min q∈[0,E X∼P 0 [X 2 ]] sup r≥0 iRS(q, r; αn, ρn) should drop abruptly from q close to EX∼P 0 [X 2 ] to q close to 0. Therefore, we first evaluate sup r≥0 iRS(q, r; αn, ρn) for q ∈ {0, EX∼P 0 [X 2 ]}.
Let X * ∼ P0,n, Z ∼ N (0, 1) be two independent random variables. When r goes to +∞, the mutual information IP 0,n (r) := I(X * ; √ r X * + Z) converges to the entropy H(X * ) since the noise Z disappears. Hence: where denotes the binary entropy function and H(P0) is the entropy of the probability distribution P0.
Of course, in this regime, q * n (γ) := arg min q∈[0,E X∼P 0 [X 2 ]] sup r≥0 iRS(q, r; αn, ρn) is not necessarily (close to) 0 or EX∼P 0 [X 2 ], but if it is then γc is the threshold at which we will observe the all-or-nothing phase transition. In practice, for the examples studied in Section 3 of the main paper, for n large we indeed observe that q * n (γ) → EX∼P 0 [X 2 ] for γ > γc and q * n (γ) → 0 for γ < γc when ρn vanishes. Thus we observe an all-or-nothing phase transition that becomes sharper and sharper as ρn becomes negligible.

C Properties of the mutual informations of the scalar channels
This appendix gives important properties on the mutual informations of the scalar channels defined in Section 2. We first recall the important Nishimori identity that we will use in this appendix and others as well. Lemma 2 (Nishimori identity). Let (X, Y ) ∈ R n 1 × R n 2 be a pair of jointly distributed random vectors. Let k ≥ 1. Let X (1) , . . . , X (k) be k independent samples drawn from the conditional distribution P (X = · |Y ), independently of every other random variables. The angular brackets − denote the expectation operator with respect to P (X = · |Y ), while E denotes the expectation with respect to (X, Y ). Then, for every integrable function g the two following quantities are equal: Proof. This is a simple consequence of Bayes' formula. It is equivalent to sample the pair (X, Y ) according to its joint distribution, or to first sample Y according to its marginal distribution and to then sample X conditionally to Y from its conditional distribution P (X = · |Y ). Hence the (k + 1)-tuple (Y , X (1) , . . . , X (k) ) is equal in law to (Y , X (1) , . . . , X (k−1) , X).
We prove the second point of the lemma by upper bounding the partial derivative of IP out with respect to q. The Lipschitzianity will then follow directly from the mean-value theorem. We denote an expectation with respect to the posterior distribution (33) using the angular brackets − q,ρ, i.e., g(w) q,ρ := g(w)dP (w|V, Y (q,ρ) ).
To prove the third, and last, point of the lemma we will now upper bound the partial derivative of IP out with respect to ρ. Note that Therefore: The second equality follows from Nishimori identity and the third one from integrating by parts with respect to W * . We now define ∀ρ ∈ [0, +∞) : h(ρ) := E ln Z(ρ, ρ) = E[ dy e uy ( √ ρ V ) uy( √ ρ V )]. We have: Combining (34), (40) and (41) yields (ln Z(q, ρ) + 1) The last two summands on the right-hand side of (42) are upper bounded by 4 ϕ 2 ∞ +∆ ∆ 2 ∂xϕ 2 ∞ (see the proof of the second point of the lemma). The first two summands on the right-hand side of (42) involve the function (x, y) → u y (x) + u y (x) 2 . We have: (43) Then, by a direct computation, we obtain: Therefore: This directly implies: We use the formula (43) for u y (x) + u y (x) 2 to get the upper bound: Trivially, Pout(y|x) ≤ 1/ √ 2π∆. This implies while, by Jensen's inequality, we have .
Hence ln Z(q, ρ) + ln(2π∆) 2 Combining (45), (46), (47) yields the following upper bound of the second term on the right-hand side of (42): where C(a, b, c) := b 2 (64a 4 + 6a 2 + 13.5) + c 8a 3 + 2 2 π . This upper bound holds for all q ∈ [0, ρ]. In particular, it holds for the first term on the right-hand side of (42) where q = ρ. We now have an upper bound for each summand on the right-hand side of (42) and we can combine them to get: We can conclude the proof of the third point of the lemma using this last upper bound and the mean-value theorem.

D Properties of the interpolating mutual information
We recall that uy(x) := ln Pout(y|x), and that u y (·) and u y (·) are the first and second derivatives of uy(·). We denote P out (y|x) and P out (y|x) the first and second derivatives of x → Pout(y|x). Finally, the scalar overlap is Q := 1 kn n i=1 X * i xi.
We directly obtain for the derivative of in, (·): where h , f n, are the derivatives of h, fn, . In Lemma 4 of Appendix C, we compute h and show: The first term on the right-hand side of (52) thus satisfies: We now turn to the computation of f n, .
It remains to compute the first kind of expectation on the right-hand side of (59), i.e., The second equality follows from a Gaussian integration by parts w.r.t. Zi ∼ N (0, 1). Plugging the two simplified expectations (64) and (65) back in (59) yields: .
The last step to end the proof of the proposition is to upper bound which appears on the right-hand side of (66).
Upper bouding the quantity (67) Remember that u y (x) + u y (x) 2 = P out (y|x) P out (y|x) and Pout(y|x) = e uy (x) . Therefore, ∀x: where the second equality follows from the direct computation (44) in Lemma 4 of Appendix C. Consequently, using the tower property of the conditionnal expectation, for all µ ∈ {1, . . . , m}: Making use of (68) and Cauchy-Schwarz inequality, we have: Using again the tower property of the conditional expectation gives: Note that conditionally on S (t, ) the random variables P out (Y (t, ) ) mn µ=1 are i.i.d. and centered. Therefore: We now use the formula (43) for u y (x) + u y (x) 2 = P out (y|x) /P out (y|x) (obtained in Lemma 4 of Appendix C) with Jensen's equality to show that for all x: Pout(y|x) .

D.2 Proof of Lemma 1
Proof. At t = 0 the functions r and q do not play any role in the observations (14) since R1(t, ) = 1 and R2(t, ) = 2. While in the main text we restricted to be in Bn := [sn, 2sn] 2 , we can define observations (Y (0, ) , Y (0, ) ) using (14) for t = 0 and ∈ [0, 2sn] 2 . We then extend the interpolating mutual information at t = 0 to all ∈ [0, 2sn] 2 : Note that the variation we want to control in this lemma satisfies: We will upper bound the two terms on the right-hand side of (75) separately.
where h : ρ ∈ [0, +∞) → E V ∼N (0,1) uy( √ ρ V )e uy ( √ ρ V ) dy. The identity (81) can be obtained exactly as the identity (51) in Appendix D.1. Under the assumptions of the lemma, all the hypotheses of domination are reunited to make sure that η → in(η) is continuous on [0, 2sn] and differentiable on (0, 2sn). Therefore, by the mean-value theorem, there exists η * ∈ (0, 2sn) such that: Again, in a similar fashion to the computation of the derivative of in, (·) in Appendix D.1, we can show that ∀η ∈ [0, +∞): In Lemma 4 of Appendix C, we compute h and show: The first term on the right-hand side of (83) thus satisfies: The second term, i.e., f n (ρ) is similar to the quantity A The proof of this uniform bound on Var ln Zη /mn is the same as the one of Proposition 7, only that it is simpler because there is no second channel similar to Y (t, ) . We now combine (82), (83), (85), (86) to finally obtain: 3. We now plug (78) and (87) back in (75) and use that ρn ∈ (0, 1] to end the proof of the lemma:
To lighten notations, we define k1 := R2(t, ), k2 iid ∼ N (0, 1) and W * := (W * µ ) mn µ=1 iid ∼ N (0, 1). Remember that and that, in the interpolation problem, we observe: Zt, is the normalization to the joint posterior density of (X * , W * ) given (Y (t, ) , Y (t, ) , Φ, V ), i.e., where Dw := dwe − w 2 2 √ 2π mn and s (t, ) µ := 1−t kn (Φx)µ + k1 Vµ + k2 wµ. We define: . Therefore, the interpolating free entropy satisfies: (Γ (t, ) From (92), it follows directly that: ln Zt, mn In order to prove Proposition 7, it remains to show that ln Zt, /mn concentrates. We recall here the classical variance bounds that we will use. We refer to [52,Chapter 3] for detailed proofs of these statements. Proposition 8 (Gaussian Poincaré inequality). Let U = (U1, . . . , UN ) be a vector of N independent standard normal random variables. Let g : R N → R be a C 1 function. Then Proposition 9 (Bounded difference). Let U ⊂ R. Let g : U N → R a function that satisfies the bounded difference property, i.e., there exists some constants c1, . . . , cN ≥ 0 such that sup Let U = (U1, . . . , UN ) be a vector of N independent random variables that take values in U. Then Proposition 10 (Efron-Stein inequality). Let U ⊂ R, and a function g : U N → R. Let u = (U1, . . . , UN ) be a vector of N independent random variables with law PU that take values in U. Let U (i) a vector which differs from U only by its i-th component, which is replaced by U i drawn from PU independently of U . Then We first show the concentration w.r.t. all Gaussian variables Φ, V , Z, Z , W * , then the concentration w.r.t. A and finally the one w.r.t. X * . The order in which we prove the concentrations does matter.
We will denote ∂xϕ and ∂xxϕ the first and second partial derivatives of ϕ with respect to its first argument. Note that |R1| ≤ 2sn + αn ρn rmax and, by the inequality (39) in Lemma 4 of Appendix C, rmax := 2 where C2 : Proof. In this proof we see g := lnẐt, /mn as a function of Z and Z, and we work conditionally on all other random variables. We have ∇g 2 = ∇ Z g 2 + ∇ Z g 2 . Each partial derivative has the form ∂ug = m −1 n ∂u Ht, t, . We find: . Applying Proposition 8 yields: The last inequality follows from ρn ≤ 1 and 2sn ≤ 1. Taking the expectation on both sides of this last inequality gives the lemma.
where C4 : Proof. In this proof we see g = E Z, Z ln Zt, /mn as a function of V , W * , Φ and we work conditionally on A, X * . Once again each partial derivative has the form ∂ug = m −1 n ∂u Ht, t, . We first compute the partial derivatives of g w.r.t. {Vµ} mn We thus conclude that g satisfies the bounded difference property: To end the proof of Lemma 7, we just need to apply Proposition 9.
Concentration with respect to the signal Let E ∼X * ≡ E A,G denote the expectation w.r.t. all quenched variables except X * . It remains to bound the variance of E ∼X * lnẐt, /mn (which only depends on X * ).
Proof. g = E[ln Z t, |X * ] /mn is a function of X * . For j ∈ {1, . . . , n}, we have: To get the last equality we use E[Φµj∂xϕ(S Making use of this upper bound, we obtain for all j ∈ {1, . . . , n}: For a fixed j ∈ {1, . . . , n}, let X (j) be a vector such that X (j) i = X * i for i = j and X (j) j ∼ P0,n independently of everything else. By the mean-value theorem and thanks to (105), we have: and Jensen's inequality (a+b) 2 ≤ 2a 2 +2b 2 to get the last inequality. To end the proof it now suffices to apply Proposition 10.

F Concentration of the overlap
In this appendix we prove Proposition 2. Define the average free entropy fn, (t) := 1 mn E ln Zt, . In this section we think of it as a function of R1 = R1(t, ) and R2 = R2(t, ), i.e., (R1, R2) → fn, (t). Similarly, we also view the free entropy for a realization of the quenched variables as a function In this appendix, to lighten the notations, we drop the indices of the angular brackets − n,t, and simply write − . We denote with · the scalar product between two vectors. We define: The fluctuations of the overlap Q := 1 kn X * · x and those of L are related through the inequality: The proof of (108) is based on integrations by parts with respect to Z and a repeated use of the Nishimori identity (see Lemma 2). Proposition 2 is then a direct consequence of the following: Proposition 11 (Concentration of L on E L ). Suppose that ∆ > 0, that all of (H1), (H2), (H3) hold, that EX∼P 0 [X 2 ] = 1 and that the family of functions (r ) ∈Bn , (q ) ∈Bn are regular. Further assume that there exist real positive numbers Mα, M ρ/α , m ρ/α such that ∀n ∈ N * : αn ≤ Mα and m ρ/α n < ρn αn ≤ M ρ/α .
where C is a polynomial in S, ϕ We now turn to the proof of Lemmas 9 and 10. The main ingredient will be a set of formulas for the first two partial derivatives of the free entropy w.r.t. R1 = R1(t, ). For any given realisation of the quenched disorder: 1 mn Averaging (111) yields: To obtain the second equality we simplified E L by using an integration by parts w.r.t. the standard Gaussian random vector Z and E x · X * = E x 2 (by Nishimori identity, see Lemma 2). Averaging (112) and integrating by parts w.r.t. the standard Gaussian random vector Z gives: 1 mn The last inequality follows from sn ≤ 1/2 and (ln 2)/2 < 1. To obtain the second inequality we bounded the partial derivative of the free entropy using (113) and E x 2 ≤ E x 2 = nρn (again by the Nishimori identity): Proof of Lemma 10 We define the two functions: Because of (112), we see that the second derivative of F (R1) is positive so that it is convex. Without the extra term Fn, (t) is not necessarily convex in R1, although fn, (t) is (it can be shown easily). Note that f (R1) is convex too. Convexity allows us to use the following standard lemma: Lemma 11 (A convexity bound). Let G and g be two convex functions. Let δ > 0 and define C δ (x) ≡ g (x + δ) − g (x − δ) ≥ 0. Then: (120) Thanks to (111) and (113) the difference of derivatives (w.r.t. R1) reads: Let δ ∈ (0, sn). Define C δ (R1) := f (R1 + δ) − f (R1 − δ) ≥ 0 (this is well-defined because δ < sn ≤ R1).
Proof. We only give the proof for the ODE y = F 2 (t, y) since the one for the ODE y = αnr /ρn, F (n) 2 (t, y) is simpler and follows the same arguments. By Jensen's inequality and Nishimori identity (see Lemma 2): i.e., E Q n,t,R ∈ [0, 1]. By Lemma 4, the function q → IP out (q, 1) is continuously twice differentiable, concave and nonincreasing on [0, 1]. Therefore, q → −2 ∂I P out/∂q q,ρ=1 is nonnegative and nondecreasing on [0, 1], which implies −2 ∂I P out/∂q q,ρ=1 ∈ [0, rmax]. We have thus shown that the function F : (t, R) → (F  To invoke Cauchy-Lipschitz theorem, we have to check that F is continuous in t and uniformly Lipschitz continuous in R (meaning the Lipschitz constant is independent of t). We can show that F is continuous on Dn and that, for all t ∈ [0, 1], F (t, ·) is differentiable on (0, +∞) × (0, t + 2sn) thanks to the standard theorems of continuity and differentiation under the integral sign. The domination hypotheses are indeed verified because we assume that (H1), (H2) hold. To check the uniform Lipschitzianity, we show that the Jacobian matrix J F (t,·) (R) of F (t, ·) is uniformly bounded in (t, R). For all (R1, R2) ∈ (0, +∞) × (0, t + 2sn), we have: