v}^{t},\qquad\tilde{r}_{f\rightarrow
v}^{t}=\tilde{f}_{t}(\tilde{b}_{f\rightarrow
v}^{0},\ldots,\tilde{b}_{f\rightarrow v}^{t};w_{f},u_{f}),$ (40a)
$\displaystyle\tilde{b}_{f\rightarrow v}^{t}=\sum_{v^{\prime}\in\partial
f\setminus v}z_{fv^{\prime}}\tilde{q}_{v^{\prime}\rightarrow
f}^{t},\qquad\tilde{q}_{v\rightarrow
f}^{t}=\tilde{g}_{t}(\tilde{a}_{v\rightarrow
f}^{1},\ldots,\tilde{a}_{v\rightarrow f}^{t};\theta_{v},v_{v}),$ (40b)

with initialization $\tilde{q}_{v\rightarrow f}^{0}=g_{0}(\theta_{v},v_{v})$.
For $t\geq 0$, define the node beliefs

$\tilde{a}_{v}^{t+1}=\sum_{f\in\partial v}z_{fv}\tilde{r}_{f\rightarrow
v}^{t},\qquad\tilde{b}_{f}^{t}=\sum_{v\in\partial
f}z_{fv}\tilde{q}_{v\rightarrow f}^{t}.$ (41)

To compactify notation, denote
$\tilde{\boldsymbol{a}}_{v}^{t}=(\tilde{a}_{v}^{1},\ldots,\tilde{a}_{v}^{t})^{\mathsf{T}}$,
and likewise for $\tilde{\boldsymbol{a}}_{v\rightarrow f}^{t}$,
$\tilde{\boldsymbol{q}}_{v\rightarrow f}^{t}$,
$\tilde{\boldsymbol{b}}_{f}^{t}$, $\tilde{\boldsymbol{b}}_{f\rightarrow
v}^{t},\tilde{\boldsymbol{r}}_{f\rightarrow v}^{t}$ (where the first two of
these are $t$-dimensional, and the last three are $(t+1)$-dimensional). We
will often write $\tilde{f}_{t}(\tilde{\boldsymbol{b}}_{f\rightarrow
v}^{t};w_{f},u_{f})$ in place of $\tilde{f}_{t}(\tilde{b}_{f\rightarrow
v}^{0},\ldots,b_{f\rightarrow v}^{t};w_{f},u_{f})$, and similarly for
$\tilde{g}_{t}$. The reader should not confuse the bold font here with that in
Section 5, in which, for example, $\boldsymbol{a}_{v\rightarrow f}^{t}$
denotes the vectorial message at time $t$ rather than the collection of scalar
messages prior to and including time $t$.

Gaussian message passing obeys a Gaussian state evolution, defined by
covariance matrices

$\Sigma_{s,s^{\prime}}=\mathbb{E}[\tilde{g}_{s}(\tilde{\boldsymbol{A}}^{s};\Theta,V)\tilde{g}_{s^{\prime}}(\tilde{\boldsymbol{A}}^{s^{\prime}};\Theta,V)],\;\;\;T_{s+1,s^{\prime}+1}=\mathbb{E}[\tilde{f}_{s}(\tilde{\boldsymbol{B}}^{s};W,U)\tilde{f}_{s^{\prime}}(\tilde{\boldsymbol{B}}^{s^{\prime}};W,U)],$
(42)

where $s,s^{\prime}\geq 0$,
$\tilde{\boldsymbol{A}}^{s}\sim{\mathsf{N}}(\boldsymbol{0}_{s},\boldsymbol{T}_{[1{:}s]})$,
$\tilde{\boldsymbol{B}}^{s}\sim{\mathsf{N}}(\boldsymbol{0}_{s+1},\boldsymbol{\Sigma}_{[0{:}s]})$,
and $(\Theta,V)\sim\mu_{\Theta,V}$, $(W,U)\sim\mu_{W,U}$ independent of
$\tilde{\boldsymbol{A}}^{s},\tilde{\boldsymbol{B}}^{s}$. The iteration is
initialized by $\Sigma_{0,0}=\mathbb{E}[\tilde{g}_{0}(\Theta,V)^{2}]$.

######  Lemma 1.

If we choose a variable node $v$ and factor node $f$ independently of the
randomness in our model, then for fixed $t$ and for $n,p\rightarrow\infty$,
$n/p\rightarrow\delta$ we have

$\displaystyle(\tilde{\boldsymbol{a}}_{v}^{t},\theta_{v},v_{v})\stackrel{{\scriptstyle\mathrm{W}}}{{\rightarrow}}\mathsf{N}(\boldsymbol{0}_{t},\boldsymbol{T}_{[1{:}t]})\otimes\mu_{\Theta,V}\;\;\text{and}\;\;(\tilde{\boldsymbol{a}}_{v\rightarrow
f}^{t},\theta_{v},v_{v})\stackrel{{\scriptstyle\mathrm{W}}}{{\rightarrow}}\mathsf{N}(\boldsymbol{0}_{t},\boldsymbol{T}_{[1{:}t]})\otimes\mu_{\Theta,V},$
(43a)
$\displaystyle(\tilde{\boldsymbol{b}}_{f}^{t},w_{f},u_{f})\stackrel{{\scriptstyle\mathrm{W}}}{{\rightarrow}}\mathsf{N}(\boldsymbol{0}_{t+1},\boldsymbol{\Sigma}_{[0{:}t]})\otimes\mu_{W,U}\;\;\text{and}\;\;(\tilde{\boldsymbol{b}}_{f\rightarrow
v}^{t},w_{f},u_{f})\stackrel{{\scriptstyle\mathrm{W}}}{{\rightarrow}}\mathsf{N}(\boldsymbol{0}_{t+1},\boldsymbol{\Sigma}_{[0{:}t]})\otimes\mu_{W,U}.$
(43b)

Further, all the random variables in the preceding displays have bounded
fourth moments and
$\mathbb{E}[\|\tilde{\boldsymbol{a}}_{v}^{t}-\tilde{\boldsymbol{a}}_{v\rightarrow
f}^{t}\|^{2}]\rightarrow 0$ and
$\mathbb{E}[\|\tilde{\boldsymbol{b}}_{f}^{t}-\tilde{\boldsymbol{b}}_{f\rightarrow
v}^{t}\|^{2}]\rightarrow 0$.

The analysis of message passing on the tree is facilitated by the many
independence relationships between messages, which follow from the following
lemma.

######  Lemma 2.

For all $(f,v)\in\mathcal{E}$ and all $t$, the messages
$\tilde{r}_{f\rightarrow v}^{t},\tilde{b}_{f\rightarrow v}^{t}$ are
$\mathcal{T}_{f\rightarrow v}$-measurable, and the messages
$\tilde{q}_{v\rightarrow f}^{t},\tilde{a}_{a\rightarrow f}^{t}$ is
$\mathcal{T}_{v\rightarrow f}$-measurable.

###### Lemma 2.

The proof is by induction. The base case is that $\tilde{q}_{v\rightarrow
f}^{0}=g_{0}(\theta_{v},v_{v})$ is $\mathcal{T}_{v\rightarrow f}$-measurable.
Then, if $\tilde{q}_{v\rightarrow f}^{s}$ are $\mathcal{T}_{v\rightarrow
f}$-measurable and $\tilde{b}_{f\rightarrow v}^{s}$ are
$\mathcal{T}_{f\rightarrow v}$-measurable for $0\leq s\leq t$ and all
$(f,v)\in\mathcal{E}$, then $\tilde{b}_{f\rightarrow
v}^{t},\tilde{r}_{f\rightarrow v}^{t}$ are $\mathcal{T}_{f\rightarrow
v}$-measurable by (40). Similarly, if $\tilde{r}_{f\rightarrow v}^{s}$ are
$\mathcal{T}_{f\rightarrow v}$-measurable and $\tilde{a}_{v\rightarrow f}^{s}$
are $\mathcal{T}_{v\rightarrow r}$-measurable for $0\leq s\leq t$ and all
$(f,v)\in\mathcal{E}$, then $\tilde{a}_{f\rightarrow
v}^{t+1},\tilde{r}_{f\rightarrow v}^{t+1}$ are $\mathcal{T}_{v\rightarrow
f}$-measurable by (40). The induction is complete. ∎

We now prove Lemma 1.

###### Lemma 1.

The proof is by induction.

Base case:
$(\theta_{v},v_{f})\stackrel{{\scriptstyle\mathrm{W}}}{{\rightarrow}}\mu_{\Theta,V}$.

This is the exact distribution in finite samples by assumption.

Inductive step 1: Eq. (43a) at $t$, bounded fourth moments of
$\tilde{\boldsymbol{a}}_{v}^{t},\tilde{\boldsymbol{a}}_{v\rightarrow f}^{t}$,
and
$\mathbb{E}[\|\tilde{\boldsymbol{a}}_{v}^{t}-\tilde{\boldsymbol{a}}_{v\rightarrow
f}^{t}\|^{2}]\rightarrow 0$ imply Eq. (43b) at $t$, bounded fourth moments of
$\tilde{\boldsymbol{b}}_{f}^{t},\tilde{\boldsymbol{b}}_{f\rightarrow v}^{t}$,
and
$\mathbb{E}[\|\tilde{\boldsymbol{b}}_{f}^{t}-\tilde{\boldsymbol{b}}_{f\rightarrow
v}^{t}\|^{2}]\rightarrow 0$.

The $\sigma$-algebras $(\mathcal{T}_{v\rightarrow f})_{v\in\partial f}$ are
independent of $(z_{fv})_{v\in\partial f}$, which are mutually independent of
each other. Thus, by (41), conditional on $\sigma((\mathcal{T}_{v\rightarrow
f})_{v\in\partial f})$ the beliefs $\tilde{\boldsymbol{b}}_{f}^{t}$ are
jointly normal with covariance
$\widehat{\boldsymbol{\Sigma}}_{[0{:}t]}:=\frac{1}{n}\sum_{v\in\partial
f}\tilde{\boldsymbol{q}}_{v\rightarrow
f}^{t}(\tilde{\boldsymbol{q}}_{v\rightarrow f}^{t})^{\mathsf{T}}$. That is,

$\tilde{\boldsymbol{b}}_{f}^{t}\bigm{|}\sigma((\mathcal{T}_{v\rightarrow
f})_{v\in\partial
f})\sim\mathsf{N}(\boldsymbol{0}_{t+1},\widehat{\boldsymbol{\Sigma}}_{[0{:}t]}).$

Because $(\tilde{\boldsymbol{a}}_{v\rightarrow
f}^{t},\theta_{v},v_{v})\mapsto\tilde{g}_{s}(\tilde{\boldsymbol{a}}_{v\rightarrow
f}^{s};\theta_{v},v_{v})\tilde{g}_{s^{\prime}}(\tilde{\boldsymbol{a}}_{v\rightarrow
f}^{s^{\prime}};\theta_{v},v_{v})$ is uniformly pseudo-Lipschitz of order 2 by
Lemma 1, we have
$\mathbb{E}[\widehat{\Sigma}_{s,s^{\prime}}]=\mathbb{E}[\tilde{q}_{v\rightarrow
f}^{s}\tilde{q}_{v\rightarrow
f}^{s^{\prime}}]=\mathbb{E}[\tilde{g}_{s}(\tilde{\boldsymbol{a}}_{v\rightarrow
f}^{s};\theta_{v},v_{v})\tilde{g}_{s^{\prime}}(\tilde{\boldsymbol{a}}_{v\rightarrow
f}^{s^{\prime}};\theta_{v},v_{v})]\rightarrow\Sigma_{s,s^{\prime}}$ by the
inductive hypothesis, Lemma 2, and (42). The terms in the sum defining
$\widehat{\boldsymbol{\Sigma}}_{[0{:}t]}$ are mutually independent by Lemma 2
and have bounded second moments by the inductive hypothesis and the Lipschitz
continuity of the functions $(\tilde{g}_{s})_{0\leq s\leq t}$. By the weak law
of large numbers,
$\widehat{\boldsymbol{\Sigma}}_{[0{:}t]}\stackrel{{\scriptstyle
L_{1}}}{{\rightarrow}}\boldsymbol{\Sigma}_{[0{:}t]}$, whence by Slutsky’s
theorem,
$\tilde{\boldsymbol{b}}_{f}^{t}\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}{\mathsf{N}}(\boldsymbol{0}_{t+1},\boldsymbol{\Sigma}_{[0{:}t]})$.
Further,
$\mathbb{E}[\tilde{\boldsymbol{b}}_{f}^{t}(\tilde{\boldsymbol{b}}_{f}^{t})^{\mathsf{T}}]=\mathbb{E}[\widehat{\boldsymbol{\Sigma}}_{[0{:}t]}]\rightarrow\boldsymbol{\Sigma}_{[0{:}t]}$.
Convergence in distribution and in second moment implies convergence in the
Wasserstein space of order 2 [Vil10, Theorem 6.9], so
$\tilde{\boldsymbol{b}}_{f}^{t}\stackrel{{\scriptstyle\mathrm{W}}}{{\rightarrow}}{\mathsf{N}}(\boldsymbol{0}_{t+1},\boldsymbol{\Sigma}_{[0{:}t]})$.

To bound the fourth moments of $\tilde{b}_{f}^{t}$, we compute

$\mathbb{E}[(\tilde{b}_{f}^{t})^{4}]=\mathbb{E}[\widehat{\Sigma}_{t,t}^{2}]=\frac{1}{n^{2}}\sum_{v\in\partial
f}\mathbb{E}[(\tilde{q}_{v\rightarrow f}^{t})^{4}]+\frac{1}{n^{2}}\sum_{v\neq
v^{\prime}\in\partial f}\mathbb{E}[(\tilde{q}_{v\rightarrow
f}^{t})^{2}]\mathbb{E}[(\tilde{q}_{v^{\prime}\rightarrow
f}^{t})^{2}]\rightarrow\Sigma_{t,t},$

where the first term goes to 0 because the fourth moments of
$\tilde{q}_{v\rightarrow f}^{t}$ are bounded by the inductive hypothesis and
Lipschitz continuity of $\tilde{g}_{t}$, and the second term goes to
$\mathbb{E}[(\tilde{q}_{v\rightarrow f}^{t})^{2}]$ by the same argument in the
preceding paragraph. The boundedness of the fourth moments of
$\tilde{b}_{f}^{s}$ holds similarly (and, anyway, will have been established
earlier in the induction).

Finally, observe $\tilde{b}_{f}^{t}-\tilde{b}_{f\rightarrow
v}^{t}=z_{fv}\tilde{q}_{v\rightarrow f}^{t}$ and
$\mathbb{E}[(z_{fv}\tilde{q}_{v\rightarrow
f}^{t})^{2}]=\mathbb{E}[\tilde{q}_{v\rightarrow f}^{t})^{2}]/n\rightarrow 0$,
where $\mathbb{E}[\tilde{q}_{v\rightarrow f}^{t})^{2}]$ is bounded by the
inductive hypothesis and Lipschitz continuity of $\tilde{g}_{t}$. The
convergence $\mathbb{E}[(\tilde{b}_{f}^{t}-\tilde{b}_{f\rightarrow
v}^{s})^{2}]\rightarrow 0$ for $s<t$ holds similarly (and, anyway, will have
been established earlier in the induction). The Wasserstein convergence of
$(\tilde{\boldsymbol{b}}_{v\rightarrow f}^{t},\theta_{v},v_{v})$ now follows.
The bounded fourth moments of $\tilde{\boldsymbol{b}}_{v\rightarrow f}^{t}$
hold similarly.

Inductive step 2: Eq. (43) at $t$, bounded fourth moments of
$\tilde{\boldsymbol{b}}_{f}^{t},\tilde{\boldsymbol{b}}_{f\rightarrow v}^{t}$,
and
$\mathbb{E}[\|\tilde{\boldsymbol{b}}_{f}^{t}-\tilde{\boldsymbol{b}}_{f\rightarrow
v}^{t}\|^{2}]\rightarrow 0$ imply Eq. (43) at $t+1$, bounded fourth moments of
$\tilde{\boldsymbol{a}}_{v}^{t},\tilde{\boldsymbol{a}}_{v\rightarrow
f}^{t+1}$, and
$\mathbb{E}[\|\tilde{\boldsymbol{a}}_{v}^{t+1}-\tilde{\boldsymbol{a}}_{v\rightarrow
f}^{t+1}\|^{2}]\rightarrow 0$.

This follows by exactly the same argument as in inductive step 1.

The induction is complete, and Lemma 1 follows. ∎

###  C.2 Message passing in the high-dimensional regression model

We prove Lemma 2 for the high-dimensional regression model by showing that the
iteration (19) is well approximated by a Gaussian message passing algorithm
after a change of variables. The functions $\tilde{f}_{t},\tilde{g}_{t}$ in
the Gaussian message passing algorithm are defined in terms of the functions
$f_{t},g_{t}$ of the original message passing algorithm (19) and the function
$h$ used to define the high-dimensional regression model.

$\displaystyle\tilde{f}_{t}(\tilde{b}^{0},\cdots,\tilde{b}^{t},w,u):=f_{t}(\tilde{b}^{1},\cdots,\tilde{b}^{t};h(\tilde{b}^{0},w),u),\;\;t\geq
0,$
$\displaystyle\tilde{g}_{0}(\theta,v)=\theta,\;\;\tilde{g}_{t}(\tilde{a}^{1},\cdots,\tilde{a}^{t};\theta,v):=g_{t}(\alpha_{1}\theta+\tilde{a}^{1},\cdots,\alpha_{1}\theta+\tilde{a}^{t};v),\;\;t\geq
1.$

Define $(\tilde{a}_{v\rightarrow f}^{t})_{t\geq 1}$,
$(\tilde{a}_{v}^{t})_{t\geq 1}$, $(\tilde{q}_{v\rightarrow f}^{t})_{t\geq 0}$,
$(\tilde{b}_{f\rightarrow v}^{t})_{t\geq 0}$, $(\tilde{b}_{f}^{t})_{t\geq 0}$,
$(\tilde{r}_{f\rightarrow v}^{t})_{t\geq 0}$ via the Gaussian message passing
algorithm (40) with initial data $\theta_{v},v_{v},w_{f},u_{f}$ and with
$z_{fv}=x_{fv}$. Because $f_{t}$, $g_{t}$, and $h$ are Lipschitz, so too are
$\tilde{f}_{t}$ and $\tilde{g}_{t}$. Under the function definitions
$\tilde{f}_{t},\tilde{g}_{t}$ given above, the definitions of $\Sigma_{s,s}$
and $T_{s,s^{\prime}}$ in (42) and (36) are equivalent. Thus, Lemma 1 holds
for the iterates of this Gaussian message passing algorithm with the
$\boldsymbol{T}_{[1{:}t]}$, $\boldsymbol{\Sigma}_{[0{:}t]}$ defined by (36).

We claim that for fixed $s\geq 1$, as $n\rightarrow\infty$ we have

$\mathbb{E}[(\alpha_{s}\theta_{v}+\tilde{a}_{v\rightarrow
f}^{s}-a_{v\rightarrow f}^{s})^{2}]\rightarrow
0\;\;\text{and}\;\;\mathbb{E}[(\tilde{b}_{f\rightarrow v}^{s}-b_{f\rightarrow
v}^{s})^{2}]\rightarrow 0,$ (44a) and $\mathbb{E}[(a_{v\rightarrow
f}^{s})^{4}]\;\;\text{and}\;\;\mathbb{E}[(b_{f\rightarrow
v}^{s})^{4}]\;\;\mbox{are uniformly bounded with respect to $n$},$ (44b)

where $(\alpha_{s})$ are defined by (36). These are the same coefficients
appearing in the AMP state evolution (Lemma 1), as claimed. We show (44) by
induction. There is no base case because the inductive steps work for $t=0$ as
written.

Inductive step 1: If (44) holds for $1\leq s\leq t$, then (44a) holds for
$s=t+1$.

We expand

$\displaystyle\alpha_{t+1}\theta_{v}+\tilde{a}_{v\rightarrow
f}^{t+1}-a_{v\rightarrow f}^{t+1}$
$\displaystyle=\alpha_{t+1}\theta_{v}+\sum_{f^{\prime}\in\partial v\setminus
f}z_{f^{\prime}v}(\tilde{f}_{t}(\tilde{\boldsymbol{b}}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})-f_{t}(\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};y_{f^{\prime}},u_{f^{\prime}}))$
$\displaystyle=\alpha_{t+1}\theta_{v}+\sum_{f^{\prime}\in\partial v\setminus
f}z_{f^{\prime}v}(\tilde{f}_{t}(\tilde{\boldsymbol{b}}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})-\tilde{f}_{t}(\tilde{b}_{f^{\prime}\rightarrow
v}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}}))$
$\displaystyle\quad\quad+\sum_{f^{\prime}\in\partial v\setminus
f}z_{f^{\prime}v}(\tilde{f}_{t}(\tilde{b}_{f^{\prime}\rightarrow
v}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})-\tilde{f}_{t}(\tilde{b}_{f^{\prime}}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}}))$
$\displaystyle=:\alpha_{t+1}\theta_{v}+\mathsf{I}+\mathsf{II}.$

(Note that $\tilde{\boldsymbol{b}}_{f^{\prime}\rightarrow v}^{t}$ is
$(t+1)$-dimensional and $\boldsymbol{b}_{f^{\prime}\rightarrow v}^{t}$ is
$t$-dimensional). First we analyze $\mathsf{I}$. We have

$\displaystyle|\tilde{f}_{t}(\tilde{\boldsymbol{b}}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})-\tilde{f}_{t}(\tilde{b}_{f^{\prime}\rightarrow
v}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})|\leq
L\sum_{s=1}^{t}|\tilde{b}_{f^{\prime}\rightarrow
v}^{s}-b_{f^{\prime}\rightarrow v}^{s}|,$

where $L$ is a Lipschitz constant of $\tilde{f}_{t}$. The terms in the sum
defining $\mathsf{I}$ are mutually independent, and
$\tilde{b}_{f^{\prime}\rightarrow v}^{s},b_{f^{\prime}\rightarrow v}^{s}$ are
independent of $z_{f^{\prime}v}$. Thus,

$\displaystyle\mathbb{E}[\mathsf{I}^{2}]$
$\displaystyle=\frac{n-1}{n}\mathbb{E}[(\tilde{f}_{t}(\tilde{\boldsymbol{b}}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})-\tilde{f}_{t}(\tilde{b}_{f^{\prime}\rightarrow
v}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}}))^{2}]$
$\displaystyle\leq\frac{L^{2}(n-1)t}{n}\sum_{s=1}^{t}\mathbb{E}[(\tilde{b}_{f^{\prime}\rightarrow
v}^{s}-b_{f^{\prime}\rightarrow v}^{s})^{2}]\rightarrow 0,$

by the inductive hypothesis.

Next we analyze $\mathsf{II}$. Note that all arguments to the functions in the
sum defining $\mathsf{II}$ are independent of $z_{f^{\prime}v}$ and
$\theta_{v}$ except for
$\tilde{b}_{f^{\prime}}^{0}=z_{f^{\prime}v}\theta_{v}+\sum_{v^{\prime}\in\partial
f^{\prime}\setminus v}z_{f^{\prime}v^{\prime}}\theta_{v^{\prime}}$. Because
$\tilde{f}_{t}$ is Lipschitz, we may apply Stein’s lemma (ie., Gaussian
integration by parts) [Ste81] to get

