Phase Transitions, Optimal Errors and Optimality of
Message-Passing in Generalized Linear Models
Jean Barbier†,♦,⊗ , Florent Krzakala? , Nicolas Macris† , Léo Miolane∗,⊗ and Lenka Zdeborová∪

arXiv:1708.03395v2 [cs.IT] 3 Nov 2017

Abstract
We consider generalized linear models (GLMs) where an unknown n-dimensional signal vector is observed through the application of a random matrix and a non-linear (possibly probabilistic) componentwise
output function. We consider the models in the high-dimensional limit, where the observation consists
of m points, and m/n → α where α stays finite in the limit m, n → ∞. This situation is ubiquitous in
applications ranging from supervised machine learning to signal processing. A substantial amount of theoretical work analyzed the model-case when the observation matrix has i.i.d. elements and the components
of the ground-truth signal are taken independently from some known distribution. While statistical physics provided number of explicit conjectures for special cases of this model, results existing for non-linear
output functions were so far non-rigorous. At the same time GLMs with non-linear output functions are
used as a basic building block of powerful multilayer feedforward neural networks. Therefore rigorously
establishing the formulas conjectured for the mutual information is a key open problem that we solve in
this paper. We also provide an explicit asymptotic formula for the optimal generalization error, and confirm the prediction of phase transitions in GLMs. Analyzing the resulting formulas for several non-linear
output functions, including the rectified linear unit or modulus functions, we obtain quantitative descriptions of information-theoretic limitations of high-dimensional inference. Our proof technique relies on
a new version of the interpolation method with an adaptive interpolation path and is of independent interest. Furthermore we show that a polynomial-time algorithm referred to as generalized approximate
message-passing reaches the optimal generalization error for a large set of parameters.

Contents
1 Introduction

2

2 Setting and main results
2.1 Generalized linear estimation: Problem statement . . . . . . . . . . . .
2.2 Two scalar inference channels . . . . . . . . . . . . . . . . . . . . . . .
2.3 Replica-symmetric formula and mutual information . . . . . . . . . . .
2.4 The case of discrete channels . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Optimality of the generalized approximate message-passing algorithm

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

4
4
6
7
8
10

† Laboratoire de Théorie des Communications, Faculté Informatique et Communications, Ecole Polytechnique Fédérale de Lausanne,
Suisse.
♦ Probability and Applications Group, School of Mathematical Sciences, Queen Mary University of London, United-Kingdom.
? Laboratoire de Physique Statistique, CNRS & Université Pierre et Marie Curie & École Normale Supérieure & PSL Université, Paris,
France.
∗ Département d’Informatique de l’ENS, École Normale Supérieure & CNRS & PSL Research University & Inria, Paris, France.
∪ Institut de Physique Théorique, CNRS & CEA & Université Paris-Saclay, Saclay, France.
⊗ Corresponding authors: jean.barbier@epfl.ch, leo.miolane@gmail.com

1

3 Optimal errors in supervised learning
3.1 Teacher-student scenario . . . . . . . . . . . . . . . . . . . .
3.2 Generalization error . . . . . . . . . . . . . . . . . . . . . . .
3.3 Computing the generalization error . . . . . . . . . . . . . .
3.4 Computing the optimal errors with (small) side information

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

11
11
12
12
13

4 Application to concrete situations
15
4.1 Generic observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 Phase diagrams of perfect learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Examples of optimal generalization error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Proof of the replica formula by the adaptive interpolation method
5.1 Interpolating estimation problem . . . . . . . . . . . . . . . . . . .
5.2 Free entropy variation along the interpolation path . . . . . . . . .
5.3 Overlap concentration . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Canceling the remainder . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Lower and upper matching bounds . . . . . . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

23
23
25
26
27
28

Appendix A Some technicalities
A.1 The Nishimori identity . . . . . . . . .
A.2 Some properties of the scalar channels
A.3 Proof of Theorem 2 . . . . . . . . . . .
A.4 Proof of Proposition 1 . . . . . . . . . .
A.5 Boundedness of an overlap fluctuation

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

29
29
29
32
34
35

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

Appendix B Proofs of the limits of optimal errors
36
B.1 Computation of the denoising error: Proof of Corollary 3 . . . . . . . . . . . . . . . . . . . . . 36
B.2 Optimal generalization error with side information: Proof of Proposition 2 . . . . . . . . . . . 37
Appendix C Proof of Proposition 4
37
C.1 Proof of (114) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
C.2 Proof that An vanishes as n → ∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Appendix D Approximation
41
D.1 Relaxing the hypotheses on P0 and Φ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
D.2 Relaxing the hypotheses on ϕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Appendix E A sup-inf formula

45

Appendix F Concentration of free entropy and overlaps
48
F.1 Concentration of the free entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
F.2 Concentration of the overlap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

1 Introduction
Modern statistical analysis and signal processing require solving very high-dimensional estimation problems
with a very large number of parameters. This paradigm arises in problems as diverse as learning with neural
networks [54] and regression problems [22] or compressed sensing in signal processing [24, 30]. Developing
algorithms up to these tasks, and understanding their limitations, has become a major challenge in computer
science, machine learning and statistics.

2

In many examples, it has been empirically observed that both the inference and learning tasks appear
to have intrinsic limitations when the available data becomes too scarce or too noisy. In some cases these
apparent thresholds are related to information-theoretic phenomena: There is simply not enough information
in the dataset. This is the case, as famously discussed by Shannon in his seminal paper on communication
theory [74], for the task of reconstructing a noisy signal when the noise is beyond the so-called Shannon
capacity of the communication channel. In many situations, including communications, there also seem to
exist jumps in the computational hardness, beyond which the most sophisticated known algorithms take
exponential time to solve the task: In this case the problem has become too complicated to be solved efficiently.
A substantial amount of work suggests that one can understand and locate these fundamental barriers in a
range of statistical models by thinking of them as phase transitions in the sense of physics. In fact, over
the last three decades or so, a large body of interdisciplinary work in the statistical physics community has
been applied to such problems [32,34,35,59,60,65,73,81,84] considering random instances, generated by given
statistical models, and then locating these phase transitions. Such models are in fact being widely used in fields
as diverse as (without any pretension of exhaustivity) statistical learning [3,17,28,33,38], compressed sensing
and signal processing [9, 11, 21, 29, 31, 55, 56, 62, 70, 84], communication theory [6, 12, 15, 41, 77], community
detection in networks [2, 23, 27, 51], combinatorial optimization problems [7, 50, 59] or to model the behavior
of neurons or neural nets [4, 5, 73, 81].
Many of these works, especially in the context of compressed sensing and machine learning, relied however on non-rigorous methods, using instead powerful heuristics like the replica and cavity approaches [60].
In the present contribution we leverage on these pioneering works and provide instead rigorous asymptotic
predictions in the case of generalized linear estimation models [64]. This includes a range of statistical models
of interest in many scientific fields such as random linear estimation in statistics, the teacher-student singlelayer perceptron problem, probit classification or quantized compressed sensing. For all these estimation and
learning problems our results completely vindicate the physics results —closing in some cases conjectures
open since almost three decades [16, 36, 42]— and considerably extend them. We also establish the value of
the generalization error after an optimal learning, which gives a bound on how accurately any algorithm is
able to predict outcome values for previously unseen data.
We compare the optimal results with the algorithmic ones provided by message-passing algorithms [31,70,
84] and observe that, while optimal performances are often thought to be intractable, in the present setting
they can actually be obtained using a polynomial-time scheme for a large set of parameters. There exists,
however, an interesting region of parameters where all so far known algorithms fail to provide a satisfactory
answer to the estimation and learning problems, while it is nevertheless information-theoretically possible
to do so. In this case there is a significant gap between what currently known polynomial algorithms can do
and what should be expected from the information-theoretic point of view.
Finally, our proof technique has an interest on its own. It exploits a powerful new technique called the
adaptive1 interpolation method [13] that is applicable to many other open problems in statistical estimation.
We informally summarise our main contributions here:
• We consider generalized linear estimation models where, given an unknown signal vector X∗ , one is

given the measurement vector Y = ϕ √1n ΦX∗ , with Φ a known random matrix with i.i.d. entries of
zero mean, and where ϕ (that can be probabilistic) acts componentwise.
• Our first main result is the rigorous determination of the expression of the (conditional) entropy H(Y|Φ)
of the observation variable, a quantity often called “the averaged free energy” in the statistical physics
literature, in the “high-dimensional regime” where the signal dimensionality n as well as the number of
In [13] the method involves a discrete time stochastic process and is called “stochastic interpolation method.” For dense graphical problems one can easily take a continuum limit in which the stochastic process does not appear explicitly and the method is
better called “adaptive interpolation method.”
1

3

observations m are jointly growing such that m/n → α > 0. As we shall see, many statistical quantities of interest, such as the mutual information between the observation and the unknown signal or
the Bayes-optimal generalization error, can be computed from this expression. We provide the proof of
this expression —which is our main technical contribution— in the last section. Only the simple linear
case was known rigorously so far [10, 14, 71], whereas including the non-linearity is an absolutely key
element towards building more powerful multilayer neural networks.
In fact, our results cover a number of cases discussed in the literature, often anticipated by statistical
physics techniques, and allow to rigorously prove many predictions obtained by the heuristic replica
method. The expression for the entropy was first famously conjectured in 1989 in [36] for the particular
case of ϕ(x) = sgn(x), a work that is at the basis of many significant developments. The generic
formula was also recently conjectured on the same heuristic basis [84]. Our proof yields a spectacular
confirmation of the cavity and replica methods.
• We demonstrate (with the technical assumption of the presence of small side-information, which is
equivalent to the presence of a small vanishing magnetic field in physics) the formula for the minimum
mean-square-error (MMSE) for the reconstruction of the unknown signal in the generalized linear estimation model.
• We also compute (under the same technivcal assumption) the Bayes-optimal generalization error in the
context of a supervised learning task of a rule used by the model (the so-called teacher-student setting). This estimator is optimal in the sense that it minimizes the label (the value of the output of ϕ)
mean-square-error among all possible student estimators. Again, this formula was anticipated with the
heuristic cavity and replica methods, and was proposed, for the restricted case ϕ(x) = sgn(x) (the
so-called perceptron problem), in pioneering works in the statistical physics community [42, 66, 73].
• While these results are information-theoretic, we also consider the performance of a well-known algorithm to solve random instances of generalized linear estimation problems, called generalized approximate message-passing (GAMP [31, 70, 84]). This algorithm, which also originated from statistical
physics [5, 46, 58, 78], is expected to be particularly powerful on these random instances, as proven for
instance for compressed sensing [14, 31, 52, 79]. Indeed we show that, for a large set of problems and
a large region of parameters, GAMP yields an optimal generalization error. There exists, however, a
region of parameters where GAMP does not reach the optimal results. It remains a challenging open
problem whether a polynomial algorithm that outperforms GAMP in this region exists.
• Finally, we study in depth the situation for many given choices of the function ϕ, and identify sharp
phase transitions and novel phase diagrams. By locating these transitions we clarify the difficulties
and challenges in solving complex non-linear high-dimensional statistical problems in many modelsituations, and characterize these problems in terms of optimal information-theoretical reconstruction.

2 Setting and main results
2.1

Generalized linear estimation: Problem statement

We now give a generic description of the observation model. Note that we describe here an estimation (or
inference) problem. In the title of the paper, we refer to generalized linear models. This is a very general
setting that will allow us to consider supervised learning problems (see Sec. 3). Precise hypotheses are given
below in Sec. 2.3.

4

Let n, m ∈ N∗ . Let P0 be a probability distribution over R and let (Xi∗ )ni=1 i.i.d.
∼ P0 be the components
i.i.d.
∗
∗
of a signal vector X (this is also denoted X ∼ P0 ). We fix a function ϕ : R × RkA → R and consider
i.i.d.
kA
(Aµ )m
µ=1 ∼ PA , where PA is a probability distribution over R , kA ∈ N. We acquire m measurements
through
 √
 1
Yµ = ϕ √ [ΦX∗ ]µ , Aµ + ∆Zµ ,
n

(1)

1 ≤ µ ≤ m,

i.i.d.
where (Zµ )m
µ=1 ∼ N (0, 1) is an additive Gaussian noise, ∆ > 0, and Φ is a m × n measurement matrix with
i.i.d. Φµi ∼ N (0, 1) entries (this hypothesis will actually be relaxed, see Sec. 2.3). The estimation problem
is to recover X∗ from the knowledge of Y = (Yµ )m
of the random
µ=1 , ϕ, Φ, ∆, P0 and PA (the realization
Pn
∗
stream A itself, if present in the model, is unknown). We use the notation [ΦX ]µ = i=1 Φµi Xi∗ . When
ϕ(x, A) = ϕ(x) = x we have a random linear estimation problem, whereas if, say, ϕ(x) = sgn(x) we
have a noisy single layer perceptron. Sec. 3 discusses various examples related to non-linear estimation and
supervised learning.
It is also fruitful to think of the measurements as the outputs of a “channel”,



1
Yµ ∼ Pout · √ [ΦX∗ ]µ
n

(2)

where the transition density, with respect to (w.r.t.) Lebesgue’s measure, is
Z

1
1
2
Pout y x = √
dPA (a)e− 2∆ (y−ϕ(x,a)) .
2π∆

(3)

Our hypotheses ensure that this is a well defined density. In fact (3) is sometimes called a “random function
representation” of a transition kernel. Our analysis uses both representations (1) and (2).
Throughout this paper we often adopt the language of statistical mechanics. In particular the random
variables Y (and also Φ, X∗ , A, Z) are called quenched variables because once the measurements are acquired
they have a “fixed realization.” An expectation taken w.r.t. all quenched random variables appearing in an
expression will simply be denoted by E without subscript. Subscripts are only used when the expectation
carries over a subset of random variables appearing in an expression or when some confusion could arise.
A fundamental role is played by the joint posterior distribution of (the signal) x and of (the random stream)
a given the quenched measurements Y (recall that X∗ , A and Z are unknown). The prior over the signal is
Q
Q
denoted dP0 (x) = ni=1 dP0 (xi ), and similarly dPA (a) = m
µ=1 dPA (aµ ). According to the Bayes formula
this joint posterior is given by
m

dP (x, a|Y, Φ) =

Y
1
1
− 1
√
dP0 (x)dPA (a)
e 2∆
Z(Y, Φ)
2π∆
µ=1

2

Yµ −ϕ( √1n [Φx]µ ,aµ )

,

(4)

where the partition function (the normalization factor) is defined as
Z
Z(Y, Φ) :=

m
Y

1
− 1
√
dP0 (x)dPA (a)
e 2∆
2π∆
µ=1

5

2

Yµ −ϕ( √1n [Φx]µ ,aµ )

.

(5)

Marginalizing (4) w.r.t. a yields the posterior of x, namely
1
dP0 (x)e−H(x;Y,Φ) ,
Z(Y, Φ)
Z
Z(Y, Φ) = dP0 (x)e−H(x;Y,Φ) ,

dP (x|Y, Φ) =

(6)
(7)

where the Hamiltonian is defined as
H(x; Y, Φ) := −

m
X



1
ln Pout Yµ √ [Φx]µ .
n
µ=1

(8)

From the point of view of statistical mechanics (6) is a Gibbs distribution and the integration over dP0 (x) in
the partition function is best thought as a “sum over annealed or fluctuating degrees of freedom” (note that in
the representation (5), (aµ )m
µ=1 also play the role of annealed variables). Let us introduce a standard statistical
mechanics notation for the expectation w.r.t. the joint posterior (4), the so called Gibbs bracket h−i defined as
Z
hg(x, a)i := dP (x, a|Y, Φ)g(x, a)
(9)
for any continuous bounded function g. The main quantity of interest here is the associated averaged free
entropy (or minus the averaged free energy)
fn :=

1
E ln Z(Y, Φ) .
n

(10)

It is perhaps useful to stress that Z(Y, Φ) is nothing else than the density of Y conditioned on Φ so we have
the explicit representation (used later on)
Z
1
fn = EΦ dYZ(Y, Φ) ln Z(Y, Φ)
n
Z
Z
1
∗
(11)
= EΦ dYdP0 (X∗ )e−H(X ;Y,Φ) ln dP0 (x) e−H(x;Y,Φ) ,
n
Q
where dY = m
µ=1 dYµ . Thus fn is minus the conditional entropy −H(Y|Φ)/n of the measurements.
One of the main contributions of this paper is the derivation, thanks to the adaptive interpolation method,
of the thermodynamic limit limn→∞ fn in the “high-dimensional regime”, namely when n, m → ∞ while
m/n → α > 0 (α is sometimes referred to as the “measurement rate” in compressed sensing terminology).

2.2

Two scalar inference channels

An important role in our proof of the asymptotic expression of the free entropy is played by simple scalar
inference channels. As we will see, the free entropy is expressed in terms of the free entropy of these channels.
This “decoupling property” results from the mean-field approach in statistical physics, used through in the
replica method to perform a formal calculation of the free entropy of the model [59,60]. Let us now introduce
these two scalar denoising models.
The first one is an additive Gaussian channel. Let r ≥ 0, which plays the role of a signal-to-noise ratio
(snr). Suppose that X0 ∼ P0 and that we observe
Y0 =

√

r X 0 + Z0 ,

(12)

where Z0 ∼ N (0, 1) independently of X0 . Consider the inference problem consisting of retrieving X0 from
6

the observations Y0 . The associated posterior distribution is
√

2

dP0 (x)e r Y0 x−rx /2
√
.
dP (x|Y0 ) = R
dP0 (x)e r Y0 x−rx2 /2

(13)

In this expression all the x-independent terms have been simplified between the numerator and the normalization. The free entropy associated with this channel is just the expectation of the logarithm of the
normalization factor
Z
√
2
ψP0 (r) := E ln dP0 (x)e r Y0 x−rx /2 .
(14)
The basic properties of ψP0 are presented in Appendix A.2.1.
The second scalar channel that appears naturally in the problem is linked to the transition kernel Pout
through the following inference model. Suppose that V, W ∗ i.i.d.
∼ N (0, 1) where V is known while the inference
∗
problem is to recover the unknown W from the following observation

√
√
Ye0 ∼ Pout · | q V + ρ − q W ∗ ,

(15)

where ρ > 0, q ∈ [0, ρ] and Pout is the transition density defined in (3). The free entropy for this model, again
related to the normalization factor of the posterior dP (w|Ye0 , V ), is
Z

√
√
(16)
ΨPout (q; ρ) = ΨPout (q) := E ln DwPout Ye0 | q V + ρ − q w ,
2

where Dw = dw(2π)−1/2 e−w /2 is the standard Gaussian measure. We prove in Appendix A.2.2 that this
function is convex, differentiable and non-decreasing w.r.t. its first argument.
√
√
√
Recall that we consider here Pout to be of the form (3), so that Ye0 = ϕ( q V + ρ − q W ∗ , A) + ∆Z,
where A ∼ PA and Z ∼ N (0, 1), independently of any other random variable. In the sequel, the joint
posterior distribution of (W ∗ , A) given (V, Ye0 ) will be particularly useful, so we define the Gibbs bracket for
the scalar channel (15) by:
1

e− 2∆

Z
hg(w, a)isc =

DwdPA (a)
R

2
√
√
Ye0 −ϕ( q V + ρ−q w,a)
2
√
√
1
− 2∆
Ye0 −ϕ( q V + ρ−q w,a)

g(w, a) ,

(17)

DwdPA (a)e

for any continuous bounded function g.

2.3

Replica-symmetric formula and mutual information

Let us now introduce our first main result, a single-letter replica-symmetric formula for the asymptotic free
entropy of model (1), (2). The result holds under the following rather general hypotheses. We will consider
two cases: The case where the entries of Φ are i.i.d. standard Gaussian random variables and the case of
general distributions. This leads to two sets of hypotheses.
(h1) The prior distribution P0 admits a finite second moment and has at least two points in its support.
(h2) There exists γ > 0 such that the sequence (E[|ϕ( √1n [ΦX∗ ]1 , A1 )|2+γ ])n≥1 is bounded.
(h3) (Φµi ) i.i.d.
∼ N (0, 1).
In the non-Gaussian case, the hypothesis (h3) has to be replaced by the following hypotheses:
(h3.a) The prior distribution P0 admits a finite third moment.
7

(h3.b) The random variables (Φµi ) are independent with zero mean, unit variance and finite third moment
that is bounded with n.
(h3.c) For almost-all values of a ∈ RkA (w.r.t. PA ), the function x 7→ ϕ(x, a) is continuous almost everywhere.
Let us define the replica-symmetric potential (or just potential). Call ρ := E[(X ∗ )2 ] where X ∗ ∼ P0 . Then
the potential is
fRS (q, r; ρ) = fRS (q, r) := ψP0 (r) + αΨPout (q; ρ) −

rq
.
2

(18)

We define also fRS (ρ, +∞) = limr→∞ fRS (ρ, r). From now on denote ψP0 0 (r) and Ψ0Pout (q) = Ψ0Pout (q; ρ)
the derivatives of ψP0 (r) and ΨPout (q; ρ) w.r.t. their first argument. We need also to define the set of the
critical points of fRS :
(
)
q = 2ψP0 0 (r)
Γ := (q, r) ∈ [0, ρ] × (R+ ∪ {+∞})
,
(19)
r = 2αΨ0Pout (q; ρ)
where, with a slight abuse of notation, we define ψP0 0 (+∞) = limr→∞ ψP0 0 (r) and Ψ0Pout (ρ) = limq→ρ Ψ0Pout (q).
These limits are well defined by convexity of ψP0 and ΨPout . The elements of Γ are called “fixed points of the
state evolution”. The main theorem of this paper is
Theorem 1 (Replica-symmetric formula). Suppose that hypotheses (h1) and (h2) hold. Suppose that either (h3)
or (h3.a)-(h3.b)-(h3.c) hold. Then, for the generalized linear estimation model (1), (2) the thermodynamic limit of
the free entropy (10) verifies
f∞ := lim fn = sup inf fRS (q, r) = sup fRS (q, r) .
n→∞

q∈[0,ρ] r≥0

(20)

(q,r)∈Γ

Moreover, the “sup inf” and the supremum over Γ in (20) are achieved over the same couples.
An immediate corollary of Theorem 1 is the limiting expression of the mutual information between the
observations and the hidden variables.
Corollary 1 (Single-letter formula for the mutual information). The thermodynamic limit of the mutual information for model (1), (2) between the observations and the hidden variables verifies
in :=

1
α
I(X∗ , A; Y |Φ) −−−→ i∞ := −f∞ − (1 + ln(2π∆)) .
n→∞
n
2

(21)

Proof. This follows from a simple calculation:
1
P (Y, X∗ , A|Φ)
1
1
I(X∗ , A; Y|Φ) = E ln
= − E ln P (Y|Φ) + E ln P (Y|X∗ , A, Φ)
∗
n
P (Y|Φ)P (X , A|Φ)
n
n
m
X
1
m
= −fn −
(Yµ − ϕ([ΦX∗ ]µ , Aµ ))2 −
E
ln(2π∆)
2n∆
2n
µ=1

