TITLE: Proving a logic statement using valuations.
QUESTION [0 upvotes]: Let $\Phi \subseteq L_{\Sigma}$ where $\Sigma$ is the set of all propositional symbols $p, q, r,\dots$ and $L_{\Sigma}$ de set of well formed formulas formed from $\Sigma$. Show that $\Phi \cup \{ \varphi_1,\dots, \varphi_n\} \models \psi$ implies $\Phi \models \varphi_1 \rightarrow \dots \rightarrow \varphi_n \rightarrow \psi$

I tried to prove it using induction on $n$ but I got a little confused. Here is what I did:
Take a valuation $v$ such that $v \models \Phi$. What I want to see is that $v \models \varphi_1 \rightarrow \dots \rightarrow \varphi_n \rightarrow \psi$ also holds.
If $n = 1$, then we have only two cases:
In the first one, $v \not \models \varphi_1$, so $v \models \varphi_1 \rightarrow \psi$ and we are done. The other possible case is where $v \models \varphi_1$. But then $v \models \Phi$ and $v \models \varphi_1$, so $v \models \Phi \cup \{ \varphi_1 \}$, and by hypothesis, then $v \models \psi$, so $v \models \varphi$ and $v \models \psi$, therefore, $v \models \varphi_1 \rightarrow \psi$.
Now this is where I got stuck. I don't know how to proceed from there. I tried to do the same thing distinguishing cases but I think it is wrong. Like before, there can be two cases: $v \models \varphi_{n+1}$ or $v \not \models \varphi_{n+1}$.
If the case is the latter, then $v \models \varphi_{n+1} \rightarrow \psi$, but can I use the induction hypothesis to conclude that
$$v \models \varphi_1 \rightarrow \dots \rightarrow \varphi_n \rightarrow \varphi_{n+1} \rightarrow \psi?$$
And again, if $v \models \varphi_{n+1}$ and having that $v \models \varphi_1 \rightarrow \dots \rightarrow \varphi_n \rightarrow \psi$, can I conclude that
$$v \models \varphi_1\rightarrow \dots \rightarrow \varphi_n \rightarrow \varphi_{n+1} \rightarrow\psi?$$
Thank you very much for your help!
Minor edit I'm assuming that the conditional $\rightarrow$ associates to the right, that is, $\varphi_1 \rightarrow \varphi_2 \rightarrow \varphi_3 \equiv \varphi_1 \rightarrow\left( \varphi_2 \rightarrow \varphi_3 \right)$ and so on.

REPLY [0 votes]: Note that the connective sequence $a\to b\to c\to d$ is implicily nested as $a\to\big(b\to(c\to d)\big)$.
Then your inductive step would be to equivate, for any $S,T$, these sequents:
$$\begin{array}{rcl}S\cup \{\varphi_k\}&\models& T\\ S&\models&\big(\varphi_k\to T\big)\end{array}$$
So if you can prove that those two are semantically equivalent, then you will have proven the following iterations are all also equivalencies.
$$\begin{align}\mathbf\Phi\cup\{\varphi_1\ldots\varphi_n\}~&\models~ \psi \\ \mathbf\Phi\cup\{\varphi_1\ldots\varphi_{n-1}\}~&\models~ (\varphi_n\to\psi) \\ &~~\vdots\\ \mathbf\Phi\cup\{\varphi_1\ldots\varphi_k\}~&\models~\Big(\varphi_{k+1}\to\big(\ldots(\varphi_n\to\psi)\!\!\!\cdots\!\!\!\big)\Big) \\ &~~\vdots\\ \mathbf\Phi~&\models~\Big(\varphi_1\to\big(\ldots(\varphi_n\to \psi)\!\!\!\cdots\!\!\!\big)\Big)\end{align}$$


TITLE: Under what conditions do expected value and linear operator commute?
QUESTION [1 upvotes]: Let $X \in L^2[0,1]$ be some squared integrable random function. $(X_n)$ is a sequence of iid realizations of $X$ with $E [X_n] = 0 $ and $E [X_n^4] < \infty$.
$\Psi$ is supposed to be some linear operator $\Psi: L^2[0,1] \rightarrow L^2[0,1]$.
I want to show that
$$
E\big[\Psi ( \langle X_n, x \rangle X_n)\big] = \Psi \big( E [\langle X_n, x \rangle X_n ] \big).
$$
Note that $x$ is some arbitrary function in $L^2$ and $\langle a,b\rangle$ is the inner product $\int a(t) b(t) d t$.
To show the above is no problem if I also assume $\Psi$ to be an integral operator of form $\Psi (X) = \int \psi(s,t) X(s) d s$, but I would like to avoid this specific assumption.
Can I simply put the expected value inside the expression on which I apply the linear operator? Or are additional assumptions necessary?
Thanks for your help!