$\displaystyle\mathbb{E}[\alpha_{t+1}\theta_{v}+\mathsf{II}\bigm{|}\theta_{v},\sigma((\mathcal{T}_{v^{\prime\prime}\rightarrow
f^{\prime}})_{v^{\prime\prime}\in\partial f^{\prime}\backslash v})]$
$\displaystyle=\alpha_{t+1}\theta_{v}+(n-1)\mathbb{E}\big{[}z_{f^{\prime}v}(\tilde{f}_{t}(\tilde{b}_{f^{\prime}\rightarrow
v}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})-\tilde{f}_{t}(\tilde{b}_{f^{\prime}}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}}))\bigm{|}\theta_{v}\big{]}$
$\displaystyle=\theta_{v}\left(\alpha_{t+1}-\frac{n-1}{n}\mathbb{E}[\partial_{\tilde{b}^{0}}\tilde{f}_{t}(\tilde{b}_{f^{\prime}}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})\bigm{|}\theta_{v}]\right),$

where $\partial_{\tilde{b}^{0}}\tilde{f}_{t}$ is the weak-derivative of
$\tilde{f}_{t}$ with respect to its first argument, which is defined almost
everywhere with respect to Lebesgue measure because $\tilde{f}_{t}$ is
Lipschitz [EG15, pg. 81].

We claim the right-hand side of the preceding display converges in $L_{2}$ to
0, as we now show. The random variable
$\mathbb{E}[\partial_{\tilde{b}^{0}}\tilde{f}_{t}(\tilde{b}_{f^{\prime}}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})|\theta_{v},(\mathcal{T}_{v^{\prime\prime}\rightarrow
f^{\prime}})_{v^{\prime\prime}\in\partial f^{\prime}\backslash v}]$ is almost-
surely bounded because $\tilde{f}_{t}$ is Lipschitz. It converges in
probability to $\alpha_{t+1}$. The random vector
$(\tilde{b}_{f^{\prime}}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow v}^{t})$
has a Gaussian distribution conditional on
$\sigma((\mathcal{T}_{v^{\prime\prime}\rightarrow
f^{\prime}})_{v^{\prime\prime}\in\partial f^{\prime}\backslash v})$ and
$\theta_{v}$; in particular,

$\displaystyle(\tilde{b}^{0}_{f^{\prime}\rightarrow
v}+z_{f^{\prime}v}\theta_{v},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t})|\theta_{v},\sigma((\mathcal{T}_{v^{\prime\prime}\rightarrow
f^{\prime}})_{v^{\prime\prime}\in\partial f^{\prime}\backslash
v})\stackrel{{\scriptstyle\mathrm{d}}}{{=}}{\mathsf{N}}(\mathbf{0},\widehat{\boldsymbol{\Sigma}}),$

where we define
$\widehat{\boldsymbol{\Sigma}}\in\mathbb{R}^{(t+1)\times(t+1)}$ by

$\displaystyle\widehat{\Sigma}_{0,0}=\dfrac{1}{n}\sum\limits_{v^{\prime}\in\partial
f^{\prime}}\theta_{v^{\prime}}^{2}\;\;\text{and}\;\;\widehat{\Sigma}_{s,s^{\prime}}=\dfrac{1}{n}\sum\limits_{v^{\prime}\in\partial
f^{\prime}\setminus v}q_{v^{\prime}\rightarrow
f^{\prime}}^{s}q_{v^{\prime}\rightarrow
f^{\prime}}^{s^{\prime}}\;\;\text{for}\;s\geq 1\mbox{ or }s^{\prime}\geq 1,$

where for the purposes of the preceding display we set
$q_{v^{\prime}\rightarrow f^{\prime}}^{0}=\theta_{v^{\prime}}$. By the
Lipschitz continuity of the functions $(g_{s})$, Lemmas 1 and 2, and the
inductive hypothesis, we have
$\mathbb{E}[\widehat{\boldsymbol{\Sigma}}]\rightarrow\boldsymbol{\Sigma}_{[0{:}t]}$.
The terms in the sums in the previous display have bounded second moments by
the inductive hypthesis (44b) and the Lipschitz continuity of the functions
$(g_{s})$. By the weak law of large numbers, we conclude
$\widehat{\boldsymbol{\Sigma}}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\boldsymbol{\Sigma}_{[0:t+1]}$.

Observe that
$\mathbb{E}[\partial_{\tilde{b}^{0}}\tilde{f}_{t}(\tilde{b}_{f^{\prime}}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})|\theta_{v},(\mathcal{T}_{v^{\prime\prime}\rightarrow
f^{\prime}})_{v^{\prime\prime}\in\partial f^{\prime}\backslash
v}]=\mathbb{E}[\partial_{\tilde{b}^{0}}\tilde{f}_{t}(\widehat{\boldsymbol{\Sigma}}^{1/2}\boldsymbol{Z};W,U)]$,
where on the right-hand side the expectation is with respect to
$(W,U)\sim\mu_{W,U}$ and
$\boldsymbol{Z}\sim{\mathsf{N}}(\boldsymbol{0}_{t+1},\boldsymbol{I}_{t+1})$
independent. Because $\partial_{\tilde{b}^{0}}\tilde{f}_{t}$ is almost surely
bounded, by the dominated convergence theorem, the right-hand side is
continuous in $\widehat{\boldsymbol{\Sigma}}$. By the continuous mapping
theorem and (36), we conclude
$\mathbb{E}[\partial_{\tilde{b}^{0}}\tilde{f}_{t}(\tilde{b}_{f^{\prime}}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})|\theta_{v},(\mathcal{T}_{v^{\prime\prime}\rightarrow
f^{\prime}})_{v^{\prime\prime}\in\partial f^{\prime}\backslash
v}]\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\alpha_{t+1}$. Then, by
dominated convergence,
$\mathbb{E}[\alpha_{t+1}\theta_{v}+\mathsf{II}\bigm{|}\theta_{v}]\stackrel{{\scriptstyle
L_{2}}}{{\rightarrow}}0$. Moreover, because the terms in the sum defining
$\mathsf{II}$ are mutually independent given $\theta_{v}$

$\displaystyle\operatorname{Var}(\alpha_{t+1}\theta_{v}+\mathsf{II}\mid\theta_{v})$
$\displaystyle\leq(n-1)\mathbb{E}\left[z_{f^{\prime}v}^{2}(\tilde{f}_{t}(\tilde{b}_{f^{\prime}\rightarrow
v}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}})-\tilde{f}_{t}(\tilde{b}_{f^{\prime}}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};w_{f^{\prime}},u_{f^{\prime}}))^{2}\mid\theta_{v}\right]$
$\displaystyle\leq
L^{2}(n-1)\mathbb{E}[z_{f^{\prime}v}^{4}\theta_{v}^{2}\mid\theta_{v}]\leq
3\theta_{v}^{2}/n,$

where $L$ is the Lipschitz constant of $\tilde{f}_{t}$. We conclude that
$\mathbb{E}[\operatorname{Var}(\alpha_{t+1}\theta_{v}+\mathsf{II}\mid\theta_{v})]\rightarrow
0$. Combined with
$\mathbb{E}[\alpha_{t+1}\theta_{v}+\mathsf{II}\bigm{|}\theta_{v}]\stackrel{{\scriptstyle
L_{2}}}{{\rightarrow}}0$, we get
$\operatorname{Var}(\alpha_{t+1}\theta_{v}+\mathsf{II})=\operatorname{Var}(\mathbb{E}[\alpha_{t+1}\theta_{v}+\mathsf{II}|\theta_{v}])+\mathbb{E}[\operatorname{Var}(\alpha_{t+1}\theta_{v}+\mathsf{II}|\theta_{v})]\rightarrow
0$, so that $\alpha_{t+1}\theta_{v}+\mathsf{II}\stackrel{{\scriptstyle
L_{2}}}{{\rightarrow}}0$. Combining $\mathsf{I}\stackrel{{\scriptstyle
L_{2}}}{{\rightarrow}}0$ and
$\alpha_{t+1}\theta_{v}+\mathsf{II}\stackrel{{\scriptstyle
L_{2}}}{{\rightarrow}}0$ gives
$\mathbb{E}[(\alpha_{t+1}\theta_{v}+\tilde{a}_{v\rightarrow
f}^{t+1}-a_{v\rightarrow f}^{t+1})^{2}]\rightarrow 0$, as desired.

We now expand

$\tilde{b}_{f\rightarrow v}^{t+1}-b_{f\rightarrow
v}^{t+1}=\sum_{v^{\prime}\in\partial f\setminus
v}z_{fv^{\prime}}(g_{t}(\boldsymbol{\alpha}_{t+1}\theta_{v^{\prime}}+\tilde{\boldsymbol{a}}_{v^{\prime}\rightarrow
f}^{t+1};v_{v^{\prime}})-g_{t}(\boldsymbol{a}_{v^{\prime}\rightarrow
f}^{t+1};v_{v^{\prime}})).$

The terms in this sum are mutually independent, and
$\tilde{\boldsymbol{a}}_{v^{\prime}\rightarrow
f}^{t+1},\boldsymbol{a}_{v^{\prime}\rightarrow f}^{t+1},\theta_{v^{\prime}}$
are independent of $z_{f^{\prime}v}$. Thus,

$\displaystyle\mathbb{E}[(\tilde{b}_{f\rightarrow v}^{t+1}-b_{f\rightarrow
v}^{t+1})^{2}]$
$\displaystyle=\frac{p-1}{n}\mathbb{E}[(g_{t}(\boldsymbol{\alpha}_{t+1}\theta_{v^{\prime}}+\tilde{\boldsymbol{a}}_{v^{\prime}\rightarrow
f}^{t+1};v_{v^{\prime}})-g_{t}(\boldsymbol{a}_{v^{\prime}\rightarrow
f}^{t+1};v_{v^{\prime}}))^{2}]$
$\displaystyle\leq\frac{L^{2}(p-1)(t+1)}{n}\sum_{s=1}^{t+1}\mathbb{E}[(\alpha_{s}\theta_{v^{\prime}}+\tilde{a}_{v^{\prime}\rightarrow
f}^{s}-a_{v^{\prime}\rightarrow f}^{s})^{2}]\rightarrow 0.$

This completes the proof of (44a) at $s=t+1$.

Inductive step 2: If (44) holds for $1\leq s\leq t$, then (44b) holds for
$s=t+1$.

By Lipschitz continuity,

$\displaystyle\left|a_{v\rightarrow f}^{t+1}-\sum_{f^{\prime}\in\partial
v\setminus f}z_{f^{\prime}v}\tilde{f}_{t}(\tilde{b}_{f^{\prime}\rightarrow
v}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t},u_{f^{\prime}},w_{f^{\prime}})\right|\leq
L|\theta_{v}|\sum_{f^{\prime}\in\partial v\setminus f}|z_{f^{\prime}v}|,$

where $L$ is a Lipschitz constant for $\tilde{f}_{t}$. The right-hand side has
bounded fourth moment, so we must only show that the sum in the previous
display has bounded fourth moment. The quantity
$\tilde{f}_{t}(\tilde{b}_{f^{\prime}\rightarrow
v}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t},u_{f^{\prime}},w_{f^{\prime}})$ has bounded fourth moment by the
inductive hypothesis and Lipschitz continuity of $\tilde{f}_{t}$. Because
$z_{f^{\prime}v}$ is independent of the argument to $\tilde{f}_{t}$ and has
fourth moment $3/n^{2}$, the product
$z_{f^{\prime}v}\tilde{f}_{t}(\tilde{b}_{f^{\prime}\rightarrow
v}^{0},\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t},u_{f^{\prime}},w_{f^{\prime}})$ has mean 0 and fourth moment
$O(1/n^{2})$. Because these products are mean zero and independent across
$f^{\prime}$, their sum has bounded fourth moment. We conclude
$a_{v\rightarrow f}^{t+1}$ has bounded fourth moment as well.

Recall $b_{f\rightarrow v}^{t+1}=\sum_{v^{\prime}\in\partial f\setminus
v}z_{fv^{\prime}}g_{t}(\boldsymbol{a}_{v^{\prime}\rightarrow
f}^{t+1};v_{v}^{\prime})$. The terms in the sum are independent, and
$z_{fv^{\prime}}$ is independent of $\boldsymbol{a}_{v^{\prime}\rightarrow
f}^{t+1};v_{v}^{\prime}$. Using the Lipschitz continuity of $g_{t}$ and the
inductive hypothesis, we conclude $b_{f\rightarrow v}^{t+1}$ has bounded
fourth moment by the same argument as in the preceding paragraph.

We conclude (44b) at $s=t+1$.

The induction is complete, and (44a) holds for all $s\geq 1$. Lemma 2 follows
by combining Lemma 1 and Eq. (44a).

###  C.3 Message passing in the low-rank matrix estimation model

Like in the preceding section, we prove Lemma 2 for the low-rank matrix
estimation model by showing that the iteration (19) is well approximated by a
Gaussian message passing algorithm after a change of variables. The functions
in the Gaussian message passing algorithm are defined in terms of the
functions $f_{t},g_{t}$ of the original message passing algorithm (19).

$\displaystyle\tilde{f}_{t}(\tilde{b}^{0},\cdots,\tilde{b}^{t},w,u):=f_{t}(\tilde{b}^{1}+\gamma_{1}w,\cdots,\tilde{b}^{t}+\gamma_{t}w;0,u),$
$\displaystyle\tilde{g}_{t}(\tilde{a}^{1},\cdots,\tilde{a}^{t};\theta,v):=g_{t}(\tilde{a}^{1}+\alpha_{1}\theta,\cdots,\tilde{a}^{t}+\alpha_{t}\theta;v).$

Note that here $\tilde{f}_{t}$ does not depend on $\tilde{b}^{0}$ is never
used, and we may define $\tilde{g}_{0}$ arbitrarily without affecting later
iterates.777The iterate $\tilde{b}^{0}$ only played a role in approximating
the high-dimensional regression message passing algorithm by a Gaussian
message passing algorithm. Define $(\tilde{a}_{v\rightarrow f}^{t})_{t\geq
1}$, $(\tilde{a}_{v}^{t})_{t\geq 1}$, $(\tilde{q}_{v\rightarrow f}^{t})_{t\geq
0}$, $(\tilde{b}_{f\rightarrow v}^{t})_{t\geq 0}$, $(\tilde{b}_{f}^{t})_{t\geq
0}$, $(\tilde{r}_{f\rightarrow v}^{t})_{t\geq 0}$ via the Gaussian message
passing algorithm (40) with initial data $\theta_{v},v_{v},u_{f},z_{fv}$ and
$w_{f}=\lambda_{f}$. Because $f_{t}$, $g_{t}$, and $h$ are Lipschitz, so too
are $\tilde{f}_{t}$ and $\tilde{g}_{t}$. Under the function definitions
$\tilde{f}_{t},\tilde{g}_{t}$ given above and the change of variables
$w_{f}=\lambda_{f}$, the definitions of $\Sigma_{s,s}$ and $T_{s,s^{\prime}}$
in (42) and (37) are equivalent. Thus, Lemma 1 holds for the iterates of this
Gaussian message passing algorithm with the $\boldsymbol{T}_{[1{:}t]}$,
$\boldsymbol{\Sigma}_{[0{:}t]}$ defined by (37).

We claim that for fixed $s\geq 1$, as $n\rightarrow\infty$ we have

$\mathbb{E}[(\alpha_{s}\theta_{v}+\tilde{a}_{v\rightarrow
f}^{s}-a_{v\rightarrow f}^{s})^{2}]\rightarrow
0\;\;\text{and}\;\;\mathbb{E}[(\gamma_{s}\lambda_{f}+\tilde{b}_{f\rightarrow
v}^{s}-b_{f\rightarrow v}^{s})^{2}]\rightarrow 0,$ (45a) and
$\mathbb{E}[\theta_{v}^{2}(a_{v\rightarrow
f}^{s})^{2}]\;\;\text{and}\;\;\mathbb{E}[\lambda_{f}^{2}(b_{f\rightarrow
v}^{s})^{2}]\;\;\text{are bounded for fixed $s$.}$ (45b)

We show this by induction. There is no base case because the inductive step
works for $t=0$ as written.

Inductive step: If (45) holds for $1\leq s\leq t$, then (45) holds for
$s=t+1$.

We expand

$\displaystyle\alpha_{t+1}\theta_{v}+\tilde{a}_{v\rightarrow
f}^{t+1}-a_{v\rightarrow f}^{t+1}$
$\displaystyle=\alpha_{t+1}\theta_{v}+\sum_{f^{\prime}\in\partial v\setminus
f}z_{f^{\prime}v}(f_{t}(\tilde{\boldsymbol{b}}_{f^{\prime}\rightarrow
v}^{t}+\boldsymbol{\gamma}_{t}\lambda_{f^{\prime}};0,u_{f^{\prime}})-f_{t}(\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};0,u_{f^{\prime}}))$
$\displaystyle\quad\quad-\frac{1}{n}\theta_{v}\sum_{f^{\prime}\in\partial
v\setminus f}\lambda_{f^{\prime}}f_{t}(\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};0,u_{f^{\prime}})$
$\displaystyle=:\alpha_{t+1}\theta_{v}+\mathsf{I}+\mathsf{II},$

where $\tilde{\boldsymbol{b}}_{f^{\prime}\rightarrow
v}^{t}=(\tilde{b}_{f^{\prime}\rightarrow
v}^{1},\ldots,\tilde{b}_{f^{\prime}\rightarrow v}^{t})$ and
$\boldsymbol{\gamma}_{t}=(\gamma_{1},\ldots,\gamma_{t})$ (note that
$\tilde{b}_{f^{\prime}\rightarrow v}^{0}$ is excluded, which differs from the
notation used in the proof of Lemma 2).

First we analyze $\mathsf{I}$. The terms in the sum defining $\mathsf{I}$ are
mutually independent, and $\tilde{b}_{f^{\prime}\rightarrow v}^{s}$,
$b_{f^{\prime}\rightarrow v}^{s}$, $\lambda_{f^{\prime}}$, $u_{f^{\prime}}$
are independent of $z_{f^{\prime}v}$. Thus,

$\displaystyle\mathbb{E}[\mathsf{I}^{2}]$
$\displaystyle=\frac{n-1}{n}\mathbb{E}[(f_{t}(\tilde{\boldsymbol{b}}_{f^{\prime}\rightarrow
v}^{t}+\boldsymbol{\gamma}_{t}\lambda_{f^{\prime}};0,u_{f^{\prime}})-f_{t}(\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};0,u_{f^{\prime}})^{2}]$
$\displaystyle\leq\frac{L^{2}(n-1)t}{n}\sum_{s=1}^{t}\mathbb{E}[(\tilde{b}_{f^{\prime}\rightarrow
v}^{s}+\gamma_{s}\lambda_{f^{\prime}}-b_{f^{\prime}\rightarrow
v}^{s})^{2}]\rightarrow 0,$

by the inductive hypothesis, where $L$ is a Lipschitz constant of $f_{t}$.
Moreover, because $\theta_{v}$ is independent of $\mathsf{I}$ and has bounded
fourth moment, $\mathbb{E}[\theta_{v}^{2}\mathsf{I}^{2}]\rightarrow 0$ as
well.

Next we analyze $\mathsf{II}$. By the inductive hypothesis and Lemma 1,

$(\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t},\lambda_{f^{\prime}},u_{f^{\prime}})\stackrel{{\scriptstyle\mathrm{W}}}{{\rightarrow}}(\boldsymbol{\gamma}_{t}\Lambda+\tilde{B}^{t},\Lambda,U),$

where $(\Lambda,U)\sim\mu_{\Lambda,U}$ and
$\tilde{B}^{t}\sim{\mathsf{N}}(\boldsymbol{0}_{t},\boldsymbol{\Sigma}_{[1{:}t]})$
independent. Because $(\boldsymbol{b}^{t},\lambda,u)\mapsto\lambda
f_{t}(\boldsymbol{b}^{t};0,u)$ is uniformly pseudo-Lipschitz of order 2 by
Lemma 1, we have
$\mathbb{E}[\lambda_{f^{\prime}}f_{t}(\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};0,u_{f^{\prime}})]\rightarrow\alpha_{t+1}$ by Lemma 2 and the state
evolution recursion (37). Moreover, because $f_{t}$ is Lipschitz, for some
constant $C$

$\displaystyle\mathbb{E}[\lambda_{f^{\prime}}^{2}f_{t}(\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};0,u_{f^{\prime}})^{2}]$ $\displaystyle\leq
C\mathbb{E}\left[\lambda_{f^{\prime}}^{2}\left(1+\sum_{s=1}^{t}(b_{f^{\prime}\rightarrow
v}^{s})^{2}+u_{f^{\prime}}^{2}\right)\right]$
$\displaystyle=C\left(\mathbb{E}[\lambda_{f^{\prime}}^{2}]+\sum_{s=1}^{t}\mathbb{E}[\lambda_{f^{\prime}}^{2}(b_{f^{\prime}\rightarrow
v}^{s})^{2}]+\mathbb{E}[\lambda_{f^{\prime}}^{2}u_{f^{\prime}}^{2}]\right),$

which bounded by the inductive hypothesis and the fourth moment assumption on
$\mu_{\Lambda,U}$. Because the terms in the sum defining $\mathsf{II}$ are
mutually independent, by the weak law of large numbers the preceding
observations imply

$\frac{1}{n}\sum_{f^{\prime}\in\partial v\setminus
f}\lambda_{f^{\prime}}f_{t}(\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};0,u_{f^{\prime}})\stackrel{{\scriptstyle
L_{2}}}{{\rightarrow}}\alpha_{t+1}.$

Because $\theta_{v}$ is independent of this sum and has bounded second moment,
we conclude that

$\alpha_{t+1}\theta_{v}+\mathsf{II}=\theta_{v}\left(\alpha_{t+1}-\frac{1}{n}\sum_{f^{\prime}\in\partial
v\setminus f}\lambda_{f^{\prime}}f_{t}(\boldsymbol{b}_{f^{\prime}\rightarrow
v}^{t};0,u_{f^{\prime}})\right)\stackrel{{\scriptstyle
L_{2}}}{{\rightarrow}}0.$

Moreover, because $\theta_{v}$ is independent of the term in parentheses and
has bounded fourth moment,
$\mathbb{E}[\theta_{v}^{2}(\alpha_{t+1}\theta_{v}+\mathsf{II})^{2}]\rightarrow
0$.

Combining the preceding results, we have that
$\mathbb{E}[(\alpha_{t+1}\theta_{v}+\tilde{a}_{v\rightarrow
f}^{t+1}-a_{v\rightarrow f}^{t+1})^{2}]\rightarrow 0$ and
$\mathbb{E}[\theta_{v}^{2}(\alpha_{t+1}\theta_{v}+\tilde{a}_{v\rightarrow
f}^{t+1}-a_{v\rightarrow f}^{t+1})^{2}]$ is bounded. Because $\theta_{v}$ is
independent of $\tilde{a}_{v\rightarrow f}^{t+1}$, the term
$\mathbb{E}[\theta_{v}^{2}(\tilde{a}_{v\rightarrow f}^{t+1})^{2}]$ is bounded,
so also $\mathbb{E}[\theta_{v}^{2}(a_{v\rightarrow f}^{t+1})^{2}]$ is bounded,
as desired.

The argument establishing that
$\mathbb{E}[(\gamma_{t+1}\lambda_{f}+\tilde{b}_{f\rightarrow
v}^{t+1}-b_{f\rightarrow v}^{t+1})^{2}]\rightarrow 0$ and that
$\mathbb{E}[\lambda_{f}^{2}(b_{f\rightarrow v}^{t+1})^{2}]$ is bounded is
equivalent. The induction is complete, and (45) holds for all $s$.