m
m
= −fn −
−
ln(2π∆) .
2n 2n

2.4

(22)

The case of discrete channels

A natural question to ask now is: Can we extend the previous results without the Gaussian noise in (1)? This
question seems to be non-trivial for various reasons. First, without the “regularizing” Gaussian noise, the
8

transition kernel Pout may not have a density w.r.t. Lebesgue’s measure: How should we define the “entropylike” quantities that we study? Second, even in the situation where the transition kernel admits a density,
it seems not totally obvious to justify the ∆ → 0 limit in Theorem 1. This is mostly due to the fact that
Shannon’s entropy is not continuous w.r.t. the weak convergence, see for instance [69]. The results of [69]
provide sufficient conditions that the densities should verify in order to have convergence of the entropies.
So it should be possible to take the ∆ → 0 limit in Theorem 1 at the cost of additional technical assumptions,
but we prefer for simplicity to only consider discrete transition kernels.
Therefore, in this section we assume that ϕ takes its values in a finite set. We suppose also that hypotheses (h1) and (h2) hold, and that either (h3) or (h3.a)-(h3.b)-(h3.c) hold.
We define
ξn :=

1
E ln
n

Z
dP0 (x)dPA (a)

m  

 1

Y
1
δ ϕ √ [ΦX∗ ]µ , Aµ − ϕ √ [Φx]µ , aµ ,
n
n
µ=1

(23)

and for q ∈ [0, ρ],
Z
Ψϕ (q) = E ln


√
√
√
√
dPA (a)Dw δ ϕ( q V + ρ − q W, A) − ϕ( q V + ρ − q w, a) ,

(24)

where V, W i.i.d.
∼ N (0, 1) and A ∼ PA are independent random variables.
Theorem 2 (Replica-symmetric formula for discrete channels). Suppose that hypotheses (h1) and (h2) hold.
Suppose that either (h3) or (h3.a)-(h3.b)-(h3.c) hold. Then, for the generalized linear estimation model (1) with
∆ = 0 and an output function ϕ taking values in a finite set, the thermodynamic limit of the free entropy (23)
verifies
n
rq o
.
(25)
ξn −−−→ sup inf ψP0 (r) + αΨϕ (q) −
n→∞ q∈[0,ρ] r≥0
2
The proof of Theorem 2 is presented in Appendix A.3.
As an application of Theorem 2 we can compute the free energy of the “planted perceptron” on the hypercube and the sphere. This perceptron model has already been studied in physics [36] and more recently
in statistics, where it is known as “one-bit compressed sensing” [21, 83]. The limit of the free entropy follows from an application of Theorem 2 with ϕ(x) = sgn(x) and P0 = 21 δ−1 + 12 δ1 (for the hypercube) or
P0 = N (0, 1) (for the sphere). For µ ∈ {1, . . . , m}, we define
n
o
Sµ = x ∈ Rn sgn(x · Φµ ) = sgn(X∗ · Φµ ) .
(26)
We will use the notation N (x) = P(Z ≤ x) for Z ∼ N (0, 1). Let Sn be the unit sphere in Rn and µn the
uniform measure on Sn .
Corollary 2 (Free entropy of the planted perceptron). Let Z, V ∼ N (0, 1).
m
 \

1
E ln #
Sµ ∩ {−1, 1}n
n
µ=1
n
h  √q V 
 √q V i r(q + 1) o
√
√
ln N √
−
−−−→ ln(2) + sup inf E ln cosh( rZ + r) + 2αE N
, (27)
n→∞
2
1−q
1−q
q∈[0,1) r≥0
m
\

n1
h  √q V 
 √q V i q o
1
E ln µn
Sµ ∩ Sn −−−→ sup
ln(1 − q) + 2αE N √
ln N √
+
.
(28)
n→∞ q∈[0,1) 2
n
2
1
−
q
1
−
q
µ=1

9

2.5

Optimality of the generalized approximate message-passing algorithm

While the main results presented until now are information-theoretic, our next one concerns the performance of a popular algorithm to solve random instances of generalized linear problems, called generalized
approximate message-passing (GAMP). We shall not re-derive its properties here, and instead refer to the original papers for details. This approach has a long history, especially in statistical physics [5, 46, 58, 78], error
correcting codes [72], and graphical models [80]. For a modern derivation in the context of linear models,
see [31, 52, 79]. The case of generalized linear models was discussed by Rangan in [70], and has been used for
classification purpose in [85].
We first need to define two so-called threshold functions that are associated to the two scalar channels
(12) and (15). The first one is the posterior mean of the signal in channel (12) with signal-to-noise ratio r:
gP0 (y, r) = E[X0 |Y0 = y] .

(29)

The second one is the posterior mean of W ∗ in channel (15) with “noise level” η = ρ − q:
√
gPout (e
y , v, η) = E[W ∗ |Ye0 = ye, q V = v] .

(30)

These functions act componentwise when applied to vectors.
Given initial estimates (b
x0 , v0 ) for the means and variances of the elements of the signal vector X∗ ,
GAMP takes as input the observation vector Y and then iterates the following equations with initialization
gµ0 = 0 for all µ = 1, . . . , m (we denote by u the average over all the components of the vector u and Φ| is
the transpose of the matrix Φ): From t = 1 until convergence,


V t = vt



t = Φb
t−1 /√n − V t gt−1

ω
x



t
t
t


∀ µ = 1, . . . m
 gµ = gPout (Yµ , ωµ , V )
t
2
t
t
(31)
λ
= α gPout (Y, ω , V )

√

t
t−1
t
|
t

b
R = x
+λ Φ g / n



t
t t

x
b
=
g
(R
∀ i = 1, . . . n

P0
i
i, λ )


 vt = (λt )−1 ∂ g (R, λt )|
∀ i = 1, . . . n
R P0
R=Rit
i
One of the strongest asset of GAMP is that its performance can be tracked rigorously in the limit n, m → ∞
via a procedure known as state evolution (SE), see [18, 19] for the linear case, and [45, 70] for the generalized
one. In our notations, state evolution tracks the asymptotic value of the overlap between the true hidden
bt defined as q t = limn→∞ X∗ · x
bt /n (that is related to the asymptotic
value X∗ and its estimate by GAMP x
bt by E t = ρ − q t , where recall that ρ = E[(X ∗ )2 ] with
mean-square error E t between X∗ and its estimate x
∗
X ∼ P0 ) via:
(
q t+1
rt

= 2ψP0 0 (rt ) ,
= 2αΨ0Pout (q t ; ρ) .

(32)

From Theorem 1 we realize that the fixed points of these equations correspond to the critical points of the
asymptotic conditional entropy in (20). In fact, in the replica heuristic, the optimizer q ∗ of the potential is
conjectured to give the optimal value of the overlap, a fact that was proven for the linear channel [10, 14]. If
the minimizer of (20) is unique, or is attractive within the GAMP dynamics, then q t converges to q ∗ when
t → +∞.
Perhaps more surprisingly, one can use GAMP in the teacher-student scenario (that we precisely describe
√
in Sec. 3.1) in order to provide an estimation of a new output Cnew = ϕ(Φnew ·X∗ / n, Anew ), where Φnew is
10

bt is the GAMP estimate of the expectation
a new row of the matrix and Anew ∼ PA a new random source. As x
of X∗ , with estimated variance vt , the natural heuristic is to consider for the posterior probability distribution
√
√
bt / n and variance V t = E t = ρ − q t
of the random variable Φnew · X∗ / n a Gaussian with mean Φnew · x
(the fact that the variance and MSE are equal follows from the Nishimori identity of Proposition 9 applied
to GAMP, see e.g. [84]). This allows to estimate the posterior mean of the output, which leads the GAMP
prediction (recall the Pout definition (3)):
b GAMP,t =
C

Z

1

e
dy dw y Pout (y|w) p
2π(ρ − q t )

1
− 2(ρ−q
t)

√1 Φnew ·b
xt −w
n

2
.

(33)

We show in Sec. 3.3.2 that this leads to a GAMP generalization error given by

 
GAMP,t
b GAMP,t 2
:= lim E Cnew − C
Egen
n→∞
p
 √


 p
2 
= EV,A ϕ( ρ V, A)2 − EV EW,A ϕ( q t V + ρ − q t W, A) ,

(34)

where V, W i.i.d.
∼ N (0, 1) and A ∼ PA .
We will see in Sec. 3.2 that this formula matches the one for the Bayes-optimal generalization error, see
(40), up to the fact that instead of q ∗ (a maximizer obtained from the replica formula (20)) appearing in the
optimal error formula, here it is q t which appears. Thus clearly, when q t converges to q ∗ (we shall see that this
is the case in many situations in the examples of Sec. 4) this yields a very interesting and non trivial result:
GAMP achieves the Bayes-optimal generalization error in a plethora of models (a task again often believed to
be intractable) and this for large sets of parameters.

3 Optimal errors in supervised learning
3.1

Teacher-student scenario

Consider the following teacher-student scenario (also called planted model). We voluntarily employ terms
coming from machine learning, instead of the signal processing terminology used in the previous sections.
First the teacher randomly generates a classifier X∗ ∈ Rn (the signal in the estimation problem) with
i.i.d.
n
X∗ i.i.d.
∼ P0 , an ensemble of m = αn patterns (row-vectors) Φµ ∈ R for µ = 1, . . . , m such that Φµ ∼
i.i.d.
N (0, In ), and a stream A = (Aµ )m
µ=1 ∼ PA . The teacher chooses a model ϕ(x, A). For deterministic
models A is simply absent. Finally the teacher associates to each pattern a label Cµ ∈ R selected by the
√
classifier, namely Cµ = ϕ(Φµ · X∗ / n, Aµ ) for µ = 1, . . . , m. Stacking the rows (Φµ )m
µ=1 in a m × n
m
matrix Φ and denoting the vector of labels C = (Cµ )µ=1 , then the labels, patterns, source of randomness and
classifier verify
 1

C = ϕ √ ΦX∗ , A ,
n

(35)

where it is understood that ϕ acts in componentwise fashion on vectors. The student is given the distributions
P0 , PA and the function ϕ and his task is to learn the classifier X∗ from the pattern-label pairs (Φµ , Cµ )m
µ=1 .
∗
How does one use this estimation to perform prediction? The teacher, still using the same X , will create
a new sample (and thus a new line of the matrix, or pattern, Φnew and a new random Anew ). The teacher
√
will first compute the new value of the projection of X∗ , that we denote znew = Φnew · X∗ / n, and then
generate the new random label Cnew = ϕ(znew , Anew ). He is now ready to evaluate the student generalization
performance.

11

3.2

Generalization error

An important quantity is the generalization error (or prediction error) which measures the performance of the
b new , C, Φ) the estimator used by the student (which is thus a measurable function
student. If we denote C(Φ
of the observations), the generalization error is defined as
h
2 i
b = E Cnew − C(Φ
b new , C, Φ)
Egen (C)
.

(36)

The optimal generalization error is then defined as the minimum of Egen over all estimators:
h
D 
E2 i
opt
b = E Cnew − ϕ √1 Φnew · x, a
:= min Egen (C)
Egen
.
n
b
C

(37)

where x is sampled according to the posterior distribution P (x = X∗ |C, Φ) and a ∼ PA . h−i denotes the
joint expectation w.r.t. (x, a).

3.3

Computing the generalization error

In order to express the limit of the generalization error, we introduce the following function:


 √
2 
 √
√
E : q 7→ E ϕ( ρ V, A)2 − E EW,A ϕ( q V + ρ − q W, A)

(38)

where V, W i.i.d.
∼ N (0, 1), A ∼ PA are independent random variables and EW,A denotes the expectation w.r.t.
W and A only. We recall ρ = E[(X ∗ )2 ].
3.3.1

Optimal generalization error

opt
The computation of the limit of Egen
is not trivial and requires a good knowledge of the posterior distribution.
In Sec. 3.4.1 we will show that under a small perturbation of the model (given some side information), one can
compute it rigorously. Here we only show that if the overlap between the planted solution X∗ and a sample (a
replica) x from the posterior distribution converges to some number q, then the optimal generalization error
converges to E(q).

Proposition 1. Assume that the overlap n1 x · X∗ converges in probability to some number 0 ≤ q < ρ. Then
opt
Egen
−−−→ E(q) .
n→∞

(39)

The proof of Proposition 1 is presented in Appendix A.4. This result by itself does not tell us how to
compute q. But in view of Proposition 2 we expect that q = q ∗ the maximizer of (20).
Conjecture 1 (Optimal generalization error). For almost all ∆ > 0 we have
opt
Egen
−−−→ E(q ∗ ) ,
n→∞

(40)

where q ∗ is a maximizer of (20).
The optimal generalization error is independent of the random function representation as long as both ϕ
√
R
R
and PA are known. EX dY Y k Pout (Y |X) = EX,a dY Y k exp{−(Y − ϕ(X, a))2 /(2∆)}/ 2π∆ implies
that the error (40) can be re-expressed equivalently as a function of the two first moments of the transition
probability Pout , namely (again, q ∗ is a maximizer of (20))
Z
h hZ
i2 i
p
p
√
opt
−−−→ EV
dY Y 2 Pout (Y | ρ V ) − EV Ew
dY Y Pout (Y | q ∗ V + ρ − q ∗ w)
− ∆ . (41)
Egen
n→∞

12

3.3.2

Generalization error of the generalized approximate message-passing algorithm

We now turn our attention to the generalization performance of the GAMP algorithm of Sec. 2.5. The following claim is from [70], where it is stated as a claim because some steps of the proof are missing. The paper [45]
affirms in its abstract to prove the claim of [70], but without further details. For these reasons, we believe that
the claim holds, however we prefer to state it here as a claim (instead of a theorem).
Claim 1 ( [70]). We have almost surely for all t ∈ N,
lim

n→∞

1 t
1 t 2
b · X∗ = lim kb
x
x k = qt .
n→∞
n
n

(42)

Provided that Claim 1 holds, we can deduce the generalization error of GAMP.
b GAMP,t is given by (33). Then
Claim 2 (GAMP generalization error). Recall that C

 
GAMP,t
b GAMP,t 2 = E(q t ) .
:= lim E Cnew − C
Egen
n→∞

(43)

Claim 2 is proved following the same proof strategy as for Proposition 1, see Appendix A.4.
3.3.3

Optimal denoising error

Another interesting error measure to study is the following “denoising error”. Assume that the observations

are noisy, as in (1). The goal here is to denoise the observations Yµ and estimate the signal ϕ √1n [ΦX∗ ]µ , Aµ .
The minimum denoising error (in L2 sense) is actually a simple corollary from the replica-symmetric
formula of Theorem 1 and follows from a so-called “I-MMSE relation”, see [40].
Corollary 3 (Limit of the optimal denoising error). For almost every ∆ > 0, for any optimal couple (q ∗ , r∗ )
of (20) we have
 D  1
E 2 i
1 h  1
E ϕ √ ΦX∗ , A − ϕ √ Φx, a
n→∞ m
n
n
p
p



 √
= E ϕ( ρ V, A)2 − E ϕ( q ∗ V + ρ − q ∗ w, a)i2sc ,
lim

(44)

where the Gibbs brackets are defined by (9) and (17) and V ∼ N (0, 1), (w, a) ∼ h−isc .
The proof of Corollary 3 is presented in Appendix B.1.

3.4
3.4.1

Computing the optimal errors with (small) side information
Optimal generalization error with side information

As presented in Sec. 3.3.1, the computation of the optimal generalization error requires a good knowledge of
the posterior distribution, typically that the overlap concentrates around a deterministic value. Proving this
kind of result seems to be highly non-trivial. An easier strategy would be to proceed as in the previous section
by using “I-MMSE relations”: Differentiating the free entropy fn w.r.t. the model parameters allows to access
interesting quantities.
However, in order to obtain an expression for the generalization error, we need to assume that the new
“test label” Cnew is also observed by the student in the scenario of Sec. 3.1 but with a large amount of noise, so
that we can differentiate fn w.r.t. this noise. For this reason we introduce the following “train-test” observation
model.
The set of rows of Φ and labels are divided into two sets by the teacher: The training set S tr of size βm, β ∈
[0, 1], that will be used by the student in order to learn the classifier, and the test set S te of size (1 − β)m that
13

will be used by the teacher in order to evaluate the performance of the student. For the training
the
√ set both βm
tr
tr
patterns and associated noisy labels are given to the student, namely S = {(Yµ = Cµ + Zµ ∆ ; Φµ )}µ=1
where Zµ ∼ N (0, 1) (recall the labels are given by (35)). Here ∆tr is strictly positive (but typically small)
and known by the student who can thus optimally tune its “confidence” in the training labels during the
training/learning stage. For the test set, the previously unseen patterns
to classify are given to the student
√
te
te
te
but the labels are (almost) not, namely S = {(Yµ = Cµ + Zµ ∆ ; Φµ )}m
µ=βm+1 where ∆ is typically
te
very large. We are particularly interested in the case ∆ → ∞ when the student has no information about
the labels of the test set but for the aforementioned technical reasons we will have to work with very large,
but finite, ∆te .
Define ∆µ = ∆tr if µ ≤ βm, ∆µ = ∆te else. Then the inference of the classifier X∗ from the noisy
p
labels Yµ = Cµ + Zµ ∆µ is a slight extension of model (1): This inference problem is nothing else than
te = (Φ )m
a supervised learning of the classifier by the student. Define Cte = (Cµ )m
µ µ=βm+1
µ=βm+1 and Φ
as the m(1 − β)-dimensional vector of labels and the m(1 − β) × n matrix, respectively, both restricted to
te
the test set and similarly for Ate = (Aµ )m
µ=βm+1 . Then the optimal generalization error at finite ∆ in this
“train-test” observation model is
h
D  1
E 2 i
1
side
:=
Egen
E Cte − ϕ √ Φte x, ate
(1 − β)m
n
 D  1
E 2 i
h  1
1
.
(45)
E ϕ √ Φte X∗ , Ate − ϕ √ Φte x, ate
=
(1 − β)m
n
n
Here the Gibbs bracket h−i is associated to the joint posterior (4) but with ∆ replaced by ∆µ in order to
take into account that the noise varies in the training and test sets. Moreover ate is the restriction of a to its
components belonging to the test set, namely ate = (aµ )m
µ=βm+1 .
By a straightforward extension of the interpolation method presented in Sec. 5 one can generalize Theorem 1 to take into account that the noise variance ∆µ differs in the training and test sets. This leads to an
asymptotic free entropy rigorously given by
n
rq o
ts
ts
tr (q; ρ) + α(1 − β)ΨP te (q; ρ) −
f∞
= sup inf fRS
(q, r) = sup inf ψP0 (r) + αβΨPout
.
(46)
out
2
q∈[0,ρ] r≥0
q∈[0,ρ] r≥0
tr and ∆ = ∆te respectively.
tr and ΨP te are obtained from (16) using Pout given by (3) with ∆ = ∆
Here ΨPout
out
ts (inside
Note that in the limit ∆te → ∞ (which means that the student has no access to the test set labels), fRS
the brackets in (46)) collapses on fRS given by (18) up to a trivial additive constant which corresponds to
0
te and a rescaling of the measurement rate α = αβ.
ΨPout
Differentiating the free entropy w.r.t. ∆te , we deduce the limit of this optimal generalization error with
side information:

Proposition 2 (Optimal generalization error with side information). For almost every ∆te > 0 we have
p
p



 √
side
lim Egen
= E ϕ( ρ V, A)2 − E ϕ( q ∗ (∆te ) V + ρ − q ∗ (∆te ) w, a)i2sc,∆te ,

n→∞

(47)

where q ∗ (∆te ) is a maximizer of (46) and where h−isc,∆te is the Gibbs bracket associated with the posterior
distribution of the second scalar channel (17) with ∆ = ∆te .
The proof of Proposition 2 is presented in Appendix B.2. A natural continuation would be to show that
for almost every value of ∆tr , q ∗ (∆te ) converges, as ∆te → ∞, to a maximizer q ∗ of the replica formula (20)
from Theorem 1. Using theorems for limit-expectations permutation, it should not be difficult to show then
side
that lim lim Egen
= E(q ∗ ). Then, provided we can justify the following permutation of limits we would
∆te →∞ n→∞

14

obtain
lim E opt
n→∞ gen

lim E side
n→∞ ∆te →∞ gen

= lim

side
lim Egen
= E(q ∗ ) .

= lim

(48)

∆te →∞ n→∞

We conjecture this formula to be true, but we were however unable to provide the technical justifications
mentioned above.
3.4.2

Optimal reconstruction error with side information

Analogously to the previous section, one can add small side information to our statistical model (1) by supposing that one observes also
Yi0 = Xi∗ +

√
∆side Zi0 ,

(49)

1 ≤ i ≤ n,

side > 0 quantifies the noise level of the
where (Zi0 )ni=1 i.i.d.
∼ N (0, 1) independently of everything else. Here ∆
side information and will typically be very large. The proof of Theorem 1 can be directly adapted to obtain
that the new free energy converges to

n

side
side
f∞
= sup inf fRS
(q, r) = sup inf ψP0 r +
q∈[0,ρ] r≥0

q∈[0,ρ] r≥0

1 
∆side

+ αΨPout (q; ρ) −

rq o
.
2

(50)

By then taking the derivative w.r.t. (∆side )−1 , which is again a I-MMSE relation [40], one deduces the minimum mean-square-error (MMSE) for the reconstruction of X∗ :
Proposition 3 (Reconstruction MMSE with side information). For almost all ∆side > 0,
MMSEn :=

1  ∗
2
E X − hxi
−−−→ ρ − q ∗ (∆side ),
n→∞
n

(51)

where q ∗ (∆side ) is a maximizer of (50).

4 Application to concrete situations
In this section, we show how our main results can be applied to several models of interest in fields ranging
from machine learning to signal processing, and unveil several interesting new phenomena in learning of
generalized linear models. For various specific cases of prior P0 and output Pout , we evaluate numerically the
free entropy potential (18), its stationary points Γ and identify which of them gives the information-theoretic
results, i.e. is the maximizer in (20). We also identify which of the stationary points corresponds to the result
obtained asymptotically by the GAMP algorithm, i.e. the fixed point of the state evolution (32). Finally we
compute the corresponding generalization error (43). We stress that in this section the results are based on
numerical investigation of the resulting formulas: We do not aim at rigor that would involve precise bounds
and more detailed analytical control for the corresponding integrals.

4.1

Generic observations

Using the functions gPout and gP0 introduced in Sec. 2.5 we can rewrite the fixed point equations (19) as
q = 2ψP0 0 (r) = E[gP0 (Y0 , r)2 ] ,
α
√
E[gPout (Ye0 , q V, ρ − q)2 ] ,
r = 2αΨ0Pout (q) =
ρ−q
15

(52)
(53)

where the expectation in (52) corresponds to the scalar channel (12) and the expectation in (53) corresponds
to the second scalar channel (15).
Non-informative fixed point and its stability: It is interesting to analyze under what conditions q ∗ = 0
is the optimizer of (20). Notice that q ∗ = 0 corresponds to the error on the recovery of the signal as large as
it would be if we had no observations at our disposition. Theorem 1 gives that any optimal couple (q ∗ , r∗ ) of
(20) should be a fixed point of the state evolution equations (52)-(53). A sufficient condition for (q, r) = (0, 0)
to be a fixed point of (52)-(53) is that
(a) The transition density Pout (y|z) is even in the argument z.
(b) The prior P0 has zero mean.
In order to see this, notice that if Pout (y|z) is even in z then from the definition (30) of the function gPout we
have gPout (y, 0, ρ) = 0 and consequently from (53) we have Ψ0Pout (0) = 0. For the second point, notice that
we have ψP0 0 (0) = 21 EP0 [X0 ]2 = 0.
We assume now that the transition density Pout (y|z) is even in the argument z and that the prior P0 has
zero mean. In order for q = 0 to be the global maximizer q ∗ of (20) or to be a relevant fixed point of the state
evolution (32) (relevant in the sense that GAMP might indeed converge to it in a practical setting) we need
q = 0 to be a numerically stable fixed point of the above equations (52)-(53). We therefore need to expand
(52)-(53) around q = 0, and doing so, we obtain that q = 0 is stable if

2 
2αΨ00Pout (0) × 2ψP00 0 (0) = αE hw2 isc − hwi2sc − 1
< 1,

(54)

where the expectation corresponds to the scalar channel (15) with q = 0 and the Gibbs bracket h−isc is given
by (17). The expectation quantifies how the observation of Ye0 in the scalar channel (15) modifies the variance
of W ∗ (which is 1 without any observation). Rewriting this condition more explicitly into a form that is
convenient for numerical evaluation we get
Z
αρ


R
0 (y|√ρz) 2
DzzPout
dy R
< 1,
√
DzPout (y| ρz)

(55)

0 (y|ω) stands for the partial derivative
where recall that Dz is a standard Gaussian measure and where Pout
w.r.t. ω. We conjecture that the condition (54) (or equivalently (55) for differentiable models) delimits precisely
the region where polynomial-time algorithms do not perform better than “random guessing” (see the discussion below, where we will make this stability condition explicit for several examples of symmetric output
channels).

Exact recovery fixed point: Another particular fixed point of (52)-(53) that we observe is the one corresponding to exact recovery q ∗ = ρ. A sufficient and necessary condition for this to be a fixed point is that
limq→ρ Ψ0Pout (q) = +∞. Heuristically, this means that the integral of the Fisher information of the output
channel should diverge:
2
Z
−ω
0 (y|ω)2
e 2ρ Pout
dydω √
= +∞ ,
(56)
2πρ Pout (y|ω)
0 (y|ω) denotes the partial derivative w.r.t. ω. This typically means that the channel should be
where again Pout
noiseless. For the Gaussian channel with noise variance ∆, the above expression equals 1/∆. For the probit
√
√
channel where Pout (y|z) = erfc(−yz/ 2∆)/2 the above expression at small ∆ is proportional to 1/ ∆.
Numerical stability of the exact recovery fixed point was also investigated, but we did not obtain any
unified expression. The stability depends non-trivially on both the properties of the output channel, but also

16

on the properties of the prior. Below we give several examples where exact recovery either is or is not possible,
or where there is a phase transition between the two regimes.

4.2

Phase diagrams of perfect learning

In this section we consider deterministic (noiseless) output channels and ask: How many measurements are
needed in order to perfectly recover the signal?
Our crucial point is to compare with the well explored phase diagram of Bayesian (noiseless) compressed
sensing in the case of the linear channel [52, 53]. As the number of samples (measurements) varies we encounter four different regimes of parameters:
• The EASY phase: This is the region in the parameter space where GAMP achieves perfect reconstruction.
• The IMPOSSIBLE phase: Region where perfect reconstruction is information-theoretically impossible.
• The HARD phase: Region where the perfect reconstruction is information-theoretically possible, but
where GAMP is unable to achieve it. However, in this region GAMP leads to a better generalization
error than the one corresponding to the non-informative fixed point. It remains a challenging open
question whether polynomial-time algorithms can achieve perfect reconstruction in this regime.
• The HARD-RG phase: This “hard-random guess” phase corresponds to the region where perfect reconstruction is information-theoretically possible but where GAMP only achieves an error as bad as
randomly guessing, given by the trivial fixed point. In this phase as well, the existence of polynomialtime exact recovery algorithms is an open question. This phase does not exist for the linear channel.
Some of the codes used in this section can be consulted online on the github repository [1].
4.2.1

The linear channel

The case of exact recovery of a sparse signal after it passed trough a noiseless linear channel, i.e. ϕ(x) = x, is
studied in the literature in great details, especially in the context of compressed sensing [24, 31]. For a signal
with a fraction ρ of non-zero entries it is found that as soon as α > ρ, perfect reconstruction is theoretically
possible, although it may remain computationally difficult. The whole field of compressed sensing builds on
the realization that, using the `1 norm minimization technique, one can efficiently recover the signal for larger
α values than the so-called Donoho-Tanner transition [29, 31].
In the context of the present paper, when the empirical distribution of the signal is known, one can fairly
easily beat the `1 transition and reconstruct the signal up to lower values of α using the Bayesian GAMP
algorithm [31, 52, 53, 70]. In this case, three different phases are present [52, 53]: i) For α < ρ, perfect reconstruction is impossible; ii) for ρ < α < αs reconstruction is possible, but not with any known polynomialcomplexity algorithm; iii) for α > αs , the so-called spinodal transition computed with state evolution, GAMP
provides a polynomial-complexity algorithm able to reach perfect reconstruction. The line αs (ρ) depends on
the distribution of the signal. For a Gauss-Bernoulli signal with a fraction ρ of non-zero (Gaussian) values we
compare the GAMP performance to the optimal one in Fig. 1 (left and right).
4.2.2