REPLY [3 votes]: Working on the assumption that you are using $X$ and $X_n$ interchangeably, the answer follows from a simple approximation argument.
Consider a random variable $X$ on a separable Hilbert space $\mathcal{H}$. (We can set $\mathcal{H} = L^2[0,1]$ in OP's case.) Also, denote by $\| \cdot\|$ the induced norm on $\mathcal{H}$.

Assume first that $X$ is simple. That is, $X$ is of the form $\sum_{k=1}^{n} x_k \mathbf{1}_{E_k}$ for some $x_1, \cdots, x_n \in \mathcal{H}$ and disjoint measurable sets $E_1, \cdots, E_n$. Then for any bounded linear operator $\Psi : \mathcal{H} \to \mathcal{H}$,
$$ \mathbb{E} \Psi(X)
= \mathbb{E} \left[ \sum_{k=1}^{n} \Psi(x_k) \mathbf{1}_{E_k} \right]
= \sum_{k=1}^{n} \Psi(x_k) \mathbb{P}(E_k)
= \Psi\left[ \sum_{k=1}^{n} x_k \mathbb{P}(E_k) \right]
= \Psi(\mathbb{E} X). $$
For a general integrable random variable $X$ on $\mathcal{H}$, separability of $\mathcal{H}$ allows us to construct a sequence $(X_n)$ of simple random variables on $\mathcal{H}$ such that $X_n \to X$ in $\mathcal{H}$ and $\|X_n\| \leq \|X\|$ almost surely. Then we also have $\Psi(X_n) \to \Psi(X)$ and $\|\Psi(X_n)\| \leq \|\Psi\|\|X\|$ almost surely. So we can apply the dominated convergence theorem to obtain
$$ \mathbb{E}\Psi(X) \stackrel{\text{DCT}}{=} \lim_{n\to\infty} \mathbb{E}\Psi(X_n) = \lim_{n\to\infty} \Psi(\mathbb{E}X_n) \stackrel{\text{DCT}}{=} \Psi(\mathbb{E}X). $$
Now, if we assume that $X$ is square-integrable in the sense that $\mathbb{E}[\|X\|^2] < \infty$, then for each $x \in \mathcal{H}$ the random variable $\langle X, x\rangle X$ is integrable. So we have
$$ \mathbb{E}[\Psi(\langle X, x \rangle X)] = \Psi(\mathbb{E}[\langle X, x\rangle X]). $$

Not surprisingly, a very general statement continues to hold. You may see here, for instance.


TITLE: Inner Product Convexity
QUESTION [0 upvotes]: Prove set $S$ is convex.
$$S = \{x \in R^2 \mid v^{T}x \geq a\}$$
Can someone explain to me how to prove if this set is convex or not? Are inner products always convex? I know that to prove the set is convex is to show that for all $x,y \in C$ and all $\alpha \in [0,1]$, $\alpha x + (1- \alpha) \in C$.

REPLY [1 votes]: Guide:
Suppose $x_1, x_2 \in S$, that is $v^Tx_i \ge a, i = 1, 2$.
Verify that $v^T(\alpha x_1 + (1-\alpha)x_2) \ge a$.
If you want to check the result for other inner product, rather than working with $v^Tx$, work with $\langle v, x \rangle $ instead.


text:
\section{Proof of the variational formula for the mutual information}\label{sec:proofthm1}
In this section we present the main steps of the proof of Theorem \ref{theorem:limit_mutual_information}. Intermediate results are found in the appendices.
\subsection{Adaptive path interpolation}
We introduce a ``time'' parameter $t \in [0,1]$.
The adaptive interpolation interpolates from the original model \eqref{eq:entries_Y} at $t=0$ to a GLM whose asymptotic mutual information is known \cite{barbierGLM}.
In between, we follow an interpolation path $R(\cdot,\epsilon): [0,1] \to (0,+\infty)$ which is a continuously differentiable function of $t$ parametrized by a ``small'' perturbation $\epsilon \in (0,+\infty)$ and is such that $R(0,\epsilon)=\epsilon$.
More precisely, for $t \in [0,1]$, the observations are:
\begin{align}\label{interpolation_model}
\begin{cases}
\bY^{(t)} \;\; = \frac{\sqrt{\lambda (1-t)}}{n} \bX^{\otimes 3} + \bZ\\
\widetilde{\bY}^{(t,\epsilon)} = \:\sqrt{\frac{\lambda R(t,\epsilon)}{2}}\, \bX \;\, + \widetilde{\bZ}
\end{cases}
\end{align}
where $\bX \triangleq \varphi(\nicefrac{\bW \bS}{\sqrt{p}})$.
The noise vector $\widetilde{\bZ} \in \R^n$ has entries $\widetilde{Z}_1,\dots,\widetilde{Z}_n \iid \cN(0,1)$, while the symmetric noise tensor $\bZ \in (\R^n)^{\otimes 3}$ has entries $\bZ_{\bi} \iid \cN(0,1)$ for $\bi \in \cI \triangleq \{(i_1, i_2, i_3) \in [n]: i_1 \leq i_2 \leq i_3\}$.

Before diving further, we introduce some important quantities and notations. We denote $i_n(t,\epsilon)$ the normalized mutual information between $\bX$ and $(\bY^{(t)},\widetilde{\bY}^{(t,\epsilon)})$ given $\bW$, that is:
\begin{equation}\label{definition_i_n}
	i_n(t,\epsilon) \triangleq \frac{1}{n}I(\bX ; \bY^{(t)},\widetilde{\bY}^{(t,\epsilon)} \vert \bW)
	=\frac{1}{n}I(\bS ; \bY^{(t)},\widetilde{\bY}^{(t,\epsilon)} \vert \bW) \;.
\end{equation}
The last equality holds because $\bX$ is a deterministic function of $\bS$ when $\bW$ is known. Set $dP_s(\bs) = \prod_{i=1}^{p} dP_s(s_i)$ for the prior
distribution of $\bS$.
The {\it usual} Bayesian posterior distribution of $\bS$ given $(\bY^{(t)},\widetilde{\bY}^{(t,\epsilon)}, \bW)$ reads:
\begin{equation}\label{posterior_interpolation}
dP(\bs ; \bY^{(t)},\widetilde{\bY}^{(t,\epsilon)}, \bW) =
\frac{1}{\cZ_{t,\epsilon}(\bY^{(t)},\widetilde{\bY}^{(t,\epsilon)}, \bW)}
dP_s(\bs) \, e^{-\cH_{t,\epsilon}(\bs \,;\, \bY^{(t)},\widetilde{\bY}^{(t,\epsilon)}, \bW)}\;,
\end{equation}
where the normalization factor $\cZ_{t,\epsilon}(\bY^{(t)},\widetilde{\bY}^{(t,\epsilon)}, \bW)$ is simply:
\begin{equation}\label{partition_function}
\cZ_{t,\epsilon}(\bY^{(t)},\widetilde{\bY}^{(t,\epsilon)}, \bW) \triangleq \int dP_s(\bs) \, e^{-\cH_{t,\epsilon}(\bs \,;\, \bY^{(t)},\widetilde{\bY}^{(t,\epsilon)}, \bW)} \;.
\end{equation}
and
\begin{multline}\label{interpolating_hamiltonian}
\cH_{t,\epsilon}(\bs ; \bY^{(t)}, \widetilde{\bY}^{(t,\epsilon)}, \bW)
\triangleq
\sum_{\bi \in \cI}\biggl(
\frac{\lambda(1-t)}{2n^2} x_{i_1}^2 x_{i_2}^2 x_{i_3}^2 - \frac{\sqrt{\lambda(1-t)}}{n}\, Y_{\bi}^{(t)} x_{i_1} x_{i_2} x_{i_3}\bigg)\\
+
\sum_{j=1}^{n} \biggl(\frac{\lambda R(t,\epsilon)}{4} x_j^2 - \sqrt{\frac{\lambda R(t,\epsilon)}{2}}\,\widetilde{Y}_j^{(t,\epsilon)} x_j\biggr) \,,
\end{multline}
with $x_1,\dots,x_n$ the entries of $\bx \triangleq \varphi(\nicefrac{\bW \bs}{\sqrt{p}})$.
This dependence on $\bs$ must be kept in mind each time we use the notation $\bx$. It is common to adopt the statistical mechanics interpretation and call
\eqref{interpolating_hamiltonian} a Hamiltonian, \eqref{partition_function} the partition function and \eqref{posterior_interpolation} the Gibbs distribution.

To deal with future computations, it is useful to introduce the angular brackets $\langle - \rangle_{t,\epsilon}$ (also called Gibbs brackets) which denote an expectation with respect to the posterior distribution \eqref{posterior_interpolation}.
That is, for a generic function $g: \R^p \to \R$, we have:
\begin{equation}
\langle g(\bs) \rangle_{t,\epsilon} \triangleq \int \!g(\bs)\,dP(\bs ; \bY^{(t)},\widetilde{\bY}^{(t,\epsilon)}, \bW)\:.
\end{equation}
Finally, we define the so-called average free entropy:
\begin{equation}\label{interpolating_free_entropy}
f_n(t,\epsilon) \triangleq \frac1n \E \ln \cZ_{t,\epsilon}(\bY^{(t)},\widetilde{\bY}^{(t,\epsilon)}, \bW)\;.
\end{equation}
This is equal to the mutual information $i_n(t,\epsilon)$ up to some additive term (see formula \eqref{link_i_n_f_n} in Lemma~\ref{lemma:link_i_n_f_n} in Appendix~\ref{app:establishing_sum_rule}). It is often easier to work directly with $f_n(t,\epsilon)$ instead of $i_n(t,\epsilon)$.

We now focus on the mutual information \eqref{definition_i_n} at both extremes of the interpolation path.
Letting $t=0$ in \eqref{interpolation_model}, we see that the observation $\bY^{(0)}$ is exactly \eqref{eq:entries_Y},
while $\widetilde{\bY}^{(0,\epsilon)} = \sqrt{\frac{\lambda \epsilon}{2}} \bX + \widetilde{\bZ}$.
This latter channel induces a perturbation to the normalized mutual information of the former channel of the order of $\epsilon$ (see Lemma~\eqref{lemma:link_i_n_f_n} in Appendix~\ref{app:establishing_sum_rule} for the proof), that is:
\begin{equation}\label{i_n_t=0}
i_n(0,\epsilon)
\triangleq \frac{1}{n}I(\bX ; \bY^{(0)},\widetilde{\bY}^{(0,\epsilon)} \vert \bW)
=\frac{I(\bX ; \bY \vert \bW)}{n} + \cO(\epsilon) \;,
\end{equation}
where $\vert \cO(\epsilon) \vert \leq C \epsilon$.
At $t=1$ the observation $\bY^{(1)}$ is pure noise, while the normalized mutual information between $\bS$ and $\widetilde{\bY}^{(1,\epsilon)} = \sqrt{\nicefrac{\lambda R(1,\epsilon)}{2}} \, \varphi(\nicefrac{\bW \bS}{\sqrt{p}}) + \widetilde{\bZ}$ is given by a variational formula in the high-dimensional regime $\nicefrac{n}{p} \to \alpha$ \cite{barbierGLM}.
Let $S \sim P_S$ and $U,V,Z,\widetilde{Z} \sim \cN(0,1)$ independent scalar random variables. Define the potential function $\widetilde{\psi}_\alpha:  [0,+\infty)^2 \times [0,\rho_s]$:
\begin{multline}
\widetilde{\psi}_\alpha(r, r_s, q_s) \triangleq
I(S;\sqrt{r_s}\,S + Z) + \alpha I\big(U; \sqrt{r}\,\varphi(\sqrt{\rho_s - q_s} \, U + \sqrt{q_s} \, V) + \widetilde{Z} \,\big\vert\, V \big) - \frac{r_s(\rho_s - q_s)}{2} \;.
\end{multline}
By \cite[Corollary 1]{barbierGLM}, we have:
\begin{equation}\label{i_n_t=1}
i_n(1,\epsilon)
= \frac{1}{n}I(\bX ; \widetilde{\bY}^{(1,\epsilon)} \vert \bW)
= \smallO_n(1) + \frac{1}{\alpha} \,\adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;
\widetilde{\psi}_\alpha\bigg(\frac{\lambda R(1,\epsilon)}{2} , r_s, q_s\bigg) \;.
\end{equation}
Combining \eqref{i_n_t=0}, \eqref{i_n_t=1} and the fundamental theorem of calculus $i_n(0,\epsilon)=i_n(1,\epsilon)-\int_{0}^{1}i_n^{\prime}(t,\epsilon) dt$, where $i_n^{\prime}(\cdot,\epsilon)$ is the derivative of $i_n(\cdot,\epsilon)$ w.r.t.\ its first argument, we obtain the sum-rule of the adaptive interpolation.
\begin{proposition}[Sum-rule]\label{prop:sum_rule}
Suppose that \ref{hyp:S_bounded_support} and \ref{hyp:varphi} hold, and that $R'(t,\epsilon)$ is uniformly bounded in $(t,\epsilon) \in [0,1] \times [0,+\infty)$ where $R'(\cdot,\epsilon)$ denotes the derivative of $R(\cdot,\epsilon)$ with respect to its first argument.
Define the scalar overlap
$$
Q \triangleq \frac{1}{n} \sum\limits_{i=1}^{n} \varphi\big(\big[\nicefrac{\bW \bs}{\sqrt{p}}\big]_i \,\big) \varphi\big(\big[\nicefrac{\bW \bS}{\sqrt{p}}\big]_i \,\big)
= \frac{1}{n} \sum_{i=1}^{n} x_i X_i \;.
$$
Then:
\begin{multline}\label{sum_rule}
\frac{I(\bX ; \bY \vert \bW)}{n}
= \cO(\epsilon) + \smallO_n(1)
 + \frac{1}{\alpha}\,\adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;
\widetilde{\psi}_\alpha\bigg(\frac{\lambda R(1,\epsilon)}{2} , r_s, q_s\bigg)\\
-\frac{\lambda}{12} \int_0^1 \big(\E\,\langle Q^3 \rangle_{t,\epsilon} - \rho_x^3\big)dt
- \frac{\lambda}{4} \int_0^1 R'(t,\epsilon)\big(\rho_x - \E\,\langle Q \rangle_{t,\epsilon}\big)dt\;,
\end{multline}
where $\smallO_n(1)$ and $\mathcal{O}(\epsilon)$ are independent of $\epsilon$ and $n$, respectively.
\begin{IEEEproof}
See Lemma~\ref{lemma:formula_derivative_free_entropy} in Appendix~\ref{app:establishing_sum_rule} for the computation
of the derivative $i_n^{\prime}(t,\epsilon)$.
\end{IEEEproof}
\end{proposition}

The sum rule of Proposition~\ref{prop:sum_rule} is valid for the general class of differentiable interpolating paths. By choosing two appropriate interpolation paths we can prove matching upper and lower bounds on the asymptotic normalized mutual information. This is discussed in the next two paragraphs.

\subsection{Upper bound on the asymptotic normalized mutual information}\label{subsec:upper_bound}

\begin{proposition}\label{prop:upperbound_mutual_info}
Suppose that \ref{hyp:S_bounded_support} and \ref{hyp:varphi} hold. Then:
\begin{equation}
\limsup_{n \to +\infty} \frac{I(\bX ; \bY \vert \bW)}{n} \leq \inf_{q_x \in [0,\rho_x]} \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;\psi_{\lambda,\alpha}\big(q_x, q_s, r_s\big)\;.
\end{equation}
\end{proposition}

\begin{IEEEproof}
Fix $\epsilon > 0$ and pick the linear interpolation path $R(t,\epsilon) = \epsilon + t q^2$ where $q \in [0,\rho_x]$.
Then the sum-rule \eqref{sum_rule} in Proposition~\ref{prop:sum_rule} reads:
\begin{align}
& \frac{I(\bX ; \bY \vert \bW)}{n}
= \cO(\epsilon) + \smallO_n(1)
+ \frac{1}{\alpha} \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;
\widetilde{\psi}_\alpha\bigg(\frac{\lambda \epsilon}{2} + \frac{\lambda q^2}{2}, r_s, q_s\bigg)
+\frac{\lambda}{12} \rho_x^3
- \frac{\lambda}{4} q^2 \rho_x
\nonumber\\&
\qquad\qquad\qquad\qquad\qquad
-\frac{\lambda}{12} \int_0^1 \bigg(\E\,\langle Q^3 \rangle_{t,\epsilon} - \E\bigg[\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^4\langle Q \rangle_{t,\epsilon}\bigg]\bigg)dt
\nonumber\\&
\qquad\qquad\qquad\qquad\qquad
-\frac{\lambda}{12}\int_0^1 \bigg(\E\bigg[\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^4\langle Q \rangle_{t,\epsilon}\bigg]- 3 q^2 \, \E\langle Q \rangle_{t,\epsilon} \bigg) dt\;. \label{sum_rule_linear_path}
\end{align}
In this last identity, we "artificially" added and subtracted the term $\E\big[\big\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \big\Vert^4\langle Q \rangle_{t,\epsilon}\big]$ for reasons that will appear immediately.
By the Nishimori identity\footnote{
	In our setting, the  Nishimori identity states that ${\E\langle g(\bs,\bS)\rangle_{t,\epsilon} = \E\langle g(\bs,\bs') \rangle_{t,\epsilon} = \E\langle g(\bS,\bs) \rangle_{t,\epsilon}}$ where $\bs,\bs'$ are two samples drawn independently from the posterior distribution of $\bS$ given $(\bY^{(t)}, \widetilde{\bY}^{(t,\epsilon)}, \bW)$.
	It is a direct consequence of Bayes' theorem.
	Here $g$ can also explicitly depend on $\bY^{(t)}, \widetilde{\bY}^{(t,\epsilon)}, \bW$ so the identity holds for $\bX = \varphi(\frac{\bW \bS}{\sqrt{p}}), \bx = \varphi(\frac{\bW \bs}{\sqrt{p}}), \bx' = \varphi(\frac{\bW \bs'}{\sqrt{p}})$ too.},
we have
\begin{equation}
\E\bigg[\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^4\langle Q \rangle_{t,\epsilon}\bigg]
= \E\,\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^6,
\quad \E\langle Q \rangle_{t,\epsilon} = \E\,\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^2 \;,
\end{equation}
and, by convexity of $x \mapsto x^3$ on $[0,+\infty)$, we have $\forall a,b \geq 0: a^3 - 3b^2 a \geq -2 b^3$.
Hence the integrand of the last integral on the right-hand side of \eqref{sum_rule_linear_path} satisfies:
\begin{equation}\label{lowerbound_convexity_x^3}
\E\bigg[\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^4\langle Q \rangle_{t,\epsilon}\bigg]- 3 q^2 \, \E\langle Q \rangle_{t,\epsilon}
= \E\bigg[\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^6 - 3 q^2 \bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^2 \bigg]
\geq - 2 q^3 \;.
\end{equation}
Besides, by Lemma~\ref{lemma:properties_functions} in Appendix \ref{app:useful_lemmas}, the function $r \mapsto \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\; \widetilde{\psi}_\alpha(q, r_s, q_s)$ is nondecreasing and $(\alpha/2) \Vert \varphi \Vert_{\infty}^2$-Lipschitz. Thus:
\begin{equation}\label{upperbound_psi_epsilon}
\adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\; \widetilde{\psi}_\alpha\bigg(\frac{\lambda \epsilon}{2} + \frac{\lambda q^2}{2}, r_s, q_s\bigg) \leq \frac{\lambda \alpha \Vert \varphi \Vert_{\infty}^2}{4} \epsilon + \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\; \widetilde{\psi}_\alpha\bigg(\frac{\lambda q^2}{2}, r_s, q_s\bigg) \;.
\end{equation}
Therefore, making use of \eqref{lowerbound_convexity_x^3} and \eqref{upperbound_psi_epsilon} to upper bound \eqref{sum_rule_linear_path} yields:
\begin{align}
\frac{I(\bX ; \bY \vert \bW)}{n}
&\leq \cO(\epsilon) + \smallO_n(1)
+ \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;
\frac{1}{\alpha}\widetilde{\psi}_\alpha\bigg(\frac{\lambda q^2}{2}, r_s, q_s\bigg)
+\frac{\lambda}{12} \rho_x^3
- \frac{\lambda}{4} q^2 \rho_x
+ \frac{\lambda}{6} q^3\nonumber\\
&\qquad\qquad\qquad\qquad\qquad\quad
-\frac{\lambda}{12} \int_0^1 \bigg(\E\,\langle Q^3 \rangle_{t,\epsilon} - \E\bigg[\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^4\langle Q \rangle_{t,\epsilon}\bigg]\bigg)dt\nonumber\\
&= \cO(\epsilon) + \smallO_n(1)
+ \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;
\psi_{\lambda,\alpha}\big(q, q_s, r_s\big)\nonumber\\
&\qquad\qquad\qquad\qquad\qquad\quad
-\frac{\lambda}{12} \int_0^1 \bigg(\E\,\langle Q^3 \rangle_{t,\epsilon} - \E\bigg[\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^4\langle Q \rangle_{t,\epsilon}\bigg]\bigg)dt\;. \label{sum_rule_upper_bound}
\end{align}
where the last equality follows from the trivial identity:
\begin{equation}\label{link_psi_tilde_and_psi}
\psi_{\lambda,\alpha}\big(q, q_s, r_s\big)
= \frac{1}{\alpha}\widetilde{\psi}_\alpha\bigg(\frac{\lambda q^2}{2}, r_s, q_s\bigg)
+\frac{\lambda}{12} \rho_x^3
- \frac{\lambda}{4} q^2 \rho_x
+ \frac{\lambda}{6} q^3 \;.
\end{equation}
It now remains to get rid of the integral on the right-hand side of \eqref{sum_rule_upper_bound}. The integrand satisfies:
\begin{multline}\label{inequality_remainder}
\bigg\vert \E\,\langle Q^3 \rangle_{t,\epsilon} - \E\bigg[\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^4\langle Q \rangle_{t,\epsilon}\bigg]\bigg\vert
= \bigg\vert \E\,\bigg\langle Q \bigg(Q + \bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^2\bigg)
 \bigg(Q - \bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^2\bigg)\bigg\rangle_{\!\! t,\epsilon} \bigg\vert\\
\leq 2 \Vert \varphi \Vert_{\infty}^4 \E\,\bigg\langle \bigg\vert Q - \bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^2\bigg\vert \bigg\rangle_{\!\! t,\epsilon}
\leq 2 \Vert \varphi \Vert_{\infty}^4 \sqrt{\E\,\bigg\langle \!\bigg( Q - \bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}}\bigg\Vert^2 \bigg)^{\!\! 2} \bigg\rangle_{\!\! t,\epsilon}} \;.
\end{multline}
We see that if the overlap $Q \triangleq \nicefrac{\bx^{\sT} \bX}{n}$ would concentrate on $\nicefrac{\langle \bx \rangle_{t, \epsilon}^{\sT} \langle \bx \rangle_{t, \epsilon}}{n}$ then the remaining integral in \eqref{sum_rule_upper_bound} would be negligible.
However, proving such a concentration property is only holds when we average on a well-chosen set of ``perturbations'' $\epsilon$.
In essence, the average over $\epsilon$ smoothens the phase transitions that might appear for particular choices of $\epsilon$ when $n$ goes to infinity.\\
We now take $\epsilon \in [s_n, 2s_n]$ where $s_n \triangleq n^{-\eta}$, $\eta > 0$, and
integrate w.r.t.\ $\epsilon$ on both sides of \eqref{sum_rule_upper_bound}:
\begin{align}\label{sumrule_lowerbound_integration_epsilon}
&\frac{I(\bX ; \bY \vert \bW)}{n} = \int_{s_n}^{2s_n}\frac{I(\bX ; \bY \vert \bW)}{n} \frac{d\epsilon}{s_n}\nonumber\\
&\leq \smallO_n(1) + \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;\psi_{\lambda,\alpha}\big(q, q_s, r_s\big)
-\frac{\lambda}{12} \int_0^1 dt \int_{s_n}^{2s_n} \bigg(\E\,\langle Q^3 \rangle_{t,\epsilon} - \E\bigg[\bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}} \bigg\Vert^4\langle Q \rangle_{t,\epsilon}\bigg]\bigg)\frac{d\epsilon}{s_n}\nonumber\\
&\leq \smallO_n(1) + \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;\psi_{\lambda,\alpha}(q, q_s, r_s)
+ \frac{\lambda \Vert \varphi \Vert_{\infty}^4}{6} \! \int_0^1 \! dt \int_{s_n}^{2s_n} \!\sqrt{\E\,\bigg\langle \!\bigg( Q - \bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}}\bigg\Vert^2 \bigg)^{\!\! 2} \bigg\rangle_{\!\! t,\epsilon}}\,\frac{d\epsilon}{s_n}\;.
\end{align}
Since $R(t,\cdot)$ is a $\mathcal{C}^1$-diffeomorphism from $[s_n,2s_n]$ to its image $R(t, [s_n,2s_n]) \subseteq [s_n, 2s_n + \rho_x^2]$, we  make the change of variables $\epsilon \to R \equiv R(t,\epsilon)$ and obtain (using Cauchy-Schwarz for the first inequality)
for all $t \in [0,1]$:
\begin{align}
\int_{s_n}^{2s_n} \sqrt{\E\,\bigg\langle \!\bigg( Q - \bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}}\bigg\Vert^2 \bigg)^{\!\! 2} \bigg\rangle_{\!\! t,\epsilon}}\,\frac{d\epsilon}{s_n}
&\leq \sqrt{\int_{s_n}^{2s_n} \E\,\bigg\langle \!\bigg( Q - \bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}}\bigg\Vert^2 \bigg)^{\!\! 2} \bigg\rangle_{\!\! t,\epsilon}\,\frac{d\epsilon}{s_n}}\nonumber\\
&=\sqrt{\int_{R(t, [s_n,2s_n])}
\E\,\bigg\langle \!\bigg( Q - \bigg\Vert \frac{\langle \bx \rangle_{t,R}}{\sqrt{n}}\bigg\Vert^2 \bigg)^{\!\! 2} \bigg\rangle_{\!\! t,R}\, \frac{dR}{s_n}}\nonumber\\
&\leq \sqrt{\int_{s_n}^{2s_n + \rho_x^2}
\E\,\bigg\langle \bigg( Q - \bigg\Vert \frac{\langle \bx \rangle_{t,R}}{\sqrt{n}} \bigg\Vert^2\bigg)^{\!\! 2} \bigg\rangle_{\!\! t,R} \,\frac{dR}{s_n}}\;. \label{lowerbound_change_variable}
\end{align}
By Proposition~\ref{prop:concentration_L_on_<L>} in Appendix \ref{app:concentration_overlap} and the inequality \eqref{lowerbound_change_variable}, we get (remember that $s_n \triangleq n^{-\eta}$):
\begin{multline}
\frac{\lambda \Vert \varphi \Vert_{\infty}^4}{6} \int_{s_n}^{2s_n} \sqrt{\E\,\bigg\langle \!\bigg( Q - \bigg\Vert \frac{\langle \bx \rangle_{t,\epsilon}}{\sqrt{n}}\bigg\Vert^2 \bigg)^{\!\! 2} \bigg\rangle_{\!\! t,\epsilon}}\,\frac{d\epsilon}{s_n}\\
\leq \frac{\sqrt{\lambda} \Vert \varphi \Vert_{\infty}^4}{3} \sqrt{\frac{\Vert \varphi \Vert_{\infty}^3}{s_n}\sqrt{\frac{\lambda (s_n + \rho_x^2)}{2n}}}
= \frac{\lambda^{\frac{3}{4}} \Vert \varphi \Vert_{\infty}^{\nicefrac{11}{2}}}{3}
\bigg(\frac{s_n + \rho_x^2}{2}\bigg)^{\frac{1}{4}}
\frac{1}{n^{\frac{1-2\eta}{4}}} \;.
\end{multline}
Therefore, we see that the remainder on the right-hand side of \eqref{sumrule_lowerbound_integration_epsilon} vanishes as $\cO(n^{-\nicefrac{1}{6}})$ if we pick $\eta = \nicefrac{1}{6}$.
Passing to the limit superior on both sides of the inequality \eqref{sumrule_lowerbound_integration_epsilon} then yields:
$$
\limsup_{n \to +\infty} \frac{I(\bX ; \bY \vert \bW)}{n} \leq \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;\psi_{\lambda,\alpha}(q, q_s, r_s) \;.
$$
This inequality is true for all $q \in [0, \rho_x]$ and Proposition~\ref{prop:upperbound_mutual_info} follows directly.
\end{IEEEproof}