Lemma 2 follows by combining Lemma 1 and Eq. (45).

##  Appendix D Proof of information-theoretic lower bounds on the computation
tree (Lemma 3)

In this section, we prove Lemma 3 in both the high-dimensional regression and
low-rank matrix estimation models. We restrict ourselves to the case $r=1$ and
$k=1$ (with $k$ the dimensionality of $\boldsymbol{W}$) because the proof for
$r>1$ or $k>1$ is completely analogous but would complicate notation.

For any pair of nodes $u,u^{\prime}$ in the tree $\mathcal{T}$, let
$d(u,u^{\prime})$ denote the length (number of edges) of the shortest path
between nodes $u$ and $u^{\prime}$ in the tree. Let
$\mathcal{T}_{u,k}=(\mathcal{V}_{u,k},\mathcal{F}_{u,k},\mathcal{E}_{u,k})$ be
the radius-$k$ neighborhood of node $u$; that is,

$\displaystyle\mathcal{V}_{u,k}=\\{v\in\mathcal{V}\mid d(u,v)\leq k\\},$
$\displaystyle\mathcal{F}_{u,k}=\\{f\in\mathcal{F}\mid d(u,f)\leq k\\},$
$\displaystyle\mathcal{E}_{u,k}=\\{(f,v)\in\mathcal{E}\mid\max\\{d(u,f),d(u,v)\\}\leq
k\\}.$

With some abuse of notation, we will often use
$\mathcal{T}_{u,k},\mathcal{V}_{u,k},\mathcal{F}_{u,k},\mathcal{E}_{u,k}$ to
denote either the collection of observations corresponding to nodes and edges
in these sets or the $\sigma$-algebra generated by these obervations. No
confusion should result. Note, our convention is that when used to denote a
$\sigma$-algebra or collection of random variables, only observed random
variables are in include. Thus, in the high-dimensional regression model,
$\mathcal{T}_{u,k}$ is the $\sigma$-algebra generated by the local
observations $x_{fv}$, $y_{f}$, $v_{v}$, and $u_{f}$; in the low-rank matrix
estimation, it is the $\sigma$-algebra genreated by the local observations
$x_{fv}$, $v_{v}$, and $u_{f}$. We also denote by $\mathcal{T}_{v\rightarrow
f}^{t,k}$ the collection of observations associated to edges or nodes of
$\mathcal{T}$ which are separated from $f$ by $v$ by at least $k$ intervening
edges and at most $t$ intervening edges. For example,
$\mathcal{T}_{v\rightarrow f}^{1,1}$ contains only
$(y_{f^{\prime}})_{f^{\prime}\in\partial v\setminus f}$, and
$\mathcal{T}_{v\rightarrow f}^{2,1}$ contains additional the observations
$v_{v^{\prime}}$ and $x_{f^{\prime}v^{\prime}}$ for $v^{\prime}\in\partial
f^{\prime}\setminus v$ for some some $f^{\prime}\in\partial v\setminus f$. The
collections (or $\sigma$-algebras) $\mathcal{V}_{v\rightarrow f}^{t,k}$,
$\mathcal{F}_{v\rightarrow f}^{t,k}$, $\mathcal{E}_{v\rightarrow f}^{t,k}$ are
defined similarly, as are the versions of these where the roles of $v$ and $f$
are reversed.

###  D.1 Information-theoretic lower bound in the high-dimensional regression
model

In this section, we prove Lemma 3 in the high-dimensional regression model.

Note that conditions on the conditional density in assumption R4 are
equivalent positivity, boundedness, and the existence finite, non-negative
constants $q_{k}^{\prime}$ such that
$\frac{|\partial_{x}^{k}p(y|x)|}{p(y|x)}\leq q_{k}^{\prime}$ for $1\leq k\leq
5$. We will often use this form of the assumption without further comment.
This implies that for any random variable $A$

$\frac{|\partial_{x}^{k}\mathbb{E}[p(y|x+A)]|}{\mathbb{E}[p(y|x+A)]}\leq\int\frac{|\partial_{x}^{k}p(y|x+a)|}{p(y|x+a)}\frac{p(y|x+a)}{\mathbb{E}[p(y|x+A)]}\mu_{A}({\mathrm{d}}a)\leq
q_{k}^{\prime},$ (46)

because $p(y|x+a)/\mathbb{E}[p(y|x+A)]$ is a probability density with respect
to $\mu_{A}$, the distribution of $A$.

Denote the regular conditional probability of $\Theta$ conditional on $V$ for
the measure $\mu_{\Theta,V}$ by
$\mu_{\Theta|V}:\mathbb{R}\times\mathcal{B}\rightarrow[0,1]$, where
$\mathcal{B}$ denotes the Borel $\sigma$-algebra on $\mathbb{R}$. The
posterior of $\theta_{v}$ given $\mathcal{T}_{v,2t}$ has density with respect
to $\mu_{\Theta|V}(v_{v},\cdot)$ given by

$p_{v}(\vartheta|\mathcal{T}_{v,2t})\propto\int\prod_{f\in\mathcal{F}_{v,2t}}p(y_{f}\mid\sum_{v^{\prime}\in\partial
f}\vartheta_{v^{\prime}}X_{v^{\prime}f},u_{f})\prod_{v^{\prime}\in\mathcal{V}_{v,2t}\setminus
v}\mu_{\Theta|V}(v_{v^{\prime}},\mathrm{d}\vartheta_{v^{\prime}}).$

Asymptotically, the posterior density with respect to
$\mu_{\Theta|V}(v_{v},\cdot)$ behaves like that produced by a Gaussian
observation of $\theta_{v}$ with variance $\tau_{t}^{2}$, where $\tau_{t}$ is
defined by (5).

######  Lemma 1.

In the high-dimensional regression model, there exist
$\mathcal{T}_{v,2t}$-measurable random variables $\tau_{v,t},\chi_{v,t}$ such
that

$p_{v}(\vartheta|\mathcal{T}_{v,2t})\propto\exp\left(-\frac{1}{2\tau_{v,t}^{2}}(\chi_{v,t}-\vartheta)^{2}+o_{p}(1)\right),$

where $o_{p}(1)$ has no $\vartheta$ dependence. Moreover,
$(\chi_{v,t},\tau_{v,t},\theta_{v},v_{v})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta+\tau_{t}G,\tau_{t},\Theta,V)$
where $(\Theta,V)\sim\mu_{\Theta,V}$, $G\sim{\mathsf{N}}(0,1)$ independent of
$\Theta,V$, and $\tau_{t}$ is given by (5).

###### Lemma 1.

We compute the posterior density $p_{v}(\vartheta|\mathcal{T}_{v,2t})$ via an
iteration called belief propagation. For each edge $(v,f)\in\mathcal{E}$,
belief propagation generates a pair of sequences of real-valued functions
$(m_{v\rightarrow f}^{t}(\vartheta))_{t\geq 0},(m_{f\rightarrow
v}^{t}(\vartheta))_{t\geq 0}$. The iteration is

$\displaystyle m_{v\rightarrow f}^{0}(\vartheta)=1,$ $\displaystyle
m_{f\rightarrow v}^{s}(\vartheta)\propto\int
p(y_{f}|X_{fv}\vartheta+\sum_{v^{\prime}\in\partial f\setminus
v}X_{fv^{\prime}}\vartheta_{v^{\prime}},u_{f})\prod_{v^{\prime}\in\partial
f\setminus v}m_{v^{\prime}\rightarrow
f}^{s}(\vartheta_{v^{\prime}})\prod_{v^{\prime}\in\partial f\setminus
v}\mu_{\Theta|V}(v_{v^{\prime}},\mathrm{d}\vartheta_{v^{\prime}}),$
$\displaystyle m_{v\rightarrow
f}^{s+1}(\vartheta)\propto\prod_{f^{\prime}\in\partial v\setminus
f}m_{f^{\prime}\rightarrow v}^{s}(\vartheta),$

with normalization $\int m_{f\rightarrow
v}^{t}(\vartheta)\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta)=\int
m_{v\rightarrow f}^{t}(\vartheta)\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta)=1$.
For any variable node $v$,

$p_{v}(\vartheta|\mathcal{T}_{v,2t})\propto\prod_{f\in\partial
v}m_{f\rightarrow v}^{t-1}(\vartheta).$ (47)

This equation is exact.

We define several quantities related to the belief propagation iteration.

$\displaystyle\mu_{v\rightarrow f}^{s}$ $\displaystyle=\int\vartheta
m_{v\rightarrow f}^{s}(\vartheta)\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta),$
$\displaystyle(\tilde{\tau}_{v\rightarrow f}^{s})^{2}$
$\displaystyle=\int\vartheta^{2}m_{v\rightarrow
f}^{s}(\vartheta)\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta)-(\mu_{v\rightarrow
f}^{s})^{2},$ $\displaystyle\mu_{f\rightarrow v}^{s}$
$\displaystyle=\sum_{v^{\prime}\in\partial f\setminus
v}x_{fv^{\prime}}\mu_{v^{\prime}\rightarrow f}^{s},$
$\displaystyle(\tilde{\tau}_{f\rightarrow v}^{s})^{2}$
$\displaystyle=\sum_{v^{\prime}\in\partial f\setminus
v}x_{fv^{\prime}}^{2}(\tilde{\tau}_{v^{\prime}\rightarrow f}^{s})^{2},$
$\displaystyle a_{f\rightarrow v}^{s}$
$\displaystyle=\frac{1}{x_{fv}}\frac{\mathrm{d}\phantom{b}}{\mathrm{d}\vartheta}\log
m_{f\rightarrow v}^{s}(\vartheta)\Big{|}_{\vartheta=0},$ $\displaystyle
b_{f\rightarrow v}^{s}$
$\displaystyle=-\frac{1}{x_{fv}^{2}}\frac{\mathrm{d}^{2}\phantom{b}}{\mathrm{d}\vartheta^{2}}\log
m_{f\rightarrow v}^{s}(\vartheta)\Big{|}_{\vartheta=0},$ $\displaystyle
a_{v\rightarrow f}^{s}$
$\displaystyle=\frac{\mathrm{d}\phantom{b}}{\mathrm{d}\vartheta}\log
m_{v\rightarrow f}^{s}(\vartheta)\Big{|}_{\vartheta=0},$ $\displaystyle
b_{v\rightarrow f}^{s}$
$\displaystyle=-\frac{\mathrm{d}^{2}\phantom{b}}{\mathrm{d}\vartheta^{2}}\log
m_{v\rightarrow f}^{s}(\vartheta)\Big{|}_{\vartheta=0},$
$\displaystyle\chi_{v\rightarrow f}^{s}$ $\displaystyle=a_{v\rightarrow
f}^{s}/b_{v\rightarrow f}^{s},$ $\displaystyle(\tau_{v\rightarrow f}^{s})^{2}$
$\displaystyle=1/b_{v\rightarrow f}^{s}.$

Lemma 1 follows from the following asymptotic characterization of the
quantities in the preceding display in the limit $n,p\rightarrow\infty$,
$n/p\rightarrow\delta$:

$\begin{gathered}\qquad\mathbb{E}[(\mu_{v\rightarrow
f}^{s})^{2}]\rightarrow\delta\sigma_{s}^{2},\qquad\mathbb{E}[(\tilde{\tau}_{v\rightarrow
f}^{s})^{2}]\rightarrow\delta\tilde{\tau}_{s}^{2},\\\ (\mu_{f\rightarrow
v}^{s},u_{f})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}{\mathsf{N}}(0,\sigma_{s}^{2})\otimes\mu_{U},\qquad(\tilde{\tau}_{f\rightarrow
v}^{s})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\tilde{\tau}_{s}^{2},\\\
(\theta_{v},v_{v},a_{v\rightarrow f}^{s}/b_{v\rightarrow
f}^{s},b_{v\rightarrow
f}^{s})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta,V,\Theta+\tau_{s}G,1/\tau_{s}^{2}),\end{gathered}$
(48)

where in the last line $\Theta\sim\mu_{\Theta}$, $G\sim{\mathsf{N}}(0,1)$
independent, and $\sigma_{s}^{2},\tau_{s}^{2}$ are defined in (5). By
symmetry, the distribution of these quantities does not depend upon $v$ or
$f$, so that the limits holds for all $v,f$ once we establish them for any
$v,f$. We establish the limits inductively in $s$.

Base case: $\mathbb{E}[(\mu_{v\rightarrow
f}^{0})^{2}]\rightarrow\delta\sigma_{0}^{2}$ and
$\mathbb{E}[(\tilde{\tau}_{v\rightarrow
f}^{0})^{2}]\rightarrow\delta\tilde{\tau}_{0}^{2}$.

Observe that $\mu_{v\rightarrow
f}^{s}=\int\vartheta\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta)=\mathbb{E}_{\Theta,V}[\Theta|V=v_{v}]$.
Because $v_{v}\sim\mu_{V}$, we have $\mathbb{E}[(\mu_{v\rightarrow
f}^{1})^{2}]=\mathbb{E}_{\Theta,V}[\mathbb{E}_{\Theta,V}[\Theta|V]^{2}]=\mathbb{E}[\Theta^{2}]-\textsf{mmse}_{\Theta,V}(\infty)=\delta\sigma_{1}^{2}$.
Similarly, $(\tilde{\tau}_{v\rightarrow
f}^{1})^{2}=\operatorname{Var}_{\Theta,V}(\Theta|V=v_{v})$, so that
$\mathbb{E}[(\tilde{\tau}_{v\rightarrow
f}^{1})^{2}]=\textsf{mmse}_{\Theta,V}(\infty)=\delta\tilde{\tau}_{0}^{2}$.

Inductive step 1: If $\mathbb{E}[(\mu_{v\rightarrow
f}^{s})^{2}]\rightarrow\delta\sigma_{s}^{2}$, then $(\mu_{f\rightarrow
v}^{s},u_{f})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}{\mathsf{N}}(0,\sigma_{s}^{2})\otimes\mu_{U}$.

The quantity $\mu_{v^{\prime}\rightarrow f}^{s}$ is
$\mathcal{T}_{v^{\prime}\rightarrow f}^{2s,0}$-measurable, whence it is
independent of $x_{fv^{\prime}}$ and $u_{f}$. Moreover,
$(\mu_{v^{\prime}\rightarrow f},x_{fv})$ are independent as we vary
$v^{\prime}\in\partial f\setminus v$. Thus, $\mu_{f\rightarrow
v}^{s}|\mathcal{T}_{f\rightarrow
v}^{2s+1,1}\sim{\mathsf{N}}(0,\frac{1}{n}\sum_{v^{\prime}\in\partial
f\setminus v}(\mu_{v^{\prime}\rightarrow f}^{s})^{2})$. Note that
$\mathbb{E}[\frac{1}{n}\sum_{v^{\prime}\in\partial f\setminus
v}(\mu_{v^{\prime}\rightarrow f}^{s})^{2}]=(p-1)\mathbb{E}[(\mu_{v\rightarrow
f}^{s})^{2}]/n\rightarrow\sigma_{s}^{2}$ by the inductive hypothesis.
Moreover, $\mu_{v\rightarrow f}^{s}$ has bounded fourth moments because it is
bounded by $M$. By the weak law of large numbers,
$\frac{1}{n}\sum_{v^{\prime}\in\partial f\setminus
v}(\mu_{v^{\prime}\rightarrow
f}^{s})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\sigma_{s}^{2}$.
We conclude by Slutsky’s theorem and independence that $(\mu_{f\rightarrow
v}^{s},u_{f})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}{\mathsf{N}}(0,\sigma_{s}^{2})\otimes\mu_{U}$.

Inductive step 2: If $\mathbb{E}[(\tilde{\tau}_{v\rightarrow
f}^{s})^{2}]\rightarrow\delta\tilde{\tau}_{s}^{2}$, then
$(\tilde{\tau}_{f\rightarrow
v}^{s})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\tilde{\tau}_{s}^{2}$.

The quantity $\tilde{\tau}_{v^{\prime}\rightarrow f}^{s}$ is
$\mathcal{T}_{v^{\prime}\rightarrow f}^{2s,0}$-measurable, whence it is
independent of $x_{fv^{\prime}}$. Therefore,

$\mathbb{E}[\sum_{v^{\prime}\in\partial f\setminus
v}x_{fv^{\prime}}^{2}(\tilde{\tau}_{v^{\prime}\rightarrow
f}^{s})^{2}]=(p-1)\mathbb{E}[(\tilde{\tau}_{v\rightarrow
f}^{s})^{2}]/n\rightarrow\tilde{\tau}_{s}^{2}.$

Moreover, $(\tilde{\tau}_{v^{\prime}\rightarrow f},x_{fv})$ are mutually
independent as we vary $v^{\prime}\in\partial f\setminus v$, and because
$\tilde{\tau}_{v\rightarrow f}^{s}$ is bounded by $M$, the terms
$nx_{fv^{\prime}}^{2}(\sigma_{v^{\prime}\rightarrow f}^{s})^{2}$ have bounded
fourth moments. By the weak law of large numbers, $(\tilde{\tau}_{f\rightarrow
v}^{s})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\tilde{\tau}_{s}^{2}$.

Inductive step 3: If $(\mu_{f\rightarrow
v}^{s},u_{f},\tilde{\tau}_{f\rightarrow
v}^{s})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}{\mathsf{N}}(0,\sigma_{s}^{2})\otimes\mu_{U}\otimes\delta_{\tilde{\tau}_{s}}$,
then $(\theta_{v},v_{v},a_{v\rightarrow f}^{s+1}/b_{v\rightarrow
f}^{s+1},b_{v\rightarrow
f}^{s+1})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta,V,\Theta+\tau_{s+1}G,1/\tau_{s+1}^{2})$
where $G\sim{\mathsf{N}}(0,1)$ independent of $(\Theta,V)\sim\mu_{\Theta,V}$.

For all $(f,v)\in\mathcal{E}$ and $s\geq 1$, define

$p_{f\rightarrow v}^{s}(y;x)=\int p(y|x+\sum_{v^{\prime}\in\partial f\setminus
v}x_{fv^{\prime}}\vartheta_{v^{\prime}},u_{f})\prod_{v^{\prime}\in\partial
f\setminus v}m_{v^{\prime}\rightarrow
f}^{s}(\vartheta_{v^{\prime}})\prod_{v^{\prime}\in\partial f\setminus
v}\mu_{\Theta|V}(v_{v^{\prime}},\mathrm{d}\vartheta_{v^{\prime}}).$

More compactly, we may write $p_{f\rightarrow
v}^{s}(y;x,u_{f})=\mathbb{E}_{\\{\Theta_{v^{\prime}}\\}}[p(y|x+\sum_{v^{\prime}\in\partial
f\setminus v}x_{fv^{\prime}}\Theta_{v^{\prime}},u_{f})]$, where it is
understood that the expectation is taken over $\Theta_{v^{\prime}}$
independent with densities $m_{v^{\prime}\rightarrow f}^{s}$ with respect to
$\mu_{\Theta|V}(v_{v^{\prime}},\cdot)$. Note that for all $x$, we have

$\int p_{f\rightarrow v}^{s}(y;x){\mathrm{d}}y=1$

everywhere. That is, $p_{f\rightarrow v}^{s}(\cdot;x)$ is a probability
density with respect to Lebesgue measure. We will denote by
$\dot{p}_{f\rightarrow
v}^{s}(y;x)=\frac{\mathrm{d}\phantom{b}}{\mathrm{d}\xi}p_{f\rightarrow
v}^{s}(y;x)\big{|}_{\xi=x}$, and likewise for higher derivatives. These
derivatives exist and may be taken under the integral by R4. Define

$a_{f\rightarrow v}^{s}(y)=\frac{\mathrm{d}\phantom{b}}{\mathrm{d}x}\log
p_{f\rightarrow v}^{s}(y;x)\Big{|}_{x=0}\qquad\text{ and }\qquad
b_{f\rightarrow
v}^{s}(y)=-\frac{\mathrm{d}^{2}\phantom{b}}{\mathrm{d}x^{2}}\log
p_{f\rightarrow v}^{s}(y;x)\Big{|}_{x=0}.$

For fixed $y$, the quantity $a_{f^{\prime}\rightarrow v}^{s}(y)$ is
independent of $x_{f^{\prime}v}$, and $(a_{f^{\prime}\rightarrow
v}^{s}(y),x_{f^{\prime}v})$ are mutually independent for
$f^{\prime}\in\partial v\setminus f$. Observe that

$\displaystyle a_{f\rightarrow v}^{s}=a_{f\rightarrow
v}^{s}(y_{f})\qquad\text{and}\qquad a_{v\rightarrow
f}^{s+1}=\sum_{f^{\prime}\in\partial v\setminus
f}x_{f^{\prime}v}a_{f^{\prime}\rightarrow v}^{s}(y_{f^{\prime}}),$
$\displaystyle b_{f\rightarrow v}^{s}=b_{f\rightarrow
v}^{s}(y_{f})\qquad\text{and}\qquad b_{v\rightarrow
f}^{s+1}=\sum_{f^{\prime}\in\partial v\setminus
f}x_{f^{\prime}v}^{2}b_{f^{\prime}\rightarrow v}^{s}(y_{f^{\prime}}).$

We will study the distributions of $a_{f\rightarrow v}^{s},a_{v\rightarrow
f}^{s+1},b_{f\rightarrow v}^{s}$, and $b_{v\rightarrow f}^{s+1}$ under several
measures, which we now introduce. Define $P_{v,\vartheta}$ to be the
distribution of the regression model with $\theta_{v}$ forced to be $\theta$
and $v_{v}$ forced to be 0. That is, under $P_{v,\theta}$, we have
$(\theta_{v^{\prime}},v_{v^{\prime}})\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mu_{\Theta,V}$
for $v^{\prime}\neq v$, $v_{v}=0$ and $\theta_{v}=\theta$, the features are
distributed independently
$x_{fv^{\prime}}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}{\mathsf{N}}(0,1/n)$
for all $f,v^{\prime}$, and the observations $y_{f}$ are drawn independently
from $p(\cdot|\sum_{v^{\prime}\in\partial
f}x_{fv^{\prime}}\theta_{v^{\prime}})$ for all $f$. We will consider the
distribution of $a_{f\rightarrow v}^{s},a_{v\rightarrow
f}^{s+1},b_{f\rightarrow v}^{s}$, and $b_{v\rightarrow f}^{s+1}$ under
$P_{v,\theta}$ for $\theta\in[-M,M]$.

We require the following lemmas, whose proofs are deferred to Section D.1.1.

######  Lemma 2.

Under $P_{v,\theta}$ for any $\theta\in[-M,M]$, we have for all fixed $y$ that

$\displaystyle p_{f\rightarrow
v}^{s}(y;0)-\mathbb{E}_{G_{1}}[p(y|\mu_{f\rightarrow
v}^{s}+\tilde{\tau}_{f\rightarrow v}^{s}G_{1},u_{f})]=o_{p}(1),$
$\displaystyle\dot{p}_{f\rightarrow
v}^{s}(y;0)-\mathbb{E}_{G_{1}}[\dot{p}(y|\mu_{f\rightarrow
v}^{s}+\tilde{\tau}_{f\rightarrow v}^{s}G_{1},u_{f})]=o_{p}(1),$
$\displaystyle\ddot{p}_{f\rightarrow
v}^{s}(y;0)-\mathbb{E}_{G_{1}}[\ddot{p}(y|\mu_{f\rightarrow
v}^{s}+\tilde{\tau}_{f\rightarrow v}^{s}G_{1},u_{f})]=o_{p}(1),$