The rectified linear unit (ReLU) channel

Let us start by discussing the case of a generalized linear model with the ReLU output channel, i.e. ϕ(x) =
√
max(0, x), with a signal coming from a Gauss-Bernoulli distribution P0 (x) = ρ exp(−x2 /2)dx/ 2π + (1 −
ρ)δ(x) with a fraction ρ of non-zero (Gaussian) values. We are motivated by the omnipresent use of the ReLU
activation function in deep learning, and explore its properties for GLMs that can be seen as a simple single
layer neural network.
17

Absolute value channel, Gauss-Bernoulli X*

Symmetric Door activation, width Κ, Rademacher X*
3

1.2
1

2.5

EASY

EASY

1.5

IMPOSSIBLE

0

1

HARD
IMPOSSIBLE

1

0.5
ρ

0.5

IMPOSSIBLE

Perfect recovery
Spinodal
instability at q=0
Spinodal CS

0

HARD,
RG

1.5

HARD

HARD, RG

0.2

α=m/n

0.6
0.4

EASY

2

HARD
α=m/n

α=m/n

0.8

Relu activation, Gauss-Bernoulli signal
2

0.5

instability at q=0
Perfect recovery
Spinodal

0
1

0

0.5

1

1.5
Κ

Perfect recovery
Spinodal
Naive spinodal

0
2

2.5

0

0.5
ρ

1

Figure 1: Phase diagrams for several non-linear output channels showing the region where a perfect recovery
is possible/hard/impossible. Left: The phase diagram for the signless output with ϕ(x) = |x| with a GaussBernoulli signal, as a function of α = m/n and the fraction of non-zero components ρ. We find that a perfect
recovery is IMPOSSIBLE for α < ρ. Perfect recovery becomes possible starting from α > ρ, as for the linear
channel. On the algorithmic side, GAMP is not able to perform better than a random guess as long as α < 0.5. We
denote this region HARD-RG, for “not better than random guess”. For larger values, the inference using GAMP
leads to better results than a purely random guess but cannot reach perfect recovery, so the problem remains
HARD. GAMP can perfectly identify the hidden signal only for values of α larger than the so-called spinodal
(or algorithmic threshold), when the problem becomes EASY. For comparison we also show the algorithmic
transition for the linear output (the spinodal CS dashed line). Middle: Phase diagram for the door function
problem, with ϕ(x) = sgn(|x| − K), for a Rademacher signal as a function of α and K. The same four regions of
parameters are observed and depicted. Right: Phase diagram for the ReLU output, with ϕ(x) = max(0, x), again
with the EASY, HARD and IMPOSSIBLE regions. Here it is always possible to generalize better than chance using
GAMP. The so-called naive spinodal shows for comparison the algorithmic performance when using information
only about the non-zero observations.

Our analysis shows that a perfect generalization (and thus a perfect reconstruction of the signal as well)
is possible whenever the number of samples per dimension (measurement rate) α > 2ρ, and impossible when
α < 2ρ. This is very intuitive, since half of the measurements (those non-zero) are giving as much information
as in the linear case, thus the factor 2.
How hard is it to actually solve the problem with an efficient algorithm? The answer is given by applying
the state evolution analysis to GAMP, which tells us that only for even larger values of α, beyond the spinodal
transition, does GAMP reach a perfect recovery. Notice, however, that this spinodal transition occurs at a
significantly lower measurement rate α than one would reach just keeping the non-zero measurements. This
shows that, actually, these zero measurements contain a useful information for the algorithm. The situation
is shown in the right side of Fig. 1: The zero measurements do not help information-theoretically but they,
however, do help algorithmically.
4.2.3

The signless channel

We now discuss the signless channel where only the absolute value of the linear mixture is observed, i.e.
ϕ(x) = |x|. This case can be seen as the real-valued analog of the famous phase retrieval problem. We again
consider the signal to come from a Gauss-Bernoulli distribution with a fraction ρ of non-zero (Gaussian)
values.
Sparse phase retrieval has been well explored in the literature in the regime where the number s of nonzeros is sub-leading in the dimension, s = O(n). This case is known to present a large algorithmic gap.
While analogously to compressed sensing exact recovery is information-theoretically possible for a number
of measurement O(s ln(n/s)), best known algorithms achieve it only with O(s2 / ln n) measurements [67],
see also [75] and references therein for a good discussion of other related literature. This is sometimes referred
18

to as the s2 barrier. We are not aware of a study where, as in our setting, the sparsity is s = ρn and the number
of measurements is αn with α = O(1). Our analysis in this regime hence sheds a new light on the hardness
of the problem of recovering a sparse signal from signless measurements.
Our analysis of the mutual information shows that a perfect reconstruction is information-theoretically
possible as soon as α > ρ: In other words, the problem is –information-theoretically– as easy, or as hard as
the compressed sensing one. This is maybe less surprising when one thinks of the following algorithm: Try
all 2m choices of the possible signs for the m outputs, and solve a compressed sensing problem for each of
them. Clearly, this should yields a perfect solution only in the case of the actual combination of signs.
Algorithmically, however, the problem is much harder than for the linear output channel. As shown in
the left side of Fig. 1, for small ρ one requires a much larger fraction α of measurements in order for GAMP
to recover the signal. For the linear channel the algorithmic transition αs (ρ) → 0 as ρ → 0, while for the
signless channel we get αs (ρ) → 1/2 as ρ → 0. In other words if one looses the signs one cannot perform
recovery in compressed sensing with less than n/2 measurements.
What we observe in this example for α < 1/2 is in the statistical physics literature on neural networks
known as retarded learning [43]. This appears in problems where the ϕ(x) function is symmetric, as seen at
the beginning of this section: There is always a critical point of the mutual information with an overlap value
q = 0. For this problem, this critical point is actually “stable” (meaning that it is actually a local minimum in
q) for all α < 1/2 independently of ρ. To see that, we have to go back to (54). For the absolute value channel,
√
the posterior distribution of W ∗ given Ye0 = ρ |W ∗ | in the second scalar channel (15) is a mean of two Dirac
masses on −W ∗ and W ∗ . Thus, the posterior variance is hw2 isc − hwi2sc = (W ∗ )2 . Consequently, (54) leads
to the stability condition α < 1/2.
This has the two following implications: i) In the IMPOSSIBLE phase, when α < 1/2 and ρ > α, the
minimum at q = 0 is actually the global one. In this case, the MMSE and the generalization error are the ones
given by using 0 as a guess for each element of X∗ ; in other words, there is no useful information that one
can exploit and no algorithmic approach can be better than a random guess. ii) In the POSSIBLE but HARD
phase when α < 1/2, GAMP initialized at random, i.e. close to the q = 0 fixed point, will remain there. This
suggests that in this region, even if a perfect reconstruction is possible, it will still be very hard to beat a
random guess with a tractable algorithm.
4.2.4

The symmetric door channel

The third output channel we study in detail is the symmetric door channel, where ϕ(x) = sgn(|x| − K). In
case of channels with discrete set of outputs exact recovery is only possible when the prior is also discrete. In
the present case we consider the signal to be Rademacher, where each element is chosen at random between
1 and −1, i.e. P0 (x) = (δ(x − 1) + δ(x + 1))/2. This channel was studied previously using the replica method
in the context of optimal data compression [44].
This output channel is in the class of symmetric channels for which overlap q = 0 is a fixed point. This
fixed point is stable for α < αc (K). Exact recovery is information-theoretically possible above αIT (K) and
tractable with the GAMP algorithms above the spinodal transition αs (K). The values of these three transition
lines are depicted in the center panel of Fig. 1.
We note that αIT ≥ 1 is a generic bound on exact recovery for every K, required by a simple counting
argument. While a-priori it is not clear whether this bound is saturated for some K, we observe that it is for
K = 0.67449 such that half of the observed measurements are negative and the rest positive. This is, however,
not efficiently achievable with GAMP. The saturation of the αIT ≥ 1 bound was remarked previously in the
context of the work [44] on optimal data compression. Our work predicts that this information-theoretic
result will not be achievable with known efficient algorithms.

19

Generalization error

Perceptron, Rademacher X*

Perceptron, Gauss-Bernoulli X*, ρ=0.2

Symmetric Door, Rademacher X*

1

1

0.8

0.8

0.6

0.6

0.6

0.4

0.4

0.4

0.2

0.2

SE
Optimal
AMP,N=1044
Logistic,N=10

0.2
0
0

0.5

1

Optimal and SE
AMP, N=104
Logistic,N=104

SE
Optimal
AMP,N=104

0.8
1
2-layer NN

0
0

0
1
α

1.5

2

5

10 15 20

0
0

0.5

1

1.5

2

2.5
α

3

3.5

4

4.5

5

0

0.5

1

1.5

2

2.5

α

Figure 2: Generalization error in three classification problems as a function of the number of data-samples per
dimension α. The red line is the Bayes-optimal generalization error, while the green one shows the (asymptotic)
performances of GAMP as predicted by the state evolution (SE), when different. For comparison, we also show
the result of GAMP (black dots) and, in blue, the performance of a standard out-of-the-box solver, both tested on a
single randomly generated instance. Left: Perceptron, with ϕ(x) = sgn(x) and a Rademacher (±1) signal. While
a perfect generalization is information-theoretically possible starting from α = 1.249(1), the state evolution
predicts that GAMP will allow such perfect prediction only from α = 1.493(1). The results of a logistic regression
with fine-tuned ridge penalty with the software scikit-learn [68] are shown for comparison. Middle: Perceptron
with Gauss-Bernoulli coefficients for the signal. No phase transition is observed in this case, but a smooth
decrease of the error with α. The results of a logistic regression with fine-tuned `1 sparsity-enhancing penalty
(again with [68]) are very close to optimal. Right: The symmetric door activation rule with parameter K =
0.67449 chosen in order to observe the same number of occurrence of the two classes. In this case there is a sharp
phase transition at α = 1 from a situation where it is impossible to learn the rule, so that the generalization is
not better than a random guess, to a situation where the optimal generalization error drops to zero. However,
GAMP identifies the rule perfectly only starting from αs = 1.566 (GAMP error stays 1 up to αstab = 1.36, see
the black dashed curve). Interestingly, this non-linear rule seems very hard to learn for other existing algorithms.
Using Keras [26], a neural network with two hidden layers was able to learn approximately the rule, but only for
much larger training set sizes (shown in inset).

4.3

Examples of optimal generalization error

Besides the formula for the mutual information, the main result of this paper is the formula (40) (or (47) when
∆te → +∞) for the optimal generalization error, and formula (43) for the generalization error achieved by
the GAMP algorithm. In this section we evaluate both these generalization errors for several cases of priors
and output functions. We study both regression problems, where the output is real-valued, and classification
problems, where the output is discrete.
While in realistic regression and classification problems the matrix Φ corresponds to the data, and is thus
not i.i.d. random, we view the practical interest of our theory as a benchmark for state-of-the art algorithms.
Our work provides an exact asymptotic analysis of optimal generalization error and sample complexity for a
range of simple rules where a teacher uses random data to generate labels. The challenge for state-of-the-art
multi-purpose algorithms is to try to match as closely as possible the performance that can be obtained with
GAMP that is fine-tuned to the specific form of the output and prior.
4.3.1

Threshold output: The perceptron

The example of non-linear output that is the most widely explored in the literature is the threshold output,
where the deterministic output (or “activation”) function is ϕ(x) = sgn(x). This output in the teacher-student
setting of the present paper is known as the perceptron problem [36], or equivalently, the one-bit compressed
sensing in signal processing [21]. Its solution has been discussed in details within the replica formalism (see
for instance [16, 46, 66, 83]) and we confirm all of these heuristic computations within our approach. Let

20

V ∼ N (0, 1). The formula (40) for the generalization error then reduces to (recall q ∗ is a maximizer of (20))
lim E opt
n→∞ gen

Z
=1−

 2 Z V
DV √
π 0

q

q∗
2(ρ−q ∗ )

−t2 /2

dt e

2

h 
= 1 − E erf V

s

2 i
q∗
.
2(ρ − q ∗ )

(57)

In Fig. 2 (left) we plot the optimal generalization error of the perceptron with a Rademacher signal, the
state evolution prediction of the generalization error of the GAMP algorithm, together with the error actually achieved by GAMP on one randomly generated instance of the problem. We also compare these to the
performance of a standard logistic regression. As expected from existing literature [36,73] we confirm that in
this case the information-theoretic transition appears at a number of samples per dimension αIT = 1.249(1),
while the algorithmic transition is at αs = 1.493(1). Logistic regression does not seem to be able to match
the performance on GAMP in this case.
In Fig. 2 (center) we plot the generalization error for a Gauss-Bernoulli signal with density ρ = 0.2. Cases
as this one were studied in detail in the context of one-bit compressed sensing [83] and GAMP was found to
match the optimal generalization performance with no phase transitions observed. In this case the logistic
regression is rather close to the performance of GAMP.
4.3.2

Symmetric Door

The next classification problem, i.e. discrete output rule, we study is the symmetric door function ϕ(x) =
sgn(|x| − K). In this case the generalization error (40) becomes
lim E opt
n→∞ gen

hn  K − √q ∗ V 
 K + √q ∗ V 
o2 i
= 1 − EV erf p
− erf − p
−1
.
2(ρ − q ∗ )
2(ρ − q ∗ )

(58)

In Fig. 2 (right) we plot the generalization error for K = 0, 67449 such that 1/2 of the outputs are 1 and
1/2 are −1. The symmetric door output is an example of function for which the optimal generalization error
for α < αIT = 1 (for that specific value of K, see phase diagram in center of Fig. 1)) is as bad as if we were
guessing randomly. The GAMP algorithm still achieves such a bad generalization until αstab = 1.36, and
achieves perfect generalization only for α > αs = 1.566.
Interestingly, labels created from this very simple symmetric door rule seem to be very challenging to
learn for general purpose algorithms. We tried to optimize parameters of a two-layers neural network and
only managed to get the performances shown in the inset of Fig. 2 (right). It is an interesting theoretical
challenge whether a deeper neural network can learn this simple rule from fewer samples.
4.3.3

Linear regression

The additive white Gaussian noise (AWGN) channel, or linear regression, is defined by ϕ(x, A) = x+σA with
A ∼ N (0, 1). This models the (noisy) linear regression problem, as well as noisy random linear estimation
and compressed sensing. In this case (40) leads to
lim E opt
n→∞ gen

= ρ − q∗ + σ2 .

(59)

This result agrees with the generalization error analyzed heuristically in [73] in the limit σ → 0. Fig. 3 (left)
depicts the generalization error for this example. Performance of GAMP in this case very close to the one of
LASSO.

21

Generalization error

AWGN σ= 0.032, Gauss-Bernoulli X*, ρ=0.2

ReLu, Gauss-Bernoulli X*, ρ=0.2
0.08
0.07
0.06
0.05
0.04
0.03
0.02
0.01
0

0.2
0.15
0.1
Optimal and SE
AMP,N=104
LASSO,N=104

0.05
0
0

0.2

0.4

0.6

Absolute value, Gauss-Bernoulli X*, ρ=0.5
0.2

SE
Optimal
AMP, N=104
Keras,N=104

0.15

SE
Optimal
AMP,N=104

0.6

0.1 0.4
0.2
0.05

PM

0
0 1 2 3 4

0
0

0.2

0.4

0.6
α

α

0.8

1

1.2

0

0.2

0.4

0.6

0.8

1

1.2

1.4

α

Figure 3: The generalization error for three regression problems is plotted as a function of the number of samples
per dimension α. The red line is again the Bayes-optimal generalization error, while the green one shows the
(asymptotic) performances of GAMP as predicted by the state evolution (SE), when different. Again, we also
show the result of GAMP on a particular instance (black dots) and, in blue, the performance of an out-of-the-box
solver. Left: White Gaussian noise output and a Gauss-Bernoulli signal. For this choice of noise, there is no sharp
transition (as opposed to what happens at smaller noises). The results of a LASSO with fine-tuned `1 sparsityenhancing penalty (with [68]) are very close to optimal. Middle: Here we analyze a ReLU output function
ϕ(x) = max(0, x), still with a Gauss-Bernoulli signal. Now there is an information-theoretic phase transition at
α = 2ρ = 0.4, but GAMP requires αs = 0.589 to reach perfect recovery. We show for comparison the result of
a maximum likelihood estimation performed with Keras [26] and observe a sizeable gap in performance. Right:
The signless output function ϕ(x) = |x|. The information-theoretic perfect recovery starts at α = ρ = 0.5,
but the problem is again harder algorithmically for GAMP that succeeds only above αs = 0.90. Again, the
problem appears to be hard for other solvers. In inset, we show the performance for the estimation problem
using PhaseMax [37], which is able to learn the rule only using about four times as many measurement than
needed information-theoretically.

4.3.4

Rectified linear unit (ReLU)

In Fig. 3 (center) we analyze the generalization error for the ReLU output function, ϕ(x) = max(0, x). This
channel models the behavior of a single neuron with the rectified linear unit activation [54] widely used in
multilayer neural networks. In this case (40) becomes after simple algebra and Gaussian integration by parts
(again V ∼ N (0, 1)),
lim E opt
n→∞ gen