\subsection{Matching lower bound on the asymptotic normalized mutual information}

We now prove a matching lower bound by considering a different choice for $R(\cdot,\epsilon)$ in the sum-rule \eqref{sum_rule}.
$R(\cdot,\epsilon)$ will be the solution to a first-order ordinary differential equations (ODE).
We first describe this ODE and give the derivation of the lower bound.

\subsubsection{An ordinary differential equation}

For $t \in [0,1]$ and $R \in [0, +\infty)$, consider the problem of estimating $\bS$ from the observations:
\begin{align}\label{interpolation_model_R}
\begin{cases}
\bY^{(t)} \;\; = \frac{\sqrt{\lambda (1-t)}}{n} \bX^{\otimes 3} + \bZ\\
\widetilde{\bY}^{(t,R)} = \:\sqrt{\frac{\lambda R}{2}}\, \bX \;\, + \widetilde{\bZ}
\end{cases};
\end{align}
where $\bX \triangleq \varphi(\nicefrac{\bW \bS}{\sqrt{p}})$, $S_1,\dots,S_p \iid P_S$.
The noise vector $\widetilde{\bZ} \in \R^n$ has entries $\widetilde{Z}_1,\dots,\widetilde{Z}_n \iid \cN(0,1)$, while the symmetric noise tensor $\bZ \in (\R^n)^{\otimes 3}$ has entries $\bZ_{\bi} \iid \cN(0,1)$ for $\bi \in \cI \triangleq \{(i_1, i_2, i_3) \in [n]: i_1 \leq i_2 \leq i_3\}$.
The posterior distribution of $\bS$ given $(\bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW)$ is:
\begin{equation}\label{posterior_H_t_R}
dP(\bs ; \bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW) =
\frac{1}{\cZ_{t,R}(\bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW)}dP_{S}(\bs) \, e^{-\cH_{t,R}(\bs ; \bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW)} \;.
\end{equation}
where $\cZ_{t,R}(\bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW) = \int  dP_{S}(\bs) \, e^{-\cH_{t,R}(\bs ; \bY^{(t)},\widetilde{\bY}^{(t,R)}, \bW)}$ and
\begin{multline}\label{hamiltonian_model_R}
\cH_{t,R}(\bs ; \bY^{(t)}, \widetilde{\bY}^{(t,R)}, \bW)
\triangleq
\sum_{\bi \in \cI}
\frac{\lambda(1-t)}{2n^2} x_{i_1}^2 x_{i_2}^2 x_{i_3}^2 - \frac{\sqrt{\lambda(1-t)}}{n}\, Y_{\bi}^{(t)} x_{i_1} x_{i_2} x_{i_3}\\
+
\sum_{j=1}^{n} \frac{\lambda R}{4} x_j^2 - \sqrt{\frac{\lambda R}{2}}\,\widetilde{Y}_j^{(t,R)} x_j \;.
\end{multline}
Again, \eqref{hamiltonian_model_R} has the interpretation of a Hamiltonian and \eqref{posterior_H_t_R} a Gibbs distribution.
The Gibbs bracket notation $\langle - \rangle_{t,R}$ denotes the expectation with respect to this last posterior.
Finally, we define the following function used to formulate the ODE satisfied by the interpolation path:
\begin{equation}
G(t, R) = (\E \langle Q \rangle_{t,R})^2\;.
\end{equation}
\begin{lemma}\label{lemma:ode_for_interpolation_path}
Assume $\varphi:\R \to \R$ is continuous and bounded.
For all $\epsilon \in [0,+\infty)$, there exists a unique global solution $R(\cdot,\epsilon): [0,1] \to [0,+\infty)$ to the first-order ODE:
\begin{equation}\label{eq:ODE}
\forall \,t \in [0,1]: \frac{d g(t)}{dt}=G(t,g(t)) \,, \quad g(0)=\epsilon\,.
\end{equation}
This solution is continuously differentiable with bounded derivative (w.r.t.\ $t$) $R'(\cdot, \epsilon)$ and, for any $\delta>0$, $R'([0,1],\epsilon) \subseteq [0, (\rho_x+\delta)^2]$ for $n$ large enough independent of $\epsilon$.
Besides, $\forall \,t \in [0,1]$, $R(t,\cdot)$ is a $\mathcal{C}^1$-diffeomorphism from $[0, +\infty)$ into its image whose derivative w.r.t.\ $\epsilon$ is greater than or equal to one, i.e.,
	\begin{equation}\label{sol_ode_derivative_gretaer_one}
	\forall \,\epsilon \in [0, +\infty): \frac{\partial R}{\partial \epsilon}\Big\vert_{t,\epsilon} \geq 1 \,.
	\end{equation}