where the expectation is over $G_{1}\sim{\mathsf{N}}(0,1)$. Further, for any
$u$, the functions
$(\mu,\tilde{\tau})\mapsto\mathbb{E}_{G_{1}}[p(y|\mu+\tilde{\tau}G_{1},u)]$,
$(\mu,\tilde{\tau})\mapsto\mathbb{E}_{G_{1}}[\dot{p}(y|\mu+\tilde{\tau}G_{1},u)]$,
and
$(\mu,\tilde{\tau})\mapsto\mathbb{E}_{G_{1}}[\ddot{p}(y|\mu+\tilde{\tau}G_{1},u)]$
are continuous.

######  Lemma 3.

Under $P_{v,\theta}$ for any $\theta\in[-M,M]$, we have for any fixed $s$

$\log\frac{m_{v\rightarrow f}^{s+1}(\vartheta)}{m_{v\rightarrow
f}^{s+1}(0)}=\vartheta a_{v\rightarrow
f}^{s+1}-\frac{1}{2}\vartheta^{2}b_{v\rightarrow f}^{s+1}+O_{p}(n^{-1/2}),$

where $O_{p}(n^{-1/2})$ has no $\vartheta$ dependence, and the statement holds
for $\vartheta\in[-M,M]$.

First we study the distribution of $a_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1}$ under $P_{v,0}$. Because $\mu_{f^{\prime}\rightarrow
v}^{s},\tilde{\tau}_{f^{\prime}\rightarrow v}^{s}$ is independent of
$\theta_{v},v_{v}$ for all $f^{\prime}\in\partial v$, its distribution is the
same under $P_{v,\theta}$ for all $\theta\in[-M,M]$ and is equal to its
distribution under the original model. Thus, the inductive hypothesis implies
$(\mu_{f\rightarrow v}^{s},\tilde{\tau}_{f\rightarrow
v}^{s})\xrightarrow[P_{v,0}]{\mathrm{d}}{\mathsf{N}}(0,\sigma_{s}^{2})\times\delta_{\tilde{\tau}_{s}}$.

By Lemma 2, the inductive hypothesis, and Lemma 3, we have for fixed $y$

$\begin{pmatrix}\mathbb{E}_{G_{1}}[p(y|\mu_{f\rightarrow
v}^{s}+\tilde{\tau}_{f\rightarrow v}^{s}G_{1},u_{f})]\\\
\mathbb{E}_{G_{1}}[\dot{p}(y|\mu_{f\rightarrow
v}^{s}+\tilde{\tau}_{f\rightarrow v}^{s}G_{1},u_{f})]\\\
\mathbb{E}_{G_{1}}[\ddot{p}(y|\mu_{f\rightarrow
v}^{s}+\tilde{\tau}_{f\rightarrow
v}^{s}G_{1},u_{f})]\end{pmatrix}\xrightarrow[P_{v,0}]{\mathrm{d}}\begin{pmatrix}\mathbb{E}_{G_{1}}[p(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U]\\\
\mathbb{E}_{G_{1}}[\dot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]\\\
\mathbb{E}_{G_{1}}[\ddot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]\end{pmatrix},$

where and $G_{0},G_{1}\sim{\mathsf{N}}(0,1)$ and $U\sim\mu_{U}$ independent.
Applying Lemma 2 and Slutsky’s Theorem, we have that

$\begin{pmatrix}p_{f\rightarrow v}^{s}(y;0)\\\ \dot{p}_{f\rightarrow
v}^{s}(y;0)\\\ \ddot{p}_{f\rightarrow
v}^{s}(y;0)\end{pmatrix}\xrightarrow[P_{v,0}]{\mathrm{d}}\begin{pmatrix}\mathbb{E}_{G_{1}}[p(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]\\\
\mathbb{E}_{G_{1}}[\dot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]\\\
\mathbb{E}_{G_{1}}[\ddot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]\end{pmatrix}.$

By the Continuous Mapping Theorem,

$\displaystyle p_{f\rightarrow
v}^{s}(y;0)\xrightarrow[P_{v,0}]{\mathrm{d}}\mathbb{E}_{G_{1}}[p(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)],$
$\displaystyle a_{f\rightarrow
v}^{s}(y)\xrightarrow[P_{v,0}]{\mathrm{d}}\frac{\mathrm{d}\phantom{b}}{\mathrm{d}x}\log\mathbb{E}_{G_{1}}[\dot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]\Big{|}_{x=0},$
$\displaystyle b_{f\rightarrow
v}^{s}(y)\xrightarrow[P_{v,0}]{\mathrm{d}}-\frac{\mathrm{d}^{2}\phantom{b}}{\mathrm{d}x^{2}}\log\mathbb{E}_{G_{1}}[\dot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]\Big{|}_{x=0}.$

Because the quantity $p(y|x)$ is bounded (assumption R4) and the quantities
$a_{f\rightarrow v}^{s}(y),b_{f\rightarrow v}^{s}(y)$ are bounded by (46), we
have

$\displaystyle\mathbb{E}_{P_{v,0}}[p_{f\rightarrow
v}^{s}(y|0)]\rightarrow\mathbb{E}_{G_{0},G_{1},U}[p(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)],$
$\displaystyle\mathbb{E}_{P_{v,0}}[a_{f\rightarrow
v}^{s}(y)^{2}]\rightarrow\mathbb{E}_{G_{0},U}\left[\left(\frac{\mathrm{d}\phantom{b}}{\mathrm{d}x}\log\mathbb{E}_{G_{1}}[\dot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]\Big{|}_{x=0}\right)^{2}\right],$
$\displaystyle\mathbb{E}_{P_{v,0}}[b_{f\rightarrow
v}^{s}]\rightarrow-\mathbb{E}_{G_{0},U}\left[\frac{\mathrm{d}^{2}\phantom{b}}{\mathrm{d}x^{2}}\log\mathbb{E}_{G_{1}}[\dot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]\Big{|}_{x=0}\right].$

Under $P_{v,0}$, we have for all $f^{\prime}\in\partial v$ that the random
variable $y_{f^{\prime}}$ is independent of $x_{f^{\prime}v}$. Thus,
conditional on $\mathcal{T}_{v\rightarrow f}^{2s+2,1}$, the random variable
$\sum_{f^{\prime}\in\partial v\setminus
f}x_{f^{\prime}v}a_{f^{\prime}\rightarrow v}^{s}(y_{f^{\prime}})$ is normally
distributed. Specifically,

$\sum_{f^{\prime}\in\partial v\setminus
f}x_{f^{\prime}v}a_{f^{\prime}\rightarrow
v}^{s}(y_{f^{\prime}})\bigm{|}\mathcal{T}_{v\rightarrow
f}^{2s+2,1}\underset{P_{v,0}}{\sim}{\mathsf{N}}\left(0,\frac{1}{n}\sum_{f^{\prime}\in\partial
v\setminus f}(a_{f^{\prime}\rightarrow v}^{s}(y_{f^{\prime}}))^{2}\right).$

Because $(a_{f^{\prime}\rightarrow v}^{s}(y_{f^{\prime}}))^{2}$ is bounded by
(46), if we show $\mathbb{E}_{P_{v,0}}[(a_{f\rightarrow
v}^{s}(y_{f}))^{2}]\rightarrow 1/\tau_{s+1}^{2}$, then the weak law of large
numbers and Slutsky’s theorem will imply that

$a_{v\rightarrow f}^{s+1}=\sum_{f^{\prime}\in\partial v\setminus
f}x_{f^{\prime}v}a_{f^{\prime}\rightarrow
v}^{s}(y_{f^{\prime}})\xrightarrow[P_{v,0}]{\mathrm{d}}{\mathsf{N}}\left(0,1/\tau_{s+1}^{2}\right).$
(49)

We compute

$\displaystyle\mathbb{E}_{P_{v,0}}[(a_{f\rightarrow v}^{s}(y_{f}))^{2}]$
$\displaystyle=\mathbb{E}_{P_{v,0}}[\mathbb{E}_{P_{v,0}}[(a_{f\rightarrow
v}^{s}(y_{f}))^{2}|\sigma(\mathcal{T}_{f\rightarrow
v}^{2s+1,1},(x_{fv^{\prime}})_{v^{\prime}\in\partial f\setminus v}),u_{f}]]$
$\displaystyle=\mathbb{E}_{P_{v,0}}\left[\int a_{f\rightarrow
v}^{s}(y)^{2}p_{f\rightarrow v}^{s}(y;0){\mathrm{d}}y\right]$
$\displaystyle=\int\mathbb{E}_{P_{v,0}}\left[a_{f\rightarrow
v}^{s}(y)^{2}p_{f\rightarrow v}^{s}(y;0)\right]{\mathrm{d}}y.$

where the second equation holds because under $P_{v,0}$ we have
$y_{f}\mid\sigma(\mathcal{T}_{f\rightarrow
v}^{2s+1,1},(x_{fv^{\prime}})_{v^{\prime}\in\partial f\setminus v},u_{f})$ has
density $p_{f\rightarrow v}^{s}(\cdot;0)$ with respect to Lebesgue measure,
and the last equation follows by Fubini’s theorem (using the non-negativity of
the integrand). Because $a_{f\rightarrow
v}^{s}(y)^{2}\leq(q_{1}^{\prime})^{2}$ and
$\mathbb{E}_{P_{v,0}}[p_{f\rightarrow v}^{s}(y;0)]$ are probability densities
which converge pointwise to
$\mathbb{E}_{G_{1}}[p(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1})]$, we conclude
that

$\displaystyle\mathbb{E}_{P_{v,0}}[(a_{f\rightarrow v}^{s}(y_{f}))^{2}]$
$\displaystyle\rightarrow\int\mathbb{E}_{G_{0},U}\left[\frac{\mathbb{E}_{G_{1}}[\dot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]^{2}}{\mathbb{E}_{G_{1}}[p(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]}\right]{\mathrm{d}}y$
$\displaystyle=\mathbb{E}_{G_{0},U}\left[\int\frac{\mathbb{E}_{G_{1}}[\dot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]^{2}}{\mathbb{E}_{G_{1}}[p(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]}{\mathrm{d}}y\right]=\frac{1}{\tau_{s+1}^{2}},$

where we have used the alternative characterization of the recursion (5) from
Lemma 4. We conclude (49).

Now we compute the asymptotic behavior of $b_{v\rightarrow f}^{s+1}$ under
$P_{v,0}$. Under $P_{v,0}$, $x_{f^{\prime}v}$ is independent of
$y_{f^{\prime}}$, and $(x_{f^{\prime}v},b_{f^{\prime}\rightarrow
v}^{s}(y_{f^{\prime}}))$ are mutually independent for $f^{\prime}\in\partial
v\setminus f$. Thus,
$\mathbb{E}_{P_{v,0}}[x_{f^{\prime}v}^{2}b_{f^{\prime}\rightarrow
v}^{s}(y_{f^{\prime}})]=\mathbb{E}_{P_{v,0}}[b_{f^{\prime}\rightarrow
v}^{s}(y_{f^{\prime}})]/n$. Because $b_{f^{\prime}\rightarrow
v}^{s}(y_{f^{\prime}})$ is bounded by (46), if we can show that
$\mathbb{E}_{P_{v,0}}[b_{f^{\prime}\rightarrow
v}^{s}(y_{f^{\prime}})]\rightarrow 1/\tau_{s+1}^{2}$, then $b_{v\rightarrow
f}^{s+1}\xrightarrow[P_{v,0}]{\mathrm{p}}1/\tau_{s+1}^{2}$ will follow by the
weak law of large numbers. We compute

$\displaystyle\mathbb{E}_{P_{v,0}}[b_{f\rightarrow v}^{s}(y_{f})]$
$\displaystyle=\mathbb{E}_{P_{v,0}}[\mathbb{E}_{P_{v,0}}[b_{f\rightarrow
v}^{s}(y_{f})|\sigma(\mathcal{T}_{f\rightarrow
v}^{2s+1,1},(x_{fv^{\prime}})_{v^{\prime}\in\partial f\setminus v},u_{f})]]$
$\displaystyle=\mathbb{E}_{P_{v,0}}\left[\int b_{f\rightarrow
v}^{s}(y)p_{f\rightarrow v}^{s}(y;0){\mathrm{d}}y\right]$
$\displaystyle=\int\mathbb{E}_{P_{v,0}}\left[b_{f\rightarrow
v}^{s}(y)p_{f\rightarrow v}^{s}(y;0)\right]{\mathrm{d}}y$

where the last equation follows by Fubini’s theorem (using that the integrand
is bounded by the integrable function
$q_{2}\mathbb{E}_{P_{v,0}}[p_{f\rightarrow v}^{s}(y;0)]$). The integrands
converge point-wise, so that

$\displaystyle\mathbb{E}_{P_{v,0}}$ $\displaystyle[b_{f\rightarrow
v}^{s}(y_{f})]$
$\displaystyle\rightarrow\mathbb{E}_{G_{0},U}\left[\int\frac{\mathbb{E}_{G_{1}}[\dot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]^{2}}{\mathbb{E}_{G_{1}}[p(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]}{\mathrm{d}}y\right]-\int\mathbb{E}_{G_{0},G_{1},U}[\ddot{p}(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]{\mathrm{d}}y$
$\displaystyle=\frac{1}{\tau_{s+1}^{2}},$

where we have concluded that the second integral is zero because
$x\mapsto\mathbb{E}_{G_{0},G_{1},U}[p(y|\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},U)]$
parameterizes a statistical model whose scores up to order 3 are bounded by
(46). Thus, we conclude that $b_{v\rightarrow
f}^{s+1}\xrightarrow[P_{v,0}]{\mathrm{p}}1/\tau_{s+1}^{2}$.

Now we compute the asymptotic distribution of $(a_{v\rightarrow
f}^{s+1},b_{v\rightarrow f}^{s+1})$ under $P_{v,\theta}$ for any
$\theta\in[-M,M]$. The log-likelihood ratio between $P_{v,\theta}$ and
$P_{v,0}$ is

$\displaystyle\sum_{f^{\prime}\in\partial v}\log\frac{p_{f^{\prime}\rightarrow
v}^{s}(y_{f^{\prime}}|x_{f^{\prime}v}\theta)}{p_{f^{\prime}\rightarrow
v}^{s}(y_{f^{\prime}}|0)}$ $\displaystyle=\log\frac{m_{v\rightarrow
f}^{s+1}(\theta)}{m_{v\rightarrow f}^{s+1}(0)}+\log\frac{p_{f\rightarrow
v}^{s}(y_{f}|x_{fv}\theta)}{p_{f\rightarrow v}^{s}(y_{f}|0)}$
$\displaystyle=\theta a_{v\rightarrow
f}^{s+1}-\frac{1}{2}\theta^{2}b_{v\rightarrow f}^{s+1}+O_{p}(n^{-1/2}),$

where we have used Lemma 3 and that $\left|\log\frac{p_{f\rightarrow
v}^{s}(y_{f}|x_{fv}\theta)}{p_{f\rightarrow v}^{s}(y_{f}|0)}\right|\leq
Mq_{1}|x_{fv}|=O_{p}(n^{-1/2})$. Thus,

$\left(a_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1},\log\frac{P_{v,\theta}}{P_{v,0}}\right)\xrightarrow[P_{v,0}]{\mathrm{p}}\left(Z,\frac{1}{\tau_{s+1}^{2}},\theta
Z-\frac{1}{2}\frac{\theta^{2}}{\tau_{s+1}^{2}}\right),$

where $Z\sim{\mathsf{N}}(0,1/\tau_{s+1}^{2})$. By Le Cam’s third lemma [Vaa98,
Example 6.7], we have

$(a_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1})\xrightarrow[P_{v,\theta}]{\mathrm{d}}\left(Z^{\prime},\frac{1}{\tau_{s+1}^{2}}\right).$

where $Z^{\prime}\sim{\mathsf{N}}(\theta/\tau_{s+1}^{2},1/\tau_{s+1}^{2})$. By
the Continuous Mapping Theorem [Vaa98, Theorem 2.3], we conclude
$(a_{v\rightarrow f}^{s+1}/b_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1})\xrightarrow[P_{v,\theta}]{\mathrm{d}}{\mathsf{N}}(\theta,\tau_{s+1}^{2})\otimes\delta_{1/\tau_{s+1}^{2}}$.

Denote by $P^{*}$ the distribution of the the original model. Consider a
continuous bounded function $f:(\theta,\nu,\chi,b)\mapsto\mathbb{R}$, and
define
$\hat{f}_{n}(\theta,\nu)=\mathbb{E}_{P_{v,\theta}}[f(\theta,\nu,a_{v\rightarrow
f}^{s+1}/b_{v\rightarrow f}^{s+1},b_{v\rightarrow f}^{s+1})]$. Under $P^{*}$,
the random variables $a_{v\rightarrow f}^{s+1},b_{v\rightarrow f}^{s+1}$ are
functions are $\theta_{v}$ and random vectors
$\boldsymbol{D}:=\mathcal{T}_{v,2t}\setminus\\{\theta_{v},v_{v}\\}$, which is
independent of $\theta_{v},v_{v}$. In particular, we may write

$\mathbb{E}_{P^{*}}[f(\theta_{v},v_{v},a_{v\rightarrow
f}^{s+1}/b_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1})]=\mathbb{E}_{P^{*}}[f(\theta_{v},v_{v},\chi(\theta_{v},\boldsymbol{D}),B(\theta_{v},\boldsymbol{D}))],$

for some measurable functions $\chi,B$. We see that

$\mathbb{E}_{P^{*}}[f(\theta_{v},v_{v},a_{v\rightarrow
f}^{s+1}/b_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1})\mid\theta_{v},v_{v}]=\hat{f}_{n}(\theta_{v},v_{v})$

where

$\hat{f}_{n}(\theta,\nu)=\mathbb{E}_{\boldsymbol{D}}[f(\theta,\nu,\chi(\theta,\boldsymbol{D}),B(\theta,\boldsymbol{D}))],$

with $\boldsymbol{D}$ distributed as it is under $P^{*}$ (see e.g., [Dur10,
Example 5.1.5]). Because $\boldsymbol{D}$ has the same distribution on $P^{*}$
as under $P_{v,\theta}$, we see that in fact
$\hat{f}_{n}(\theta,\nu)=\mathbb{E}_{P_{v,\theta}}[f(\theta,\nu,a_{v\rightarrow
f}^{s+1}/b_{v\rightarrow f}^{s+1},b_{v\rightarrow f}^{s+1})]$. Because
$(a_{v\rightarrow f}^{s+1}/b_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1})\xrightarrow[P_{v,\theta}]{\mathrm{d}}{\mathsf{N}}(\theta,\tau_{s+1}^{2})\otimes\delta_{1/\tau_{s+1}^{2}}$,
we conclude that
$\hat{f}_{n}(\theta,\nu)\rightarrow\mathbb{E}_{G}[f(\theta,\nu,\theta+\tau_{s+1}G,\tau_{s+1}^{-2})]$
for all $\theta,\nu$. By bounded convergence and the tower property,
$\mathbb{E}_{\Theta,V}[\hat{f}_{n}(\Theta,V)]\rightarrow\mathbb{E}_{\Theta,V,G}[f(\theta,\nu,\theta+\tau_{s+1}G,\tau_{s+1}^{-2})]$
where $(\Theta,V)\sim\mu_{\Theta,V}$ independent of $G\sim{\mathsf{N}}(0,1)$.
Also by the tower property, we have

$\mathbb{E}_{\Theta,V}[\hat{f}_{n}(\Theta,V)]=\mathbb{E}_{P^{*}}[f(\theta_{v},v_{v},\chi(\theta_{v},\boldsymbol{D}),B(\theta_{v},\boldsymbol{D}))]=\mathbb{E}_{P^{*}}[f(\theta_{v},v_{v},a_{v\rightarrow
f}^{s+1}/b_{v\rightarrow f}^{s+1},b_{v\rightarrow f}^{s+1})].$

We conclude

$\mathbb{E}_{P^{*}}[f(\theta_{v},v_{v},a_{v\rightarrow
f}^{s+1}/b_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1})]\rightarrow\mathbb{E}_{\Theta,V,G}[f(\Theta,V,\Theta+\tau_{s+1}G,\tau_{s+1}^{-2})].$

Thus, we conclude that $(\theta_{v},v_{v},a_{v\rightarrow
f}^{s+1}/b_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1})\xrightarrow[P^{*}]{\mathrm{d}}(\Theta,V,\Theta+\tau_{s+1}G,1/\tau_{s+1}^{2})$,
as desired.

Inductive step 4: If $(\theta_{v},v_{v},a_{v\rightarrow
f}^{s+1}/b_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta,V,\Theta+\tau_{s+1}G,1/\tau_{s+1}^{2})$
where $G\sim{\mathsf{N}}(0,1)$ independent of $(\Theta,V)\sim\mu_{\Theta,V}$,
then $\mathbb{E}[(\mu_{v\rightarrow
f}^{s})^{2}]\rightarrow\delta\sigma_{s}^{2}$ and
$\mathbb{E}[(\tilde{\tau}_{v\rightarrow
f}^{s})^{2}]\rightarrow\textsf{mmse}_{\Theta,V}(\tau_{s}^{2})$.

Define

$\epsilon_{v\rightarrow
f}^{s}=\sup_{\vartheta\in[-M,M]}\left|\log\frac{m_{v\rightarrow
f}^{s}(\vartheta)}{m_{v\rightarrow f}^{s}(0)}-\left(\vartheta a_{v\rightarrow
f}^{s}-\frac{1}{2}\vartheta^{2}b_{v\rightarrow f}^{s}\right)\right|,$

where because all the terms are continuous in $\vartheta$, the random variable
$\epsilon_{v\rightarrow f}^{s}$ is measurable and finite. We have that

$\mu_{v\rightarrow f}^{s}\geq\frac{\int\vartheta\exp(\vartheta a_{v\rightarrow
f}^{s}-\vartheta^{2}b_{v\rightarrow f}^{s}/2-\epsilon_{v\rightarrow
f}^{s})\mu_{\Theta}(v_{v},\mathrm{d}\vartheta)}{\int\exp(\vartheta
a_{v\rightarrow f}^{s}-\vartheta^{2}b_{v\rightarrow
f}^{s}/2+\epsilon_{v\rightarrow
f}^{s})\mu_{\Theta}(v_{v},\mathrm{d}\vartheta)}\geq
e^{-2\epsilon_{v\rightarrow f}^{s}}\eta_{\Theta,V}(a_{v\rightarrow
f}^{s}/b_{v\rightarrow f}^{s},v_{v};1/b_{v\rightarrow f}^{s})$

where
$\eta_{\Theta,V}(y,v;\tau^{2})=\mathbb{E}_{\Theta,V,G}[\Theta|\Theta+\tau
G=y;V=v]$ where $(\Theta,V)\sim\mu_{\Theta,V}$, $G\sim{\mathsf{N}}(0,1)$
independent. Likewise,

$\mu_{v\rightarrow f}^{s}\leq e^{2\epsilon_{v\rightarrow
f}^{s}}\eta_{\Theta,V}(a_{v\rightarrow f}^{s}/b_{v\rightarrow
f}^{s},v_{v};1/b_{v\rightarrow f}^{s}).$

