We obtain that

$$I(W^*; \sqrt{\lambda}f(Y^{(q)}) + Z'|V) = I(f(Y^{(q)}); \sqrt{\lambda}f(Y^{(q)}) + Z'|V) - I(f(Y^{(q)}); \sqrt{\lambda}f(Y^{(q)}) + Z'|V, W^*). \quad (129)$$

Notice that the last mutual information in the above equation does not depend on $q$ nor $r$. Therefore we have:

$$\inf_{q \in [0, \rho]} \sup_{r \ge 0} \tilde{I}_{\text{RS}}(q, r, \lambda) = -\epsilon I(f(Y^{(q)}); \sqrt{\lambda}f(Y^{(q)}) + Z'|V, W^*) + \inf_{q \in [0, \rho]} \sup_{r \ge 0} \tilde{\tilde{I}}_{\text{RS}}(q, r, \lambda). \quad (130)$$

Now, by the chain rule, we have

$$\frac{1}{n} I(\mathbf{X}^*; \mathbf{Y}, \sqrt{\lambda}\mathbf{Y}' + \mathbf{Z}'|\mathbf{\Phi}, \mathbf{\Phi}') = \frac{1}{n} I(\mathbf{X}^*; \mathbf{Y}|\mathbf{\Phi}) + \frac{1}{n} I(\mathbf{X}^*; \sqrt{\lambda}\mathbf{Y}' + \mathbf{Z}'|\mathbf{Y}, \mathbf{\Phi}, \mathbf{\Phi}'). \quad (131)$$

The limit of the left-hand side is given by (127). By Corollary 2, we have $\lim_{n \to \infty} I(\mathbf{X}^*; \mathbf{Y}|\mathbf{\Phi})/n = i_\infty$. It remains to investigate the last term of the equation above. By the arguments used to prove (129), we have

$$\begin{aligned} I(\mathbf{X}^*; \sqrt{\lambda}\mathbf{Y}' + \mathbf{Z}'|\mathbf{Y}, \mathbf{\Phi}, \mathbf{\Phi}') &= I(\mathbf{Y}'; \sqrt{\lambda}\mathbf{Y}' + \mathbf{Z}'|\mathbf{Y}, \mathbf{\Phi}, \mathbf{\Phi}') - I(\mathbf{Y}'; \sqrt{\lambda}\mathbf{Y}' + \mathbf{Z}'|\mathbf{Y}, \mathbf{\Phi}, \mathbf{X}^*, \mathbf{\Phi}') \\ &= I(\mathbf{Y}'; \sqrt{\lambda}\mathbf{Y}' + \mathbf{Z}'|\mathbf{Y}, \mathbf{\Phi}, \mathbf{\Phi}') - I(\mathbf{Y}'; \sqrt{\lambda}\mathbf{Y}' + \mathbf{Z}'|\mathbf{X}^*, \mathbf{\Phi}'). \end{aligned} \quad (132)$$

We have $I(\mathbf{Y}'; \sqrt{\lambda}\mathbf{Y}' + \mathbf{Z}'|\mathbf{X}^*, \mathbf{\Phi}')/n = \epsilon I(Y_1'; \sqrt{\lambda}Y_1' + Z_1'|\mathbf{X}^*, \mathbf{\Phi}_1')$ and it is not difficult to show, using similar computations as in the proof of Corollary 2, that

$$I(Y_1'; \sqrt{\lambda}Y_1' + Z_1'|\mathbf{X}^*, \mathbf{\Phi}_1') \xrightarrow{n \to \infty} I(f(Y^{(q)}); \sqrt{\lambda}f(Y^{(q)}) + Z'|V, W^*),$$

(recall that the right-hand side does not depend on $q$). Combining this with (132), (131), (127), Corollary 2 and (130), we obtain the desired result. $\square$

### 5.1.2 Proof of Theorem 4

In order to compute the limit of the (generalized) generalization error, we work in the teacher-student scenario with side-information discussed in the previous section.

**Lemma 3.** For all $\alpha, \lambda > 0$ the set

$$D_{\alpha, \lambda} := \{ \epsilon \ge 0 \mid \text{the infimum in (122) is achieved at a unique } q_{\alpha, \epsilon, \lambda}^* \} \quad (133)$$

is equal to $[0, +\infty)$ minus some countable set. Moreover, $\epsilon \mapsto q_{\alpha, \lambda, \epsilon}^*$ is continuous on $D_{\alpha, \epsilon}$.

*Proof.* This follows from the same arguments than the proof of Proposition 1. $\square$

**Lemma 4.** For all $\alpha, \lambda > 0$, we have for all $\epsilon \in D_{\alpha, \lambda} \setminus \{0\}$

$$\lim_{n \to \infty} \text{MMSE}(Y_1'|\mathbf{Y}, \mathbf{U}, \mathbf{\Phi}, \mathbf{\Phi}') = M_f(\lambda, q_{\alpha, \epsilon, \lambda}^*),$$

where $q_{\alpha, \epsilon, \lambda}^*$ is the unique minimizer of (122).

*Proof.* Let us fix $\alpha, \epsilon > 0$. Consider the function

$$h_{\alpha, \epsilon} : \lambda \mapsto \inf_{q \in [0, \rho]} \sup_{r \ge 0} \tilde{\tilde{I}}_{\text{RS}}(q, r, \lambda). \quad (134)$$
Corollary 4 from [93] gives that $h_{\alpha, \epsilon}$ is differentiable at $\lambda$ if and only if

$$ \left\{ \epsilon \frac{\partial}{\partial \lambda} I(f(Y^{(q)}); \sqrt{\lambda} f(Y^{(q)}) + Z'|V) = \frac{\epsilon}{2} M_f(\lambda, q) \mid q \text{ minimizer of (122) (or equivalently of (134))} \right\} $$

is a singleton (the equality comes from the I-MMSE relation from Proposition 13). In such case, Corollary 4 from [93] also gives that

$$ h'_{\alpha, \epsilon}(\lambda) = \frac{\epsilon}{2} M_f(\lambda, q), \qquad (135) $$

for all $q$ minimizer of (134). So if now $\epsilon \in D_{\alpha, \lambda} \setminus \{0\}$, then the minimizer is unique and thus $h_{\alpha, \epsilon}$ is differentiable at $\lambda$, with derivative $h'_{\alpha, \lambda}(\lambda) = \epsilon M_f(\lambda, q^*_{\alpha, \epsilon, \lambda})/2$. However, by (122) in Lemma 2, $h_{\alpha, \epsilon}$ is the pointwise limit on $\mathbb{R}_+$ of the sequence of concave functions

$$ (h_n)_{n \ge 1} = \left( \lambda \mapsto \frac{1}{n} I(\mathbf{Y}'; \sqrt{\lambda}\mathbf{Y}' + \mathbf{Z}' | \mathbf{Y}, \mathbf{\Phi}, \mathbf{\Phi}') + i_{\infty} \right)_{n \ge 1}. $$

Consequently, a standard convex analysis result gives that $h'_n(\lambda) \xrightarrow{n \to \infty} h'_{\alpha, \epsilon}(\lambda)$. By the I-MMSE relation (Proposition 13) we have $h'_n(\lambda) = \epsilon \text{MMSE}(Y'_1|\mathbf{Y}, \mathbf{U}, \mathbf{\Phi}, \mathbf{\Phi}')/2$ and we conclude using the fact that $\epsilon \neq 0$. $\square$

**Lemma 5.** For all $\alpha \in D^*$ given by (50),

$$ \lim_{\lambda \to 0} \lim_{\epsilon \to 0} M_f(\lambda, q^*_{\alpha, \epsilon, \lambda}) = \mathcal{E}_f(q^*(\alpha)). $$

*Proof.* Let $\alpha \in D^*$ and $\lambda > 0$. We have by definition of $D_{\alpha, \lambda}$, of $D^*$ and using the link between $\tilde{i}_{RS}$ and $i_{RS}$ given by (123), that $0 \in D_{\alpha, \lambda}$. By Lemma 3 above, we have

$$ q^*_{\alpha, \epsilon, \lambda} \xrightarrow{\epsilon \to 0, \epsilon \in D_{\alpha, \lambda}} q^*_{\alpha, 0, \lambda} = q^*(\alpha). $$

Analogously to Proposition 22, $M_f(\lambda, \cdot)$ is continuous on $[0, \rho]$, thus $\lim_{\epsilon \to 0} M_f(\lambda, q^*_{\alpha, \epsilon, \lambda}) = M_f(\lambda, q^*(\alpha))$. And we obtain the result by taking $\lim_{\lambda \to 0} M_f(\lambda, q^*(\alpha)) = \mathcal{E}_f(q^*(\alpha))$, using that $M_f(\cdot, q)$ is continuous for $q \in [0, \rho]$ fixed (by Proposition 13) and by comparing (125) and (61). $\square$

In order to simplify the proof, we assume that $m = \alpha n$. By definition of the generalization error (60) and of the labels $\mathbf{Y}'$ given by (119),

$$ \mathcal{E}_{f,n}(\alpha) := \text{MMSE}(Y'_1|\mathbf{Y}, \mathbf{\Phi}, \mathbf{\Phi}'). $$

**Lemma 6 (Lower bound on the generalization error).** For all $\alpha \in D^*$,

$$ \liminf_{n \to \infty} \mathcal{E}_{f,n}(\alpha) \ge \mathcal{E}_f(q^*(\alpha)). $$

*Proof.* Let $\alpha \in D^*$, $\lambda > 0$ and $\epsilon \in D_{\alpha, \lambda} \setminus \{0\}$. Obviously,

$$ \mathcal{E}_{f,n}(\alpha) \ge \text{MMSE}(Y'_1|\mathbf{Y}, \mathbf{U}, \mathbf{\Phi}, \mathbf{\Phi}') \xrightarrow{n \to \infty} M_f(\lambda, q^*_{\alpha, \epsilon, \lambda}), $$

where we used Lemma 4. Consequently $\liminf_{n \to \infty} \mathcal{E}_{f,n}(\alpha) \ge M_f(\lambda, q^*_{\alpha, \epsilon, \lambda})$ and we obtain the lower bound by letting $\epsilon, \lambda \to 0$ and using Lemma 5. $\square$

Let us now prove the converse upper bound.

**Lemma 7.** There exists a constant $C > 0$ (that only depend on $f$) such that for all $\alpha, \lambda > 0$ and all $\epsilon \in D_{\alpha, \lambda} \setminus \{0\}$

$$ \limsup_{n \to \infty} \mathcal{E}_{f,n}(\alpha + \epsilon) \le M_f(\lambda, q^*_{\alpha, \epsilon, \lambda}) + C\lambda. $$
Proof. We will let the signal-to-noise ratio (snr) of the observation of $Y'_1$ go to zero. Let us denote by $\lambda_1$ this snr: $U_1 = \sqrt{\lambda_1} Y'_1 + Z'_1$. We will let $\lambda_1$ go from $\lambda$ to 0 while the other snr for the observations of $U_\mu$ for $\mu = 2, \dots, \epsilon n$ will remain equal to $\lambda$. Recall that we denote $\mathbf{U} = (U_\mu)_{\mu=1}^{\epsilon n}$. Using Proposition 9 from [94],

$$ \left| \frac{\partial}{\partial \lambda_1} \mathrm{MMSE}(Y'_1 | \mathbf{Y}, \mathbf{U}, \mathbf{\Phi}, \mathbf{\Phi}') \right| = \mathbb{E}[\mathrm{Var}(Y'_1 | \mathbf{Y}, \mathbf{U}, \mathbf{\Phi}, \mathbf{\Phi}')^2] \le \mathbb{E}[(Y'_1)^4] \le \|f\|_{\infty}^4. $$

We define $C := \|f\|_{\infty}^4$. Consequently, by the mean value theorem,

$$ |\mathrm{MMSE}(Y'_1 | \mathbf{Y}, \mathbf{U}, \mathbf{\Phi}, \mathbf{\Phi}') - \mathrm{MMSE}(Y'_1 | \mathbf{Y}, (U_\mu)_{\mu=2}^{\epsilon n}, \mathbf{\Phi}, \mathbf{\Phi}')| \le C\lambda. \quad (136) $$

Since $(U_\mu)_{\mu=2}^{\epsilon n}$ contains less information than $(\tilde{Y}_\mu)_{\mu=2}^{\epsilon n}$ because of the additional Gaussian noise and the application of the function $f$, we have

$$ \mathrm{MMSE}(Y'_1 | \mathbf{Y}, (U_\mu)_{\mu=2}^{\epsilon n}, \mathbf{\Phi}, \mathbf{\Phi}') \ge \mathrm{MMSE}(Y'_1 | \mathbf{Y}, (\tilde{Y}_\mu)_{\mu=2}^{\epsilon n}, \mathbf{\Phi}, \mathbf{\Phi}') = \mathcal{E}_{f,n}(\alpha + \epsilon - 1/n) \ge \mathcal{E}_{f,n}(\alpha + \epsilon). \quad (137) $$

The last identity combined with (136) leads to

$$ \mathrm{MMSE}(Y'_1 | \mathbf{Y}, \mathbf{U}, \mathbf{\Phi}, \mathbf{\Phi}') + C\lambda \ge \mathcal{E}_{f,n}(\alpha + \epsilon). \quad (138) $$

By Lemma 4 we know that $\lim_{n \to \infty} \mathrm{MMSE}(Y'_1 | \mathbf{Y}, \mathbf{U}, \mathbf{\Phi}, \mathbf{\Phi}') = M_f(\lambda, q_{\alpha, \epsilon, \lambda}^*)$. Thus we conclude by taking the limsup in the inequality above. $\square$

**Corollary 6** (Upper bound on the generalization error). For all $\alpha \in D^*$,

$$ \limsup_{n \to \infty} \mathcal{E}_{f,n}(\alpha) \le \mathcal{E}_f(q^*(\alpha)). $$

Proof. Let $\alpha \in D^*$, $\lambda > 0$ and $\epsilon_1 > 0$ such that $\alpha - \epsilon_1 \in D^*$. Since by Lemma 3 the set $D_{\alpha-\epsilon_1, \lambda}$ is dense in $\mathbb{R}_+$, we can find $\epsilon_2 \in D_{\alpha-\epsilon_1, \lambda}$ such that $0 < \epsilon_2 \le \epsilon_1$. Using Lemma 7 above, we have

$$ \limsup_{n \to \infty} \mathcal{E}_{f,n}(\alpha - \epsilon_1 + \epsilon_2) \le M_f(\lambda, q_{\alpha-\epsilon_1, \epsilon_2, \lambda}^*) + C\lambda. $$

Now, using the fact that $\epsilon_2 \le \epsilon_1$ we have

$$ \limsup_{n \to \infty} \mathcal{E}_{f,n}(\alpha) \le \limsup_{n \to \infty} \mathcal{E}_{f,n}(\alpha - \epsilon_1 + \epsilon_2) \le M_f(\lambda, q_{\alpha-\epsilon_1, \epsilon_2, \lambda}^*) + C\lambda. $$

Now, by Lemma 5 we have

$$ \lim_{\lambda \to 0} \lim_{\epsilon_2 \to 0} M_f(\lambda, q_{\alpha-\epsilon_1, \epsilon_2, \lambda}^*) + C\lambda = \mathcal{E}_f(q^*(\alpha - \epsilon_1)) $$

which leads to $\limsup_{n \to \infty} \mathcal{E}_{f,n}(\alpha) \le \mathcal{E}_f(q^*(\alpha - \epsilon_1))$. We conclude by letting $\epsilon_1 \to 0$ (recall that by Proposition 1 $D^*$ is dense in $\mathbb{R}_+$ so it is possible to find $\epsilon_1 > 0$ arbitrary small such that $\alpha - \epsilon_1 \in D^*$), using the continuity of $\mathcal{E}_f$ (by Proposition 22) and the continuity of $q^*$ (by Proposition 1). $\square$

**Proof of Theorem 4:** For the moment we have proven Theorem 4 when $f$ is continuous and bounded. We are going to relax this assumption by approximation. Let $f: \mathbb{R} \to \mathbb{R}$ such that $\mathbb{E}[|f(Y_{\mathrm{new}})|^{2+\gamma}]$ remains bounded as $n$ goes to infinity, for some $\gamma > 0$. Let $\epsilon > 0$. By density of the continuous and bounded functions in the space $L^2(\mathbb{R})$ equipped with the law of $Y^{(q)} \sim P_{\mathrm{out}}(\cdot | \sqrt{q}V + \sqrt{\rho-q}W)$ ($V, W \stackrel{\mathrm{iid}}{\sim} \mathcal{N}(0, 1)$), we can find a continuous bounded function $\tilde{f}: \mathbb{R} \to \mathbb{R}$ such that $\mathbb{E}[(f(Y^{(q)}) - \tilde{f}(Y^{(q)}))^2] \le \epsilon$.
**Lemma 8.** For all $q \in [0, \rho]$ (because the law of $Y^{(q)}$ does not depend on $q$), we have

$$f(Y_{\text{new}}) - \tilde{f}(Y_{\text{new}}) \xrightarrow[n \to \infty]{(d)} f(Y^{(q)}) - \tilde{f}(Y^{(q)}). \quad (139)$$

*Proof.* Let $(\mathbf{A}_{\text{new}}, Z_{\text{new}}) \sim P_A \otimes \mathcal{N}(0, 1)$ such that $Y_{\text{new}} = \varphi(\mathbf{\Phi}_{\text{new}} \cdot \mathbf{X}^*/\sqrt{n}, \mathbf{A}_{\text{new}}) + \sqrt{\Delta}Z_{\text{new}}$. By the central limit theorem (that we apply under (h1)-(h3) and using (h4))

$$\varphi\left(\frac{\mathbf{\Phi}_{\text{new}} \cdot \mathbf{X}^*}{\sqrt{n}}, \mathbf{A}_{\text{new}}\right) \xrightarrow[n \to \infty]{(d)} \varphi(\sqrt{\rho}Z, \mathbf{A}_{\text{new}}), \quad (140)$$

where $Z \sim \mathcal{N}(0, 1)$ is independent from $\mathbf{A}_{\text{new}}$. Under (h5.b) this proves Lemma 8, because in that case $Y_{\text{new}} = \varphi(\mathbf{\Phi}_{\text{new}} \cdot \mathbf{X}^*/\sqrt{n}, \mathbf{A}_{\text{new}})$ takes values in $\mathbb{N}$. Under (h5.a) we let $g: \mathbb{R} \to \mathbb{R}$ be a continuous bounded function and we write $h := f - \tilde{f}$. Then

$$\begin{aligned} \mathbb{E}[g \circ h(Y_{\text{new}})] &= \mathbb{E}\left[g \circ h\left(\varphi\left(\frac{\mathbf{\Phi}_{\text{new}} \cdot \mathbf{X}^*}{\sqrt{n}}, \mathbf{A}_{\text{new}}\right) + \sqrt{\Delta}Z_{\text{new}}\right)\right] \\ &= \mathbb{E}\left[\frac{1}{\sqrt{2\pi\Delta}} \int g \circ h(z) \exp\left\{-\frac{1}{2\Delta}\left(z - \varphi\left(\frac{\mathbf{\Phi}_{\text{new}} \cdot \mathbf{X}^*}{\sqrt{n}}, \mathbf{A}_{\text{new}}\right)\right)^2\right\} dz\right]. \end{aligned}$$

The function $x \mapsto \int g \circ h(z) \frac{e^{-\frac{1}{2\Delta}(z-x)^2}}{\sqrt{2\pi\Delta}} dz$ is continuous and bounded: (140) then gives that

$$\mathbb{E}[g \circ h(Y_{\text{new}})] \xrightarrow[n \to \infty]{\sim} \mathbb{E}\left[\frac{1}{\sqrt{2\pi\Delta}} \int g \circ h(z) \exp\left\{-\frac{1}{2\Delta}\left(z - \varphi(\sqrt{\rho}Z, \mathbf{A}_{\text{new}})\right)^2\right\} dz\right] = \mathbb{E}[g \circ h(Y^{(q)})],$$

which concludes the proof by the Portemanteau Theorem. $\square$

The sequence $((f(Y_{\text{new}}) - \tilde{f}(Y_{\text{new}}))^2)_{n \ge 0}$ is uniformly integrable because bounded in $L^{1+\gamma}$ with $\gamma > 0$. Consequently, Lemma 8 above implies

$$\mathbb{E}\left[(f(Y_{\text{new}}) - \tilde{f}(Y_{\text{new}}))^2\right] \xrightarrow[n \to \infty]{\sim} \|f(Y^{(q)}) - \tilde{f}(Y^{(q)})\|_{L^2}^2 = \mathbb{E}\left[(f(Y^{(q)}) - \tilde{f}(Y^{(q)}))^2\right] \le \epsilon.$$

Therefore, we can find $n_0 \in \mathbb{N}$ such that for all $n \ge n_0$, $\|f(Y_{\text{new}}) - \tilde{f}(Y_{\text{new}})\|_{L^2}^2 = \mathbb{E}[(f(Y_{\text{new}}) - \tilde{f}(Y_{\text{new}}))^2] \le 2\epsilon$. If we now apply Theorem 4 for $\tilde{f}$, we can find $n_1 \ge n_0$ such that for all $n \ge n_1$, $|\mathcal{E}_{\tilde{f},n}^{1/2} - \mathcal{E}_{\tilde{f}}(q^*(\alpha))^{1/2}| \le \sqrt{\epsilon}$. Let $n \ge 1$, and compute

$$\begin{aligned} |\mathcal{E}_{f,n}^{1/2} - \mathcal{E}_{\tilde{f},n}^{1/2}| &= \|f(Y_{\text{new}}) - \mathbb{E}[f(Y_{\text{new}})|\mathbf{Y}, \mathbf{\Phi}, \mathbf{\Phi}_{\text{new}}]\|_{L^2} - \|\tilde{f}(Y_{\text{new}}) - \mathbb{E}[\tilde{f}(Y_{\text{new}})|\mathbf{Y}, \mathbf{\Phi}, \mathbf{\Phi}_{\text{new}}]\|_{L^2} \\ &\le \|f(Y_{\text{new}}) - \tilde{f}(Y_{\text{new}})\|_{L^2} + \|\mathbb{E}[f(Y_{\text{new}}) - \tilde{f}(Y_{\text{new}})|\mathbf{Y}, \mathbf{\Phi}, \mathbf{\Phi}_{\text{new}}]\|_{L^2} \\ &\le 2\|f(Y_{\text{new}}) - \tilde{f}(Y_{\text{new}})\|_{L^2} \le 2\sqrt{2\epsilon}, \end{aligned}$$

where we successively used the triangular inequality twice for the first inequality ($|a - b| - |x - y| \le |a - x + y - b| \le |a - x| + |y - b|$) and Jensen's inequality for the second. By the same arguments we have also $|\mathcal{E}_f(q)^{1/2} - \mathcal{E}_{\tilde{f}}(q)^{1/2}| \le 2\sqrt{\epsilon}$ for all $q \in [0, \rho]$. We conclude that for all $n \ge n_1$,

$$\begin{aligned} |\mathcal{E}_{f,n}^{1/2} - \mathcal{E}_f(q^*(\alpha))^{1/2}| &\le |\mathcal{E}_{f,n}^{1/2} - \mathcal{E}_{\tilde{f},n}^{1/2}| + |\mathcal{E}_{\tilde{f}}(q^*(\alpha))^{1/2} - \mathcal{E}_f(q^*(\alpha))^{1/2}| + |\mathcal{E}_{\tilde{f},n}^{1/2} - \mathcal{E}_{\tilde{f}}(q^*(\alpha))^{1/2}| \\ &\le (2\sqrt{2} + 3)\sqrt{\epsilon}, \end{aligned} \quad (141)$$

which proves Theorem 4. $\square$
## 5.2 Generalization error of GAMP: Proof of Proposition 2

Let us decompose:

$$ \mathcal{E}_{\text{gen}}^{\text{GAMP},t} := \mathbb{E}[(Y_{\text{new}} - \hat{Y}^{\text{GAMP},t})^2] = \mathbb{E}[Y_{\text{new}}^2] + \mathbb{E}[(\hat{Y}^{\text{GAMP},t})^2] - 2\mathbb{E}[Y_{\text{new}}\hat{Y}^{\text{GAMP},t}]. \quad (142) $$

**Lemma 9.** We have

$$ \mathbb{E}[Y_{\text{new}} \hat{Y}^{\text{GAMP},t}] \xrightarrow{n \to \infty} \mathbb{E}_W \left[ \mathbb{E}_W \left[ \int dY Y P_{\text{out}}(Y | \sqrt{q^t} V + \sqrt{\rho - q^t} W)^2 \right] \right]. \quad (143) $$

*Proof.* Start by writing

$$ \mathbb{E}[Y_{\text{new}} \hat{Y}^{\text{GAMP},t}] = \mathbb{E} \int y y' P_{\text{out}} \left( y \left| \frac{\mathbf{\Phi}_{\text{new}} \cdot \mathbf{X}^*}{\sqrt{n}} \right. \right) P_{\text{out}} \left( y' \left| \frac{\mathbf{\Phi}_{\text{new}} \cdot \hat{\mathbf{x}}^t}{\sqrt{n}} + \sqrt{\rho - q^t} W \right. \right) dy dy' $$

where $W \sim \mathcal{N}(0, 1)$ is independent of everything else. $\mathbf{\Phi}_{\text{new}} \sim \mathcal{N}(0, I_n)$ is independent of $\mathbf{X}^*$ and $\hat{\mathbf{x}}^t$, so, conditionally on $\mathbf{X}^*, \hat{\mathbf{x}}^t$ we have

$$ \left( \frac{\mathbf{\Phi}_{\text{new}} \cdot \mathbf{X}^*}{\sqrt{n}}, \frac{\mathbf{\Phi}_{\text{new}} \cdot \hat{\mathbf{x}}^t}{\sqrt{n}} \right) \sim \mathcal{N} \left( 0, \frac{1}{n} \left( \frac{\|\mathbf{X}^*\|^2}{\hat{\mathbf{x}}^t \cdot \mathbf{X}^*} \frac{\hat{\mathbf{x}}^t \cdot \mathbf{X}^*}{\|\hat{\mathbf{x}}^t\|^2} \right) \right). $$

We assumed that (69) holds, i.e. $\mathbf{X}^* \cdot \hat{\mathbf{x}}^t / n \to q^t$ and $\|\hat{\mathbf{x}}^t\|^2 / n \to q^t$, in probability. By the law of large numbers $\|\mathbf{X}^*\|^2 / n \to \rho$ in probability. Consequently,

$$ \left( \frac{\mathbf{\Phi}_{\text{new}} \cdot \mathbf{X}^*}{\sqrt{n}}, \frac{\mathbf{\Phi}_{\text{new}} \cdot \hat{\mathbf{x}}^t}{\sqrt{n}} \right) \xrightarrow{n \to \infty} \mathcal{N} \left( 0, \left( \begin{pmatrix} \rho & q^t \\ q^t & q^t \end{pmatrix} \right) \right). $$

Since $x \mapsto P_{\text{out}}(\cdot|x)$ is continuous almost everywhere for the Wasserstein distance of order 2, the function $h: (a, b) \mapsto \mathbb{E}_W \int yy' P_{\text{out}}(y|a)P_{\text{out}}(y'|b + \sqrt{\rho - q^t} W)dydy'$ with $W \sim \mathcal{N}(0, 1)$ is continuous almost everywhere. Therefore

$$ H_n := h \left( \frac{\mathbf{\Phi}_{\text{new}} \cdot \mathbf{X}^*}{\sqrt{n}}, \frac{\mathbf{\Phi}_{\text{new}} \cdot \hat{\mathbf{x}}^t}{\sqrt{n}} \right) \xrightarrow{n \to \infty} h \left( \sqrt{q^t} Z_0 + \sqrt{\rho - q^t} Z_1, \sqrt{q^t} Z_0 \right), \quad (144) $$

where $Z_0, Z_1 \stackrel{\text{iid}}{\sim} \mathcal{N}(0, 1)$. We have by Jensen's inequality

$$ \begin{aligned} \mathbb{E}[|H_n|^{1+\eta}] &\le \mathbb{E}[|Y_{\text{new}} \hat{Y}^{\text{GAMP},t}|^{1+\eta}] \\ &\le \mathbb{E} \left[ \left( \frac{1}{2} Y_{\text{new}}^2 + \frac{1}{2} (\hat{Y}^{\text{GAMP},t})^2 \right)^{1+\eta} \right] \\ &\le \frac{1}{2} \mathbb{E} |Y_1|^{2+2\eta} + \frac{1}{2} \mathbb{E} |\hat{Y}^{\text{GAMP},t}|^{2+2\eta}. \end{aligned} $$

By assumption, there exists $\eta > 0$ such that the two last terms above remain bounded with $n$: $H_n$ is therefore bounded in $L^{1+\eta}$ and is therefore uniformly integrable. From (144) we thus get

$$ \begin{aligned} \mathbb{E}[Y_{\text{new}} \hat{Y}^{\text{GAMP},t}] &= \mathbb{E}[H_n] \xrightarrow{n \to \infty} \mathbb{E}[h(\sqrt{q^t} Z_0 + \sqrt{\rho - q^t} Z_1, \sqrt{q^t} Z_0)] \\ &= \mathbb{E}_V \left[ \mathbb{E}_W \left[ \int dY Y P_{\text{out}}(Y | \sqrt{q^t} V + \sqrt{\rho - q^t} W)^2 \right] \right]. \end{aligned} $$

□
Following the arguments of Lemma 9 one can also show that

$$
\begin{align*}
\mathbb{E}[(\hat{Y}^{\text{GAMP},t})^2] &\xrightarrow[n \to \infty]{} \mathbb{E}_V[\mathbb{E}_W[\int dY Y P_{\text{out}}(Y|\sqrt{q^t}V + \sqrt{\rho-q^t}W)^2]], \\
\mathbb{E}[Y_{\text{new}}^2] &\xrightarrow[n \to \infty]{} \mathbb{E}_V \int dY Y^2 P_{\text{out}}(Y|\sqrt{\rho}V).
\end{align*}
$$

This proves (together with (142) and Lemma 9) Proposition 2.

5.3 Limit of the overlap: Proof of Theorem 2

Recall the definition of the overlap (105): $Q_n := \mathbf{X}^* \cdot \mathbf{x}/n$, where $\mathbf{x} = (x_1, \dots, x_n)$ is a sample from the posterior distribution $P(\mathbf{X}^*|\mathbf{Y}, \mathbf{\Phi})$, independently of everything else. In this section we will show that $|Q_n|$ converges in probability to $q^*(\alpha)$, when $\alpha \in D^*$ given by (50). We will first show an upper-bound in Sec. 5.3.1 below, before proving the converse lower-bound in Sec. 5.3.2.

5.3.1 Upper bound on the overlap

**Proposition 9 (Upper bound on the overlap).** For all $\alpha \in D^*$ and for all $\epsilon > 0$,

$$
\mathbb{P}(|Q_n| \geq q^*(\alpha) + \epsilon) \xrightarrow{n \to \infty} 0.
$$

Let us fix $\alpha \in D^*$ and let $p \ge 1$. In order to obtain an upper bound on the overlap, we consider an
observation model with some (small) extra information (that takes the form of a tensor of order $2p$) in addition
of the original model (21), i.e. we observe

$$
\left\{
\begin{array}{l}
\mathbf{Y} \sim P_{\text{out}}(\cdot | \mathbf{\Phi} \mathbf{X}^* / \sqrt{n}), \\
\mathbf{Y}' = \sqrt{\frac{\lambda}{n^{2p-1}}} (\mathbf{X}^*)^{\otimes 2p} + \mathbf{Z}',
\end{array}
\right.
\qquad (145)
$$

where $\lambda \ge 0$, $\mathbf{Z}' = (Z'_{i_1 \dots i_{2p}})_{1 \le i_1 < \dots < i_{2p} \le n} \stackrel{\text{id}}{\approx} \mathcal{N}(0, 1)$ and $(\mathbf{X}^*)^{\otimes 2p} = (X_{i_1} \dots X_{i_{2p}})_{1 \le i_1 < \dots < i_{2p} \le n}$. In order to
prove Proposition 9 we need the two results below, which are proven after the proof of Proposition 9.

**Proposition 10 (Mutual information of the perturbed model).** For all $\lambda \ge 0$, the mutual information for model (145) verifies

$$
\lim_{n \to \infty} \frac{1}{n} I(\mathbf{X}^*; \mathbf{Y}, \mathbf{Y}' | \mathbf{\Phi}) = I(\lambda), \qquad (146)
$$

where the right-hand-side is

$$
I(\lambda) := \inf_{q \in [0, \rho]} \sup_{r \ge 0} \left\{ I_{P_0}(r + 2p\lambda q^{2p-1}) + \alpha I_{P_{\text{out}}}(q) - \frac{r}{2}(\rho - q) + \frac{2p-1}{2}\lambda q^{2p} - \rho p \lambda q^{2p-1} + \frac{\lambda}{2}\rho^{2p} \right\}. \quad (147)
$$

**Lemma 10.** The function *I* defined above by (147) is concave on *R*+. Its left- and right-derivatives are given by

$$
I'(\lambda^+) = \min \left\{ \frac{1}{2} (\rho^{2p} - q_*(\lambda)^{2p}) \middle| q_*(\lambda) \text{ achieves the infimum in (147)} \right\},
$$

$$
I'(\lambda^-) = \max \left\{ \frac{1}{2} (\rho^{2p} - q_*(\lambda)^{2p}) \middle| q_*(\lambda) \text{ achieves the infimum in (147)} \right\}.
$$

We are now in position to prove Proposition 9.
Proof of Proposition 9: By the I-MMSE relation of Proposition 13,

$$ \frac{1}{n} \frac{\partial}{\partial \lambda} I(\mathbf{X}^*; \mathbf{Y}, \mathbf{Y}' | \mathbf{\Phi}) = \frac{1}{n} \frac{\partial}{\partial \lambda} I((\mathbf{X}^*)^{\otimes 2p}; \mathbf{Y}, \mathbf{Y}' | \mathbf{\Phi}) = \frac{1}{2n^{2p}} \text{MMSE}((\mathbf{X}^*)^{\otimes 2p} | \mathbf{Y}, \mathbf{Y}', \mathbf{\Phi}). $$

Using Proposition 10 and Lemma 10 above we obtain by concavity that

$$ \frac{1}{2n^{2p}} \text{MMSE}((\mathbf{X}^*)^{\otimes 2p} | \mathbf{Y}, \mathbf{Y}', \mathbf{\Phi}) = \frac{1}{n} \frac{\partial}{\partial \lambda} I(\mathbf{X}^*; \mathbf{Y}, \mathbf{Y}' | \mathbf{\Phi}) \underset{n \to \infty}{\longrightarrow} I'(\lambda) = \frac{1}{2}(\rho^{2p} - q_*(\lambda)^{2p}), $$

for all $\lambda > 0$ for which the infimum of (147) is achieved at a unique $q_*(\lambda)$. Consequently,

$$ \liminf_{n \to \infty} \frac{1}{n^{2p}} \text{MMSE}((\mathbf{X}^*)^{\otimes 2p} | \mathbf{Y}, \mathbf{\Phi}) \geq \liminf_{n \to \infty} \frac{1}{n^{2p}} \text{MMSE}((\mathbf{X}^*)^{\otimes 2p} | \mathbf{Y}, \mathbf{Y}', \mathbf{\Phi}) = \rho^{2p} - q_*(\lambda)^{2p}. \quad (148) $$

Let us now suppose that $\alpha \in D^*$. In that case, there exists a unique $q_*(\lambda = 0) = q^*(\alpha)$ that achieves the infimum in (147). Consequently, $I'(0^+) = \frac{1}{2}(\rho^{2p} - q^*(\alpha)^{2p})$. By concavity, $I'(\lambda) \to I'(0^+)$ as $\lambda \to 0$, which gives $q_*(\lambda) \to q^*(\alpha)$. By taking the $\lambda \to 0$ limit in (148) above we get

$$ \liminf_{n \to \infty} \frac{1}{n^{2p}} \text{MMSE}((\mathbf{X}^*)^{\otimes 2p} | \mathbf{Y}, \mathbf{\Phi}) \geq \rho^{2p} - q^*(\alpha)^{2p}. $$

One verifies easily that

$$ \frac{1}{n^{2p}} \text{MMSE}((\mathbf{X}^*)^{\otimes 2p} | \mathbf{Y}, \mathbf{\Phi}) = \rho^{2p} - \mathbb{E}[Q_n^{2p}] + o_n(1), \quad (149) $$

so we deduce that

$$ \limsup_{n \to \infty} \mathbb{E}[Q_n^{2p}] \leq q^*(\alpha)^{2p}. $$

Let $\epsilon > 0$. By Markov's inequality we have

$$ \mathbb{P}(|Q_n| \geq q_*(\alpha) + \epsilon) \leq \frac{\mathbb{E}[Q_n^{2p}]}{(q_*(\alpha) + \epsilon)^{2p}}. $$

By taking the $\limsup$ in $n$ on both sides we obtain

$$ \limsup_{n \to \infty} \mathbb{P}(|Q_n| \geq q_*(\alpha) + \epsilon) \leq \frac{q^*(\alpha)^{2p}}{(q_*(\alpha) + \epsilon)^{2p}}, $$

and Proposition 9 follows by taking the $p \to \infty$ limit in the inequality above. $\square$

We now prove the two preliminary results used in the proof of Proposition 9.

Proof of Proposition 10: The proof is very similar to the one of Theorem 1 (and Corollary 2), by the adaptive interpolation method (see Sec. 4), so we provide only the main arguments and omit to write the small perturbation (i.e. the $\epsilon_1, \epsilon_2$ present in Sec. 4) for simplicity.

In order to tackle model (145) we need first to study a simpler one, namely when we have access to the simultaneous observations $\mathbf{Y} \sim P_{\text{out}}(\cdot | \mathbf{\Phi}\mathbf{X}^*/\sqrt{n})$ and $\mathbf{Y}'' = \sqrt{\gamma}\mathbf{X}^* + \mathbf{Z}''$. Define, for $\gamma \geq 0$, the free entropy (expected log-partition function) of this model:

$$ F_n(\gamma) := \frac{1}{n} \mathbb{E} \ln \int dP_0(\mathbf{x}) \exp \left( \sum_{i=1}^{n} \sqrt{\gamma} Z_i'' x_i + \gamma x_i X_i^* - \frac{\gamma}{2} x_i^2 \right) \prod_{\mu=1}^{m} P_{\text{out}} \left( Y_{\mu} \middle| \frac{1}{\sqrt{n}} \mathbf{\Phi}_{\mu} \cdot \mathbf{x} \right), \quad (150) $$
where $Z_i'' \stackrel{\text{iid}}{\sim} \mathcal{N}(0, 1)$ are independent of everything else. Let us define

$$F_{\text{RS}}(\gamma) := \sup_{q \in [0, \rho]} \inf_{r \ge 0} \left\{ \psi_{P_0}(r + \gamma) + \alpha \Psi_{P_{\text{out}}}(q) - \frac{rq}{2} \right\}. \quad (151)$$

A slight and easy modification of the Theorem 1 gives that for all $\gamma \ge 0$

$$F_n(\gamma) \xrightarrow{n \to \infty} F_{\text{RS}}(\gamma). \quad (152)$$

$F_n$ is a convex function of $\gamma$ (this can be checked by relating it to the mutual information like in Corollary 2 and then using the I-MMSE relation of Proposition 13), thus $F_{\text{RS}}$ is too. The function $F_{\text{RS}}$ is therefore continuous on $\mathbb{R}_+$. $F_n$ is also a non-decreasing function of $\gamma$ (this is again checked using the I-MMSE relation). By Dini's second theorem we obtain that the convergence of (152) is uniform over all compact subsets of $\mathbb{R}_+$.

Now that we have studied this simpler model, we come back to the analysis of (145). We proceed by interpolation as in Sec. 4.1. Let $q: [0, 1] \to [0, \rho]$ be a continuous interpolating function. For $t \in [0, 1]$, consider the following “interpolating estimation model”:

$$\left\{
\begin{array}{ll}
Y_{\mu} & \sim P_{\text{out}}(\cdot | \mathbf{\Phi} \mathbf{X}^*/\sqrt{n}), & 1 \le \mu \le m, \\
\mathbf{Y}'_t & = \sqrt{\frac{\lambda(1-t)}{n^{2p-1}} (\mathbf{X}^*)^{\otimes 2p} + \mathbf{Z}'}, & \\
Y''_{t,i} & = \sqrt{2p\lambda \int_0^t q(v)^{2p-1} dv} X_i^* + Z_i'', & 1 \le i \le n.
\end{array}
\right.
\quad (153)$$

Define the corresponding interpolating free entropy:

$$f_n(t) := \frac{1}{n} \mathbb{E} \ln \int dP_0(\mathbf{x}) e^{H_{n,t}(\mathbf{x})} \prod_{\mu=1}^{m} P_{\text{out}} \left( Y_{\mu} \middle| \frac{1}{\sqrt{n}} \mathbf{\Phi}_{\mu} \cdot \mathbf{x} \right),$$

where the Hamiltonian of the model is

$$H_{n,t}(\mathbf{x}) = \sum_{i=1}^{n} \left\{ \begin{aligned} & \sqrt{2p\lambda \int_{0}^{t} q(v)^{2p-1} dv} Z_{i}'' x_{i} + 2p\lambda \int_{0}^{t} q(v)^{2p-1} dv x_{i} X_{i}^{*} - p\lambda \int_{0}^{t} q(v)^{2p-1} dv x_{i}^{2} \\ & + \sum_{i_{1}, \dots, i_{2p}} \left\{ \begin{aligned} & \sqrt{\frac{\lambda(1-t)}{n^{2p-1}}} Z'_{i_{1} \dots i_{2p}} x_{i_{1}} \dots x_{i_{2p}} + \frac{\lambda(1-t)}{n^{2p-1}} x_{i_{1}} \dots x_{i_{2p}} X_{i_{1}}^{*} \dots X_{i_{2p}}^{*} \\ & - \frac{\lambda(1-t)}{2n^{2p-1}} x_{i_{1}}^{2} \dots x_{i_{2p}}^{2} \end{aligned} \right\} \end{aligned} \right\}$$

We aim at computing $f_n := f_n(0)$. We have $f_n(1) = F_n(2p\lambda \int_0^1 q(t)^{2p-1} dt)$. Similarly to Proposition 3 one can compute (see [52] where this computation is done):

$$f'_{n}(t) = -\frac{\lambda}{2} \mathbb{E} \langle Q_{t}^{2p} - 2pq(t)^{2p-1} Q_{t} \rangle_{t} \quad (154)$$

where $Q_t = \sum_{i=1}^n X_i^* x_i / n$ is the overlap between the planted solution $\mathbf{X}^*$ and $\mathbf{x} = (x_1, \dots, x_n)$, a sample from the posterior distribution $P(\mathbf{X}^* | \mathbf{Y}, \mathbf{Y}'_t, \mathbf{Y}''_t)$. Similarly as in Sec. 4.1 the Gibbs bracket $\langle - \rangle_t$ denotes the expectation w.r.t. this $t$-dependent posterior acting on $\mathbf{x}$, $\mathbb{E}$ is w.r.t. the quenched variables $\mathbf{Y}, \mathbf{Y}'_t, \mathbf{Y}''_t$. By convexity of the function $x \mapsto x^{2p}$, we have for all $a, b \in \mathbb{R}$, $a^{2p} - 2pab^{2p-1} \ge (1-2p)b^{2p}$. Consequently, if we choose $q$ to be a constant function, i.e. $q(t) = q$ for all $t \in [0, 1]$, we have

$$f'_{n}(t) \le \frac{\lambda}{2}(2p-1)q^{2p}.$$
This gives

$$f_n = f_n(0) = f_n(1) - \int_0^1 f'_n(t) dt \geq F_n(2p\lambda q^{2p-1}) - \frac{\lambda}{2}(2p-1)q^{2p}.$$

By taking the lim inf in $n$ on both sides, we obtain $\liminf_{n \to \infty} f_n \geq F_{RS}(2p\lambda q^{2p-1}) - \frac{\lambda}{2}(2p-1)q^{2p}$ using (152) and since this holds for all $q \in [0, \rho]$ we get

$$\liminf_{n \to \infty} f_n \geq \sup_{q \in [0, \rho]} \left\{ F_{RS}(2p\lambda q^{2p-1}) - \frac{\lambda}{2}(2p-1)q^{2p} \right\}.$$

Let us now prove the converse upper-bound. One can show as in Sec. 4.3 that the overlap $Q_t$ concentrates around its expectation: Proposition 4 applies. This perturbation does not change the free entropy in the limit $n \to \infty$ nor the following derivation, so we do not track it explicitely for the sake of simplicity. Let us go back to (154). Therefore, using this concentration and then choosing $q(t) = \tilde{q}(t) = \mathbb{E}\langle Q_t \rangle_t$ as done in Sec. 4.4, we obtain that

$$f'_n(t) = \frac{\lambda}{2}(2p-1)\tilde{q}(t)^{2p} + o_n(1).$$

Consequently,

$$\begin{align*}
f_n &= f_n(1) - \int_0^1 f'_n(t) dt = F_n\left(2p\lambda \int_0^1 \tilde{q}(t)^{2p-1} dt\right) - \frac{\lambda}{2}(2p-1) \int_0^1 \tilde{q}(t)^{2p} dt + o_n(1) \\
&\leq F_n\left(2p\lambda \int_0^1 \tilde{q}(t)^{2p-1} dt\right) - \frac{\lambda}{2}(2p-1) \left( \int_0^1 \tilde{q}(t)^{2p-1} dt \right)^{\frac{2p}{2p-1}} + o_n(1) \\
&\leq \sup_{q \in [0, \rho]} \left\{ F_n(2p\lambda q^{2p-1}) - \frac{\lambda}{2}(2p-1)q^{2p} \right\} + o_n(1).
\end{align*}$$

We use now the fact that the convergence in (152) is uniform over all compact sets to get the upper-bound: $\limsup_{n \to \infty} f_n \leq \sup_{q \in [0, \rho]} \{F_{RS}(2p\lambda q^{2p-1}) - \frac{\lambda}{2}(2p-1)q^{2p}\}$. We conclude that

$$\lim_{n \to \infty} f_n = \sup_{q \in [0, \rho]} \left\{ F_{RS}(2p\lambda q^{2p-1}) - \frac{\lambda}{2}(2p-1)q^{2p} \right\}. \quad (155)$$

We are now going to simplify the right-hand side of the above equation.

**Lemma 11.** $F_{RS}$ is a convex function on $\mathbb{R}_+$, whose left- and right-derivatives at $\gamma \geq 0$ are:

$$\begin{align*}
F'_{RS}(\gamma^+) &= \max \left\{ \frac{1}{2} q_*(\gamma) \mid q_*(\gamma) \text{ achieves the supremum in (151)} \right\}, \\
F'_{RS}(\gamma^-) &= \min \left\{ \frac{1}{2} q_*(\gamma) \mid q_*(\gamma) \text{ achieves the supremum in (151)} \right\}.
\end{align*}$$

In particular, $F_{RS}$ is differentiable at $\gamma \geq 0$ if and only if the supremum in (151) is achieved at a unique $q_*(\gamma)$.

*Proof.* We already know that $F_{RS}$ is convex (as a limit of convex functions, see (152)). We have

$$F_{RS}(\gamma) = \sup_{q \in [0, \rho]} \inf_{r \geq 0} \left\{ \psi_{P_0}(r + \gamma) + \alpha \Psi_{P_{\text{out}}}(q) - \frac{rq}{2} \right\} = \sup_{q \in [0, \rho]} \left\{ \alpha \Psi_{P_{\text{out}}}(q) - g(\gamma, q/2) \right\} \quad (156)$$

where $g(\gamma, x) = \sup_{r \geq 0} \{xr - \psi_{P_0}(\gamma + r)\}$ is the Legendre transform of $r \mapsto \psi_{P_0}(\gamma + r)$. Let us now compute $\frac{\partial g}{\partial \gamma}(\gamma, x)$. If $x \leq \psi'_{P_0}(\gamma)$, then the supremum in $r$ is achieved at $r = 0$, $g(x, \gamma) = -\psi_{P_0}(\gamma)$. If now $x > \psi'_{P_0}(\gamma)$ then

$$g(\gamma, x) = \sup_{r \geq -\gamma} \{xr - \psi_{P_0}(\gamma + r)\} = -\gamma x + \sup_{r \geq 0} \{xr - \psi_{P_0}(r)\}.$$
The first equality comes from the fact that the supremum can not be achieved on $[-\gamma, 0]$ because for all $r \in [-\gamma, 0]$, $x > \psi'_{P_0}(\gamma) \ge \psi'_{P_0}(\gamma + r)$. We obtain

$$g(\gamma, x) = \begin{cases} -\psi_{P_0}(\gamma) & \text{if } x \le \psi'_{P_0}(\gamma), \\ -x\gamma + g(0, x) & \text{if } x > \psi'_{P_0}(\gamma). \end{cases}$$

From there, we conclude that $\frac{\partial g}{\partial \gamma}(\gamma, x) = -\max(\psi'_{P_0}(\gamma), x)$. By Lemma 23, every optimal couple $(q_*(\gamma), r_*(\gamma))$ satisfy $q_*(\gamma) = 2\psi'_{P_0}(\gamma + r_*(\gamma))$. This implies (by convexity of $\psi'_{P_0}$) that $q_*(\gamma)/2 \ge \psi'_{P_0}(\gamma)$. Using Corollary 4 from [93] $F_{RS}$ we get that

$$F'_{RS}(\gamma^+) = \max \left\{ -\frac{\partial g}{\partial \gamma}(\gamma, q_*(\gamma)) \mid q_*(\gamma) \text{ maximizer of (151)} \right\} = \max \left\{ \frac{1}{2} q_*(\gamma) \mid q_*(\gamma) \text{ maximizer of (151)} \right\}$$

and analogously for $F'_{RS}(\gamma^-)$. $\square$

**Lemma 12.** We have

$$\sup_{\tilde{q} \in [0, \rho]} \{F_{RS}(2p\lambda\tilde{q}^{2p-1}) - (2p-1)\frac{\lambda}{2}\tilde{q}^{2p}\} = \sup_{q \in [0, \rho]} \inf_{r \ge 0} \{\psi_{P_0}(r+2p\lambda q^{2p-1}) + \alpha\Psi_{P_{\text{out}}}(q) - \frac{rq}{2} - (2p-1)\frac{\lambda}{2}q^{2p}\}.$$

*Proof.* Consider the equality above. The inequality l.h.s $\ge$ r.h.s. is obvious because it suffices to restrict the supremum over $(q, \tilde{q}) \in [0, \rho]^2$ to the supremum over the couples $(q, q)$ for $q \in [0, \rho]$.

Let us prove now the converse inequality. Let us do the change of variable $x = \tilde{q}^{2p-1}$ and define $H(x) := F_{RS}(2p\lambda x) - (2p-1)\frac{\lambda}{2}x^{2p/(2p-1)}$. $F_{RS}$ is left- and right-differentiable everywhere, so is $H$. We have

$$H'(x) = 2p\lambda F'_{RS}(2p\lambda x) - \frac{\lambda}{2}2px^{1/(2p-1)} = p\lambda(2F'_{RS}(2p\lambda x) - x^{1/(2p-1)}) \quad (157)$$

at the points at which $H$ is differentiable, and analogously for the left- and right-derivatives of $H$. Let $x \in [0, \rho^{2p-1}]$ be a point at which $H$ achieves its supremum over $[0, \rho^{2p-1}]$. Let us distinguish 3 cases:

* Case 1: $x = 0$. In that case, we have $H'(0^+) \le 0$ and thus $F'_{RS}(0^+) \le 0$. Using Lemma 11, we obtain that the only $q \in [0, \rho]$ that achieves the supremum in (151) is $q = 0 = x^{1/(2p-1)}$.

* Case 2: $0 < x < \rho^{2p-1}$. We have then $H'(x^-) \ge 0$ and $H'(x^+) \le 0$. Using (157), we deduce that

$$2F'_{RS}((2p\lambda x)^+) \le x^{1/(2p-1)} \le 2F'_{RS}((2p\lambda x)^-).$$

$F_{RS}$ is convex, so the above inequalities collapses into equalities and we get that $F_{RS}$ is differentiable at $2p\lambda x$ with derivative given by $F'_{RS}(2p\lambda x) = x^{1/(2p-1)}/2$. Lemma 11 above gives then that the supremum in (151) is achieved uniquely at $q = x^{1/(2p-1)}$.

* Case 3: $x = \rho^{2p-1}$. Using the same arguments than in Case 1, we obtain also $q = x^{1/(2p-1)}$.

**Conclusion:** In all 3 cases above, $q = x^{1/(2p-1)}$ achieves the supremum in (151). Recall that we used the change of variable $x = \tilde{q}^{2p-1}$. Consequently, if $\tilde{q} \in [0, \rho]$ achieves the supremum of $\tilde{q} \mapsto F_{RS}(2p\lambda\tilde{q}^{2p-1}) - (2p-1)\lambda\tilde{q}^{2p}$, then $\tilde{q}$ achieves also the supremum in (151). This proves the converse bound. $\square$

By Lemma 12 and (155) above, we get that

$$f_n \xrightarrow{n \to \infty} \sup_{q \in [0, \rho]} \inf_{r \ge 0} \left\{ \psi_{P_0}(r + 2p\lambda q^{2p-1}) + \alpha \Psi_{P_{\text{out}}}(q) - \frac{rq}{2} - (2p-1)\frac{\lambda}{2}q^{2p} \right\}.$$
Proposition 10 follows then by rewriting the above limit in terms of mutual information, as we did to deduce Corollary 2 from Theorem 1. □

*Proof of Lemma 10:* The proof follows exactly the same steps than the one of Lemma 11, so we omit it for the sake brevity. □

### 5.3.2 Lower bound using the generalization error

Let us fix $\alpha \in D^*$. The sequence of the overlaps $(Q_n)_{n \ge 1}$ is tight (because bounded in $L^1$). By Prokhorov's Theorem we know that the sequence of the laws of $(Q_n)_{n \ge 1}$ is relatively compact. We can thus consider a subsequence along which it converges in law, to some random variable $Q$. In order to simplify the notations (and because working with an extraction does not change the proof) we will assume in the sequel that

$$Q_n \xrightarrow[n \to \infty]{(d)} Q,$$

for some random variable $Q$. We aim now at showing that $|Q| = q^*(\alpha)$ almost-surely.

**Lemma 13 (Upper bound on the overlap).** $|Q| \le q^*(\alpha)$ almost-surely.

*Proof.* Let $\epsilon > 0$. The set $[0, q^*(\alpha) + \epsilon]$ is closed, so by Portmanteau's Theorem

$$\mathbb{P}(|Q| \le q^*(\alpha) + \epsilon) \ge \limsup_{n \to \infty} \mathbb{P}(|Q_n| \le q^*(\alpha) + \epsilon) = 1,$$

by Proposition 9. So $\mathbb{P}(|Q| \le q^*(\alpha) + \epsilon) = 1$ for all $\epsilon > 0$ which gives $\mathbb{P}(|Q| \le q^*(\alpha)) = 1$. □

We are going to prove the converse lower bound using Theorem 4. Let $f: \mathbb{R} \to \mathbb{R}$ be a continuous bounded function. Theorem 4 gives $\mathcal{E}_{f,n}(\alpha) \xrightarrow[n \to \infty]{} \mathcal{E}_f(q^*(\alpha))$. The function $\mathcal{E}_f$ can be written as

$$\mathcal{E}_f(q) = \frac{1}{2} \mathbb{E} \left[ h_f \left( \sqrt{q} Z_0 + \sqrt{\rho-q} Z_1, \sqrt{q} Z_0 + \sqrt{\rho-q} Z'_1 \right) \right]$$

where $Z_0, Z_1, Z'_1 \stackrel{\text{iid}}{\sim} \mathcal{N}(0, 1)$ and $h_f: (a, b) \in \mathbb{R}^2 \mapsto \int (f(y_1) - f(y_2))^2 P_{\text{out}}(y_1|a)P_{\text{out}}(y_2|b)dy_1dy_2$. By a central limit argument, we have:

**Lemma 14.**

$$\left( \frac{\mathbf{x} \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}, \frac{\mathbf{X}^* \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}} \right) \xrightarrow{(d)} (Z_1, Z_2),$$

where $(Z_1, Z_2)$ is sampled, conditionally on $Q$, from $\mathcal{N}(0, \begin{pmatrix} \rho & Q \\ Q & \rho \end{pmatrix})$.

*Proof.* Notice that $\mathbf{x}$ and $\mathbf{X}$ are independent of $\mathbf{\Phi}_{\text{new}}$. If $(\mathbf{\Phi}_{\text{new},1}, \dots, \mathbf{\Phi}_{\text{new},n}) \stackrel{\text{iid}}{\sim} \mathcal{N}(0, 1)$, then Lemma 14 is obvious because in that case

$$\left( \frac{\mathbf{x} \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}, \frac{\mathbf{X}^* \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}} \right) \sim \mathcal{N} \left( 0, \frac{1}{n} \left( \frac{\|\mathbf{x}\|^2}{\mathbf{x} \cdot \mathbf{X}^*} \frac{\mathbf{x} \cdot \mathbf{X}^*}{\|\mathbf{X}^*\|^2} \right) \right) \quad \text{and} \quad \frac{1}{n} \left( \frac{\|\mathbf{x}\|^2}{\mathbf{x} \cdot \mathbf{X}^*} \frac{\mathbf{x} \cdot \mathbf{X}^*}{\|\mathbf{X}^*\|^2} \right) \xrightarrow[n \to \infty]{(d)} \begin{pmatrix} \rho & Q \\ Q & \rho \end{pmatrix}.$$

Let us now suppose that the entries of $\mathbf{\Phi}_{\text{new}}$ are not i.i.d. standard Gaussian (but still verify hypothesis (h3)). Let $g_1, \dots, g_n \stackrel{\text{iid}}{\sim} \mathcal{N}(0, 1)$. Let $L: \mathbb{R}^2 \to \mathbb{R}$ be a bounded $C^3$ function, with bounded partial derivatives. We have to show that

$$\mathbb{E} \left[ L \left( \frac{\mathbf{x} \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}, \frac{\mathbf{X}^* \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}} \right) \right] \xrightarrow[n \to \infty]{(d)} \mathbb{E} \left[ L(Z_1, Z_2) \right]. \quad (158)$$
We have seen above that $\mathbb{E}[L(\frac{\mathbf{x} \cdot \mathbf{g}}{\sqrt{n}}, \frac{\mathbf{X}^* \cdot \mathbf{g}}{\sqrt{n}})] \xrightarrow{n \to \infty} \mathbb{E}[L(Z_1, Z_2)]$. We now apply Theorem 5 (Theorem 2 from [95]) conditionally on $\mathbf{x}, \mathbf{X}^*$ to obtain

$$ \mathbb{E}[L\left(\frac{\mathbf{x} \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}, \frac{\mathbf{X}^* \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}\right)] = \mathbb{E}[L\left(\frac{\mathbf{x} \cdot \mathbf{g}}{\sqrt{n}}, \frac{\mathbf{X}^* \cdot \mathbf{g}}{\sqrt{n}}\right)] + \mathcal{O}_n(n^{-1/2}), $$

which proves (158) and therefore Lemma 14. □

**Proposition 11.** We have

$$ \mathcal{E}_{f,n}(\alpha) \xrightarrow{n \to \infty} \frac{1}{2} \mathbb{E}[h_f(Z_1, Z_2)], $$

where $(Z_1, Z_2)$ is defined in Lemma 14 above.

*Proof.* We have

$$ \begin{aligned} \mathcal{E}_{f,n} &= \mathbb{E}\left[\left(f(Y_{\text{new}}) - \mathbb{E}[f(Y_{\text{new}})|\mathbf{\Phi}_{\text{new}}, \mathbf{\Phi}, \mathbf{Y}]\right)^2\right] \\ &= \frac{1}{2}\mathbb{E}\left[\int (f(y_{\text{new}}) - f(y))^2 P_{\text{out}}(y_{\text{new}}|\mathbf{\Phi}_{\text{new}} \cdot \mathbf{X}^*/\sqrt{n}) P_{\text{out}}(y|\mathbf{\Phi}_{\text{new}} \cdot \mathbf{x}/\sqrt{n}) dy_{\text{new}} dy\right] \\ &= \frac{1}{2}\mathbb{E}\left[h_f\left(\frac{\mathbf{x} \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}, \frac{\mathbf{X}^* \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}\right)\right]. \end{aligned} $$

By Lemma 14 above, we have $(\frac{\mathbf{x} \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}, \frac{\mathbf{X}^* \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}) \xrightarrow{(d)} (Z_1, Z_2)$. Using (h4) (and the fact that either (h5.a) or (h5.b) hold), we can find a Borel set $S \subset \mathbb{R}$ of full Lebesgue's measure such that $x \mapsto P_{\text{out}}(y|x)$ is continuous on $S$, for all $y \in \mathbb{R}$. By dominated convergence (recall that $f$ is assumed to be bounded), we obtain that $h_f$ is continuous on $S \times S$. The set of discontinuity points of $h_f$ has thus zero measure for the law of $(Z_1, Z_2)$. Indeed if we condition on $Q$:

* if $|Q| < \rho$, then $(Z_1, Z_2)$ has a density over $\mathbb{R}^2$.

* if $Q = \rho$, then $Z_1 = Z_2$ almost surely, but $h_f$ is continuous on $\{(s, s) | s \in S\}$ that has full Lebesgue's measure on the diagonal $\{(x, x) | x \in \mathbb{R}\}$.

* if $Q = -\rho$, then $Z_1 = -Z_2$ almost surely and we use then similar arguments as for the previous point.

We have therefore:

$$ h_f\left(\frac{\mathbf{x} \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}, \frac{\mathbf{X}^* \cdot \mathbf{\Phi}_{\text{new}}}{\sqrt{n}}\right) \xrightarrow{n \to \infty} h_f(Z_1, Z_2), $$

and Lemma 11 follows from the fact that $h_f$ is bounded. □

Let us now define:

$$ H_f: \begin{array}{c} \left| \begin{array}{c} [-\rho, \rho] \\ q \end{array} \right. \rightarrow \mathbb{R} \\ q \mapsto \frac{1}{2} \mathbb{E}[h_f(G^{(q)})] \end{array} \qquad (159) $$

where $G^{(q)} \sim \mathcal{N}(0, (\rho_q^q, \rho_q^q))$. Notice that $H_f$ is equal to the function $\mathcal{E}_f$ on $[0, \rho]$. By Proposition 11 above and Theorem 4, we have:

$$ H_f(q^*(\alpha)) = \lim_{n \to \infty} \mathcal{E}_{f,n}(\alpha) = \mathbb{E}[H_f(Q)]. \qquad (160) $$

**Lemma 15.** For all $q \in [-\rho, \rho]$, $H_f(q) \ge H_f(|q|)$.

*Proof.* Let $q \in [0, \rho]$ and $Z_0, Z_1, Z'_1 \stackrel{\text{iid}}{\sim} \mathcal{N}(0, 1)$.

$$ H_f(-q) = \frac{1}{2} \mathbb{E} \left[ h_f \left( \sqrt{q} Z_0 + \sqrt{\rho - q} Z_1, -\sqrt{q} Z_0 + \sqrt{\rho - q} Z'_1 \right) \right]. $$
Let us denote by $\mathbb{E}_{Z_1}$ and $\mathbb{E}_{Z'_1}$ the expectations with respect to $Z_1$ and $Z'_1$. By replacing $h_f$ by its expression, we have

$$
\begin{align*}
H_f(-q) &= \frac{1}{2} \mathbb{E} \int (f(y) - f(y'))^2 P_{\text{out}}(y|\sqrt{q}Z_0 + \sqrt{\rho-q}Z_1) P_{\text{out}}(y'|\sqrt{q}Z_0 + \sqrt{\rho-q}Z'_1) dydy' \\
&= \frac{1}{2} \mathbb{E} \int (f(y) - f(y'))^2 \mathbb{E}_{Z_1} P_{\text{out}}(y|\sqrt{q}Z_0 + \sqrt{\rho-q}Z_1) \mathbb{E}_{Z'_1} P_{\text{out}}(y'|\sqrt{q}Z_0 + \sqrt{\rho-q}Z'_1) dydy' \\
&= \frac{1}{2} \mathbb{E} \int (f(y) - f(y'))^2 \tilde{P}_{\text{out}}(y|Z_0) \tilde{P}_{\text{out}}(y'|Z_0) dydy',
\end{align*}
$$

where $\tilde{P}_{\text{out}}(y|z) = \mathbb{E}_{Z_1}P_{\text{out}}(y|\sqrt{q}z + \sqrt{\rho-q}Z_1)$. Let now $Y$ and $Y'$ be two random variables that are independent conditionally on $Z_0$ and distributed as

$$ Y \sim \tilde{P}_{\text{out}}(\cdot|Z_0) \quad \text{and} \quad Y' \sim \tilde{P}_{\text{out}}(\cdot|Z_0). $$

Then we have

$$
\begin{align*}
H_f(-q) &= \frac{1}{2} \mathbb{E} \left[ (f(Y) - f(Y'))^2 \right] \\
&= \frac{1}{2} \mathbb{E} \left[ \left( f(Y) - \mathbb{E}[f(Y)|Z_0] + \mathbb{E}[f(Y)|Z_0] - f(Y') \right)^2 \right] \\
&= \frac{1}{2} \mathbb{E} \left[ \left( f(Y) - \mathbb{E}[f(Y)|Z_0] \right)^2 \right] + \frac{1}{2} \mathbb{E} \left[ \left( \mathbb{E}[f(Y)|Z_0] - f(Y') \right)^2 \right],
\end{align*}
$$

because $Y$ and $Y'$ are independent conditionally on $Z_0$. The conditional expectation $\mathbb{E}[f(Y)|Z_0]$ is $Z_0$-measurable, therefore $\mathbb{E}[(\mathbb{E}[f(Y)|Z_0]-f(Y'))^2] \ge \mathbb{E}[(\mathbb{E}[f(Y')|Z_0]-f(Y'))^2] = \mathbb{E}[(\mathbb{E}[f(Y)|Z_0]-f(Y))^2]$. We conclude

$$ H_f(-q) \ge \mathbb{E}[(\mathbb{E}[f(Y)|Z_0] - f(Y))^2] = H_f(q). $$

□

We have now all the tools needed to prove Theorem 2. Using Lemma 15 and (160) above, we get that $\mathbb{E}H_f(|Q|) \le \mathbb{E}H_f(Q) = H_f(q^*(\alpha))$. Since $H_f$ is equal to $\mathcal{E}_f$ on $[0, \rho]$ this gives

$$ \mathbb{E}[\mathcal{E}_f(|Q|)] \le \mathcal{E}_f(q^*(\alpha)). \qquad (161) $$

If $q^*(\alpha) = 0$, then Theorem 2 follows simply from Proposition 9. We suppose now that $q^*(\alpha) > 0$ and consider $\epsilon \in (0, q^*(\alpha))$. We define $p(\epsilon) = \mathbb{P}(|Q| \le q^*(\alpha) - \epsilon)$. We are going to show that $p(\epsilon) = 0$. We assumed that $P_{\text{out}}$ is informative, so by Proposition 23 and Proposition 24 in Appendix B.2, there exists a continuous bounded function $f: \mathbb{R} \mapsto \mathbb{R}$ such that $\mathcal{E}_f$ is strictly decreasing on $[0, \rho]$. In the following, $f$ is assumed to be such a function. We have

$$
\begin{align*}
\mathbb{E}[\mathcal{E}_f(|Q|)] &= \mathbb{E}[\mathbf{1}(|Q| \le q^*(\alpha) - \epsilon)\mathcal{E}_f(|Q|) + \mathbf{1}(|Q| > q^*(\alpha) - \epsilon)\mathcal{E}_f(|Q|)] \\
&\ge p(\epsilon)\mathcal{E}_f(q^*(\alpha) - \epsilon) + (1 - p(\epsilon))\mathcal{E}_f(q^*(\alpha)).
\end{align*}
$$

because $\mathcal{E}_f$ is non-increasing and because $|Q| \le q^*(\alpha)$ almost-surely (Lemma 13). Combining this with (161) leads to

$$ p(\epsilon)\mathcal{E}_f(q^*(\alpha)) \ge p(\epsilon)\mathcal{E}_f(q^*(\alpha) - \epsilon). $$

Since $\mathcal{E}_f$ is strictly decreasing: $\mathcal{E}_f(q^*(\alpha)) < \mathcal{E}_f(q^*(\alpha) - \epsilon)$, which implies $p(\epsilon) = 0$. This is true for all $\epsilon > 0$, consequently $|Q| \ge q^*(\alpha)$ almost-surely. We get (using Lemma 13) that

$$ |Q| = q^*(\alpha), \quad \text{almost-surely.} $$
We conclude that the only possible limit in law of the tight sequence ($|Q_n|$)$_{n \ge 1}$ is $q^*(\alpha)$. Therefore $|Q_n| \to q^*(\alpha)$ in law and in probability because $q^*(\alpha)$ is a constant.

## 5.4 Denoising error: Proof of Corollary 5

Start by noticing that the denoising error, i.e. the right hand side of (74), is obtained through the I-MMSE theorem, see Proposition 13, applied to $\tilde{i}_n := I(\mathbf{X}^*, \mathbf{A}; \mathbf{Y} | \mathbf{\Phi})/n$:

$$ \frac{\partial \tilde{i}_n}{\partial \Delta^{-1}} = \frac{1}{2n} \text{MMSE} \left( \varphi \left( \frac{1}{\sqrt{n}} \mathbf{\Phi} \mathbf{X}^*, \mathbf{A} \right) \middle| \mathbf{\Phi}, \mathbf{Y} \right). \quad (162) $$

This mutual information is simply computed using our main theorem. Indeed,

$$ \tilde{i}_{\infty} := \lim_{n \to \infty} \tilde{i}_n = \lim_{n \to \infty} \frac{1}{n} H(\mathbf{Y} | \mathbf{\Phi}) - \lim_{n \to \infty} \frac{1}{n} H(\mathbf{Y} | \mathbf{\Phi}, \mathbf{X}^*, \mathbf{A}) = -f_{\infty} - \lim_{n \to \infty} \frac{1}{n} H(\mathbf{Y} | \mathbf{\Phi}, \mathbf{X}^*, \mathbf{A}). $$

One can simply check that $\lim_{n \to \infty} H(\mathbf{Y} | \mathbf{\Phi}, \mathbf{X}^*, \mathbf{A})/n = \alpha \ln(2\pi\Delta e)/2$ by similar computations as in the proof of Corollary 2. Therefore, defining

$$ \tilde{i}_{\text{RS}}(q, \Delta) := -\frac{\alpha}{2} \ln(2\pi\Delta e) - \alpha \Psi_{\text{Pout}}(q) - \inf_{r \ge 0} \left\{ \psi_{P_0}(r) - \frac{qr}{2} \right\}, $$

we have $\tilde{i}_{\infty} = \sup_{q \in [0, \rho]} \tilde{i}_{\text{RS}}(q, \Delta)$ from Theorem 1.

One can verify easily that $\tilde{i}_n$ is a concave differentiable function of $\Delta^{-1}$ (this is again related to the I-MMSE theorem). Thus its limit $\tilde{i}_{\infty}$ is also a concave function of $\Delta^{-1}$. Therefore, a standard analysis lemma gives that the derivative of $\tilde{i}_n$ w.r.t. $\Delta^{-1}$ converges to the derivative of $\tilde{i}_{\infty}$ at every point at which $\tilde{i}_{\infty}$ is differentiable (i.e. almost every points, by concavity): $\lim_{n \to \infty} \partial_{\Delta^{-1}} \tilde{i}_n = \partial_{\Delta^{-1}} \tilde{i}_{\infty} = \partial_{\Delta^{-1}} \sup_{q \in [0, \rho]} \tilde{i}_{\text{RS}}(q, \Delta)$. The first limit is given by the limit of the right hand side of (162). It thus remains to compute $\partial_{\Delta^{-1}} \sup_{q \in [0, \rho]} \tilde{i}_{\text{RS}}(q, \Delta)$.

Assume for a moment that the $\partial_{\Delta^{-1}}$ and $\sup_{q \in [0, \rho]}$ operations commute. Then we need to compute $\partial_{\Delta^{-1}} \Psi_{\text{Pout}}(q)$; this follows from the I-MMSE theorem. Indeed, if we denote $S = \varphi(\sqrt{q} V + \sqrt{\rho-q} W^*, \mathbf{A})$, notice that $\Psi_{\text{Pout}}(q) = -I(S; S + \sqrt{\Delta}Z | V) - \ln(2\pi e \Delta)/2$, because $\Psi_{\text{Pout}}(q) = -H(S + \sqrt{\Delta}Z | V)$ and $I(S + \sqrt{\Delta}Z; S | V) = H(S + \sqrt{\Delta}Z | V) - H(S + \sqrt{\Delta}Z | V, S) = -\Psi_{\text{Pout}}(q) - \ln(2\pi e \Delta)/2$. Therefore

$$ \begin{aligned} \frac{\partial \Psi_{\text{Pout}}(q)}{\partial \Delta^{-1}} &= \frac{\Delta}{2} - \frac{\partial}{\partial \Delta^{-1}} I(S + \sqrt{\Delta}Z; S | V) = \frac{\Delta}{2} - \frac{1}{2} \text{MMSE}(S | V, S + \sqrt{\Delta}Z) \\ &= \frac{\Delta}{2} - \frac{1}{2} \left( \mathbb{E}[\varphi(\sqrt{\rho}V, \mathbf{A})^2] - \mathbb{E}[\langle \varphi(\sqrt{q}V + \sqrt{\rho-q}w, \mathbf{a}) \rangle_{\text{sc}}^2] \right). \end{aligned} $$

Consequently,

$$ \frac{\partial \tilde{i}_{\text{RS}}(q, \Delta)}{\partial \Delta^{-1}} = \frac{\alpha}{2} \left( \mathbb{E}[\varphi(\sqrt{\rho}V, \mathbf{A})^2] - \mathbb{E}[\langle \varphi(\sqrt{q}V + \sqrt{\rho-q}w, \mathbf{a}) \rangle_{\text{sc}}^2] \right). $$

Now, Theorem 1 from [93] gives that at every $\Delta^{-1}$ at which $i_{\infty}$ is differentiable

$$ \frac{\partial \tilde{i}_{\infty}}{\partial \Delta^{-1}} = \frac{\partial}{\partial \Delta^{-1}} \sup_{q \in [0, \rho]} \tilde{i}_{\text{RS}}(q, \Delta) = \frac{\alpha}{2} \left( \mathbb{E}[\varphi(\sqrt{\rho}V, \mathbf{A})^2] - \mathbb{E}[\langle \varphi(\sqrt{q^*}V + \sqrt{\rho-q^*}w, \mathbf{a}) \rangle_{\text{sc}}^2] \right) $$

where $q^* \in [0, \rho]$ is a point where the supremum above is achieved, and thus corresponds to an optimal couple in (43). As explained above, $\lim_{n \to \infty} \partial_{\Delta^{-1}} \tilde{i}_n = \partial_{\Delta^{-1}} \tilde{i}_{\infty}$ at every $\Delta^{-1}$ at which $\tilde{i}_{\infty}$ is differentiable, which concludes the proof.
# Appendix A: Some technicalities

## A.1 The Nishimori identity

**Proposition 12** (Nishimori identity). Let $(\mathbf{X}, \mathbf{Y}) \in \mathbb{R}^{n_1} \times \mathbb{R}^{n_2}$ be a couple of random variables. Let $k \ge 1$ and let $\mathbf{X}^{(1)}, \dots, \mathbf{X}^{(k)}$ be $k$ i.i.d. samples (given $\mathbf{Y}$) from the conditional distribution $P(\mathbf{X} = \cdot | \mathbf{Y})$, independently of every other random variables. Let us denote $\langle - \rangle$ the expectation operator w.r.t. $P(\mathbf{X} = \cdot | \mathbf{Y})$ and $\mathbb{E}$ the expectation w.r.t. $(\mathbf{X}, \mathbf{Y})$. Then, for all continuous bounded function $g$ we have

$$ \mathbb{E}\langle g(\mathbf{Y}, \mathbf{X}^{(1)}, \dots, \mathbf{X}^{(k)}) \rangle = \mathbb{E}\langle g(\mathbf{Y}, \mathbf{X}^{(1)}, \dots, \mathbf{X}^{(k-1)}, \mathbf{X}) \rangle. \quad (163) $$

*Proof.* This is a simple consequence of Bayes formula. It is equivalent to sample the couple $(\mathbf{X}, \mathbf{Y})$ according to its joint distribution or to sample first $\mathbf{Y}$ according to its marginal distribution and then to sample $\mathbf{X}$ conditionally to $\mathbf{Y}$ from its conditional distribution $P(\mathbf{X} = \cdot | \mathbf{Y})$. Thus the $(k+1)$-tuple $(\mathbf{Y}, \mathbf{X}^{(1)}, \dots, \mathbf{X}^{(k)})$ is equal in law to $(\mathbf{Y}, \mathbf{X}^{(1)}, \dots, \mathbf{X}^{(k-1)}, \mathbf{X})$. $\square$

## A.2 Unicity of the optimizer $q^*$ of the replica formula: Proof of Proposition 1

The function

$$ h: \alpha \mapsto \inf_{q \in [0, \rho]} \left\{ \alpha \mathcal{I}_{P_{\text{out}}}(q) + \sup_{r \ge 0} \left\{ I_{P_0}(r) - \frac{r}{2}(\rho - q) \right\} \right\} \quad (164) $$

is concave (as an infimum of linear functions). An “envelope” theorem (Corollary 4 from [93]) gives that $h$ is differentiable at $\alpha$ if and only if

$$ \{ \mathcal{I}_{P_{\text{out}}}(q) \mid q \text{ minimizer of (164)} \} $$

is a singleton. We assumed that $P_{\text{out}}$ is informative, so Proposition 21 gives that $\mathcal{I}_{P_{\text{out}}}$ is strictly decreasing. We obtain thus that the set of points at which $h$ is differentiable is exactly $D^*$. Since $h$ is concave, $D^*$ is equal to $\mathbb{R}_+^*$ minus a countable set. Corollary 4 from [93] gives also that $h'(\alpha) = \mathcal{I}_{P_{\text{out}}}(q^*(\alpha))$, for all $\alpha \in D^*$. The function $h$ is concave, so its derivative $h'$ is non-increasing. Since $\mathcal{I}_{P_{\text{out}}}$ is strictly decreasing, we obtain that $\alpha \in D^* \mapsto q^*(\alpha)$ is non-decreasing.

Let now $\alpha_0 \in D^*$. By concavity of $h$, $h'(\alpha) \to h'(\alpha_0)$ when $\alpha \in D^* \to \alpha_0$. Therefore:

$$ \mathcal{I}_{P_{\text{out}}}(q^*(\alpha)) \xrightarrow[\alpha \in D \to \alpha_0]{\alpha \in D} \mathcal{I}_{P_{\text{out}}}(q^*(\alpha_0)) $$

which implies $q^*(\alpha) \to q^*(\alpha_0)$ by strict monotonicity of $\mathcal{I}_{P_{\text{out}}}$.

## A.3 Continuity properties of the mutual information

We establish in this section two continuity properties of the mutual information, namely Proposition 14 and Corollary 7. Recall definition (33) of the MMSE function. The following proposition comes from [54] and will be repeatedly used in the sequel.

**Proposition 13** (I-MMSE theorem, [54, 94]). Let $P_X$ be a probability distribution over $\mathbb{R}^n$ that admits a finite second moment. Let $\mathbf{X} \sim P_X$ and $\mathbf{Z} \sim \mathcal{N}(0, \mathbf{I}_n)$ be independent random variables. Then the function

$$ I_{P_X} : \begin{array}{c} \mathbb{R}_+ \to \mathbb{R} \\ \lambda \mapsto I(\mathbf{X}; \sqrt{\lambda}\mathbf{X} + \mathbf{Z}) \end{array} $$
is concave, continuously differentiable over $\mathbb{R}_+$, with derivative given by

$$I'_{P_X}(\lambda) = \frac{1}{2}\mathrm{MMSE}(\mathbf{X} | \sqrt{\lambda}\mathbf{X} + \mathbf{Z}) = \frac{1}{2}\mathrm{E}\left[\|\mathbf{X} - \mathrm{E}[\mathbf{X} | \sqrt{\lambda}\mathbf{X} + \mathbf{Z}]\|^2\right].$$

**Remark:** We will often apply Proposition 13 in a “conditional fashion”. Let $\mathbf{U}$ be some random variable independent from $\mathbf{Z}$, then

$$\frac{\partial}{\partial \lambda} I(\mathbf{X}; \sqrt{\lambda}\mathbf{X} + \mathbf{Z}|\mathbf{U}) = \frac{1}{2}\mathrm{MMSE}(\mathbf{X} | \sqrt{\lambda}\mathbf{X} + \mathbf{Z}, \mathbf{U}) = \frac{1}{2}\mathrm{E}\left[\|\mathbf{X} - \mathrm{E}[\mathbf{X} | \sqrt{\lambda}\mathbf{X} + \mathbf{Z}, \mathbf{U}]\|^2\right].$$

**Proposition 14.** Let $P_1$ and $P_2$ be two probability distributions on $\mathbb{R}^n$, that admits a finite second moment. We denote by $W_2(P_1, P_2)$ the Wasserstein distance of order 2 between $P_1$ and $P_2$.

$$|I(\mathbf{X}_1; \mathbf{X}_1 + \mathbf{Z}) - I(\mathbf{X}_2; \mathbf{X}_2 + \mathbf{Z})| \le (\sqrt{\mathrm{E}\|\mathbf{X}_1\|^2} + \sqrt{\mathrm{E}\|\mathbf{X}_2\|^2}) W_2(P_1, P_2).$$

A similar result was proved in [96] but with a weaker bound for the $W_2$ distance.

*Proof.* Let $\epsilon > 0$. Let us fix a coupling of $\mathbf{X}_1 \sim P_1$ and $\mathbf{X}_2 \sim P_2$ such that

$$(\mathrm{E}\|\mathbf{X}_1 - \mathbf{X}_2\|^2)^{1/2} \le W_2(P_1, P_2) + \epsilon.$$

Let us consider for $t_1, t_2 \in [0, 1]$ the observation model

$$\begin{cases} \mathbf{Y}_1^{(t_1)} = \sqrt{t_1}\mathbf{X}_1 + \mathbf{Z}_1, \\ \mathbf{Y}_2^{(t_2)} = \sqrt{1-t_2}\mathbf{X}_2 + \mathbf{Z}_2, \end{cases}$$

where $\mathbf{Z}_1, \mathbf{Z}_2 \stackrel{\mathrm{iid}}{\sim} \mathcal{N}(0, \mathbf{I}_n)$ are independent from $(\mathbf{X}_1, \mathbf{X}_2)$. Define $J(t_1, t_2) = I(\mathbf{X}_1, \mathbf{X}_2; \mathbf{Y}_1^{(t_1)}, \mathbf{Y}_2^{(t_2)})$ and $I(t) = J(t, t)$. Let us now differentiate $J$ with respect to $t_1$. Using the chain rule for the mutual information,

$$\begin{aligned} J(t_1, t_2) &= I(\mathbf{X}_1, \mathbf{X}_2; \mathbf{Y}_2^{(t_2)}) + I(\mathbf{X}_1, \mathbf{X}_2; \mathbf{Y}_1^{(t_1)} | \mathbf{Y}_2^{(t_2)}) = I(\mathbf{X}_1, \mathbf{X}_2; \mathbf{Y}_2^{(t_2)}) + I(\mathbf{X}_1; \mathbf{Y}_1^{(t_1)} | \mathbf{Y}_2^{(t_2)}) + I(\mathbf{X}_2; \mathbf{Y}_1^{(t_1)} | \mathbf{X}_1, \mathbf{Y}_2^{(t_2)}) \\ &= I(\mathbf{X}_1, \mathbf{X}_2; \mathbf{Y}_2^{(t_2)}) + I(\mathbf{X}_1; \mathbf{Y}_1^{(t_1)} | \mathbf{Y}_2^{(t_2)}) \end{aligned}$$

because, conditionally on $\mathbf{X}_1, \mathbf{X}_2$ and $\mathbf{Y}_1^{(t_1)}$ are independent. The quantity $I(\mathbf{X}_1, \mathbf{X}_2; \mathbf{Y}_2^{(t_2)})$ does not depend on $t_1$, therefore by the “I-MMSE relation” from Proposition 13:

$$\frac{\partial J}{\partial t_1}(t_1, t_2) = \frac{1}{2}\mathrm{MMSE}(\mathbf{X}_1 | \mathbf{Y}_1^{(t_1)}, \mathbf{Y}_2^{(t_2)})$$

and similarly

$$\frac{\partial J}{\partial t_2}(t_1, t_2) = -\frac{1}{2}\mathrm{MMSE}(\mathbf{X}_2 | \mathbf{Y}_1^{(t_1)}, \mathbf{Y}_2^{(t_2)}).$$

Let us write $\mathbf{E}_i = \mathrm{E}[\mathbf{X}_i | \mathbf{Y}_1^{(t)}, \mathbf{Y}_2^{(t)}]$ for $i = 1, 2$, then

$$I'(t) = \frac{1}{2}\mathrm{MMSE}(\mathbf{X}_1 | \mathbf{Y}_1^{(t)}, \mathbf{Y}_2^{(t)}) - \frac{1}{2}\mathrm{MMSE}(\mathbf{X}_2 | \mathbf{Y}_1^{(t)}, \mathbf{Y}_2^{(t)}) = \frac{1}{2}\mathrm{E}\left[\|\mathbf{X}_1 - \mathbf{E}_1\|^2 - \|\mathbf{X}_2 - \mathbf{E}_2\|^2\right]$$
so that

$$
\begin{align*}
|I'(t)| &= \frac{1}{2} \mathbb{E} \left[ \left( \|\mathbf{X}_1 - \mathbf{E}_1\| + \|\mathbf{X}_2 - \mathbf{E}_2\| \right) \left( \|\mathbf{X}_1 - \mathbf{E}_1\| - \|\mathbf{X}_2 - \mathbf{E}_2\| \right) \right] \\
&\le \frac{1}{2} \mathbb{E} \left[ \left\|\mathbf{X}_1\right\|^2 + \left\|\mathbf{X}_2\right\|^2 \right]^{1/2} \mathbb{E} \left[ \left( \|\mathbf{X}_1 - \mathbf{E}_1\| - \|\mathbf{X}_2 - \mathbf{E}_2\| \right)^2 \right]^{1/2} \\
&\le \frac{1}{2} \mathbb{E} \left[ \left\|\mathbf{X}_1\right\|^2 + \left\|\mathbf{X}_2\right\|^2 \right]^{1/2} \mathbb{E} \left[ \left\|\mathbf{X}_1 - \mathbf{X}_2 + \mathbf{E}_2 - \mathbf{E}_1\right\|^2 \right]^{1/2} \\
&\le \frac{1}{2} \left( \sqrt{\mathbb{E}\|\mathbf{X}_1\|^2} + \sqrt{\mathbb{E}\|\mathbf{X}_2\|^2} \right) \mathbb{E} \left[ 2\|\mathbf{X}_1 - \mathbf{X}_2\|^2 + 2\|\mathbf{E}_2 - \mathbf{E}_1\|^2 \right]^{1/2} \\
&\le \left( \sqrt{\mathbb{E}\|\mathbf{X}_1\|^2} + \sqrt{\mathbb{E}\|\mathbf{X}_2\|^2} \right) (W_2(P_1, P_2) + \epsilon).
\end{align*}
$$

We obtain the result by letting $\epsilon \to 0$.

<figure><img src="image_8.png" /></figure>

**Proposition 15.** Let $P_U$ be a probability distribution over $\mathbb{N}^m$ that admits a finite second moment. Let $\mathbf{U} \sim P_U$ and $\mathbf{Z} \sim \mathcal{N}(0, \mathbf{I}_m)$ be two independent random variables. Then $H(\mathbf{U}) = -\sum_{\mathbf{n} \in \mathbb{N}^m} P_U(\mathbf{n}) \ln P_U(\mathbf{n})$ is finite and for all $\Delta \in (0, 1]$,

$$
|I(\mathbf{U}; \mathbf{U} + \sqrt{\Delta}\mathbf{Z}) - H(\mathbf{U})| \le 48me^{-1/(16\Delta)}.
$$

Proof. Let us define for $\Delta > 0$, $h(\Delta) = I(\mathbf{U}; \mathbf{U} + \sqrt{\Delta}\mathbf{Z}) = I_{P_U}(\Delta^{-1})$. By Proposition 13 we have for all $\Delta > 0$,

$$
h'(\Delta) = -\frac{1}{2\Delta^2} \mathrm{MMSE}(\mathbf{U} | \mathbf{U} + \sqrt{\Delta Z}). \quad (165)
$$

We are now going to upper bound MMSE($\mathbf{U} | \mathbf{U} + \sqrt{\Delta Z}$) by considering the following estimator:

$$
\hat{\theta}_i = \arg \min_{u \in \mathbb{N}} |u - U_i + \sqrt{\Delta} Z_i|,
$$

for all $i \in \{1, \dots, m\}$. Note that $\hat{\theta}_i$ is well-defined almost-surely since there is a.s. a unique minimizer above.
We have

$$
\mathbb{P}(\hat{\theta}_i \neq U_i) \le \mathbb{P}(\sqrt{\Delta} |Z_i| \ge 1/2) = 2\mathbb{P}(\mathcal{N}(0,1) \ge \frac{1}{2\sqrt{\Delta}}) \le 2\frac{1}{\sqrt{2\pi}} 2\sqrt{\Delta} e^{-1/(8\Delta)} \le 2\sqrt{\Delta} e^{-1/(8\Delta)},
$$

by usual bounds on the Gaussian cumulative distribution function. We have then

$$
\begin{align*}
\text{MMSE}(\mathbf{U} | \mathbf{U} + \sqrt{\Delta Z}) &\le \mathbb{E}\|\mathbf{U} - \hat{\theta}\|^2 = \sum_{i=1}^{m} \mathbb{E}(U_i - \hat{\theta}_i)^2 = \sum_{i=1}^{m} \mathbb{E}[\mathbf{1}(\hat{\theta}_i \neq U_i)(U_i - \hat{\theta}_i)^2] \\
&\le \sum_{i=1}^{m} 2\mathbb{E}[\mathbf{1}(\hat{\theta}_i \neq U_i)(U_i - (U_i + \sqrt{\Delta}Z_i))^2] + 2\mathbb{E}[\mathbf{1}(\hat{\theta}_i \neq U_i)(U_i + \sqrt{\Delta}Z_i - \hat{\theta}_i)^2] \\
&\le \sum_{i=1}^{m} 2\mathbb{E}[\mathbf{1}(\hat{\theta}_i \neq U_i)\Delta Z_i^2] + \frac{1}{2}\mathbb{E}[\mathbf{1}(\hat{\theta}_i \neq U_i)] \\
&\le \sum_{i=1}^{m} 2\Delta\mathbb{P}(\hat{\theta}_i \neq U_i)^{1/2}\mathbb{E}[Z_i^4]^{1/2} + \frac{1}{2}\mathbb{P}(\hat{\theta}_i \neq U_i) \\
&\le me^{-1/(16\Delta)} (2\sqrt{6}\Delta^{5/4} + \sqrt{\Delta}) \le 6me^{-1/(16\Delta)}
\end{align*}
$$

for $\Delta \le 1$. Plugging this inequality in (165), we obtain for all $\Delta \in (0, 1]$,

$$
|h'(\Delta)| \le \frac{3m}{\Delta^2} e^{-1/(16\Delta)}. \qquad (166)
$$
Since $h(1)$ is finite and $\int_0^1 \frac{e^{-1/(16\Delta)}}{\Delta^2} d\Delta < +\infty$ we obtain that

$$ \sup_{\Delta \in (0,1]} |h(\Delta)| < +\infty. \qquad (167) $$

By definition of $h$:

$$ h(\Delta) = I(\mathbf{U}; \mathbf{U} + \sqrt{\Delta}\mathbf{Z}) = -\frac{m}{2} - \mathbb{E} \ln \sum_{\mathbf{U} \in \mathbb{N}^m} P_U(\mathbf{U}) \exp \left( -\frac{1}{2\Delta} \|\mathbf{U} + \sqrt{\Delta}\mathbf{Z} - \mathbf{U}\|^2 \right). \quad (168) $$

By the previous equality and (167), the family of (non-negative) random variables

$$ \left( -\ln \sum_{\mathbf{U} \in \mathbb{N}^m} P_U(\mathbf{U}) \exp \left( -\frac{1}{2\Delta} \|\mathbf{U} + \sqrt{\Delta}\mathbf{Z} - \mathbf{U}\|^2 \right) \right)_{\Delta \in (0,1]} $$

is bounded in $L^1$. Notice that (by dominated convergence)

$$ -\ln \sum_{\mathbf{U} \in \mathbb{N}^m} P_U(\mathbf{U}) \exp \left( -\frac{1}{2\Delta} \|\mathbf{U} + \sqrt{\Delta}\mathbf{Z} - \mathbf{U}\|^2 \right) \xrightarrow{\Delta \to 0} -\ln \left( P_U(\mathbf{U})e^{-\frac{1}{2}\|\mathbf{Z}\|^2} \right) = \frac{1}{2}\|\mathbf{Z}\|^2 - \ln P_U(\mathbf{U}) $$

almost-surely. This gives (by Fatou's Lemma) that this almost-sure limit is integrable and thus that $H(\mathbf{U}) = -\mathbb{E} \ln P_U(\mathbf{U})$ is finite. Let us now show that $h(\Delta) \xrightarrow{\Delta \to 0} H(\mathbf{U})$. We have almost-surely

$$ \ln \left( P_U(\mathbf{U})e^{-\frac{1}{2}\|\mathbf{Z}\|^2} \right) \le \ln \sum_{\mathbf{U} \in \mathbb{N}^m} P_U(\mathbf{U}) \exp \left( -\frac{1}{2\Delta} \|\mathbf{U} + \sqrt{\Delta}\mathbf{Z} - \mathbf{U}\|^2 \right) \le 0. $$

Since we now know that the left-hand side is integrable (because $H(\mathbf{U})$ is finite), we can apply the dominated convergence theorem to obtain that

$$ \mathbb{E} \ln \sum_{\mathbf{U} \in \mathbb{N}^m} P_U(\mathbf{U}) \exp \left( -\frac{1}{2\Delta} \|\mathbf{U} + \sqrt{\Delta}\mathbf{Z} - \mathbf{U}\|^2 \right) \xrightarrow{\Delta \to 0} \mathbb{E} \ln \left( P_U(\mathbf{U}) e^{-\frac{1}{2}\|\mathbf{Z}\|^2} \right) = H(\mathbf{U}) - \frac{m}{2}, $$

which combined with (168) gives $h(\Delta) \xrightarrow{\Delta \to 0} H(\mathbf{U})$. Now, using the bound on the derivative of $h$ (166) we conclude that for all $\Delta \in (0, 1]$,

$$ |h(\Delta) - H(\mathbf{U})| \le 3m \int_0^\Delta \frac{e^{-1/(16t)}}{t^2} dt = 3m \left[ 16e^{-1/(16t)} \right]_0^\Delta = 48me^{-1/(16\Delta)}. $$

□

**Corollary 7.** Let $\mathbf{U}$ be a random variable over $\mathbb{N}^m$ with finite second moment, let $\mathbf{X}$ be a random variable over $\mathbb{R}^n$ and let $\mathbf{Z} \sim \mathcal{N}(0, \mathbf{I}_m)$. We assume $(\mathbf{U}, \mathbf{X})$ to be independent from $\mathbf{Z}$. Then, for all $\Delta \in (0, 1]$,

$$ |I(\mathbf{X}; \mathbf{U} + \sqrt{\Delta}\mathbf{Z}) - I(\mathbf{X}; \mathbf{U})| \le 100me^{-1/(16\Delta)}. $$

*Proof.* We have by the chain rule of the mutual information:

$$ I(\mathbf{U}; \mathbf{U} + \sqrt{\Delta}\mathbf{Z}) = I(\mathbf{U}, \mathbf{X}; \mathbf{U} + \sqrt{\Delta}\mathbf{Z}) = I(\mathbf{X}; \mathbf{U} + \sqrt{\Delta}\mathbf{Z}) + I(\mathbf{U}; \mathbf{U} + \sqrt{\Delta}\mathbf{Z}|\mathbf{X}). $$

By applying Proposition 15 twice, we get

$$ |I(\mathbf{U}; \mathbf{U} + \sqrt{\Delta}\mathbf{Z}) - H(\mathbf{U})|, |I(\mathbf{U}; \mathbf{U} + \sqrt{\Delta}\mathbf{Z}|\mathbf{X}) - H(\mathbf{U}|\mathbf{X})| \le 48me^{-1/(16\Delta)}. $$
Since $I(\mathbf{X}; \mathbf{U}) = H(\mathbf{U}) - H(\mathbf{U}|\mathbf{X})$ we obtain the desired inequality. $\square$

### A.4 A simple consequence of hypotheses (h1)-(h2)-(h3)-(h4)

**Proposition 16.** Assume that hypotheses (h1)-(h2)-(h3)-(h4) hold. Then there exists $\eta > 0$ such that

$$ \mathbb{E}[\varphi(\sqrt{\rho}Z, \mathbf{A})^{2+\eta}] < \infty, $$

where the expectation above is with respect to $(Z, \mathbf{A}) \sim \mathcal{N}(0, 1) \otimes P_A$.

*Proof.* By the Central Limit Theorem (using the fact that the third moments of $(X_i^*\Phi_{1,i})$ are bounded with $n$, because of hypotheses (h1) and (h3)) we have $([\Phi\mathbf{X}^*]_1/\sqrt{n}, \mathbf{A}_1) \xrightarrow{n\to\infty} (\sqrt{\rho}G, \mathbf{A}_1)$. This implies that

$$ \varphi\left(\frac{[\Phi\mathbf{X}^*]_1}{\sqrt{n}}, \mathbf{A}_1\right) \xrightarrow{n\to\infty} \varphi(\sqrt{\rho}G, \mathbf{A}_1), \quad (169) $$

because $\varphi(\cdot, \mathbf{A}_1)$ is almost-surely continuous almost-everywhere, by assumption (h4). The sequence of random variables $(\varphi([\Phi\mathbf{X}^*]_1/\sqrt{n}, \mathbf{A}_1))_n$ is by assumption (h2) bounded in $L^{2+\eta}$ for some $\eta > 0$. By (169) we conclude that $\mathbb{E}[\varphi(\sqrt{\rho}G, \mathbf{A}_1)^{2+\eta}] < \infty$. $\square$

### A.5 Derivative of the interpolating free entropy: Proof of Proposition 3

Recall $u'_y(x)$ is the $x$-derivative of $u_y(x) = \ln P_{\text{out}}(y|x)$. Moreover denote $P'_{\text{out}}(y|x)$ and $P''_{\text{out}}(y|x)$ the first and second $x$-derivatives, respectively, of $P_{\text{out}}(y|x)$. We will first prove that for all $t \in (0, 1)$

$$ \frac{df_{n,\epsilon}(t)}{dt} = -\frac{1}{2} \mathbb{E} \left\langle \left( \frac{1}{n} \sum_{\mu=1}^{m} u'_{Y_{t,\mu}}(S_{t,\mu}) u'_{Y_{t,\mu}}(S_{t,\mu}) - r(t) \right) (Q - q(t)) \right\rangle_{n,t,\epsilon} + \frac{r(t)}{2} (q(t) - \rho) - \frac{A_n}{2}, \quad (170) $$

where recall $Q := \sum_{i=1}^n X_i^*x_i/n$ and

$$ A_{n,\epsilon} := \mathbb{E} \left[ \frac{1}{\sqrt{n}} \sum_{\mu=1}^{m} \frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})} \left( \frac{1}{\sqrt{n}} \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right) \frac{1}{n} \ln \mathcal{Z}_{t,\epsilon} \right]. \quad (171) $$

Once this is done, we will prove that $A_{n,\epsilon}$ goes to 0 as $n \to \infty$ uniformly in $t \in [0, 1]$, in order to obtain Proposition 3.

#### A.5.1 Proof of (170)

Recall definition (98) which becomes, when written as a function of the interpolating Hamiltonian (95),

$$ f_{n,\epsilon}(t) = \frac{1}{n} \mathbb{E}_{\Phi, \mathbf{V}} \int d\mathbf{Y}_t d\mathbf{Y}_t' dP_0(\mathbf{X}^*) \mathcal{D}\mathbf{W}^* e^{-\mathcal{H}_{t,\epsilon}(\mathbf{X}^*, \mathbf{W}^*; \mathbf{Y}_t, \mathbf{Y}_t', \Phi, \mathbf{V})} \ln \int dP_0(\mathbf{x}) \mathcal{D}\mathbf{w} e^{-\mathcal{H}_{t,\epsilon}(\mathbf{x}, \mathbf{w}; \mathbf{Y}_t, \mathbf{Y}_t', \Phi, \mathbf{V})}. \quad (172) $$

We will need the Hamiltonian $t$-derivative $\mathcal{H}'_{t,\epsilon}$ given by

$$ \mathcal{H}'_{t,\epsilon}(\mathbf{X}^*, \mathbf{W}^*; \mathbf{Y}_t, \mathbf{Y}_t', \Phi, \mathbf{V}) = -\sum_{\mu=1}^{m} \frac{dS_{t,\mu}}{dt} u'_{Y_{t,\mu}}(S_{t,\mu}) - \frac{r(t)}{2\sqrt{R_1(t)}} \sum_{i=1}^{n} X_i^* (Y'_{t,i} - \sqrt{R_1(t)} X_i^*). \quad (173) $$
The derivative of the interpolating free entropy thus reads, for $0 < t < 1$,

$$ \frac{df_{n,\epsilon}(t)}{dt} = -\underbrace{\frac{1}{n}\mathbb{E}[\mathcal{H}_{t,\epsilon}'(\mathbf{X}^*, \mathbf{W}^*; \mathbf{Y}_t, \mathbf{Y}_t', \mathbf{\Phi}, \mathbf{V}) \ln \mathcal{Z}_{t,\epsilon}]}_{T_1} - \underbrace{\frac{1}{n}\mathbb{E}\langle \mathcal{H}_{t,\epsilon}'(\mathbf{x}, \mathbf{w}; \mathbf{Y}_t, \mathbf{Y}_t', \mathbf{\Phi}, \mathbf{V}) \rangle_{n,t,\epsilon}}_{T_2} \quad (174) $$

where recall the definition of $\mathcal{Z}_{t,\epsilon} = \mathcal{Z}_{t,\epsilon}(\mathbf{Y}_t, \mathbf{Y}_t', \mathbf{\Phi}, \mathbf{V})$ given by (97).

Let us compute $T_1$. Let $1 \le \mu \le m$. Let us start with the following term

$$ \mathbb{E}\left[\frac{dS_{t,\mu}}{dt} u'_{Y_{t,\mu}}(S_{t,\mu}) \ln \mathcal{Z}_{t,\epsilon}\right] = \frac{1}{2}\mathbb{E}\left[\left(-\frac{[\mathbf{\Phi}\mathbf{X}^*]_{\mu}}{\sqrt{n(1-t)}} + \frac{q(t)}{\sqrt{R_2(t)}}V_{\mu} + \frac{\rho-q(t)}{\sqrt{\rho t - R_2(t) + 2s_n}}W_{\mu}^*\right)u'_{Y_{t,\mu}}(S_{t,\mu}) \ln \mathcal{Z}_{t,\epsilon}\right]. \quad (175) $$

Let us compute the first term of the right-hand side of the last identity. By Gaussian integration by parts w.r.t $\Phi_{\mu i}$ we obtain

$$ \begin{aligned} & \frac{1}{\sqrt{n(1-t)}}\mathbb{E}[[(\mathbf{\Phi}\mathbf{X}^*)_{\mu}u'_{Y_{t,\mu}}(S_{t,\mu}) \ln \mathcal{Z}_{t,\epsilon}]] \\ &= \frac{1}{\sqrt{n(1-t)}}\sum_{i=1}^{n}\mathbb{E}\left[\int d\mathbf{Y}_td\mathbf{Y}_t'e^{-\mathcal{H}_{t,\epsilon}(\mathbf{X}^*,\mathbf{W}^*;\mathbf{Y}_t,\mathbf{Y}_t',\mathbf{\Phi},\mathbf{V})}\Phi_{\mu i}X_i^*u'_{Y_{t,\mu}}(S_{t,\mu}) \ln \mathcal{Z}_{t,\epsilon}\right] \\ &= \frac{1}{n}\sum_{i=1}^{n}\left(\mathbb{E}[(X_i^*)^2(u''_{Y_{t,\mu}}(S_{t,\mu}) + u'_{Y_{t,\mu}}(S_{t,\mu})^2) \ln \mathcal{Z}_{t,\epsilon}] + \mathbb{E}\langle X_i^*x_iu'_{Y_{t,\mu}}(S_{t,\mu})u'_{Y_{t,\mu}}(s_{t,\mu})\rangle_{n,t,\epsilon}\right) \\ &= \mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}(X_i^*)^2\frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}\ln \mathcal{Z}_{t,\epsilon}\right] + \mathbb{E}\langle\frac{1}{n}\sum_{i=1}^{n}X_i^*x_iu'_{Y_{t,\mu}}(S_{t,\mu})u'_{Y_{t,\mu}}(s_{t,\mu})\rangle_{n,t,\epsilon}, \end{aligned} \quad (176) $$

where we used the identity

$$ u''_{Y_{t,\mu}}(x) + u'_{Y_{t,\mu}}(x)^2 = \frac{P''_{\text{out}}(Y_{t,\mu}|x)}{P_{\text{out}}(Y_{t,\mu}|x)}. \quad (177) $$

We now compute the second term of the right hand side of (175). Using again Gaussian integrations by parts but this time w.r.t $V_{\mu}$, $W_{\mu}^*$ is $\mathcal{N}(0, 1)$ as well as the previous formula, we obtain similarly

$$ \begin{aligned} & \mathbb{E}\left[\left(\frac{q(t)}{\sqrt{R_2(t)}}V_{\mu} + \frac{\rho-q(t)}{\sqrt{\rho t - R_2(t) + 2s_n}}W_{\mu}^*\right)u'_{Y_{t,\mu}}(S_{t,\mu}) \ln \mathcal{Z}_{t,\epsilon}\right] \\ &= \mathbb{E}\left[\int d\mathbf{Y}_td\mathbf{Y}_t'e^{-\mathcal{H}_{t,\epsilon}(\mathbf{X}^*,\mathbf{W}^*;\mathbf{Y}_t,\mathbf{Y}_t',\mathbf{\Phi},\mathbf{V})}\left(\frac{q(t)}{\sqrt{R_2(t)}}V_{\mu} + \frac{\rho-q(t)}{\sqrt{\rho t - R_2(t) + 2s_n}}W_{\mu}^*\right)u'_{Y_{t,\mu}}(S_{t,\mu}) \ln \mathcal{Z}_{t,\epsilon}\right] \\ &= \mathbb{E}\left[\rho\frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}\ln \mathcal{Z}_{t,\epsilon}\right] + \mathbb{E}\langle q(t)u'_{Y_{t,\mu}}(S_{t,\mu})u'_{Y_{t,\mu}}(s_{t,\mu})\rangle_{n,t,\epsilon}. \end{aligned} \quad (178) $$

Combining equations (175), (176) and (178) together, we have

$$ \begin{aligned} & -\mathbb{E}\left[\frac{dS_{t,\mu}}{dt} u'_{Y_{t,\mu}}(S_{t,\mu}) \ln \mathcal{Z}_{t,\epsilon}\right] \\ &= \frac{1}{2}\mathbb{E}\left[\frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}\left(\frac{1}{n}\sum_{i=1}^{n}(X_i^*)^2 - \rho\right) \ln \mathcal{Z}_{t,\epsilon}\right] + \frac{1}{2}\mathbb{E}\left\langle\left(\frac{1}{n}\sum_{i=1}^{n}X_i^*x_i - q(t)\right)u'_{Y_{t,\mu}}(S_{t,\mu})u'_{Y_{t,\mu}}(s_{t,\mu})\right\rangle_{n,t,\epsilon}. \end{aligned} $$

As seen from (173), (174) it remains to compute $\mathbb{E}[X_j^*(Y_{t,j}' - \sqrt{R_1(t)}X_j^*) \ln \mathcal{Z}_{t,\epsilon}]$. Recalling that for $1 \le j \le n$,
$Y'_{t,j} - \sqrt{R_1(t)}X_j^* = Z'_j$ and then using again a Gaussian integration by parts w.r.t $Z'_j \sim \mathcal{N}(0, 1)$ we obtain

$$
\begin{align}
\mathbb{E}[X_j^*(Y'_{t,j} - \sqrt{R_1(t)}X_j^*) \ln \mathcal{Z}_{t,\epsilon}] &= \mathbb{E}[X_j^* Z'_j \ln \mathcal{Z}_{t,\epsilon}] = \mathbb{E}[X_j^* Z'_j \ln \int dP_0(\mathbf{x}) \mathcal{D}\mathbf{w} e^{-\mathcal{H}_{t,\epsilon}(\mathbf{x},\mathbf{w};\mathbf{Y}_t,\mathbf{Y}'_t,\mathbf{\Phi},\mathbf{V})} \nonumber \\
&= \mathbb{E}[X_j^* Z'_j \ln \int dP_0(\mathbf{x}) \mathcal{D}\mathbf{w} \exp \left\{ \sum_{\mu=1}^m u_{Y_{t,\mu}}(s_{t,\mu}) - \frac{1}{2} \sum_{i=1}^n (\sqrt{R_1(t)}X_i^* + Z'_i - \sqrt{R_1(t)}x_i)^2 \right\}] \nonumber \\
&= -\mathbb{E}[X_j^* \langle \sqrt{R_1(t)}(X_j^* - x_j) + Z'_j \rangle_{n,t,\epsilon}] \nonumber \\
&= -\sqrt{R_1(t)}(\rho - \mathbb{E}\langle X_j^* x_j \rangle_{n,t,\epsilon}). \tag{179}
\end{align}
$$

Thus, by taking the sum,

$$
-\frac{r(t)}{2\sqrt{R_1(t)}} \mathbb{E} \left[ \frac{1}{n} \sum_{i=1}^{n} X_i^* (Y'_{t,i} - \sqrt{R_1(t)} X_i^*) \ln \mathcal{Z}_{t,\epsilon} \right] = \frac{r(t)\rho}{2} - \frac{r(t)}{2} \mathbb{E} \left\langle \frac{1}{n} \sum_{i=1}^{n} X_i^* x_i \right\rangle_{n,t,\epsilon}. \quad (180)
$$

Therefore, for all $t \in (0, 1)$,

$$
\begin{align}
T_1 = \frac{1}{2} \mathbb{E} \left[ \frac{1}{\sqrt{n}} \sum_{\mu=1}^{m} \frac{P_{\text{out}}''(Y_{t,\mu} | S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu} | S_{t,\mu})} \left( \frac{1}{\sqrt{n}} \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right) \frac{1}{n} \ln \mathcal{Z}_{t,\epsilon} \right] &+ \frac{r(t)\rho}{2} - \frac{r(t)q(t)}{2} \nonumber \\
&+ \frac{1}{2} \mathbb{E} \left\langle \left( \frac{1}{n} \sum_{\mu=1}^{m} u'_{Y_{t,\mu}}(S_{t,\mu}) u'_{Y_{t,\mu}}(s_{t,\mu}) - r(t) \right) \left( \frac{1}{n} \sum_{i=1}^{n} X_i^* x_i - q(t) \right) \right\rangle_{n,t,\epsilon}. \tag{181}
\end{align}
$$

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

$$
T_2 = \frac{1}{n} \mathbb{E} \langle \mathcal{H}_{t,\epsilon}'(\mathbf{x}, \mathbf{w}; \mathbf{Y}_t, \mathbf{Y}_t', \mathbf{\Phi}) \rangle_{n,t,\epsilon} = \frac{1}{n} \mathbb{E} \mathcal{H}_{t,\epsilon}'(\mathbf{X}^*, \mathbf{W}^*; \mathbf{Y}_t, \mathbf{Y}_t', \mathbf{\Phi}) = 0. \quad (182)
$$

For obtaining the Lemma, it remains to show that $A_{n,\epsilon}$ goes to 0 uniformly in $t \in [0, 1]$.

### A.5.2 Proof that $A_{n,\epsilon}$ vanishes as $n \to \infty$

We now consider the final step, that is showing that $A_{n,\epsilon}$ given by (171) vanishes in the $n \to \infty$ limit uniformly in $t \in [0, 1]$ under conditions (H1)-(H2)-(H3). First we show that

$$
\mathbb{E} \left[ \frac{1}{\sqrt{n}} \sum_{\mu=1}^{m} \frac{P_{\text{out}}''(Y_{t,\mu} | S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu} | S_{t,\mu})} \left( \frac{1}{\sqrt{n}} \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right) \right] = 0. \quad (183)
$$

Once this is done, we use the fact that $\frac{1}{n} \ln \mathcal{Z}_{t,\epsilon}$ concentrates around $f_{n,\epsilon}(t)$ to prove that $A_{n,\epsilon}$ converges to 0 as $n \to \infty$. We start by noticing the simple fact that for all $s \in \mathbb{R}$, $\int P_{\text{out}}''(y|s)dy = 0$. Consequently, for $\mu \in \{1, \dots, m\}$,

$$
\mathbb{E} \left[ \frac{P_{\text{out}}''(Y_{t,\mu} | S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu} | S_{t,\mu})} \middle| \mathbf{X}^*, \mathbf{s}_t \right] = \int dY_{t,\mu} P_{\text{out}}''(Y_{t,\mu} | S_{t,\mu}) = 0. \quad (184)
$$

Thus, using the “tower property” of the conditional expectation:

$$
\mathbb{E} \left[ \left( \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right) \sum_{\mu=1}^{m} \frac{P_{\text{out}}''(Y_{t,\mu} | S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu} | S_{t,\mu})} \right] = \mathbb{E} \left[ \left( \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right) \mathbb{E} \left[ \sum_{\mu=1}^{m} \frac{P_{\text{out}}''(Y_{t,\mu} | S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu} | S_{t,\mu})} \middle| \mathbf{X}^*, \mathbf{s}_t \right] \right] = 0
$$
which gives (183). We now show that $A_{n,\epsilon}$ goes to 0 uniformly in $t \in [0, 1]$ as $n \to \infty$. Using successively (183) and the Cauchy-Schwarz inequality, we have

$$ egin{aligned} |A_{n,\epsilon}| &= \left| \mathbb{E} \left[ \frac{1}{\sqrt{n}} \sum_{\mu=1}^{m} \frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})} \left( \frac{1}{\sqrt{n}} \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right) \left( \frac{1}{n} \ln \mathcal{Z}_{t,\epsilon} - f_{n,\epsilon}(t) \right) \right] \right| \\ &\le \mathbb{E} \left[ \left( \frac{1}{\sqrt{n}} \sum_{\mu=1}^{m} \frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})} \right)^2 \left( \frac{1}{\sqrt{n}} \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right)^2 \right]^{1/2} \mathbb{E} \left[ \left( \frac{1}{n} \ln \mathcal{Z}_{t,\epsilon} - f_{n,\epsilon}(t) \right)^2 \right]^{1/2} . \end{aligned} \quad (185) $$

Using again the “tower property” of conditional expectations

$$ egin{aligned} & \mathbb{E} \left[ \left( \sum_{\mu=1}^{m} \frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})} \right)^2 \left( \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right)^2 \right] \\ &= \mathbb{E} \left[ \left( \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right)^2 \mathbb{E} \left[ \left( \sum_{\mu=1}^{m} \frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})} \right)^2 \left| \mathbf{X}^*, \mathbf{S}_t \right. \right] \right]. \end{aligned} \quad (186) $$

Now, using the fact that conditionally on $\mathbf{S}_t$, the random variables $(\frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})})_{1\le\mu\le m}$ are i.i.d. and centered, we have

$$ \mathbb{E} \left[ \left( \sum_{\mu=1}^{m} \frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})} \right)^2 \left| \mathbf{X}^*, \mathbf{S}_t \right. \right] = \mathbb{E} \left[ \left( \sum_{\mu=1}^{m} \frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})} \right)^2 \left| \mathbf{S}_t \right. \right] = m \mathbb{E} \left[ \left( \frac{P''_{\text{out}}(Y_1|S_{t,1})}{P_{\text{out}}(Y_1|S_{t,1})} \right)^2 \left| \mathbf{S}_t \right. \right]. \quad (187) $$

Under condition (H2), it is not difficult to show that there exists a constant $C > 0$ such that

$$ \mathbb{E} \left[ \left( \frac{P''_{\text{out}}(Y_{t,1}|S_{t,1})}{P_{\text{out}}(Y_{t,1}|S_{t,1})} \right)^2 \left| \mathbf{S}_t \right. \right] \le C. \quad (188) $$

Combining now (188), (187) and (186) we obtain that

$$ \mathbb{E} \left[ \left( \sum_{\mu=1}^{m} \frac{P''_{\text{out}}(Y_{t,\mu}|S_{t,\mu})}{P_{\text{out}}(Y_{t,\mu}|S_{t,\mu})} \right)^2 \left( \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right)^2 \right] \le mC \mathbb{E} \left[ \left( \sum_{i=1}^{n} ((X_i^*)^2 - \rho) \right)^2 \right] = mnC \text{Var}((X_1^*)^2). $$

Going back to (185), therefore there exists a constant $C' > 0$ such that

$$ |A_{n,\epsilon}| \le C' \mathbb{E} \left[ \left( \frac{1}{n} \ln \mathcal{Z}_{t,\epsilon} - f_{n,\epsilon}(t) \right)^2 \right]^{1/2} . \quad (189) $$

By Theorem 6 we have $\mathbb{E}[(n^{-1} \ln \mathcal{Z}_{t,\epsilon} - f_{n,\epsilon}(t))^2] \to 0$ as $n \to \infty$ uniformly in $t \in [0, 1]$. Thus $A_{n,\epsilon}$ goes to 0 as $n \to \infty$ uniformly in $t \in [0, 1]$, $\epsilon$ and w.r.t. the choice of the interpolation functions. This ends the proof of Proposition 3.

## A.6 Boundedness of an overlap fluctuation

In this appendix we show that the “overlap fluctuation”

$$ \mathbb{E} \left\langle \left( \frac{1}{n} \sum_{\mu=1}^{m} u'_{Y_{t,\mu}}(S_{t,\mu}) u'_{Y_{t,\mu}}(s_{t,\mu}) - r_{\epsilon}(t) \right)^2 \right\rangle_{n,t,\epsilon} \le 2r_{\max}^2 + 2\mathbb{E} \left\langle \left( \frac{1}{n} \sum_{\mu=1}^{m} u'_{Y_{t,\mu}}(S_{t,\mu}) u'_{Y_{t,\mu}}(s_{t,\mu}) \right)^2 \right\rangle_{n,t,\epsilon} \quad (190) $$
is bounded uniformly in $t$ under hypothesis (H2) on $\varphi$. From the representation (22) (recall we consider $\Delta = 1$ in Sec. 4)

$$u_{Y_{t,\mu}}(s) = \ln P_{\text{out}}(Y_{t,\mu}|s) = \ln \int dP_A(\mathbf{a}_{\mu}) \frac{1}{\sqrt{2\pi}} e^{-\frac{1}{2}(Y_{t,\mu}-\varphi(s, \mathbf{a}_{\mu}))^2} \quad (191)$$

and thus

$$u'_{Y_{t,\mu}}(s) = \frac{\int dP_A(\mathbf{a}_{\mu})(Y_{t,\mu} - \varphi(s, \mathbf{a}_{\mu}))\varphi'(s, \mathbf{a}_{\mu})e^{-\frac{1}{2}(Y_{t,\mu}-\varphi(s, \mathbf{a}_{\mu}))^2}}{\int dP_A(\mathbf{a}_{\mu})e^{-\frac{1}{2}(Y_{t,\mu}-\varphi(s, \mathbf{a}_{\mu}))^2}} \quad (192)$$

where $\varphi'$ is the derivative w.r.t. the first argument. From (20) at $\Delta = 1$ we get $|Y_{t,\mu}| \le \sup |\varphi| + |Z_{\mu}|$, where the supremum is taken over both arguments of $\varphi$, and thus immediately obtain for all $s \in \mathbb{R}$

$$|u'_{Y_{t,\mu}}(s)| \le (2 \sup |\varphi| + |Z_{\mu}|) \sup |\varphi'|. \quad (193)$$

From (193) and (190) we see that it suffices to check that

$$\frac{m^2}{n^2} \mathbb{E} [((2 \sup |\varphi| + |Z_{\mu}|)^2 (\sup |\varphi'|)^2)] \le C(\varphi, \alpha)$$

where $C(\varphi, \alpha)$ is a constant depending only on $\varphi$ and $\alpha$. This is easily seen by expanding all squares and using that $m/n$ is bounded.

## A.7 Proof of Proposition 6

The continuity and differentiability properties of $F_n$ follow from the standard theorems of continuity and derivation under the integral sign. The domination hypotheses are easily verified because we are working under hypotheses (H1)-(H2).

The overlap $\mathbb{E}\langle Q \rangle_{n,t,\epsilon}$ is related to the minimum mean-square error by

$$\frac{1}{n}\text{MMSE}(\mathbf{X}^*|\mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{\Phi}) = \frac{1}{n}\mathbb{E}[\|\mathbf{X}^* - \mathbb{E}[\mathbf{X}^*|\mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{\Phi}]\|^2] = \frac{1}{n}\mathbb{E}[\|\mathbf{X}^* - \langle \mathbf{x} \rangle_{n,t,\epsilon}\|^2] = \rho - \mathbb{E}\langle Q \rangle_{n,t,\epsilon}.$$

Since the left hand side belongs to $[0, \rho]$, we obtain that $\mathbb{E}\langle Q \rangle_{n,t,\epsilon} \in [0, \rho]$.

It remains therefore to prove that MMSE($\mathbf{X}^*|\mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{\Phi}$) is separately non-increasing in $R_1$ and $R_2$. $R_1$ only appears in the definition of $\mathbf{Y}'_t$. Recall that $\mathbf{Y}'_t = \sqrt{R_1}\mathbf{X}^* + \mathbf{Z}'$, where $\mathbf{Z}'$ is a standard Gaussian vector, so MMSE($\mathbf{X}^*|\mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{\Phi}$) is obviously a non-increasing function of $R_1$.

$R_2$ only plays a role in $\mathbf{Y}_t \sim P_{\text{out}}(\cdot | \sqrt{(1-t)/n} \mathbf{\Phi} \mathbf{X}^* + \sqrt{R_2} \mathbf{V} + \sqrt{\rho t - R_2 + 2s_n} \mathbf{W}^*).$ Let $0 < r_2 \le r'_2 < \rho t$. Let $\mathbf{V}' \sim \mathcal{N}(0, \mathbf{I}_m)$, independently of everything else. Define

$$\tilde{\mathbf{Y}}_t \sim P_{\text{out}}\left(\cdot \left| \sqrt{\frac{1-t}{n}} \mathbf{\Phi} \mathbf{X}^* + \sqrt{r_2} \mathbf{V} + \sqrt{r'_2 - r_2} \mathbf{V}' + \sqrt{\rho t - r'_2 + 2s_n} \mathbf{W}^* \right)\right),$$

independently of everything else. Now notice that

$$\text{MMSE}(\mathbf{X}^*|\mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{\Phi})|_{R_2=r_2} = \text{MMSE}(\mathbf{X}^*|\tilde{\mathbf{Y}}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{\Phi}),$$

$$\text{MMSE}(\mathbf{X}^*|\mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{\Phi})|_{R_2=r'_2} = \text{MMSE}(\mathbf{X}^*|\tilde{\mathbf{Y}}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{V}', \mathbf{\Phi}),$$

which implies of course that $\text{MMSE}(\mathbf{X}^*|\mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{\Phi})|_{R_2=r_2} \ge \text{MMSE}(\mathbf{X}^*|\mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{\Phi})|_{R_2=r'_2}$. We have proved that $\text{MMSE}(\mathbf{X}^*|\mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{V}, \mathbf{\Phi})$ is a non-increasing function of $R_2$.
# Appendix B: Some properties of the scalar channels

## B.1 The additive Gaussian scalar channel

We recall some properties (see [54] and [97] for proofs) of the free entropy of the first scalar channel (36).

**Proposition 17.** Let $X_0 \sim P_0$ be a real random variable with finite second moment. Let $r \ge 0$ and $Y_0 = \sqrt{r}X_0 + Z_0$, where $Z_0 \sim \mathcal{N}(0, 1)$ is independent from $X_0$. Then the function

$$ \psi_{P_0} : r \mapsto \mathbb{E} \ln \int dP_0(x) e^{\sqrt{r} Y_0 x - r x^2 / 2} $$

is convex, differentiable, non-decreasing and $\frac{1}{2}\mathbb{E}[X_0^2]$-Lipschitz on $\mathbb{R}_+$. Moreover, $\psi_{P_0}$ is strictly convex, if $P_0$ is not a Dirac measure.

## B.2 The non-linear scalar channel

We prove here some properties of the free entropy of the second scalar channel (39), where $V, W^* \stackrel{\text{iid}}{\sim} \mathcal{N}(0, 1)$ and

$$ Y^{(q)} \sim P_{\text{out}}\left(\cdot \mid \sqrt{q}V + \sqrt{\rho-q}W^*\right). \qquad (194) $$

In this channel, the statistician observes $V$ and $Y^{(q)}$ and wants to recover $W^*$. Recall that by definition $\mathcal{I}_{P_{\text{out}}}(q) = I(W^*; Y^{(q)}|V) = \Psi_{P_{\text{out}}}(\rho) - \Psi_{P_{\text{out}}}(q)$ so the properties we will prove on $\Psi_{P_{\text{out}}}$ can be directly translated for $\mathcal{I}_{P_{\text{out}}}$, and vice-versa.

**Proposition 18.** Suppose that for all $x \in \mathbb{R}$, $P_{\text{out}}(\cdot|x)$ is the law of $\varphi(x, A) + \sqrt{\Delta}Z$ where $\Delta > 0$, $\varphi: \mathbb{R} \times \mathbb{R}^{k_A} \to \mathbb{R}$ is a measurable function and $(Z, A) \sim \mathcal{N}(0, 1) \otimes P_A$, for some probability distribution $P_A$ over $\mathbb{R}^{k_A}$. In that case $P_{\text{out}}$ admits a density given by

$$ P_{\text{out}}(y|x) = \frac{1}{\sqrt{2\pi\Delta}} \int dP_A(\mathbf{a}) e^{-\frac{1}{2\Delta}(y-\varphi(x, \mathbf{a}))^2} $$

Assume that $\varphi$ is bounded and $C^2$ with respect to its first coordinate, with bounded first and second derivatives. Then $q \mapsto \Psi_{P_{\text{out}}}(q)$ is convex, $C^2$ and non-decreasing on $[0, \rho]$.

*Proof.* Let $V, W^* \stackrel{\text{iid}}{\sim} \mathcal{N}(0, 1)$ and $Y^{(q)}$ be the output of the scalar channel given by (194). Then for all $q \in [0, \rho]$,

$$ \Psi_{P_{\text{out}}}(q) = \mathbb{E} \ln \int dw \frac{e^{-\frac{w^2}{2}}}{\sqrt{2\pi}} P_{\text{out}}(Y^{(q)} | \sqrt{q}V + \sqrt{\rho-q}w) $$

Under the hypotheses we made on $\varphi$, 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 $\Psi_{P_{\text{out}}}$ is continuous on $[0, \rho]$.

We compute now the first derivative. Recall that $\langle - \rangle_{\text{sc}}$, defined in (72), denotes the posterior distribution of $W^*$ given $Y^{(q)}$. We will use the notation $u_y(x) = \ln P_{\text{out}}(y|x)$. For $q \in (0, \rho)$ we have

$$ \begin{aligned} \Psi'_{P_{\text{out}}}(q) &= \frac{1}{2} \mathbb{E} \langle u'_{Y^{(q)}}(\sqrt{q}V + \sqrt{\rho-q}w) u'_{Y^{(q)}}(\sqrt{q}V + \sqrt{\rho-q}W^*) \rangle_{\text{sc}} \\ &= \frac{1}{2} \mathbb{E} \langle u'_{Y^{(q)}}(\sqrt{q}V + \sqrt{\rho-q}w) \rangle_{\text{sc}}^2 \ge 0, \end{aligned} $$

where $w \sim \langle - \rangle_{\text{sc}}$, independently of everything else. $\Psi_{P_{\text{out}}}$ is therefore non-decreasing. Using the boundedness assumption on $\varphi$ and its derivatives, it is not difficult to check that $\Psi'_{P_{\text{out}}}$ is indeed bounded.
We will now compute $\Psi''_{P_{\text{out}}}$. To lighten the notations, we write $u'(w)$ for $u'_{Y(q)}(\sqrt{q}V + \sqrt{\rho-q}w)$. We compute

$$
\begin{align}
\partial_q \mathbb{E} \langle u'(w) u'(W^*) \rangle_{\text{sc}} &= \mathbb{E} \left[ \left( \frac{1}{2\sqrt{q}} V - \frac{1}{2\sqrt{\rho-q}} W^* \right) u'(W^*) \langle u'(w) u'(W^*) \rangle_{\text{sc}} \right] \tag{A} \\
&\quad + 2\mathbb{E} \left\langle \left( \frac{1}{2\sqrt{q}} V - \frac{1}{2\sqrt{\rho-q}} W^* \right) u''(W^*) u'(w) \right\rangle_{\text{sc}} \tag{B} \\
&\quad + \mathbb{E} \left\langle \left( \frac{1}{2\sqrt{q}} V - \frac{1}{2\sqrt{\rho-q}} W^* \right) u'(W^*)^2 u'(w) \right\rangle_{\text{sc}} \tag{C} \\
&\quad - \mathbb{E} \langle u'(W^*) u'(w) \rangle_{\text{sc}} \left\langle \left( \frac{1}{2\sqrt{q}} V - \frac{1}{2\sqrt{\rho-q}} w \right) u'(w) \right\rangle_{\text{sc}} \tag{D}
\end{align}
$$

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

$$
(A) = \frac{1}{2} \mathbb{E} \left[ u'(W^*) \langle u'(W^*) u''(w) \rangle_{\text{sc}} \right] + \frac{1}{2} \mathbb{E} \left[ u'(W^*) \langle u'(W^*) u'(w)^2 \rangle_{\text{sc}} \right] \\
\qquad - \frac{1}{2} \mathbb{E} \left[ u'(W^*) \langle u'(W^*) u'(w) \rangle_{\text{sc}} \langle u'(w) \rangle_{\text{sc}} \right] \tag{196}
$$

$$
(B) = \mathbb{E}\langle u''(W^*)u''(w) \rangle_{\text{sc}} + \mathbb{E}\langle u''(W^*)u'(w)^2 \rangle_{\text{sc}} - \mathbb{E}\langle u''(W^*)u'(w) \rangle_{\text{sc}}\langle u'(w) \rangle_{\text{sc}} \quad (197)
$$

$$
\begin{align}
(D) &= -\mathbb{E}\left\langle \left(\frac{1}{2\sqrt{q}}V - \frac{1}{2\sqrt{\rho-q}}W^*\right)u'(W^*)u'(w^{(1)})u'(w^{(2)})\right\rangle_{\text{sc}} \nonumber \\
&= -\mathbb{E}\langle u'(W^*)u''(w^{(1)})u'(w^{(2)})\rangle_{\text{sc}} - \mathbb{E}\langle u'(W^*)u'(w^{(1)})^2u'(w^{(2)})\rangle_{\text{sc}} \nonumber \\
&\quad + \mathbb{E}\langle u'(W^*)u'(w^{(1)})u'(w^{(2)})\rangle_{\text{sc}}\langle u'(w)\rangle_{\text{sc}} \tag{198}
\end{align}
$$

We now replace (196), (197) and (198) in (195):

$$
\begin{align*}
2\Psi''_{P_{\text{out}}}(q) ={}& \mathbb{E}\langle u'(W^*)^2 u''(w) \rangle_{\text{sc}} + \mathbb{E}\langle u'(W^*)^2 u'(w)^2 \rangle_{\text{sc}} - \mathbb{E}\langle u'(W^*)^2 u'(w^{(1)}) u'(w^{(2)}) \rangle_{\text{sc}} \\
& + \mathbb{E}\langle u''(W^*) u''(w) \rangle_{\text{sc}} + \mathbb{E}\langle u''(W^*) u'(w)^2 \rangle_{\text{sc}} - \mathbb{E}\langle u''(W^*) u'(w^{(1)}) u'(w^{(2)}) \rangle_{\text{sc}} \\
& - \mathbb{E}\langle u'(W^*) u''(w^{(1)}) u'(w^{(2)}) \rangle_{\text{sc}} - \mathbb{E}\langle u'(W^*) u'(w^{(1)})^2 u'(w^{(2)}) \rangle_{\text{sc}} + \mathbb{E}\langle u'(w) \rangle_{\text{sc}}^4.
\end{align*}
$$

Using the identity $u''_Y(x) + u'_Y(x)^2 = \frac{P''_{\text{out}}(Y|x)}{P_{\text{out}}(Y|x)}$, this factorizes and gives

$$
\Psi''_{P_{\text{out}}}(q) = \frac{1}{2} \mathbb{E} \left[ \left( \left\langle \frac{P''_{\text{out}}(Y|\sqrt{q}V + \sqrt{\rho-q}w)}{P_{\text{out}}(Y|\sqrt{q}V + \sqrt{\rho-q}w)} \right\rangle_{\text{sc}} - \left\langle u'_{Y(q)}(\sqrt{q}V + \sqrt{\rho-q}w) \right\rangle_{\text{sc}}^2 \right)^2 \right] \ge 0. \quad (199)
$$

$\Psi_{P_{\text{out}}}$ is thus convex on $[0, \rho]$. It is not difficult to verify (by standard arguments of continuity under the integral) that $\Psi''_{P_{\text{out}}}$ is continuous on $[0, \rho]$, which gives that $\Psi_{P_{\text{out}}}$ is $C^2$ on its domain. $\square$

**Proposition 19.** Suppose that for all $x \in \mathbb{R}$, $P_{\text{out}}(\cdot | x)$ is the law of $\varphi(x, A) + \sqrt{\Delta}Z$ where $\varphi : \mathbb{R} \times \mathbb{R}^{k_A} \to \mathbb{R}$ is a measurable function and $(Z, A) \sim \mathcal{N}(0, 1) \otimes P_A$, for some probability distribution $P_A$ over $\mathbb{R}^{k_A}$. Assume also that

$$
\mathbb{E}[\varphi(\sqrt{\rho}Z, A)^2] < \infty, \qquad (200)
$$

and that we are in one of the following cases:

(i) $\Delta > 0$.

(ii) $\Delta = 0$ and $\varphi$ takes values in $\mathbb{N}$.

Then $q \mapsto \Psi_{P_{\text{out}}}(q)$ is continuous, convex and non-decreasing over $[0, \rho]$.
Notice that (200) is for instance verified under hypotheses (h1)-(h2)-(h3)-(h4), see Proposition 16.

*Proof.* We deduce Proposition 19 from Proposition 18 above by an approximation procedure. Since $\Psi_{P_{\text{out}}} = \Psi_{P_{\text{out}}} (\rho) - \mathcal{I}_{P_{\text{out}}}$, we will work with the mutual information $\mathcal{I}_{P_{\text{out}}}$. Let us define $U^{(q)} = \varphi(\sqrt{q}V + \sqrt{\rho-q}W^*, A)$ and $Y^{(q)} = U^{(q)} + \sqrt{\Delta}Z$.

We start by proving Proposition 19 under the assumption (i). Let $\epsilon > 0$. By density of the $C^\infty$ functions with compact support in $L^2$ (see for instance Corollary 4.2.2 from [98]), one can find a $C^\infty$ function $\hat{\varphi}$ with compact support, such that

$$ \mathbb{E} \left[ \left( \varphi(\sqrt{\rho} Z, A) - \hat{\varphi}(\sqrt{\rho} Z, A) \right)^2 \right] \le \epsilon^2. $$

Let us write $\hat{U}^{(q)} = \hat{\varphi}(\sqrt{q}V + \sqrt{\rho-q}W^*, A)$ and $\hat{Y}^{(q)} = \hat{U} + \sqrt{\Delta}Z$. We have by the chain rule for the mutual information

$$ \begin{aligned} I(U^{(q)}; Y^{(q)}|V) &= I(W^*, U^{(q)}; Y^{(q)}|V) \\ &= I(U^{(q)}; Y^{(q)}|V, W^*) + I(W^*; Y^{(q)}|V) = I(U^{(q)}; Y^{(q)}|V, W^*) + \mathcal{I}_{P_{\text{out}}}(q) \end{aligned} \quad (201) $$

and similarly, $\mathcal{I}_{\hat{P}_{\text{out}}}(q) = I(\hat{U}^{(q)}; \hat{Y}^{(q)}|V) - I(\hat{U}^{(q)}; \hat{Y}^{(q)}|V, W^*)$. By Proposition 14, there exists a constant $C > 0$ such that

$$ |I(\hat{U}^{(q)}; \hat{Y}^{(q)}|V) - I(U^{(q)}; Y^{(q)}|V)| \le C\epsilon \quad \text{and} \quad |I(\hat{U}^{(q)}; \hat{Y}^{(q)}|V, W^*) - I(U^{(q)}; Y^{(q)}|V, W^*)| \le C\epsilon. $$

We get that for all $q \in [0, \rho]$, $|\mathcal{I}_{P_{\text{out}}}(q) - \mathcal{I}_{\hat{P}_{\text{out}}}(q)| \le C\epsilon$. The function $\mathcal{I}_{P_{\text{out}}}$ can therefore be uniformly approximated by continuous, concave, non-increasing functions on $[0, \rho]: \mathcal{I}_{P_{\text{out}}}$ is therefore continuous, concave and non-increasing.

Let us now prove Proposition 19 under the assumption (ii). Under this assumption we have $\mathcal{I}_{P_{\text{out}}}(q) = I(W^*; U^{(q)}|V)$ and by the case (i) we know that the function $i_\Delta(q) = I(W^*; U^{(q)} + \sqrt{\Delta}Z|V)$ is concave and non-increasing for all $\Delta > 0$. By Corollary 7 we obtain that for all $q \in [0, \rho]$ and all $\Delta \in (0, 1]$ we have

$$ |\mathcal{I}_{P_{\text{out}}}(q) - i_{\Delta}(q)| \le 100e^{-1/(16\Delta)}, $$

which proves (by uniform approximation) that $\mathcal{I}_{P_{\text{out}}}$ is continuous, concave and non-increasing. $\square$

**Proposition 20.** Under the same hypotheses than Proposition 19 above, $\Psi_{\text{out}}$ is differentiable over $[0, \rho)$ and for all $q \in [0, \rho)$

$$ \Psi'_{P_{\text{out}}}(q) = \frac{1}{2(\rho-q)} \mathbb{E} \langle w \rangle_{\text{sc}}^2, $$

where we recall that $\langle - \rangle_{\text{sc}}$ is defined by (72).

*Proof.* The fact that $\Psi_{P_{\text{out}}}$ is differentiable on $[0, \rho)$ follows from differentiation under the expectation sign. In order to see it, we define $X = \sqrt{q}V + \sqrt{\rho-q}W^*$. Then, for all $q \in [0, \rho)$:

$$ \Psi_{P_{\text{out}}}(q) = \mathbb{E} \int dX \frac{1}{\sqrt{2\pi(\rho-q)}} e^{-\frac{(X-\sqrt{q}V)^2}{2(\rho-q)}} \int dY P_{\text{out}}(Y|X) \ln \int dx \frac{1}{\sqrt{2\pi(\rho-q)}} e^{-\frac{(x-\sqrt{q}V)^2}{2(\rho-q)}} P_{\text{out}}(Y|x). \quad (202) $$

We are now in a good setting to differentiate under the expectation sign. We have for all $q \in (0, \rho)$,

$$ \frac{\partial}{\partial q} \left[ \frac{1}{\sqrt{\rho-q}} e^{-\frac{(X-\sqrt{q}V)^2}{2(\rho-q)}} \right] = \frac{1}{2\sqrt{\rho-q}} \left( \frac{1}{\rho-q} - \frac{(X-\sqrt{q}V)^2}{(\rho-q)^2} + \frac{V(X-\sqrt{q}V)}{\sqrt{q}(\rho-q)} \right) e^{-\frac{(X-\sqrt{q}V)^2}{2(\rho-q)}}. \quad (203) $$
Thus

$$ \Psi'_{P_{\text{out}}}(q) = \frac{1}{2} \mathbb{E} \left[ \left( \frac{1}{\rho - q} - \frac{(X - \sqrt{q} V)^2}{(\rho - q)^2} + \frac{V(X - \sqrt{q} V)}{\sqrt{q} (\rho - q)} \right) \ln \int dx \frac{1}{\sqrt{2\pi(\rho - q)}} e^{-\frac{(x - \sqrt{q} V)^2}{2(\rho - q)}} P_{\text{out}}(Y|x) \right] \\ + \frac{1}{2} \mathbb{E} \left\langle \frac{1}{\rho - q} - \frac{(x - \sqrt{q} V)^2}{(\rho - q)^2} + \frac{V(x - \sqrt{q} V)}{\sqrt{q} (\rho - q)} \right\rangle_{\text{sc}} $$

where the Gibbs brackets $\langle - \rangle_{sc}$ denotes the expectation with respect to $x \sim P(X|Y^{(q)}, V)$. The second term of the sum above is equal to zero. Indeed by the Nishimori identity (Proposition 12):

$$ \mathbb{E} \left\langle \frac{1}{\rho - q} - \frac{(x - \sqrt{q} V)^2}{(\rho - q)^2} + \frac{V(x - \sqrt{q} V)}{\sqrt{q} (\rho - q)} \right\rangle_{\text{sc}} = \mathbb{E} \left[ \frac{1}{\rho - q} - \frac{(X - \sqrt{q} V)^2}{(\rho - q)^2} + \frac{V(X - \sqrt{q} V)}{\sqrt{q} (\rho - q)} \right] \\ = \frac{1}{\rho - q} \mathbb{E} [1 - (W^*)^2] = 0. $$

We now compute, by Gaussian integration by parts with respect to $V \sim \mathcal{N}(0, 1)$:

$$ \mathbb{E} \left[ \frac{V(X - \sqrt{q} V)}{\sqrt{q} (\rho - q)} \ln \int dx \frac{1}{\sqrt{2\pi(\rho - q)}} e^{-\frac{(x - \sqrt{q} V)^2}{2(\rho - q)}} P_{\text{out}}(Y^{(q)}|x) \right] \\ = \mathbb{E} \left[ \frac{-1}{\rho - q} \ln \int dx \frac{e^{-\frac{(x - \sqrt{q} V)^2}{2(\rho - q)}}}{\sqrt{2\pi(\rho - q)}} P_{\text{out}}(Y^{(q)}|x) \right] + \mathbb{E} \left[ \frac{(X - \sqrt{q} V)^2}{(\rho - q)^2} \ln \int dx \frac{e^{-\frac{(x - \sqrt{q} V)^2}{2(\rho - q)}}}{\sqrt{2\pi(\rho - q)}} P_{\text{out}}(Y^{(q)}|x) \right] \\ + \mathbb{E} \left\langle \frac{(X - \sqrt{q} V)(x - \sqrt{q} V)}{(\rho - q)^2} \right\rangle_{\text{sc}}. $$

Bringing all together, we conclude:

$$ \Psi'_{P_{\text{out}}}(q) = \frac{1}{2} \mathbb{E} \left\langle \frac{(X - \sqrt{q} V)(x - \sqrt{q} V)}{(\rho - q)^2} \right\rangle_{\text{sc}} = \frac{1}{2(\rho - q)} \mathbb{E} \langle w \rangle_{\text{sc}}^2. $$

This derivative is continuous at $q = 0$ thus $\Psi_{P_{\text{out}}}$ is differentiable at $q = 0$ with derivative given by the same expression. $\square$

**Proposition 21.** Assume that the hypotheses of Proposition 19 hold and suppose also that the kernel $P_{\text{out}}$ is informative. Then $\Psi_{P_{\text{out}}}$ is strictly increasing on $[0, \rho]$.

*Proof.* Let us suppose that $\Psi_{P_{\text{out}}}$ is not strictly increasing on $[0, \rho]$. There exists thus $q \in (0, \rho)$ such that $\Psi'_{P_{\text{out}}}(q) = 0$. This means that $\langle w \rangle_{\text{sc}} = 0$ almost surely and therefore that

$$ \int_{\mathbb{R}} P_{\text{out}}(Y^{(q)} | \sqrt{q} V + \sqrt{\rho - q} w) w e^{-w^2/2} dw = 0 $$

almost-surely. Let us write $\sigma = \sqrt{\rho - q}$. Consequently,

$$ \int_{\mathbb{R}} P_{\text{out}}(y | v + \sigma w) w e^{-w^2/2} dw = 0 \qquad (204) $$

for almost all $y$ in $\mathbb{R}$ (if we are under assumption (i)) or all $y \in \mathbb{N}$ (under assumption (ii)) and almost all $v \in \mathbb{R}$. We will now use the following lemma:
**Lemma 16.** Let $Z \sim \mathcal{N}(0, 1)$ and let $f: \mathbb{R} \to \mathbb{R}$ be a bounded function. Suppose that for almost all $v \in \mathbb{R}$,

$$ \mathbb{E}[Zf(v+Z)] = 0. $$

Then, there exists a constant $C \in \mathbb{R}$ such that $f(v) = C$ for almost every $v$.

*Proof.* Let us define the function

$$ h: t \mapsto \mathbb{E}[f(Z-t)] = \frac{1}{\sqrt{2\pi}} \int f(x)e^{-(x+t)^2/2}dx. $$

We have $h'(t) = \frac{-1}{\sqrt{2\pi}} \int f(x)(x+t)e^{-(x+t)^2/2}dx = -\mathbb{E}[Zf(Z-t)] = 0$ and therefore $h$ is equal to some constant $C \in \mathbb{R}$. We are going to show that $f = C$ almost everywhere. Without loss of generality we can assume that $C = 0$, otherwise it suffices to consider the function $\tilde{f} = f - C$. Now we have for all $n \ge 0$, $t \in \mathbb{R}$

$$ 0 = h^{(n)}(t) = \frac{1}{\sqrt{2\pi}} \int f(x) \frac{\partial}{\partial t} e^{-(x+t)^2/2} dx = \frac{1}{\sqrt{2\pi}} \int f(x) (-1)^n H_n(x+t) e^{-(x+t)^2/2} dx, $$

where $H_n$ is $n^{\text{th}}$ Hermite polynomial, defined as $H_n(x) = (-1)^n e^{x^2/2} \frac{d^n}{dx^n} e^{-x^2/2}$. Therefore, for all $n \ge 0$,

$$ \int f(x)H_n(x)e^{-x^2/2}dx = 0, $$

which implies that $f = 0$ almost everywhere since the Hermite functions form an orthonormal basis of $L^2(\mathbb{R})$. $\square$

We apply now Lemma 16 to (204) where the function $f$ is given by $f(x) = P_{\text{out}}(y|\sigma x)$. We thus obtain that for almost every $y$, $P_{\text{out}}(y|\cdot)$ is almost everywhere equal to a constant. Under assumption (ii), we get that for all $y \in \mathbb{N}$, $P_{\text{out}}(y|\cdot)$ is almost everywhere equal to a constant: this contradicts the hypothesis that $P_{\text{out}}$ is informative.

If now assumption (i) holds, then by (22) the density function $P_{\text{out}}(\cdot|x)$ is continuous on $\mathbb{R}$ for all $x \in \mathbb{R}$. Let us fix $y \in \mathbb{R}$. We are going to show that $P_{\text{out}}(y|\cdot)$ is almost everywhere equal to a constant $C_y$. Given what we just showed, we can construct a sequence $(y_n)_n \in \mathbb{R}^\mathbb{N}$ that converges to $y$ such that for all $n \ge 0$, there exists $E_n \subset \mathbb{R}$ with full Lebesgue's measure and $C_n \in \mathbb{R}$ such that for all $x \in E_n$,

$$ P_{\text{out}}(y_n|x) = C_n. $$

Let us define $E = \cap_{n \ge 0} E_n$. $E$ has therefore full Lebesgue's measure. Let now $x_1, x_2 \in E$. By continuity of $P_{\text{out}}(\cdot|x_i)$, we get

$$ P_{\text{out}}(y_n|x_i) \xrightarrow{n \to \infty} P_{\text{out}}(y|x_i), \quad \text{for } i = 1, 2. $$

Since we know that for all $n \ge 0$ that $P_{\text{out}}(y_n|x_1) = C_n = P_{\text{out}}(y_n|x_2)$, we deduce that $P_{\text{out}}(y|x_1) = P_{\text{out}}(y|x_2)$. This proves that $P_{\text{out}}(y|\cdot)$ is almost everywhere equal to a constant $C_y$ and contradicts the fact that $P_{\text{out}}$ is informative. $\square$

We turn now our attention to the study of the function:

$$ \mathcal{E}_f: \begin{array}{c} \begin{bmatrix} 0, \rho \end{bmatrix} \rightarrow \mathbb{R}_+ \\ q \mapsto \mathbb{E}[(f(Y^{(q)}) - \mathbb{E}[f(Y^{(q)})|V])^2] \end{array} \qquad (205) $$
where $f: \mathbb{R} \to \mathbb{R}$ is a continuous bounded function. We will prove that $\mathcal{E}_f$ is continuous (Proposition 22) and strictly decreasing (Proposition 23) under the following hypotheses.

(a) For all $x \in \mathbb{R}$, $P_{\text{out}}(\cdot|x)$ is the law of $\varphi(x, \mathbf{A}) + \sqrt{\Delta} Z$ where $\varphi: \mathbb{R} \times \mathbb{R}^{k_A} \to \mathbb{R}$ is a measurable function and $(Z, \mathbf{A}) \sim \mathcal{N}(0, 1) \otimes P_A$, for some probability distribution $P_A$ over $\mathbb{R}^{k_A}$.

(b) For almost all $a \in \mathbb{R}^{k_A}$ (w.r.t. $P_A$), $\varphi(\cdot, a)$ is continuous almost everywhere.

We suppose also that we are in one of the following cases:

(i) $\Delta > 0$.

(ii) $\Delta = 0$ and $\varphi$ takes values in $\mathbb{N}$.

**Proposition 22.** Under the hypotheses presented above, $\mathcal{E}_f$ is continuous on $[0, \rho]$.

*Proof.* Consider expression (62): The first term does not depend on $q$ and the second one is continuous by Lebesgue's convergence theorem. $\square$

**Proposition 23.** Assume that the hypotheses of Proposition 22 hold. Suppose that $x \mapsto \int f(y) P_{\text{out}}(y|x) dy$ is not almost-everywhere equal to a constant. Then $\mathcal{E}_f$ is strictly decreasing on $[0, \rho]$.

*Proof.* $\mathcal{E}_f(q) = \mathbb{E}[f(Y^{(q)})^2] - \mathbb{E}[\mathbb{E}[f(Y^{(q)})|V]^2]$. Since the first term does not depend on $q$, it suffices to show that $H: q \mapsto \mathbb{E}[\mathbb{E}[f(Y^{(q)})|V]^2]$ is strictly increasing on $[0, \rho]$. We have for $q \in (0, \rho)$:

$$ \mathbb{E}[f(Y^{(q)})|V] = \iint f(y) \frac{e^{-w^2/2}}{\sqrt{2\pi}} P_{\text{out}}(y|\sqrt{q}V + \sqrt{\rho-q}w) dydw = \iint f(y) \frac{e^{-\frac{(x-\sqrt{q}V)^2}{2(\rho-q)}}}{\sqrt{2\pi(\rho-q)}} P_{\text{out}}(y|x) dydx. $$

So we have, using (203):

$$ \begin{aligned} \frac{\partial}{\partial q} \mathbb{E}[f(Y^{(q)})|V] &= \iint \frac{f(y)}{2} \left( \frac{1}{\rho-q} - \frac{(x-\sqrt{q}V)^2}{(\rho-q)^2} + \frac{V(x-\sqrt{q}V)}{\sqrt{q}(\rho-q)} \right) \frac{e^{-\frac{(x-\sqrt{q}V)^2}{2(\rho-q)}}}{\sqrt{2\pi(\rho-q)}} P_{\text{out}}(y|x) dydw \\ &= \frac{1}{2(\rho-q)} \mathbb{E} \left[ f(Y^{(q)}) \left( 1 - W^{*2} + \frac{\sqrt{\rho-q}VW^{*}}{\sqrt{q}} \right) \middle| V \right]. \end{aligned} $$

We obtain

$$ H'(q) = \frac{1}{\rho-q} \mathbb{E} \left[ \mathbb{E}[f(Y^{(q)})|V] \mathbb{E} \left[ f(Y^{(q)}) \left( 1 - W^{*2} + \frac{\sqrt{\rho-q}VW^{*}}{\sqrt{q}} \right) \middle| V \right] \right]. \quad (206) $$

We compute by Gaussian integration by parts:

$$ \begin{aligned} \mathbb{E} \left[ \mathbb{E}[f(Y^{(q)})|V] \mathbb{E} \left[ f(Y^{(q)}) V W^* \middle| V \right] \right] &= \mathbb{E} \left[ V \mathbb{E}[f(Y^{(q)})|V] \mathbb{E} \left[ f(Y^{(q)}) W^* \middle| V \right] \right] \\ &= \mathbb{E} \left[ \frac{\partial}{\partial V} \mathbb{E}[f(Y^{(q)})|V] \mathbb{E} \left[ f(Y^{(q)}) W^* \middle| V \right] \right] + \mathbb{E} \left[ \mathbb{E}[f(Y^{(q)})|V] \frac{\partial}{\partial V} \mathbb{E} \left[ f(Y^{(q)}) W^* \middle| V \right] \right]. \end{aligned} \quad (207) $$
We compute successively

$$
\begin{align}
\frac{\partial}{\partial V} \mathbb{E}[f(Y^{(q)})|V] &= \frac{\partial}{\partial V} \iint f(y) \frac{e^{-\frac{(x-\sqrt{q}V)^2}{2(\rho-q)}}}{\sqrt{2\pi(\rho-q)}} P_{\text{out}}(y|x)dydx \nonumber \\
&= \iint f(y) \frac{\sqrt{q}(x-\sqrt{q}V)}{\rho-q} \frac{e^{-\frac{(x-\sqrt{q}V)^2}{2(\rho-q)}}}{\sqrt{2\pi(\rho-q)}} P_{\text{out}}(y|x)dydx = \frac{\sqrt{q}}{\sqrt{\rho-q}} \mathbb{E}[f(Y^{(q)})W^*|V]. \tag{208}
\end{align}
$$

$$
\begin{align}
\frac{\partial}{\partial V} \mathbb{E}[f(Y^{(q)})W^*|V] &= \frac{\partial}{\partial V} \iint f(y) \frac{x - \sqrt{q} V}{\sqrt{\rho - q}} \frac{e^{-\frac{(x-\sqrt{q}V)^2}{2(\rho-q)}}}{\sqrt{2\pi(\rho-q)}} P_{\text{out}}(y|x)dydx \nonumber \\
&= \iint f(y) \left( \frac{-\sqrt{q}}{\sqrt{\rho-q}} + \frac{\sqrt{q}(x-\sqrt{q}V)^2}{(\rho-q)^{3/2}} \right) \frac{e^{-\frac{(x-\sqrt{q}V)^2}{2(\rho-q)}}}{\sqrt{2\pi(\rho-q)}} P_{\text{out}}(y|x)dydx \nonumber \\
&= \frac{\sqrt{q}}{\sqrt{\rho-q}} \mathbb{E}[f(Y^{(q)})(-1+W^{*2})|V]. \tag{209}
\end{align}
$$

By plugging (207)-(208)-(209) back in (206) we get:

$$
H'(q) = \frac{1}{\rho - q} \mathbb{E} \left[ \mathbb{E} \left[ f(Y^{(q)}) W^* | V \right]^2 \right] \geq 0.
$$

Let us suppose now that $H$ is not strictly increasing on $[0, \rho]$. This means that we can find $q \in (0, \rho)$ such that $H'(q) = 0$ and therefore $\mathbb{E}[f(Y^{(q)})W^*|V] = 0$ almost-surely. This gives that for almost all $v \in \mathbb{R}$,

$$
\mathbb{E} \left[ W \int f(y) P_{\text{out}}(y | \sqrt{q} v + \sqrt{\rho - q} W) dy \right] = 0,
$$

where $\mathbb{E}$ is the expectation with respect to $W \sim \mathcal{N}(0, 1)$. Lemma 16 gives then that the function $x \mapsto \int f(y) P_{\text{out}}(y|x) dy$ is almost everywhere equal to a constant: we obtain a contradiction. We conclude that $H$ is strictly increasing on $[0, \rho]$ and thus $\mathcal{E}_f$ is strictly decreasing on $[0, \rho]$. $\square$

**Proposition 24.** Assume that the hypotheses of Proposition 22 hold. If the channel $P_{\text{out}}$ is informative, then there exists a continuous bounded function $f : \mathbb{R} \to \mathbb{R}$ such that $x \mapsto \int f(y) P_{\text{out}}(y|x) dy$ is not almost everywhere equal to a constant.

*Proof.* Let us suppose that for all continuous bounded function $f: \mathbb{R} \to \mathbb{R}$ we have

$$
\int f(y) P_{\text{out}}(y|x) dy = C_f
$$

for almost all $x \in \mathbb{R}$, for some constant $C_f \in \mathbb{R}$. Let $X \sim \mathcal{N}(0, 1)$ and $Y \sim P_{\text{out}}(\cdot|X)$. We have then $\mathbb{E}[f(Y)|X] = C_f = \mathbb{E}[f(Y)]$ almost surely. Let $g: \mathbb{R} \to \mathbb{R}$ be another continuous bounded function and compute:

$$
\mathbb{E}[g(X)f(Y)] = \mathbb{E}[g(X)\mathbb{E}[f(Y)|X]] = \mathbb{E}[g(X)]\mathbb{E}[f(Y)].
$$

It follows that $X$ and $Y$ are independent: The measures $P_{\text{out}}(y|x) \frac{e^{-x^2/2}}{\sqrt{2\pi}} dy dx$ and $\mathbb{E}[P_{\text{out}}(y|X)] \frac{e^{-x^2/2}}{\sqrt{2\pi}} dy dx$ are therefore equal. Consequently, for almost every $x, y$ we have

$$
P_{\text{out}}(y|x) = \mathbb{E}[P_{\text{out}}(y|X)].
$$

This gives that for almost every $y$, $P_{\text{out}}(y|\cdot)$ is almost everywhere equal to a constant. We conclude by
the arguments presented at the end of the proof of Proposition 21 that $P_{\text{out}}$ is not informative, which is a contradiction. $\square$

# Appendix C: Approximation

Let us recall the various hypotheses considered in this paper, starting with the stronger set:

(H1) The prior distribution $P_0$ has a bounded support.

(H2) $\varphi$ is a bounded $C^2$ function with bounded first and second derivatives w.r.t. its first argument.

(H3) $(\Phi_{\mu i})^{\text{iid}} \mathcal{N}(0, 1)$.

The aim of this section is to relax them to the weaker ones:

(h1) The prior distribution $P_0$ admits a finite third moment and has at least two points in its support.

(h2) There exists $\gamma > 0$ such that the sequence $(\mathbb{E}[|\varphi(\frac{1}{\sqrt{n}}[\mathbf{\Phi}\mathbf{X}^*]_1, \mathbf{A}_1)|^{2+\gamma}])_{n\ge 1}$ is bounded.

(h3) The random variables $(\Phi_{\mu i})$ are independent with zero mean, unit variance and finite third moment that is bounded with $n$.

(h4) For almost-all values of $\mathbf{a} \in \mathbb{R}^{k_A}$ (w.r.t. $P_A$), the function $x \mapsto \varphi(x, \mathbf{a})$ is continuous almost everywhere.

The hypotheses on the presence or not of the Gaussian noise in (20) are:

(h5.a) $\Delta > 0$.

(h5.b) $\Delta = 0$ and $\varphi$ takes values in $\mathbb{N}$.

In this section, we suppose that Theorem 1 holds for channels of the form (20) (with $\Delta > 0$) under the hypotheses (H1), (H2) and (H3), as proven in Section 4.

We show in this section that this imply that Theorem 1 holds under the weaker hypotheses (h1)-(h2)-(h3)-(h4), and either (h5.a) or (h5.b). This section is organized as follows: We first prove Theorem 1 under (h1)-(h2)-(h3)-(h4) and (h5.a) (i.e. $\Delta > 0$). This is done by first relaxing the hypotheses on $P_0$ and $\mathbf{\Phi}$ (Sec. C.1) and then the hypotheses on $\varphi$ (Sec. C.2). Finally, in Sec. C.3, we let $\Delta \to 0$ in order to prove Theorem 1 under (h1)-(h2)-(h3)-(h4) and (h5.b).

Note that the statement of Theorem 1 is equivalent to the statement of Corollary 2, which simply express the result in terms of mutual information. This formulation will be slightly more convenient to relax the hypotheses. We will therefore prove in this section that (46) holds under the hypotheses (h1)-(h2)-(h3)-(h4), and either (h5.a) or (h5.b). The statement of Theorem 1 can then be directly obtained by using the expressions of $I_{P_0}$, $\mathcal{I}_{P_{\text{out}}}$ in terms of $\psi_{P_0}$, $\Psi_{P_{\text{out}}}$, the relation (49) and Lemma 23.

## C.1 Relaxing the hypotheses on $P_0$ and $\mathbf{\Phi}$

As explained at the beginning of Sec. 4, it suffices to consider the case $\Delta = 1$. We start by relaxing the hypothesis (H1).

**Lemma 17 (Relaxing $P_0$).** Suppose that (h1)-(H2)-(H3) and (h5.a) hold. Then Theorem 1 holds.

*Proof.* The ideas are basically the same that in [99] (Sec. 6.2.2). We omit the details here for the sake of brevity. $\square$

We now relax the Gaussian assumption on the “measurement matrix” $\mathbf{\Phi}$.

**Lemma 18 (Relaxing $\mathbf{\Phi}$).** Suppose that $\varphi: \mathbb{R} \times \mathbb{R}^{k_A} \to \mathbb{R}$ is $C^\infty$ with compact support and that (h1)-(h3)-(h5.a) hold. Then Theorem 1 holds.
**Proof.** The proof is based on the Lindeberg generalization theorem (Theorem 2 from [95]) which is a variant of the generalized “Lindeberg principle” from [100]:

**Theorem 5** (Lindeberg generalization theorem). Let $(U_i)_{1\le i\le n}$ and $(V_i)_{1\le i\le n}$ be two collections of random variables with independent components and $f: \mathbb{R}^n \to \mathbb{R}$ a $C^3$ function. Denote $a_i = |EU_i - EV_i|$ and $b_i = |E[U_i^2] - E[V_i^2]|$. Then

$$|\mathbb{E}f(\mathbf{U}) - \mathbb{E}f(\mathbf{V})| \le \sum_{i=1}^{n} \left\{ a_i \mathbb{E}|\partial_i f(U_{1:i-1}, 0, V_{i+1:n})| + \frac{b_i}{2} \mathbb{E}|\partial_i^2 f(U_{1:i-1}, 0, V_{i+1:n})| \right. \\ \left. + \frac{1}{2} \mathbb{E} \int_0^{U_i} |\partial_i^3 f(U_{1:i-1}, 0, V_{i+1:n})|(U_i - s)^2 ds + \frac{1}{2} \mathbb{E} \int_0^{V_i} |\partial_i^3 f(U_{1:i-1}, 0, V_{i+1:n})|(V_i - s)^2 ds \right\}.$$

Let $(\Phi'_{\mu,i})_{i \le n} \sim \mathcal{N}(0, 1)$ and let $(\Phi_{\mu,i})$ be a family of independent random variables, with zero mean and unit variance. Let $f'_n$ be the free entropy (29) with design matrix $\Phi'$ and $f_n$ be the free entropy (29) with design matrix $\Phi$.

We will apply Theorem 5 to the function

$$F: \mathbf{U} \in \mathbb{R}^{m \times n} \mapsto \frac{1}{n} \mathbb{E} \ln \int_{\mathbf{x}, \mathbf{a}} dP_A(\mathbf{a}) dP_0(\mathbf{x}) e^{-\frac{1}{2} \sum_{\mu=1}^{m} \left( \varphi\left(\frac{1}{\sqrt{n}}[\mathbf{U}\mathbf{X}^*]_\mu, \mathbf{A}_\mu\right) - \varphi\left(\frac{1}{\sqrt{n}}[\mathbf{U}\mathbf{x}]_\mu, \mathbf{a}_\mu\right) + Z_\mu \right)^2}$$

where the expectation $\mathbb{E}$ is taken w.r.t. $\mathbf{X}^*, \mathbf{A}$ and $\mathbf{Z}$. We have

$$f_n = \mathbb{E}F(\mathbf{\Phi}) \quad \text{and} \quad f'_n = \mathbb{E}F(\mathbf{\Phi}')$$

It is not difficult to verify that $F$ is a $C^3$ function and that for all $1 \le \mu \le m$ and $1 \le i \le n$:

$$\left\| \frac{\partial^3 F}{\partial U_{\mu,i}^3} \right\|_{\infty} \le \frac{C}{n^{5/2}},$$

for some constant $C$ that only depends on $\varphi$ and the first three moments of $P_0$. Thus, an application of Theorem 5 gives $|f_n - f'_n| \le \frac{C}{\sqrt{n}}$. By Proposition 17, we know that Theorem 1 holds for $f'_n$, thus it holds for $f_n$. $\square$

## C.2 Relaxing the hypotheses on $\varphi$

It remains to relax the hypotheses on $\varphi$. This section is dedicated to the proof of the following proposition, which is of course exactly the statement of Theorem 1.

**Proposition 25** (Relaxing $\varphi$). Suppose that (h1)-(h2)-(h3)-(h4) and (h5.a) hold. Then, Theorem 1 holds for the output channel (20).

To prove Proposition 25 we will approximate the function $\varphi$ with a function $\hat{\varphi}$ which is $C^\infty$ with compact support. In the following, $G$ is a standard Gaussian random variable, independent of everything else.

**Proposition 26.** Suppose that (h1)-(h2)-(h3)-(h4) hold. Then, for all $\epsilon > 0$, there exist $\hat{\varphi} \in C^\infty(\mathbb{R} \times \mathbb{R}^{k_A})$ with compact support, such that

$$\mathbb{E} \left[ \left( \varphi \left( \frac{1}{\sqrt{n}} [\mathbf{\Phi} \mathbf{X}^*]_1, \mathbf{A}_1 \right) - \hat{\varphi} \left( \frac{1}{\sqrt{n}} [\mathbf{\Phi} \mathbf{X}^*]_1, \mathbf{A}_1 \right) \right)^2 \right] \le \epsilon,$$

and for $n$ large enough, we have

$$\mathbb{E} \left[ \left( \varphi \left( \frac{1}{\sqrt{n}} [\mathbf{\Phi} \mathbf{X}^*]_1, \mathbf{A}_1 \right) - \hat{\varphi} \left( \frac{1}{\sqrt{n}} [\mathbf{\Phi} \mathbf{X}^*]_1, \mathbf{A}_1 \right) \right)^2 \right] \le \epsilon.$$
**Proof.** By the Central Limit Theorem (using the fact that the third moments of $(X_i^* \Phi_{1,i})$ are bounded with $n$, because of hypotheses (h1) and (h3))

$$ \left( \frac{[\mathbf{\Phi} \mathbf{X}^*]_1}{\sqrt{n}}, \mathbf{A}_1 \right) \xrightarrow[n \to \infty]{(d)} (\sqrt{\rho}G, \mathbf{A}_1). \qquad (210) $$

This implies that

$$ \varphi \left( \frac{[\mathbf{\Phi} \mathbf{X}^*]_1}{\sqrt{n}}, \mathbf{A}_1 \right) \xrightarrow[n \to \infty]{(d)} \varphi(\sqrt{\rho}G, \mathbf{A}_1), \qquad (211) $$

because $\varphi(\cdot, \mathbf{A}_1)$ is almost-surely continuous almost-everywhere, by assumption (h4). The following sequence $(\varphi(\frac{[\mathbf{\Phi} \mathbf{X}^*]_1}{\sqrt{n}}, \mathbf{A}_1))_n$ is by assumption (h2) bounded in $L^2$, thus by (211) we have that $\mathbb{E}[\varphi(\sqrt{\rho}G, \mathbf{A}_1)^2] < \infty$. Let $\epsilon > 0$. We have just proved that $\varphi \in L^2(\mathbb{R} \times \mathbb{R}^{k_A})$ with the measure induced by $(\sqrt{\rho}G, \mathbf{A}_1)$. There exists (see for instance Corollary 4.2.2 in [98]) a $C^\infty$ function with compact support $\hat{\varphi}$ such that $\mathbb{E}[(\varphi(\sqrt{\rho}G, \mathbf{A}) - \hat{\varphi}(\sqrt{\rho}G, \mathbf{A}))^2] \le \epsilon$.

One deduce from (210) and (211) that

$$ \left( \varphi \left( \frac{1}{\sqrt{n}} [\mathbf{\Phi} \mathbf{X}^*]_1, \mathbf{A}_1 \right) - \hat{\varphi} \left( \frac{1}{\sqrt{n}} [\mathbf{\Phi} \mathbf{X}^*]_1, \mathbf{A}_1 \right) \right)^2 \xrightarrow[n \to \infty]{(d)} (\varphi(\sqrt{\rho}G, \mathbf{A}) - \hat{\varphi}(\sqrt{\rho}G, \mathbf{A}))^2. $$

Now, hypothesis (h2) gives that the sequence above is uniformly integrable. This gives that

$$ \mathbb{E} \left( \varphi \left( \frac{1}{\sqrt{n}} [\mathbf{\Phi} \mathbf{X}^*]_1, \mathbf{A}_1 \right) - \hat{\varphi} \left( \frac{1}{\sqrt{n}} [\mathbf{\Phi} \mathbf{X}^*]_1, \mathbf{A}_1 \right) \right)^2 \xrightarrow[n \to \infty]{n \to \infty} \mathbb{E} \left( \varphi(\sqrt{\rho}G, \mathbf{A}) - \hat{\varphi}(\sqrt{\rho}G, \mathbf{A}) \right)^2 \le \epsilon. $$

Consequently, the left-hand side is smaller than $2\epsilon$ for $n$ large enough. This concludes the proof. $\square$

In the remaining of this section, we prove Proposition 25. Let $\epsilon > 0$. Let $\varphi$ and $\hat{\varphi}$ as in Proposition 26. Let us define $\mathbf{Y} = \varphi(n^{-1/2}\mathbf{\Phi}\mathbf{X}^*, \mathbf{A}) + \sqrt{\Delta}Z$ and $\hat{\mathbf{Y}} = \hat{\varphi}(n^{-1/2}\mathbf{\Phi}\mathbf{X}^*, \mathbf{A}) + \sqrt{\Delta}Z$.

**Lemma 19.** Suppose that (h1)-(h2)-(h3)-(h4) and (h5.a) hold. There exists a constant $C > 0$ such that for $n$ large enough

$$ \left| \frac{1}{n} I(\mathbf{X}^*; \mathbf{Y} | \mathbf{\Phi}) - \frac{1}{n} I(\mathbf{X}^*; \hat{\mathbf{Y}} | \mathbf{\Phi}) \right| \le C \sqrt{\epsilon}. $$

Proof. We have, for $n$ large enough

$$ \mathbb{E} \| \mathbf{Y} - \hat{\mathbf{Y}} \|^2 = m \mathbb{E} \left[ \left( \varphi \left( \frac{1}{\sqrt{n}} [\mathbf{\Phi} \mathbf{X}^*]_1, \mathbf{A}_1 \right) - \hat{\varphi} \left( \frac{1}{\sqrt{n}} [\mathbf{\Phi} \mathbf{X}^*]_1, \mathbf{A}_1 \right) \right)^2 \right] \le m \epsilon. $$

By Proposition 14, we obtain that there exists a constant $C > 0$ (that depends only on $\Delta$ and $\varphi$) such that

$$ |I(\mathbf{X}^*; \mathbf{Y} | \mathbf{\Phi}) - I(\mathbf{X}^*; \hat{\mathbf{Y}} | \mathbf{\Phi})| \le Cm\sqrt{\epsilon}, $$

which gives the result. $\square$

Let $P_{\text{out}}$ denote the transition kernel associated to $\varphi$ and $\hat{P}_{\text{out}}$ the one associated to $\hat{\varphi}$. Analogously to the previous Lemma, one can show:

**Lemma 20.** There exists a constant $C' > 0$ such that for all $q \in [0, \rho]$, $|\mathcal{I}_{P_{\text{out}}}(q) - \mathcal{I}_{\hat{P}_{\text{out}}}(q)| \le C' \sqrt{\epsilon}$.

From there we obtain that

$$ \left| \inf_{q \in [0, \rho]} \sup_{r \ge 0} i_{\text{RS}}(q, r) - \inf_{q \in [0, \rho]} \sup_{r \ge 0} \hat{i}_{\text{RS}}(q, r) \right| \le C' \sqrt{\epsilon}. \qquad (212) $$
Applying Theorem 1 for $\hat{P}_{\text{out}}$, we obtain that for $n$ large enough $|\frac{1}{n}I(\mathbf{X}^*; \hat{\mathbf{Y}}|\mathbf{\Phi}) - \inf_{q \in [0, \rho]} \sup_{r \ge 0} \hat{i}_{\text{RS}}(q, r)| \le \sqrt{\epsilon}$. We now combine this with (212) and Lemma 19 we obtain that for $n$ large enough

$$ \left| \frac{1}{n} I(\mathbf{X}^*; \mathbf{Y}|\mathbf{\Phi}) - \inf_{q \in [0, \rho]} \sup_{r \ge 0} i_{\text{RS}}(q, r) \right| \le \left| \frac{1}{n} I(\mathbf{X}^*; \hat{\mathbf{Y}}|\mathbf{\Phi}) - \inf_{q \in [0, \rho]} \sup_{r \ge 0} \hat{i}_{\text{RS}}(q, r) \right| + (C+C')\sqrt{\epsilon} \le (C+C'+1)\sqrt{\epsilon}, $$

which concludes the proof of Proposition 25, because of (49) and the definition of the functions $I_{P_0}$ and $\mathcal{I}_{P_{\text{out}}}$ in Corollary 2.

### C.3 The case of discrete channels: Removing the Gaussian noise

Now that we proved (Proposition 25) that Theorem 1 holds under hypotheses (h1)-(h2)-(h3)-(h4) and (h5.a), we are going to show that it holds under (h1)-(h2)-(h3)-(h4) and (h5.b) by letting $\Delta \to 0$. We suppose in this section that $\varphi$ takes values in $\mathbb{N}$ and write $\mathbf{Y} = \varphi(\mathbf{\Phi}\mathbf{X}^*/\sqrt{n}, \mathbf{A})$. By Proposition 25 we know that for all $\Delta > 0$,

$$ \frac{1}{n} I(\mathbf{X}^*; \mathbf{Y} + \sqrt{\Delta Z}|\mathbf{\Phi}) \xrightarrow{n \to \infty} \inf_{q \in [0, \rho]} \sup_{r \ge 0} \left\{ I_{P_0}(r) + \alpha I(W^*; \varphi(\sqrt{q}V + \sqrt{\rho-q}W^*, A) + \sqrt{\Delta Z}|V) - \frac{r}{2}(\rho-q) \right\}, $$

where $\mathbf{Z} \sim \mathcal{N}(0, \mathbf{I}_m)$ and $(V, W^*, Z, A) \sim \mathcal{N}(0, 1)^{\otimes 3} \otimes \mathbf{P}_A$. Since $\mathbf{Y}$ takes values in $\mathbb{N}^m$ and $\varphi$ takes values in $\mathbb{N}$, we can apply Corollary 7 twice to obtain that for all $\Delta \in (0, 1]$,

$$ \left| I(\mathbf{X}^*; \mathbf{Y} + \sqrt{\Delta Z}|\mathbf{\Phi}) - I(\mathbf{X}^*; \mathbf{Y}|\mathbf{\Phi}) \right| \le 100me^{-1/(16\Delta)} $$

and (recall that by definition $\mathcal{I}_{P_{\text{out}}}(q) = I(W^*; \varphi(\sqrt{q}V + \sqrt{\rho-q}W^*, A)|V))$):

$$ |I(W^*; \varphi(\sqrt{q}V + \sqrt{\rho-q}W^*, A) + \sqrt{\Delta Z}|V) - \mathcal{I}_{P_{\text{out}}}(q)| \le 100e^{-1/(16\Delta)}. $$

Since our control over $\Delta$ is uniform in $n$, we can permute the $n \to \infty$ limit with the $\Delta \to 0$ limit to get:

$$ \frac{1}{n} I(\mathbf{X}^*; \mathbf{Y}|\mathbf{\Phi}) \xrightarrow{n \to \infty} \inf_{q \in [0, \rho]} \sup_{r \ge 0} \left\{ I_{P_0}(r) + \alpha \mathcal{I}_{P_{\text{out}}}(q) - \frac{r}{2}(\rho - q) \right\}. $$

## Appendix D: Some sup-inf formulas

This appendix gathers some useful lemmas for the manipulations of “sup-inf” formulas like (43).

**Lemma 21.** Let $f, g: \mathbb{R}_+ \to \mathbb{R}$ be two non-decreasing convex functions. We have

$$ \sup_{x \ge 0} \inf_{y \ge 0} \{f(x) + g(y) - xy\} = \sup_{y \ge 0} \inf_{x \ge 0} \{f(x) + g(y) - xy\}. $$

*Proof.* Let us define the monotone conjugate (see the end of §12 of [101]) of $f$ and $g$:

$$ f^*(y) = \sup_{x \ge 0} \{xy - f(x)\} \quad \text{and} \quad g^*(y) = \sup_{x \ge 0} \{xy - g(x)\}. $$

These conjugates satisfy an analog of the Fenchel-Moreau Theorem: $f(x) = \sup_{y \ge 0} \{xy - f^*(y)\}$ and $g(y) =$
$\sup_{x \ge 0} \{xy - g^*(x)\}$, see Theorem 12.4 from [101]. We have then

$$
\begin{align*}
\sup_{x \ge 0} \inf_{y \ge 0} \{f(x) + g(y) - xy\} &= \sup_{x \ge 0} \{f(x) - g^*(x)\} = \sup_{x \ge 0} \sup_{y \ge 0} \{xy - f^*(y) - g^*(x)\} \\
&= \sup_{y \ge 0} \left\{ -f^*(y) + \sup_{x \ge 0} \{xy - g^*(x)\} \right\} = \sup_{y \ge 0} \{-f^*(y) + g(y)\} \\
&= \sup_{y \ge 0} \inf_{x \ge 0} \{f(x) + g(y) - xy\}.
\end{align*}
$$

□

The next Lemma on the Legendre transform will be useful.

**Lemma 22.** Let $V \subset \mathbb{R}$ be a non-empty, closed interval and let $g : V \to \mathbb{R}$ be a continuous convex function.
Define

$$
g^* : x \in \mathbb{R} \mapsto \sup_{y \in V} \{xy - g(y)\} \in \mathbb{R} \cup \{+\infty\}. \qquad (213)
$$

Let $\text{dom } g^* = \{x \in \mathbb{R} | g^*(x) < \infty\}$. Then $g^*$ is a closed convex function and $\text{dom } g^*$ is a non-empty interval.
Moreover, for all $x \in \text{dom } g^*$,

$$
\partial g^*(x) = \arg \max_{y \in V} \{xy - g(y)\}. \qquad (214)
$$

In particular, if $g$ is strictly convex then $g^*$ is differentiable around every point in the interior of $\text{dom } g^*$.

**Proof.** We first extend the function $g$ on $\mathbb{R}$ by setting $g(x) = +\infty$ for all $x \notin V$. Notice that this does not change the definition of the function $g^*$. $g$ is then a proper, closed convex function (see for instance [101] for the definitions of these properties). By Theorem 12.2 in [101], $g^*$ is also a proper closed convex function on $\mathbb{R}$, which gives that $\text{dom } g^*$ is a non-empty interval. We now apply Corollary 23.5.1 from [101] to obtain

$$
y \in \partial g^*(x) \iff x \in \partial g(y) \iff y \text{ maximizes } \{xy - g(y)\},
$$

for all $x \in \text{dom } g^*$, which concludes the proof.

**Corollary 8.** Let $f : \mathbb{R}_+ \to \mathbb{R}$ be a convex, Lipschitz, non-decreasing function. Define $\rho = \sup_{x \ge 0} f'(x^+)$. Let $g : [0, \rho] \to \mathbb{R}$ be a convex, Lipschitz, non-decreasing function. For $q_1 \in \mathbb{R}_+$ and $q_2 \in [0, \rho]$ we define $\psi(q_1, q_2) = f(q_1) + g(q_2) - q_1 q_2$. Then

$$
\sup_{q_1 \ge 0} \inf_{q_2 \in [0, \rho]} \psi(q_1, q_2) = \sup_{q_2 \in [0, \rho]} \inf_{q_1 \ge 0} \psi(q_1, q_2).
$$

*Proof*. In order to apply Lemma 21 we need to extend $g$ on $\mathbb{R}_+$. We thus define for $x \ge 0$

$$
g(x) = \begin{cases} g(x) & \text{if } x \le \rho, \\ g(\rho) + (x - \rho)g'(\rho^{-}) & \text{if } x \ge \rho. \end{cases}
$$

Obviously $g$ is a convex, Lipschitz, non-decreasing function on $\mathbb{R}_+$. One can thus apply Lemma 21:

$$
\sup_{q_1 \ge 0} \inf_{q_2 \ge 0} \{f(q_1) + g(q_2) - q_1 q_2\} = \sup_{q_2 \ge 0} \inf_{q_1 \ge 0} \{f(q_1) + g(q_2) - q_1 q_2\}. \quad (215)
$$

We will show now that $\sup_{q_1 \ge 0} \inf_{q_2 \ge 0} \psi(q_1, q_2) = \sup_{q_1 \ge 0} \inf_{q_2 \in [0, \rho]} \psi(q_1, q_2)$. Let us define for $q_1 \ge 0$

$$
g^*(q_1) = \sup_{q_2 \in [0, \rho]} \{q_1 q_2 - g(q_2)\} \quad \text{and} \quad h(q_1) = \inf_{q_2 \in [0, \rho]} \{f(q_1) + g(q_2) - q_1 q_2\} = f(q_1) - g^*(q_1).
$$
For $q_1 \ge g'(\rho^-)$ we have $g^*(q_1) = q_1\rho - g(\rho)$. The function $h$ is therefore non-increasing on $[g'(\rho^-), +\infty)$, because $f$ is $\rho$-Lipschitz. We get that $h = f - g^*$ achieves its supremum on $[0, g'(\rho^-)]$. Let $q_1^*$ be the smallest point at which this supremum is achieved. Let us show that $\inf_{q_2 \in [0, \rho]} \{g(q_2) - q_1^* q_2\} = \inf_{q_2 \ge 0} \{g(q_2) - q_1^* q_2\}$.

* If $q_1^* = 0$, then the minimum over $[0, \rho]$ is achieved at $q_2 = 0$, because $g$ is non-decreasing. By convexity, $q_2$ is also the minimizer over $\mathbb{R}_+$: both infimum are equal.

* If $q_1^* > 0$, the optimality condition of $q_1^*$ gives $f'(q_1^{*-}) - (g^*)'(q_1^{*-}) \ge 0$. By (214) we obtain that there exists $q_2^* \in \arg\min_{q_2 \in [0, \rho]} \{g(q_2) - q_1^* q_2\}$ such that $f'(q_1^{*-}) \ge q_2^*$. If $q_2^* < \rho$ we conclude, as above, that both infimum are equal. Suppose now that $q_2^* = \rho$ and define $q_1' = g'(\rho^-)$. By the optimality condition of $q_2^* = \rho$ we have $q_1' = g'(\rho^-) \le q_1^*$. Compute

$$h(q_1^*) - h(q_1') = f(q_1^*) - f(q_1') - \rho(q_1^* - q_1') \le 0$$

because $f$ is $\rho$-Lipschitz. Since $q_1' \le q_1^*$ and $q_1^*$ is defined as the smallest maximizer of $h$, we get that $q_1^* = q_1'$. The left-hand derivative of $q_2 \mapsto g(q_2) - q_1^* q_2$ at $q = \rho$ is therefore equal to 0: $\rho$ minimizes $q_2 \mapsto g(q_2) - q_1^* q_2$ over $\mathbb{R}_+$: both infimum are equal.

We have proved that $\inf_{q_2 \in [0, \rho]} \{g(q_2) - q_1^* q_2\} = \inf_{q_2 \ge 0} \{g(q_2) - q_1^* q_2\}$. Therefore

$$\sup_{q_1 \ge 0} \inf_{q_2 \in [0, \rho]} \psi(q_1, q_2) = \inf_{q_2 \in [0, \rho]} \psi(q_1^*, q_2) = \inf_{q_2 \ge 0} \psi(q_1^*, q_2) \le \sup_{q_1 \ge 0} \inf_{q_2 \ge 0} \psi(q_1, q_2).$$

We conclude that $\sup_{q_1 \ge 0} \inf_{q_2 \ge 0} \psi(q_1, q_2) = \sup_{q_1 \ge 0} \inf_{q_2 \in [0, \rho]} \psi(q_1, q_2)$ because the converse inequality is trivial. It remains to show now that $\sup_{q_2 \ge 0} \inf_{q_1 \ge 0} \psi(q_1, q_2) = \sup_{q_2 \in [0, \rho]} \inf_{q_1 \ge 0} \psi(q_1, q_2)$ to prove the Lemma, because of (215). The inequality "$\ge$" is obvious and the inequality "$\le$" follows from the fact that $\inf_{q_1 \ge 0} \psi(q_1, q_2) = -\infty$ if $q_2 > \rho$. $\square$

**Lemma 23.** Let $g$ be a strictly convex, differentiable, Lipschitz non-decreasing function on $\mathbb{R}_+$. Define $\rho = \sup_{x \ge 0} g'(x)$. Let $f$ be a convex, continuous, strictly increasing function on $[0, \rho]$, differentiable on $[0, \rho)$. For $(q_1, q_2) \in [0, \rho] \times \mathbb{R}_+$ we define $\psi(q_1, q_2) = f(q_1) + g(q_2) - q_1 q_2$. Then

$$\sup_{q_1 \in [0, \rho]} \inf_{q_2 \ge 0} \psi(q_1, q_2) = \sup_{(q_1, q_2) \in \Gamma} \psi(q_1, q_2), \qquad (216)$$

where

$$\Gamma = \left\{ (q_1, q_2) \in [0, \rho] \times (\mathbb{R}_+ \cup \{+\infty\}) \mid \begin{array}{l} q_1 = g'(q_2) \\ q_2 = f'(q_1) \end{array} \right\},$$

where all the function are extended by there limits at the points at which they may not be defined (for instance $g'(+\infty) = \lim_{q \to \infty} g'(q)$, $f'(\rho) = \lim_{q \to \rho} f'(q)$). Moreover, the above extremas are achieved precisely on the same couples.

*Proof.* Let $q_1^*$ be a maximizer of $f - g^*$ over $[0, \rho]$. $q_1^*$ is well defined because $f$ is continuous and $g^*$ is continuous over $[0, \rho)$ and is either continuous at $\rho$ or goes to $+\infty$ at $\rho$ (this comes from the fact that $g^*$ is a closed convex function, see Lemma 22).

**Case 1:** $0 < q_1^* < \rho$. By strict convexity of $g$, $\psi(q_1, \cdot)$ admits a unique minimizer $q_2^*$ and $(g^*)'(q_1^*) = q_2^*$ by Lemma 22. Thus, the optimality condition at $q_1^*$ gives

$$0 = f'(q_1^*) - (g^*)'(q_1^*) = f'(q_1^*) - q_2^*.$$

The optimality of $q_2^*$ gives then $q_1^* \le g'(q_2^*)$. Suppose that $q_1^* < g'(q_2^*)$. This is only possible when $q_2^* = 0$. Define $q_1' = g'(q_2^*) = g'(0)$. Remark that $g^*(q_1') = -g(0) = g^*(q_1^*)$. We supposed that $q_1' > q_1^*$ thus, by
strict monotonicity of $f, f(q'_1) - g^*(q'_1) > f(q_1^*) - g^*(q_1^*)$ which contradict the optimality of $q_1^*$. We obtain therefore that $q_1^* = g'(q_2^*)$.

**Case 2:** $q_1^* = 0$. The optimality condition gives now

$$0 \le f'(q_1^* = 0) \le q_2^*, \qquad (217)$$

where $q_2^*$ is again the unique minimizer of $\psi(q_1^* = 0, \cdot) = f(0) + g$. $g$ is strictly increasing, so $q_2^* = 0$. Therefore $q_2^* = 0 = f'(q_1^* = 0)$, by (217). As before we have necessarily, by optimality of $q_2^*$ that $q_1^* = g'(q_2^*)$.

**Case 3:** $q_1^* = \rho$. In that case $\arg\min_{q_2 \ge 0}\{g(q_2) - q_1^*q_2\} = \emptyset$ because $g$ is strictly convex and $\rho$-Lipschitz. Lemma 22 gives then that $\partial g^*(\rho) = \emptyset$ which implies (see Theorem 23.3 from [101]) that $(g^*)'(\rho^-) = +\infty$. Since $q_1^* = \rho$ maximizes $f - g^*$, we necessarily have then $f'(\rho^-) = +\infty$.

Using the slight abuse of notation explained in the Lemma, we have $f'(q_1^*) = +\infty = q_2^*$, where $q_2^* = +\infty$ is the unique “minimizer” of $\psi(q_1^*, \cdot)$, by strict convexity of $g$. By definition of $\rho$ we have also $g'(q_2^*) = g'(+\infty) = \rho = q_1^*$.

We conclude from the tree cases above that the “sup-inf” in (216) is achieved, and that all the couples $(q_1^*, q_2^*)$ that achieve this “sup-inf” belong to $\Gamma$. Thus

$$\sup_{q_1 \in [0, \rho]} \inf_{q_2 \ge 0} \psi(q_1, q_2) \le \sup_{(q_1, q_2) \in \Gamma} \psi(q_1, q_2).$$

Let now be $(q_1, q_2) \in \Gamma$. By convexity of $g$ we see easily that $\psi(q_1, q_2) = \inf_{q_2'} \psi(q_1, q_2')$. Thus, $\psi(q_1, q_2) \le \sup_{q_1'} \inf_{q_2'} \psi(q_1, q_2')$. Therefore

$$\sup_{(q_1, q_2) \in \Gamma} \psi(q_1, q_2) \le \sup_{q_1 \in [0, \rho]} \inf_{q_2 \ge 0} \psi(q_1, q_2).$$

This concludes the proof of (216). It remains to see that a couple $(q_1^*, q_2^*) \in \Gamma$ that achieves the supremum in (216) also achieves the “sup-inf”. This simply follows from the fact that $\psi(q_1^*, q_2^*) = \inf_{q_2} \psi(q_1^*, q_2)$ and (216). $\square$

# Appendix E: Concentration of free entropy and overlaps

## E.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. 4.1 concentrates around its expectation. To simplify the notations we use $C(\varphi, S, \alpha)$ for a generic non-negative constant depending only on $\varphi, S$ and $\alpha$ ($S$ is the supremum over the signal values). We will also use the notation $K = 1 + \max(\rho, r_{\max})$ for a constant (depending only on $\rho \le S^2$ and $\varphi$) that upper bounds both $R_1$ and $R_2$ given by (89). It is also understood that $n$ and $m$ are large enough and $m/n \to \alpha$.

**Theorem 6 (Free entropy concentration).** Under assumptions (H1), (H2) and (H3) there exists a non-negative constant $C(\varphi, S, \alpha)$ such that the partition function (97) concentrates as

$$\mathrm{Var}\left(\frac{1}{n} \ln \mathcal{Z}_{t, \epsilon}\right) = \mathbb{E}\left[\left(\frac{1}{n} \ln \mathcal{Z}_{t, \epsilon} - \frac{1}{n} \mathbb{E} \ln \mathcal{Z}_{t, \epsilon}\right)^2\right] \le \frac{C(\varphi, S, \alpha)}{n}. \qquad (218)$$

The remaining of this appendix is dedicated to the proof of Theorem 6. We first recall some set-up and
notation for the convenience of the reader. Recall that the interpolating Hamiltonian (95)–(93) is

$$ \mathcal{H}_{t,\epsilon}(\mathbf{x}, \mathbf{w}; \mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{\Phi}, \mathbf{V}) = -\sum_{\mu=1}^{m} \ln P_{\text{out}}(Y_{t,\mu}|s_{t,\mu}(\mathbf{x}, w_{\mu})) + \frac{1}{2} \sum_{i=1}^{n} (Y'_{t,i} - \sqrt{R_1(t)} x_i)^2 \quad (219) $$

where

$$ s_{t,\mu}(\mathbf{x}, w_{\mu}) := \sqrt{\frac{1-t}{n}}[\mathbf{\Phi}\mathbf{x}]_{\mu} + k_1(t)V_{\mu} + k_2(t)w_{\mu}, \quad k_1(t) := \sqrt{R_2(t)}, \quad k_2(t) := \sqrt{\rho t - R_2(t) + 2s_n}. $$

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

$$ \begin{cases} Y_{t,\mu} = \varphi\left(\sqrt{\frac{1-t}{n}}[\mathbf{\Phi}\mathbf{X}^*]_{\mu} + k_1(t)V_{\mu} + k_2(t)W_{\mu}^*, \mathbf{A}_{\mu}\right) + Z_{\mu}, \\ Y'_{t,i} = \sqrt{R_1(t)}X_i^* + Z'_i. \end{cases} $$

In this representation the random variables $(\mathbf{A}_{\mu})_{1\le\mu\le m} \stackrel{\text{iid}}{\sim} P_A$ are arbitrary, and $(Z_{\mu})_{1\le\mu\le m} \stackrel{\text{iid}}{\sim} \mathcal{N}(0, 1)$, $(Z'_i)_{1\le i\le n} \stackrel{\text{iid}}{\sim} \mathcal{N}(0, 1)$. We have

$$ \begin{aligned} P_{\text{out}}(Y_{t,\mu}|s_{t,\mu}(\mathbf{x}, w_{\mu})) &= \int dP_A(\mathbf{a}_{\mu}) \frac{1}{\sqrt{2\pi}} \exp \left\{ -\frac{1}{2} \left( Y_{t,\mu} - \varphi(s_{t,\mu}(\mathbf{x}, w_{\mu}), \mathbf{a}_{\mu}) \right)^2 \right\} \\ &= \int dP_A(\mathbf{a}_{\mu}) \frac{1}{\sqrt{2\pi}} \exp \left\{ -\frac{1}{2} \left( \Gamma_{t,\mu}(\mathbf{x}, w_{\mu}, \mathbf{a}_{\mu}) + Z_{\mu} \right)^2 \right\} \end{aligned} \quad (220) $$

where, using the random function representation,

$$ \begin{aligned} \Gamma_{t,\mu}(\mathbf{x}, w_{\mu}, \mathbf{a}_{\mu}) &= \varphi\left(\sqrt{\frac{1-t}{n}}[\mathbf{\Phi}\mathbf{X}^*]_{\mu} + k_1(t)V_{\mu} + k_2(t)W_{\mu}^*, \mathbf{A}_{\mu}\right) - \varphi\left(\sqrt{\frac{1-t}{n}}[\mathbf{\Phi}\mathbf{x}]_{\mu} + k_1(t)V_{\mu} + k_2(t)w_{\mu}, \mathbf{a}_{\mu}\right). \end{aligned} \quad (221) $$

From (219), (220), (221) we can express the free entropy of the interpolating model as

$$ \frac{1}{n} \ln \mathcal{Z}_{t,\epsilon} = \frac{1}{n} \ln \int dP_0(\mathbf{x}) dP_A(\mathbf{a}) \mathcal{D}\mathbf{w} e^{-\mathcal{H}_{t,\epsilon}(\mathbf{x}, \mathbf{w}, \mathbf{a})} - \frac{m}{2n} \ln(2\pi) \quad (222) $$

where $\mathcal{D}\mathbf{w}$ denote the standard $m$-dimensional Gaussian measure and where the Hamiltonian $\mathcal{H}_{t,\epsilon}$ is re-expressed as

$$ \mathcal{H}_{t,\epsilon}(\mathbf{x}, \mathbf{w}, \mathbf{a}) = \frac{1}{2} \sum_{\mu=1}^{m} \left( \Gamma_{t,\mu}(\mathbf{x}, w_{\mu}, \mathbf{a}_{\mu}) + Z_{\mu} \right)^2 + \frac{1}{2} \sum_{i=1}^{n} \left( \sqrt{R_1(t)} (X_i^* - x_i) + Z'_i \right)^2. \quad (223) $$

The interpretation here is that $\mathbf{x}, \mathbf{w}, \mathbf{a}$ are annealed variables and $\mathbf{\Phi}, \mathbf{V}, \mathbf{A}, \mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{X}^*, \mathbf{W}^*$, or equivalently $\mathbf{\Phi}, \mathbf{V}, \mathbf{A}, \mathbf{Z}, \mathbf{Z}', \mathbf{X}^*, \mathbf{W}^*$ are quenched. The inference problem is to recover $\mathbf{X}^*, \mathbf{W}^*$ given $\mathbf{\Phi}, \mathbf{V}, \mathbf{Y}_t, \mathbf{Y}'_t$. The free entropy can be further re-expressed as

$$ \frac{1}{n} \ln \mathcal{Z}_{t,\epsilon} = \frac{1}{n} \ln \hat{\mathcal{Z}}_{t,\epsilon} - \frac{1}{2n} \sum_{\mu=1}^{m} Z_{\mu}^2 - \frac{1}{2n} \sum_{i=1}^{n} Z'_{i}^2 - \frac{m}{2n} \ln(2\pi) \quad (224) $$
where

$$ \frac{1}{n} \ln \hat{Z}_{t, \epsilon} = \frac{1}{n} \ln \int dP_0(\mathbf{x}) dP_A(\mathbf{a}) \mathcal{D}\mathbf{w} e^{-\hat{H}_{t, \epsilon}(\mathbf{x}, \mathbf{w}, \mathbf{a})}, \qquad (225) $$

$$ \hat{H}_{t,\epsilon}(\mathbf{x}, \mathbf{w}, \mathbf{a}) = \frac{1}{2} \sum_{\mu=1}^{m} \left\{ \Gamma_{t,\mu}(\mathbf{x}, w_{\mu}, \mathbf{a}_{\mu})^2 + 2Z_{\mu}\Gamma_{t,\mu}(\mathbf{x}, w_{\mu}, \mathbf{a}_{\mu}) \right\} \\ + \frac{1}{2} \sum_{i=1}^{n} \left\{ R_1(t)(X_i^* - x_i)^2 + 2Z_i'\sqrt{R_1(t)}(X_i^* - x_i) \right\}. \qquad (226) $$

In order to prove Theorem 6 it remains to show that there exists a constant $C(\varphi, S, \alpha) > 0$ such that $\mathrm{Var}(\ln \hat{Z}_{t,\epsilon}/n) \le C(\varphi, S, \alpha)/n$. This concentration property together with (224) implies (218).

We will first show concentration w.r.t. all Gaussian variables $\mathbf{\Phi}, \mathbf{V}, \mathbf{Z}, \mathbf{Z}', \mathbf{W}^*$ thanks to the classical Gaussian Poincaré inequality, then the concentration w.r.t. $\mathbf{A}$ and finally the one w.r.t. $\mathbf{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 [102] (Chapter 3) for detailed proofs of these statements.

**Proposition 27** (Gaussian Poincaré inequality). Let $\mathbf{U} = (U_1, \dots, U_N)$ be a vector of $N$ independent standard normal random variables. Let $g: \mathbb{R}^N \to \mathbb{R}$ be a continuously differentiable function. Then

$$ \mathrm{Var}(g(\mathbf{U})) \le \mathbb{E}[\|\nabla g(\mathbf{U})\|^2]. \qquad (227) $$

**Proposition 28** (Bounded difference). Let $\mathcal{U} \subset \mathbb{R}$. Let $g: \mathcal{U}^N \to \mathbb{R}$ a function that satisfies the bounded difference property, i.e., there exists some constants $c_1, \dots, c_N \ge 0$ such that

$$ \sup_{\substack{u_1, \dots, u_N \in \mathcal{U}^N \\ u'_i \in \mathcal{U}}} |g(u_1, \dots, u_i, \dots, u_N) - g(u_1, \dots, u'_i, \dots, u_N)| \le c_i \quad \text{for all } 1 \le i \le N. $$

Let $\mathbf{U} = (U_1, \dots, U_N)$ be a vector of $N$ independent random variables that take values in $\mathcal{U}$. Then

$$ \mathrm{Var}(g(\mathbf{U})) \le \frac{1}{4} \sum_{i=1}^{N} c_i^2. \qquad (228) $$

### E.1.1 Concentration with respect to the Gaussian random variables Z, Z', V, W*, Φ

**Lemma 24.** Let $\mathbb{E}_G$ denotes the joint expectation w.r.t. Z, Z', V, W*, Φ only. There exists a constant $C(\varphi, S, \alpha) > 0$ such that

$$ \mathbb{E} \left[ \left( \frac{1}{n} \ln \hat{Z}_{t, \epsilon} - \frac{1}{n} \mathbb{E}_G \ln \hat{Z}_{t, \epsilon} \right)^2 \right] \le \frac{C(\varphi, S, \alpha)}{n}. \qquad (229) $$

Lemma 24 follows directly from Lemmas 25 and 26 below.

**Lemma 25.** Let $\mathbb{E}_{Z,Z'}$ denotes the expectation w.r.t. Z, Z' only. There exists a constant $C(\varphi, S, \alpha) > 0$ such that

$$ \mathbb{E} \left[ \left( \frac{1}{n} \ln \hat{Z}_{t, \epsilon} - \frac{1}{n} \mathbb{E}_{Z,Z'} \ln \hat{Z}_{t, \epsilon} \right)^2 \right] \le \frac{C(\varphi, S, \alpha)}{n}. \qquad (230) $$

*Proof.* We consider here $g = \ln \hat{Z}_{t,\epsilon}/n$ only as a function of Z and Z' and work conditionally on all other random variables. We have

$$ \|\nabla g\|^2 = \sum_{\mu=1}^{m} \left| \frac{\partial g}{\partial Z_{\mu}} \right|^2 + \sum_{i=1}^{n} \left| \frac{\partial g}{\partial Z_i'} \right|^2. \qquad (231) $$
Each of these partial derivatives are of the form $|\partial_u g| = |n^{-1}\langle \partial_u \hat{H}_{t,\epsilon} \rangle_{\hat{H}_{t,\epsilon}}|$ where the Gibbs bracket $\langle - \rangle_{\hat{H}_{t,\epsilon}}$ pertains to the effective Hamiltonian (226). We find

$$ \begin{aligned} \left| \frac{\partial g}{\partial Z_{\mu}} \right| &= n^{-1} \left| \langle \Gamma_{t,\mu} \rangle_{\hat{H}_{t,\epsilon}} \right| \le 2n^{-1} \sup |\varphi|, \\ \left| \frac{\partial g}{\partial Z'_{i}} \right| &= n^{-1} \sqrt{R_1(t)} |X_i^* - \langle x_i \rangle_{\hat{H}_{t,\epsilon}}| \le 2n^{-1} \sqrt{KS}, \end{aligned} $$

and replacing in (231) we get $\|\nabla g\|^2 \le 4n^{-1}(\frac{m}{n}(\sup |\varphi|)^2 + KS^2)$. Applying Proposition 27 we have

$$ \mathbb{E}_{\mathbf{Z}, \mathbf{Z}'} \left[ \left( \frac{1}{n} \ln \hat{Z}_{t, \epsilon} - \frac{1}{n} \mathbb{E}_{\mathbf{Z}, \mathbf{Z}'} \ln \hat{Z}_{t, \epsilon} \right)^2 \right] \le \frac{C(\varphi, S, \alpha)}{n}. \quad (232) $$

Taking the expectation in (232) gives the lemma. □

**Lemma 26.** There exists a constant $C(\varphi, S, \alpha) > 0$ such that

$$ \mathbb{E} \left[ \left( \frac{1}{n} \mathbb{E}_{\mathbf{Z}, \mathbf{Z}'} \ln \hat{Z}_{t, \epsilon} - \frac{1}{n} \mathbb{E}_{G} \ln \hat{Z}_{t, \epsilon} \right)^2 \right] \le \frac{C(\varphi, S, \alpha)}{n}. \quad (233) $$

*Proof.* We consider here $g = \mathbb{E}_{\mathbf{Z}, \mathbf{Z}'} \ln \hat{Z}_{t, \epsilon}/n$ as a function of $\mathbf{V}$, $\mathbf{W}^*$, $\mathbf{\Phi}$ and we work conditionally on the other random variables. Let $\partial_x \varphi$ be the derivative of $\varphi$ w.r.t. its first argument. We compute

$$ \begin{aligned} \left| \frac{\partial g}{\partial V_{\mu}} \right| &= n^{-1} \left| \mathbb{E}_{\mathbf{Z}, \mathbf{Z}'} \left\langle \left( \Gamma_{t, \mu} + Z_{\mu} \right) \frac{\partial \Gamma_{t, \mu}}{\partial V_{\mu}} \right\rangle_{\hat{H}_{t, \epsilon}} \right| \\ &\le n^{-1} \mathbb{E}_{\mathbf{Z}, \mathbf{Z}'} \left[ \left( 2 \sup |\varphi| + |Z_{\mu}| \right) 2\sqrt{K} \sup |\partial_x \varphi| \right] = n^{-1} \left( 2 \sup |\varphi| + \sqrt{\frac{2}{\pi}} \right) 2\sqrt{K} \sup |\partial_x \varphi|. \end{aligned} $$

The same inequality holds for $|\frac{\partial g}{\partial W_{\mu}^*}|$. To compute the derivative w.r.t. $\Phi_{\mu i}$ we first remark

$$ \frac{\partial \Gamma_{t, \mu}}{\partial \Phi_{\mu i}} = \sqrt{\frac{1-t}{n}} \left\{ X_i^* \partial_{x\varphi} \left( \sqrt{\frac{1-t}{n}} [\mathbf{\Phi} \mathbf{X}]_{\mu} + k_1(t)V_{\mu} + k_2(t)W_{\mu}^*, \mathbf{A}_{\mu} \right) \right. \\ \left. - x_i \partial_{x\varphi} \left( \sqrt{\frac{1-t}{n}} [\mathbf{\Phi} \mathbf{x}]_{\mu} + k_1(t)V_{\mu} + k_2(t)w_{\mu}, \mathbf{a}_{\mu} \right) \right\}. $$

Therefore, as $t \in [0, 1]$,

$$ \begin{aligned} \left| \frac{\partial g}{\partial \Phi_{\mu i}} \right| &= n^{-1} \left| \mathbb{E}_{\mathbf{Z}, \mathbf{Z}'} \left\langle \left( \Gamma_{t, \mu} + Z_{\mu} \right) \frac{\partial \Gamma_{t, \mu}}{\partial \Phi_{\mu i}} \right\rangle_{\hat{H}_{t, \epsilon}} \right| \\ &\le n^{-3/2} \mathbb{E}_{\mathbf{Z}, \mathbf{Z}'} \left[ (2 \sup |\varphi| + |Z_{\mu}|) 2S \sup |\partial_x \varphi| \right] = n^{-3/2} \left( 2 \sup |\varphi| + \sqrt{\frac{2}{\pi}} \right) 2S \sup |\partial_x \varphi|. \end{aligned} $$

Putting these inequalities together we find

$$ \begin{aligned} \|\nabla g\|^2 &= \sum_{\mu=1}^{m} \left| \frac{\partial g}{\partial V_{\mu}} \right|^2 + \sum_{\mu=1}^{m} \left| \frac{\partial g}{\partial W_{\mu}^*} \right|^2 + \sum_{\mu=1}^{m} \sum_{i=1}^{n} \left| \frac{\partial g}{\partial \Phi_{\mu i}} \right|^2 \\ &\le 2 \frac{m}{n^2} \left( 2 \sup |\varphi| + \sqrt{\frac{2}{\pi}} \right)^2 4K \left( \sup |\partial_x \varphi| \right)^2 + \frac{mn}{n^3} \left( 2 \sup |\varphi| + \sqrt{\frac{2}{\pi}} \right)^2 4S^2 \left( \sup |\partial_x \varphi| \right)^2. \end{aligned} $$

The lemma follows again from Proposition 27. □
### E.1.2 Bounded difference with respect to $A_μ$

The next step is an application of the variance bound of Lemma 28 to show that $\mathbb{E}_G \ln \hat{Z}_{t,\epsilon}/n$ concentrates w.r.t. $\mathbf{A}$ (we still keep $\mathbf{X}^*$ fixed for the moment).

**Lemma 27.** Let $\mathbb{E}_A$ denotes the expectation w.r.t. $\mathbf{A}$ only. There exists a constant $C(\varphi, \alpha) > 0$ such that

$$ \mathbb{E}\left[\left(\frac{1}{n}\mathbb{E}_G \ln \hat{Z}_{t,\epsilon} - \frac{1}{n}\mathbb{E}_{G,A} \ln \hat{Z}_{t,\epsilon}\right)^2\right] \le \frac{C(\varphi, \alpha)}{n}. \quad (234) $$

*Proof.* Let us consider $g = \mathbb{E}_G \ln \hat{Z}_{t,\epsilon}/n$ as a function of $\mathbf{A}$ only. Let $\nu \in \{1, \dots, m\}$. We must estimate variations $g(\mathbf{A}) - g(\mathbf{A}^{(\nu)})$ corresponding to two configurations $\mathbf{A}$ and $\mathbf{A}^{(\nu)}$ with $A_\mu^{(\nu)} = A_\mu$ for $\mu \neq \nu$ and $A_\nu^{(\nu)} = \tilde{A}_\nu$. We will use the notations $\hat{\mathcal{H}}_{t,\epsilon}^{(\nu)}$ and $\Gamma_{t,\mu}^{(\nu)}$ to denote respectively the quantities $\hat{\mathcal{H}}_{t,\epsilon}$ and $\Gamma_{t,\mu}$ where $\mathbf{A}$ is replaced by $\mathbf{A}^{(\nu)}$. By an application of Jensen's inequality one finds

$$ \frac{1}{n} \mathbb{E}_G \langle \hat{\mathcal{H}}_{t,\epsilon}^{(\nu)} - \hat{\mathcal{H}}_{t,\epsilon} \rangle_{\hat{\mathcal{H}}_{t,\epsilon}^{(\nu)}} \le g(\mathbf{A}) - g(\mathbf{A}^{(\nu)}) \le \frac{1}{n} \mathbb{E}_G \langle \hat{\mathcal{H}}_{t,\epsilon}^{(\nu)} - \hat{\mathcal{H}}_{t,\epsilon} \rangle_{\hat{\mathcal{H}}_{t,\epsilon}} \quad (235) $$

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

$$ \hat{\mathcal{H}}_{t,\epsilon}^{(\nu)} - \hat{\mathcal{H}}_{t,\epsilon} = \frac{1}{2} \sum_{\mu=1}^{m} \left( \Gamma_{t,\mu}^{(\nu)2} - \Gamma_{t,\mu}^{2} + 2Z_{\mu}(\Gamma_{t,\mu}^{(\nu)} - \Gamma_{t,\mu}) \right) = \frac{1}{2} \left( \Gamma_{t,\nu}^{(\nu)2} - \Gamma_{t,\nu}^{2} + 2Z_{\nu}(\Gamma_{t,\nu}^{(\nu)} - \Gamma_{t,\nu}) \right). $$

Consequently

$$ \frac{1}{2n} \mathbb{E}_G \langle \Gamma_{t,\nu}^{(\nu)2} - \Gamma_{t,\nu}^{2} + 2Z_{\nu}(\Gamma_{t,\nu}^{(\nu)} - \Gamma_{t,\nu}) \rangle_{\hat{\mathcal{H}}_{t,\epsilon}^{(\nu)}} \le g(\mathbf{A}) - g(\mathbf{A}^{(\nu)}) \\ \le \frac{1}{2n} \mathbb{E}_G \langle \Gamma_{t,\nu}^{(\nu)2} - \Gamma_{t,\nu}^{2} + 2Z_{\nu}(\Gamma_{t,\nu}^{(\nu)} - \Gamma_{t,\nu}) \rangle_{\hat{\mathcal{H}}_{t,\epsilon}}. \quad (236) $$

Notice that $|\Gamma_{t,\nu}^{(\nu)2} - \Gamma_{t,\nu}^{2} + 2Z_{\nu}(\Gamma_{t,\nu}^{(\nu)} - \Gamma_{t,\nu})| \le 8(\sup |\varphi|)^2 + 8|Z_{\nu}| \sup |\varphi|$. Thus we conclude by (236) that $g$ satisfies a bounded difference property:

$$ |g(\mathbf{A}) - g(\mathbf{A}^{(\nu)})| \le \frac{4}{n} \sup |\varphi| \left( \sup |\varphi| + \sqrt{\frac{2}{\pi}} \right). \quad (237) $$

Lemma 27 follows then by an application of Proposition 28. $\square$

### E.1.3 Bounded difference with respect to $X_i^*$

Let $\mathbb{E}_\Theta = \mathbb{E}_{A,G}$ denote the expectation w.r.t. all quenched variables except $\mathbf{X}^*$. It remains to bound the variance of $\mathbb{E}_\Theta \ln \hat{Z}_{t,\epsilon}/n$ (which only depends on $\mathbf{X}^*$).

**Lemma 28.** There exists a constant $C(\varphi, S, \alpha) > 0$ such that

$$ \mathbb{E}\left[\left(\frac{1}{n}\mathbb{E}_{\Theta} \ln \hat{Z}_{t,\epsilon} - \frac{1}{n}\mathbb{E}_{\Theta} \ln \hat{Z}_{t,\epsilon}\right)^2\right] \le \frac{C(\varphi, S, \alpha)}{n}. \quad (238) $$

*Proof.* The lemma is proved using again a bounded difference argument. Let $g = \mathbb{E}_\Theta \ln \hat{Z}_{t,\epsilon}/n$ a function of $\mathbf{X}^*$. Let $j \in \{1, \dots, n\}$. Let $\mathbf{X}^*, \mathbf{X}^{*(j)} \in [-S, S]^n$ be two input signals such that $X_i^{*(j)} = X_i^*$ for $i \neq j$.

We are going to interpolate between $g(\mathbf{X}^*)$ and $g(\mathbf{X}^{*(j)})$. For $s \in [0, 1]$ we define

$$ \psi(s) = g(s\mathbf{X}^* + (1-s)\mathbf{X}^{*(j)}). $$
Obviously $\psi(1) = g(\mathbf{X}^*)$ and $\psi(0) = g(\mathbf{X}^{(j)})$. Using Gaussian integration by parts, it is not difficult to verify that for $s \in [0, 1]$

$$|\psi'(s)| \le \frac{C(\varphi, S, \alpha)}{n}.$$

This implies the bounded difference property $|g(\mathbf{X}^*) - g(\mathbf{X}^{(j)})| \le C(\varphi, S, \alpha)/n$ and using Proposition 28 we obtain the lemma. □

### E.1.4 Proof of Theorem 6

From Lemmas 24, 27 and 28 above, we obtain directly that $\mathrm{Var}(\ln \hat{Z}_{t,\epsilon}/n) \le C(\varphi, S, \alpha)/n$ for some constant $C(\varphi, S, \alpha) > 0$. As mentioned before this implies, thanks to (224), the Theorem 6.

## E.2 Concentration of the overlap

In this appendix we provide the proof of Proposition 4. Recall the notation $\langle - \rangle_{n,t,\epsilon}$ for the Gibbs bracket associated to the Hamiltonian (95). It is crucial that it preserves the Nishimori identity of Appendix A.1, i.e. it must come from an inference problem with known parameters. Consider the corresponding average free entropy $f_{n,\epsilon}(t)$. In this section we think of it as a function of $R_1 = R_1(t, \epsilon)$ and $R_2 = R_2(t, \epsilon)$ given by (89), i.e. $(R_1, R_2) \mapsto f_{n,\epsilon}(t)$. Similarly the free entropy for a realization of the quenched variables is also viewed here as a function $(R_1, R_2) \mapsto F_{n,\epsilon}(t) := \ln \mathcal{Z}_{t,\epsilon}(\mathbf{Y}_t, \mathbf{Y}'_t, \mathbf{\Phi}, \mathbf{V})/n$. For this section, we drop the indices in the Gibbs bracket $\langle - \rangle_{n,t,\epsilon}$ and simply write $\langle - \rangle$.

Let

$$\mathcal{L} := \frac{1}{n} \sum_{i=1}^{n} \left( \frac{x_i^2}{2} - x_i X_i^* - \frac{x_i Z_i'}{2\sqrt{R_1}} \right).$$

The fluctuations of the overlap $Q := n^{-1} \sum_{i=1}^n X_i^* x_i$ and those of $\mathcal{L}$ are related through the remarkable identity

$$\mathbb{E}\langle (\mathcal{L} - \mathbb{E}\langle \mathcal{L} \rangle)^2 \rangle = \frac{1}{4}\mathbb{E}\langle (Q - \mathbb{E}\langle Q \rangle)^2 \rangle + \frac{1}{2}\mathbb{E}[\langle Q^2 \rangle - \langle Q \rangle^2] + \frac{1}{4nR_1}\mathbb{E}[(X_1^*)^2]. \quad (239)$$

In particular

$$\mathbb{E}\langle (\mathcal{L} - \mathbb{E}\langle \mathcal{L} \rangle)^2 \rangle \ge \frac{1}{4}\mathbb{E}\langle (Q - \mathbb{E}\langle Q \rangle)^2 \rangle. \quad (240)$$

A detailed derivation of (239) involves only lengthy but straightforward algebra, using the Nishimori identity and integrations by parts w.r.t. the Gaussian noise $Z'_i$, and can be found in Sec. 6 of [52]. Proposition 4 is then a direct consequence of the following:

**Proposition 29** (Concentration of $\mathcal{L}$ on $\mathbb{E}\langle \mathcal{L} \rangle$). Let $\mathcal{B}_n := [s_n, 2s_n]^2$, where the sequence $(s_n) \in (0, 1/2]^N$. Assume that the interpolation functions $(r_\epsilon)$ and $(q_\epsilon)$ are regular (recall Definition 1). Under assumptions (H1), (H2) and (H3) there exists a constant $C(\varphi, S, \alpha)$ such that

$$\int_{\mathcal{B}_n} d\epsilon \mathbb{E}\langle (\mathcal{L} - \mathbb{E}\langle \mathcal{L} \rangle)_{n,t,\epsilon}^2 \rangle_{n,t,\epsilon} \le \frac{C(\varphi, S, \alpha)}{n^{1/4}}. \quad (241)$$

The proof of this proposition is broken in two parts. Notice that

$$\mathbb{E}\langle (\mathcal{L} - \mathbb{E}\langle \mathcal{L} \rangle)^2 \rangle = \mathbb{E}\langle (\mathcal{L} - \langle \mathcal{L} \rangle)^2 \rangle + \mathbb{E}[\langle (\mathcal{L} - \mathbb{E}\langle \mathcal{L} \rangle)^2 \rangle]. \quad (242)$$
Thus it suffices to prove the two following lemmas (see the proofs below). 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 entropy and the Nishimori identity.

**Lemma 29** (Concentration of $\mathcal{L}$ on $\langle \mathcal{L} \rangle$). Under the same hypotheses as in Proposition 29 we have

$$ \int_{\mathcal{B}_n} d\epsilon \mathbb{E}\langle (\mathcal{L} - \langle \mathcal{L} \rangle_{n,t,\epsilon})^2 \rangle_{n,t,\epsilon} \le \frac{\rho(1+\rho)}{n}. \quad (243) $$

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 entropy (more precisely Theorem 6 in Appendix E.1).

**Lemma 30** (Concentration of $\langle \mathcal{L} \rangle$ on $\mathbb{E}\langle \mathcal{L} \rangle$). Under the same hypotheses as in Proposition 29 there exists a constant $C(\varphi, S, \alpha)$ such that

$$ \int_{\mathcal{B}_n} d\epsilon \mathbb{E}[(\langle \mathcal{L} \rangle_{n,t,\epsilon} - \mathbb{E}\langle \mathcal{L} \rangle_{n,t,\epsilon})^2] \le \frac{C(\varphi, S, \alpha)}{n^{1/4}}. \quad (244) $$

We now turn to the proof of Lemmas 29 and 30. The main ingredient is a set of formulas for the first two derivatives of the free entropy w.r.t. $R_1 = R_1(t, \epsilon)$. For any given realisation of the quenched disorder,

$$ \frac{dF_{n,\epsilon}(t)}{dR_1} = -\langle \mathcal{L} \rangle - \frac{1}{2n} \sum_{i=1}^{n} \left( (X_i^*)^2 + \frac{1}{\sqrt{R_1}} X_i^* Z_i' \right), \quad (245) $$

$$ \frac{1}{n} \frac{d^2 F_{n,\epsilon}(t)}{dR_1^2} = \langle \mathcal{L}^2 \rangle - \langle \mathcal{L} \rangle^2 - \frac{1}{4n^2 R_1^{3/2}} \sum_{i=1}^{n} \langle x_i \rangle Z_i'. \quad (246) $$

Averaging (245) and (246), using a Gaussian integration by parts w.r.t. $Z_i'$ and the (Nishimori) identity $\mathbb{E}[\langle x_i X_i^* \rangle] = \mathbb{E}[\langle x_i \rangle^2]$ we find

$$ \frac{df_{n,\epsilon}(t)}{dR_1} = -\mathbb{E}\langle\mathcal{L}\rangle - \frac{\rho}{2} = \frac{1}{2n} \sum_{i=1}^{n} \mathbb{E}[\langle x_i \rangle^2] - \frac{\rho}{2}, \quad (247) $$

$$ \frac{1}{n} \frac{d^2 f_{n,\epsilon}(t)}{dR_1^2} = \mathbb{E}[\langle \mathcal{L}^2 \rangle - \langle \mathcal{L} \rangle^2] - \frac{1}{4n^2 R_1} \sum_{i=1}^{n} \mathbb{E}[\langle x_i^2 \rangle - \langle x_i \rangle^2]. \quad (248) $$

**Proof of Lemma 29**

From (248) we have

$$ \begin{aligned} \mathbb{E}\langle (\mathcal{L} - \langle \mathcal{L} \rangle)^2 \rangle &= \frac{1}{n} \frac{d^2 f_{n,\epsilon}(t)}{dR_1^2} + \frac{1}{4n^2 R_1} \sum_{i=1}^{n} \mathbb{E}[\langle x_i^2 \rangle - \langle x_i \rangle^2] \\ &\le \frac{1}{n} \frac{d^2 f_{n,\epsilon}(t)}{dR_1^2} + \frac{\rho}{4n\epsilon_1}, \end{aligned} \quad (249) $$

where we used $\mathbb{E}[\langle x_i^2 \rangle] = \mathbb{E}_{P_0}[(X^*)^2] = \rho$ by the Nishimori identity, and $R_1 \ge \epsilon_1$. Recall $\mathcal{B}_n := [s_n, 2s_n]^2$. By assumption $q$ and $r$ are regular. Therefore $R^t := (\epsilon_1, \epsilon_2) \mapsto (R_1(t, \epsilon), R_2(t, \epsilon))$ is a diffeomorphism whose
Jacobian $J(R^t)$ verifies $J(R^t)(\epsilon) \ge 1$ for all $\epsilon \in \mathcal{B}_n$. Integrating over $\epsilon \in \mathcal{B}_n$ we obtain

$$ 
\begin{aligned}
\int_{\mathcal{B}_n} d\epsilon \mathbb{E}\langle (\mathcal{L} - \langle \mathcal{L} \rangle)^2 \rangle &\le \frac{1}{n} \int_{R^t(\mathcal{B}_n)} \frac{dR_1 dR_2}{J(R^t)} \frac{d^2 f_{n,\epsilon}(t)}{dR_1^2} + \frac{\rho s_n}{4n} \int_{s_n}^{2s_n} \frac{d\epsilon_1}{\epsilon_1} \\
&\le \frac{1}{n} \int_{R^t(\mathcal{B}_n)} dR_1 dR_2 \frac{d^2 f_{n,\epsilon}(t)}{dR_1^2} + \frac{\rho s_n}{4n} \ln 2,
\end{aligned} 
\quad (250) $$

where in the integral above $J(R^t)$ is a function of $(R^t)^{-1}(R_1, R_2)$. Note that from (89) we have $R^t(\mathcal{B}_n) \subset [s_n, 2s_n + r_{\max}] \times [s_n, 2s_n + \rho]$ and therefore

$$ 
\begin{aligned}
\int_{\mathcal{B}_n} d\epsilon \mathbb{E}\langle (\mathcal{L} - \langle \mathcal{L} \rangle)^2 \rangle &\le \frac{1}{n} \int_{s_n}^{2s_n+\rho} dR_2 \left\{ \frac{df_{n,\epsilon}(t)}{dR_1} \Big|_{R_1=s_n} - \frac{df_{n,\epsilon}(t)}{dR_1} \Big|_{R_1=2s_n+r_{\max}} \right\} + \frac{\rho s_n}{4n} \ln 2 \\
&\le \frac{\rho(s_n + \rho)}{n} + \frac{\rho s_n}{4n} \ln 2
\end{aligned} 
\quad (251) $$

using (247) combined with $\mathbb{E}\langle x_i^2 \rangle = \rho$ to assert that the derivative of the free entropy is bounded in absolute value by $\rho/2$. This concludes the proof of Lemma 29 using $s_n \le 1/2$ and $(\ln 2)/4 < 1$. $\square$

## Proof of Lemma 30

Consider the two functions

$$ \tilde{F}(R_1) := F_{n,\epsilon}(t) - \frac{\sqrt{R_1}}{n} S \sum_{i=1}^{n} |Z'_{i}|, \quad \tilde{f}(R_1) := \mathbb{E} \tilde{F}(R_1) = f_{n,\epsilon}(t) - \frac{\sqrt{R_1}}{n} S \sum_{i=1}^{n} \mathbb{E} |Z'_{i}|. \quad (252) $$

Because of (246) we see that the second derivative of $\tilde{F}(R_1)$ is positive so that it is convex (without this extra term $F_{n,\epsilon}(t)$ is not necessarily convex in $R_1$, although $f_{n,\epsilon}(t)$ is, which can be shown easily). Note that $\tilde{f}(R_1)$ is convex too. Convexity allows us to use the following lemma (proved at the end of this section):

**Lemma 31 (A bound on differences of derivatives due to convexity).** Let $G(x)$ and $g(x)$ be convex functions. Let $\delta > 0$ and define $C_{\delta}^{+}(x) := g'(x + \delta) - g'(x) \ge 0$ and $C_{\delta}^{-}(x) := g'(x) - g'(x - \delta) \ge 0$. Then

$$ |G'(x) - g'(x)| \le \delta^{-1} \sum_{u \in \{x-\delta, x+\delta\}} |G(u) - g(u)| + C_{\delta}^{+}(x) + C_{\delta}^{-}(x). $$

From (252)

$$ \tilde{F}(R_1) - \tilde{f}(R_1) = F_{n,\epsilon}(t) - f_{n,\epsilon}(t) - \sqrt{R_1} S A, \quad \text{with} \quad A = \frac{1}{n} \sum_{i=1}^{n} (|Z'_{i}| - \mathbb{E}|Z'_{i}|). \quad (253) $$

and from (245), (247) we obtain for the difference of derivatives (w.r.t. $R_1$)

$$ \tilde{F}'(R_1) - \tilde{f}'(R_1) = \mathbb{E}\langle \mathcal{L} \rangle - \langle \mathcal{L} \rangle + \frac{\rho}{2} - \frac{1}{2n} \sum_{i=1}^{n} \left( (X_{i}^{*})^{2} + \frac{1}{\sqrt{R_{1}}} X_{i}^{*} Z'_{i} \right) - \frac{SA}{2\sqrt{R_{1}}}. \quad (254) $$
From (253), (254) it is easy to show that Lemma 31 implies

$$ \begin{aligned} |\langle \mathcal{L} \rangle - \mathbb{E}\langle \mathcal{L} \rangle| \le \delta^{-1} \sum_{u \in \{R_1-\delta, R_1, R_1+\delta\}} & (|F_{n,\epsilon}(t, R_1=u) - f_{n,\epsilon}(t, R_1=u)| + S|A|\sqrt{u}) \\ & + C_{\delta}^{+}(R_1) + C_{\delta}^{-}(R_1) + \frac{S|A|}{2\sqrt{\epsilon_1}} + \left|\frac{\rho}{2} - \frac{1}{2n}\sum_{i=1}^{n} \left((X_i^*)^2 + \frac{1}{\sqrt{R_1}}X_i^*Z_i'\right)\right| \end{aligned} \quad (255) $$

where $C_{\delta}^{+}(R_1) := \tilde{f}'(R_1 + \delta) - \tilde{f}'(R_1) \ge 0$ and $C_{\delta}^{-}(R_1) := \tilde{f}'(R_1) - \tilde{f}'(R_1 - \delta) \ge 0$. We used $R_1 \ge \epsilon_1$ for the term $S|A|/(2\sqrt{\epsilon_1})$. Note that $\delta$ will be chosen later on strictly smaller than $s_n$ (namely $\delta = s_n n^{-1/4}$) so that $R_1 - \delta \ge \epsilon_1 - \delta \ge s_n - \delta$ remains positive. Remark that by independence of the noise variables $\mathbb{E}[A^2] \le an^{-1}$ for some constant $a > 0$; and that by independence between signal and noise, the last term in the absolute value in (255), call it $B$, is satisfies $\mathbb{E}[B^2] \le bn^{-1}$ for some constant $b > 0$. We now square the identity (255) and take its expectation. Then using $(\sum_{i=1}^p v_i)^2 \le p \sum_{i=1}^p v_i^2$ (by convexity), and that $R_1 \le K$ ($K = 1+\max(\rho, r_{\max})$ upper bounds both $R_1$ and $R_2$ given by (89)), as well as the free entropy concentration Theorem 6,

$$ \frac{1}{10} \mathbb{E}[(\langle \mathcal{L} \rangle - \mathbb{E}\langle \mathcal{L} \rangle)^2] \le 3\delta^{-2}(C + aS^2(K + \delta))\frac{1}{n} + C_{\delta}^{+}(R_1)^2 + C_{\delta}^{-}(R_1)^2 + \frac{S^2a}{4\epsilon_1n} + \frac{b}{n}. \quad (256) $$

where $C = C(\varphi, S, \alpha)$ is a positive constant depending only on $\varphi, S$ and $\alpha$ that comes from the use of Theorem 6. Recall $|C_{\delta}^{\pm}(R_1)| = |\tilde{f}'(R_1 \pm \delta) - \tilde{f}'(R_1)|$. We have

$$ |\tilde{f}'(R_1)| \le \frac{1}{2}\left(\rho + \frac{S}{\sqrt{R_1}}\right) \le \frac{1}{2}\left(\rho + \frac{S}{\sqrt{\epsilon_1}}\right) \quad (257) $$

from (247), (252) and $R_1 \ge \epsilon_1$. This implies $|C_{\delta}^{\pm}(R_1)| \le \rho + S/\sqrt{\epsilon_1} \le \rho + S/\sqrt{s_n}$ as $\epsilon_1 \ge s_n$. Recall also that $B_n := [s_n, 2s_n]^2$. Then

$$ \begin{aligned} & \int_{B_n} d\epsilon \{C_{\delta}^{+}(R_1(t, \epsilon))^2 + C_{\delta}^{-}(R_1(t, \epsilon))^2\} \\ & \le \left(\rho + \frac{S}{\sqrt{s_n}}\right) \int_{B_n} d\epsilon \{C_{\delta}^{+}(R_1(t, \epsilon)) + C_{\delta}^{-}(R_1(t, \epsilon))\} \\ & = \left(\rho + \frac{S}{\sqrt{s_n}}\right) \int_{R^t(B_n)} \frac{dR_1 dR_2}{J(R^t)} \{C_{\delta}^{+}(R_1) + C_{\delta}^{-}(R_1)\} \\ & \le \left(\rho + \frac{S}{\sqrt{s_n}}\right) \int_{R^t(B_n)} dR_1 dR_2 \{C_{\delta}^{+}(R_1) + C_{\delta}^{-}(R_1)\} \\ & \le \left(\rho + \frac{S}{\sqrt{s_n}}\right) \int_{s_n}^{2s_n+\rho} dR_2 \left[\left(\tilde{f}(2s_n + r_{\max} + \delta) - \tilde{f}(2s_n + r_{\max} - \delta)\right) \right. \\ & \qquad \left. + \left(\tilde{f}(s_n - \delta) - \tilde{f}(s_n + \delta)\right)\right]. \end{aligned} \quad (258) $$

where we used that the Jacobian $J(R^t)$ of the $C^1$ diffeomorphism $R^t: (\epsilon_1, \epsilon_2) \mapsto (R_1(t, \epsilon), R_2(t, \epsilon))$ is greater or equal to 1 (by regularity of the interpolation functions $q$ and $r$) and $R^t(B_n) \subset [s_n, 2s_n+r_{\max}] \times [s_n, 2s_n+\rho]$. The mean value theorem and (257) imply $|\tilde{f}(R_1-\delta) - \tilde{f}(R_1+\delta)| \le \delta(\rho+S/\sqrt{s_n})$ uniformly in $R_2$. Therefore

$$ \int_{B_n} d\epsilon \{C_{\delta}^{+}(R_1(t, \epsilon))^2 + C_{\delta}^{-}(R_1(t, \epsilon))^2\} \le 2\delta(s_n + \rho) \left(\rho + \frac{S}{\sqrt{s_n}}\right)^2. \quad (259) $$
Thus, integrating (256) over $\epsilon \in \mathcal{B}_n$ yields (using $\mathrm{Vol}(\mathcal{B}_n) = s_n^2$ and $s_n \le 1/2$)

$$ \int_{\mathcal{B}_n} d\epsilon \mathbb{E}[(\langle \mathcal{L} \rangle - \mathbb{E}[\langle \mathcal{L} \rangle])^2] \\ \le 30(C + aS^2\sqrt{K+\delta})\delta^{-2}s_n^2n^{-1} + 20\delta(1/2 + \rho)\left(\rho + \frac{S}{\sqrt{s_n}}\right)^2 + 5S^2a\frac{\ln 2}{2}\frac{s_n}{n} + \frac{bs_n^2}{n}. $$

Finally we choose $\delta = s_n n^{-1/4}$ and obtain the desired result. □

*Proof of Lemma 31:* Convexity implies that for any $\delta > 0$ we have

$$ G'(x) - g'(x) \le \frac{G(x + \delta) - G(x)}{\delta} - g'(x) \\ \le \frac{G(x + \delta) - G(x)}{\delta} - g'(x) + g'(x + \delta) - \frac{g(x + \delta) - g(x)}{\delta} \\ = \frac{G(x + \delta) - g(x + \delta)}{\delta} - \frac{G(x) - g(x)}{\delta} + C_{\delta}^{+}(x), $$

$$ G'(x) - g'(x) \ge \frac{G(x) - G(x - \delta)}{\delta} - g'(x) + g'(x - \delta) - \frac{g(x) - g(x - \delta)}{\delta} \\ = \frac{G(x) - g(x)}{\delta} - \frac{G(x - \delta) - g(x - \delta)}{\delta} - C_{\delta}^{-}(x). $$

Combining these two inequalities ends the proof. □

# Appendix F: Details on numerics

Most of our experiments and codes are provided on the associated GitHub repository [62], with codes in the Julia programming language [103] (with a Jupyter notebook interface) and in matlab. In this appendix, we shall give additional details on how the plots have been obtained.

## F.1 General purpose algorithms

We have been using free available softwares in our experiments: Standard machine learning tasks such as LASSO or logistic regression were done using scikit-learn [65]. Keras [66], with a tensorflow backend [104], was used for neural networks. We also used CVXPY, a python-embedded language for performing convex optimization [84], as well as PhaseMax for phase retrieval [85] experiments.

Figure 4 (in both the main text and SI) contrasts results of these general purpose algorithms with the optimal generalization error in three classification problems. In the left panel of Fig. 4 (for the binary perceptron), we used logistic regression with hand-tuned $\ell_2$ regularization (basically, we have hand-selected the regularization parameter in order to obtain the best results) with the function Logistic Regression in the software scikit-learn [65]. In the center panel of Fig. 4 (this time for a sparse signal), we used the same software but this time with a sparsity enhancing $\ell_1$ regularization, again fine-tuned by hand. In the right panel of Fig. 4, we show, in the inset, how a neural network with 2 hidden layers was able to learn only approximately the “symmetric door” rule. In this experiment, we used Keras with a tensorflow backend.

The data are created with a signal-vector of dimension $n = 2500$ and are sent into a network made with a first layer of dimension $2500 \times 64$ followed by a rectified linear unit (ReLU), and a dropout layer with fraction 0.2 for regularization. This is followed by a second layer of dimension $64 \times 64$, this time with a sigmoid activation and again a dropout layer. Finally, we classify with a final output layer with a softmax, using the categorical cross-entropy as the loss function. The minimization is done using the RMSprop optimizer for 1000 epochs. The code is shown in the GitHub repository [62].
We have tried many variations around this network. Interestingly, the dropout layers have a strong effect on the regularization, and help significantly in improving the generalization error. Also interestingly, the number of epochs used for fitting was an important parameter. Indeed, the quality of the fit improves drastically as the number of epochs is increased: It seems that it actually takes a lot of time to escape the initial point, where prediction is just as bad as random. Finally, we also tried to increase the depth of the neural nets. Interestingly this did not affect the performance and the network was fitting the data and generalizing just as well with deeper and deeper networks. We believe that it should be very instructive to further study empirically this problem.

In Fig. 5 in this SI, similar plots are shown for three regression problems. In the left panel, we used the LASSO function in the software scikit-learn [65] with its sparsity enhancing $\ell_1$ regularization, again fine-tuned by hand.

For the middle panel, we had to turn to a different software. In this case, the idea was to solve $\mathbf{Y} = \operatorname{Relu}(\mathbf{\Phi x}) = \max(0, \mathbf{\Phi x})$ (componentwise) subject to a sparse penalty on $\mathbf{x}$. Luckily, this can be turned into a linear programming framework: Minimize the $\ell_1$ norm of $\mathbf{x}$ subject to the constraint that $\mathbf{Y} = \operatorname{Relu}(\mathbf{\Phi x})$ which can be implemented by enforcing $Y_{\mu} = \mathbf{\Phi}_{\mu} \cdot \mathbf{x}$ for $\mu$'s such that $Y_{\mu} > 0$, and $\mathbf{\Phi}_{\mu} \cdot \mathbf{x} < 0$ for $\mu$'s such that $Y_{\mu} = 0$. This linear program is solved with CVXPY [84] (CVX-2). We also show the results when only the indices $\mu$ associated with positive $Y_{\mu} > 0$ are used for comparison (CVX-1). Finally, for the right figure, we used PhaseMax [85] out-of-the-box to solve the problem.

## F.2 Evaluating the replica formula

In order to evaluate numerically the replica formula (41) we proceed as it is common in the statistical physics literature since the early papers on spin glasses. First, we found the critical points (42) by iterating the state evolution equations (67)—also called the replica self-consistent equations—starting from two different initial conditions ($q^{t=0} = 0$ and $q^{t=0} = \rho$). Next we computed the associated value of the free entropy and then selected, if two different fixed points were found, the correct one following the prescription given by Theorem 1. We also took special care in checking that we could not identify other fixed points. An example of such a procedure is shown in the GitHub repository [62], with codes in the Julia programming language [103], for the perceptron problem.

## F.3 Breaking the symmetry in GAMP

A last notable point concerns the symmetry issue in GAMP. Indeed, when $q = 0$ is a fixed point of the state evolution (which is the case if the prior has zero mean and the channel is symmetric), then GAMP should stay in this fixed point forever. This is the case, for instance, for two problems considered in the present paper: The symmetric door output function $\varphi(z) = \operatorname{sgn}(|z| - K)$ with a Rademacher prior $\pm 1$, and for the sign-less channel $\varphi(z) = |z|$. In both cases, both $z$ and $-z$ are giving the same output, and therefore so does both $\mathbf{X}^*$ and $-\mathbf{X}^*$. Notice, however, that this is not a problem in the computation of the free entropy. Here, one has to compute all the fixed points anyway. It is also not a problem if the prior is breaking the symmetry (for instance if one is working with a binary signal where $X_i^* = 1$ with probability $p_+ = 1/2 + \epsilon$ and $X_i^* = -1$ with probability $p_- = 1/2 - \epsilon$ with, say, $\epsilon = 10^{-7}$). In this case the symmetry is broken, GAMP works, and the state evolution predicts its behavior correctly. Even though this problem is thus restricted to a very small class of channels and priors, and even though perturbations solve it, it is still an interesting mathematical challenge, especially from the rigorous point of view. Indeed, this problem has attracted attention recently where initializations based on spectral algorithms were analyzed [61].

In the present paper, we adopted a pragmatic point of view. We did not break the symmetry in the data generative model (as that would make the problem slightly easier), instead we broke the symmetry in the GAMP solver, thus making it slightly but un-noticeably suboptimal. An example of our code is given in the
associated GitHub repository [62]. We created the data in the symmetric manner, but when we ran GAMP to solve the problem, we broke the channel symmetry slightly. For instance, instead of solving with a door function that returns 1 only for $-0.674489 < z < 0.674489$, we use a function that instead returned 1 for $-0.674489 < z < 0.6745$. The same strategy was used for the absolute value function, which can be replaced by $\varphi(z) = z$ for $x > -\epsilon$ and $-z$ otherwise. Again, when $\epsilon$ is small, this makes only an unnoticeable difference in the figures. This trick allowed GAMP to solve symmetric problems without trouble in practice, and to reach perfect recovery even in the symmetric problems as close to the theoretical threshold as numerically desired.