\end{lemma}
\begin{remark}
This lemma guarantees a unique global solution $R_n(t,\epsilon)$ for each finite $n$. Slightly abusively we do not indicate the $n$-dependence and simply write $R(t, \epsilon)$ for the solution.
\end{remark}
\begin{IEEEproof}
The function $G: (t, R) \in [0,1] \times [0,+\infty) \mapsto G(t,R)$ is continuous in $t$ and uniformly Lipschitz continuous in $R$ (meaning the Lipschitz constant is independent of $t$).
The later is readily checked by computing the derivative of $G(t,\cdot)$ and showing it is uniformly bounded in $(t, R)$:
\begin{align}
\frac{\partial G}{\partial R}\bigg\vert_{t,R}
&= \frac{\lambda \E\langle Q \rangle_{t, R}}{n} \sum_{i,j=1}^{n} \E[(\langle x_i x_j \rangle_{t,R} - \langle x_i \rangle_{t,R} \langle x_j \rangle_{t,R})^2]
\in [0, 4 \lambda \Vert \varphi \Vert_{\infty}^6 n ] \;.\label{derivative_G_wrt_R}
\end{align}
Therefore, by the Cauchy-Lipschitz theorem, for all $\epsilon \geq 0$ there exists a unique solution $R(\cdot, \epsilon): [0,\gamma] \to [0,+\infty)$ to the initial value problem \eqref{eq:ODE}.
Here $\gamma \in [0,1]$ is such that $[0,\gamma]$ is the maximal interval of existence of the solution.
By the Cauchy-Schwarz inequality and Nishimory identity, we have:
$$
\E \langle Q \rangle_{t, R}
\leq \frac{\E \langle \Vert \bx \Vert \Vert \bX \Vert \rangle_{t,R}}{n}
\leq \frac{1}{n} \sqrt{\E \langle \Vert \bx \Vert^2 \rangle_{t,R} \, \E \Vert \bX \Vert^2 }
= \frac{\E \Vert \bX \Vert^2 }{n}
= \E\bigg[\varphi\bigg(\frac{\bW_{1,\cdot}\,\bS}{\sqrt{p}}\bigg)^{\! 2}\bigg]
\xrightarrow[n \to +\infty]{} \rho_x \;.
$$
See \cite[Lemma 3 of Supplementary material]{Gabrie_TwoLayerGLM_JSTAT_2019} for a proof of the later limit.
Besides, by Nishimori identity, $\E \langle Q \rangle_{t, R} = n^{-1}\E \Vert \langle \bx \rangle_{t,R}\Vert^2$ is nonnegative.
Hence, for any $\delta > 0$, $G$ has its image in $[0, (\rho_x + \delta)^2]$ and $R([0, \gamma],\epsilon) \subseteq [\epsilon, \epsilon + \gamma (\rho_x + \delta)^2]$ as long as $n$ is large enough. It implies that $\gamma = 1$ (the solution never leaves the domain of definition of $G$).