Because $\eta_{\Theta,V}$ takes values in the bounded interval $[-M,M]$ and
$\epsilon_{v\rightarrow f}=o_{p}(1)$ by Lemma 3, we conclude that

$\mu_{v\rightarrow f}^{s}=\eta_{\Theta,V}(a_{v\rightarrow
f}^{s}/b_{v\rightarrow f}^{s},v_{v};1/b_{v\rightarrow f}^{s})+o_{p}(1).$

For a fixed $v_{v}$, the Bayes estimator $\eta_{\Theta,V}$ is continuous in
the observation and the noise variance on
$\mathbb{R}\times\mathbb{R}_{>0}$.888This commonly known fact holds, for
example, by [LR05, Theorem 2.7.1] because the posterior mean can be viewed as
the mean in an exponential family paramterized by the observation and noise
variance. Thus, by the inductive hypothesis and the fact that
$v_{v}\sim\mu_{V}$ for all $n$, we have
$\mathbb{E}[\eta_{\Theta,V}(a_{v\rightarrow f}^{s}/b_{v\rightarrow
f}^{s},v_{v};1/b_{v\rightarrow
f}^{s})^{2}]=\mathbb{E}[\eta_{\Theta,V}(a_{v\rightarrow f}^{s}/b_{v\rightarrow
f}^{s},v_{v};1/b_{v\rightarrow f}^{s})^{2}\vee
M^{2}]\rightarrow\mathbb{E}_{\Theta,V,G}[\eta_{\Theta,V}(\Theta+\tau_{s}G,V;\tau_{s}^{2})]=\mathbb{E}[\Theta^{2}]-\textsf{mmse}_{\Theta,V}(\tau_{s}^{2})=\delta\sigma_{s}^{2}$
by Lemma 3. By the previous display and the boundedness of $\mu_{v\rightarrow
f}^{s}$ and $\eta_{\Theta,V}$, we conclude $\mathbb{E}[(\mu_{v\rightarrow
f}^{s})^{2}]\rightarrow\delta\sigma_{s}^{2}$, as desired.

Similarly, we may derive that

$\displaystyle e^{-2\epsilon_{v\rightarrow
f}^{s}}s_{\Theta,V}^{2}(a_{v\rightarrow f}^{s}/b_{v\rightarrow
f}^{s},v_{v};1/b_{v\rightarrow f}^{s})$
$\displaystyle\leq\int\vartheta^{2}m_{v\rightarrow
f}^{s}(\vartheta)\mu_{\Theta}(\mathrm{d}\vartheta)$ $\displaystyle\leq
e^{2\epsilon_{v\rightarrow f}^{s}}s_{\Theta,V}^{2}(a_{v\rightarrow
f}^{s}/b_{v\rightarrow f}^{s},v_{v};1/b_{v\rightarrow f}^{s}),$

where
$s_{\Theta,V}^{2}(y,v;\tau^{2})=\mathbb{E}_{\Theta,V,G}[\Theta^{2}|\Theta+\tau
G=y,V=v]$ where $(\Theta,V)\sim\mu_{\Theta,V}$, $G\sim{\mathsf{N}}(0,1)$
independent. For fixed $v_{v}$, the the posterior second moment is continuous
in the observation and the noise variance. Further, it is bounded by $M^{2}$.
Thus, by exactly the same argument as in the previous paragraph, we have that
$\mathbb{E}[(\tilde{\tau}_{v\rightarrow
f}^{s})^{2}]\rightarrow\mathbb{E}_{\Theta,V,G}[s_{\Theta,V}^{2}(\Theta+\tau_{s}G,V;\tau_{s}^{2})-\eta_{\Theta,V}(\Theta+\tau_{s}G,V;\tau_{s}^{2})^{2}]=\textsf{mmse}_{\Theta,V}(\tau_{s}^{2})$,
as desired.

The inductive argument is complete, and (48) is established.

To complete the proof of Lemma 1, first observe by (47) that we may express
$\log p_{v}(\vartheta|\mathcal{T}_{v,2t})$ as, up to a constant,
$\log\frac{m_{v\rightarrow f}^{t}(\vartheta)}{m_{v\rightarrow
f}^{t}(0)}+\log\frac{m_{f\rightarrow v}^{t-1}(\vartheta)}{m_{f\rightarrow
v}^{t-1}(0)}$. Note that

$\left|\log\frac{m_{f\rightarrow v}^{t-1}(\vartheta_{v})}{m_{f\rightarrow
v}^{t-1}(0)}\right|\leq
M|x_{fv}|\sup_{x\in\mathbb{R}}\left|\frac{\dot{p}_{f\rightarrow
v}^{t-1}(y_{f};x)}{p_{f\rightarrow v}^{t-1}(y_{f};x)}\right|\leq
Mq_{1}|x_{fv}|=o_{p}(1).$

By Lemma 3, we have that, up to a constant, $\log\frac{m_{v\rightarrow
f}^{t}(\vartheta)}{m_{v\rightarrow f}^{t}(0)}=-\frac{1}{2}b_{v\rightarrow
f}^{s}\left(a_{v\rightarrow f}^{t}/b_{v\rightarrow
f}^{t}-\vartheta\right)^{2}+o_{p}(1)$. The lemma follows from (48). ∎

We complete the proof of Lemma 3 for the high-dimensional regression model.
Consider any estimator $\hat{\theta}:\mathcal{T}_{v,2t}\mapsto[-M,M]$ on the
computation tree. We compute

$\displaystyle\mathbb{E}[\ell(\theta_{v},\hat{\theta}(\mathcal{T}_{v,2t}))]=\mathbb{E}[\mathbb{E}[\ell(\theta_{v},\hat{\theta}(\mathcal{T}_{v,2t}))|\mathcal{T}_{v,2t}]]$
$\displaystyle\qquad=\mathbb{E}\left[\int\ell(\vartheta,\hat{\theta}(\mathcal{T}_{v,2t}))\frac{1}{Z(\mathcal{T}_{v,2t})}\exp\left(-\frac{1}{2\tau_{v,t}^{2}}(\chi_{v,t}-\vartheta)^{2}+o_{p}(1)\right)\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta)\right]$
$\displaystyle\qquad\geq\mathbb{E}\left[\exp(-2\epsilon_{v})\int\ell(\vartheta,\hat{\theta}(\mathcal{T}_{v,2t}))\frac{1}{Z(\chi_{v,t},\tau_{v,t},v_{v})}\exp\left(-\frac{1}{2\tau_{v,t}^{2}}(\chi_{v,t}-\vartheta)^{2}\right)\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta)\right]$
$\displaystyle\qquad\geq\mathbb{E}\left[\exp(-2\epsilon_{v})R(\chi_{v,2t},\tau_{v,2t},v_{v})\right],$

where
$Z(\mathcal{T}_{v,2t})=\int\exp\left(-\frac{1}{2\tau_{v,t}^{2}}(\chi_{v,t}-\vartheta)^{2}+o_{p}(1)\right)\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta)$,

$R(\chi,\tau,v):=\inf_{d\in\mathbb{R}}\int\frac{1}{Z}\ell(\vartheta,d)e^{-\frac{1}{2\tau^{2}}(\chi-\vartheta)^{2}}\mu_{\Theta|V}(v,{\mathrm{d}}\vartheta)\,,$

and

$\epsilon_{v}=\sup_{\vartheta\in[-M,M]}\left|\log\frac{p(\vartheta|\mathcal{T}_{v,2t})}{p(0|\mathcal{T}_{v,2t})}+\vartheta\chi_{v,t}/\tau_{v,t}^{2}-\vartheta^{2}/(2\tau_{v,t}^{2})\right|.$

Because $\Theta$ is bounded support, by Lemma 5(b), $R(\chi,\tau,v)$ is
continuous in $(\chi,\tau)$ on $\mathbb{R}\times\mathbb{R}_{>0}$. By Lemma 1,
$\epsilon_{v}=o_{p}(1)$. The quantity on the right-hand side does not depend
on $\hat{\theta}$, so provides a uniform lower bound over the performance of
any estimator. Because
$(v_{v},\chi_{v,2t},\tau_{v,2t},\epsilon_{v})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(V,\Theta+\tau_{t}G,\tau_{t},0)$,
$v_{v}\stackrel{{\scriptstyle\mathrm{d}}}{{=}}V$ for all $n$, and
$\tau_{t}>0$, we have
$\mathbb{E}\left[\exp(-2\epsilon_{v})R(\chi_{v,2t},\tau_{v,2t},v_{v})\right]\rightarrow\mathbb{E}[R(\Theta+\tau_{t}G,\tau_{t},V)]=\inf_{\hat{\theta}(\cdot)}\mathbb{E}[\ell(\Theta,\hat{\theta}(\Theta+\tau_{t}G,V))]$,
where the convergence holds by Lemma 3 and the equality holds by Lemma 5(a).
Thus,

$\liminf_{n\rightarrow\infty}\inf_{\hat{\theta}(\cdot)}\mathbb{E}[\ell(\theta_{v},\hat{\theta}(\mathcal{T}_{v,2t}))]\geq\inf_{\hat{\theta}(\cdot)}\mathbb{E}[\ell(\Theta,\hat{\theta}(\Theta+\tau_{t}G))].$

The proof of Lemma 3 in the high-dimensional regression model is complete.

####  D.1.1 Technical tools

###### Lemma 2.

By Lindeberg’s principle (see, e.g., [Cha06]) and using that $\mu_{\Theta}$ is
supported on $[-M,M]$, we have

$\displaystyle|p_{f\rightarrow
v}^{s}(y;0)-\mathbb{E}_{G_{1}}[p(y|\mu_{f\rightarrow
v}^{s}+\tilde{\tau}_{f\rightarrow
v}^{s}G_{1},u_{f})]|\leq\frac{M^{3}\sup_{x\in\mathbb{R}}|\partial_{x}^{3}p(y|x,u_{f})|}{3}\sum_{v^{\prime}\in\partial
f\setminus v}|x_{fv^{\prime}}|^{3},$ $\displaystyle|\dot{p}_{f\rightarrow
v}^{s}(y;0)-\mathbb{E}_{G_{1}}[\dot{p}(y|\mu_{f\rightarrow
v}^{s}+\tilde{\tau}_{f\rightarrow
v}^{s}G_{1},u_{f})]|\leq\frac{M^{3}\sup_{x\in\mathbb{R}}|\partial_{x}^{4}p(y|x,u_{f})|}{3}\sum_{v^{\prime}\in\partial
f\setminus v}|x_{fv^{\prime}}|^{3},$ $\displaystyle|\ddot{p}_{f\rightarrow
v}^{s}(y;0)-\mathbb{E}_{G_{1}}[\ddot{p}(y|\mu_{f\rightarrow
v}^{s}+\tilde{\tau}_{f\rightarrow
v}^{s}G_{1},u_{f})]|\leq\frac{M^{3}\sup_{x\in\mathbb{R}}|\partial_{x}^{5}p(y|x,u_{f})|}{3}\sum_{v^{\prime}\in\partial
f\setminus v}|x_{fv^{\prime}}|^{3}.$

Using the $\sup_{x\in\mathbb{R}}|\partial_{x}^{k}p(y|x,u)|\leq
q_{k}^{\prime}\sup_{x\in\mathbb{R}}|p(y|x,u)|<\infty$ for $k=3,4,5$ by R4, we
have that for fixed $y$ the expectations on the right-hand side go to 0 as
$n\rightarrow\infty$, whence the required expessions are $o_{p}(1)$.

Further,
$|\mathbb{E}_{G_{1}}[p(y|\mu+\tilde{\tau}G_{1},u)]-\mathbb{E}_{G_{1}}[p(y|\mu^{\prime}+\tilde{\tau}^{\prime}G_{1},u)]|\leq(|\mu-\mu^{\prime}|+|\tilde{\tau}-\tilde{\tau}^{\prime}|\sqrt{2/\pi})\sup_{x\in\mathbb{R}}|\dot{p}(y|x,u)|$,
whence $\mathbb{E}_{G_{1}}[p(y|\mu+\tilde{\tau}G_{1},u)]$ is continuous in
$(\mu,\tilde{\tau})$ by R4. The remaining continuity results follow similarly.
∎

###### Lemma 3.

Fix any $\vartheta\in[-M,M]$. By Taylor’s theorem, there exist
$\vartheta_{i}\in[-M,M]$ (in fact, between $0$ and $\vartheta$) such that

$\displaystyle\log$ $\displaystyle\frac{m_{v\rightarrow
f}^{s+1}(\vartheta)}{m_{v\rightarrow f}^{s+1}(0)}=\sum_{f^{\prime}\in\partial
v\setminus f}\log\frac{m_{f^{\prime}\rightarrow
v}^{s}(\vartheta)}{m_{f^{\prime}\rightarrow v}^{s}(0)}$
$\displaystyle=\vartheta a_{v\rightarrow
f}^{s+1}-\frac{1}{2}\vartheta^{2}b_{v\rightarrow
f}^{s+1}+\frac{1}{6}\vartheta^{3}\sum_{f^{\prime}\in\partial v\setminus
f}\left(\frac{\mathrm{d}^{3}}{\mathrm{d}\vartheta^{3}}\log\mathbb{E}_{\hat{G}_{f^{\prime}}}[p(y_{f^{\prime}}|x_{f^{\prime}v}\vartheta+\hat{G}_{f^{\prime}},u_{f^{\prime}})]\bigg{|}_{\vartheta=\vartheta_{i}}\right).$

where it is understood that expectation is taken with respect to
$\hat{G}_{f^{\prime}}\stackrel{{\scriptstyle\mathrm{d}}}{{=}}\sum_{v^{\prime}\in\partial
f^{\prime}\setminus v}x_{f^{\prime}v^{\prime}}\Theta_{v^{\prime}\rightarrow
f^{\prime}}$ where $x_{f^{\prime}v^{\prime}}$ is considered fixed and
$\Theta_{v^{\prime}\rightarrow f^{\prime}}$ are drawn independently with
densities $m_{v^{\prime}\rightarrow f^{\prime}}^{s}$ with respect to
$\mu_{\Theta|V}(v_{v^{\prime}},\cdot)$. We bound the sum using assumption R4:

$\displaystyle\left|\sum_{f^{\prime}\in\partial v\setminus
f}\left(\frac{\mathrm{d}^{3}}{\mathrm{d}\vartheta^{3}}\log\mathbb{E}_{\hat{G}_{f^{\prime}}}[p(y_{f}|x_{fv}\vartheta+\hat{G}_{f^{\prime}},u_{f^{\prime}})]\bigg{|}_{\vartheta=\vartheta_{i}}\right)\right|$
$\displaystyle\leq q_{3}\sum_{f^{\prime}\in\partial v\setminus
f}|x_{f^{\prime}v}|^{3}=O_{p}(n^{-1/2}).$

The proof is complete. ∎

###  D.2 Information-theoretic lower bound in the low-rank matrix estimation
model

In this section, we prove Lemma 3 in the low-rank matrix estimation model.

Recall that conditions on the conditional density in assumption R4 are
equivalent positivity, boundedness, and the existence finite, non-negative
constants $q_{k}^{\prime}$ such that
$\frac{|\partial_{x}^{k}p(y|x)|}{p(y|x)}\leq q_{k}^{\prime}$ for $1\leq k\leq
5$. In particular, we have (46) for any random variable $A$.

Denote the regular conditional probability of $\Theta$ conditional on $V$ for
the measure $\mu_{\Theta,V}$ by
$\mu_{\Theta|V}:\mathbb{R}\times\mathcal{B}\rightarrow[0,1]$, where
$\mathcal{B}$ denotes the Borel $\sigma$-algebra on $\mathbb{R}$, similarly
for $\mu_{\Lambda|U}$. The posterior density of $\theta_{v}$ given
$\mathcal{T}_{v,2t-1}$ has density respect to $\mu_{\Theta|V}(v_{v},\cdot)$
given by

$p_{v}(\vartheta_{v}|\mathcal{T}_{v,2t-1})\propto\int\prod\exp\left(-\frac{n}{2}(x_{f^{\prime}v^{\prime}}-\frac{1}{n}\ell_{f^{\prime}}\vartheta_{v^{\prime}})^{2}\right)\prod\mu_{\Lambda}(u_{f},\mathrm{d}\ell_{f})\prod\mu_{\Theta}(v_{v^{\prime}},\mathrm{d}\vartheta_{v^{\prime}}),$

where the produces are over $(f^{\prime},v^{\prime})\in\mathcal{E}_{v,2t-1}$,
$f\in\mathcal{F}_{v,2t-1}$, and $v^{\prime}\in\mathcal{V}_{v,2t-1}$,
respectively. Asymptotically, the posterior behaves like that produced by a
Gaussian observation of $\theta_{v}$ with variance $\tau_{t}^{2}$.

######  Lemma 4.

In the low-rank matrix estimation model, there exist
$\mathcal{T}_{v,2t-1}$-measurable random variables $q_{v,t},\chi_{v,t}$ such
that for fixed $t\geq 1$

$p_{v}(\vartheta|\mathcal{T}_{v,2t-1})\propto\exp\left(-\frac{1}{2}(\chi_{v,t}-q_{v,t}^{1/2}\vartheta)^{2}+o_{p}(1)\right),$

where $o_{p}(1)$ has no $\vartheta$ dependence. Moreover,
$(\theta_{v},v_{v},\chi_{v,t},q_{v,t})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta,V,q_{t}^{1/2}\Theta+G,q_{t})$
where $(\Theta,V)\sim\mu_{\Theta,V},G\sim{\mathsf{N}}(0,1)$ independent of
$\Theta,V$, and $q_{t}$ is given by (7).

###### Lemma 4.

As in the proof of Lemma 1, we compute the posterior density
$p_{v}(\vartheta|\mathcal{T}_{v,2t-1})$ via belief propogation. The belief
propagation iteration is

$\displaystyle m_{f\rightarrow v}^{0}(\ell)=1,$ $\displaystyle m_{v\rightarrow
f}^{s+1}(\vartheta)\propto\int\prod_{f^{\prime}\in\partial v\setminus
f}\left(\exp\left(-\frac{n}{2}(x_{f^{\prime}v}-\frac{1}{n}\ell_{f^{\prime}}\vartheta)^{2}\right)m_{f^{\prime}\rightarrow
v}^{s}(\ell_{f^{\prime}})\mu_{\Lambda|U}(u_{f^{\prime}},\mathrm{d}\ell_{f^{\prime}})\right),$
$\displaystyle m_{f\rightarrow
v}^{s}(\ell)\propto\int\prod_{v^{\prime}\in\partial f\setminus
v}\left(\exp\left(-\frac{n}{2}(x_{fv^{\prime}}-\frac{1}{n}\ell\vartheta_{v^{\prime}})^{2}\right)m_{v^{\prime}\rightarrow
f}^{s}(\vartheta_{v^{\prime}})\mu_{\Theta|V}(v_{v^{\prime}},\mathrm{d}\vartheta_{v^{\prime}})\right),$

with normalization $\int m_{f\rightarrow
v}^{s}(\ell)\mu_{\Lambda|U}(u_{f},\mathrm{d}\ell)=\int m_{v\rightarrow
f}^{s}(\vartheta)\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta)=1$. For $t\geq 1$

$\displaystyle
p_{v}(\vartheta|\mathcal{T}_{v,2t-1})\propto\int\prod_{f\in\partial
v}\left(\exp\left(-\frac{n}{2}(x_{fv}-\frac{1}{n}\ell_{f}\vartheta)^{2}\right)m_{f\rightarrow
v}^{t-1}(\ell_{f})\mu_{\Lambda|U}(u_{f},\mathrm{d}\ell_{f})\right),$

This equation is exact.

We define several quantities related to the belief propagation iteration.

$\displaystyle\mu_{f\rightarrow v}^{s}$ $\displaystyle=\int\ell
m_{f\rightarrow v}^{s}(\ell)\mu_{\Lambda|U}(u_{f},\mathrm{d}\ell),$
$\displaystyle s_{f\rightarrow v}^{s}$
$\displaystyle=\int\ell^{2}m_{f\rightarrow
v}^{s}(\ell)\mu_{\Lambda|U}(u_{f},\mathrm{d}\ell),$
$\displaystyle\alpha_{v\rightarrow f}^{s+1}$
$\displaystyle=\frac{1}{n}\sum_{f^{\prime}\in\partial v\setminus
f}\mu_{f^{\prime}\rightarrow v}^{s}\lambda_{f^{\prime}},$
$\displaystyle(\tau_{v\rightarrow f}^{s+1})^{2}$
$\displaystyle=\frac{1}{n}\sum_{f^{\prime}\in\partial v\setminus
f}(\mu_{f^{\prime}\rightarrow v}^{s})^{2},$ $\displaystyle a_{v\rightarrow
f}^{s}$ $\displaystyle=\frac{\mathrm{d}\phantom{b}}{\mathrm{d}\vartheta}\log
m_{v\rightarrow f}^{s}(\vartheta)\Big{|}_{\vartheta=0},$ $\displaystyle
b_{v\rightarrow f}^{s}$
$\displaystyle=-\frac{\mathrm{d}^{2}\phantom{b}}{\mathrm{d}\vartheta^{2}}\log
m_{v\rightarrow f}^{s}(\vartheta)\Big{|}_{\vartheta=0},$
$\displaystyle\mu_{v\rightarrow f}^{s}$ $\displaystyle=\int\vartheta
m_{v\rightarrow f}^{s}(\vartheta)\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta),$
$\displaystyle s_{v\rightarrow f}^{s}$
$\displaystyle=\int\vartheta^{2}m_{v\rightarrow
f}^{s}(\vartheta)\mu_{\Theta|V}(v_{v},\mathrm{d}\vartheta),$
$\displaystyle\alpha_{f\rightarrow v}^{s}$
$\displaystyle=\frac{1}{n}\sum_{v^{\prime}\in\partial f\setminus
v}\mu_{v^{\prime}\rightarrow f}^{s}\theta_{v^{\prime}},$
$\displaystyle(\hat{\tau}_{f\rightarrow v}^{s})^{2}$
$\displaystyle=\frac{1}{n}\sum_{v^{\prime}\in\partial f\setminus
v}(\mu_{v^{\prime}\rightarrow f}^{s})^{2},$ $\displaystyle a_{f\rightarrow
v}^{s}$ $\displaystyle=\frac{\mathrm{d}\phantom{b}}{\mathrm{d}\ell}\log
m_{f\rightarrow v}^{s}(\ell)\Big{|}_{\ell=0},$ $\displaystyle b_{f\rightarrow
v}^{s}$
$\displaystyle=-\frac{\mathrm{d}^{2}\phantom{b}}{\mathrm{d}\ell^{2}}\log
m_{f\rightarrow v}^{s}(\ell)\Big{|}_{\ell=0},$

Lemma 4 follows from the following asymptotic characterization of the
quantities in the preceding display in the limit $n,p\rightarrow\infty$,
$n/p\rightarrow\delta$:

