\section{The adaptive path interpolation method}\label{interp}

For $t=1,\dots, T$ let $V^{(t)}_i$ be i.i.d. r.v. distributed according to $\sfx^{(t)}\in \mathcal{X}$.
Consider the r.v.
\begin{align}
U^{(t)} = \tanh^{-1} \Big( \tanh \tilde{J} \prod_{i=1}^{K-1} V_i^{(t)} \Big ) \label{eq:BP-update}
\end{align}
and independent copies denoted $U^{(t)}_B$ where $B$ is a subscript which runs over $l^{(t)} \sim \mathrm{Poi}(\frac{K}{RT})$ of these copies. 
Later on, we call $\tilde \sfx^{(t)}$ the distribution of $U^{(t)}$ (induced by $\sfx^{(t)}$ and $\sfc$).

Let also define two extra random variables, $H$ with distribution $\epsilon \Delta_{\infty} + (1-\epsilon) \Delta_{0} \in \mathcal{B}$, and $\tilde{H}$ with 
distribution $\delta n^{-\theta} \Delta_{\infty} + (1-\delta  n^{-\theta}) \Delta_0 \in \mathcal{B}$, where $\epsilon, \delta \in (0,1)$ and $\theta \in (0, 1)$ (eventually we will have to take $\theta\in (0, 1/5]$ in the final estimates). 

Let us set $\underline \sfx = (\sfx^{(1)}, \dots, \sfx^{(T)})$.
We define the {\it generalized free entropy functional}:
\begin{align}
\tilde{h}_{\epsilon,\delta}( \underline{\sfx} ) 
	& \equiv\mathbb{E} \Big[\ln \Big( \prod_{t=1}^{T} \prod_{B=1}^{l^{(t)}} (1 + \tanh U_B^{(t)} ) + e^{-2(H+\tilde{H})} \prod_{t=1}^{T} \prod_{B=1}^{l^{(t)}} (1 - \tanh U_B^{(t)} ) \Big ) \nonumber \\
	& \hspace{2cm} - \frac{\alpha(K-1)}{T} \sum_{t=1}^{T} \ln \Big (1 + \tanh \tilde{J} \prod_{i=1}^{K} \tanh V_i^{(t)} \Big ) 
	-\alpha \ln (1 + \tanh \tilde{J}) \Big].
\label{eq:RSFreeEntropy_coupled1}
\end{align}

One can easily check that if $\sfx^{(t)} = \sfx$ for all $t$, then $\tilde{h}_{\epsilon = 0, \delta = 0}(\underline{\sfx}) = h_{\mathrm{RS}}(\sfx)$. 
More is true as the following lemma shows:

\begin{lemma}\label{equivalence}
Let $\sX^T = \mathcal{X}\times \mathcal{X}\times \ldots \times \mathcal{X}$. We have for $\underline{\sfx} \in \mathcal{X}^T$
\begin{align}
\sup_{\underline{\sfx} \in \sX^T} \tilde{h}_{\epsilon = 0, \delta = 0}(\underline{\sfx}) = \sup_{\sfx \in \sX} h_{\mathrm{RS}}(\sfx).
\label{eq:h_RS_coupled:equivalence}
\end{align}
\end{lemma}
\begin{remark}
 We prove this lemma in Sec.~\ref{proof:h_RS_coupled:equivalence}. For distributions in $\underline \sfx\in \mathcal{B}^T$ the supremum carries over $(x^{(1)}, \cdots, x^{(T)})\in[0, 1]^T$ and the proof only requires real analysis.  
\end{remark}


\subsection{The $(t,s)$--interpolating model}\label{subsec:tsmodel}

Consider the construction of an interpolating factor graph ensemble $\sG_{t,s}$ involving discrete and a continuous interpolation parameters, $t \in \{1, 2, \dots, T \}$ and $s \in [0,1]$. 
This is the sparse graph counterpart of the interpolating ensemble initialy developed for dense graphs in \cite{BarbierM17a} (and the simplified in \cite{BarbierMacrisCW2019}).