Each initial condition $\epsilon \in [0, +\infty)$ is tied to a unique solution $R(\cdot,\epsilon)$. This implies that the function $\epsilon \mapsto R(t,\epsilon)$ is injective. Its derivative is given by Liouville's formula \cite{hartman1982ordinary}
\begin{equation}\label{liouville_formula_ode_lowerbound}
\frac{\partial R}{\partial \epsilon}\bigg\vert_{t,\epsilon}
	= \exp \biggl\{\int_0^t ds \, \frac{\partial G}{\partial R}\bigg\vert_{s,R(s,\epsilon)}\biggr\}
\end{equation}
and is greater than, or equal to one, by positivity of $\frac{\partial G}{\partial R}$ -- see \eqref{derivative_G_wrt_R} above --.
The fact that this partial derivative is bounded away from $0$ uniformly in $\epsilon$ implies by the inverse function theorem that the injective function  $\epsilon \mapsto R(t,\epsilon)$ is a $\mathcal{C}^1$-diffeomorphism from $[0, +\infty)$ onto its image.
\end{IEEEproof}

\subsubsection{Derivation of the lower bound}

\begin{proposition}\label{prop:lowerbound_mutual_info}
Suppose that \ref{hyp:S_bounded_support} and \ref{hyp:varphi} hold. Then:
	\begin{equation}
	\limsup_{n \to +\infty} \frac{I(\bX ; \bY \vert \bW)}{n}
	\geq \mathop{\vphantom{p}\inf}_{q_x \in [0,\rho_x]} \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;\psi_{\lambda,\alpha}(q_x, q_s, r_s)\;.
	\end{equation}