$\begin{gathered}\mathbb{E}[\mu_{f\rightarrow v}^{s}\lambda_{f}]\rightarrow
q_{s+1},\qquad\mathbb{E}[(\mu_{f\rightarrow v}^{s})^{2}]\rightarrow
q_{s+1},\\\ \alpha_{v\rightarrow
f}^{s+1}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1},\qquad(\tau_{v\rightarrow
f}^{s+1})\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1},\\\
(\theta_{v},v_{v},a_{v\rightarrow f}^{s},b_{v\rightarrow
f}^{s})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta,V,q_{s}\Theta+q_{s}^{1/2}G_{2},q_{s}),\\\
\mathbb{E}[\mu_{v\rightarrow
f}^{s}\theta_{v}]\rightarrow\delta\hat{q}_{s},\qquad\mathbb{E}[(\mu_{v\rightarrow
f}^{s})^{2}]\rightarrow\delta\hat{q}_{s},\\\ \alpha_{f\rightarrow
v}^{s}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\hat{q}_{s},\qquad(\hat{\tau}_{f\rightarrow
v}^{s+1})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\hat{q}_{s},\\\
(\lambda_{f},u_{f},a_{f\rightarrow v}^{s},b_{f\rightarrow
v}^{s})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Lambda,U,\hat{q}_{s}\Lambda+\hat{q}_{s}^{1/2}G,\hat{q}_{s}).\end{gathered}$
(50)

As in the proof of Lemma 1, the distribution of these quantities does not
depend upon $v$ or $f$, so that the limits hold for all $v,f$ once we
establish them for any $v,f$. We establish the limits inductively in $s$.

Base case: $\mathbb{E}[\mu_{f\rightarrow v}^{0}\lambda_{f}]\rightarrow q_{1}$
and $\mathbb{E}[(\mu_{f\rightarrow v}^{0})^{2}]\rightarrow q_{1}$.

Note $\mu_{f\rightarrow v}^{0}=\mathbb{E}[\lambda_{f}|u_{f}]$. Thus
$\mathbb{E}[\mu_{f\rightarrow
v}^{0}\lambda_{f}]=\mathbb{E}[\mathbb{E}[\lambda_{f}|u_{f}]^{2}]=V_{\Lambda,U}(0)=q_{1}$
exactly in finite samples, so also asymptotically. The expectation
$\mathbb{E}[(\mu_{f\rightarrow v}^{0})^{2}]$ has the same value.

Inductive step 1: If $\mathbb{E}[\mu_{f\rightarrow
v}^{s}\lambda_{f}]\rightarrow q_{s+1}$ and $\mathbb{E}[(\mu_{f\rightarrow
v}^{s})^{2}]\rightarrow q_{s+1}$, then $\alpha_{v\rightarrow
f}^{s+1}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1}$ and
$(\tau_{v\rightarrow
f}^{s+1})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1}$.

By the inductive hypothesis, $\mathbb{E}[\alpha_{v\rightarrow
f}^{s+1}]=(n-1)\mathbb{E}[\mu_{f\rightarrow v}^{s}\lambda_{f}]/n\rightarrow
q_{s+1}$ and $\mathbb{E}[(\tau_{v\rightarrow
f}^{s+1})^{2}]=(n-1)\mathbb{E}[(\mu_{f\rightarrow v}^{s})^{2}]/n\rightarrow
q_{s+1}$. Moreover, $\mu_{f^{\prime}\rightarrow v}^{s}\lambda_{f^{\prime}}$
are mutually independent as we vary $f^{\prime}\in\partial v\setminus f$, and
likewise for $\mu_{f^{\prime}\rightarrow v}^{s}$. We have
$\mathbb{E}[(\mu_{f^{\prime}\rightarrow v}^{s}\lambda_{f^{\prime}})^{2}]\leq
M^{4}$ and $\mathbb{E}[(\mu_{f^{\prime}\rightarrow v}^{s})^{4}]\leq M^{4}$
because the integrands are bounded by $M^{4}$. By the weak law of large
numbers, $\alpha_{v\rightarrow
f}^{s+1}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1}$ and
$(\tau_{v\rightarrow
f}^{s+1})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1}$.

Inductive step 2: If $\alpha_{v\rightarrow
f}^{s+1}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1}$ and
$(\tau_{v\rightarrow
f}^{s+1})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1}$, then
$(\theta_{v},v_{v},a_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta,V,q_{s+1}\Theta+q_{s+1}^{1/2}G,q_{s+1})$.

We may express

$\log m_{v\rightarrow
f}^{s+1}(\vartheta)=\mathsf{const}+\sum_{f^{\prime}\in\partial v\setminus
f}\log\mathbb{E}_{\Lambda_{f^{\prime}}}\left[\exp\left(-\frac{1}{2n}\Lambda_{f^{\prime}}^{2}\vartheta^{2}+x_{f^{\prime}v}\Lambda_{f^{\prime}}\vartheta\right)\right],$

where $\Lambda_{f^{\prime}}$ has density $m_{f^{\prime}\rightarrow v}^{s}$
with respect to $\mu_{\Lambda|U}(u_{f^{\prime}},\cdot)$. We compute

$\displaystyle\frac{\mathrm{d}\phantom{b}}{\mathrm{d}\vartheta}\mathbb{E}_{\Lambda_{f^{\prime}}}\left[\exp\left(-\frac{1}{2n}\Lambda_{f^{\prime}}^{2}\vartheta^{2}+x_{f^{\prime}v}\Lambda_{f^{\prime}}\vartheta\right)\right]\Big{|}_{\vartheta=0}$
$\displaystyle=\mathbb{E}_{\Lambda_{f^{\prime}}}\left[x_{f^{\prime}v}\Lambda_{f^{\prime}}\right]=x_{f^{\prime}v}\mu_{f^{\prime}\rightarrow
v}^{s},$
$\displaystyle\frac{\mathrm{d}^{2}\phantom{b}}{\mathrm{d}\vartheta^{2}}\mathbb{E}_{\Lambda_{f^{\prime}}}\left[\exp\left(-\frac{1}{2n}\Lambda_{f^{\prime}}^{2}\vartheta^{2}+x_{f^{\prime}v}\Lambda_{f^{\prime}}\vartheta\right)\right]\Big{|}_{\vartheta=0}$
$\displaystyle=\mathbb{E}_{\Lambda_{f^{\prime}}}\left[x_{f^{\prime}v}^{2}\Lambda_{f^{\prime}}^{2}-\frac{1}{n}\Lambda_{f^{\prime}}^{2}\right]=\left(x_{f^{\prime}v}^{2}-\frac{1}{n}\right)s_{f^{\prime}\rightarrow
v}^{s}.$

Then

$\displaystyle a_{v\rightarrow f}^{s+1}=\sum_{f^{\prime}\in\partial v\setminus
f}x_{f^{\prime}v}\mu_{f^{\prime}\rightarrow
v}^{s}\;\;\text{and}\;\;b_{v\rightarrow f}^{s+1}=\sum_{f^{\prime}\in\partial
v\setminus f^{\prime}}\left(x_{f^{\prime}v}^{2}(\mu_{f^{\prime}\rightarrow
v}^{s})^{2}-\left(x_{f^{\prime}v}^{2}-\frac{1}{n}\right)s_{f^{\prime}\rightarrow
v}^{s}\right).$

We compute

$\displaystyle a_{v\rightarrow
f}^{s+1}=\left(\frac{1}{n}\sum_{f^{\prime}\in\partial v\setminus
f}\mu_{f^{\prime}\rightarrow
v}^{s}\lambda_{f^{\prime}}\right)\theta_{v}+\sum_{f^{\prime}\in\partial
v\setminus f}z_{f^{\prime}v}\mu_{f^{\prime}\rightarrow v}^{s}.$

Because $(z_{f^{\prime}v})_{f^{\prime}\in\partial v\setminus f}$ are
independent of $\mu_{f^{\prime}\rightarrow v}^{2}$ and are mutually
independent from each other, conditional on $\mathcal{T}_{v\rightarrow f}^{1}$
the quantity $\sum_{f^{\prime}\in\partial v\setminus
f}z_{f^{\prime}v}\mu_{f^{\prime}\rightarrow v}^{s}$ is distributed
${\mathsf{N}}(0,(\tau_{v\rightarrow f}^{s+1})^{2})$. By the inductive
hypothesis, $(\tau_{f\rightarrow
v}^{s+1})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1}$, so
that $\sum_{f^{\prime}\in\partial v\setminus
f}z_{f^{\prime}v}\mu_{f^{\prime}\rightarrow
v}^{s}\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}{\mathsf{N}}(0,q_{s+1})$.
Further, $z_{f^{\prime}v}$ and $\mu_{f^{\prime}\rightarrow v}^{s}$ are
independent of $\theta_{v}$, and by the inductive hypothesis, the coefficient
of $\theta_{v}$ converges in probability to $q_{s+1}$. By the Continuous
Mapping Theorem [Vaa98, Theorem 2.3], we conclude that
$(\theta_{v},v_{v},a_{v\rightarrow
f}^{s+1})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta,V,q_{s+1}\Theta+q_{s+1}^{1/2}G)$
where $G\sim{\mathsf{N}}(0,1)$ independent of $\Theta$, as desired.

Now we show that $b_{v\rightarrow
f}^{s+1}\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}q_{s+1}$. We expand
$b_{v\rightarrow f}^{s+1}=A-B$ where $A=\sum_{f^{\prime}\in\partial v\setminus
f}x_{f^{\prime}v}^{2}(\mu_{f^{\prime}\rightarrow v}^{s})^{2}$ and
$B=\sum_{f^{\prime}\in\partial v\setminus
f}(x_{f^{\prime}v}^{2}-1/n)s_{f^{\prime}\rightarrow v}^{s}$. We have

$A=\frac{1}{n^{2}}\sum_{v^{\prime}\in\partial f\setminus
v}\lambda_{f^{\prime}}^{2}\theta_{v}^{2}(\mu_{f^{\prime}\rightarrow
v}^{s})^{2}+\frac{2}{n}\sum_{f^{\prime}\in\partial v\setminus
f}\lambda_{f^{\prime}}\theta_{v}z_{f^{\prime}v}(\mu_{f^{\prime}\rightarrow
v}^{s})^{2}+\sum_{v^{\prime}\in\partial f\setminus
v}z_{f^{\prime}v}^{2}(\mu_{f^{\prime}\rightarrow v}^{s})^{2}.$

Observe
$\mathbb{E}[\lambda_{f^{\prime}}^{2}\theta_{v}^{2}(\mu_{f^{\prime}\rightarrow
v}^{s})^{2}]\leq M^{6}$, so that the expectation of the first term is bounded
by $M^{6}(p-1)/n^{2}\rightarrow 0$. Thus, the first term converges to 0 in
probability. Because $z_{f^{\prime}v}$ is independent of
$\mu_{f^{\prime}\rightarrow v}^{s}$,
$\mathbb{E}[|\lambda_{f^{\prime}}\theta_{v}z_{f^{\prime}v}(\mu_{f^{\prime}\rightarrow
v}^{s})^{2}|]\leq M^{4}\sqrt{2/(\pi n)}$, so that the absolute value of the
expectation of the second term is bounded by $2M^{4}\sqrt{2/(\pi
n)}\rightarrow 0$. Thus, the second term converges to 0 in probability.
Because $\mu_{f^{\prime}\rightarrow v}^{s}$ is independent of
$z_{f^{\prime}v}$, the expectation of the last term is
$(n-1)\mathbb{E}[(\mu_{f^{\prime}\rightarrow v})^{2}]/n\rightarrow q_{s+1}$
(we have used here the assumption of inductive step 1). The terms
$(z_{f^{\prime}v}^{2}(\mu_{f^{\prime}\rightarrow
v}^{s})^{2})_{f^{\prime}\in\partial v\setminus f}$ are mutually independent
and $\mathbb{E}[z_{f^{\prime}v}^{4}(\mu_{f^{\prime}\rightarrow
v}^{s})^{4}]\leq 3M^{4}/n^{2}$, so that by the weak law of large numbers we
have that the last term converges to $q_{s+1}$ in probability. Thus,
$A\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1}$.

We have

$B=\frac{1}{n^{2}}\sum_{v^{\prime}\in\partial f\setminus
v}\lambda_{f}^{2}\theta_{v^{\prime}}^{2}s_{v^{\prime}\rightarrow
f}^{s}+\frac{2}{n}\sum_{v^{\prime}\in\partial f\setminus
v}\lambda_{f}\theta_{v^{\prime}}s_{v^{\prime}\rightarrow
f}^{s}+\sum_{v^{\prime}\in\partial f\setminus
v}(z_{f^{\prime}v}^{2}-1/n)s_{v^{\prime}\rightarrow f}^{s}.$

As in the analysis of the first two terms of $A$, we may use that
$s_{v^{\prime}\rightarrow f}^{s}\leq M^{2}$ to argue that the first two terms
of $B$ converge to 0 in probability. Further, because $z_{f^{\prime}v}$ is
independent of $s_{v^{\prime}\rightarrow f}^{s}$, the expectation of the last
term is 0. Further,
$\mathbb{E}[(z_{f^{\prime}v}^{2}-1/n)^{2}(s_{v^{\prime}\rightarrow
f}^{s})^{2}]\leq
2\mathbb{E}[(z_{f^{\prime}v}^{4}+1/n^{2})]\mathbb{E}[(s_{v^{\prime}\rightarrow
f}^{s})^{2}]\leq 8M^{4}/n^{2}$, so that by the weak law of large numbers, the
final term converges to 0 in probability. Thus,
$B\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}0$. Because, as we have
shown, $A\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1}$, we
conclude $b_{v\rightarrow
f}^{s+1}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}q_{s+1}$.

Combining with $(\theta_{v},v_{v},a_{v\rightarrow
f}^{s+1})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta,V,q_{s+1}\Theta+q_{s+1}^{1/2}G)$
and applying the Continuous Mapping Theorem [Vaa98, Theorem 2.3], we have
$(\theta_{v},a_{v\rightarrow f}^{s+1},b_{v\rightarrow
f}^{s+1})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta,q_{s+1}\Theta+q_{s+1}^{1/2}G,q_{s+1})$.

Inductive step 3: If $(\theta_{v},v_{v},a_{v\rightarrow f}^{s},b_{v\rightarrow
f}^{s})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Theta,V,q_{s}\Theta+q_{s}^{1/2}G_{1},q_{s})$,
then $\mathbb{E}[\mu_{v\rightarrow
f}^{s}\theta_{v}]\rightarrow\delta\hat{q}_{s}$ and
$\mathbb{E}[(\mu_{v\rightarrow f}^{s})^{2}]\rightarrow\delta\hat{q}_{s}$.

We will require the following lemma, whose proof is deferred to section D.2.1.

######  Lemma 5.

For any fixed $s$, we have $\vartheta,\ell\in[-M,M]$

$\displaystyle\log\frac{m_{v\rightarrow f}^{s}(\vartheta)}{m_{v\rightarrow
f}^{s}(0)}=\vartheta a_{v\rightarrow
f}^{s}-\frac{1}{2}\vartheta^{2}b_{v\rightarrow f}^{s}+O_{p}(n^{-1/2}),$
$\displaystyle\log\frac{m_{f\rightarrow v}^{s}(\ell)}{m_{f\rightarrow
v}^{s}(0)}=\ell a_{f\rightarrow v}^{s}-\frac{1}{2}\ell^{2}b_{f\rightarrow
v}^{s}+O_{p}(n^{-1/2}),$

where $O_{p}(n^{-1/2})$ has no $\vartheta$ (or $\ell$) dependence.

Define

$\epsilon_{f\rightarrow
v}^{s}=\sup_{\vartheta\in[-M,M]}\left|\log\frac{m_{v\rightarrow
f}^{s}(\vartheta)}{m_{v\rightarrow f}^{s}(0)}-\left(\vartheta a_{v\rightarrow
f}^{s}-\frac{1}{2}\vartheta^{2}b_{v\rightarrow f}^{s}\right)\right|.$

By Lemma 5, we have $\epsilon_{v\rightarrow f}^{s}=o_{p}(1)$. Moreover, using
the same argument as in inductive step 4 of the proof of Theorem 1, we have
that

$\displaystyle e^{-2\epsilon_{v\rightarrow
f}^{s}}\eta_{\Theta,V}(a_{v\rightarrow f}^{s}(b_{v\rightarrow f}^{s})^{-1/2}$
$\displaystyle,v_{v};b_{v\rightarrow f}^{s})\leq\mu_{v\rightarrow f}^{s}$
$\displaystyle\leq e^{2\epsilon_{v\rightarrow
f}^{s}}\eta_{\Theta,V}(a_{v\rightarrow f}^{s}(b_{v\rightarrow
f}^{s})^{1/2},v_{v};b_{v\rightarrow f}^{s}),$

where
$\eta_{\Theta,V}(y,v;q)=\mathbb{E}_{\Theta,V,G}[\Theta|q^{1/2}\Theta+\tau
G=y;V=v]$. Because $\eta_{\Theta,V}$ takes values in the bounded interval
$[-M,M]$ and $\epsilon_{v\rightarrow f}^{s}=o_{p}(1)$ by Lemma 5, we conclude
that

$\mu_{v\rightarrow f}^{s}=\eta_{\Theta,V}(a_{v\rightarrow
f}^{s}/b_{v\rightarrow f}^{s},v_{v};b_{v\rightarrow f}^{s})+o_{p}(1).$

For a fixed $v_{v}$, the Bayes estimator in the observation and coefficient
$q$. Thus, by the inductive hypothesis and the fact that $v_{v}\sim\mu_{V}$
for all $n$, we have that $\mathbb{E}[\Theta\eta_{\Theta,V}(a_{v\rightarrow
f}^{s}(b_{v\rightarrow f}^{s})^{1/2},v_{v};b_{v\rightarrow f}^{s})]$ has limit
$\mathbb{E}[\Theta\eta_{\Theta,V}(q_{s}^{1/2}\Theta+G,V;q_{s})]=\delta\hat{q}_{s}$
and $\mathbb{E}[\eta_{\Theta,V}(q_{s}^{1/2}\Theta+G,V;q_{s})^{2}]$ has limit
$\mathbb{E}_{\Theta,V,G}[\eta_{\Theta,V}(q_{s}^{1/2}\Theta+G,V;q_{s})^{2}]=\delta\hat{q}_{s}$.
Because $|\theta_{v}|,|\mu_{v\rightarrow
f}^{s}|,|\eta_{\Theta,V}(a_{v\rightarrow f}^{s}/b_{v\rightarrow
f}^{s},v_{v};b_{v\rightarrow f}^{s})|\leq M$, by bounded convergence, we
conclude $\mathbb{E}[\mu_{v\rightarrow
f}^{s}\theta_{v}]\rightarrow\delta\hat{q}_{s}$ and
$\mathbb{E}[(\mu_{f\rightarrow v}^{s})^{2}]\rightarrow\delta\hat{q}_{s}$.

The remaining inductive steps are completely analagous to those already shown.
We list them here for completeness.

Inductive step 4: If $\mathbb{E}[\mu_{v\rightarrow
f}^{s}\theta_{v}]\rightarrow\delta\hat{q}_{s}$ and
$\mathbb{E}[(\mu_{v\rightarrow f}^{s})^{2}]\rightarrow\delta\hat{q}_{s}$, then
$\alpha_{f\rightarrow
v}^{s}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\hat{q}_{s}$ and
$(\hat{\tau}_{f\rightarrow
v}^{s+1})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\hat{q}_{s}$.

Inductive step 5: If $\alpha_{f\rightarrow
v}^{s}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\hat{q}_{s}$ and
$(\hat{\tau}_{f\rightarrow
v}^{s})^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\hat{q}_{s}$,
then $(\lambda_{f},u_{f},a_{f\rightarrow v}^{s},b_{f\rightarrow
v}^{s})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Lambda,U,\hat{q}_{s}\Lambda+\hat{q}_{s}^{1/2}G,\hat{q}_{s})$.

Inductive step 6: If $(\lambda_{f},u_{f},a_{f\rightarrow
v}^{s},b_{f\rightarrow
v}^{s})\stackrel{{\scriptstyle\mathrm{d}}}{{\rightarrow}}(\Lambda,U,\hat{q}_{s}\Lambda+\hat{q}_{s}^{1/2}G,\hat{q}_{s})$,
then $\mathbb{E}[\mu_{f\rightarrow v}^{s}\lambda_{f}]\rightarrow q_{s+1}$ and
$\mathbb{E}[(\mu_{f\rightarrow v}^{s})^{2}]\rightarrow q_{s+1}$.

The induction is complete, and we conclude (50).

To complete the proof of Lemma 4, first observe that we may express
$\log\frac{p_{v}(\vartheta|\mathcal{T}_{v,2t-1})}{p_{v}(0|\mathcal{T}_{v,2t-1})}$
as $\log\frac{m_{v\rightarrow f}^{t}(\vartheta)}{m_{v\rightarrow
f}^{t}(\vartheta)}+\log\mathbb{E}_{\Lambda_{f}}[\exp(\vartheta
x_{fv}\Lambda_{f}-\vartheta^{2}\Lambda_{f}^{2}/(2n))]$. Note that

$\left|\log\mathbb{E}_{\Lambda_{f}}[\exp(\vartheta
x_{fv}\Lambda_{f}-\vartheta^{2}\Lambda_{f}^{2}/(2n))]\right|\leq
M^{2}|x_{fv}|+M^{4}/2n=o_{p}(1).$

By Lemma 5, we have that, up to a constant, $\log\frac{m_{v\rightarrow
f}^{t}(\vartheta)}{m_{v\rightarrow
f}^{t}(\vartheta)}=-\frac{1}{2}((a_{v\rightarrow f}^{t}(b_{v\rightarrow
f}^{t})^{-1/2}-b_{v\rightarrow f}^{t})^{1/2}\vartheta)^{2}+o_{p}(1)$. The
lemma follows from (50) and Slutsky’s theorem. ∎

Lemma 3 in the low-rank matrix estimation model follows from Lemma 4 by
exactly the same argument that derived Lemma 3 in the high-dimensional
regression model from Lemma 1.

####  D.2.1 Technical tools

###### Lemma 5.

Fix any $\vartheta\in[-M,M]$. By Taylor’s theorem, there exist
$\vartheta_{f^{\prime}}\in[-M,M]$ (in fact, between $0$ and $\vartheta$) such
that

$\displaystyle\log\frac{m_{v\rightarrow f}^{s}(\vartheta)}{m_{v\rightarrow
f}^{s}(0)}$ $\displaystyle=\sum_{f^{\prime}\in\partial v\setminus
f}\log\frac{\mathbb{E}_{\Lambda_{f^{\prime}}}[\exp(-n(x_{f^{\prime}v}-\Lambda_{f^{\prime}}\vartheta/n)^{2}/2)]}{\mathbb{E}_{\Lambda_{f^{\prime}}}[\exp(-nx_{f^{\prime}v}^{2}/2)]}$
$\displaystyle=\vartheta a_{v\rightarrow
f}^{s+1}-\frac{1}{2}\vartheta^{2}b_{v\rightarrow
f}^{s+1}+\frac{1}{6}\vartheta^{3}\sum_{f^{\prime}\in\partial v\setminus
f}\frac{\mathrm{d}^{3}}{\mathrm{d}\vartheta^{3}}\log\mathbb{E}_{\Lambda_{f^{\prime}}}[\exp(-n(x_{f^{\prime}v}-\Lambda_{f^{\prime}}\vartheta/n)^{2}/2)]\Big{|}_{\vartheta=\vartheta_{f^{\prime}}},$

where it is understood that
$\Lambda_{f^{\prime}}\sim\mu_{\Lambda|U}(u_{f^{\prime}},\cdot)$. Denote
$\psi(\vartheta,\ell,x)=-n(x_{f^{\prime}v}-\ell\vartheta/n)^{2}/2$. By the
same argument that allowed us to derive (46) from R4 in the proof of Lemma
3(a), we conclude