\begin{algorithm}
\caption{Construction of $\sG_{t,s}$}
\begin{algorithmic}
\label{algo:G(t,s)}
	\For {$i = 1, \dots, n$}
	\For {$t' = 1, \dots, t-1$}
		\State {\_draw a random number $e_i^{(t')} \sim \mathrm{Poi}\big( \frac{\alpha K}{T} \big)$}
		\For {$B = 1, \dots, e_i^{(t')}$}
			\State{\_connect variable node $i$ with a half edge and assign a weight $U_{B \rightarrow i}^{(t')} \sim \tilde{\sfx}^{(t')}$ to this half-edge}
		\EndFor
	\EndFor
	\State {\_draw a random number $e_{i,s}^{(t)} \sim \mathrm{Poi}\big ( \frac{\alpha Ks}{T} \big )$}
	\For {$C = 1, \dots, e_{i,s}^{(t)}$}
		\State{\_connect variable node $i$ with a half edge and assign a weight $U_{C \rightarrow i}^{(t)} \sim \tilde{\sfx}^{(t)}$ to this half-edge}
	\EndFor
\EndFor\\


\State {\_draw a random number $m_s^{(t)} \sim \mathrm{Poi}\big ( \frac{\alpha n(T-t+1-s)}{T} \big )$}
\For {$A = 1, \dots, m_s^{(t)}$}
		\State {\_assign to factor node $A$ a r.v $\tilde{J}_{A} \sim \sfc$}
		\State {\_uniformly and randomly connect factor node $A$ to $K$ variable nodes (this subset of variable nodes is also denoted $A$ by a slight abuse of notation)}
	\EndFor
\end{algorithmic}
\end{algorithm}


The interpolating graph is designed such that $\sG_{t,1}$ is statistically equivalent to $\sG_{t+1,0}$; 
in addition, $\sG_{t,s}$ maintains the degree distribution of variable nodes invariant: For any $(t,s)$ the degree of each variable node is an independent ${\rm Poi}(K/R)$ random variable. The Hamiltonian associated with $\sG_{t,s}$ is 


\begin{align}
\sH_{t,s}(\underline{\sigma}, \underline{\tilde{J}}, \underline{U}, \underline{m}, \underline{e}) 
	= &
	-  \sum_{i=1}^{n}\Big\{\sum_{t' =1}^{t-1} \sum_{B=1}^{e_{i}^{(t')}} U_{B \rightarrow i}^{(t')} + \sum_{C=1}^{e_{i,s}^{(t)}} U_{C \rightarrow i}^{(t)}\Big\} ( \sigma_i - 1 )
	- \sum_{A=1}^{m_s^{(t)}} \tilde{J}_{A} ( \sigma_{A} - 1 ).
\label{eq:Hamiltonian_ts}
\end{align}

We further consider a generalized version of \eqref{eq:Hamiltonian_ts} by adding two kinds of perturbations that can be interpreted as small additional observations from side-channels for each node $i=1,\cdots, n$. 
These perturbations are then removed at the end of the analysis. let $H_i$ and $\tilde{H}_i$ be half-log-likelihood variables, where $H_i$ and $\tilde{H}_i$ have the same distribution as $H$ and $\tilde{H}$ 
defined at the beginning of this section. Our final {\it interpolating Hamiltonian} is
\begin{align}
\sH_{t,s; \epsilon, \delta}(\underline{\sigma}, \underline{\tilde{J}}, \underline{U}, \underline{m}, \underline{e}, \underline{H}, \underline{\tilde{H}}) 
	& \equiv \sH_{t,s}(\underline{\sigma}, \underline{\tilde{J}}, \underline{U}, \underline{m}, \underline{e}) - \sum_{i=1}^{n} (H_i + \tilde{H}_i) ( \sigma_i - 1 ).
	\label{eq:Hamiltonian_tse}
\end{align}
The associated interpolating partition function, Gibbs expectation and free entropy are:
\begin{align}
{\cal Z}_{t,s; \epsilon,\delta}
	& \equiv \sum_{\underline{\sigma}\in\{-1,+1\}^n} e^{-{\sH_{t,s; \epsilon,\delta}(\underline{\sigma}, \underline{\tilde{J}}, \underline{U}, \underline{m}, \underline{e}, \underline{H}, \underline{\tilde{H}})}},
	\label{eq:partitionFunction_tse} \\
\< A(\underline{\sigma}) \>_{t,s; \epsilon, \delta} 
	& \equiv \frac{1}{{\cal Z}_{t,s; \epsilon,\delta}}\sum_{\underline{\sigma}\in\{-1,+1\}^n} A(\underline{\sigma})\, 
	e^{-{\sH_{t,s; \epsilon,\delta}(\underline{\sigma}, \underline{\tilde{J}}, \underline{U}, \underline{m}, \underline{e}, \underline{H}, \underline{\tilde{H}})}}, 
	\label{eq:GibbsExp_tse} \\
h_{t,s; \epsilon, \delta} & \equiv \frac{1}{n} \mathbb{E}\ln {\cal Z}_{t,s; \epsilon,\delta}, \label{eq:htse} \\
H_{t,s; \epsilon,\delta} & \equiv \frac{1}{n} \mathbb{E}_{\underline{\tilde{H}}} \ln \mathcal{Z}_{t,s; \epsilon,\delta}\,. \label{eq:Htse}
\end{align}
Recall our notation: The expectation $\mathbb{E}$ here carries over {\it all} quenched variables entering in the interpolating system, thus $\underline{\tilde{J}}, \underline{U}, \underline{m}, \underline{e}$, $\underline{H}$ and $\underline{\tilde{H}}$.
Note that Nishimori's identity \eqref{eq:Nishimori} and GKS inequalities \eqref{eq:GKS1}, \eqref{eq:GKS2} still apply to the Gibbs 
expectation $\< - \>_{t,s; \epsilon,\delta}$. 

One may check that, at the initial point of the interpolating path, $t=1$, $s=0$ the free entropy $h_{1,0;\epsilon=0,\delta=0}$ is equal to the averaged conditional entropy of the original model
(see formula \eqref{h10ish} below), and at the end-point $t=T$, $s=1$ the free entropy $h_{T,1;\epsilon,\delta}$ is given by a part
of the generalized entropy functional \eqref{eq:RSFreeEntropy_coupled1} (see formula \eqref{eq:h_T1}).

The connection between the unperturbed and perturbed free entropies is given by (see Sec.~\ref{sec:proofepsilon-free})
\begin{lemma}\label{pert-free}
 Let $\sfc\in \mathcal{B}$ and $\underline \sfx\in \mathcal{B}^T$. We have
 \begin{align}
  & \vert h_{t, s; \epsilon,\delta} - h_{t, s; \epsilon=0,\delta=0} \vert \leq  ( \epsilon + \frac{\delta}{n^{\theta}} ) \ln 2\, ,\label{eq:pert-free:1} \\
  & \vert \tilde{h}_{\epsilon,\delta}(\underline{\sfx}) - \tilde{h}_{\epsilon=0,\delta=0}(\underline{\sfx}) \vert \leq  ( \epsilon + \frac{\delta}{n^{\theta}} ) \ln 2\, . \label{eq:pert-free:2}
  \end{align}
\end{lemma}


\subsection{Evaluating the free entropy change along the $(t,s)$--interpolation}

By interpolating $h_{t,s; \epsilon, \delta}$ from the initial state $(t=1, s=0)$ to the final one $(t=T, s=1)$, we have
\begin{align}
h_{1,0; \epsilon, \delta} = h_{T,1; \epsilon, \delta} + \sum_{t=1}^{T} ( h_{t,0; \epsilon, \delta} - h_{t,1; \epsilon, \delta}) = h_{T,1; \epsilon, \delta} - \sum_{t=1}^T \int_0^1 ds \frac{dh_{t,s; \epsilon, \delta}}{ds}.
\label{eq:interpolation:main1}
\end{align}
We have $m_{s=0}^{(t=1)}=m\sim{\rm Poi}(\alpha n)$ and thus
\begin{align*}


\sH_{1,0; \epsilon, \delta} =- \sum_{A=1}^{m} \tilde{J}_{A} (\sigma_{A}-1) - \sum_{i=1}^{n} (H_i + \tilde{H}_i) (\sigma_i - 1) .
\end{align*}

Therefore the initial interpolating free entropy without perturbation equals the average conditional entropy per variable:
\begin{align}
h_{1,0; \epsilon=0, \delta = 0}=\frac{1}{n}\mathbb{E} H(\underline \sigma | \underline{\tilde J}). \label{h10ish}	
\end{align}
On the other hand $h_{T,1; \epsilon, \delta}$ corresponds to a part of the generalized free entropy functional \eqref{eq:RSFreeEntropy_coupled1}. 
A subsequent computation (see Sec.~\ref{proof:interpolation:main2}) on \eqref{eq:interpolation:main1} leads to the {\it fundamental sum rule}
\begin{align}
h_{1,0; \epsilon, \delta} = \tilde{h}_{\epsilon, \delta}(\underline{\sfx}) + \frac{\alpha }{T} \sum_{t=1}^T \int_0^1 ds \,\sR_{t,s; \epsilon, \delta}
\label{eq:interpolation:main2}
\end{align}
where 
\begin{align}
\sR_{t,s; \epsilon, \delta} = \sum_{p=1}^{\infty} \frac{\mathbb{E} [ (\tanh \tilde{J})^{2p} ]}{2p(2p-1)} \ \mathbb{E} \big\langle Q_{2p}^{K} - K  (q_{2p}^{(t)})^{K-1} ( Q_{2p} - q_{2p}^{(t)}) - 
(q_{2p}^{(t)})^K \big\rangle_{t,s; \epsilon, \delta} 
\label{eq:interpolation:remainder}
\end{align}
with $$Q_{p} \equiv \frac{1}{n} \sum_{i=1}^{n} \sigma_i^{(1)} \cdots \sigma_i^{(p)}$$ the {\it overlap} 
of $p$ independent {\it replicas} $\underline{\sigma}^{(1)}, \dots , \underline{\sigma}^{(p)}$ 
and 
$$
q_p^{(t)} \equiv \mathbb{E} [(\tanh V^{(t)})^p].
$$
In \eqref{eq:interpolation:remainder} the Gibbs average $\langle - \rangle_{t, s;\epsilon, \delta}$ over a polynomial of $Q_p$ must be understood as an
average over the product measure
\begin{align*}
 \prod_{\alpha=1}^p \frac{1}{{\cal Z}_{t,s; \epsilon,\delta}}
	e^{-{\sH_{t,s; \epsilon,\delta}(\underline{\sigma}^{(\alpha)}, \underline{\tilde{J}}, \underline{U}, \underline{m}, \underline{e}, \underline{H}, \underline{\tilde{H}})}}
\end{align*}
where the quenched variables have the same realization for all replicas. We still denote this Gibbs average by $\langle - \rangle_{t, s;\epsilon, \delta}$ for simplicity.


\subsection{Lower bound}

In order to show the lower bound we need the following important concentration lemma (proven in Sec.~\ref{sec:overlap}), which is at the core of the ``replica symmetric'' behavior of the model:
\begin{lemma}[Concentration of $Q_p^K$ on $\< Q_p \>_{t,s; \epsilon; \theta}^K$]
For any $\sfc \in \sB$, $\underline\sfx\in \mathcal{B}^T$ we have
\begin{align}
\int_{\varepsilon_0}^{\varepsilon_1} d\epsilon \ \mathbb{E}  \big\< \big| Q_p^{K} - \< Q_p \>_{t,s; \epsilon,\delta}^K \big| \big\>_{t,s; \epsilon,\delta}  \leq K \Big ( \frac{3p(\varepsilon_1-\varepsilon_0)}{n} \Big )^{1/2}.
\end{align}
\label{thm:concentration1}
\end{lemma}


\begin{proposition}[Lower bound]\label{prop:lowerbound}
For $\sfc \in \mathcal{B}$ we have
\begin{align}\label{lower-bound-guerra-style}
\liminf_{n \rightarrow \infty} \frac{1}{n} \mathbb{E}H(\underline{\sigma} | \underline{\tilde{J}}) 
\geq \sup_{\sfx \in \mathcal{B}} h_{\mathrm{RS}}(\sfx).
\end{align}
\end{proposition}

\begin{remark}
 The methods of this paper can be extended to show this proposition for $\mathrm{c}, \sfx\in \mathcal{X}$.
\end{remark}


\begin{proof}
Eq.~\eqref{eq:interpolation:main2} implies
\begin{align}
h_{1,0;\epsilon=0, \delta=0} 
	& = \tilde{h}_{\epsilon=0,\delta=0}(\underline{\sfx}) + \frac{\alpha }{T} \sum_{t=1}^{T} \int_0^1 ds \sR_{t,s;\epsilon,\delta}(\underline{\sfx}) \nonumber \\
	& + \big ( \tilde{h}_{\epsilon,\delta}(\underline{\sfx}) - \tilde{h}_{\epsilon=0,\delta=0}(\underline{\sfx}) \big ) 
	- \big ( h_{1,0;\epsilon,\delta} - h_{1,0;\epsilon=0,\delta=0} \big ). \label{eq:bd-start}
\end{align}
We fix $\delta=0$. From \eqref{eq:interpolation:remainder} we have $\sR_{t,s;\epsilon,\delta=0}$ equal to
\begin{align*}
\sum_{p=1}^{\infty} \frac{\mathbb{E}[ (\tanh \tilde{J})^{2p} ] }{2p(2p-1)} 
\Big ( \mathbb{E}
\Big[ \langle Q_{2p} \rangle_{t,s; \epsilon,0}^{K} - K (q_{2p}^{(t)})^{K-1} (\langle Q_{2p} \rangle_{t,s; \epsilon,0} - 
q_{2p}^{(t)}) - (q_{2p}^{(t)})^K \Big ] - \mathbb{E} \< ( Q_p^K - \< Q_p \>_{t,s;\epsilon,0}^K ) \>_{t,s;\epsilon,0} \Big ).
\end{align*}
 Note that the convexity $x\mapsto x^K$ for $x \in \mathbb{R}_{+}$ implies 
$x^K - y^K \geq K y^{K-1} (x-y)\geq 0$ for any $x,y\in \mathbb{R}_+$. As $\<Q_{2p}\>_{t,s; \epsilon,0}=\frac{1}{n} \sum_{i=1}^n \<\sigma_i\>_{t,s; \epsilon,0}^{2p} \geq 0$ and $q_{2p}^{(t)} \geq 0$,
\begin{align*}
 \langle Q_{2p} \rangle_{t,s; \epsilon,0}^{K} - K (q_{2p}^{(t)})^{K-1} (\langle Q_{2p} \rangle_{t,s; \epsilon,0} - 
q_{2p}^{(t)}) - (q_{2p}^{(t)})^K \geq 0.
\end{align*}
Thus with Lemma~\ref{thm:concentration1} we obtain
\begin{align}
\frac{1}{\epsilon_n} \int_{\epsilon_n}^{2\epsilon_n} d\epsilon\, \sR_{t,s;\epsilon,0} \geq - (\ln 2) K \Big ( \frac{3p}{\epsilon_n n} \Big )^{1/2}.
\label{eq:almost-positivity}
\end{align}
Now we average both side of \eqref{eq:bd-start} over $\epsilon \in [\epsilon_n, 2 \epsilon_n]$ for some sequence $\epsilon_n$ specified at the end. Using \eqref{eq:almost-positivity} and Lemma~\ref{pert-free}
\begin{align*}
h_{1,0;\epsilon=0,\delta=0} \geq \tilde{h}_{\epsilon=0,\delta=0}(\underline{\sfx}) + \mathcal{O} \big ( \frac{1}{\sqrt{\epsilon_n n}} \big ) + \mathcal{O}(\epsilon_n).
\end{align*}
Choosing $\epsilon_n = n^{-\gamma}$ with $0<\gamma<1$, we conclude
\begin{align*}
\liminf_{n \rightarrow \infty} h_{1,0;\epsilon=0,\delta=0} \geq \tilde{h}_{\epsilon=0,\delta=0}(\underline{\sfx}).
\end{align*}
Finally one can take the supremum of the right hand side and use \eqref{eq:h_RS_coupled:equivalence} as well as \eqref{h10ish} to obtain \eqref{lower-bound-guerra-style}.
\end{proof}


\subsection{Upper bound}

In this paragraph we crucially use the specificities of the BEC. We take interpolating paths $\underline{\sfx}=(\sfx^{(1)},\cdots, \sfx^{(T)})\in \mathcal{B}^T$, where 
$\sfx^{(t)} = x^{(t)}\Delta_0 + (1- x^{(t)})\Delta_{\infty}$.
In particular we use the following lemma (proven in Sec.~\ref{sec:proof:BEC:overlap}):

\begin{lemma}
For any $\sfc \in \sB$, and any interpolation path $\underline\sfx(\epsilon) \in \mathcal{B}^T$ depending on $\epsilon$, and any $A \subseteq \{ 1, \dots, n \}$ we have $\< \sigma_A \>_{t,s; \epsilon,\delta}\in\{0,1\}$.
\label{thm:BEC:overlap}
\end{lemma}


Notice that $\< Q_p^k \>_{t,s; \epsilon,\delta} = \frac{1}{n^k}\sum_{i_1,\dots,i_k=1}^n \langle\sigma_{i_1} \cdots \sigma_{i_k}\rangle_{t,s; \epsilon,\delta}^p$ for any $k \in \mathbb{N}$. 
Lemma~\ref{thm:BEC:overlap} then implies 
$$
\< Q_p^k \>_{t,s; \epsilon,\delta} = \< Q_1^k \>_{t,s; \epsilon,\delta}
$$
for all $p \in \mathbb{N}^{*}$. We also have $\tanh V^{(t)}\in\{0,1\}$ because $\sfx^{(t)}\in \mathcal{B}$ and thus $$q_p^{(t)}= q_1^{(t)} \ \forall \ p \in \mathbb{N}^{*}.$$ 
Finally recall that $\sfc(\tilde J|1) = (1-q)\Delta_\infty + q \Delta_0$, therefore $\mathbb{E}[(\tanh \tilde{J})^{2p}] = 1- q$. 
These facts reduce \eqref{eq:interpolation:remainder} to
\begin{align}
\sR_{t,s; \epsilon, \delta} = (1-q)(\ln 2) \mathbb{E}
\Big [ \langle Q_{1}^K \rangle_{t,s; \epsilon, \delta} - K (q_{1}^{(t)})^{K-1} (\langle Q_{1} \rangle_{t,s; \epsilon, \delta} - q_{1}^{(t)}) - 
(q_{1}^{(t)})^K \Big ].
\label{eq:interpolation:remainder:simplify}
\end{align}

We then split the remainder as follows:
\begin{align}
\sR_{t,s; \epsilon, \delta} 
& = (\sR_{t,s; \epsilon, \delta} - \sR_{t,0; \epsilon, \delta}) + \sR_{t,0; \epsilon, \delta} \nonumber \\
& = (\sR_{t,s; \epsilon, \delta} - \sR_{t,0; \epsilon, \delta})
+ (1-q)(\ln 2) \Big ( \mathbb{E} [ \< Q_{1} \>_{t,0; \epsilon, 0} ]^K - K (q_{1}^{(t)})^{K-1} (\mathbb{E} \< Q_{1} \>_{t,0; \epsilon, 0} - q_{1}^{(t)}) - 
(q_{1}^{(t)})^K \Big ) \nonumber \\
& + (1-q) (\ln 2) \big ( \mathbb{E} \<Q_1^K\>_{t,0;\epsilon,\delta} - \mathbb{E}[\<Q_1\>_{t,0;\epsilon,\delta}]^K \big ) \nonumber \\
& + (1-q) (\ln 2) \big ( \mathbb{E}[\<Q_1\>_{t,0;\epsilon,\delta}]^K - \mathbb{E}[\<Q_1\>_{t,0;\epsilon,0}]^K
- K (q_1^{(t)})^{K-1} ( \mathbb{E}[\<Q_1\>_{t,0;\epsilon,\delta}] - \mathbb{E}[\<Q_1\>_{t,0;\epsilon,0}] ) \big )
\label{eq:interpolation:remainder:decompose}
\end{align}
and treat each part thanks to the three following lemmas.
Lemma \ref{thm:bd_fixed_t} is proven in Sec.~\ref{sec:proof:bd_fixed_t}, lemma \ref{thm:concentration2} in Sec.~\ref{sec:overlap}, 
and lemma~\ref{thm:rmv-delta} in Sec.~\ref{sec:proof:rmv-delta}).


\begin{lemma}[Weak $s$-dependence at fixed $t$]\label{thm:bd_fixed_t}
For any $k \in \mathbb{N}$ and $s\in [0,1]$ we have
\begin{align}
\big| \mathbb{E}\< Q_1^k \>_{t,s; \epsilon,\delta}  - \mathbb{E} \< Q_1^k \>_{t,0; \epsilon,\delta}  \big| \leq  \frac{2\alpha (K+1)n}{T}.
\end{align}
\end{lemma}

\begin{lemma}[Concentration of $\< Q_1 \>_{t,s; \epsilon,\delta}^K$ on $\mathbb{E}{[}\langle Q_1 \rangle_{t,s; \epsilon,\delta}{]}^K$ ]\label{thm:concentration2}

For any $\sfc \in \sB$ and $\underline\sfx(\epsilon) \in \mathcal{B}^T$ such that every component satisfies $dx^{(t)}/d\epsilon \geq 0$ we have for $\theta\in (0, 1/5]$
\begin{align}
\int_{\delta_0}^{\delta_1} d\delta \int_{\varepsilon_0}^{\varepsilon_1} d\epsilon \mathbb{E}\big[ \big| \< Q_1 \>_{t,s; \epsilon,\delta}^{K}  - \mathbb{E} [\< Q_1 \>_{t,s; \epsilon,\delta}]^K \big| \big ] 
	= \mathcal{O} \bigg ( \bigg ( (\delta_1-\delta_0)(\varepsilon_1-\varepsilon_0) \frac{\delta_1-\delta_0 + \varepsilon_1-\varepsilon_0}{n^{\theta}} \bigg )^{1/2} \bigg ).
\label{eq:concentration2}
\end{align}
\end{lemma}

\begin{lemma}
For any $\sfc \in \sB$ and $\underline\sfx(\epsilon) \in \mathcal{B}^T$ such that every component satisfies $dx^{(t)}/d\epsilon \geq 0$ we have
\begin{align}
& \bigg \vert \int_{\delta_0}^{\delta_1} d\delta \int_{\varepsilon_0}^{\varepsilon_1} d\epsilon \Big \{ \mathbb{E}[\<Q_1\>_{t,0;\epsilon,\delta}]^K - \mathbb{E}[\<Q_1\>_{t,0;\epsilon,0}]^K \nonumber \\
& \hspace{1cm} - K (q_1^{(t)})^{K-1} ( \mathbb{E}[\<Q_1\>_{t,0;\epsilon,\delta}] - \mathbb{E}[\<Q_1\>_{t,0;\epsilon,0}] ) \Big \} \bigg \vert \leq \frac{3K(\delta_1^2-\delta_0^2)}{n^{\theta}(1-\delta_1/n^{\theta})}\,.
\end{align}
where $\theta\in (0, 1/5]$.
\label{thm:rmv-delta}
\end{lemma}

Now we look into each term of \eqref{eq:interpolation:remainder:decompose}. Lemma~\ref{thm:bd_fixed_t} and \eqref{eq:interpolation:remainder:simplify} imply 
$$
|\sR_{t,s; \epsilon, \delta} - \sR_{t,0; \epsilon, \delta}| \leq \frac{2 (\ln 2) \alpha (K+1)^2 n}{T} = \mathcal{O}(\frac{n}{T}).
$$
Since $T$ is a free parameter (controlling the mean of $e_{i,s}^{(t)}$ and $m_s^{(t)}$) we can set it 
significantly larger than $n$. The first term of \eqref{eq:interpolation:remainder:decompose} thus can be neglected and it is sufficient to work with $\sR_{t,0; \epsilon, \delta}$. 
This separation is important because we use that $\mathbb{E} \langle Q_{1} \rangle_{t,0; \epsilon,0}$ 
(in the second term of \eqref{eq:interpolation:remainder:decompose}) is independent of $\{ \sfx^{(t')} \}_{t' \geq t}$. Also recall $q_1^{(t)}\equiv \mathbb{E} \tanh V^{(t)}$. 
This allows us to sequentially choose a distribution 
$\hat{\sfx}_n^{(t)}$ for $V^{(t)}$ along our interpolation from $t=1$ to $T$ such that the following equation is satisfied:

\begin{align}
q_1^{(t)} = \mathbb{E} \langle Q_1 \rangle_{t,0; \epsilon, 0} .
\label{eq:momentMatching}
\end{align}

In other words the interpolation path is {\it adapted} so that \eqref{eq:momentMatching} holds, which then cancels the second term in \eqref{eq:interpolation:remainder:decompose}. This 
path is also independent of $\delta$ because we have set $\delta=0$ in the Gibbs expectation \eqref{eq:momentMatching} as well as in the second term of \eqref{eq:interpolation:remainder:decompose}. 
We must still check that equation \eqref{eq:momentMatching} possesses a (unique) solution, see Sec.~\ref{sec:proof:momentMatching:solution} for the proof:

\begin{lemma}[Existence of the optimal interpolation path]\label{thm:momentMatching:solution}
Eq. \eqref{eq:momentMatching} has 
a unique solution $\underline{\hat{\sfx}}_n(\epsilon) = \{ \hat{\sfx}^{(t)}_n \}_{t=1}^T \in \sB^T$. The solution $\hat{\sfx}_n \equiv \hat{x}_n^{(t)} \Delta_\infty + (1-\hat{x}_n^{(t)}) \Delta_0$ satisfies $d \hat{x}_n^{(t)}/d\epsilon \geq 0$.
\end{lemma}

Fixing $\underline{\sfx} = \underline{\hat{\sfx}}_n(\epsilon)$, lemmas~\ref{thm:concentration2} and \ref{thm:rmv-delta} 
are used to upper bound the last two terms of \eqref{eq:interpolation:remainder:decompose} upon integrating over $\delta,\epsilon$. 
The solution of \eqref{eq:momentMatching}, that eliminates $\sR_{t,s; \epsilon, \delta}$, therefore can be considered as the ``optimal interpolation path''.

In summary, using lemmas~\ref{thm:bd_fixed_t} to \ref{thm:momentMatching:solution} on \eqref{eq:interpolation:remainder:decompose} we have
\begin{align}
\bigg \vert \int_{0}^{1} d\delta \int_{\epsilon_n}^{2\epsilon_n} d\epsilon \sR_{t,s;\epsilon,\delta} \big ( \underline{\hat{\sfx}}_n(\epsilon) \big ) \bigg \vert 
	= \mathcal{O} \big (\frac{n\epsilon_n}{T} \big ) + \mathcal{O} \big ( \frac{\sqrt{\epsilon_n}}{n^{\theta/2}} \big ) + \mathcal{O} \big ( \frac{1}{n^{\theta}} \big )
	\label{eq:R-order}
\end{align}
for any sequence $\epsilon_n$.

We are now ready to prove the upper bound.
\begin{proposition}[Upper bound]\label{prop:upperbound}
For any $\sfc \in \sB$ we have
\begin{align}
\limsup_{n \rightarrow \infty} \frac{1}{n} \mathbb{E} H(\underline{\sigma} | \underline{\tilde{J}}) 
\leq \sup_{\sfx \in \mathcal{B}} h_{\mathrm{RS}}(\sfx).
\end{align}
\end{proposition}

\begin{proof}
We evaluate \eqref{eq:bd-start} at $\underline{\sfx} = \underline{\hat{\sfx}}_n(\epsilon)$ and average the equation over $\delta \in [0,1]$, $\epsilon \in [\epsilon_n, 2 \epsilon_n]$. Using \eqref{eq:R-order} and Lemma~\ref{pert-free}
\begin{align*}
h_{1,0;\epsilon=0,\delta=0}
	& = \tilde{h}_{\epsilon=0,\delta=0}(\underline{\hat{\sfx}}_n(\epsilon)) + \mathcal{O} \big (\frac{n}{T} \big ) + \mathcal{O} \big ( \frac{1}{\sqrt{\epsilon_n n^{\theta}}} \big ) + \mathcal{O} \big ( \frac{1}{\epsilon_n n^{\theta}} \big ) + \mathcal{O}(\epsilon_n + \frac{1}{n^{\theta}}).
\end{align*}
Choosing $\epsilon_n = n^{-\gamma}$ with $0<\gamma<1$, we conclude
\begin{align}
\limsup_{n \rightarrow \infty} h_{1,0;\epsilon=0,\delta=0} = \tilde{h}_{\epsilon=0,\delta=0}(\underline{\hat{\sfx}}_n(\epsilon)).
\label{eq:up-bd-eq}
\end{align}
A trivial upper bound together with Lemma~\ref{eq:h_RS_coupled:equivalence} gives
\begin{align}
\tilde{h}_{\epsilon=0,\delta=0}(\underline{\hat{\sfx}}_n(\epsilon))
	\leq \sup_{\underline{\sfx} \in \mathcal{B}^T} \tilde{h}_{\epsilon=0,\delta=0}(\underline{\sfx})
	= \sup_{\sfx \in \mathcal{B}} h_{\mathrm{RS}}(\sfx). \label{eq:trivial-ub}
\end{align}
The proof is ended by substituting \eqref{eq:trivial-ub} into \eqref{eq:up-bd-eq} and using \eqref{h10ish}.
\end{proof}
{"config": "arxiv", "file": "1806.05121/sections/Kint.tex"}