h

ρ q∗ 
1 + EV V 2 erf V
= −
2
4

s

2 i (ρ − q ∗ )3/2  1
q∗
q∗
√
−
+
2(ρ − q ∗ )
ρ + q ∗ 2π ρπ

r

ρ + q∗ 
.
ρ − q∗

(60)

For sparse Gauss-Bernoulli signals in Fig. 3 (center) we observe again the information-theoretic transition
to perfect generalization to be distinct from the algorithmic one. At the same time our test with existing
algorithms were not able to closely match the performance of GAMP. This hence also remains an interesting
benchmark.
4.3.5

Signless channel

In Fig. 3 (right) we analyze the generalization error for the signless output function where ϕ(x) = |x|. This
models a situation similar to compressed sensing, except that the sign of the output has been lost. This is
a real-valued analog of the phase retrieval problem as discussed in Sec. 4.2.3. In this case the generalization
error (40) becomes
p


opt
lim Egen
= ρ − EV b(V q ∗ , ρ − q ∗ )2 ,

n→∞

(61)

where
r
b(x, y) =



2y − x2y2
x
x  xn
x o
e
+ erfc − √
−
1 + erf − √
.
π
2
2
2y
2y
22

(62)

Our comparison with the performance of a state-of-the-art algorithm PhaseMax [37] suggests that also
for this simple benchmark there is room for improvement in term of matching the performance of GAMP.
4.3.6

Sigmoid, or logistic regression

Let us also consider an output function with auxiliary randomization. After having generated the classifier
X∗ , the teacher randomly associates the label +1 to the pattern Φµ with probability fλ (n−1/2 Φµ ·X∗ ), where
fλ (x) = (1 + exp(−λx))−1 ∈ [0, 1] is the sigmoid of parameter λ > 0, and the label −1 with probability
1 − fλ (n−1/2 Φµ · X∗ ). One of the (many) possible ways for the teacher to do so is by selecting ϕ(x, A) =
I(A ≤ fλ (x)) − I(A > fλ (x)), where I(E) is the indicator function of the event E. He then generates a
i.i.d.
stream of uniform random numbers A i.i.d.
∼ U[0,1] and obtains the labels through (35). Let V, w ∼ N (0, 1). In
this setting the error (40) becomes
opt
lim Egen
= 2 − 4 EV

n→∞

p
p

Ew fλ ( q ∗ V + ρ − q ∗ w)

2

.

(63)

This fomula reduces to (57) when λ → ∞ as it should.

5 Proof of the replica formula by the adaptive interpolation
method
We now prove Theorem 1. Our main tool will be an interpolation method recently introduced in [13] and
called “adaptive interpolation method”. Here we formulate the method as a direct evolution of the Guerra and
Toninelli interpolation method developed in the context of spin glasses [39]. In constrast with the discrete
and more pedestrian version of the adaptive interpolation method presented in [13] (and called in this case
“stochastic interpolation method”), here we employ a continuous approach which is more straightforward
(see [13] for the links between the discrete and continuous versions of the method) and that has also been
recently used in [8] for studying non-symmetric tensor estimation.
We will prove Theorem 1 under the following hypotheses:
(H1) The prior distribution P0 has a bounded support.
(H2) ϕ is a bounded C 2 function with bounded first and second derivatives w.r.t. its first argument.
(H3) (Φµi ) i.i.d.
∼ N (0, 1).
These assumptions will then be relaxed in Appendix D to the assumptions (h1), (h2) and (h3) or (h3.a)-(h3.b)(h3.c). Since the observations (1) are equivalent to the rescaled observations
 1

Yeµ := ∆−1/2 Yµ = ∆−1/2 ϕ √ [ΦX∗ ]µ , Aµ + Zµ ,
n

1 ≤ µ ≤ m,

(64)

the variance ∆ of the Gaussian noise can be “incorporated” inside the function ϕ. Thus, it suffices to prove
Theorem 1 for ∆ = 1 and we suppose, for the rest of the proof, that we are in this equivalent case.

5.1

Interpolating estimation problem

We introduce an “interpolating estimation problem” that interpolates between the orginal problem (2) at t = 0,
t ∈ [0, 1] being the interpolation parameter, and the two scalar problems described in Sec. 2.2 at t = 1 which
are analytically tractable. For t ∈ (0, 1) the interpolating estimation problem is a mixture of the original
and scalar problems. This interpolation scheme is inspired from the interpolation paths used by Talagrand to

23

study the perceptron, see [76]. There are two major differences between the “non-planted perceptron” studied
by Talagrand, and the “planted perceptron” that we are investigating:
• In the planted case, the presence of a planted solution forces (under small perturbations) the correlations
to vanish for all values of the parameters, see [48,63]. In the non-planted case, proving such decorelation
is much more involved, and is proved only in a limited region of the parameter space, see [76].
• However, in the planted case, there can be arbitrarily many (see Remark 21 in [82]) solutions to the
state evolution equations (19), whereas in the region studied by [76], there is only one solution. For this
reason, our interpolation method needs to be more sophisticated in order to interpolate with the “right
fixed point”.
Let q : [0, 1] → [0, ρ] be a continuous “interpolation function” and r ≥ 0. Define
r
St,µ :=

1−t
[ΦX∗ ]µ +
n

sZ

sZ

t

t

q(v)dv Vµ +
0

(ρ − q(v))dv Wµ∗

(65)

0