\end{proposition}
\begin{IEEEproof}
For all $\epsilon \in [0, +\infty)$, choose for the interpolation path the unique solution $R(\cdot, \epsilon)$ to the first-order ODE \eqref{eq:ODE}.
Fix $\nu > 0$ and let $n$ be large enough so that $\forall \epsilon \in [0, +\infty):R'(\cdot, \epsilon) \subseteq [0,(\rho_x+\nu)^2]$.
The interpolation path satisfies $R'(t,\epsilon) = (\E \langle Q \rangle_{t,\epsilon})^2$ and the sum-rule of Proposition~\ref{prop:sum_rule} yields:
\begin{multline}\label{sum_rule_sol_ode}
\frac{I(\bX ; \bY \vert \bW)}{n}
= \cO(\epsilon) + \smallO_n(1)
+ \frac{1}{\alpha} \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0}\;
\widetilde{\psi}_\alpha\bigg(\frac{\lambda \epsilon}{2} + \int_0^1 \frac{\lambda R'(t,\epsilon)}{2}dt, r_s, q_s\bigg)\\
+ \int_0^1 \bigg(\frac{\lambda}{12} \rho_x^3 + \frac{\lambda}{6} (\E\,\langle Q \rangle_{t,\epsilon})^3
- \frac{\lambda}{4} (\E\,\langle Q \rangle_{t,\epsilon})^2 \rho_x \bigg)dt
-\frac{\lambda}{12} \int_0^1 \Big( \E\,\langle Q^3 \rangle_{t,\epsilon} -  (\E\,\langle Q \rangle_{t,\epsilon})^3  \Big) dt \;.
\end{multline}
By Lemma~\ref{lemma:properties_functions} in Appendix \ref{app:useful_lemmas}, the map $r \mapsto \inf_{q_s \in [0,\rho_s]} \sup_{r_s \geq 0}\; \widetilde{\psi}_\alpha(r , r_s, q_s)$ is nondecreasing and concave. Therefore:
\begin{equation}\label{lowerbound_psi_tilde_jensen}
\adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0} \;\widetilde{\psi}_\alpha\bigg(\frac{\lambda \epsilon}{2} + \int_0^1 \frac{\lambda R'(t,\epsilon)}{2}dt, r_s, q_s\bigg)
\geq \int_0^1 \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0} \;\widetilde{\psi}_\alpha\bigg(\frac{\lambda R'(t,\epsilon)}{2}, r_s, q_s\bigg) dt \;.
\end{equation}
Combining the identity \eqref{sum_rule_sol_ode} with \eqref{lowerbound_psi_tilde_jensen} yields:
\begin{align}
&\frac{I(\bX ; \bY \vert \bW)}{n}\nonumber\\
&\qquad\geq
\int_0^1 \!\bigg\{\adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0} \frac{1}{\alpha}\widetilde{\psi}_\alpha\bigg(\frac{\lambda(\E \langle Q \rangle_{t,\epsilon})^2}{2}, r_s, q_s \!\bigg) + \frac{\lambda \rho_x^3}{12}  + \frac{\lambda(\E\,\langle Q \rangle_{t,\epsilon})^3}{6}
- \frac{\lambda (\E\,\langle Q \rangle_{t,\epsilon})^2 \rho_x}{4}  \bigg\}dt
\nonumber\\&
\qquad\qquad\qquad\qquad\qquad\qquad\quad
-\frac{\lambda}{12} \int_0^1 \Big( \E\,\langle Q^3 \rangle_{t,\epsilon} -  (\E\,\langle Q \rangle_{t,\epsilon})^3  \Big) dt
+ \cO(\epsilon) + \smallO_n(1)  \nonumber\\
&\qquad\geq
\mathop{\vphantom{p}\inf}_{q_x \in [0,\rho_x + \nu]} \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0} \; \psi_{\lambda,\alpha}(q_x, q_s, r_s)\nonumber\\
&\qquad\qquad\qquad\qquad\qquad\qquad\quad
-\frac{\lambda}{12} \int_0^1 \Big( \E\,\langle Q^3 \rangle_{t,\epsilon} -  (\E\,\langle Q \rangle_{t,\epsilon})^3  \Big) dt
+ \cO(\epsilon) + \smallO_n(1) \;.\label{lowerbound_I(X,Y)_with_remainder}
\end{align}
The second inequality follows from identity \eqref{link_psi_tilde_and_psi} and $\E\langle Q \rangle_{t, \epsilon} \in [0, \rho_x + \nu]$.

The result of the proposition will follow if we can get rid of the integral term on the right-hand side of \eqref{lowerbound_I(X,Y)_with_remainder}
This is achieved by proceeding exactly as in the proof of the upper bound in Section~\ref{subsec:upper_bound}, that is, we integrate \eqref{lowerbound_I(X,Y)_with_remainder} over $\epsilon \in [s_n, 2 s_n]$ where $s_n = n^{-\eta}$, $\eta > 0$.
Then:
\begin{align}
&\frac{I(\bX ; \bY \vert \bW)}{n} = \int_{s_n}^{2s_n} \frac{I(\bX ; \bY \vert \bW)}{n}\,\frac{d\epsilon}{s_n}\nonumber\\
&\geq \smallO_n(1) \!
+  \! \mathop{\vphantom{p}\inf}_{q_x \in [0,\rho_x + \nu]} \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0} \; \psi_{\lambda,\alpha}(q_x, q_s, r_s)

-\frac{\lambda}{12} \int_0^1 \! dt \! \int_{s_n}^{2s_n} \! \frac{d\epsilon}{s_n}
\Big( \E\,\langle Q^3 \rangle_{t,\epsilon} -  (\E\,\langle Q \rangle_{t,\epsilon})^3  \Big)
\nonumber \\ &
\geq \smallO_n(1) \!
+  \! \mathop{\vphantom{p}\inf}_{q_x \in [0,\rho_x + \nu]} \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0} \; \psi_{\lambda,\alpha}(q_x, q_s, r_s)