$\displaystyle\frac{\mathrm{d}^{3}}{\mathrm{d}\vartheta^{3}}\log\mathbb{E}_{\Lambda}[\exp(\psi(\vartheta,\Lambda,x))]\Big{|}_{\vartheta=\vartheta_{f^{\prime}}}$
$\displaystyle\qquad\qquad\leq
C\sup_{\ell,\vartheta\in[-M,M]}\max\\{|\partial_{\vartheta}\psi(\vartheta,\ell,x)|^{3},|\partial_{\vartheta}\psi(\vartheta,\ell,x)\partial_{\vartheta}^{2}\psi(\vartheta,\ell,x)|,|\partial_{\vartheta}^{3}\psi(\vartheta,\ell,x)|\\}$
$\displaystyle\qquad\qquad\leq
C\max\left\\{M^{3}|M^{2}/n+x_{f^{\prime}v}|^{3},(M^{2}/n)M|M^{2}/n+x_{f^{\prime}v}|,0\right\\},$

where $C$ is a universal constant. The expectaton of the right-hand side is
$O(n^{-3/2})$, whence we get

$\frac{1}{6}\vartheta^{3}\sum_{f^{\prime}\in\partial v\setminus
f}\frac{\mathrm{d}^{3}}{\mathrm{d}\vartheta^{3}}\log\mathbb{E}_{\Lambda_{f^{\prime}}}[\exp(-n(x_{f^{\prime}v}-\Lambda_{f^{\prime}}\vartheta/n)^{2}/2)]\Big{|}_{\vartheta=\vartheta_{f^{\prime}}}=O_{p}(n^{-1/2}),$

where because $\vartheta\in[-M,M]$, we may take $O_{p}(n^{-1/2})$ to have no
$\vartheta$-dependence.

The expansion of $\log\frac{m_{f\rightarrow v}^{s}(\ell)}{m_{f\rightarrow
v}^{s}(0)}$ is proved similarly. ∎

##  Appendix E Weakening the assumptions

Section 5 and the preceding appendices establish under the assumptions A1, A2
and either R3, R4 or M2 all claims in Theorems 1 and 2 except that the lower
bound may be achieved. In this section we show that if these claims hold under
assumptions A1, A2, R3, R4, then they also hold under assumptions A1, A2, R1,
R2 in the high-dimensional regression model; and similarly for the low-rank
matrix estimation model. In the next section we prove we can achieve the lower
bounds under the weaker assumptions A1, A2 and either R1, R2 or M1.

###  E.1 From strong to weak assumptions in the high-dimensional regression
model

To prove the reduction from the stronger assumptions in the high-dimensional
regression model, we need the following lemma, whose proof is given at the end
of this section.

######  Lemma 1.

Consider on a single probability space random variables $A,B,(B_{n})_{n\geq
1}$, and $Z\sim{\mathsf{N}}(0,1)$ independent of the $A$’s and $B$’s, all with
finite second moment. Assume $\mathbb{E}[(B-B_{n})^{2}]\rightarrow 0$. Let
$Y=B+\tau Z$ and $Y_{n}=B_{n}+\tau Z$ for $\tau>0$. Then

$\mathbb{E}[\mathbb{E}[A|Y_{n}]^{2}]\rightarrow\mathbb{E}[\mathbb{E}[A|Y]^{2}]\,.$

We now establish the reduction.

Consider $\mu_{W,U}$, $\mu_{\Theta,V}$, and $h$ satisfying R1 and R2. For any
$\epsilon>0$, we construct $\mu_{\tilde{\boldsymbol{W}},\tilde{U}}$,
$\mu_{\tilde{\Theta},\tilde{V}}$, and $\tilde{h}$ satisfying R3 and R4 for
$k=3$ as well as data $\boldsymbol{X}\in\mathbb{R}^{n\times p}$,
$\boldsymbol{\theta},\tilde{\boldsymbol{\theta}},\boldsymbol{v},\tilde{\boldsymbol{v}}\in\mathbb{R}^{p}$,
and
$\boldsymbol{y},\tilde{\boldsymbol{y}},\boldsymbol{w},\boldsymbol{u},\tilde{\boldsymbol{u}}\in\mathbb{R}^{n}$
and $\tilde{\boldsymbol{w}}\in\mathbb{R}^{n\times 3}$ such that the following
all hold.

  1. 1.

$(\boldsymbol{X},\boldsymbol{\theta},\boldsymbol{v},\boldsymbol{u},\boldsymbol{w},\boldsymbol{y})$
and
$(\boldsymbol{X},\tilde{\boldsymbol{\theta}},\tilde{\boldsymbol{v}},\tilde{\boldsymbol{u}},\tilde{\boldsymbol{w}},\tilde{\boldsymbol{y}})$
are generated according to their respective regression models: namely,
$(\theta_{j},v_{j})\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mu_{\Theta,V}$
and $(w_{i},u_{i})\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mu_{W,U}$
independent;
$(\tilde{\theta}_{j},\tilde{v}_{j})\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mu_{\tilde{\Theta},\tilde{V}}$
and
$(\tilde{\boldsymbol{w}}_{i},\tilde{\boldsymbol{u}}_{i})\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mu_{\tilde{\boldsymbol{W}},\tilde{U}}$
independent;
$x_{ij}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}{\mathsf{N}}(0,1/n)$
independent of everything else; and
$\boldsymbol{y}=h(\boldsymbol{X}\boldsymbol{\theta},\boldsymbol{w})$ and
$\tilde{\boldsymbol{y}}=\tilde{h}(\boldsymbol{X}\tilde{\boldsymbol{\theta}},\tilde{\boldsymbol{v}})$.
Here $\tilde{\boldsymbol{w}}_{i}^{\mathsf{T}}$ is the $i^{\text{th}}$ row of
$\tilde{\boldsymbol{w}}$. We emphasize that the data from the two models are
not independent.

  2. 2.

We have

$\displaystyle\mathbb{P}\left(\frac{1}{n}\|\boldsymbol{y}-\tilde{\boldsymbol{y}}\|^{2}>\epsilon\right)\rightarrow
0,\;\mathbb{P}\left(\frac{1}{p}\|\boldsymbol{v}-\tilde{\boldsymbol{v}}\|^{2}>\epsilon\right)\rightarrow
0,\;\mathbb{P}\left(\frac{1}{n}\|\boldsymbol{u}-\tilde{\boldsymbol{u}}\|^{2}>\epsilon\right)\rightarrow
0\,.$ (51)

Note that because in any GFOM the functions
$F_{t}^{(1)},F_{t}^{(2)},G_{t}^{(1)},G_{t}^{(2)},G_{*}$ are Lipschitz and
$\|\boldsymbol{X}\|_{\mathsf{op}}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}C_{\delta}<\infty$
as $n,p\rightarrow\infty,n/p\rightarrow 0$ [Ver12, Theorem 5.31], the previous
display and the iteration (1) imply

$\mathbb{P}\left(\frac{1}{p}\|\hat{\boldsymbol{\theta}}^{t}-\tilde{\hat{\boldsymbol{\theta}}}^{t}\|^{2}>c(\epsilon,t)\right)\rightarrow
0\,,$ (52)

for some $c(\epsilon,t)<\infty$ which goes to 0 as $\epsilon\rightarrow 0$ for
fixed $t$.

  3. 3.

We have

$\displaystyle|\textsf{mmse}_{\Theta,V}(\tau_{s}^{2})-\textsf{mmse}_{\tilde{\Theta},\tilde{V}}(\tau_{s})^{2}|<\epsilon,$
(53)
$\displaystyle\left|\mathbb{E}\left[\mathbb{E}[G_{1}|h(G,W)+\epsilon^{1/2}Z,G_{0}]^{2}\right]-\mathbb{E}\left[\mathbb{E}[G_{1}|\tilde{h}(G,\tilde{\boldsymbol{W}}),G_{0}]^{2}\right]\right|<\tilde{\tau}_{s}^{2}\epsilon\,,$
(54)

for all $s\leq t$ where
$G_{0},G_{1},Z\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}{\mathsf{N}}(0,1)$,
$W\sim\mu_{W}$, and $\tilde{\boldsymbol{W}}\sim\mu_{\tilde{\boldsymbol{W}}}$
independent, and $G=\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1}$.

We now describe the construction described and prove it has the desired
properties. Let $\mu_{A}$ be a smoothed Laplace distribution with mean zero
and variance 1; namely, $\mu_{A}$ has a $C_{\infty}$ positive density
$p_{A}(\cdot)$ with respect to Lebesgue measure which satisfies
$\partial_{a}\log p_{A}(a)=c\cdot\mathsf{sgn}(a)$ when $|x|>1$ for some
positive constant $c$. This implies that $|\partial_{a}^{k}\log p_{A}(a)|\leq
q_{k}$ for all $k$ and some constants $q_{k}$, and that $\mu_{A}$ has moments
of all orders.

First we construct $\tilde{h}$ and $\tilde{\boldsymbol{W}}$. For a $\xi>0$ to
be chosen, let $\hat{h}$ be a Lipschitz function such that
$\mathbb{E}[(\hat{h}(G,W)-h(G,W))^{2}]<\xi$ for $(G,W)$ as above, which is
permitted by assumption R2. Let $L>0$ be a Lipschitz constant for $\hat{h}$.
Choose $M>0$ such that $\mathbb{E}[W^{2}\mathbf{1}\\{|W|>M\\}]<\xi/L^{2}$.
Define $\bar{W}=W\mathbf{1}\\{|W|\leq M\\}$. Note that
$\mathbb{E}[(h(G,W)-\hat{h}(G+\xi^{1/2}A,\bar{W}))^{2}]\leq
2\mathbb{E}[(h(G,W)-\hat{h}(G,W))^{2}]+2\mathbb{E}[(\hat{h}(G,W)-\hat{h}(G+\xi^{1/2}A,\bar{W}))^{2}]<4\xi$.
By Lemma 1, we may pick $0<\xi<\min\\{\epsilon/4,\epsilon/L^{2}\\}$
sufficiently small that

$\left|\mathbb{E}\left[\mathbb{E}[G_{1}|h(G,W)+\epsilon^{1/2}Z,G_{0}]^{2}\right]-\mathbb{E}\left[\mathbb{E}[G_{1}|\hat{h}(G+\xi^{1/2}A,\bar{W})+\epsilon^{1/2}Z,G_{0}]^{2}\right]\right|<\tilde{\tau}_{s}^{2}\epsilon\,.$

In fact, because $t$ is finite, we may choose $\xi>0$ small enough that this
holds for all $s\leq t$. Define $\tilde{\boldsymbol{W}}=(\bar{W},A,Z)$ and
$\tilde{h}(x,\tilde{\boldsymbol{w}})=\hat{h}(x+\xi^{1/2}a,\bar{w})+\epsilon^{1/2}z$
where $\tilde{\boldsymbol{w}}=(\bar{w},a,z)$. Then $\tilde{h}$ is Lipschitz,
Eq. (54) holds for all $s\leq t$, and
$\mathbb{E}[(h(G,W)-\tilde{h}(G,\tilde{\boldsymbol{W}}))^{2}]<\epsilon$ (the
last because $\xi<\epsilon/4$).

Now choose $K>0$ large enough that

$\displaystyle\mathbb{E}[\Theta^{2}\mathbf{1}\\{|\Theta|>K\\}]<\delta\epsilon/L^{2},\;\;\mathbb{E}[U^{2}\mathbf{1}\\{|U|>K\\}]<\epsilon/2,\;\;\mathbb{E}[V^{2}\mathbf{1}\\{|V|>K\\}]<\epsilon/2\,.$
(55)

Define $\tilde{\Theta}=\bar{\Theta}=\Theta\mathbf{1}\\{|\Theta|\leq K\\}$,
$\tilde{V}=\bar{V}=V\mathbf{1}\\{|V|\leq K\\}$,
$\tilde{U}=\bar{U}=U\mathbf{1}\\{|U|\leq K\\}$, and let
$\mu_{\tilde{\Theta},\tilde{V}},\mu_{\tilde{\boldsymbol{W}},\tilde{U}}$ be the
corresponding distributions; namely, $\mu_{\tilde{\Theta},\tilde{V}}$ is the
distribution of $(\Theta\mathbf{1}\\{|\Theta|\leq K\\},V\mathbf{1}\\{|V|\leq
K\\})$ when $(\Theta,V)\sim\mu_{\Theta,V}$, and
$\mu_{\tilde{\boldsymbol{W}},\tilde{U}}$ is the distribution of
$(W\mathbf{1}\\{|W|\leq M\\},A,Z)$ when $(W,U)\sim\mu_{W,U}$ and
$(A,Z)\sim\mu_{A}\otimes{\mathsf{N}}(0,1)$ independent. Because the Bayes risk
converges as $K\rightarrow\infty$ to the Bayes risk with respect to the
untruncated prior, we may choose $K$ large enough that also (53) holds for
these truncated distributions.

The distributions
$\mu_{\tilde{\Theta},\tilde{V}},\mu_{\tilde{\boldsymbol{W}},\tilde{U}}$
satisfy assumption R3. We now show that $\tilde{h}$ and
$\tilde{\boldsymbol{W}}$ constructed in this way satisfy assumption R4. The
function $\tilde{h}$ is Lipschitz because $\hat{h}$ is Lipschitz. The random
variable $\tilde{Y}:=\hat{h}(x+\xi^{1/2}A,\bar{W})+\epsilon^{1/2}Z$ has
density with respect to Lebesgue measure given by

$p(y|x)=\int\int
p_{\xi^{1/2}A}\left(s-x\right)p_{{\mathsf{N}}(0,\epsilon)}(y-\hat{h}(s,\bar{w}))\mu_{\bar{W}}({\mathrm{d}}\bar{w}){\mathrm{d}}s,$

where $p_{{\mathsf{N}}(0,\epsilon)}$ is the density of
${\mathsf{N}}(0,\epsilon)$ and $p_{\xi^{1/2}A}\left(s-x\right)$ the density of
$\xi^{1/2}A$ with respect to Lebesgue measure. We have
$p(y|x)\leq\sup_{y}p_{{\mathsf{N}}(0,\epsilon)}(y)=1/\sqrt{2\pi\epsilon}$, so
is bounded, as desired. Moreover

$\left|\frac{\int\int\partial_{x}p_{\xi^{1/2}A}\left(s-x\right)p_{{\mathsf{N}}(0,\epsilon)}(y-\hat{h}(s,\bar{w}))\mu_{\bar{W}}({\mathrm{d}}\bar{w}){\mathrm{d}}s}{p(y|x)}\right|\leq\sup_{s}\left|\frac{\dot{p}_{\xi^{1/2}A}(s)}{p_{\xi^{1/2}A}(s)}\right|.$

Because $A$ has a smoothed Laplace distribution, the right-hand side is
finite. Thus, by bounded convergence, we may exchange differentiation and
integration and the preceding display is equal to $\partial_{x}\log p(y|x)$.
We conclude that $|\partial_{x}\log p(y|x)|$ is bounded. The boundededness of
all higher derivatives holds similarly. Thus, R4 holds.

We now generate the appropriate joint distribution over
$(\boldsymbol{X},\boldsymbol{\theta},\boldsymbol{v},\boldsymbol{u},\boldsymbol{w},\boldsymbol{y})$
and
$(\boldsymbol{X},\tilde{\boldsymbol{\theta}},\tilde{\boldsymbol{v}},\tilde{\boldsymbol{u}},\tilde{\boldsymbol{w}},\tilde{\boldsymbol{y}})$.
First, generate
$(\boldsymbol{X},\boldsymbol{\theta},\boldsymbol{v},\boldsymbol{u},\boldsymbol{w},\boldsymbol{y})$
from original the high-dimensional regression model. Then generate
$\boldsymbol{a},\boldsymbol{z}$ independent and with entries
$a_{i}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mu_{A}$ and
$z_{i}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}{\mathsf{N}}(0,1)$. Define
$\tilde{\boldsymbol{\theta}},\tilde{\boldsymbol{v}},\tilde{\boldsymbol{u}}$ by
truncating $\boldsymbol{\theta},\boldsymbol{v},\boldsymbol{u}$ at threshold
$K$; define $\tilde{\boldsymbol{w}}$ by truncating $\boldsymbol{w}$ at
threshold $M$ to form $\bar{\boldsymbol{w}}$ and concatenating to it the
vectors $\boldsymbol{a},\boldsymbol{z}$ to form a matrix in
$\mathbb{R}^{n\times 3}$; and define
$\tilde{\boldsymbol{y}}=\tilde{h}(\boldsymbol{X}\tilde{\boldsymbol{\theta}},\tilde{\boldsymbol{w}})$.

All that remains is to show (51) holds for the model generated in this way.
The bounds on $\|\boldsymbol{v}-\tilde{\boldsymbol{v}}\|^{2}$ and
$\|\boldsymbol{u}-\tilde{\boldsymbol{u}}\|^{2}$ hold by the weak law of large
numbers and (55). To control $\|\boldsymbol{y}-\tilde{\boldsymbol{y}}\|$, we
bound

$\displaystyle\|\boldsymbol{y}-\tilde{\boldsymbol{y}}\|=\|h(\boldsymbol{X}\boldsymbol{\theta},\boldsymbol{w})-\tilde{h}(\boldsymbol{X}\tilde{\boldsymbol{\theta}},\tilde{\boldsymbol{w}})\|$
$\displaystyle\qquad\leq\|h(\boldsymbol{X}\boldsymbol{\theta},\boldsymbol{w})-\hat{h}(\boldsymbol{X}\boldsymbol{\theta},\boldsymbol{w})\|+\|\hat{h}(\boldsymbol{X}\boldsymbol{\theta},\boldsymbol{w})-\hat{h}(\boldsymbol{X}\tilde{\boldsymbol{\theta}},\boldsymbol{w})\|+\|\hat{h}(\boldsymbol{X}\tilde{\boldsymbol{\theta}},\boldsymbol{w})-\tilde{h}(\boldsymbol{X}\tilde{\boldsymbol{\theta}},\tilde{\boldsymbol{w}})$
$\displaystyle\qquad\leq\|h(\boldsymbol{X}\boldsymbol{\theta},\boldsymbol{w})-\hat{h}(\boldsymbol{X}\boldsymbol{\theta},\boldsymbol{w})\|+L\|\boldsymbol{X}(\boldsymbol{\theta}-\tilde{\boldsymbol{\theta}})\|+L\xi^{1/2}\|\boldsymbol{a}\|+L\|\boldsymbol{w}-\bar{\boldsymbol{w}}\|+\epsilon^{1/2}\|\boldsymbol{z}\|\,.$

Because $|h(x,w)|\leq C(1+|x|+|w|)$ by R2 and $\hat{h}$ is Lipschitz, there
exist $C>0$ such that $|h(x,w)-\hat{h}(x,w)|\leq C(1+|x|+|w|)$. Then,
$\mathbb{E}[(h(\tau Z,w)-\hat{h}(\tau
Z,w))^{2}]=\int(h(x,w)-\hat{h}(x,w))^{2}\frac{1}{\sqrt{2\pi}\tau}e^{-\frac{1}{2\tau^{2}}x^{2}}{\mathrm{d}}x<C(1+\tau^{2}+w^{2})$
and is continuous in $\tau^{2}$ for $\tau>0$ by dominated convergence
convergence, and is uniformly continuous for $\tau$ bounded away from 0 and
infinity and $w_{i}$ restricted to a compact set. Because
$\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\theta}|\boldsymbol{\theta}\sim{\mathsf{N}}(0,\|\boldsymbol{\theta}\|^{2}/n)$
and
$\|\boldsymbol{\theta}\|^{2}/n\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\tau_{\Theta}^{2}/\delta$,
we have that

$\mathbb{E}[(h(\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\theta},w_{i})-\hat{h}(\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\theta},w_{i}))^{2}|\boldsymbol{\theta},w_{i}]=\mathbb{E}[(h(\tau_{\Theta}\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\theta}/\|\boldsymbol{\theta}\|,w_{i})-\hat{h}(\tau_{\Theta}\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\theta}/\|\boldsymbol{\theta}\|,w_{i}))^{2}|\boldsymbol{\theta},w_{i}]+o_{p}(1)\,.$

The right-hand side is a constant equal to
$\mathbb{E}[(h(G,W)-\hat{h}(G,W))^{2}]$ and the left-hand side is uniformly
integrable. Thus,

$\limsup_{n\rightarrow\infty}\mathbb{E}[(h(\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\theta},w_{i})-\hat{h}(\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\theta},w_{i}))^{2}]\leq\mathbb{E}[(h(G,w_{i})-\hat{h}(G,w_{i}))^{2}]<\xi\,.$

Markov’s inequality proves the the first convergence in (51) because
$\xi<\epsilon$. Further, by the weak law of large numbers

$\frac{L^{2}}{n}\|\boldsymbol{X}(\boldsymbol{\theta}-\tilde{\boldsymbol{\theta}})\|^{2}\leq\frac{L^{2}\|\boldsymbol{X}\|_{\mathsf{op}}^{2}}{n}\|\boldsymbol{\theta}-\tilde{\boldsymbol{\theta}}\|^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}L^{2}C_{\delta}\delta^{-1}\mathbb{E}[\Theta^{2}\mathbf{1}\\{|\Theta|>M\\}]<C_{\delta}\epsilon\,,$

where $C_{\delta}$ is the constant satisfying
$\|\boldsymbol{X}\|_{\mathsf{op}}^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}C_{\delta}$
[Ver12, Theorem 5.31]. Similarly, by the weak law of large numbers

$\frac{L^{2}\xi}{n}\|\boldsymbol{a}\|^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}L^{2}\xi<\epsilon,\;\;\frac{L^{2}}{n}\|\boldsymbol{w}-\bar{\boldsymbol{w}}\|^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}L^{2}\mathbb{E}[W^{2}\mathbf{1}\\{|W|>M\\}]<\xi<\epsilon,\;\;\frac{\epsilon}{n}\|\boldsymbol{z}\|^{2}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\epsilon\,.$

We conclude that

$\mathbb{P}\left(\frac{1}{n}\|\boldsymbol{y}-\tilde{\boldsymbol{y}}\|^{2}>5(C_{\delta}+4)\epsilon\right)\rightarrow
0.$

Becuse $\epsilon$ was arbitrary, we can in fact achieve (51) by considering a
smaller $\epsilon$ (without affecting the validity of (53)).

This completes the construction. To summarize, we have two models: the first
satisfying R1 and R2, and the second satisfying R3 and R4.

With the construction now complete, we explain why it establishes the
reduction. Let $\tau_{s}^{(\epsilon)},\tilde{\tau}_{s}^{(\epsilon)}$ be the
state evolution parameters generated by (5) with
$\mu_{\tilde{\boldsymbol{W}},\tilde{U}}$, $\mu_{\tilde{\Theta},\tilde{V}}$,
and $\tilde{h}$ in place of $\mu_{W,U},\mu_{\Theta,V}$, and $h$. First, we
claim that Eqs. (53) and (54) imply, by induction, that as
$\epsilon\rightarrow 0$, we have

$\tau_{t}^{(\epsilon)}\rightarrow\tau_{t}.$