where Vµ , Wµ∗ i.i.d.
∼ N (0, 1). Consider the following observation channels, with two types of observations
obtained through
(
Yt,µ ∼ Pout ( · | St,µ ) ,
1 ≤ µ ≤ m,
√
(66)
0
Yt,i
=
r t Xi∗ + Zi0 ,
1 ≤ i ≤ n,
m
where (Zi0 )ni=1 i.i.d.
∼ N (0, 1). We assume that V = (Vµ )µ=1 is known. Then the inference problem is to recover
∗
∗
m
∗
∗
n
both unknowns W = (Wµ )µ=1 and X = (Xi )i=1 from the knowledge of V, Φ and the “time-dependent”
0
0 n
observations Yt = (Yt,µ )m
µ=1 and Yt = (Yt,i )i=1 .
We now understand that rt appearing in the second set of measurements in (66), and the terms 1 − t,
Rt
Rt
q(v)dv
and 0 (ρ − q(v))dv appearing in the first set all play the role of signal-to-noise ratios in the in0
terpolating model, with t giving more and more “power” (or weight) to the scalar inference channels when
increasing. Here is the first crucial and novel ingredient of our interpolation scheme. In the classical interpolation method, these signal intensities would all take a trivial form (i.e. would be linear in t) but here, the
non-trivial (integral) dependency in t of the two latter intensities through the use of the interpolation function
q allows for much more flexibility when choosing the interpolation path. This will allow us to actually choose
the “optimal interpolation path” (this will become clear soon).
Define uy (x) := ln Pout (y|x) and, with a slight abuse of notations,

r
st,µ = st,µ (x, wµ ) :=

1−t
[Φx]µ +
n

sZ

sZ

t

0

t

(ρ − q(v))dv wµ .

q(v)dv Vµ +

(67)

0

We introduce the interpolating Hamiltonian
Ht (x, w; Y, Y0 , Φ, V) := −

m
X

n

ln Pout (Yµ |st,µ ) +

µ=1

=−

m
X

2
1X 0 √
Yi − t r xi
2
i=1

uYt,µ (st,µ ) +

µ=1

n
1X √

2

t r (Xi∗ − xi ) + Zi0

2

.

(68)

i=1

The dependence in Φ and V of the Hamiltonian is through the (st,µ )m
µ=1 . We also introduce the corresponding
Gibbs bracket h−it which is the expectation operator w.r.t. the t-dependent posterior distribution of (x, w)

24

given (Yt , Yt0 , Φ, V). It is defined as
1
hg(x, w)it :=
Zt (Yt , Yt0 , Φ, V)

Z

0

dP0 (x)Dw g(x, w) e−Ht (x,w;Yt ,Yt ,Φ,V) ,

(69)

Q
2 /2
−wµ
for every continuous bounded function g on Rn × Rm . In (69) Dw = (2π)−m/2 m
is the
µ=1 dwµ e
0
m-dimensional standard Gaussian distribution and Zt (Yt , Yt , Φ, V) is the appropriate normalization:
Z
0
0
Zt (Yt , Yt , Φ, V) := dP0 (x)Dw e−Ht (x,w;Yt ,Yt ,Φ,V) .
(70)
Finally the interpolating free entropy is
fn (t) :=

1
E ln Zt (Y, Y0 , Φ, V) .
n

(71)

One verifies easily that
(

fn (0) = fn − 21 ,
fn (1) = ψP0 (r) −

1+rρ
2

+

R1
m
n ΨPout ( 0 q(t)dt; ρ) ,

(72)

where fn is given by (11). We emphasize a crucial property of the interpolating model: It is such that at t = 0
we recover the original model and thus fn (0) = fn − 1/2 (the trivial constant comes from the purely noisy
measurements of the second channel in (66)), while at t = 1 we have the two scalar inference channels and
thus the associated terms ψP0 and ΨPout discussed in Sec. 2.2 appear in fn (1). These are precisely the terms
appearing in the potential (18).

5.2

Free entropy variation along the interpolation path

From the understanding of the previous section, it is at this stage very natual to evaluate the variation of free
entropy along the interpolation path, which allows to “compare” the original and purely scalar models thanks
to the identity
1
fn = fn (0) + = fn (1) −
2

Z
0

1

1
dfn (t)
dt + ,
dt
2

(73)

where the first equality follows from (72). As discussed above, part of the potential (18) appears in fn (1). If the
interpolation is properly done, the missing terms required to obtain the potential on the r.h.s. of (73) should
naturally appear. Then by choosing the optimal interpolation path thanks to the non-trivial snr dependencies
in t (i.e. by selecting the proper interpolating function q), we will be able to show the equality between the
replica formula and the true entropy fn .
We thus now compute the t-derivative of the free entropy along the interpolation path (see Appendix C
for the proof). Let u0y (x) be the derivative (w.r.t. x) of uy (x). Then we have the following.
Proposition 4 (Free entropy variation). For model (2), the derivative of the free entropy (71) verifies, for all
t ∈ (0, 1),
m

E
dfn (t)
1 D 1 X 0
rq(t) rρ
=− E
uYt,µ (St,µ )u0Yt,µ (st,µ ) − r Q − q(t)
+
−
+ On (1) ,
dt
2
n
2
2
t
µ=1

25

(74)

where On (1) is a quantity that goes to 0 in the n, m → ∞ limit, uniformly in t ∈ [0, 1] and the overlap is
n

Q :=

1X ∗
Xi xi .
n

(75)

i=1

5.3

Overlap concentration

The next lemma plays a key role in our proof. Essentially it states that the overlap concentrates around
its mean, a behavior called “replica symmetric” in statistical physics. Similar results have been obtained in
the context of the analysis of spin glasses [76]. Here we use a formulation taylored to Bayesian inference
problems as developed in the context of LDPC codes, random linear estimation [14] and Nishimori symmetric
spin glasses [47, 48, 57].
We introduce a “small” perturbation of the interpolating estimation problem by adding to the Hamiltonian
(68) a term
n  2

X
√
x
bi
 i − xi Xi∗ − xi Z
2

(76)

i=1

where (Zbi )ni=1 i.i.d.
∼ N (0, 1). This√term can be interpreted as having a set of extra observations coming from
a Gaussian side-channel Ybi = Xi∗ + Zbi for i = 1, . . . , n and that preserves the Nishimori identity (see
Appendix A.1). The new Hamiltonian Ht, (x, w; Y, Y0 , Φ, V) defines a new Gibbs bracket h−in,t, and free
entropy fn, (t), and all the set up of Sec. 5.1 and Proposition 4 trivially extend. This perturbation induces
only a small change in the free entropy, namely of the order of :
Lemma 1 (Small free entropy variation under perturbation). Let S > 0 such that the support of P0 is included
in [−S, S]. For all  > 0 and all t ∈ [0, 1],
|fn, (t) − fn (t)| ≤ 

S2
.
2

(77)

Proof. A simple computation gives
∂fn, (t)
1
S2
= EhQin,t, ≤
,
∂
2
2

(78)

which proves the lemma.
Moreover, this small perturbation forces the overlap to concentrate around its mean:
Lemma 2 (Overlap concentration). For any 0 < a < b < 1,
b

Z
lim

n→∞ a

Z

1

dt E Q − EhQin,t,

d
0

2
n,t,

= 0.

(79)

In Appendix F.2 we briefly sketch the main steps of the proof for the convenience of the reader and refer
to [13] for more details where the method has been streamlined.
∗
Lemma 2 implies that there exists a sequence (n )n≥1 ∈ (0, 1)N that converges to 0 such that
Z
lim

n→∞ 0

1

dt E Q − EhQin,t,n

2
n,t,n

= 0.

(80)

(n )n≥1 converges to 0, so Lemma 1 gives that fn,n (t) and fn (t) have the same limit (provided it exists). In
26

the rest of the section, in order to alleviate the notations, we abusively remove the perturbation subscript n
since it makes no difference for the computation of the limit of the free entropy.

5.4

Canceling the remainder

Note from (72) and (18) that the second and third terms appearing in (74) are precisely the missing ones
that are required in order to obtain the expression of the potential on the r.h.s. of (73). Thus in order to
prove Theorem 1 we would like to “cancel” the Gibbs bracket in (74), which is the so called remainder (once
integrated over t). This is made possible thanks to the adaptive interpolating parameter q. We would like to
choose q(t) = E hQit , which is approximately equal to Q because it concentrates, see Lemma 2. However,
Rt
E hQit depends on 0 q(v)dv (and on r too). The equation q(t) = E hQit is therefore a first order differential
Rt
equation over t 7→ 0 q(v)dv.
Proposition 5 (Existence of the optimal interpolation function). For all r ≥ 0 the differential equation
(81)

q(t) = E hQit
(r)

admits a unique solution qn (t) on [0, ρ] and the mapping
Z

1

r ≥ 0 7→

(82)

qn(r) (v)dv

0

is continuous.
Rt
Proof. One verify easily that E hQit is a bounded C 1 function of ( 0 q(v)dv, r). The proposition follows then
from an application of the parametric Cauchy-Lipschitz theorem.
Using this optimal choice for the interpolating function allows then to relate the potential and free entropy.
(r )

n
Proposition 6. Let (rn )n≥1 ∈ RN
be the solution of (81). Then
+ be a bounded sequence. For n ∈ N, let qn

Z

1

fn = fRS

qn(rn ) (v)dv, rn


+ On (1) .

(83)

0
(r )

Proof. qn n satisfies (81). Therefore by the Cauchy-Schwarz inequality
m

D 1 X
E
u0Yt,µ (St,µ )u0Yt,µ (st,µ ) − rn Q − qn(rn ) (t)
dt E
n
t
0
µ=1
m
Z 1
D 1 X
2 E 1/2  Z 1
2 1/2
≤
dt E
u0Yt,µ (St,µ )u0Yt,µ (st,µ ) − rn
dt E Q − qn(rn ) (t) t
= On (1) .
n
t
0
0

Z

1

µ=1

The last equality uses that the first factor is bounded (independently of t) because we supposed that Pout is
generated by (64) with assumptions (H1), (H2) and (H3) (see Appendix A.5 for proof details) and the second
factor goes to 0 when n, m → ∞ by (80), (81). Therefore from (74)
Z
0

1

rn
dfn (t)
dt =
dt
2

Z

1

qn(rn ) (t)dt −

0

rn ρ
+ On (1) .
2

(84)

When replacing this identity in (73) and combining this with (72) we reach

m
fn = ψP0 (rn ) + ΨPout
n

Z

1



qn(rn ) (t)dt; ρ

0

27

rn
−
2

Z
0

1

qn(rn ) (t)dt + On (1) .

(85)

Recalling that m/n → α as m, n → ∞ allows to recognize from (18) the claimed identity (83).

5.5

Lower and upper matching bounds

We now possess all the necessary tools to prove Theorem 1 in three steps.
(i) We prove that, under assumptions (H1), (H2) and (H3), limn→∞ fn = supr≥0 inf q∈[0,ρ] fRS (q, r).
(ii) Under hypothesis (H2), the function ΨPout is convex, Lipschitz and non-decreasing (Proposition 11). We
thus apply Corollary 5 of Appendix E to get supr≥0 inf q∈[0,ρ] fRS (q, r) = supq∈[0,ρ] inf r≥0 fRS (q, r). We
then deduce from (i) that limn→∞ fn = supq∈[0,ρ] inf r≥0 fRS (q, r) under (H1)-(H2)-(H3).
(iii) Finally, the approximation arguments given in Appendix D permit to relax (H1)-(H2) to the weaker
hypotheses (h1)-(h2) and allow to replace the Gaussian assumption (H3) on Φ by (h3.a)-(h3.b)-(h3.c).
This proves the first equality of Theorem 1. The last equality in (20) and the remaining part of Theorem 1
follow then from Lemma 13.
It remains thus to tackle (i). Let us start by the lower bound.
Proposition 7 (Lower bound). The free entropy (10) verifies
lim inf fn ≥ sup inf fRS (q, r) .
n→∞

r≥0 q∈[0,ρ]

(86)

Proof. By Proposition 6 we have that for any r ≥ 0,
fn ≥ fRS

1

Z

qn(r) (t)dt, r



+ On (1) ≥ inf fRS (q, r) + On (1)
q∈[0,ρ]

0

(87)

and thus
lim inf fn ≥ inf fRS (q, r) .
n→∞

q∈[0,ρ]

(88)

This is true for all r ≥ 0 thus we obtain Proposition 7.
We now turn our attention to the converse bound.
Proposition 8 (Upper bound). The free entropy (10) verifies
lim sup fn ≤ sup inf fRS (q, r) .
r≥0 q∈[0,ρ]

n→∞

(89)

Proof. Let K = 2αΨ0Pout (ρ; ρ). The mapping from equation (82) is continuous, consequently the application
[0, K] →
[0, K]

R 1 (r)
0
r
7→ 2αΨPout 0 qn (t)dt; ρ

(90)

is continuous (recall that Ψ0Pout denotes the derivative of ΨPout w.r.t. its first argument, and is shown to be
R 1 (r∗ )
continuous and bounded in Appendix A.2.2). It admits therefore a fixed point rn∗ = 2αΨ0Pout ( 0 qn n (t)dt; ρ).
Proposition 6 gives then
Z 1 ∗

fn = fRS
qn(rn ) (t)dt, rn∗ + On (1) .
(91)
0

28

We now remark that
fRS

Z

1


∗
qn(rn ) (t)dt, rn∗ = inf fRS (q, rn∗ ) .
q∈[0,ρ]

0

(92)

Indeed, the function grn∗ : q ∈ [0, ρ] 7→ fRS (q, rn∗ ) is convex (because of Proposition 11) and its q-derivative is
gr0 n∗ (q) = αΨ0Pout (q) −

rn∗
.
2

(93)

R 1 (r∗ )
R 1 (r∗ )
Since gr0 n∗ ( 0 qn n (t)dt) = 0 by definition of rn∗ , the minimum of grn∗ is necessarily achieved at 0 qn n (t)dt.
Combining (91) with (92) we reach
fn = inf fRS (q, rn∗ ) + On (1) ≤ sup inf fRS (q, r) + On (1)
q∈[0,ρ]

r≥0 q∈[0,ρ]

(94)

which allows to deduce Proposition 8.
From the arguments given at the beginning of the section, this ends the proof of Theorem 1.

Appendix A: Some technicalities
A.1

The Nishimori identity

Proposition 9 (Nishimori identity). Let (X, Y) ∈ Rn1 × Rn2 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 denote h−i the 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
Ehg(Y, X(1) , . . . , X(k) )i = Ehg(Y, X(1) , . . . , X(k−1) , X)i .

(95)

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 first 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).

A.2
A.2.1

Some properties of the scalar channels
The additive Gaussian scalar channel

We recall here some properties of the free entropy of the first scalar channel (12).
Proposition 10. Let X0 ∼ P0 be a real random variable with finite second moment. Let r ≥ 0 and Y0 =
√
rX0 + Z0 , where Z0 ∼ N (0, 1) is independent from X0 . Then the function
Z
√
2
ψP0 : r 7→ E ln dP0 (x)e r Y0 x−rx /2
is convex, differentiable, non-decreasing and 12 E[X02 ]-Lipschitz on R+ . Moreover, ψP0 is strictly convex, if P0 is
not a Dirac measure.
Proof. Denote by h−ir the posterior distribution of X0 given Y0 in the channel (12). Using Gaussian integration by parts and the Nishimori property (Proposition 9), one verify easily that for all r ≥ 0
2ψP0 0 (r) = EhxX0 ir = Ehxi2r ∈ [0, E[X02 ]] ,
29

where x ∼ h−ir , independently of everything else. ψP0 0 is non-decreasing because it is linked to the minimal
mean square error mmse(r) of the channel (12) which is non-increasing with r:
h
2 i
mmse(r) = E X0 − E[X0 |Y0 ]
= E[X02 ] − 2ψP0 0 (r) .
It remains to show that ψP0 is strictly convex when P0 differs from a Dirac mass. When P0 admits a finite
moment of order 4, one can compute the second derivative and again, using Gaussian integration by parts
and the Nishimori identity one obtain:
2 i
1 h
ψP00 0 (r) = E hx2 ir − hxi2r
.
2
(N )

Without the 4th moment assumption, one can proceed by truncation. We consider now the distribution P0
(N )
of X0 = X0 I(−N ≤ X0 ≤ N ). h−ir,N will denote the corresponding posterior distribution. We apply
the previous computation to obtain
ψ 0 (N ) (t)
P0

−

ψ 0 (N ) (s)
P0

1
=
2

t

Z

h

hx2 ir,N − hxi2r,N

E

2 i

dr ,

(96)

s

for 0 < s < t. Now suppose that ψP0 0 is not strictly increasing. We can then find 0 < s < t such that
ψP0 0 (s) = ψP0 0 (t). The sequence of convex functions (ψP (N ) )N converges to ψP0 which is differentiable. A
0

standard analysis lemma gives then that the derivatives (ψ 0

(N )

P0

)N converges to ψP0 0 . Therefore, equation (96)

and Fatou’s Lemma lead to

Z t 
Z t h
2
2 i
2
2
0≤
E lim inf hx ir,N − hxir,N
dr ≤ lim inf
E hx2 ir,N − hxi2r,N
dr = 0 .
s

N →∞

N →∞

s

It is not difficult to verify that hx2 ir,N − hxi2r,N −−−−→ hx2 ir − hxi2r almost surely. We conclude
N →∞

Z

t

h
E

hx2 ir − hxi2r

2 i

dr = 0 .

s

We can thus find r ∈ [s, t] such that hx2 ir − hxi2r = 0 almost surely. This means that h−ir is almost surely a
Dirac distribution. This is absurd because h−ir admits almost surely a strictly positive density w.r.t. P0 , and
P0 is assumed not to be a Dirac distribution. This concludes the proof.
A.2.2

The non-linear scalar channel

We prove here some properties of the free entropy of the second scalar channel (15).
Proposition 11. Let Pout be as in (3) where ϕ : R × RkA → R is a measurable function. Suppose that for
(Z, A) ∼ N (0, 1) ⊗ PA we have
√
E[ϕ( ρZ, A)2 ] < ∞ .
(97)
Let V, W ∗ i.i.d.
∼ N (0, 1) and Y be the output of the scalar channel (15). Then for all q ∈ [0, ρ],
Z
ΨPout (q) = E ln

w2


√
e− 2
√
dw √ Pout Y | q V + ρ − q w
2π

is well define and the function ΨPout is convex, non-decreasing on [0, ρ] and differentiable on [0, ρ). Moreover, if
ϕ is bounded and C 2 with respect to its first coordinate, with bounded first and second derivatives, then ΨPout is
Lipschtitz on [0, ρ].
30

Notice that (97) is for instance verified under hypotheses (h2).
Proof. We have for all x, y ∈ R
1
Pout (y|x) = √
2π∆

Z



1
1
2
exp −
(y − ϕ(x, a)) dPA (a) ≤ √
.
2∆
2π∆

Thus, using Jensen’s inequality
√
1
1
√
Ea,w (Y − ϕ( qV + ρ − qw))2
− ln(2π∆) −
2
2∆
w2
Z

√
1
e− 2
√
≤ ln dw √ Pout Y | q V + ρ − q w ≤ − ln(2π∆) ,
2
2π

(98)

where Ea,w denotes the expectation w.r.t. (w, a) ∼ N (0, 1) ⊗ PA . By assumptions, the left-hand side is integrable, so that ΨPout (q) is well defined for all q ∈ [0, ρ].
Let us assume now that ϕ is bounded and C 2 w.r.t. its first coordinate, with bounded first and second
derivatives. In that case, we will be able to use continuity and differentiation under the expectation, because
all the domination hypotheses will be easily verified. It is thus easy to check that ΨPout is continuous on [0, ρ].
We compute now the first derivative. Recall that h−isc , defined in (17), denotes the posterior distribution
of W ∗ given Y . We will use the notation uy (x) = ln Pout (y|x). For q ∈ (0, ρ) we have
E
√
√
1 D
√
√
Ψ0Pout (q) = E u0Y ( qV + ρ − qw)u0Y ( qV + ρ − qW ∗ )
2
sc
E2
√
1 D 0 √
= E uY ( qV + ρ − qw)
≥ 0,
2
sc
where w ∼ h−isc , independently of everything else. ΨPout is therefore non-decreasing. Using the boundedness assumption on ϕ, it is not difficult to check that Ψ0Pout is indeed bounded. ΨPout is thus Lipschtitz.
√
√
We will now compute Ψ00Pout . To lighten the notations, we write u0Y (w) for u0Y ( qV + ρ − qw). We
compute
D
E
h 1

D
E i
1
∂q E u0Y (w)u0Y (W ∗ )
=E
W ∗ u0Y (W ∗ ) u0Y (w)u0Y (W ∗ )
√ V − √
2 q
2 ρ−q
sc
sc
D 1

E
1
+2E
W ∗ u00Y (W ∗ )u0Y (w)
√ V − √
2 q
2 ρ−q
sc
D 1

E
1
+E
W ∗ u0Y (W ∗ )2 u0Y (w)
√ V − √
2 q
2 ρ−q
sc
D
E D 1

E
1
−E u0Y (W ∗ )u0Y (w)
w u0Y (w)
√ V − √
2 q
2 ρ−q
sc
sc

(A)
(B)
(C)
(D)

(99)

Notice that (A) = (C). We compute, using Gaussian integration by parts and the Nishimori identity (Pro-

31

position 9)
D
E i 1 h
D
E i
1 h
(A) = E u0Y (W ∗ ) u0Y (W ∗ )u00Y (w)
+ E u0Y (W ∗ ) u0Y (W ∗ )u0Y (w)2
2
2
sc
sc
D
E D
E i
1 h 0
− E uY (W ∗ ) u0Y (W ∗ )u0Y (w)
u0Y (w)
2
sc
D
E D
D
Esc
D
E

− E u00Y (W ∗ )u0Y (w)
+ E u00Y (W ∗ )u0Y (w)2
(B) = E u00Y (W ∗ )u00Y (w)
sc
sc
D 1

E
1
∗
0
∗ 0
(1) 0
(2)
√
V
−
W
u
(W
)u
(w
)u
(w
)
(D) = −E
√
Y
Y
Y
2 q
2 ρ−q
sc

sc

(100)
u0Y (w)

E
sc

(101)

= −Ehu0Y (W ∗ )u00Y (w(1) )u0Y (w(2) )isc − Ehu0Y (W ∗ )u0Y (w(1) )2 u0Y (w(2) )isc
+ Ehu0Y (W ∗ )u0Y (w(1) )u0Y (w(2) )isc hu0Y (w)isc

(102)

We now replace (100), (101) and (102) in (99):
D
E
D
E
D
E
− E u0Y (W ∗ )2 u0Y (w(1) )u0Y (w(2) )
+ E u0Y (W ∗ )2 u0Y (w)2
2Ψ00Pout (q) = E u0Y (W ∗ )2 u00Y (w)
E sc
E sc D
D
E sc D
00
∗ 0
(1) 0
(2)
00
∗ 0
2
00
∗ 00
− E uY (W )uY (w )uY (w )
+ E uY (W )uY (w)
+ E uY (W )uY (w)
−

sc
0
∗ 00
(1) 0
EhuY (W )uY (w )uY (w(2) )isc

Using the identity u00Y (x) + u0Y (x)2 =
Ψ00Pout (q)

00 (Y |x)
Pout
Pout (Y |x) ,

−

sc
0
∗ 0
EhuY (W )uY (w(1) )2 u0Y (w(2) )isc

+

sc
0
4
EhuY (w)isc .

this factorizes and gives

E 2 2 i
D
00 (Y |√q V + √ρ − qw) E
√
1 hD Pout
√
√
= E
≥ 0.
− u0Y ( q V + ρ − qw)
√
2
Pout (Y | q V + ρ − qw) sc
sc

(103)

ΨPout is thus convex on [0, ρ].
It remains now to prove that ΨPout is convex without the boundedness and C 2 assumptions on ϕ. Using
the same arguments than in Appendix D one see that we can approximate with arbitrary precision ΨPout with
a function ΨP̂out , where P̂out can be represented by a couple (ϕ̂, ∆) and ϕ̂ is bounded and C 2 w.r.t. its first
coordinate, with bounded first and second derivatives. This proves that ΨPout is convex. The fact that ΨPout
is differentiable on [0, ρ) follows from differentiation under the expectation sign. In order to see it, we define
√
√
X = q V + ρ − q W ∗ . Then, for all q ∈ [0, ρ):
Z
ΨPout (q) = E

1

−

e
dX p
2π(ρ − q)

√
(X− q V )2
2(ρ−q)

Z

Z
dY Pout (Y |X) ln

dx p

1
2π(ρ − q)

e

−

√
(x− q V )2
2(ρ−q)

Pout (Y |x) .
(104)

We are now in a good setting to differentiate under the expectation sign. The domination follows by the same
convexity argument than for (98).

A.3

Proof of Theorem 2

Define for ∆ > 0,
m
ln(2π∆)
fˆn (∆) = fn +
2n


Z
m
X
√
1
1
= E log  dP0 (x)dPa (a) exp −
(ϕ([ΦX]µ , Aµ ) − ϕ([Φx]µ , aµ ) + ∆Zµ )2 
n
2∆
µ=1

32

Lemma 3.

m
fˆn (∆) −−−→ ξn −
∆→0
2n

Proof. This follows from two applications of the dominated convergence Theorem. Define



Z
m
X
√
1
(ϕ([ΦX]µ , Aµ ) − ϕ([Φx]µ , aµ ) + ∆Zµ )2 
h(X, A, Z, ∆) = log  dP0 (x)dPa (a) exp −
2∆
µ=1

and


Z
g(X, A, Z) = log 

dP0 (x)dPa (a)

m
Y

Z2
− 2µ

δ (ϕ([ΦX]µ , Aµ ) − ϕ([Φx]µ , aµ )) e




µ=1

By the dominated convergence Theorem (the domination is here obvious), for all Φ, X, A, Z
h(X, A, Z, ∆) −−−→ g(X, A, Z) .
∆→0

Now, for all Φ, X, A, Z, x, a we have
m
Y

δ(ϕ([ΦX]µ , Aµ ) − ϕ([Φx]µ , aµ )) e−

2
Zµ
2

m

 1 X
√
(ϕ([ΦX]µ , Aµ )−ϕ([Φx]µ , aµ )+ ∆Zµ )2 ≤ 1
≤ exp −
2∆
µ=1

µ=1

Consequently, g(X, A, Z) ≤ h(X, A, Z, ∆) ≤ 0 . Thus h is lower and upper bounded by integrable random
variables (that do not depend on ∆). We can thus apply the dominated convergence Theorem to obtain the
Lemma.
(∆)

We will need to write explicitely the dependence of Pout in ∆ by writting: Pout . We also define
Ψ̂P (∆) (q) = ΨP (∆) (q) +
out

out

1
ln(2π∆)
2

Let (∆k )k≥0 be a sequence of positive numbers that converges to 0.


Lemma 4. The sequence Ψ̂ (∆k )
converges uniformly on [0, ρ] to Ψϕ − 21 .
Pout

k≥0

Proof. The pointwise convergence is proved using the same arguments as in the previous lemma. The uni
form convergence follows from Dini’s second Theorem, Ψ̂ (∆k ) k≥0 is indeed a sequence of non-decreasing
Pout

functions on [0, ρ] that converges pointwise to Ψϕ − 12 , which is continuous over [0, ρ] (as a pointwise limit
of convex functions, for instance).
The uniform convergence implies then the convergence of the sup − inf :
Corollary 4.
n
n
rq o
rq o α
sup inf ψP0 (r) + αΨP (∆) (q) −
−−−→ sup inf ψP0 (r) + αΨϕ (q) −
−
∆→0 q∈[0,ρ] r≥0
out
2
2
2
q∈[0,ρ] r≥0
We have now all the tools needed for the proof of Theorem 2.
Proof of Theorem 2. We extend by continuity (see Lemma 3) fˆn at ∆ = 0, to obtain a sequence of convex

33

functions on [0, 1]. Define for ∆ ∈ [0, 1]

o
n
supq∈[0,ρ] inf r≥0 ψP0 (r) + αΨ (∆) (q) − rq
Pout
n
o2
fˆ∞ (∆) =
rq
sup
− α2
q∈[0,ρ] inf r≥0 ψP0 (r) + αΨϕ (q) − 2

if ∆ > 0 ,
if ∆ = 0 .

By Theorem 1, fˆ∞ is the pointwise limit of the sequence of convex functions (fˆn )n≥1 on (0, 1], it is thus
continuous on (0, 1]. By Corollary 4 we obtain that fˆ∞ is continuous on [0, 1].
Moreover, fˆn is differentiable on (0, 1) and it is not difficult to check that its derivative is uniformly
bounded in n:
" 
2 #
m
1
0
∀n ≥ 1, sup |fn (∆)| ≤
E ϕ √ [ΦX]1 , A1
n
n
∆∈(0,1)
which is bounded by assumption (h2). This implies that fˆn (0) → fˆ∞ (0), otherwise the derivative of fˆn would
explode near 0.

A.4

Proof of Proposition 1

In this section, we prove Proposition 1. In order to prove Proposition 1, we will need the following lemma.
For k ≥ 1 we denote by Sk+ the set of positive semi-definite k × k matrices and by Sk+∗ the set of positive
definite k × k matrices.
Lemma 5. Let (Cn )n≥1 be a sequence of random variables in Sk+ , that converges in law to C, such that C is
almost surely positive definite. Let f : Rk → R be a measurable function and Z ∼ N (0, Ik ) be independent
from (Cn ). Assume that the sequence (f (Cn Z))n≥1 is uniformly integrable. Then
E[f (Cn Z)] −−−→ E[f (CZ)]
n→∞

Proof. By the uniform integrability assumption, it suffices to show that (f (Cn Z))n converges to f (CZ) in
law. Let g : R → R be a continuous bounded function. Let EZ denote the expectation w.r.t. Z only. Then the
function
h : Sk+ → R
M 7→ EZ [g(f (MZ))]
is continuous over Sk+∗ . Indeed, for M ∈ Sk+∗ ,
1
h(M) =
k/2
(2π) |detM|k

Z



1 | −2
exp − x M x g(f (x))dx .
2

The discontinuity points of h are thus in Sk+ \ Sk+∗ , which has 0 measure for the law of C (because C is
a.s. positive definite). Consequently, by Portemanteau Theorem E[h(Cn )] → E[h(C)] which proves that
(f (Cn Z))n converges to f (CZ) in law.
We can now prove Proposition 1.
Proof. We define
1
Cn =
n

kX∗ k2 x · X∗
x · X∗ kxk2

!

34

P

−−−→
n→∞

ρ q
q ρ

!
∈ S2+∗

By the Nishimori property, one verify easily that
* 
 
  
 2


2 +
Φnew · X∗
Φnew · x
Φnew · x
1
Φnew · X∗
√
√
√
√
E ϕ
,A − ϕ
,a
,A − ϕ
,a
= E
ϕ
2
n
n
n
n
n
n
*
 


2 +
∗
Φnew · X
Φnew · x
1
√
√
,A − ϕ
,a
= E Ea,A ϕ
2
n
n

n

Now, we remark that

 


2
Φnew · X∗
Φnew · x
√
√
Ea,A ϕ
,A − ϕ
,a
n
n

is simply a measurable function that we denote f of


Φnew · X∗ Φnew · x
√
= C1/2
, √
n Z
n
n
in law, where Z ∼ N (0, I2 ) is independent from Cn . We can thus apply Lemma 5 (the uniform integrability
assumption follows from our hypothesis (h2)):
*
 


2 +
Φnew · X∗
Φnew · x
√
√
lim E Ea,A ϕ
,A − ϕ
,a
n→∞
n
n
n
h
2 i
√
√
√
√
1/2
= E[f (C Z)] = E ϕ( qZ1 + ρ − qZ2 , A) − ϕ( qZ1 + ρ − qZ20 , a)
for Z1 , Z2 , Z20 i.i.d.
∼ N (0, 1). By expanding the square of the right-hand side and applying Bayes rule, one
obtains exactly twice the right-hand side of (39). This concludes the proof.

A.5

Boundedness of an overlap fluctuation

In this appendix we show that the “overlap fluctuation”
m
m
D 1 X
2 E
D 1 X
2 E
0
0
2
E
uYt,µ (St,µ )uYt,µ (st,µ ) − rn
≤ 2rn + 2E
u0Yt,µ (St,µ )u0Yt,µ (st,µ )
n
n
t
t
µ=1

(105)

µ=1

is bounded uniformly in t under hypothesis (H2) on ϕ. From the representation (3) (recall we consider ∆ = 1
in Sec. 5)
uYt,µ (s) = ln Pout (Yt,µ |s)
Z
1
1
2
= ln dPA (aµ ) √ e− 2 (Yt,µ −ϕ(s,aµ ))
2π

(106)

and thus
u0Yt,µ (s)

R
=

1

2

dPA (aµ )(Yt,µ − ϕ(s, aµ ))ϕ0 (s, aµ )e− 2 (Yt,µ −ϕ(s,aµ ))
R
1
2
dPA (aµ )e− 2 (Yt,µ −ϕ(s,aµ ))

(107)

where ϕ0 is the derivative w.r.t. the first argument. From (1) at ∆ = 1 we get |Yt,µ | ≤ sup |ϕ| + |Zµ |, where
the supremum is taken over both arguments of ϕ, and thus immediately obtain for all s ∈ R
|u0Yt,µ (s)| ≤ (2 sup |ϕ| + |Zµ |) sup |ϕ0 | .

35

(108)

From (108) and (105) we see that it suffices to check that
2 
m2 
E (2 sup |ϕ| + |Zµ |)2 (sup |ϕ0 |)2
≤ C(ϕ)
2
n
where C(ϕ) is a constant depending only on ϕ. This is easily seen by expanding all squares and using that
m/n is bounded.

Appendix B: Proofs of the limits of optimal errors
B.1

Computation of the denoising error: Proof of Corollary 3

One can verify easily that in (defined by (21)) is a concave differentiable function of ∆−1 (see [40]). Thus its
limit i∞ is also a concave function of ∆−1 . Therefore, a standard analysis lemma gives that the derivative of
in w.r.t. ∆−1 converges to the derivative of i∞ at every point at which i∞ is differentiable (i.e. almost every
points, by concavity). Let us now compute these two derivatives. Using the I-MMSE Theorem from [40], one
obtain
m
 1
 D  1
E
1 X
∂in
∗
√
√
=
E
ϕ
[ΦX
]
,
A
−
ϕ
[Φx]
,
a
µ
µ
µ
µ
∂∆−1
2n
n
n

2

.

(109)

µ=1

Second, define
h(q, ∆) =

n
qr o
α
(1 + ln(2π∆)) + αΨPout (q) + inf ψP0 (r) −
.
r≥0
2
2

(110)

Then i∞ = − supq∈[0,ρ] h(q, ∆). The computation of ∂ΨPout (q)/∂∆−1 follows from the I-MMSE theorem
√
√
√
of [40]. Indeed, if we denote S = ϕ( qV + ρ − qW ∗ , A), notice that ΨPout (q) = −I(S; S + ∆Z | V ) −
√
√
√
1
2 log(2πe∆), because ΨPout (q) = −H(S + ∆Z | V ) and I(S + ∆Z; S | V ) = H(S + ∆Z | V ) − H(S +
√
∆Z | V, S) = −ΨPout (q) − 12 log(2πe∆). Therefore
√
√
∂ΨPout (q)
∆
∂
∆ 1
=
−
I(S
+
∆Z;
S
|
V
)
=
−
MMSE(S
+
∆Z | V, S)
∂∆−1
2
∂∆−1
2
2

p
p



∆ 1  √
=
−
E ϕ( ρ V, A)2 − E ϕ( q ∗ V + ρ − q ∗ w, a)i2sc .
2
2
Consequently,
p
p



∂h(q, ∆)
α  √
2
∗V +
∗ w, a)i2
E
ϕ(
ρ
V,
A)
−
E
ϕ(
q
ρ
−
q
.
=
−
sc
∂∆−1
2
Now, Theorem 1 from [61] gives that at every ∆−1 at which i∞ is differentiable
p
p



∂i∞
∂
α  √
2
∗V +
∗ w, a)i2
ρ
V,
A)
−
E
ϕ(
q
ρ
−
q
=
−
sup
h(q,
∆)
=
E
ϕ(
.
sc
∂∆−1
∂∆−1 q∈[0,ρ]
2
where q ∗ ∈ [0, ρ] is a point where the supremum above is achieved, and thus correspond to an optimal couple
in (20). As explained above, ∂in /∂∆−1 converges to ∂i∞ /∂∆−1 at every ∆−1 at which i∞ is differentiable,
which concludes the proof.

36

B.2

Optimal generalization error with side information: Proof of Proposition 2

Here the arguments are the same as for the proof of Corollary 3, but we repeat them briefly for the reader.
By a straightforward generalization of (22), fn is related to the mutual information I(X∗ , A; Y|Φ) between
the noisy labels and the classifier and stream A through
in :=

1
α
I(X∗ , A; Y|Φ) = −fn − − αβ ln(2π∆tr ) − α(1 − β) ln(2π∆te ) ,
n
2

(111)

Now in order to access the generalization error we employ the classical I-MMSE relation [40] for Gaussian
noise but restricted to the test set. It takes the following form in the present setting
(1 − β)m side
din
=
Egen .
te
−1
d(∆ )
2n

(112)

Again we use that in is a sequence of concave functions in (∆te )−1 and thus its limit (which exists by Theorem 1) is concave too. Again, these concavity properties allow to permute limits and differentiation. Therefore from (111) and (112) we find that for almost every ∆te > 0
lim E side
n→∞ gen

= ∆te −

2
d
sup inf f ts (q, r) .
α(1 − β) d(∆te )−1 q∈[0,ρ] r≥0 RS

(113)

It remains to evaluate this derivative using (46) to finally assess the asymptotic generalization error. This is
done as in the previous section using an envelope Theorem, see [61].

Appendix C: Proof of Proposition 4
0 (y|x) and P 00 (y|x) the first
Recall u0y (x) is the x-derivative of uy (x) = ln Pout (y|x). Moreover denote Pout
out
and second x-derivatives, respectively, of Pout (y|x). We will first prove that for all t ∈ (0, 1)
m
n
 1 X
E
dfn (t)
1 D 1 X 0
rq(t) rρ An
=− E
uYµ (St,µ )u0Yµ (st,µ ) − r
Xi∗ xi − q(t)
+
−
−
,
dt
2
n
n
2
2
2
t
µ=1

(114)

i=1

where
m
n
1
i
h 1 X
00 (Y |S ) 
Pout
1 X
µ t,µ
√
((Xi∗ )2 − ρ)
ln Zt .
An := E √
n
n µ=1 Pout (Yµ |St,µ )
n

(115)

i=1

Once this is done, we will prove that An goes to 0 as n → ∞ uniformly in t ∈ [0, 1], in order to obtain
Proposition 4.

C.1

Proof of (114)

Recall definition (71) which becomes, when written as a function of the interpolating Hamiltonian (68),
Z
Z
1
0
0
∗
∗ −Ht (X∗ ,W∗ ;Y,Y 0 ,Φ,V)
fn (t) = EΦ,V dYdY dP0 (X )DW e
ln dP0 (x)Dw e−Ht (x,w;Y,Y ,Φ,V) .
n
(116)

37

We will need the Hamiltonian t-derivative Ht0 given by
Ht0 (X∗ , W∗ ; Y, Y0 , Φ, V)

=−

m
X
dSt,µ
µ=1

dt

u0Yµ (St,µ )

1
−
2

r

n
rX ∗ 0 √
Xi (Yi − t rXi∗ ) .
t

(117)

i=1

The derivative of the interpolating free entropy thus reads, for 0 < t < 1,
 1
dfn (t)
1 
= − E Ht0 (X∗ , W∗ ; Y, Y0 , Φ, V) ln Zt − E Ht0 (x, w; Y, Y0 , Φ, V) t
dt
{z
} |n
{z
}
|n
T1

(118)

T2

where recall the definition of Zt = Zt (Y, Y0 , Φ, V) given by (70).
Let us compute T1 . Let 1 ≤ µ ≤ m. Let us start with the following term

i
h dS
i 1 h
[ΦX∗ ]µ
ρ − q(t)
q(t)
t,µ 0
Vµ + qR
Wµ∗ u0Yµ (St,µ ) ln Zt .
E
+ qR
uYµ (St,µ ) ln Zt = E − p
t
t
dt
2
n(1 − t)
0 q(s)ds
0 (ρ − q(s))ds
(119)
Let us compute the first term of the right-hand side of the last identity. By Gaussian integration by parts w.r.t
Φµi we obtain


1
p
E [ΦX∗ ]µ u0Yµ (St,µ ) ln Zt
n(1 − t)
n
hZ
i
X
1
∗
∗
0
=p
E
dYdY0 e−Ht (X ,W ;Y,Y ,Φ,V) Φµi Xi∗ u0Yµ (St,µ ) ln Zt
n(1 − t) i=1
=

n



1 X  ∗ 2 00
E (Xi ) uYµ (St,µ ) + u0Yµ (St,µ )2 ln Zt + E Xi∗ xi u0Yµ (St,µ )u0Yµ (st,µ ) t
n
i=1

n
n
i
D1 X
E
h1 X
P 00 (Yµ |St,µ )
(Xi∗ )2 out
ln Zt + E
Xi∗ xi u0Yµ (St,µ )u0Yµ (st,µ ) ,
=E
n
Pout (Yµ |St,µ )
n
t
i=1

(120)

i=1

where we used the identity
u00Yµ (x) + u0Yµ (x)2 =

00 (Y |x)
Pout
µ
.
Pout (Yµ |x)

(121)

We now compute the second term of the right hand side of (119). Using again Gaussian integrations by parts
but this time w.r.t Vµ , Wµ∗ i.i.d.
∼ N (0, 1) as well as the previous formula, we obtain similarly
h

i
q(t)
ρ − q(t)
E qR
Vµ + qR
Wµ∗ u0Yµ (Sµ,t ) ln Zt
t
t
0 q(s)ds
0 (ρ − q(s))ds

i
hZ

q(t)
ρ − q(t)
∗
∗
0
=E
dYdY0 e−Ht (X ,W ;Y,Y ,Φ,V) qR
Vµ + qR
Wµ∗ u0Yµ (Sµ,t ) ln Zt
t
t
0 q(s)ds
0 (ρ − q(s))ds
i
h P 00 (Y |S )
µ µ,t
ln Zt + E q(t)u0Yµ (Sµ,t )u0Yµ (sµ,t ) t .
(122)
= E ρ out
Pout (Yµ |Sµ,t )

38

Combining equations (119), (120) and (122) together, we have
h dS
i
t,µ 0
−E
uYµ (St,µ ) ln Zt
dt
n
n
h

i 1 D 1 X

E
00
1 P (Yµ |Sµ,t )  1 X ∗ 2
= E out
(Xi ) − ρ ln Zt + E
Xi∗ xi − q(t) u0Yµ (St,µ )u0yµ (st,µ ) . (123)
2 Pout (Yµ |Sµ,t ) n
2
n
t
i=1

i=1

As seen from (118) it remains to compute, recalling that for 1 ≤ j ≤ n, Yj0 −
Gaussian integration by parts w.r.t Zj0 ∼ N (0, 1),

√

t rXj∗ = Zj0 and then again a

Z
h
i
 ∗ 0 √

 ∗ 0

0
∗
∗ 0
E Xj (Yj − t rXj ) ln Zt = E Xj Zj ln Zt = E Xj Zj ln dP0 (x)Dw e−Ht (x,w;Y,Y ,Φ,V)
Z
n
m
h
n X
√
2 oi
1X √
∗ 0
= E Xj Zj ln dP0 (x)Dw exp −
uYµ (st,µ ) +
trXi∗ + Zi0 − t r xi
2
µ=1
i=1

 ∗ √
∗
0
t r(Xj − xj ) + Zj t
= E Xj
√

(124)
= t r ρ − EhXj∗ xj it .
Thus, by taking the sum,
1
−
2

r

n
n
E
i rρ r D 1 X
r h1 X ∗ 0 √
E
Xi (Yi − t rXi∗ ) ln Zt =
− E
Xi∗ xi .
t n
2
2 n
t
i=1

(125)

i=1

Therefore, for all t ∈ (0, 1),
m
n
1
i rρ rq(t)
00 (Y |S ) 
1 h 1 X Pout
1 X
µ µ,t
∗ 2
√
√
T1 = E
((Xi ) − ρ)
ln Zt +
−
2
Pout (Yµ |Sµ,t )
n
2
2
n
n
µ=1

i=1

m
n
 1 X
E
1 D 1 X 0
uYµ (St,µ )u0Yµ (st,µ ) − r
+ E
Xi∗ xi − q(t)
.
2
n
n
t
µ=1

(126)

i=1

To obtain (114), it remains to show that T2 = 0. This is a direct consequence of the Nishimori identity (see
Appendix A.1):
T2 =

1
E Ht0 (x, w; Y, Y0 , Φ)
n

t

=

1
E Ht (X∗ , W∗ ; Y, Y0 , Φ) = 0 .
n

(127)

For obtaining the Lemma, it remains to show that An goes to 0 uniformly in t ∈ [0, 1].

C.2

Proof that An vanishes as n → ∞

We now consider the final step, that is showing that An given by (115) vanishes in the n → ∞ limit uniformly
in t ∈ [0, 1] under conditions (H1)-(H2)-(H3). First we show that
m
n
h 1 X
i
00 (Y |S ) 
Pout
1 X
µ t,µ
√
fn (t)E √
((Xi∗ )2 − ρ) = 0 .
n µ=1 Pout (Yµ |St,µ )
n

(128)

i=1

Once this is done, we use the fact that n1 ln Zt concentrates around fn (t) to prove that An converges to 0
R 00
as n → ∞. We start by noticing the simple fact that for all s ∈ R, Pout
(y|s)dy = 0. Consequently, for

39

µ ∈ {1, . . . , m},
h P 00 (Y |S )
i Z
out µ t,µ
∗
00
E
X , St = dYµ Pout
(Yµ |St,µ ) = 0 .
Pout (Yµ |St,µ )

(129)

Thus, using the “tower property” of the conditionnal expectation:
n
m
n
m
ii
h X
X
h X
 hX
00 (Y |S ) i
00 (Y |S )
Pout
Pout
µ t,µ
µ t,µ
X ∗ , St = 0
E
((Xi∗ )2 − ρ)
=E
((Xi∗ )2 − ρ) E
Pout (Yµ |St,µ )
Pout (Yµ |St,µ )
i=1

µ=1

µ=1

i=1

(130)
which implies (128). We now show that An goes to 0 uniformly in t ∈ [0, 1] as n → ∞. Using successively
(128) and the Cauchy-Schwarz inequality, we have
m
n
h 1 X
i
 1
00 (Y |S ) 
Pout
1 X
µ t,µ
√
√
|An | = E
ln Zt − fn (t)
((Xi∗ )2 − ρ)
n
n µ=1 Pout (Yµ |St,µ )
n
i=1

m
n
h 1 X
2 i1/2 h 1
2 i1/2
00 (Y |S ) 2 
Pout
1 X
µ t,µ
√
≤ E √
E
.
((Xi∗ )2 − ρ)
ln Zt − fn (t)
n
n µ=1 Pout (Yµ |St,µ )
n

(131)

i=1

Using again the “tower property” of conditional expectations
m
n
n
m
h X
2 i
h X
ii
2 h X
00 (Y |S ) 2  X
00 (Y |S ) 2
Pout
Pout
µ t,µ
µ t,µ
∗ 2
∗ 2
E
((Xi ) − ρ)
=E
X∗ , St .
((Xi ) − ρ) E
Pout (Yµ |St,µ )
Pout (Yµ |St,µ )
µ=1

i=1

µ=1

i=1

(132)
Now, using the fact that conditionally on St , the random variables
we have


00 (Y |S
Pout
µ t,µ )
Pout (Yµ |St,µ ) 1≤µ≤m

are i.i.d. and centered,

m
m
h X
i
h X
i
h P 00 (Y |S ) 2
i
00 (Y |S ) 2
00 (Y |S ) 2
Pout
Pout
µ t,µ
µ t,µ
out 1 t,1
X∗ , St = E
St = mE
St . (133)
E
Pout (Yµ |St,µ )
Pout (Yµ |St,µ )
Pout (Y1 |St,1 )
µ=1

µ=1

Under condition (H2), it is not difficult to show that there exists a constant C > 0 such that
h P 00 (Y |S ) 2
i
out 1 t,1
E
St ≤ C .
Pout (Y1 |St,1 )

(134)

Combining now (134), (133) and (132) we obtain that
m
n
n
h X
2 i
h X
2 i
00 (Y |S ) 2  X

Pout
µ t,µ
((Xi∗ )2 − ρ)
≤ mC E
((Xi∗ )2 − ρ)
= mnC Var (X1∗ )2 .
E
Pout (Yµ |St,µ )
µ=1

i=1

i=1

Going back to (131), therefore there exists a constant C 0 > 0 such that
2 i1/2
h 1
|An | ≤ C 0 E
ln Zt − fn (t)
.
n

(135)

By Theorem 4 we have E[(n−1 ln Zt − fn (t))2 ] → 0 as n → ∞ uniformly in t ∈ [0, 1]. Thus An goes to 0
uniformly in t ∈ [0, 1] as n → ∞. This ends the proof of Proposition 4.

40

Appendix D: Approximation
In this section, we suppose that Theorem 1 holds for channels of the form (1) under the hypotheses (H1), (H2)
and (H3).
We show in this section that this imply that Theorem 1 holds under the hypotheses (h1), (h2), and either
(h3) or (h3.a)-(h3.b)-(h3.c). Again, as explained at the beginning of Sec. 5, it suffices to consider the case where
∆ = 1. We start by relaxing the hypothesis (H1).

D.1

Relaxing the hypotheses on P0 and Φ

The goal of this section is to prove the following proposition:
Proposition 12. Suppose that (h1) holds and that ϕ is C ∞ with compact support. Suppose that (h3) or (h3.a)(h3.b)-(h3.c) hold. Then Theorem 1 holds.
Proposition 12 will follow from Lemma 6 and Lemma 7 below.
Lemma 6. Suppose that (h1) (H2) and (h3) hold. Then Theorem 1 holds.
Proof. The ideas are basically the same that in [55] (Sec. 6.2.2). We omit the details here for the sake of
brevity.
We now relax the Gaussian assumption on the “measurement matrix” Φ.
Lemma 7. Suppose that (h1) holds, and that ϕ is C ∞ with compact support. Suppose that (h3.a)-(h3.b) hold.
Then Theorem 1 holds.
Proof. The proof is based on the Lindeberg generalization theorem (Theorem 2 from [49]) which is a variant
of the generalized “Lindeberg principle” from [25].
Theorem 3 (Lindeberg generalization theorem). Let (Ui )1≤i≤n and (Vi )1≤i≤n be two collection of random
variables with independent components and f : Rn → R a C 3 function. Denote ai = |EUi − EVi | and bi =
|EUi2 − EVi2 |. Then
n 
X
bi
ai E|∂i f (U1:i−1 , 0, Vi+1:n )| + E|∂i2 f (U1:i−1 , 0, Vi+1:n )|
|Ef (U) − Ef (V)| ≤
2
i=1
Z Ui
Z Vi

1
1
3
2
3
2
+ E
|∂ f (U1:i−1 , 0, Vi+1:n )|(Ui − s) ds + E |∂i f (U1:i−1 , 0, Vi+1:n )|(Vi − s) ds .
2 0 i
2 0

Let (Φ0µ,i ) i.i.d.
∼ N (0, 1) and let (Φµ,i ) be a family of independent random variables, with zero mean and
unit variance. Let fn0 be the free entropy (10) with design matrix Φ0 and fn be the free entropy (10) with
design matrix Φ.
We will apply Theorem 3 to the function
F : U ∈ Rm×n 7→

1
E ln
n

Z

− 12

dPA (a)dP0 (x) e

m
P

 

 
2
ϕ √1n [UX∗ ]µ ,Aµ −ϕ √1n [Ux]µ ,aµ +Zµ

µ=1

x,a

where the expectation E is taken w.r.t. X∗ , A and Z. We have
fn = EF (Φ)

and

41

fn0 = EF (Φ0 ) .

It is not difficult to verify that F is a C 3 function and that for all 1 ≤ µ ≤ m and 1 ≤ i ≤ n:
∂3F
3
∂Uµ,i

≤
∞

C
,
n5/2

for some constant C that only depends on ϕ and the first three moments of P0 . Thus, an application of
Theorem 3 gives
C
|fn − fn0 | ≤ √ .
n
By Proposition 6, we know that Theorem 1 holds for fn0 , thus it holds for fn .

D.2

Relaxing the hypotheses on ϕ

It remains to relax the hypotheses on ϕ. This section is dedicated to the proof of the following proposition,
which is of course exactly the statement of Theorem 1.
Proposition 13. Suppose that (h1) and (h2) hold. Suppose that (h3) or (h3.a)-(h3.b)-(h3.c) hold. Then, Theorem 1
holds for the output channel (1).
To prove Proposition 13 we will approximate the function ϕ with a function ϕ̂ which is C ∞ with compact
support. In the following, G is a standard Gaussian random variable, independent of everything else.
Proposition 14. Suppose that (h1) and (h2) hold. Suppose that (h3) or (h3.a)-(h3.b)-(h3.c) hold. Then, for all
 > 0, there exist ϕ̂ ∈ C ∞ (R × RkA ) with compact support, such that
 √

√
E (ϕ( ρG, A) − ϕ̂( ρG, A))2 ≤  ,
and for n large enough, we have
" 
E

ϕ

1
√ [ΦX∗ ]1 , A1
n




− ϕ̂

1
√ [ΦX∗ ]1 , A1
n

2 #
≤ .

Proof. We will distinguish the cases where (h3) holds and where (h3.a)-(h3.b)-(h3.c) holds.
Case 1: The Gaussian case: (h3) holds.
Notice that [ΦX∗ ]1 = kX∗ kG in law. Thus, if |X1∗ | is a constant random variable, then ϕ is in L2 (R × RkA )
√
with the measure induced by ( ρG, A1 ). The result follows by density of the C ∞ functions with compact
support in L2 .
We consider now the case where |X1∗ | is not constant. We start with a useful lemma.
Lemma 8. Let f : R → R+ be a measurable function. Let G ∼ N (0, 1) and 0 < a ≤ b. Then
√

r

E[f ( aG)] ≤

√
b
E[f ( bG)].
a

√
√
In particular, if f ( bG) is integrable then f ( aG) is also integrable.
R
√
√
2
Proof. For x ∈ [a, b], notice that: xE[f ( xG)] = (2π)−1/2 e−g /(2x) f (g)dg which is clearly non-decreasing
in x.

42

|X1∗ | is not constant and ρ = E[(X1∗ )2 ], therefore there exists ρ < r < r0 such that P(r ≤ (X1∗ )2 ≤ r0 ) > 0.
Consequently, using Lemma 8,
√
√
P(r ≤ (X1∗ )2 ≤ r0 )E[ϕ( rG, A1 )2 ] = E[1r≤(X1∗ )2 ≤r0 ϕ( rG, A1 )2 ]
|X ∗ |
≤ E[1r≤(X1∗ )2 ≤r0 √1 ϕ(|X1∗ |G, A1 )2 ] ≤
r

r

r0
E[ϕ(|X1∗ |G, A1 )2 ] < ∞.
r

√
Therefore E[ϕ( rG, A1 )2 ] < ∞.
√
Let  > 0. We have just proved that ϕ ∈ L2 (R × RkA ) with the measure induced by ( rG, A1 ). There
 √

√
exists a C ∞ function with compact support ϕ̂ such that E (ϕ( rG, A) − ϕ̂( rG, A))2 ≤ . Thus by
Lemma 8
r
r


 √
√
r  √
r
√
2
2
E (ϕ( rZ, A) − ϕ̂( rZ, A)) ≤
.
E (ϕ( ρZ, A) − ϕ̂( ρZ, A)) ≤
ρ
ρ
 


2 
1
1
√
√
. By the law of large numbers, n1 kXk2
It remains to bound E ϕ
kXkG, A1 − ϕ̂
kXkG, A1
n
n
converges to ρ in probability as n → ∞. Thus P( n1 kXk2 ∈
/ [ρ/2, r]) −−−→ 0. We now apply Hölder’s
n→∞
inequality:
"


2 #
 
1
1
E 1kXk2 /n∈[ρ/2,r]
ϕ √ kXkG, A1 − ϕ̂ √ kXkG, A1
/
n
n
2
" 


2+γ # 2+γ
γ
1
1
≤ P(kXk2 /n ∈
/ [ρ/2, r]) 2+γ E ϕ √ kXkG, A1 − ϕ̂ √ kXkG, A1
n
n
γ

≤ C 2+γ ,
for some constant C > 0 and for n large enough. It remain to bound
"
E 1kXk2 /n∈[ρ/2,r] ϕ



1
√ kXkG, A1
n



 !2 #
1
− ϕ̂ √ kXkG, A1
n


r

2
√
√
nr
≤ E 1kXk2 /n∈[ρ/2,r]
ϕ rG, A1 − ϕ̂ rG, A1
kXk2
r

2 i
√
√
2r h
≤
E ϕ rG, A1 − ϕ̂ rG, A1
ρ
r
2r
.
≤
ρ


Case 2: The non-Gaussian case: (h3.a)-(h3.b)-(h3.c) hold.
In that case, by the Central Limit Theorem (using the fact that the third moments of (Xi∗ Φ1,i ) are bounded
with n, because of hypotheses (h3.a) and (h3.b))


[ΦX∗ ]1
√
(d)
√
, A1 −−−→ ( ρG, A1 ) .
(136)
n→∞
n
This implies that


ϕ

[ΦX∗ ]1
√
, A1
n



√
(d)
−−−→ ϕ( ρG, A1 ) .
n→∞

(137)

Indeed, let g : R → R be a continuous bounded function. We have, by Portemanteau Theorem, that for almost
43

all a ∈ RkA (with respect to PA )



[ΦX∗ ]1
√
√
,a
−−−→ E [g ◦ ϕ( ρG, a)] .
E g◦ϕ
n→∞
n
because for almost all a, g◦ϕ(·, a) is continuous almost-everywhere and bounded. By dominated convergence,
it follows that



[ΦX∗ ]1
√
√
E g◦ϕ
−−−→ E [g ◦ ϕ( ρG, A1 )] .
, A1
n→∞
n


∗]
√ 1 , A1 )n is by assumption (h2) bounded in L2 , thus
That finishes the proof of (137). The sequence (ϕ [ΦX
n
√
by (137) we have that E[ϕ( ρG, A1 )2 ] < ∞.
√
Let  > 0. We have just proved that ϕ ∈ L2 (R × RkA ) with the measure induced by ( ρG, A1 ). There


√
√
exists a C ∞ function with compact support ϕ̂ such that E (ϕ( ρG, A) − ϕ̂( ρG, A))2 ≤ .
One deduce from (136) and (137) that


2
 
1
1
√
√
(d)
∗
∗
−−−→ (ϕ( ρG, A) − ϕ̂( ρG, A))2 .
ϕ √ [ΦX ]1 , A1 − ϕ̂ √ [ΦX ]1 , A1
n→∞
n
n
Now, hypothesis (h2) gives that the sequence above is uniformly integrable. This gives that
 


2
1
1
√
√
E ϕ √ [ΦX∗ ]1 , A1 − ϕ̂ √ [ΦX∗ ]1 , A1
−−−→ E(ϕ( ρG, A) − ϕ̂( ρG, A))2 ≤  .
n→∞
n
n
Consequently, the left-hand side is smaller that 2 for n large enough. This concludes the proof.
In the remaining of this section, we prove Proposition 13. Let  > 0. Let ϕ and ϕ̂ as in Proposition 14. Let
fn be the free entropy associated to ϕ and fˆn the free entropy corresponding to ϕ̂.
Lemma 9. There exists a constant C > 0 such that for n large enough
√
|fn − fˆn | ≤ C  .
Proof. Consider the observation channel given by


√  1
 Yt,µ =
tϕ √n [ΦX∗ ]µ , Aµ + Zµ


√
 Ŷt,µ =
1 − tϕ̂ √1n [ΦX∗ ]µ , Aµ + Ẑµ
for 1 ≤ µ ≤ m. Let fn (t) denote the interpolating free energy:
1
fn (t) = E ln
n

Z

− 12

dPA (a)dP0 (x) e

m
P



√
Yt,µ − tϕ

µ=1

√1 [Φx]µ ,aµ
n

 2


2

√
+ Ŷt,µ − 1−tϕ̂ √1n [Φx]µ ,aµ

.

x,a
(x,a)

In order to shorten the notations, we will now write ϕµ
We compute, for 0 < t < 1:
fn0 (t)



i
m h (X∗ ,A) 2
(X∗ ,A) 2
E (ϕ̂1
) − (ϕ1
) +
=
2n
i
m h (X∗ ,A) 2
(X∗ ,A) 2
=
E (ϕ̂1
) − (ϕ1
) +
2n

(x,a)

and ϕ̂µ





for ϕ √1n [Φx]µ , aµ and ϕ̂ √1n [Φx]µ , aµ .

m
E
1 X D (x,a) (X∗ ,A)
∗ ,A)
− ϕ̂(x,a)
ϕ̂(X
E ϕµ ϕµ
µ
µ
2n
t
µ=1
D
E
m
(x,a) (X∗ ,A)
(X∗ ,A)
(x,a)
(x,a) (X∗ ,A)
E ϕ1 (ϕ1
− ϕ̂1
) + (ϕ1
− ϕ̂1 )ϕ̂1
.
2n
t

44

We start by controlling the first term:
 
h
i
  
 1/2
(X∗ ,A) 2
(X∗ ,A) 2
(X∗ ,A)
(X∗ ,A) 2
(X∗ ,A)
(X∗ ,A) 2
≤ E ϕ̂1
E (ϕ̂1
) − (ϕ1
)
+ ϕ1
E ϕ̂1
− ϕ1
√
≤ C0  ,
by Proposition 14, for some constant C0 and n large enough. The two other terms can be bounded the same
way:
D
E

(x,a) (X∗ ,A)
ϕ1 (ϕ1

−

(X∗ ,A)
ϕ̂1
)

 
  
 1/2
(X∗ ,A) 2
(X∗ ,A)
(X∗ ,A) 2
≤ E ϕ1
E ϕ̂1
− ϕ1

E
t

√
≤ C0  ,

by Proposition 14, for n large enough. Consequently, there exists a constant C > 0 such that for n large
√
enough and for all 0 < t < 1, |fn0 (t)| ≤ C . Notice that t 7→ fn (t) is continuous over [0, 1], fn (0) = fˆn
R1
√
and fn (1) = fn , hence |fn − fˆn | ≤ 0 |fn0 (t)|dt ≤ C .
Let Pout denote the transition kernel associated to ϕ and P̂out the one associated to ϕ̂. Analogously to the
previous Lemma, one can show:
Lemma 10. There exists a constant C 0 > 0 such that for all q ∈ [0, ρ]
√
|ΨPout (q) − ΨP̂out (q)| ≤ C 0  .
From there we obtain that
√
sup inf fRS (q, r) − sup inf fˆRS (q, r) ≤ C 0  .

q∈[0,ρ] r≥0

q∈[0,ρ] r≥0

(138)

Applying Theorem 1 for Pout , we obtain that for n large enough |fn − supq∈[0,ρ] inf r≥0 fRS (q, r)| ≤ . We
now combine this with (138) and Lemma 9 we obtain that for n large enough
√
√
fn − sup inf fRS (q, r) ≤ fˆn − sup inf fˆRS (q, r) + (C + C 0 )  ≤ (C + C 0 )  +  ,
q∈[0,ρ] r≥0

r≥0 q∈[0,ρ]

which concludes the proof of Proposition 13.

Appendix E: A sup-inf formula
This appendix gathers some useful lemmas for the manipulations of “sup-inf” formulas like (20). We first need
to indroduce some notations about convex functions. Let f be a convex function on some interval I ⊂ R. For
t ∈ I we will denote respectlively by f 0 (t− ) and f 0 (t+ ) the left- and right-hand derivatives of f at t. We also
define the subgradient of f at t as ∂f (t) = [f 0 (t− ), f 0 (t+ )]. If t is the right (resp. left) border of I, then we
define ∂f (t) = [f 0 (t− ), +∞) (resp. ∂f (t) = (−∞, f 0 (t+ )]).
Lemma 11. Let f and g be two convex, Lipschitz, non-decreasing functions on R+ . For q1 , q2 ∈ R+ we define
ψ(q1 , q2 ) = f (q1 ) + g(q2 ) − q1 q2 . Then
sup inf ψ(q1 , q2 ) =

q1 ≥0 q2 ≥0

sup

ψ(q1 , q2 ) =

q1 ∈∂g(q2 )
q2 =f 0 (q1+ )

45

sup
q1 ∈∂g(q2 )
q2 ∈∂f (q1 )

ψ(q1 , q2 ) ,

(139)

and these extremas are achieved at some (possibly many) couples. Moreover, if g is strictly convex, then the above
extremas are achieved precisely on the same couples (q1 , q2 ) and f is differentiable at q1 .
Corollary 5. Let f be a convex, Lipschitz, non-decreasing function on R+ . Define ρ = supx≥0 f 0 (x+ ). Let
g : [0, ρ] → R be a convex, Lipschitz, non-decreasing function. For q1 ∈ R+ and q2 ∈ [0, ρ] we define ψ(q1 , q2 ) =
f (q1 ) + g(q2 ) − q1 q2 . Then
sup

inf ψ(q1 , q2 ) = sup

inf ψ(q1 , q2 ) .

q2 ∈[0,ρ] q1 ≥0

q1 ≥0 q2 ∈[0,ρ]

Proof. In order to apply Lemma 11 we need to extend g on R+ . We thus define for x ≥ 0
g̃(x) =

(
g(x)

if x ≤ ρ

g(ρ) + (x − ρ)g 0 (ρ+ ) if x ≥ ρ

g̃ is simply equal to g that we extend for x ≥ ρ using its tangent at ρ. Obviously g̃ is a convex, Lipschitz,
non-decreasing function on R+ . One can thus apply Lemma 11:
sup inf f (q1 ) + g̃(q2 ) − q1 q2 = sup inf f (q1 ) + g̃(q2 ) − q1 q2

q1 ≥0 q2 ≥0

q2 ≥0 q1 ≥0

and both “sup-inf” are achieved on [0, supx≥0 g̃ 0 (x+ )]×[0, supx≥0 f 0 (x+ )]. By definition, ρ = supx≥0 f 0 (x+ ),
thus
sup

inf f (q1 ) + g̃(q2 ) − q1 q2 = sup inf f (q1 ) + g̃(q2 ) − q1 q2
q1 ≥0 q2 ≥0

q1 ≥0 q2 ∈[0,ρ]

= sup inf f (q1 ) + g̃(q2 ) − q1 q2 = sup
q2 ≥0 q1 ≥0

inf f (q1 ) + g̃(q2 ) − q1 q2

q2 ∈[0,ρ] q1 ≥0

which concludes the proof because g̃(q2 ) = g(q2 ) for q2 ∈ [0, ρ].
To prove Lemma 11 we will need the following lemma on the Fenchel-Legendre transform.
Lemma 12. Let V ⊂ R be a non-empty interval and let g : V → R be a convex function. Define

g ∗ : x ∈ R 7→ sup xy − g(y) ∈ R ∪ {+∞} .

(140)

y∈V

Let Dg∗ = {x ∈ R | g ∗ (x) < ∞}. Then g ∗ is a convex function on the interval Dg∗ 6= ∅. Moreover, Dg∗ = {a}
if and only if g : x 7→ ax. For all x ∈ Dg∗ the set of maximizers of (140) is of the form [ax , bx ], where
ax , bx ∈ R ∪ {±∞}. Then, the left-hand and right-hand derivatives of g ∗ at x are respectlively ax and bx .
In particular, if g is strictly convex then g ∗ is differentiable around every point in the interior of Dg∗ .
Proof. g is convex, so there exists an affine function h : x 7→ ax + b such that ∀x ∈ V, g(x) ≥ h(x). Compute


g ∗ (a) = sup ay − g(y) ≤ sup ay − h(y) = b < ∞ .
y∈V

y∈V

Thus Dg∗ 6= ∅. It is easy to verify that Dg∗ is convex. g ∗ is then convex as a supremum of linear functions.
For x ∈ R we define the function ϕx : y 7→ xy − g(y). Let x ∈ Dg∗ . Because of convexity, g ∗ is left- and
right-hand differentiable at x. We are only going to show that the left-hand derivative of g ∗ at x is equal to
ax , the result for the right-hand derivative is proved analogously.
First of all, notice that if ax = −∞ then g ∗ (x0 ) = +∞ for any x0 < x, so the left-hand derivative of g ∗ is
not defined. We will thus concentrate on the cases where ax ∈ R or ax = +∞.
46

Let us consider first the case where ax is finite. By definition, g ∗ (x) = ϕx (ax ). Let now x0 < x. We have
ax (x − x0 ) = ϕx (ax ) − ϕx0 (ax ) ≥ g ∗ (x) − g ∗ (x0 ) ,
which implies that (g ∗ )0 (x− ) ≤ ax . Let now x0 < x in Dg∗ . Notice that, by convexity of g, bx0 ≤ ax . The
fact that ax achieves the maximum in (140) implies that x ∈ ∂g(ax ). We have then, by convexity g(bx0 ) ≥
g(ax ) + (bx0 − ax )x which implies
g ∗ (x) − g ∗ (x0 ) = ax x − g(ax ) − bx0 x0 + g(bx0 )
≥ ax − g(a) − bx0 x0 + g(a) + (bx0 − ax )x
≥ bx (x − x0 ) .
When x0 → x, it is not difficult to verify that bx0 → ax . We obtain therefore that (g ∗ )0 (x− ) ≤ ax . We conclude
(g ∗ )0 (x− ) = ax .
Suppose now that ax = +∞. Let x0 < x. Notice that ax0 is finite, because the converse would imply
that g ∗ (x) = +∞. Using the result we just proved, we have ax0 = (g ∗ )0 (x0− ) ≤ (g ∗ )0 (x− ), where the last
inequality is due to convexity. When x0 → x it is again not difficult to verify that ax0 → ax = +∞. We
conclude (g ∗ )0 (x− ) = +∞.
Proof of Lemma 11. By convexity of g, for all q1 , q2 ≥ 0 such that q1 ∈ ∂g(q2 ), we have ψ(q1 , q2 ) = inf q20 ≥0 ψ(q1 , q20 ).
Consequently:
sup inf ψ(q1 , q2 ) ≥

q1 ≥0 q2 ≥0

ψ(q1 , q2 ) ≥

sup
q1 ∈∂g(q2 )
q2 ∈∂f (q1 )

sup

ψ(q1 , q2 ) .

q1 ∈∂g(q2 )
q2 =f 0 (q1+ )

Let us now prove the converse bound. Let Lg = supy≥0 g 0 (y + ). Lg is finite because g is Lipschitz. Notice
that for 0 ≤ y < Lg , g ∗ (y) < ∞ while for y > Lg , g ∗ (y) = +∞. f is continuous on [0, Lg ] and g ∗ is convex
on [0, Lg ] (g ∗ (Lg ) may be equal to +∞). Therefore f − g ∗ achieves its suppremum at some q1∗ ∈ [0, Lg ].
If 0 < q1∗ < Lg then the optimality condition at q1∗ gives f 0 (q1∗− ) − g ∗0 (q1∗− ) ≥ 0 and f 0 (q1∗+ ) − g ∗0 (q1∗+ ) ≤ 0.
Thus
(141)
g ∗0 (q1∗− ) ≤ f 0 (q1∗− ) ≤ f 0 (q1∗+ ) ≤ g ∗0 (q1∗+ ) .
We know by Lemma 12 that [g ∗0 (q1∗− ), g ∗0 (q1∗+ )] is the set of maximizers of q2 7→ q1∗ q2 − g(q2 ). Consequently
q2∗ := f 0 (q1∗+ ) maximizes q2 7→ q1∗ q2 − g(q2 ). This gives q1∗ ∈ ∂g(q2∗ ). We conclude:
sup inf ψ(q1 , q2 ) = f (q1∗ ) + g(q2∗ ) − q1∗ q2∗ ≤

q1 ≥0 q2 ≥0

sup

f (q1 ) + g(q2 ) − q1 q2 .

q1 ∈∂g(q2 )
q2 =f 0 (q1+ )

If now q1∗ = 0, the optimality condition is now: f 0 (0+ ) − g ∗0 (0+ ) ≤ 0. f is non-decreasing, hence 0 ≤
f 0 (0+ ) ≤ g ∗0 (0+ ). g is non-decreasing, thus the set of maxizers of g ∗ (0) is, by Lemma 12 [0, g ∗0 (0+ )]. Therefore q2∗ := f (0+ ) maximizes q2 7→ q1∗ q2 − g(q2 ) and we conclude similarly as before.
If q1∗ = Lg , then the optimality condition is f 0 (q1∗− ) − g ∗0 (q1∗− ) ≥ 0. Therefore f 0 (q1+ ) ≥ f 0 (q1− ) ≥ g ∗0 (q1∗− ).
Again by Lemma 12, q2∗ := f (q1∗+ ) maximizes q2 7→ q1∗ q2 − g(q2 ), we conclude similarly as before.
The equalities (139) are now proved. Moreover, we have seen in the proof above that there exists a couple
(q1∗ , q2∗ ) that achieves all three extremas.
Suppose now that g is strictly convex. This means (by Lemma 12) that g ∗ is differentiable.
47

Let (q1 , q2 ) ∈ R2+ be a couple that achieves the supremum in one of the last two sup. This means in particular that q1 ∈ ∂g(q2 ). By convexity of g we have then ψ(q1 , q2 ) = inf q20 ≥0 ψ(q1 , q20 ). Since ψ(q1 , q2 ) =
supq10 ≥0 inf q20 ≥0 ψ(q10 , q20 ), (q1 , q2 ) achieves the sup-inf.
Let (q1 , q2 ) be a couple that achieves the sup-inf. It remains to show that q1 ∈ ∂g(q2 ) and q2 = f10 (q1+ ).
First of all, the fact that ψ(q1 , q2 ) = inf q20 ≥0 ψ(q1 , q20 ) implies (by convexity) that q1 ∈ ∂g(q2 ). Now, as in the
proof above we have to distiguish whenever q1 ∈ (0, Lg ), q1 = 0 or q1 = Lg . When q1 ∈ (0, Lg ), the strict
convexity of g implies the differentiability of g ∗ , therefore the inequality (141) gives that f is differentiable
at q1 and f 0 (q1 ) = g ∗0 (q1 ) = q2 . The case q1 = 0 goes the same way. It remains to see that q1 could not be
equal to Lg . Indeed, by strict convexity, the infimum of q20 7→ ψ(Lg , q20 ) is only achieved when q20 → +∞.
∗
Lemma 12 gives then that g ∗ (L−
g ) = +∞, which gives that the function q1 7→ f (q1 ) − g (q1 ) is decreasing
on [Lg − , Lg ], for some  > 0. The supremum can therefore not be achieved at q1 = Lg .
Lemma 13. Let g be a strictly convex, differentiable, Lipschitz non-decreasing function on R+ . Define ρ =
supx≥0 g 0 (x). Let f be a convex, non-decreasing function on [0, ρ], differentiable on [0, ρ). For q1 , q2 ∈ R+ we
define ψ(q1 , q2 ) = f (q1 ) + g(q2 ) − q1 q2 . Then
sup

inf ψ(q1 , q2 ) =

q1 ∈[0,ρ] q2 ≥0

where

sup

(
Γ=

(142)

ψ(q1 , q2 ) ,

(q1 ,q2 )∈Γ

(q1 , q2 ) ∈ [0, ρ] × (R+ ∪ {+∞})

q1 = g 0 (q2 )
q2 = f 0 (q1 )

)
,

where all the function are extended by there limits at the points at which they may not be defined (for instance
g 0 (+∞) = lim g 0 (q)). Moreover, the above extremas are achieved precisely on the same couples.
q→∞

Proof. The proof goes almost exactly as for Lemma 11. The only difference with Lemma 11 and Corollary 5
above is that, without the Lipschitz assumption on f , the extremas in (142) can be achieved for (q1 , q2 ) =
(ρ, +∞) ∈ Γ, when f 0 (ρ− ) = +∞. It remains only to deal with this case, because the others can be handled
exactly as in the proof of Lemma 11.
First, suppose that q1 = ρ maximizes q1 7→ inf q2 ≥0 ψ(q1 , q2 ) over [0, ρ]. In that case, the infimum in q2 is
achieved for q2 → +∞, because by assumption q2 7→ g(q2 ) − ρq2 is strictly decreasing. Thus in that case we
still have
sup inf ψ(q1 , q2 ) = ψ(ρ, +∞) ≤ sup ψ(q1 , q2 ) .
q1 ∈[0,ρ] q2 ≥0

(q1 ,q2 )∈Γ

It remains now to show that ψ(ρ, +∞) ≤ supq1 inf q2 ψ(q1 , q2 ). Let q2 ≥ 0 and define q1 = g 0 (q2 ). By
convexity
ψ(q1 , q2 ) ≤ sup inf
ψ(q10 , q20 ) .
0
q10 ∈[0,ρ] q2 ≥0

Now notice that f (q1 ) + g(q2 ) − ρq2 ≤ ψ(q1 , q2 ) and that the left-hand side of this last inequality goes to
ψ(ρ, +∞) as q2 → ∞. This concludes the proof.

Appendix F: Concentration of free entropy and overlaps
F.1

Concentration of the free entropy

The goal of this Appendix is to prove that the free entropy of the interpolating model studied in Sec. 5.1
concentrates around its expectation. To simplify the notations we use C(ϕ, S, α), for a generic strictly positive
48

constant depending only on ϕ, S and α (S the supremum over signal values). It is also understood that n and
m are large enough and m/n → α.
Theorem 4. Under assumptions (H1), (H2) and (H3) we can find a constant C(ϕ, S, α) > 0 such that
"
2 #

C(ϕ, S, α)
1
1
≤
E
ln Zt − E
ln Zt
.
n
n
n

(143)

The remaining of this Appendix is dedicated to the proof of Theorem 4. We first recall some set-up and
notation for the convenience of the reader. The interpolating Hamiltonian (68)-(67) is (we indicate only the
annealed variables in its arguments)
−

m
X
µ=1

n

1X 0 √
(Yi − trxi )2
ln Pout (Yµ |st,µ (x, wµ )) +
2

(144)

i=1

where
r
st,µ (x, wµ ) =

1−t
[Φx]µ + k1 (t)Vµ + k2 (t)wµ ,
n

sZ

sZ

t

q(v)dv,

k1 (t) =
0

t

(ρ − q(v))dv

k2 (t) =
0

We find it convenient to use the random function representation (1) for the interpolating model, namely

q

1−t
Y = ϕ
∗ ] + k (t)V + k (t)W ∗ , A
[ΦX
+ Zµ ,
t,µ
µ
1
µ
2
µ
µ
n
√
Y 0 = rtX ∗ + Z 0
t,i

i

i

i.i.d.
In this representation the random variables (Aµ )1≤µ≤m i.i.d.
∼ PA are arbitrary, and (Zµ )1≤µ≤m ∼ N (0, 1). We
have
Z
 1
2
1
Pout (Yt,µ |st,µ (x, w)) = dPA (aµ ) √ exp − Yt,µ − ϕ(st,µ (x, wµ ), aµ
2
2π


Z
1
1
2
(145)
= dPA (aµ ) √ exp − (Γt,µ (x, wµ , aµ ) + Zµ )
2
2π

where, using the random function representation,
Γt,µ (x, wµ , aµ )
(146)
r 1 − t

r 1 − t

=ϕ
[ΦX∗ ]µ + k1 (t)Vµ + k2 (t)Wµ∗ , Aµ − ϕ
[Φx]µ + k1 (t)Vµ + k2 (t)wµ , aµ .
n
n
From (144), (145), (146) we can express the free entropy of the interpolating model as
Z
1 n
m
1
ln Zt = ln
dP0 (x)dPA (a)Dw e−Ht (x,w,a) −
ln(2π)
n
n
2n

(147)

where Dw denote the standard m-dimensional Gaussian measure and where the Hamiltonian Ht is
Ht (x, w, a) =

m

n

µ=1

i=1

√
1X
1X √
Γt,µ (x, wµ , aµ )2 +
( rtXi∗ + Zi0 − trxi )2 .
2
2

(148)

The interpretation here is that x, w, a are annealed variables and Φ, V, A, Z, Z0 , X∗ , W∗ are quenched. The
inference problem is to recover X∗ , W∗ given all other quenched variables.
49

Our goal is to show that the free energy (147) concentrates around its expectation. We will first show concentration w.r.t. all Gaussian variables Φ, V, Z, Z0 , W∗ thanks to the classical Gaussian Poincaré inequality,
then the concentration w.r.t. A and finally the one w.r.t. X∗ using classical bounded differences arguments.
The order in which we prove the concentrations matters. We recall here these two variances bounds. The
reader can refer to [20] (Chapter 3) for detailled proofs of these statements.
Proposition 15 (Gaussian Poncaré inequality). Let U = (U1 , . . . , UN ) be a vector of N independent standard
normal random variables. Let g : RN → R be a continuously differentiable function. Then
(149)



Var(g(U)) ≤ E k∇g(U)k2 .

Proposition 16. 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
u1 ,...uN ∈U N
u0i ∈U

|g(u1 , . . . , ui , . . . , uN ) − g(u1 , . . . , u0i , . . . , uN )| ≤ ci , for all 1 ≤ i ≤ N .

Let U = (U1 , . . . , UN ) be a vector of N independent random variables that takes values in U. Then
N

1X 2
Var(g(U)) ≤
ci .
4

(150)

i=1

Before we proceed it is useful to remark
m

n

µ=1

i=1

1
1
1 X 2
1 X 02 m
ln Zt = ln Ẑt −
Zµ −
ln(2π)
Zi −
n
n
2n
2n
2n

(151)

where
1
1 
ln Ẑt = ln
n
n

Z

dP0 (x)dPA (a)Dw e−Ĥt (x,w,a)



(152)

and
m

Ĥt (x, w, a) =

o
1 Xn
Γt,µ (x, wµ , aµ )2 + 2Zµ Γt,µ (x, wµ , aµ )
2
µ=1

n
o
√
√
√
1 Xn √
+
( rtXi∗ − trxi )2 + 2Zi0 ( rtXi∗ − trxi ) .
2

(153)

i=1

In order
Theorem 4 it remains to show that there exists a constant C(ϕ, S, α) > 0 such that
 to prove

C(ϕ,S,α)
1
. This concentration property together with (151) implies (143).
Var n ln Ẑt ≤
n
F.1.1

Concentration with respect to Gaussian random variables Zµ , Zi0 , Vµ , Wµ∗ , Φµi

In this section, we prove that n1 ln Ẑt is close to its expectation w.r.t. the Gaussian random variables Z, Z0 , V, W∗ , Φ.
Lemma 14. Let EG denotes the expectation w.r.t. Z, Z0 , V, W∗ , Φ only. There exists an constant C(ϕ, S, α) > 0
such that
"

2 #
1
1
C(ϕ, S, α)
E
ln Ẑt − EG
ln Ẑt
≤
.
(154)
n
n
n
50

Lemma 14 follows, by Pythagorean theorem, from Lemmas 15 and 16 below.
Lemma 15. Let EZ,Z0 denotes the expectation w.r.t. Z, Z0 only. There exists an constant C(ϕ, S, α) > 0 such
that
"

2 #
1
C(ϕ, S, α)
1
≤
E
ln Ẑt − EZ,Z0
ln Ẑt
.
(155)
n
n
n
Proof. We consider here g =
random variables. We have

1
n

ln Ẑt only as a function of Z and Z0 and work conditionnaly to all other
m
X
∂g
k∇gk =
∂Zµ
2

µ=1

2

n
X
∂g
+
∂Zi0

2

.

(156)

i=1

Each of these partial derivatives are of the form ∂g = n−1 h∂ Ĥt iĤt where the Gibbs bracket h−iĤt pertains
to the effective Hamiltonian (153). We find
∂g
= n−1 hΓt,µ iĤt ≤ 2n−1 sup |∂x ϕ|
∂Zµ
√
√
∂g
= n−1 h rtXi∗ − trxi iĤt ≤ 2n−1 S
0
∂Zi
and replacing in (156) we get k∇gk2 ≤ 2n−1 ( m
n sup |∂x ϕ| + S). Applying Proposition 15 we have
"
EZ,Z0


2 #
1
1
C(ϕ, S, α)
ln Ẑt − EZ,Z0
ln Ẑt
≤
n
n
n

(157)

almost surely. Taking the expectation in (157) gives the lemma.
Lemma 16. There exists an constant C(ϕ, S, α) > 0 such that
"



2 #
1
1
C(ϕ, S, α)
E EZ,Z0
ln Ẑt − EG
ln Ẑt
.
≤
n
n
n

(158)

Proof. We consider here g = n−1 EZ,Z0 [ln Ẑt ] as a function of V, W∗ , Φ and we work conditionnaly to the
other random variables.
hD
∂Γt,µ E i
∂g
= n−1 EZ,Z0 (Γt,µ + Zµ )
∂Vµ
∂Vµ Ht
r
h
i
2
−1
−1
)(2 sup |∂x ϕ|)
≤ n EZ,Z0 (2 sup |ϕ| + |Zµ |)(2 sup |∂x ϕ|) = n (2 sup |ϕ| +
π
The same inequality holds for

∂g
∂Wµ∗

. To compute the derivative w.r.t. Φµi we first remark

r
r 1 − t

n
∂Γt,µ
1−t ∗
=
Xi − xi ∂x ϕ
[ΦX∗ ]µ + k1 (t)Vµ + k2 (t)Wµ∗ , Aµ
∂Φµi
n
n
r
 1−t
o
− ∂x ϕ
[Φx]µ + k1 (t)Vµ + k2 (t)wµ , aµ .
n

51

Therefore
hD
∂Γt,µ E i
∂g
= n−1 EZ,Z0 (Γt,µ + Zµ )
∂Φµi
∂Φµi Ht
r
h
i
2
−3/2
−3/2
≤n
EZ,Z0 (2 sup |ϕ| + |Zµ |)(4S sup |∂x ϕ|) = n
(2 sup |ϕ| +
)(4S sup |∂x ϕ|)
π
Putting these inequalities together we find
m
m n
X
∂g 2 X X
+
∂Vµ
µ=1
µ=1
µ=1 i=1
r
m
2
≤ 2 (2 sup |ϕ| +
)(2 sup |∂x ϕ|) +
n
π

k∇gk2 =

m
X
∂g
∂Vµ

2

+

∂g
∂Φµi

2

mn
(2 sup |ϕ| +
n3

r

2
)(4S sup |∂x ϕ|) .
π

We the lemma follows again from Proposition 15.
F.1.2

Bounded difference with respect to Aµ

The next step is an application of the variance bound of Lemma 16 to show that n1 EG [ln Ẑt ] concentrates w.r.t.
A (we still keep X∗ fixed for the moment).
Lemma 17. Let EA denotes the expectation w.r.t. A only. There exists an constant C(ϕ, S, α) > 0 such that
" 


2 #
1
1
C(ϕ, S, α)
E EG
ln Ẑt − EA EG
ln Ẑt
.
(159)
≤
n
n
n
Proof. Let us consider n1 EG [ln Ẑt ] as a function g of A only. Let ν ∈ {1, . . . , m}. We must estimate variations
(ν)

(ν)

g(A) − g(A(ν) ) corresponding to two configurations A and A(ν) with Aµ = Aµ for µ 6= ν and Aν = Ãν .
(ν)
(ν)
We will use the notations Ĥt and Γt,µ to denote respectively the quantities Ĥt and Γt,µ where A is replaced
by A(ν) . By an application of Jensen’s inequality one finds
1
1
(ν)
(ν)
EG hĤt − Ĥt iĤ(ν) ≤ g(A) − g(A(ν) ) ≤ EG hĤt − Ĥt iĤt
t
n
n

(160)

where the Gibbs brackets pertain to the effective Hamiltonians (153). From (153) we obtain
(ν)

Ht

− Ht =

m
 1

1 X  (ν)2
(ν)
(ν)2
(ν)
Γt,µ − Γ2t,µ + 2Zµ (Γt,µ − Γt,µ ) =
Γt,ν − Γ2t,ν + 2Zν (Γt,ν − Γt,ν ) .
2
2
µ=1

Consequently
D
E
D
E
1
1
(ν)2
(ν)
(ν)2
(ν)
EG Γt,ν − Γ2t,ν + 2Zν (Γt,ν − Γt,ν ) (ν) ≤ g(A) − g(A(ν) ) ≤
EG Γt,ν − Γ2t,ν + 2Zν (Γt,ν − Γt,ν )
.
2n
2n
Ht
Ht
(161)
(ν)2

(ν)

Notice that Γt,ν − Γ2t,ν + 2Zν (Γt,ν − Γt,ν ) ≤ 4 sup |ϕ|2 + 4|Zν | sup |ϕ|. Thus we conclude by (161) that g
satisfies a bounded difference property:
r !
2
2
|g(A) − g(A(ν) )| ≤ sup |ϕ| sup |ϕ| + 2
.
(162)
n
π
Lemma 17 follows then by an application of Proposition 16.
52

F.1.3

Bounded difference with respect to Xi∗

∗
Let EΘ = EA EhG denotes
i the expectation w.r.t. all quenched variables except X . It remains to bound the
variance of EΘ n1 ln Ẑt (which only depends on X∗ ).

Lemma 18. There exists an constant C(ϕ, S, α) > 0 such that
" 


2 #
1
1
C(ϕ, S, α)
E EΘ
ln Ẑt − E
ln Ẑt
≤
.
n
n
n

(163)

Proof. The lemma is proved using again a bounded difference argument. n1 EΘ [ln Ẑt ] is a function of X∗
that we denote by g. We will show that g satisfies a bounded difference property. Let j ∈ {1, . . . , n}. Let
∗(j)
X∗ , X∗(j) ∈ [−S, S]n be two input signals such that Xi = Xi∗ for i 6= j.
We are going to interpolate between g(X∗ ) and g(X∗(j) ). For s ∈ [0, 1] we define
ψ(s) = g(sX∗ + (1 − s)X∗(j) )
Obviously ψ(1) = g(X∗ ) and ψ(0) = g(X∗(j) ). Using Gaussian integration by parts, it is not difficult to
verify that for s ∈ [0, 1]
C(ϕ, S, α)
|ψ 0 (s)| ≤
.
n
This implies that |g(X∗ ) − g(X∗(j) )| ≤
F.1.4

C(ϕ,S,α)
n

and using Proposition 16 we obtain the lemma.

Proof of Theorem 4




ln Ẑt ≤
From Lemmas 14, 17 and 18 above, we obtain using Pythagorean theorem that Var
some constant C(ϕ, S, α) > 0. As mentioned before, this implies (thanks to (151)) Theorem 4.

F.2

1
n

C(ϕ,S,α)
n

for

Concentration of the overlap

In this appendix we give the main steps of the proof of Lemma 2. We denote by h−in,t, the Gibbs measure
associated to the perturbed Hamiltonian
n
X

√
x2
Ht (x, w; Y, Y ) +
 i − xi Xi∗ − xi Ẑi
2
0

i=1

i.e., the sum of (68) and (76). It is crucial that the second term is a perturbation which preserves the Nishimori
identity of Appendix A.1. We note that the precise form of the first term does not matter and all subsequent
arguments are generic as long as it is a Hamiltonian whose Gibbs distribution satisfies this Nishimori identity.
The corresponding average free entropy is denoted fn, (t) and we call Fn, (t) the free entropy for a realization
of the quenched variables, that is Fn, (t) = n−1 ln Zt (Y, Y0 ).
Let
n

L :=

1 X  x2i
xi zbi 
− xi si − √ .
n
2
2 
i=1

Up to the prefactor n−1 this quantity is the derivative of the perturbation term in (76). The fluctuations of the

53

overlap Q = n−1

Pn

∗
i=1 Xi xi

E (L − EhL in,t, )2

and those of L are related through the remarkable identity
n,t,

1
= Eh(Q − EhQin,t, )2
4

n,t,

1
+ E[hQ2 in,t, − hQi2n,t, ]
2
n
1 X
+ 2
E[hXi2 in,t, − hXi i2n,t, ].
4n 
i=1

A detailed derivation can be found in Appendix IX of [13] and involves only some algebra using the Nishimori
identity and integrations by parts w.r.t. the Gaussian Ẑi in the perturbation term. Lemma 2 is then a direct
consequence of the following:
Proposition 17 (Concentration of L on E [hL i] ). Under assumptions (H1), (H2) and (H3) we have for any
0 < a < b < 1,
Z

b

d E (L − EhL in,t, )2

lim

n→+∞ a

n,t,

= 0.

(164)

The proof of this proposition is broken in two parts. Notice that
E (L − EhL in,t, )2

n,t,

= E (L − hL in,t, )2

n,t,



+ E (hL in,t, − EhL in,t, )2 .

(165)

Thus it suffices to prove the two following lemmas. The first lemma expresses concentration w.r.t. the posterior
distribution (or “thermal fluctuations”) and is an elementary consequence of concavity properties of the free
energy and the Nishimori identity.
Lemma 19 (Concentration of L on hL i ). Under assumptions (H1), (H2) and (H3), we have for any 0 < a <
b < 1,
Z
lim

n→+∞ a

b


d E (L − hL in,t, )2


n,t,

=0

(166)

The second lemma expresses the concentration of the average overlap w.r.t. the realizations of quenched
disorder variables and is a consequence of the concentration of the free energy (more precisely equation (143)
in Appendix F.1).
Lemma 20 (Concentration of hL i on EhL i ). Under assumptions (H1), (H2) and (H3), we have for any 0 <
a < b < 1,
Z
lim

n→+∞ a

b



d E (hL in,t, − E[hL in,t, ])2 = 0

(167)

The reader is referred to Sec. V of [13] for the proof of these two Lemmas. We point out that the analysis
gives a rate of decay O(n−1 ) for (166) which is optimal but a weaker decay rate for (167). However any decay
rate will suit for the present proof of the replica formula.

Acknowledgments
Jean Barbier acknowledges funding from the Swiss National Science Foundation (grant 200021-156672). Florent
Krzakala acknowledges funding from the ERC under the European Union 7th Framework Programme Grant
Agreement 307087-SPARCS. Lenka Zdeborová acknowledges funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No
714608 - SMiLe). Part of this work was done while Léo Miolane was visiting EPFL.
54

References
[1] Github repository of numerical experiments for the current paper. https://github.com/sphinxteam/
GeneralizedLinearModel2017, 2017.
[2] E. Abbe. Community detection and stochastic block models: recent developments. ArXiv e-prints arxiv
1703.10146, March 2017.
[3] Madhu Advani and Surya Ganguli. An equivalence between high dimensional bayes optimal inference
and m-estimation. In Advances in Neural Information Processing Systems, pages 3378–3386, 2016.
[4] Carlo Baldassi, Christian Borgs, Jennifer T. Chayes, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti,
and Riccardo Zecchina. Unreasonable effectiveness of learning neural networks: From accessible states
and robust ensembles to basic algorithmic schemes. Proceedings of the National Academy of Sciences,
113(48):E7655–E7662, 2016.
[5] Carlo Baldassi, Alfredo Braunstein, Nicolas Brunel, and Riccardo Zecchina. Efficient supervised learning
in networks with binary synapses. Proceedings of the National Academy of Sciences, 104(26):11079–11084,
2007.
[6] J. Barbier, M. Dia, and N. Macris. Proof of threshold saturation for spatially coupled sparse superposition
codes. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 1173–1177, July 2016.
[7] J. Barbier, F. Krzakala, L. Zdeborová, and P. Zhang. The hard-core model on random graphs revisited.
In Journal of Physics Conference Series, volume 473 of Journal of Physics Conference Series, page 012021,
December 2013.
[8] J. Barbier, N. Macris, and L. Miolane. The Layered Structure of Tensor Estimation and its Mutual Information. In 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton),
September 2017.
[9] Jean Barbier. Statistical physics and approximate message-passing algorithms for sparse linear estimation
problems in signal processing and coding theory. PhD thesis, Université Paris Diderot, 2015.
[10] Jean Barbier, Mohamad Dia, Nicolas Macris, and Florent Krzakala. The mutual information in random
linear estimation. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing
(Allerton), 2016.
[11] Jean Barbier, Mohamad Dia, Nicolas Macris, Florent Krzakala, Thibault Lesieur, and Lenka Zdeborová.
Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula. In Advances in Neural Information Processing Systems 29, page 424–432. 2016.
[12] Jean Barbier and Florent Krzakala. Approximate message-passing decoder and capacity-achieving sparse
superposition codes.
[13] Jean Barbier and Nicolas Macris. The stochastic interpolation method: A simple scheme to prove replica
formulas in bayesian inference. Arxiv preprints arxiv 1705.02780, 2017.
[14] Jean Barbier, Nicolas Macris, Mohamad Dia, and Florent Krzakala. Mutual information and optimality
of approximate message-passing in random linear estimation. arXiv preprint arXiv:1701.05823, 2017.
[15] A. R. Barron and A. Joseph. Toward fast reliable communication at rates near capacity with gaussian
noise. In 2010 IEEE International Symposium on Information Theory, pages 315–319, June 2010.
[16] Eric B Baum and Yuh-Dauh Lyuu. The transition to perfect generalization in perceptrons. Neural computation, 3(3):386–401, 1991.
55

[17] M. Bayati and A. Montanari. The lasso risk for gaussian matrices. IEEE Transactions on Information
Theory, 58(4):1997–2017, April 2012.
[18] Mohsen Bayati, Marc Lelarge, and Andrea Montanari. Universality in polytope phase transitions and
message passing algorithms. The Annals of Applied Probability, 25(2):753–822, 2015.
[19] Mohsen Bayati and Andrea Montanari. The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Transactions on Information Theory, 57(2):764–785, Feb 2011.
[20] Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Advanced
Lectures on Machine Learning, pages 208–240. Springer, 2004.
[21] Petros T Boufounos and Richard G Baraniuk. 1-bit compressive sensing. In Information Sciences and
Systems, 2008. CISS 2008. 42nd Annual Conference on, pages 16–21. IEEE, 2008.
[22] Peter Bühlmann and Sara Van De Geer. Statistics for high-dimensional data: methods, theory and applications. Springer Science & Business Media, 2011.
[23] F. Caltagirone, M. Lelarge, and L. Miolane. Recovering asymmetric communities in the stochastic block
model. ArXiv e-prints, October 2016.
[24] E. J. Candes and T. Tao. Near-optimal signal recovery from random projections: Universal encoding
strategies? IEEE Transactions on Information Theory, 52(12):5406–5425, Dec 2006.
[25] Sourav Chatterjee et al. A generalization of the lindeberg principle. The Annals of Probability, 34(6):2061–
2076, 2006.
[26] François Chollet. keras. https://github.com/fchollet/keras, 2015.
[27] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Inference and Phase Transitions in the Detection
of Modules in Sparse Networks. Physical Review Letters, 107(6):065701, August 2011.
[28] David Donoho and Andrea Montanari. High dimensional robust m-estimation: asymptotic variance via
approximate message passing. Probability Theory and Related Fields, 166(3):935–969, Dec 2016.
[29] David Donoho and Jared Tanner. Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philosophical Transactions of
the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 367(1906):4273–4293,
2009.
[30] David L. Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed
sensing. Proc. Natl. Acad. Sci., 106(45):18914–18919, 2009.
[31] David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed
sensing. Proceedings of the National Academy of Sciences, 106(45):18914–18919, Nov 2009.
[32] Viktor Dotsenko. An introduction to the theory of spin glasses and neural networks, volume 54. World
Scientific, 1995.
[33] Noureddine El Karoui, Derek Bean, Peter J. Bickel, Chinghway Lim, and Bin Yu. On robust regression
with high-dimensional predictors. Proceedings of the National Academy of Sciences, 110(36):14557–14562,
2013.
[34] Andreas Engel and Christian Van den Broeck. Statistical mechanics of learning. Cambridge University
Press, 2001.
[35] Konrad H Fischer and John A Hertz. Spin glasses, volume 1. Cambridge university press, 1993.

56

[36] Elizabeth Gardner and Bernard Derrida. Three unfinished works on the optimal storage capacity of
networks. Journal of Physics A: Mathematical and General, 22(12):1983, 1989.
[37] Tom Goldstein and Christoph Studer. Phasemax: Convex phase retrieval via basis pursuit. arXiv preprint
arXiv:1610.07531, 2016.
[38] Rémi Gribonval and Pierre Machart. Reconciling" priors" &" priors" without prejudice? In Advances in
Neural Information Processing Systems, pages 2193–2201, 2013.
[39] Francesco Guerra and Fabio Lucio Toninelli. The thermodynamic limit in mean field spin glass models.
Communications in Mathematical Physics, 230(1):71–79, 2002.
[40] Dongning Guo, S. Shamai, and S. Verdú. Mutual information and minimum mean-square error in gaussian channels. IEEE Transactions on Information Theory, 51(4):1261–1282, April 2005.
[41] Dongning Guo and Sergio Verdú. Randomly spread cdma: Asymptotics via statistical physics. IEEE
Transactions on Information Theory, 51(6):1983–2010, June 2005.
[42] Géza Györgyi. First-order transition to perfect generalization in a neural network with binary synapses.
Physical Review A, 41(12):7097, 1990.
[43] D Hansel, G Mato, and C Meunier. Memorization without generalization in a multilayered neural network. EPL (Europhysics Letters), 20(5):471, 1992.
[44] Tadaaki Hosaka, Yoshiyuki Kabashima, and Hidetoshi Nishimori. Statistical mechanics of lossy data
compression using a nonmonotonic perceptron. Physical Review E, 66(6):066126, 2002.
[45] Adel Javanmard and Andrea Montanari. State evolution for general approximate message passing algorithms, with applications to spatial coupling. Information and Inference: A Journal of the IMA, 2(2):115–
144, 2013.
[46] Y Kabashima. Inference from correlated patterns: a unified theory for perceptron learning and linear
vector channels. Journal of Physics: Conference Series, 95(1):012001, 2008.
[47] S. B. Korada and N. Macris. Tight bounds on the capacity of binary input random cdma systems. IEEE
Transactions on Information Theory, 56(11):5590–5613, Nov 2010.
[48] Satish Babu Korada and Nicolas Macris. Exact solution of the gauge symmetric p-spin glass model on a
complete graph. Journal of Statistical Physics, 136(2):205–230, 2009.
[49] Satish Babu Korada and Andrea Montanari. Applications of the Lindeberg principle in communications
and statistical learning. IEEE Transactions on Information Theory, 57(4):2440–2450, 2011.
[50] F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová. Gibbs states and the set
of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Science,
104:10318–10323, June 2007.
[51] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang. Spectral redemption in
clustering sparse networks. Proceedings of the National Academy of Science, 110:20935–20940, December
2013.
[52] Florent Krzakala, Marc Mézard, François Sausset, YF Sun, and Lenka Zdeborová. Statistical-physicsbased reconstruction in compressed sensing. Phys. Rev. X, 2:021005(18), May 2012.
[53] Florent Krzakala, Marc Mézard, Francois Sausset, Yifan Sun, and Lenka Zdeborová. Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices. Journal
of Statistical Mechanics: Theory and Experiment, 2012(08):P08009(57), 2012.
57

[54] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436–444, 2015.
[55] M. Lelarge and L. Miolane. Fundamental limits of symmetric low-rank matrix estimation. ArXiv e-prints,
November 2016.
[56] T. Lesieur, L. Miolane, M. Lelarge, F. Krzakala, and L. Zdeborová. Statistical and computational phase
transitions in spiked tensor estimation. ArXiv e-prints, January 2017.
[57] N. Macris. Griffith-Kelly-Sherman correlation inequalities: A useful tool in the theory of error correcting
codes. IEEE Transactions on Information Theory, 53(2):664–683, Feb 2007.
[58] M Mézard. The space of interactions in neural networks: Gardner’s computation with the cavity method.
Journal of Physics A: Mathematical and General, 22(12):2181–2190, 1989.
[59] Marc Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press,
2009.
[60] Marc Mézard, Giorgio Parisi, and Miguel-Angel Virasoro. Spin glass theory and beyond. 1987.
[61] Paul Milgrom and Ilya Segal. Envelope theorems for arbitrary choice sets. Econometrica, 70(2):583–601,
2002.
[62] L. Miolane. Fundamental limits of low-rank matrix estimation: the non-symmetric case. ArXiv e-prints,
February 2017.
[63] Andrea Montanari. Estimating random variables from random sparse observations. European Transactions on Telecommunications, 19(4):385–403, 2008.
[64] John Ashworth Nelder and R Jacob Baker. Generalized linear models. Wiley Online Library, 1972.
[65] Hidetoshi Nishimori. Statistical physics of spin glasses and information processing: an introduction, volume
111. Clarendon Press, 2001.
[66] Manfred Opper and David Haussler. Generalization performance of bayes optimal classification algorithm for learning a perceptron. Physical Review Letters, 66(20):2677, 1991.
[67] Samet Oymak, Amin Jalali, Maryam Fazel, Yonina C Eldar, and Babak Hassibi. Simultaneously structured
models with application to sparse and low-rank matrices. IEEE Transactions on Information Theory,
61(5):2886–2908, 2015.
[68] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer,
R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.
Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011.
[69] Francisco J Piera and Patricio Parada. On convergence properties of shannon entropy. Problems of
Information Transmission, 45(2):75–94, 2009.
[70] S. Rangan. Generalized approximate message passing for estimation with random linear mixing. In 2011
IEEE International Symposium on Information Theory Proceedings, pages 2168–2172, July 2011.
[71] G. Reeves and H. D. Pfister. The replica-symmetric prediction for compressed sensing with gaussian
matrices is exact. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 665–669,
July 2016.
[72] Tom Richardson and Ruediger Urbanke. Modern coding theory. Cambridge university press, 2008.
[73] H. S. Seung, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Phys. Rev.
A, 45:6056–6091, Apr 1992.
58

[74] Claude E Shannon. A mathematical theory of communication, part i, part ii. Bell Syst. Tech. J., 27:623–656,
1948.
[75] Mahdi Soltanolkotabi. Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization. arXiv preprint arXiv:1702.06175, 2017.
[76] Michel Talagrand. Mean field models for spin glasses: Volume I: Basic examples, volume 54. Springer
Science & Business Media, 2010.
[77] Toshiyuki Tanaka. A statistical-mechanics approach to large-system analysis of cdma multiuser detectors. IEEE Transactions on Information Theory, 48(11):2888–2910, Nov 2002.
[78] David J Thouless, Philip W Anderson, and Robert G Palmer. Solution of‘solvable model of a spin glass’.
Philosophical Magazine, 35(3):593–601, 1977.
[79] Jeremy P Vila and Philip Schniter. Expectation-maximization gaussian-mixture approximate message
passing. IEEE Transactions on Signal Processing, 61(19):4658–4672, 2013.
[80] Martin J Wainwright, Michael I Jordan, et al. Graphical models, exponential families, and variational
inference. Foundations and Trends® in Machine Learning, 1(1–2):1–305, 2008.
[81] Timothy L. H. Watkin, Albrecht Rau, and Michael Biehl. The statistical mechanics of learning a rule.
Rev. Mod. Phys., 65:499–556, Apr 1993.
[82] Yihong Wu and Sergio Verdú. Optimal phase transitions in compressed sensing. IEEE Transactions on
Information Theory, 58(10):6241–6263, Oct 2012.
[83] Yingying Xu, Yoshiyuki Kabashima, and Lenka Zdeborová. Bayesian signal reconstruction for 1-bit
compressed sensing. Journal of Statistical Mechanics: Theory and Experiment, 2014(11):P11015, 2014.
[84] Lenka Zdeborová and Florent Krzakala. Statistical physics of inference: thresholds and algorithms.
Advances in Physics, 65(5):453–552, 2016.
[85] Justin Ziniel, Philip Schniter, and Per Sederberg. Binary linear classification and feature selection via
generalized approximate message passing. In Information Sciences and Systems (CISS), 2014 48th Annual
Conference on, pages 1–6. IEEE, 2014.

59