-\frac{\lambda \Vert \varphi \Vert_{\infty}^4}{6} \int_0^1 \! dt \! \int_{s_n}^{2s_n} \! \frac{d\epsilon}{s_n}
\sqrt{\E\,\langle (Q -\E\,\langle Q \rangle_{t,\epsilon})^2 \rangle_{t,\epsilon}} .
\label{integral_perturbation_upperbound}
\end{align}
The last inequality is simply due to:
\begin{align*}
 \E\langle Q^3 \rangle_{t,\epsilon} -  (\E\langle Q \rangle_{t,\epsilon})^3
= \E\langle Q(Q + \E\langle Q \rangle_{t,\epsilon})(Q -\E\langle Q \rangle_{t,\epsilon} ) \rangle_{t,\epsilon}
\leq 2 \Vert \varphi \Vert_{\infty}^4 \sqrt{\E\langle (Q -\E\langle Q \rangle_{t,\epsilon})^2 \rangle_{t,\epsilon}} \;.
\end{align*}
After the change of variables $\epsilon \to R \equiv R(t,\epsilon)$, which is justified by $R(t,\cdot)$ being a $\mathcal{C}^1$-diffeomorphism from $[0,+\infty)$ to its image (see Lemma~\ref{lemma:ode_for_interpolation_path}), we can upper bound the remainder on the right-side of \eqref{integral_perturbation_upperbound} in a way similar to \eqref{lowerbound_change_variable}:
$$
\bigg\vert  \int_{s_n}^{2s_n} \sqrt{\E\,\langle (Q -\E\,\langle Q \rangle_{t,\epsilon})^2 \rangle_{t,\epsilon}}\, \frac{d\epsilon}{s_n} \bigg\vert
\leq \sqrt{\int_{s_n}^{2s_n + \rho_x^2}
	\E\,\big\langle \big( Q - \E\,\langle Q \rangle_{t,R}\big)^{2} \big\rangle_{t,R} \,\frac{dR}{s_n}}\;.