Indeed, to show this, we must only establish that
$\mathbb{E}\left[\mathbb{E}[G_{1}|h(G,W)+\epsilon^{1/2}Z,G_{0}]^{2}\right]$
converges to $\mathbb{E}[\mathbb{E}[G_{1}|h(G,W),G_{0}]^{2}]$ as
$\epsilon\rightarrow 0$. Without loss of generality, we may assume that on the
same probability space there exists a Brownian motion
$(B_{\epsilon})_{\epsilon>0}$ independent of everything else. We see that
$\mathbb{E}[G_{1}|h(G,W)+\epsilon^{1/2}Z,G_{0}]^{2}]\stackrel{{\scriptstyle\mathrm{d}}}{{=}}\mathbb{E}[G_{1}|h(G,W)+B_{\epsilon},G_{0}]=\mathbb{E}[G_{1}|(h(G,W)+B_{s})_{s\geq\epsilon},G_{0}]$.
By Lévy’s upward theorem [Dur10, Theorem 5.5.7], we have that
$\mathbb{E}[G_{1}|(h(G,W)+B_{s})_{s\geq\epsilon},G_{0}]$ converges to
$\mathbb{E}[G_{1}|(h(G,W)+B_{s})_{s\geq
0},G_{0}]=\mathbb{E}[G_{1}|h(G,W),G_{0}]$ almost surely. By uniform
integrability, we conclude that
$\mathbb{E}[\mathbb{E}[G_{1}|(h(G,W)+B_{s})_{s\geq\epsilon},G_{0}]^{2}]\rightarrow\mathbb{E}[\mathbb{E}[G_{1}|h(G,W),G_{0}]^{2}]$,
as claimed. Thus, we conclude the previous display.

We now show that as $\epsilon\rightarrow 0$, we have

$\inf_{\hat{\theta}(\cdot)}\mathbb{E}[\ell(\tilde{\Theta},\hat{\theta}(\tilde{\Theta}+\tau_{t}^{(\epsilon)}G,V))]\rightarrow\inf_{\hat{\theta}(\cdot)}\mathbb{E}[\ell(\Theta,\hat{\theta}(\Theta+\tau_{t}G,V))]\,.$

Because the truncation level $K$ can be taken to $\infty$ as
$\epsilon\rightarrow 0$, this holds by combining Lemma 5(a) and (c), and
specifically, Eqs. (25) and (27).

Because the lower bound of Theorem 1 holds under assumptions R3 and R4, which
are satisfied by $\mu_{\tilde{\boldsymbol{W}},\tilde{U}}$,
$\mu_{\tilde{\Theta},\tilde{V}}$, and $\tilde{h}$, we conclude that

$\lim_{n\rightarrow\infty}\frac{1}{p}\sum_{j=1}^{p}\ell(\theta_{j},\hat{\theta}_{j}^{t})\geq\inf_{\hat{\theta}(\cdot)}\mathbb{E}[\ell(\tilde{\Theta},\hat{\theta}(\tilde{\Theta}+\tau_{t}^{(\epsilon)}G,V))].$

Taking $\epsilon\rightarrow 0$ and applying (52), we conclude that (6) holds
for $\hat{\boldsymbol{\theta}}^{t}$, as desired.

The reduction in the high-dimensional regression model is complete.

###### Lemma 1.

It is enough to prove the result for $\tau=1$. Note

$\mathbb{E}[A|Y=y]=\frac{\int
ae^{-(y-b)^{2}}\mu({\mathrm{d}}a,{\mathrm{d}}b)}{\int
e^{-(y-b)^{2}}\mu({\mathrm{d}}a,{\mathrm{d}}b)},\qquad\mathbb{E}[A|Y_{n}=y]=\frac{\int
ae^{-(y-b)^{2}}\mu_{n}({\mathrm{d}}a,{\mathrm{d}}b)}{\int
e^{-(y-b)^{2}}\mu_{n}({\mathrm{d}}a,{\mathrm{d}}b)}.$

Because $\mu_{n}\stackrel{{\scriptstyle\mathrm{W}}}{{\rightarrow}}\mu$, we
have

$\frac{\int ae^{-(y-b)^{2}}\mu_{n}({\mathrm{d}}a,{\mathrm{d}}b)}{\int
e^{-(y-b)^{2}}\mu_{n}({\mathrm{d}}a,{\mathrm{d}}b)}\rightarrow\frac{\int
ae^{-(y-b)^{2}}\mu({\mathrm{d}}a,{\mathrm{d}}b)}{\int
e^{-(y-b)^{2}}\mu({\mathrm{d}}a,{\mathrm{d}}b)},$

for all $y$, and moreover, this convergence is uniform on compact sets.
Moreover, one can check that the stated functions are Lipschitz (with uniform
Lipschitz constant) in $y$ on compact sets. This implies that
$\mathbb{E}[A|Y_{n}]\rightarrow\mathbb{E}[A|Y]$ almost surely. Because the
$\mathbb{E}[A|Y_{n}]^{2}$ are uniformly integrable, the lemma follows. ∎

###  E.2 From strong to weak assumptions in the low-rank matrix estimation
model

Consider
$\mu_{\boldsymbol{\Lambda},\boldsymbol{U}},\mu_{\boldsymbol{\Theta},\boldsymbol{V}}$
satisfying M1. Fix $M>0$. For
$(\boldsymbol{\Lambda},\boldsymbol{U})\sim\mu_{\boldsymbol{\Lambda},\boldsymbol{U}}$,
define $\tilde{\Lambda}$ by setting
$\tilde{\Lambda}_{i}=\Lambda_{i}\mathbf{1}\\{|\Lambda_{i}|\leq M\\}$ for
$1\leq i\leq k$. Define $\tilde{\boldsymbol{U}}$ similarly, and let
$\mu_{\tilde{\boldsymbol{\Lambda}},\tilde{\boldsymbol{U}}}$ be the
distribution of $(\tilde{\boldsymbol{\Lambda}},\tilde{\boldsymbol{U}})$ so
constructed. Define $\mu_{\tilde{\boldsymbol{\Theta}},\tilde{\boldsymbol{V}}}$
similarly.

Consider $\\{(\boldsymbol{\lambda}_{i},\boldsymbol{u}_{i})\\}_{i\leq
n}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mu_{\boldsymbol{\Lambda},\boldsymbol{U}}$
and $\\{(\boldsymbol{\theta}_{j},\boldsymbol{v}_{j})\\}_{j\leq
p}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mu_{\boldsymbol{\Theta},\boldsymbol{V}}$
and $\boldsymbol{Z}\in\mathbb{R}^{n\times p}$ independent with
$z_{ij}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}{\mathsf{N}}(0,1/n)$.
Constructe
$\tilde{\boldsymbol{\lambda}}_{i},\tilde{\boldsymbol{u}}_{i},\tilde{\boldsymbol{\theta}}_{j},\tilde{\boldsymbol{v}}_{j}$
by truncated each coordinate at level $M$ as above. Define
$\boldsymbol{X},\tilde{\boldsymbol{X}}\in\mathbb{R}^{n\times p}$ by
$x_{ij}=\frac{1}{n}\boldsymbol{\lambda}_{i}^{\mathsf{T}}\boldsymbol{\theta}_{j}+z_{ij}$
and
$\tilde{z}_{ij}=\frac{1}{n}\tilde{\boldsymbol{\lambda}}_{i}^{\mathsf{T}}\tilde{\boldsymbol{\theta}}+z_{ij}$.
As in the previous section, we have for any $\epsilon>0$ that

$\mathbb{P}(\|\boldsymbol{X}-\tilde{\boldsymbol{X}}\|_{\mathsf{op}}>\epsilon)\rightarrow
0,\;\;\mathbb{P}\left(\frac{1}{p}\|\boldsymbol{v}-\tilde{\boldsymbol{v}}\|^{2}>\epsilon\right)\rightarrow
0,\;\;\mathbb{P}\left(\frac{1}{p}\|\boldsymbol{u}-\tilde{\boldsymbol{u}}\|^{2}>\epsilon\right)\rightarrow
0.$

As in the previous section, this implies that the iterates of the GFOMs before
and after the truncation become arbitrarily close with high probability at a
fixed iterate $t$ as we take $M\rightarrow\infty$.

Further, as $M\rightarrow\infty$ we have
$\boldsymbol{V}_{\tilde{\boldsymbol{\Theta}},\tilde{\boldsymbol{V}}}(\boldsymbol{Q})\rightarrow\boldsymbol{V}_{\boldsymbol{\Theta},\boldsymbol{V}}(\boldsymbol{Q})$
for all $\boldsymbol{Q}$, and likewise for
$\tilde{\boldsymbol{\Lambda}},\tilde{\boldsymbol{U}}$. Further,
$\boldsymbol{V}_{\tilde{\boldsymbol{\Theta}},\tilde{\boldsymbol{V}}}(\boldsymbol{Q})$
is jointly continuous in $\boldsymbol{Q}$ and $M$ (where $M$ is implicit in
the truncation used to generate
$\tilde{\boldsymbol{\Theta}},\tilde{\boldsymbol{V}}$). Thus, as we take
$M\rightarrow\infty$, the state evolution (7) after the truncation converges
to the state evolution with no truncation.

The reduction now occurs exactly as in the previous section.

##  Appendix F Achieving the bound

All that remains to prove Theorems 1 and 2 under assumptions A1, A2 and either
R1, R2 or M1, respectively, is to show that the lower bounds in Eqs. (6) and
(8) can be achieved. In both cases, we can achieve the bound up to tolerance
$\epsilon$ using a certain AMP algorithm.

###  F.1 Achieving the bound in the high-dimensional regression model

We first derive certain monotonicity properies of the parameters
$\tau_{s},\sigma_{s},\tilde{\tau}_{s}$ defined in the state evolution
recursion (5). As we saw in Appendix D.1 and in particular, in Lemma 1, the
posterior of $\theta_{v}$ on the computation tree given observations in the
local neighborhood $T_{v,2s}$ behaves like that from an observation under
Gaussian noise with variance $\tau_{s}^{2}$. This is made precise in Lemma 1.
Moreover, we saw in the same section that a consequence of Lemma 1 is that the
asymptotic limiting Bayes risk with respect to loss $\ell$ for estimation
$\theta_{v}$ given observations in $\mathcal{T}_{v,2s}$ is given by the
corresponding risk for estimating $\Theta$ given $\Theta+\tau_{s}G$, $V$ with
$(\Theta,V)\sim\mu_{\Theta,V}$ and $G\sim{\mathsf{N}}(0,1)$ independent. In
particular, this applies to the minimum mean square error. On the computation
tree, minimum mean square error can only decrease as $s$ grows because as $s$
grows we receive strictly more information. If
$\mathbb{E}[\operatorname{Var}(\Theta|V)]>0$, then
$\textsf{mmse}_{\Theta,V}(\tau^{2})$ is strictly increasing in $\tau$, so that
we conclude that $\tau_{s}$ is non-increasing in $s$. Thus, by (5), we have
also $\tilde{\tau}_{s}$ is non-increasing in $s$ and $\sigma_{s}$ is non-
decreasing in $s$. In the complementary case that
$\mathbb{E}[\operatorname{Var}(\Theta|V)]=0$, we compute
$\sigma_{s}^{2}=\tau_{\Theta}^{2}/\delta$ and $\tilde{\tau}_{s}^{2}=0$ for all
$s\geq 0$, and $\tau_{s}^{2}=0$ for all $s\geq 1$. Thus, the same monotoncity
results hold in this case. These monotonicity results will imply the needed
structural properties of the state evolution matrices
$(T_{s,s^{\prime}}),(\Sigma_{s,s^{\prime}})$ used below.

For all $s\leq t$, define

$\alpha_{s}=\frac{1}{\tilde{\tau}_{s}}\mathbb{E}[\mathbb{E}[G_{1}|Y,G_{0},U]^{2}],\;\;T_{s,t}=\mathbb{E}[\mathbb{E}[G_{1}|Y,G_{0},U]^{2}],\;\;\Sigma_{s,t}=\sigma_{t}^{2},$

where $Y=h(\sigma_{s}G_{0}+\tilde{\tau}_{s}G_{1},W)$ and
$G_{0},G_{1}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}{\mathsf{N}}(0,1)$
and $W\sim\mu_{W}$ independent. By the monotoncity properties stated,
$(T_{s,t}),(\Sigma_{s,t})$ define positive definite arrays. Define

$\displaystyle
f_{t}(b^{t};y,u)=\mathbb{E}[B^{0}-B^{t}|h(B^{0},W)=y,\,B^{t}=b^{t},\,U=u]/\tilde{\tau}_{t},$
$\displaystyle
g_{t}(a^{t};v)=\mathbb{E}[\Theta|V=v,\,\alpha_{t}\Theta+Z^{t}=a^{t}],$

where $(\Theta,V)\sim\mu_{\Theta,V})$, $(W,U)\sim\mu_{W,U}$,
$(B^{0},\ldots,B^{t})\sim{\mathsf{N}}(\boldsymbol{0},\boldsymbol{\Sigma}_{[0{:}t]})$,
$(Z^{1},\ldots,Z^{t})\sim{\mathsf{N}}(\boldsymbol{0},\boldsymbol{T}_{[1{:}t]})$,
all independent. With these definitions,
$(B^{t},B^{0}-B^{t})\stackrel{{\scriptstyle\mathrm{d}}}{{=}}(\sigma_{t}G_{0},\tilde{\tau}_{t}G_{1})$
where
$G_{0},G_{1}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}{\mathsf{N}}(0,1)$.
In particular, $(B^{t})$ form a backwards Gaussian random walk. We thus
compute

$\displaystyle\mathbb{E}[(B^{0}-B^{t})f_{t}(B^{t};h(B^{0},W),U)]/\tilde{\tau}_{t}^{2}=\mathbb{E}[(\mathbb{E}[B^{0}-B^{t}|Y,B^{t},U]/\tilde{\tau}_{t})^{2}]/\tilde{\tau}_{t}=\alpha_{t},$
$\displaystyle\mathbb{E}[f_{s}(B^{s};h(B^{0},W),U)f_{t}(B^{t};h(B^{0},W),U)]$
$\displaystyle\qquad\qquad=\mathbb{E}[\mathbb{E}[B^{0}-B^{s}|Y,B^{s},U]\mathbb{E}[B^{0}-B^{t}|Y,B^{t},U]]/\tilde{\tau}_{t}^{2}$
$\displaystyle\qquad\qquad=\mathbb{E}[(B^{0}-B^{t})^{2}|Y,B^{t},U]/\tilde{\tau}_{t}^{2}=T_{s,t},$
$\displaystyle\frac{1}{\delta}\mathbb{E}[\Theta
g_{t}(\alpha_{t}\Theta+Z^{t};V)]=\frac{1}{\delta}\mathbb{E}[\mathbb{E}[\Theta|\Theta+Z^{t}/\alpha_{t},V]^{2}]=\sigma_{t}^{2},$
$\displaystyle\frac{1}{\delta}\mathbb{E}[g_{s}(\alpha_{s}\Theta+Z^{s};V)g_{t}(\alpha_{t}\Theta+Z^{t};V)]=\frac{1}{\delta}\mathbb{E}[\mathbb{E}[\Theta|\Theta+Z^{t}/\alpha_{t},V]^{2}].$

If $f_{t},g_{t}$ are Lipschitz, then, because $h$ is also Lipschitz, Stein’s
lemma [Ste81] implies that the first line is equivalent to
$\mathbb{E}[\partial_{B^{0}}f_{t}(B^{t};h(B^{0},W),U)]=\alpha_{t}$. (Here, we
have used that $B^{0}-B^{t}$ is independent of $B^{t}$). Thus,
$(\alpha_{s}),(T_{s,t}),(\Sigma_{s,t})$ are exactly the state evolution
parameters determined by (36), and Lemma 1 implies that AMP with these
$(f_{s}),(g_{s})$ achieves the lower bound.

If the $f_{t},g_{t}$ are not Lipschitz, we proceed as follows. Fix
$\epsilon>0$. First, pick Lipschitz $\hat{f}_{0}$ such that
$\mathbb{E}[(\hat{f}_{0}(B^{0},W)-f_{0}(B^{0},W))^{2}]<\epsilon$, which is
possibly because Lipschitz functions are dense in $L_{2}$. Define
$\hat{\alpha}_{0}$ and $\hat{T}_{1,1}$ via (36) with $\hat{f}_{0}$ in place of
$f_{0}$. Note that $\lim_{\epsilon\rightarrow 0}\hat{\alpha}_{0}=\alpha_{0}$
and $\lim_{\epsilon\rightarrow 0}\hat{T}_{1,1}=T_{1,1}$. Next, pick Lipschitz
$\hat{g}_{0}$ such that
$\mathbb{E}[(\hat{g}_{0}(\hat{\alpha}_{0}\Theta+\hat{T}_{1,1}^{1/2}G;V)-\mathbb{E}[\Theta|\hat{\alpha}_{0}+\Theta+\hat{T}_{1,1}^{1/2}G;V)])^{2}]<\epsilon$,
which is again possibly because Lipschitz functions are dense in $L_{2}$.
Define
$\hat{\Sigma}_{0,1}=\frac{1}{\delta}\mathbb{E}[\Theta\hat{g}_{t}(\hat{\alpha}\Theta+\hat{T}_{1,1}^{1/2}G;V)]$
and
$\hat{\Sigma}_{1,1}=\frac{1}{\delta}\mathbb{E}[\hat{g}_{t}(\hat{\alpha}\Theta+\hat{T}_{1,1}^{1/2}G;V)^{2}]$.
Because as $\alpha\rightarrow\alpha_{0}$ and $\tau\rightarrow T_{0,0}^{1/2}$,
we have $\mathbb{E}[\Theta|\alpha\Theta+\tau G;V)]\stackrel{{\scriptstyle
L_{2}}}{{\rightarrow}}\mathbb{E}[\Theta|\alpha_{0}\Theta+T_{0,0}^{1/2}G;V)]$,
we conclude that as $\epsilon\rightarrow 0$ that
$\hat{\Sigma}_{0,1}\rightarrow\Sigma_{1,1}$ and
$\hat{\Sigma}_{1,1}\rightarrow\Sigma_{1,1}$. Continuing in this way, we are
able to by taking $\epsilon$ sufficiently small construct Lipschitz functions
$(\hat{f}_{t}),(\hat{g}_{t})$ which track the state evolutoin of the previous
paragraph arbitrarily closely up to a fixed time $t^{*}$. Thus, we may come
arbitrarily close to achieving the lower bound of Theorem 1.

###  F.2 Achieving the bound in the low-rank matrix estimation model

Let $\boldsymbol{\gamma}_{t}=\hat{\boldsymbol{Q}}_{t}$ for $t\geq 0$ and
$\boldsymbol{\alpha}_{t}=\boldsymbol{Q}_{t}$,
$\boldsymbol{\Sigma}_{t,t}=\hat{\boldsymbol{Q}}_{t}$,
$\boldsymbol{T}_{t,t}=\boldsymbol{Q}_{t}$ for $t\geq 1$. Define

$\displaystyle
f_{t}(\boldsymbol{b}^{t};\boldsymbol{u})=\mathbb{E}[\boldsymbol{\Lambda}|\boldsymbol{\gamma}_{t}\boldsymbol{\Lambda}+\boldsymbol{\Sigma}_{t,t}^{1/2}\boldsymbol{G}=\boldsymbol{b}^{t};\boldsymbol{U}],$
$\displaystyle
g_{t}(\boldsymbol{a}^{t};\boldsymbol{v})=\mathbb{E}[\boldsymbol{\Theta}|\boldsymbol{\alpha}_{t}\boldsymbol{\Theta}+\boldsymbol{T}_{t,t}^{1/2}\boldsymbol{G}=\boldsymbol{a}^{t};\boldsymbol{V}].$

We check that the parameters so defined satisfy the AMP state evolution (37).
Note that by (7),

$\displaystyle\boldsymbol{T}_{t+1,t+1}$
$\displaystyle=\boldsymbol{Q}_{t+1}=\mathbb{E}[\mathbb{E}[\boldsymbol{\Lambda}|\hat{\boldsymbol{Q}}_{t}^{1/2}\boldsymbol{\Lambda}+\boldsymbol{G};\boldsymbol{U}]\mathbb{E}[\boldsymbol{\Lambda}|\hat{\boldsymbol{Q}}_{t}^{1/2}\boldsymbol{\Lambda}+\boldsymbol{G};\boldsymbol{U}]^{\mathsf{T}}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\boldsymbol{\Lambda}|\hat{\boldsymbol{Q}}_{t}\boldsymbol{\Lambda}+\hat{\boldsymbol{Q}}_{t}^{1/2}\boldsymbol{G};\boldsymbol{U}]\mathbb{E}[\boldsymbol{\Lambda}|\hat{\boldsymbol{Q}}_{t}\boldsymbol{\Lambda}+\hat{\boldsymbol{Q}}_{t}^{1/2}\boldsymbol{G};\boldsymbol{U}]^{\mathsf{T}}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\boldsymbol{\Lambda}|\boldsymbol{\gamma}_{t}\boldsymbol{\Lambda}+\boldsymbol{\Sigma}_{t,t}^{1/2}\boldsymbol{G};\boldsymbol{U}]\mathbb{E}[\boldsymbol{\Lambda}|\boldsymbol{\gamma}_{t}\boldsymbol{\Lambda}+\boldsymbol{\Sigma}_{t,t}^{1/2}\boldsymbol{G};\boldsymbol{U}]^{\mathsf{T}}],$
$\displaystyle\boldsymbol{\alpha}_{t+1}$
$\displaystyle=\mathbb{E}[\mathbb{E}[\boldsymbol{\Lambda}|\hat{\boldsymbol{Q}}_{t}^{1/2}\boldsymbol{\Lambda}+\boldsymbol{G};\boldsymbol{U}]\mathbb{E}[\boldsymbol{\Lambda}|\hat{\boldsymbol{Q}}_{t}^{1/2}\boldsymbol{\Lambda}+\boldsymbol{G};\boldsymbol{U}]^{\mathsf{T}}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\boldsymbol{\Lambda}|\boldsymbol{\gamma}_{t}\boldsymbol{\Lambda}+\boldsymbol{\Sigma}_{t,t}^{1/2}\boldsymbol{G};\boldsymbol{U}]\boldsymbol{\Lambda}^{\mathsf{T}}]$

where
$(\boldsymbol{\Theta},\boldsymbol{V})\sim\mu_{\boldsymbol{\Theta},\boldsymbol{V}}$
and
$(\boldsymbol{\Lambda},\boldsymbol{U})\sim\mu_{\boldsymbol{\Lambda},\boldsymbol{U}}$.
The state evolution equations (7) for $\boldsymbol{\Sigma}_{t,t}$ and
$\boldsymbol{\gamma}_{t}$ hold similarly.

If $f_{t},g_{t}$ so defined are Lipschitz, then
$(\alpha_{s}),(\boldsymbol{T}_{s,t}),(\boldsymbol{\Sigma}_{s,t})$ are exactly
the state evolution parameters determined by (36), and Lemma 1 implies that
AMP with these $(f_{s}),(g_{s})$ achieves the lower bound. If the
$f_{t},g_{t}$ so defined are not Lipschitz, then the same strategy used in the
previous section allows us to achieve the lower bound within tolerance
$\epsilon>0$.

##  Appendix G Proofs for sparse phase retrieval and sparse PCA

###  G.1 Proof of Lemma 1

Note that $\|\overline{\boldsymbol{\theta}}_{0}\|_{2}$ is tightly concentrated
around $\mu^{2}\varepsilon$. As a consequence, we can replace the side
information $\overline{\boldsymbol{v}}$ by
$\boldsymbol{v}=\sqrt{\tilde{\alpha}}\boldsymbol{\theta}_{0}+\boldsymbol{g}$.
We apply Theorem 2 with $r=1$, and loss