$$
Finally, applying Proposition~\ref{prop:concentration_overlap} in Appendix \ref{app:concentration_overlap} with $M=2 + \rho_x^2, a=s_n, b=2s_n + \rho_x^2$ and $\delta=s_n n^{\frac{2\eta-1}{3}}$, we can further bound the right-hand side of the last inequality to obtain:
$$
\bigg\vert  \frac{\lambda \Vert \varphi \Vert_{\infty}^4}{6} \int_{s_n}^{2s_n} \sqrt{\E\,\langle (Q -\E\,\langle Q \rangle_{t,\epsilon})^2 \rangle_{t,\epsilon}}\, \frac{d\epsilon}{s_n} \bigg\vert
\leq C n^{\frac{5\eta-1}{6}}
$$
for $n$ large enough and $C$ a positive constant which does not depend on $t$ and $n$.
Thus, the remaining term on the right-hand side of \eqref{integral_perturbation_upperbound} vanishes when $n$ goes to infinity as long as $\eta < \nicefrac{1}{5}$.
Passing to the limit inferior on both sides of the inequality \eqref{integral_perturbation_upperbound} yields:
\begin{equation*}
\liminf_{n \to +\infty} \frac{I(\bX ; \bY \vert \bW)}{n} \geq
 \mathop{\vphantom{p}\inf}_{q_x \in [0,\rho_x + \nu]} \adjustlimits{\inf}_{q_s \in [0,\rho_s]} {\sup}_{r_s \geq 0} \; \psi_{\lambda,\alpha}(q_x, q_s, r_s) \;.
\end{equation*}
This is true for all $\nu > 0$ and Proposition~\ref{prop:lowerbound_mutual_info} follows directly.
\end{IEEEproof}

config: arxiv


text:
\subsection{Scalable Inference}
\label{sec:low_rank}

As pointed out in Section \ref{sec:gpr}, inference in GPR using the entire training dataset (of size $N$) scales as $O(N^3)$ due to covariance matrix inversion. This is exacerbated by certain methods to enforce constraints, such as the linear PDE constraints in Section \ref{pde_constraints}, which require the inclusion of ``virtual'' constraint points in the training data.There have been few studies on improving scalability of constrained GPs. Thus, in this section, we mention several promising approaches and possible applications to constrained GPs.

Some strategies, including the subset of data approach, the inducing point approach, and the spectral expansion approach, are specific to covariance matrices of GPs. Other methods are based on general linear algebra techniques.

\subsubsection{Subset of data \& Inducing point methods}
\label{sec:subset_of_data}

One notable feature of increasing the density of training data is that the covariance matrix tends to become more ill-conditioned, the result of partially redundant information being added to the matrix.

In such situations it is worthwhile to identify a \emph{subset of data} that minimizes prediction error subject to a maximum dataset size constraint \citep{quinonero2005JMLR}.

Greedy methods involve sequentially choosing points in the domain that have the maximal predictive variance in order to reduce the uncertainty in the final GP.
This choice is natural and has connections to information-theoretic metrics;

other metrics include cross-validation prediction error, the likelihood value, or Bayesian mean-square prediction error.

Rather than building a new covariance matrix and inverting it for each added point, one may take advantage of the Woodbury matrix inversion lemma and block-matrix inversions to efficiently compute the inverse of the covariance matrix\citep{quinonero2005JMLR}.

Other methods for performing subset selection are based on \emph{local approximation}.

Frequently, the function values far away from a point of interest may have little influence on the function value there.

A simple strategy based on this idea is to select the nearest neighbors to the target point to form the prediction.

The local approximation GP~\citep{gramacy_lagp,gramacy_lagpR} approach combines such local approximation with a greedy search heuristic to identify a better set of points to minimize the mean-squared prediction error at the location of interest.

Using a subset of points to form the GP corresponds to selecting a subset of the rows/columns of a full covariance matrix to represent the dataset. \citet{quinonero2005RR} generalize this to a broad set of low-rank approximations to the full covariance matrix based on \emph{inducing points}. In these methods, a subset (size $m$) of the data is used to form an approximate likelihood or prior for the entire dataset; all of the data is used, but most of the data is modeled as being conditionally dependent on a few inducing points. This reduces the cost of inference from $O(N^3)$ to $O(Nm^2)$. The greedy methods discussed above may be applied to identify an optimal set of inducing points.

Such methods may be especially helpful for selection and placement of virtual points for enforcing constraints. However, to our knowledge, there have not been any studies of this. An important question is how to treat the two sets of data -- training and virtual -- using these approaches.

\subsubsection{Spectral expansion approximation}
\label{sec:spectral_low_rank}

The approach of Section \ref{spectral_expansion_approach} for boundary condition constraints can also be used for reduced rank GPR \citep{solin2019hilbert,hensman2017}.
An expansion of a covariance kernel in terms of the eigenvalues of the Laplacian with periodic boundary values in an artificial box containing the data is used to approximate the covariance kernel, as in \eqref{e:spectral_expansion_kernel}. The error of approximation should be small if the boundaries of the box are sufficiently far from the data locations.
With $m$ basis functions in the expansion \eqref{e:spectral_expansion_kernel}, the formula \eqref{e:regression_formulas_bc} implies that inverses are required only of matrices of size $m$. Therefore, inversion scales as $O(m^3)$, while multiplication for inference in \eqref{e:regression_formulas_bc} scales as $O(m^2 N)$.

Moreover, formulas \eqref{e:nlml_bc} and \eqref{e:nlml_bc_derivatives} and the fact that $\Phi$ does not depend on the kernel hyperparameters imply that the same reduced-rank advantage is present in hyperparameter training via MLE.

\subsubsection{Linear Algebra Techniques}
\label{sec:hierarchical_matrices}

Rather than trying to reduce the effective size of the training and virtual constraint points, it is possible to simply approximate covariance matrix inversion using more general numerical linear algebra techniques.

We expect such methods to extend more readily to constrained GPs than the methods of Section \ref{sec:subset_of_data}, although they may be less optimal and may not inform the placement of virtual constraint points.

The pseudo-inverse is often used to avoid the small eigenvalues that can corrupt predictions \citep{brunton2019data}, although the singular value decomposition or eigenvalue decomposition are both computationally expensive as well.

Hierarchical matrices are an efficient way of approximating the full covariance matrix in a manner amenable to fast inversion \citep{pouransari2017fast}. Sub-blocks of the matrix are replaced with fixed-rank approximations using a computational tree to organize the hierarchy of the matrix, and operations on the full matrix such as multiplication or inversion can be accomplished efficiently by operating on each of the individual ``leaves'' of the tree. \citet{geoga2019scalable} applied hierarchical matrices methods to maximum likelihood estimation for Gaussian processes.

An alternative to inverting the covariance matrix is to

to set up an optimization problem for a matrix such that the error between the product of the matrix with the covariance matrix and the identity matrix is minimized \citep{zhao2013sparse}. The solution to this linear program is, of course, the precision matrix,

but by adding a $L_1$ penalty term on the entries of the matrix to the objective function as in LASSO regression, sparsity will be induced in the result. This estimator is referred to as CLIME \citep{cai2011}.

Another popular approach for modeling sparsity in random processes is to use a Gaussian Markov random field (GMRF) \citep{sorbye2014scaling, rue2002fitting}. In a GMRF, the data may be seen as forming an undirected graph where points close to each other in data-space are connected by an edge, and points far from each other are not. Thus while all points are correlated with each other, most are only conditionally dependent on each other; this translates to a sparse precision matrix where the only off-diagonal entries correspond to points that are connected to each other. Different choices of the covariance widths or kernels, such as truncated or tapered kernels \citep{shaby2012tapered,kaufman2008covariance}, yield different levels of sparsity in the final precision matrix.