# Sudakov-Fernique post-AMP,
and a new proof of the local convexity of the TAP free energy

Michael Celentano Department of Statistics, University of California,
Berkeley. E-mail<EMAIL_ADDRESS>
###### Abstract

In many problems in modern statistics and machine learning, it is often of
interest to establish that a first order method on a non-convex risk function
eventually enters a region of parameter space in which the risk is locally
convex. We derive an asymptotic comparison inequality, which we call the
_Sudakov-Fernique post-AMP inequality_ , which, in a certain class of problems
involving a ${\rm GOE}$ matrix, is able to probe properties of an optimization
landscape locally around the iterates of an approximate message passing (AMP)
algorithm. As an example of its use, we provide a new, and arguably simpler,
proof of some of the results of [CFM21], which establishes that the so-called
TAP free energy in the $\mathbb{Z}_{2}$-synchronization problem is locally
convex in the region to which AMP converges. We further prove a conjecture of
[AMS22] involving the local convexity of a related but distinct TAP free
energy, which, as a consequence, confirms that their algorithm efficiently
samples from the Sherrington-Kirkpatrick Gibbs measure throughout the “easy”
regime.

##  1 Introduction

Many problems in modern statistics and machine-learning involve optimizing a
non-convex loss function. In many instances, first-order methods like gradient
descent, stochastic gradient descent, approximate message passing, and related
algorithms have been observed, both empirically and theoretically, to perform
well even when the objective is highly non-convex. Examples include phase
retrieval [CLS15, CC15, SWW17, CCFM19, CLM16], matrix completion, blind
deconvolution [MWCC20], neural networks [VSL+22, GAS+19, SMBC+20a], spiked
matrix and tensor estimation [MZ20, MKUZ19, SMBC+19, SMBC+20b], Gaussian
mixture classification [MKUZ20], among others. In all of these examples, there
are regimes in which first-order methods successfully find points with near-
minimal objective value or learn parameters with good statistical performance.
Substantial research effort has been dedicated— and continues to be dedicated
—to understanding what drives the success or failure of these methods in non-
convex settings.

In some instances, the success of first-order methods can be explained by the
following two-stage phenomenon [CCFM19, CFM21]. Upon initialization, the
first-order method is in a region of parameter space where the landscape is
non-convex. In the first stage, the algorithm makes progress towards the
global optimum or builds correlation with the unknown signal, despite the non-
convexity of the surrounding landscape. Often, the analysis in this stage is
primarily statistical: in each step, the randomness in the data generating
distribution is used to argue that, with high-probability, the algorithm
continues to make progress towards the global optimum or the hidden signal.
This statistical analysis typically fails after sufficiently many iterations
because— without resampling —the iterates become correlated with the
randomness in the data in a complex way which is difficult to control. It is
important, then, that the algorithm eventually enters a second stage, in which
it arrives in a region of parameter space which is locally convex. Now, the
analysis becomes geometric: the algorithm makes progress towards a local
optimum based on standard results from convex optimization theory. Because the
statistical analysis in the first stage fails after sufficiently many
iterations, it is important that the argument in the second stage is geometric
rather than statistical. Once the local geometry of the landscape is
established, the analysis becomes worst-case and deterministic.

In this paper, we present a comparison inequality— _the Sudakov-Fernique post-
AMP inequality_ —which in a certain class of problems is able to probe
properties of an optimization landscape locally around the iterates of an
approximate message passing algorithm. Thus, it is well suited to establishing
the two-stage phenomenon described in the previous paragraph when AMP is used
in the first stage. Recent papers [CMW20, MW22, CCM21] have shown that a large
class of first-order methods, including gradient descent, accelerated gradient
descent, and related algorithms on appropriate optimization objectives, are
equivalent to AMP algorithms after a change of variables. Thus, the Sudakov-
Fernique post-AMP inequality can also probe the local landscape surrounding
the iterates of such methods.

As an example, we consider in detail the problem of
$\mathbb{Z}_{2}$-synchronization and the corresponding optimization problem
based on the TAP free energy. This model and optimization problem are defined
in Section 1.1. We demonstrate how to use the Sudakov-Fernique post-AMP
inequality to probe the landscape of the TAP free energy locally around
iterates of an AMP algorithm tailored to this model. This provides a new— and
arguably simpler —proof of one of the main results in the paper [CFM21],
namely, that AMP eventually enters a region of strong convexity around a
stationary point of the objective. More recently, the paper [AMS22] considered
the problem of efficiently sampling from the Sherrington-Kirkpatrick
Hamiltonian, which we also define in Section 1.1. One part of their proof
requires considering a different but closely related version of the
$\mathbb{Z}_{2}$-synchronization problem and TAP free energy. In order to
establish the success of their algorithm, they require establishing the
convergence of AMP to a region of this TAP free energy which is strongly
convex. Our proof of the local convexity of the TAP free energy considered by
[CFM21] is easily modified to arrive at the same result for the TAP free
energy considered by [AMS22]. This confirms that the algorithm of [AMS22]
successfully samples from the Sherrington-Kirkpatrick Hamiltonian throughout
the computationally easy regime, resolving the conjecture of computational
tractability.

The remainder of the paper is organized as follows. In Section 1.1, we provide
the necessary background on the $\mathbb{Z}_{2}$-synchronization problem and
its corresponding approximate message passing algorithm and TAP free energy.
In Section 1.2, we provide an overview of our results. In Section 1.3, we
briefly review related literature. The Sudakov-Fernique inequality is
presented in Section 2, and our results on the local convexity of TAP free
energy in $\mathbb{Z}_{2}$-synchronization are stated in Section 3. Finally,
our proof of the local convexity of the TAP free energy is presented in
Section 4, which includes the application of the Sudakov-Fernique post-AMP
inequality. Some technical details are deferred to appendices.

###  1.1 Background on $\mathbb{Z}_{2}$-synchronization and the Sherrington-
Kirkpatrick model

In the $\mathbb{Z}_{2}$-synchronization problem, we observe the matrix

${\bm{Y}}=\frac{\lambda}{n}{\bm{x}}{\bm{x}}^{\top}+{\bm{W}}\in{\mathbb{R}}^{n},$
(1)

where ${\bm{W}}\sim{\rm GOE}(n)$, and
$x_{i}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mathsf{Unif}\\{-1,+1\\}$
are unobserved and $\lambda$ is known. The goal is to estimate the unobserved
vector ${\bm{x}}$ with respect to $\ell_{2}$-loss. The observations Eq. (1)
only identify ${\bm{x}}$ up to sign: the posterior
$\mathbb{P}({\bm{x}}\in\cdot\mid{\bm{Y}})$ is equal to the the posterior
$\mathbb{P}(-{\bm{x}}\in\cdot\mid{\bm{Y}})$. Thus, we seek an estimator
$\widehat{\bm{m}}{}=\widehat{\bm{m}}{}({\bm{Y}})$ for which
$\mathbb{E}[\min\\{\|\widehat{\bm{m}}{}\pm{\bm{x}}\|_{2}^{2}\\}]/n$ is small.

Several aspects of this problem are now well-understood from both an
information-theoretic and computational point of view. The paper [DAM16]
studied the asymptotic Bayes risk in this model, and established that for
$\lambda<1$, it is impossible to do better asymptotically (as
$n\rightarrow\infty$) than the trivial estimator
$\widehat{\bm{m}}{}({\bm{Y}})={\bm{0}}=\mathbb{E}[{\bm{x}}]$. For $\lambda>1$,
weak recovery becomes information-theoretically possible: the Bayes estimator
$\widehat{\bm{m}}{}_{\mathrm{Bayes}}$ achieves a non-trivial correlation with
the signal, and
$\mathbb{E}[\min\\{\|\widehat{\bm{m}}{}_{\mathrm{Bayes}}\pm{\bm{x}}\|_{2}^{2}\\}]/n$
converges to a constant in $(0,1)$ which [DAM16] characterize via the solution
to a non-linear fixed-point equation. Moreover, for all $\lambda>1$, [DAM16]
proposed a practical algorithm— a so-called Approximate Message Passing (AMP)
algorithm —which they proved achieves the Bayes risk up to asymptotically
negligible terms provided it was initialized appropriately. Although they
conjectured that their results would hold when using the leading eigenvector
of ${\bm{Y}}$ as an initialization, for technical reasons they only considered
initializations based on independent side information. For example, their
results handle initializations of the form

${\bm{y}}=\gamma_{0}{\bm{x}}+\sqrt{\gamma_{0}}{\bm{g}},$ (2)

for some $\gamma_{0}>0$ arbitrarily small but non-vanishing asymptotically,
where ${\bm{g}}\sim{\sf N}(0,{\mathbf{I}}_{n})$. Explicitly, their algorithm
takes the form

$\displaystyle{\bm{z}}^{0}$ $\displaystyle={\bm{y}},\qquad\qquad\qquad$
$\displaystyle{\bm{m}}^{s}$ $\displaystyle=\tanh({\bm{z}}^{s}),$ (3)
$\displaystyle{\bm{z}}^{s+1}$
$\displaystyle=\lambda{\bm{Y}}{\bm{m}}^{s}-\lambda\widehat{\mathsf{b}}{}_{s}{\bm{m}}^{s-1},\qquad\qquad\qquad$
$\displaystyle\widehat{\mathsf{b}}{}_{s}$
$\displaystyle=\lambda(1-Q({\bm{m}}^{s})),$

where ${\bm{m}}\in[-1,1]^{n}$, $Q({\bm{m}}):=\|{\bm{m}}\|_{2}^{2}/n$, and
$\tanh(\,\cdot\,)$ is applied coordinate-wise. They show that

$\lim_{s\rightarrow\infty}\lim_{n\rightarrow\infty}\frac{1}{n}\mathbb{E}[\|\widehat{\bm{m}}{}^{s}-{\bm{x}}\|_{2}^{2}]=\lim_{n\rightarrow\infty}\frac{1}{n}\mathbb{E}[\min\\{\|\widehat{\bm{m}}{}_{\mathrm{Bayes}}\pm{\bm{x}}\|_{2}^{2}\\}],$
(4)

where the limits in $n$ are taken almost-surely. Note that the initialization
in Eq. (2) breaks the symmetry, so that no minimum is needed inside the
expectation on the left-hand side. Nevertheless, it is unsatisfying for the
result to rely on small but non-negligible side information, which may not be
available. The later paper [MV21a] establishes the same result as [DAM16] when
a spectral initialization is used; that is, ${\bm{z}}^{0}$ is taken to be the
leading eigenvector of ${\bm{Y}}$, appropriately scaled. For simplicity, in
this paper we will study the algorithm of [DAM16] with initialization (2),
although our results are easily extended to the case in which a spectral
initialization is used (see Remark 1).

An alternative but related approach is based on optimization. This approach,
studied by [FMM21, CFM21], is based on minimizing— or attempting to minimize
—the so-called TAP free energy

${\mathcal{F}}({\bm{m}};{\bm{Y}}):=-\frac{\lambda}{2n}{\bm{m}}^{\top}{\bm{Y}}{\bm{m}}-\frac{1}{n}\sum_{i=1}^{n}{\mathsf{h}}(m_{i})-\frac{\lambda^{2}}{4}(1-Q({\bm{m}}))^{2},$
(5)

over the domain ${\bm{m}}\in[-1,1]^{n}$, where
${\mathsf{h}}(m):=-\frac{1+m}{2}\log\frac{1+m}{2}-\frac{1-m}{2}\log\frac{1-m}{2}$
is the binary entropy function. The TAP free energy can be seen as a
correction to a ‘naïve mean field’ free energy which was first derived in the
context of spin-glasses in statistical physics [TAP77]. The TAP free energy is
related to the AMP algorithm Eq. (3): the fixed-points of Eq. (3) exactly
correspond to the stationary points of ${\mathcal{F}}(\,\cdot\,;{\bm{Y}})$. In
fact, approximate message passing algorithms were first derived as an
iterative construction of solution to the TAP equation
$\nabla{\mathcal{F}}({\bm{m}};{\bm{y}})=0$ [Bol14]. It is widely believed that
the global minimizer of the TAP free energy asymptotically achieves Bayes
optimal performance, and the papers [FMM21, CFM21] have made progress towards
making this conjecture rigorous. [FMM21] establishes that for sufficiently
large $\lambda$, all stationary points of the TAP free energy with
sufficiently small objective value are clustered in a small region around the
Bayes estimate, and so asymptotically achieve Bayes optimal performance. The
paper [CFM21] showed that for all $\lambda>1$, the TAP free energy has a
unique local minimizer close to the Bayes estimate, and established its global
minimality subject to a conjecture that was checked numerically. Thus, there
is strong evidence that minimizing the TAP free energy achieves asymptotically
optimal performance throughout the weak-recovery regime $\lambda>1$. One
potential advantage of the TAP formulation, however, is that it opens the
possibility to use methods like gradient descent or other descent algorithms
to construct estimates of ${\bm{x}}$. Our purpose here is not to give a
complete account of the origin and merits of the TAP approach. We refer the
interested reader to the discussions in [TAP77, MPV87, FMM21, CFM21] and
references therein. Rather, for our purposes, the TAP free energy serves as an
example of the use of the Sudakov-Fernique post-AMP inequality to probe the
local structure of a non-convex objective around the iterates of an AMP
algorithm. Indeed, our approach will reproduce some of the results of [CFM21],
but arguably in a simpler way.

More recently, the paper [AMS22] considered the problem of sampling from the
Sherrington-Kirkpatrick Hamiltonian. In particular, for a matrix
${\bm{W}}\sim{\rm GOE}(n)$, one would like to sample from the measure on
$\\{-1,1\\}^{n}$ with density relative to he uniform measure

$\mu_{{\bm{W}}}({\bm{x}})=\frac{1}{Z(\lambda,{\bm{W}})}e^{(\lambda/2)\langle{\bm{x}},{\bm{W}}{\bm{x}}\rangle},$
(6)

where $Z(\lambda,{\bm{W}})$ is a normalizing constant. The authors propose a
randomized algorithm which runs in polynomial time, takes as input the matrix
${\bm{W}}$, and outputs a random vector
${\bm{x}}^{\mathrm{alg}}\in\\{-1,1\\}^{n}$ with distribution, conditional on
${\bm{W}}$, denoted by $\mu_{{\bm{W}}}^{\mathrm{alg}}$. For an appropriately
chosen distance $\mathsf{dist}$ on probability measures (in this case, the
$\ell_{2}$-Wasserstein distance, which we will define in Section 1.4), the
authors show that
$\mathsf{dist}(\mu_{\bm{W}},\mu_{\bm{W}}^{\mathrm{alg}})\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}0$
when $\lambda<1/2$, where the probabalistic convergence is over randomness in
${\bm{W}}$ and auxiliary randomness in the algorithm. Further, for
$\lambda>1$, they present an impossibility result: no algorithm which
satisfies a certain stability property is able to sample from $\mu_{{\bm{W}}}$
in the sense
$\mathsf{dist}(\mu_{\bm{W}},\mu_{\bm{W}}^{\mathrm{alg}})\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}0$.
A phase transition occurs at $\lambda=1$ in the structure of the measure
$\mu_{{\bm{W}}}$ which forms the basis of this impossibility result, and which
has led to the conjecture that sampling from the SK measure for $\lambda>1$ is
impossible for any polynomial time algorithm, not just those satisfying the
given stability property. Conversely, it is conjectured that for $\lambda<1$,
sampling is possible in polynomial time, and in fact, the authors of [AMS22]
conjecture their algorithm achieves this. Indeed, for $\lambda\in[1/2,1)$,
their proof breaks down in only one step, in which the local strong convexity
of a certain TAP free energy, similar but distinct from the one in Eq. (5),
must be but has not been established.

We will not in this paper describe the details of the SK-sampling algorithm,
and refer the interested reader to [AMS22] for details. The step in which
their argument breaks down occurs in a sub-routine which estimates the
posterior mean of ${\bm{x}}$ in the $\mathbb{Z}_{2}$-synchronization model (1)
with side information (2). Note that above, although we use ${\bm{y}}$ as an
initialization, our interest was in computing the Bayes estimator given
$\mathbb{P}({\bm{x}}\in\cdot|{\bm{Y}})$; now we will be interested in
computing the mean of $\mathbb{P}({\bm{x}}\in\,\cdot\,|{\bm{Y}},{\bm{y}})$.
This can be computed, as above, using an AMP algorithm or by minimizing a
certain TAP free energy whose stationary points agree with the fixed points of
the AMP algorithm. Because we have a different target, the AMP algorithm used
by [AMS22] is modified to

$\displaystyle{\bm{z}}^{0}$ $\displaystyle={\bm{y}},\qquad\qquad\qquad$
$\displaystyle{\bm{m}}^{s}$ $\displaystyle=\tanh({\bm{z}}^{s}),$ (7)
$\displaystyle{\bm{z}}^{s+1}$
$\displaystyle=\lambda{\bm{Y}}{\bm{m}}^{s}+{\bm{y}}-\lambda\widehat{\mathsf{b}}{}_{s}{\bm{m}}^{s-1},\qquad\qquad\qquad$
$\displaystyle\widehat{\mathsf{b}}{}_{s}$
$\displaystyle=\lambda(1-Q({\bm{m}}^{s})),$

and the TAP free energy they use is modified to

${\mathcal{F}}({\bm{m}};{\bm{Y}}):=-\frac{\lambda}{2n}{\bm{m}}^{\top}{\bm{Y}}{\bm{m}}-\frac{1}{n}\sum_{i=1}^{n}{\mathsf{h}}(m_{i})-\frac{1}{n}\langle{\bm{y}},{\bm{m}}\rangle-\frac{\lambda^{2}(1-q_{\infty})(1+q_{\infty}-2Q({\bm{m}}))}{4},$
(8)

where $q_{\infty}$ is a deterministic constant which we will specify below in
Proposition 3. We will show that with high-probability as
$n\rightarrow\infty$, the AMP algorithm (7) in finitely many iterations
arrives in a region of space in which the TAP free energy (8) is locally
strongly convex and contains a unique stationary point. We establish this for
any $\lambda>0$. For $\lambda\in[1/2,1)$, this closes the only gap in the
proof of [AMS22] and confirms that in this regime, their algorithm samples
from the SK Gibbs measure in polynomial time in the sense of
$\mathsf{dist}(\mu_{\bm{W}},\mu_{\bm{W}}^{\mathrm{alg}})\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}0$.

###  1.2 Overview of results

We now provide a brief overview of our results.

  1. 1.

We prove a comparison inequality— _the Sudakov-Fernique post-AMP inequality_
—which allows one to study properties of an optimization landscape defined in
terms of the iterates of an approximate message passing algorithm. Strictly
speaking, this is not a new comparison inequality: in fact, it is nothing but
the original Sudakov-Fernique inequality applied to a matrix whose
distribution conditional on the AMP iterates is drawn from a Gaussian
Orthogonal Ensemble. Moreover, the idea of applying the Sudakov-Fernique
inequality conditionally on linear constraints is not new; for example, it was
used extensively in [CFM21]. Our main insight is to identify certain structure
in the conditional inequality which facilitates its analysis, and to write the
inequality in a way which better elucidates this structure. The structure we
identify is as follows: whereas the original Sudakov-Fernique inequality
involves an optimization involving a single high-dimensional Gaussian vector,
the Sudakov-Fernique post-AMP inequality involves an optimization involving a
finite number of high-dimensional approximately-Gaussian vectors. This
structure greatly simplifies the analysis of the Sudakov-Fernique post-AMP
inequality.

  2. 2.

We provide a novel proof that the TAP free energy of [FMM21] is strongly
convex in a local region around the AMP fixed point. Moreover, we show that
for sufficiently large (but fixed) $k$, the $k^{\text{th}}$ iterate of the AMP
algorithm arrives in this local region of strong convexity with asymptotically
high-probability. This result already appeared in [CFM21], but our analysis
simplifies several key steps, and in particular, avoids using the Kac-Rice
formula. In fact, the structure described above allows us to reduce the
analysis of the Sudakov-Fernique inequality conditioned on a large number of
AMP iterates to a certain low-dimensional optimization problem which was
already analyzed in [CFM21].

  3. 3.

We apply our proof technique to the modified TAP free energy and AMP iteration
considered in [AMS22], establishing for the first time the local strong
convexity of their TAP free energy around sufficiently late iterates of the
AMP algorithm. This confirms their conjecture that the algorithm they present
successfully samples from the Sherrington-Kirkpatrick Gibbs measure for all
$\lambda<1$.

We are able to analyze the TAP free energy of [CFM21] and of [AMS22] in almost
exactly the same way, and, in fact, our presentation of the two arguments is
unified. We feel that the ability to seamlessly analyze both problems at once
is emblematic of the simplicity of the Sudakov-Fernique post-AMP approach we
develop.

###  1.3 Related literature

The Sudakov-Fernique inequality was developed in [Sud71, Sud79, Fer75], which
built on the Slepian inequality of [Sle62]. The Sudakov-Fernique inequality
was used extensively in the analysis of the TAP free energy in [CFM21], and
the analysis in this paper is inspired by the analysis which occurs there.
[CFM21] apply the Sudakov-Fernique inequality after conditioning on
stationarity of the TAP free energy at a point ${\bm{m}}$ chosen _a priori_.
The TAP free energy in general has exponentially many stationary points, and
the authors are interested in local convexity around stationary points
${\bm{m}}$ which have been chosen _a posteriori_ using the AMP algorithm.
Thus, sophisticated arguments involving the Kac-Rice formula are required to
show that the TAP free energy landscape around stationary points chosen a
priori behave likes the landscape around points chosen a posteriori in this
way. We avoid this problem by conditioning on the full sequence of AMP
iterates, and thus avoid the Kac-Rice formula. Nevertheless, some keys steps
in our argument, which we will point out in our proofs, are borrowed directly
from [CFM21].

The use of the Sudakov-Fernique inequality to study optimization problems in
spiked ${\rm GOE}$ models is related to the use of Gordon’s comparison
inequality to study optimization problems in regression models. Gordon’s
inequality was first developed in [Gor85, Gor88], and has recently been
applied to study regression estimates in [Sto13, TAH15, TOH15, MM21, CM21].
The paper [CM21] used Gordon conditionally on the stationary point of an
optimization problem, and arrived at a conditional comparison inequality with
similar structure to that of the Sudakov-Fernique post-AMP inequality.

The sharp characterization of Approximate Message Passing algorithms using
state evolution was developed in [Bol14, BM10, JM13, BMN19]. The Bayes risk in
the $\mathbb{Z}_{2}$-synchronization problem and the Bayes optimality of the
corresponding AMP algorithm was first studied by [DAM16], and the paper
[MV21b] extended the analysis to AMP with spectral initialization. The TAP
free energy was first introduced by physicists as a variational formula for
the free energy in the Sherrington-Kirkpatrick model [TAP77]. Substantial
literature has studied the relationship between the TAP free energy and the
Sherrington-Kirkpatrick Gibbs measure and $\mathbb{Z}_{2}$-synchronization
posterior. We refer the reader to the discussions in [FMM21, CFM21] for
pointers to the relevant literature. As we have already described, this paper
builds on the paper [CFM21, AMS22], which study the local convexity of the TAP
free energy in the $\mathbb{Z}_{2}$-synchronization model and sampling from
the Sherrington-Kirkipatrick Hamiltonian, respectively.

###  1.4 Notation

For a sequence of random variables $X_{n}$, we denote

$\operatorname*{p-lim\,inf}_{n\rightarrow\infty}=\sup\Big{\\{}t\in{\mathbb{R}}\Bigm{|}\mathbb{P}(X_{n}\leq
t)\rightarrow
0\Big{\\}},\qquad\operatorname*{p-lim\,sup}_{n\rightarrow\infty}=\inf\Big{\\{}t\in{\mathbb{R}}\Bigm{|}\mathbb{P}(X_{n}\geq
t)\rightarrow 0\Big{\\}}.$ (9)

We use $\,\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\,$ to denote
convergence in probability, and for a constant $c\in{\mathbb{R}}$, we write
$\operatorname*{p-lim}_{n\rightarrow\infty}X_{n}=c$ to mean
$X_{n}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}c$. Recall that for
probability measures $\mu,\nu$ on ${\mathbb{R}}^{m}$, a coupling of $\mu$ and
$\nu$ is a probability measure $\Pi$ on $({\mathbb{R}}^{m})^{2}$, whose first
$m$ coordinates are distributed according to $\mu$, and whose last $m$
coordinates are distributed according to $\nu$. We denote by
$W_{2}({\mathbb{R}}^{m})$ the space of square integrable probability measures
on ${\mathbb{R}}^{m}$ endowed with the $\ell_{2}$-Wasserstein metric,

$W_{2}(\mu,\nu):=\inf_{\Pi}\mathbb{E}[\|{\bm{X}}-{\bm{Y}}\|_{2}^{2}]^{1/2},$
(10)

where the infimum is over couplings $\Pi$ of $\mu$ and $\nu$, and
$({\bm{X}},{\bm{Y}})\sim\Pi$. There is a mild abuse in notation—
$W_{2}({\mathbb{R}}^{m})$ denotes the metric space, and $W_{2}(\mu,\nu)$
denotes the metric —but this should cause no confusion. For a sequence of
probability measures $\mu_{n}\in W_{2}({\mathbb{R}}^{m})$, we write
$\mu_{n}\stackrel{{\scriptstyle W_{2}}}{{\rightarrow}}\mu$ to mean
$W_{2}(\mu_{n},\mu)\rightarrow 0$. For a square matrix
$\bm{\Gamma}\in{\mathbb{R}}^{m\times m}$ or a bi-infinite matrix
$\bm{\Gamma}\in{\mathbb{R}}^{\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}}$, we use
$\bm{\Gamma}_{\leq k}$ to denote the $k\times k$ matrix consisting of its
first $k$ rows and columns, $\bm{\Gamma}_{k,\,\cdot\,}$ to denote its
$k^{\text{th}}$ row, and $\bm{\Gamma}_{\,\cdot\,,k}$ to denotes its
$k^{\text{th}}$ column, and $K_{i,j}$ to denote its $(i,j)^{\text{th}}$ entry.
For a matrix ${\bm{M}}\in{\mathbb{R}}^{n\times m}$, we will typically denote
columns of ${\bm{M}}$ with lower-case bold-face, as in ${\bm{m}}_{i}$ for the
$i^{\text{th}}$ column, and rows of ${\bm{M}}$ with lower-case bold-face with
a breve accent, as in $\breve{\bm{m}}{}_{i}$ for the $i^{\text{th}}$ row. In
any case, we will specify how we denote rows and columns in the text when this
comes up. For a collection of vectors and matrices, we will use
$\widehat{\mu}{}$ with these vectors and matrices as subscripts to denote the
joint empirical distribution of their coordinates and rows. For example, if
${\bm{a}}\in{\mathbb{R}}^{n}$ and ${\bm{A}}\in{\mathbb{R}}^{n\times m}$, then
$\widehat{\mu}{}_{{\bm{a}},{\bm{A}}}$ is the distribution on
${\mathbb{R}}^{m+1}$ given by

$\widehat{\mu}{}_{{\bm{a}},{\bm{A}}}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{a_{i},\breve{\bm{a}}_{i}},$
(11)

where $\delta_{a_{i},\breve{\bm{a}}_{i}}$ is a unit-sized point mass at
$(a_{i},\breve{\bm{a}}_{i})$. We will denote by $\mathbb{S}_{>0}^{m}$ the
space of $m\times m$ symmetric positive-definite matrices. We denote by
$\mathbb{S}_{>0}^{\infty}$ the space of bi-infinite symmetric matrices whose
finite diagonal sub-matrices are all positive definite. For a matrix
${\bm{A}}$, we denote by $\|{\bm{A}}\|_{{\rm op}}$ its operator norm. For a
vector ${\bm{x}}\in{\mathbb{R}}^{n}$, we denote by $\|{\bm{x}}\|$ its
Euclidean norm. For any $n$, we denote by $\mathsf{B}_{2}(0,R)$ the Euclidean
ball in ${\mathbb{R}}^{n}$ with radius $R$ centered at the origin:
$\mathsf{B}_{2}(0,R)=\\{{\bm{x}}\in{\mathbb{R}}^{n}\mid\|{\bm{x}}\|\leq n\\}$.
The dimension will always be clear from context.

##  2 The Sudakov-Fernique post-AMP inequality

First, we recall the following form of classical Sudakov-Fernique inequality
[Sud71, Sud79, Fer75].

######  Proposition 1 (Sudakov-Fernique inequality).

Let ${\bm{W}}\sim{\rm GOE}(n)$, ${\bm{\xi}}\sim{\sf
N}({\bm{0}},{\mathbf{I}}_{n})$, and for ${\bm{v}}\in{\mathbb{R}}^{n}$, let
${\bm{g}}({\bm{v}}):=\|{\bm{v}}\|{\bm{\xi}}$. Then for any $t\in{\mathbb{R}}$,
closed set $K\subset{\mathbb{R}}^{n+m}$, and continuous function
$f:{\mathbb{R}}^{n+m}\rightarrow{\mathbb{R}}$,

$\mathbb{P}\left(\sup_{({\bm{v}},{\bm{u}})\in
K}{\bm{v}}^{\top}{\bm{W}}{\bm{v}}+f({\bm{u}},{\bm{v}})\geq
t\right)\leq\mathbb{P}\left(\sup_{({\bm{v}},{\bm{u}})\in
K}\frac{2}{\sqrt{n}}\langle{\bm{g}}({\bm{v}}),{\bm{v}}\rangle+f({\bm{u}},{\bm{v}})\geq
t\right).$ (12)

(Here ${\bm{v}}\in{\mathbb{R}}^{n}$ and ${\bm{u}}\in{\mathbb{R}}^{m}$ for some
non-negative integer $m$).

Typically we would like to understand the optimization problem on the left-
hand side of Eq. (12), but this is difficult because it involves a ${\rm
GOE}(n)$ matrix. The utility of the Sudakov-Fernique inequality is that it
allows us to instead study the optimization problem on the right-hand side of
Eq. (12), which is substantially easier because it involves a random vector.
The Sudakov-Fernique inequality states that this simpler optimization problem
is stochastically larger than the complicated one involving a ${\rm GOE}(n)$
matrix.

An important insight of this paper is that the comparison inequality we arrive
at by applying Sudakov-Fernique after a finite number of iterations of an
approximate message passing algorithm has a structure remarkably similar to
that in Eq. (12). Although we will apply these results to the particular AMP
algorithms in Eqs. (3) and (7), we will state the Sudakov-Fernique post-AMP
inequality for a more general AMP algorithm, as appears in, for example,
[JM13]. We will then specialize it to AMP for the
$\mathbb{Z}_{2}$-synchronization problem.

###  2.1 Sudakov-Fernique post-AMP: the general case

An AMP algorithm is defined by a sequence of $L_{s}$-Lipschitz functions
$f_{s}:{\mathbb{R}}^{s+1}\rightarrow{\mathbb{R}}$ for some sequence of
Lipschitz constants $L_{s}$. The algorithm takes the form

$\displaystyle{\bm{g}}^{0}$ $\displaystyle\sim{\sf
N}(0,{\mathbf{I}}_{n}),\qquad\qquad\qquad$ $\displaystyle{\bm{m}}^{s}$
$\displaystyle=f_{s}({\bm{g}}^{0},\ldots,{\bm{g}}^{s}),$ (13)
$\displaystyle{\bm{g}}^{s+1}$
$\displaystyle={\bm{W}}{\bm{m}}^{s}-\sum_{j=1}^{s}{\mathsf{b}}_{sj}{\bm{m}}^{j-1},$

where ${\mathsf{b}}_{sj}$ are carefully chosen deterministic constants which
we will define below. The functions $f_{s}$ are applied row-wise to
${\bm{g}}^{0},\ldots,{\bm{g}}^{s}$; that is,
$f_{s}({\bm{g}}^{0},\ldots,{\bm{g}}^{s})_{i}=f_{s}(g^{0}_{i},\ldots,g^{s}_{i})$.
The iterations in Eqs. (3) and (7) are not in the form given by Eq. (13), but
are well approximated by an iteration in this form, so that, using an argument
that is standard in the AMP literature, our main result will extend to these
iterations.

The behavior of the iterates of the AMP algorithm are well described by a
certain scalar iteration called _state evolution_. State evolution is given by
a bi-infinite covariance matrix $\bm{K}\in\mathbb{S}^{\infty}_{\geq 0}$
defined inductively by

$K_{s+1,t+1}=\mathbb{E}[f_{s}(G_{0},\ldots,G_{s})f_{t}(G_{0},\ldots,G_{t})],$
(14)

where $(G_{1},\ldots,G_{t})\sim{\sf N}(0,\bm{K}_{\leq t})$ independent of
$G_{0}\sim{\sf N}(0,1)$. Note that the base case of this definition is handled
automatically: $K_{1,1}=\mathbb{E}[f_{0}(G_{0})^{2}]$, where $G_{0}\sim{\sf
N}(0,1)$. Then, for $1\leq j\leq s$,

${\mathsf{b}}_{sj}:=\mathbb{E}[\partial_{G_{j}}f_{s}(G_{0},\ldots,G_{s})],$
(15)

where $(G_{1},\ldots,G_{t})$ and $G_{0}$ have the distribution given by the
state evolution. Here, the derivative exists almost surely by Rademacher’s
theorem.

The state evolution for AMP is given by the following theorem, proved, for
example, in [JM13].

######  Proposition 2 (State evolution).

For ${\bm{W}}\sim{\rm GOE}(n)$ and any $k\in\mathbb{Z}_{>0}$, the empirical
distribution of the coordinates of the AMP iteration converges almost surely
in $W_{2}({\mathbb{R}}^{k+1})$ as follows:

$\frac{1}{n}\sum_{i=1}^{n}\delta_{(g_{i}^{0},\ldots,g_{i}^{k+1})}\xrightarrow[n\rightarrow\infty]{W_{2}}{\sf
N}(0,1)\times{\sf N}(0,\bm{K}_{\leq k}).$ (16)

In particular, if $G_{0}\sim{\sf N}(0,1)$ independent of
$(G_{1},\ldots,G_{k})\sim{\sf N}(0,\bm{K}_{\leq k})$ and, for $0\leq s\leq k$,
$M_{s}:=f_{s}(G_{0},\ldots,G_{s})$, we get almost surely

$\frac{1}{n}\sum_{i=1}^{n}\delta_{(m_{i}^{0},\ldots,m_{i}^{k},g_{i}^{0},\ldots,g_{i}^{k+1})}\xrightarrow[n\rightarrow\infty]{W_{2}}(M_{0},\ldots,M_{k},G_{0},\ldots,G_{k}).$
(17)

Proposition 2 states that, in a certain sense, the iterates
${\bm{g}}^{0},\ldots,{\bm{g}}^{k}$ behave like high-dimensional jointly
Gaussian vectors with a covariance described by the state evolution matrix
$\bm{K}_{\leq k}$. A consequence of Proposition 2 and the definition of
$\bm{K}$ in Eq. (14) is that the geometry of the iterates ${\bm{m}}^{s}$
agrees with the geometry of the iterates ${\bm{g}}^{s+1}$. In particular, if
we let ${\bm{M}}\in{\mathbb{R}}^{n\times k}$ be the matrix whose
$s^{\text{th}}$ column is ${\bm{m}}^{s-1}$, and
${\bm{G}}\in{\mathbb{R}}^{n\times k}$ be the matrix whose $s^{\text{th}}$
column is ${\bm{g}}^{s}$, we have almost surely

$\lim_{n\rightarrow\infty}\frac{1}{n}{\bm{M}}^{\top}{\bm{M}}=\lim_{n\rightarrow\infty}\frac{1}{n}{\bm{G}}^{\top}{\bm{G}}=\bm{K}_{\leq
k}.$ (18)

Provided $\bm{K}_{\leq k}$ is positive definite, both
$\\{{\bm{m}}^{0},\ldots,{\bm{m}}^{k-1}\\}$ and
$\\{{\bm{g}}^{1},\ldots,{\bm{g}}^{k}\\}$ span $k$-dimensional subspaces of
${\mathbb{R}}^{n}$, and there is a canonical linear mapping between them which
maps ${\bm{m}}^{s-1}$ to ${\bm{g}}^{s}$ for all $s$ which, for $k$ fixed with
$n\rightarrow\infty$, is an approximate isometry. This linear mapping is given
by

$\bm{T}:={\bm{G}}({\bm{M}}^{\top}{\bm{M}})^{-1}{\bm{M}}^{\top}.$ (19)

The mapping $\bm{T}$ first projects onto the space spanned by
$\\{{\bm{m}}^{0},\ldots,{\bm{m}}^{k-1}\\}$, and then maps this space onto
$\\{{\bm{g}}^{0},\ldots,{\bm{g}}^{k}\\}$ through an approximate isometry.

We are now ready to state the Sudakov-Fernique post-AMP inequality.

######  Theorem 1 (Sudakov-Fernique post-AMP).

Consider ${\bm{W}}\sim{\rm GOE}(n)$, any $k\in\mathbb{Z}_{>0}$, and the AMP
iteration in Eq. (13). Let ${\bm{\xi}}\sim{\sf N}(0,{\mathbf{I}}_{n})$
independent of everything else. Define $\bm{T}$ as in Eq. (19), and, for
${\bm{v}}\in{\mathbb{R}}^{n}$, define

${\bm{g}}_{\mathsf{AMP}}({\bm{v}}):=\sqrt{n}\bm{T}{\bm{v}}+\|{\mathsf{P}}_{{\bm{M}}}^{\perp}{\bm{v}}\|{\bm{\xi}}.$
(20)

For some $R>0$ and $m\in\mathbb{Z}_{\geq 0}$, let
$K_{n}=K_{n}({\bm{M}},{\bm{G}})$ be a subset of ${\mathbb{R}}^{n+m}$ contained
in the ball $\mathsf{B}_{2}(0,R)$ which may depend on the AMP iterates
${\bm{M}},{\bm{G}}$, and let
$f_{n}:{\mathbb{R}}^{n+m}\times({\mathbb{R}}^{n\times
k})^{2}\times{\mathbb{R}}^{n}$ be a continuous function. Then,

$\operatorname*{p-lim\,sup}_{n\rightarrow\infty}\sup_{({\bm{v}},{\bm{u}})\in
K_{n}}\big{\\{}{\bm{v}}^{\top}{\bm{W}}{\bm{v}}+f_{n}({\bm{v}},{\bm{u}};{\bm{M}},{\bm{G}},{\bm{g}}^{0})\big{\\}}\leq\operatorname*{p-lim\,sup}_{n\rightarrow\infty}\sup_{({\bm{v}},{\bm{u}})\in
K_{n}}\Big{\\{}\frac{2}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{AMP}}({\bm{v}}),{\bm{v}}\rangle+f_{n}({\bm{v}},{\bm{u}};{\bm{M}},{\bm{G}},{\bm{g}}^{0})\Big{\\}}.$
(21)

It is important that both the optimization function $f_{n}$ and the constraint
set $K_{n}$ in Theorem 1 can depend on the AMP iterates ${\bm{M}},{\bm{G}}$.
As we will see in the $\mathbb{Z}_{2}$-synchronization example, this will be
essential to applying Theorem 1 to probe local properties of an optimization
around the AMP iterates. The probabilistic suprema are taken with respect to
all sources of randomness, including in the choice of constraint set $K$. We
prove Theorem 1 in Appendix A.

It is worth stopping here to interpret Theorem 1. As we have described, we can
view the matrix $\bm{T}$ as first projecting onto the space spanned by
$\\{{\bm{m}}^{0},\ldots,{\bm{m}}^{k-1}\\}$, and then mapping this space onto
$\\{{\bm{g}}^{0},\ldots,{\bm{g}}^{k}\\}$ through an approximate isometry.
Moreover, the AMP state evolution (Proposition 2) implies that every vector in
the span of $\\{{\bm{g}}^{1},\ldots,{\bm{g}}^{k}\\}$ looks Gaussian in the
sense of having coordinates with approximately Gaussian empirical
distribution. Thus, $\sqrt{n}\bm{T}{\bm{v}}$ behaves like a vector drawn from
${\sf N}(0,\|{\mathsf{P}}_{{\bm{M}}}{\bm{v}}\|^{2}{\mathbf{I}}_{n})$.111We are
not being precise about what we mean by “behaves like,” though a precise
statement would involve the convergence of empirical coordinate distributions.
Because ${\bm{\xi}}\sim{\sf N}(0,{\mathbf{I}}_{n})$ is independent of
everything else, ${\bm{g}}_{\mathsf{AMP}}({\bm{v}})$ behaves like a vector
drawn from ${\sf N}(0,\|{\bm{v}}\|^{2}{\mathbf{I}}_{n})$. Note that the vector
${\bm{g}}({\bm{v}})$ appearing in the classical Sudakov-Fernique inequality
(12) also exhibits this behavior: ${\bm{g}}({\bm{v}})=\|{\bm{v}}\|{\bm{\xi}}$
is, for fixed ${\bm{v}}$, distributed ${\sf
N}(0,\|{\bm{v}}\|^{2}{\mathbf{I}}_{n})$. In this sense, the classical Sudakov-
Fernique inequality and the Sudakov-Fernique post-AMP inequality have a
remarkably similar structure.

Nevertheless, they also have important differences. In the classical Sudakov-
Fernique inequality, ${\bm{g}}({\bm{v}})$ has a direction chosen uniformly at
random and independent of everything else, but has a norm determined
implicitly by the optimization variable ${\bm{v}}$. In contrast, in the
Sudakov-Fernique post-AMP inequality, both the direction and the norm of
${\bm{g}}_{\mathsf{AMP}}({\bm{v}})$ are determined implicitly by the
optimization variable ${\bm{v}}$. Whereas in the classical Sudakov-Fernique
inequality, ${\bm{g}}({\bm{v}})$ lies in the 1-dimensional space spanned by
the Gaussian vector ${\bm{\xi}}$, in the Sudakov-Fernique post-AMP inequality,
${\bm{g}}_{\mathsf{AMP}}({\bm{v}})$ lies in the $(k+1)$-dimensional space
spanned by the approximately Gaussian vectors
${\bm{g}}^{1},\ldots,{\bm{g}}^{k}$ and the Gaussian vector ${\bm{\xi}}$. Its
decomposition into these components exactly corresponds to the decomposition
of ${\bm{v}}$ into ${\bm{m}}^{0},\ldots,{\bm{m}}^{k-1}$ and its component
orthogonal to their span. In this way, the Sudakov-Fernique post-AMP
inequality is able to capture relationships between the AMP iterates, the
optimization function $f$, the random matrix ${\bm{W}}$, and the constraints
set $K$.

Finally, whereas the classical Sudakov-Fernique inequality makes a comparison
which is valid for finite $n$, the Sudakov-Fernique post-AMP inequality makes
a comparison which is valid asymptotically. Nevertheless, the proof of Theorem
1 uses a finite sample comparison inequality similar to the Sudakov-Fernique
post-AMP inequality, and which provides the more fundamental comparison.
Because it is more difficult to state and harder to motivate this inequality,
we defer details to Appendix A.

###  2.2 Sudakov-Fernique post-AMP in $\mathbb{Z}_{2}$-synchronization

The AMP algorithms in Eqs. (3) and (7) are not of the type appearing in Eq.
(13). Nevertheless, they are well approximated by such an iteration. Thus, it
is not surprising that a result like Theorem 1 holds for this iteration. We
present this result in this section.

In this and the next section, we will present results for the AMP algorithms
and TAP free energies of [FMM21] and [AMS22] in a unified way. In particular,
we consider the iteration

$\displaystyle{\bm{z}}^{0}$ $\displaystyle={\bm{y}},\qquad\qquad\qquad$
$\displaystyle{\bm{m}}^{s}$ $\displaystyle=\tanh({\bm{z}}^{s}),$ (22)
$\displaystyle{\bm{z}}^{s+1}$
$\displaystyle=\lambda{\bm{Y}}{\bm{m}}^{s}+\chi_{{\mathsf{x}}}{\bm{y}}-\lambda\widehat{\mathsf{b}}{}_{s}{\bm{m}}^{s-1},\qquad\qquad\qquad$
$\displaystyle\widehat{\mathsf{b}}{}_{s}$
$\displaystyle=\lambda(1-Q({\bm{m}}^{k})).$

where ${\bm{m}}\in[-1,1]^{n}$ and $Q({\bm{m}}):=\|{\bm{m}}\|_{2}^{2}/n$, and
we take ${\mathsf{x}}\in\\{\mathsf{FMM},\mathsf{AMS}\\}$, with
$\chi_{\mathsf{FMM}}=0$ and $\chi_{\mathsf{AMS}}=1$. Taking
$\chi_{\mathsf{FMM}}=0$ gives Eq. (3), the AMP algorithm considered by [FMM21,
CFM21], and taking $\chi_{\mathsf{AMS}}=1$ gives Eq. (7), the AMP algorithm
considered by [AMS22].

The state evolution for iteration (22) consists of an infinite sequence of
scalar parameters $(\gamma_{s})_{s\geq 0}$, initialized at $\gamma_{0}$ as in
Eq. (2), defined recursively by

$\displaystyle\gamma_{s+1}$
$\displaystyle=\lambda^{2}\mathbb{E}[\tanh^{2}(\gamma_{s}+\sqrt{\gamma_{s}}G)]+\chi_{{\mathsf{x}}}\gamma_{0},$
(23)

where $G_{s}\sim{\sf N}(0,\gamma_{s})$ for $s\geq 1$. The next proposition
states how these parameters describe the behavior of the iterates
${\bm{z}}^{s}$, ${\bm{m}}^{s}$. Moreover, for future reference, we give some
useful properties of the parameters $\gamma_{s}$ and related parameters.

######  Proposition 3 (State evolution).

Consider ${\bm{m}}^{s},{\bm{z}}^{s}$ as defined as in (22), and
$(\gamma_{s})_{s\geq 0}$ as defined in Eq. (23). Moreover, for $s\geq 0$,
define

${\bm{g}}^{s+1}:=\lambda{\bm{W}}{\bm{m}}^{s}-\lambda^{2}(1-Q({\bm{m}}^{s})){\bm{m}}^{s-1}.$
(24)

Fix $k\geq 1$, and let ${\bm{M}}\in{\mathbb{R}}^{n\times k}$ be the matrix
whose $s^{\text{th}}$ column is ${\bm{m}}^{s-1}$, and
${\bm{G}}_{\mathsf{AMP}}$ be the matrix whose $s^{\text{th}}$ column is
${\bm{g}}^{s}$. Denote the $i^{\text{th}}$ row of ${\bm{M}}$ and
${\bm{G}}_{\mathsf{AMP}}$ by $\breve{\bm{m}}{}_{i}$ and
$\breve{\bm{g}}{}_{i}$, respectively. Let $\bm{\Gamma}_{\leq
k}\in\mathbb{S}^{k}_{\geq 0}$ be the matrix given by
$\Gamma_{st}=\gamma_{s\wedge t}$. For ${\mathsf{x}}=\mathsf{FMM}$, we also
assume $\gamma_{0}<\gamma_{\infty}$, defined in Eq. (28).

We have the following:

  1. (i)

We have $\gamma_{s}>0$ for all $s\geq 0$. Further, $\bm{\Gamma}_{\leq k}$ is
positive definite.

  2. (ii)

Let $\bm{K}_{\leq k}=\bm{\Gamma}_{\leq
k}-\chi_{{\mathsf{x}}}\gamma_{0}\bm{1}\bm{1}^{\top}$. Then $\bm{K}_{\leq k}$
is positive definite. Further, let $X$,
$\breve{\bm{M}}{}=(M_{0},\ldots,M_{k-1})$ and
$\breve{\bm{G}}{}=(G_{1},\ldots,G_{k})$ be random vectors in
${\mathbb{R}}^{k}$ with distribution given by $\breve{\bm{G}}{}\sim{\sf
N}(0,\bm{K}_{\leq k})$, $W\sim{\sf N}(0,1)$ independent, and
$M_{0}=\tanh(\gamma_{0}X+\sqrt{\gamma_{0}}W)$,
$M_{s}=\tanh(\gamma_{s}X+G_{s}+\chi_{{\mathsf{x}}}\sqrt{\alpha}W)$. Then the
AMP iterates converge almost surely in Wasserstein sense:

$\frac{1}{n}\sum_{i=1}^{n}\delta_{\breve{\bm{m}}{}_{i},\breve{\bm{g}}{}_{i},w_{i}}\stackrel{{\scriptstyle
W_{2}}}{{\rightarrow}}(\breve{\bm{M}}{},\breve{\bm{G}}{},W).$ (25)

Moreover,

$\mathbb{E}[\breve{\bm{G}}{}\breve{\bm{G}}{}^{\top}]=\lambda^{2}\mathbb{E}[\breve{\bm{M}}{}\breve{\bm{M}}{}^{\top}]=\bm{K}_{\leq
k}.$ (26)

  3. (iii)

We have for $s,t\geq 0$,

$\displaystyle\lambda^{2}\mathbb{E}[\tanh(\gamma_{s}+\mathbf{1}_{s>0}G_{s}+\chi_{{\mathsf{x}}}\sqrt{\gamma_{0}}G_{0})\tanh(\gamma_{t}+\mathbf{1}_{t>0}G_{t}+\chi_{{\mathsf{x}}}\sqrt{\gamma_{0}}G_{0})]$
$\displaystyle=\lambda^{2}\mathbb{E}[\tanh(\gamma_{s\wedge
t}+\sqrt{\gamma_{s\wedge t}}G)]$ (27) $\displaystyle=\gamma_{(s\wedge
t)+1}-\chi_{{\mathsf{x}}}\gamma_{0},$

where $G_{0},G_{s},G_{t}$ are distributed as in the previous item, and
$G\sim{\sf N}(0,1)$.

  4. (iv)

There exists $\gamma_{\infty}\in(0,1)$ such that
$\gamma_{s}\rightarrow\gamma_{\infty}$ as $s\rightarrow\infty$. The parameter
$\gamma_{\infty}$ solves

$\gamma_{\infty}=\lambda^{2}\mathbb{E}\big{[}\tanh^{2}(\gamma_{\infty}+\sqrt{\gamma_{\infty}}G)\big{]}+\chi_{{\mathsf{x}}}\gamma_{0},$
(28)

where $G\sim{\sf N}(0,1)$.

  5. (v)

Let
$q_{\infty}=\mathbb{E}\big{[}\tanh^{2}(\gamma_{\infty}+\sqrt{\gamma_{\infty}}G)\big{]}$
and
$b_{\infty}=\mathbb{E}\big{[}\tanh^{4}(\gamma_{\infty}+\sqrt{\gamma_{\infty}}G)\big{]}$.
We have the identities:

$\begin{gathered}\lambda^{2}(1-q_{\infty})<1,\\\
q_{\infty}=\mathbb{E}\big{[}\tanh^{2}(\gamma_{\infty}+\sqrt{\gamma_{\infty}}G)\big{]}=\mathbb{E}\big{[}\tanh(\gamma_{\infty}+\sqrt{\gamma_{\infty}}G)\big{]},\\\
b_{\infty}=\mathbb{E}\big{[}\tanh^{4}(\gamma_{\infty}+\sqrt{\gamma_{\infty}}G)\big{]}=\mathbb{E}\big{[}\tanh^{3}(\gamma_{\infty}+\sqrt{\gamma_{\infty}}G)\big{]}.\end{gathered}$
(29)

We now provide the Sudakov-Fernique post-AMP inequality in the context of the
AMP algorithm (22) in the $\mathbb{Z}_{2}$-synchronization model.

######  Corollary 1 (Sudakov-Fernique post-AMP in
$\mathbb{Z}_{2}$-synchronization).

Consider the data generating process in Eqs. (1) and (2), and the AMP
iteration in Eq. (22). Let ${\bm{M}}\in{\mathbb{R}}^{n\times k}$ be the matrix
whose $s^{\text{th}}$ column is ${\bm{m}}^{s-1}$,
${\bm{G}}\in{\mathbb{R}}^{n\times k}$ be the matrix whose $s^{\text{th}}$
column is ${\bm{g}}^{s}$ as defined in Eq. (24), and
$\bm{T}=\lambda^{-1}{\bm{G}}({\bm{M}}^{\top}{\bm{M}})^{-1}{\bm{M}}^{\top}$.
Let ${\bm{\xi}}\sim{\sf N}(0,{\mathbf{I}}_{n})$ independent of everything
else, and

${\bm{g}}_{\mathsf{AMP}}({\bm{v}}):=\sqrt{n}\bm{T}{\bm{v}}+\|{\mathsf{P}}_{{\bm{M}}}^{\perp}{\bm{v}}\|{\bm{\xi}}.$
(30)

For some $R>0$ and $m\in\mathbb{Z}_{\geq 0}$, let
$K_{n}=K_{n}({\bm{M}},{\bm{G}})$ be a subset of ${\mathbb{R}}^{n+m}$ which may
depend on the AMP iterates ${\bm{M}},{\bm{G}}$, and let
$f_{n}:{\mathbb{R}}^{n+m}\times({\mathbb{R}}^{n\times k})^{2}$ be a continuous
function. Then,

$\operatorname*{p-lim\,sup}_{n\rightarrow\infty}\sup_{({\bm{v}},{\bm{u}})\in
K_{n}}\big{\\{}{\bm{v}}^{\top}{\bm{W}}{\bm{v}}+f_{n}({\bm{v}},{\bm{u}};{\bm{M}},{\bm{G}},{\bm{g}}^{0},{\bm{x}})\big{\\}}\leq\operatorname*{p-lim\,sup}_{n\rightarrow\infty}\sup_{({\bm{v}},{\bm{u}})\in
K_{n}}\Big{\\{}\frac{2}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{AMP}}({\bm{v}}),{\bm{v}}\rangle+f_{n}({\bm{v}},{\bm{u}};{\bm{M}},{\bm{G}},{\bm{g}}^{0},{\bm{x}})\Big{\\}}.$
(31)

As we show in the next section, Corollary 1 is the central tool in
establishing the local strong convexity of the TAP free energy. The
interpretation of this inequality agrees with the interpretation described in
the discussion following Theorem 1. We prove Corollary 1 in Appendix A.

##  3 Local convexity of the TAP free energy

We expect the Sudakov-Fernique post-AMP inequality to be a generally useful
tool for probing local properties of an optimization landscape around the
iterates of an AMP algorithm. We illustrate this by establishing the local
strong convexity of the TAP free energy after several iterations of the AMP
algorithm (22) in the $\mathbb{Z}_{2}$-synchronization model. As with the AMP
algorithms, we will analyze the TAP free energies in Eqs. (5) and (8) in a
unified way. Thus, for ${\mathsf{x}}\in\\{\mathsf{FMM},\mathsf{AMS}\\}$,
define the TAP free energy

${\mathcal{F}}_{{\mathsf{x}}}({\bm{m}}):=-\frac{\lambda}{2n}{\bm{m}}^{\top}{\bm{Y}}{\bm{m}}-{\mathcal{L}}_{{\mathsf{x}}}({\bm{m}}).$
(32)

where

$\displaystyle{\mathcal{L}}_{\mathsf{FMM}}({\bm{m}})$
$\displaystyle:=\frac{1}{n}\sum_{i=1}^{n}{\mathsf{h}}(m_{i})+\frac{\lambda^{2}}{4}(1-Q({\bm{m}}))^{2},$
(33) $\displaystyle{\mathcal{L}}_{\mathsf{AMS}}({\bm{m}})$
$\displaystyle:=\frac{1}{n}\sum_{i=1}^{n}{\mathsf{h}}(m_{i})+\frac{\langle{\bm{y}},{\bm{m}}\rangle}{n}+\frac{\lambda^{2}(1-q_{\infty})(1+q_{\infty}-2Q({\bm{m}}))}{4},$

for ${\bm{m}}\in[-1,1]^{n}$ and
${\mathsf{h}}(m):=-\frac{1+m}{2}\log\frac{1+m}{2}-\frac{1-m}{2}\log\frac{1-m}{2}$
the binary entropy function. Taking ${\mathsf{x}}=\mathsf{FMM}$ gives the TAP
free energy in Eq. (5), and ${\mathsf{x}}=\mathsf{AMS}$ gives the TAP free
energy in Eq. (8).

Note the TAP free energy is $c/n$-strongly convex in an $\epsilon$-ball around
the $(k-1)^{\text{st}}$ AMP iterate if and only if

$\inf_{\begin{subarray}{c}\|{\bm{v}}\|_{2}=1\\\
\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\end{subarray}}{\bm{v}}^{\top}\nabla^{2}{\mathcal{F}}_{{\mathsf{x}}}({\bm{u}}){\bm{v}}>c/n.$
(34)

Our next theorem establishes that for large enough $k$, this occurs with high-
probability.

######  Theorem 2 (Local convexity).

Consider data generated from the $\mathbb{Z}_{2}$-synchronization model Eqs.
(1) and (2). Consider ${\mathsf{x}}\in\\{\mathsf{FMM},\mathsf{AMS}\\}$. We
have the following.

  1. (i)

If either (1) ${\mathsf{x}}=\mathsf{FMM}$ and $\lambda>1$,
$\gamma_{\infty}>\gamma_{0}>0$, or (2) ${\mathsf{x}}=\mathsf{AMS}$ and
$\lambda>0$, $\gamma_{0}>0$, then there exists $c,c^{\prime}>0$ (depending on
$\lambda,\gamma_{0}$) such that, for any $\epsilon<c^{\prime}$, and any
sufficiently large $k$ (where “sufficiently large” may depend on
$\lambda,\gamma_{0},\epsilon$),

$\operatorname*{p-lim\,inf}_{n\rightarrow\infty}\inf_{\begin{subarray}{c}\|{\bm{v}}\|_{2}=1\\\
\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\end{subarray}}{\bm{v}}^{\top}\nabla^{2}{\mathcal{F}}_{{\mathsf{x}}}({\bm{u}}){\bm{v}}>c/n,$
(35)

where ${\bm{m}}^{k-1}$ is defined via Eq. (22) with $\chi_{{\mathsf{x}}}$ set
according to ${\mathsf{x}}$.

  2. (ii)

Under the conditions of item (i), there exists $c,c^{\prime}>0$ such that for
any $\epsilon<c^{\prime}$, there exists large enough $k$ such that, with
probability approaching $1$ as $n\rightarrow\infty$, the TAP free energy
contains a unique stationary point on
$\\{\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\\}\cap[-1,1]^{n}$. This
stationary point in fact lies in $(-1,1)^{n}$.

We prove Theorem 2 in the next section, with some details deferred to the
appendices.

######  Remark 1.

Although Theorem 2 is stated for a random initialization, we expect it to hold
also for a spectral initialization. A formal argument would proceed as
follows: one can compute the leading eigenvector ${\bm{v}}_{0}$ (with
normalization $\|{\bm{v}}_{0}\|=1$) of ${\bm{Y}}$ to accuracy
$\|{\bm{v}}-{\bm{v}}_{0}\|<\epsilon^{\prime}$ for any $\epsilon^{\prime}>0$
arbitrarily small using finitely many iterations of an AMP algorithm with
independent and informative initialization. Having computed ${\bm{v}}_{0}$ to
this accuracy, one can then begin running the AMP algorithm 22 for $k$
iterations. This two step procedure approximates the AMP algorithm 22 with
spectral initialization with a separate AMP algorithm with random and
informative initialization. Using this alternative AMP, none of the steps in
the proof of Theorem 2 would be fundamentally altered. The result with
spectral initialization is recovered by taking $\epsilon^{\prime}\rightarrow
0$. We do not carry out the complete details of such an argument.

##  4 Proof of Theorem 2

Theorem 2 is proved using the Sudakov-Fernique post-AMP inequality, as it
appears in Corollary 1. First, we use Corollary 1 to reduce the analysis of
the objective in Eq. (35) to analysis of an auxiliary optimization problem.
Although the auxiliary problem is high-dimensional, we can, through a sequence
of approximations, reduce its analysis to that of low-dimensional optimization
problem which is straightforward to understand. This reduction and analysis
forms the remainder of the proof.

By symmetry, the distribution of the infimum in Theorem 2 is the same for all
realization of ${\bm{x}}$. Thus, throughout the rest of the paper, we assume
without loss of generality

${\bm{x}}=\bm{1}=(1,1,\ldots,1)^{\top}.$ (36)

Likewise, we replace $X$ in Proposition 3 with $X=1$.

Note that, to prove Theorem 2(i), it is equivalent to show that there exists
$c>0$ (depending on $\lambda,\gamma_{0}$) such that

$\liminf_{\epsilon\rightarrow
0}\;\;\liminf_{k\rightarrow\infty}\;\;\operatorname*{p-lim\,inf}_{n\rightarrow\infty}\inf_{\begin{subarray}{c}\|{\bm{v}}\|_{2}=1\\\
\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\end{subarray}}{\bm{v}}^{\top}\nabla^{2}{\mathcal{F}}_{{\mathsf{x}}}({\bm{u}}){\bm{v}}>c/n.$
(37)

(Note the order of the first two $\liminf$’s matters, and cannot be
exchanged). A direct calculation gives the Hessian of
${\mathcal{F}}_{{\mathsf{x}}}$:

${\bm{v}}^{\top}\nabla^{2}{\mathcal{F}}_{{\mathsf{x}}}({\bm{u}}){\bm{v}}=-\frac{1}{n}\Big{(}\lambda{\bm{v}}^{\top}{\bm{W}}{\bm{v}}+f_{{\mathsf{x}}}({\bm{v}},{\bm{u}})\Big{)},$
(38)

where

$\displaystyle f_{\mathsf{FMM}}({\bm{v}},{\bm{u}})$
$\displaystyle=\frac{\lambda^{2}\langle\bm{1},{\bm{v}}\rangle^{2}}{n}-\sum_{i=1}^{n}\frac{v_{i}^{2}}{1-u_{i}^{2}}-\lambda^{2}(1-Q({\bm{u}}))\|{\bm{v}}\|^{2}+\frac{2\lambda^{2}\langle{\bm{u}},{\bm{v}}\rangle^{2}}{n},$
(39) $\displaystyle f_{\mathsf{AMS}}({\bm{v}},{\bm{u}})$
$\displaystyle=\frac{\lambda^{2}\langle\bm{1},{\bm{v}}\rangle^{2}}{n}-\sum_{i=1}^{n}\frac{v_{i}^{2}}{1-u_{i}^{2}}-\lambda^{2}(1-q_{\infty})\|{\bm{v}}\|^{2}.$

Now we apply the Sudakov-Fernique post-AMP inequality: by Corollary 1, it
suffices to show that, in the relevant ranges of $\lambda$, there exists
$c>0$, depending only $\lambda,\gamma_{0}>0$, such that

$\limsup_{\epsilon\rightarrow
0}\;\;\limsup_{k\rightarrow\infty}\;\;\operatorname*{p-lim\,sup}_{n\rightarrow\infty}\sup_{\begin{subarray}{c}\|{\bm{v}}\|_{2}=1\\\
\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\end{subarray}}\mathsf{F}_{{\mathsf{x}},k}({\bm{v}},{\bm{u}};{\bm{R}},{\bm{G}},{\bm{\xi}})<-c/n,$
(40)

where

$\mathsf{F}_{{\mathsf{x}},k}({\bm{v}},{\bm{u}};{\bm{R}},{\bm{G}},{\bm{\xi}}):=\frac{2\lambda}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{AMP}}({\bm{v}}),{\bm{v}}\rangle+f_{{\mathsf{x}}}({\bm{v}},{\bm{u}}),$
(41)

for ${\bm{g}}_{\mathsf{AMP}}({\bm{v}})$ as defined in Corollary 1. The
objective $\mathsf{F}_{{\mathsf{x}},k}$ is substantially easier to analyze
than the objective
$({\bm{v}},{\bm{u}})\mapsto{\bm{v}}^{\top}\nabla^{2}{\mathcal{F}}_{{\mathsf{x}}}({\bm{u}}){\bm{v}}$.
The rest of this section establishes Eq. (40).

###  4.1 Reduction to optimization on Wasserstein space

Our first observation is that $\mathsf{F}_{{\mathsf{x}},k}$ is permutation-
invariant with respect to the coordinates of its arguments, so that it is in
fact a function of the empirical distribution

$\widehat{\mu}{}_{\sqrt{n}{\bm{v}},{\bm{u}},{\bm{M}},{\bm{G}},{\bm{g}}^{0},{\bm{\xi}}}:=\frac{1}{p}\sum_{i=1}^{n}\delta_{\sqrt{n}v_{i},u_{i},\breve{\bm{m}}{}_{i},\breve{\bm{g}}{}_{i},g^{0}_{i},\xi_{i}}\in
W_{2}({\mathbb{R}}\times(-1,1)^{k+1}\times{\mathbb{R}}^{k+2}),$ (42)

where $\breve{\bm{m}}{}_{i}$ and $\breve{\bm{g}}{}_{i}$ are the
$i^{\text{th}}$ rows of ${\bm{M}}$ and ${\bm{G}}$, respectively. This
empirical distribution contains $p$ atomic elements of equal size, so that
$\mathsf{F}_{{\mathsf{x}},k}$, viewed in this way, is not defined on all of
$W_{2}({\mathbb{R}}\times(-1,1)^{k+1}\times{\mathbb{R}}^{k+1})$. We will
define a natural extension of $\mathsf{F}_{{\mathsf{x}},k}$ to all of
$W_{2}({\mathbb{R}}\times(-1,1)^{k+1}\times{\mathbb{R}}^{k+1})$. It will
suffice to control the optimal value of this extended objective over a certain
(non-random) subset of
$W_{2}({\mathbb{R}}\times(-1,1)^{k+1}\times{\mathbb{R}}^{k+1})$.

For any $\mu\in W_{2}({\mathbb{R}}^{2k+3})$, let
$(V,U,\breve{\bm{M}}{},\breve{\bm{G}}{},G_{0},\Xi)\sim\mu$, where
$\breve{\bm{M}}{}=(M_{0},\ldots,M_{k-1})$ and
$\breve{\bm{G}}{}=(G_{1},\ldots,G_{k})$. Define

$G_{\mathsf{AMP}}:=G_{\mathsf{AMP}}\big{(}V,\breve{\bm{M}}{},\breve{\bm{G}}{},\Xi\big{)}:=\lambda^{-1}\breve{\bm{G}}{}^{\top}\mathbb{E}\big{[}\breve{\bm{M}}{}\breve{\bm{M}}{}^{\top}\big{]}^{\dagger}\mathbb{E}\big{[}\breve{\bm{M}}{}V\big{]}+\|{\mathsf{P}}_{\breve{\bm{M}}{}}^{\perp}V\|_{L_{2}}\Xi,$
(43)

where ${\mathsf{P}}_{\breve{\bm{M}}{}}^{\perp}$ is the projector onto the
orthogonal complement of the linear span of $M_{0},\ldots,M_{k-1}$ in $L_{2}$.
Explicitly,
${\mathsf{P}}_{\breve{\bm{M}}{}}^{\perp}V=V-\breve{\bm{M}}{}^{\top}\mathbb{E}\big{[}\breve{\bm{M}}{}\breve{\bm{M}}{}^{\top}\big{]}^{\dagger}\mathbb{E}\big{[}\breve{\bm{M}}{}V\big{]}$.
Note that $G_{\mathsf{AMP}}$ is a linear combination of $G_{1},\ldots,G_{k}$,
and $\Xi$, with coefficients which depend only on $\mu$. Thus, the joint
distribution of $G_{\mathsf{AMP}}$ and $V$ is also only a function of $\mu$.
In particular, the functions

$\displaystyle\mathsf{F}^{(1)}_{\mathsf{FMM},k}(\mu)$
$\displaystyle:=2\lambda\langle
G_{\mathsf{AMP}},V\rangle_{L_{2}}+\lambda^{2}\mathbb{E}[V]^{2}-\mathbb{E}\Big{[}\frac{V^{2}}{1-U^{2}}\Big{]}-\lambda^{2}(1-\|U\|_{L_{2}}^{2})+2\lambda^{2}\langle
V,U\rangle_{L_{2}}^{2},$ (44)
$\displaystyle\mathsf{F}^{(1)}_{\mathsf{AMS},k}(\mu)$
$\displaystyle:=2\lambda\langle
G_{\mathsf{AMP}},V\rangle_{L_{2}}+\lambda^{2}\mathbb{E}[V]^{2}-\mathbb{E}\Big{[}\frac{V^{2}}{1-U^{2}}\Big{]}-\lambda^{2}(1-q_{\infty}),$

are well-defined functions of $\mu$. It is straightforward to check that

$\mathsf{F}_{{\mathsf{x}},k}({\bm{v}},{\bm{u}};{\bm{M}},{\bm{G}},{\bm{\xi}}):=\mathsf{F}^{(1)}_{{\mathsf{x}},k}\big{(}\widehat{\mu}{}_{\sqrt{n}{\bm{v}},{\bm{u}},{\bm{M}},{\bm{G}},{\bm{g}}^{0},{\bm{\xi}}}\big{)},$
(45)

so that, indeed, $\mathsf{F}^{(1)}_{{\mathsf{x}},k}$ can be viewed as an
extension of $\mathsf{F}_{{\mathsf{x}},k}$. The careful reader may wonder why
we include the empirical distribution of ${\bm{g}}^{0}$ in the argument to
$\mathsf{F}_{{\mathsf{x}},k}^{(1)}$, because the $\mathsf{F}_{{\mathsf{x}},k}$
does not depend on ${\bm{g}}^{0}$. This will become apparent in the
approximations we make in the next section, which will make use of
${\bm{g}}^{0}$.

We will give an upper bound on Eq. (40) in terms of the supremum of the
objective $\mathsf{F}^{(1)}_{{\mathsf{x}},k}$ taken over a particular subset
of the Wasserstein space
$W_{2}({\mathbb{R}}\times(-1,1)^{k+1}\times{\mathbb{R}}^{k+1})$. In
particular, let

$\mathsf{SE}_{{\mathsf{x}},k}:=\mathsf{Law}(\breve{\bm{M}}{},\breve{\bm{G}}{},G_{0},\Xi)\quad\text{where}\quad\begin{cases}&\breve{\bm{G}}{}\sim{\sf
N}(0,\bm{K}_{\leq k})\;\;\text{independent
of}\;\;\Xi,G_{0}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}{\sf N}(0,1),\\\
&M_{s}=\tanh(\gamma_{s}+\mathbf{1}_{s>0}G_{s}+\chi_{{\mathsf{x}}}\sqrt{\gamma_{0}}G_{0}),\;\;\;\;0\leq
s\leq k-1.\end{cases}$ (46)

In particular, $\mathsf{SE}_{{\mathsf{x}},k}$ is the AMP state evolution up to
iteration $k$, as described in Proposition 3, augmented by the independent
Gaussian noise $\Xi$. The set over which we optimize is

$\displaystyle{\mathcal{S}}^{(1)}_{{\mathsf{x}},k}(\epsilon):=\Big{\\{}\mathsf{Law}(V,U,\breve{\bm{M}}{},\breve{\bm{G}}{},G_{0},\Xi)\Bigm{|}$
$\displaystyle\|V\|_{L_{2}}=1,\,\mathbb{P}(|U|<1)=1,\,\|U-M_{k-1}\|_{L_{2}}\leq\epsilon,\,(\breve{\bm{M}}{},\breve{\bm{G}}{},G_{0},\Xi)\sim\mathsf{SE}_{{\mathsf{x}},k}\Big{\\}}.$
(47)

We have the following lemma.

######  Lemma 1.

For any fixed $\epsilon>0$ and $0<k<\infty$,

$\displaystyle\limsup_{\epsilon\rightarrow
0}\;\limsup_{k\rightarrow\infty}\;\operatorname*{p-lim\,sup}_{n\rightarrow\infty}\sup_{\begin{subarray}{c}\|{\bm{v}}\|=1\\\
\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\end{subarray}}\mathsf{F}_{{\mathsf{x}},k}({\bm{v}},{\bm{u}};{\bm{M}},{\bm{G}},{\bm{\xi}})\leq\limsup_{\epsilon\rightarrow
0}\;\limsup_{k\rightarrow\infty}\;\sup_{\mu\in{\mathcal{S}}^{(1)}_{{\mathsf{x}},k}(\epsilon)}\mathsf{F}^{(1)}_{{\mathsf{x}},k}(\mu).$
(48)

We prove Lemma 1 in Appendix B.2.

###  4.2 Dimensionality reduction of Wasserstein space

The objective $\mathsf{F}_{{\mathsf{x}},k}^{(1)}$ depends on a distribution on
$(2k+4)$-dimensional space. In particular, the complexity of studying the
right-hand side of Eq. (48) appears, at first glance, to grow with $k$. In
this section, we show that for large $k$, we may reduce the problem to
studying an optimization problem over distributions on a low-dimensional
space.

Consider $(V,U,\breve{\bm{M}}{},\breve{\bm{G}}{},G_{0},\Xi)\sim\mu^{(1)}$ for
$\mu^{(1)}\in{\mathcal{S}}^{(1)}_{{\mathsf{x}},k}(\epsilon)$, and define
$G_{\mathsf{AMP}}$ as in Eq. (43). Note that $G_{\mathsf{AMP}}$, being a
linear combination of jointly Gaussian random variables, is itself Gaussian.
Because, by Proposition 3,
$\mathbb{E}\big{[}\breve{\bm{G}}{}\breve{\bm{G}}{}^{\top}\big{]}=\lambda^{2}\mathbb{E}\big{[}\breve{\bm{M}}{}\breve{\bm{M}}{}^{\top}\big{]}=\bm{K}_{\leq
k}$, we get

$\displaystyle\mathbb{E}[G_{\mathsf{AMP}}^{2}]$
$\displaystyle=\mathbb{E}\big{[}V\breve{\bm{M}}{}^{\top}\big{]}^{\top}\mathbb{E}\big{[}\breve{\bm{M}}{}\breve{\bm{M}}{}^{\top}\big{]}^{-1}\mathbb{E}\big{[}\breve{\bm{M}}{}V\big{]}+\big{\|}{\mathsf{P}}_{\breve{\bm{M}}{}}^{\perp}V\big{\|}_{L_{2}}^{2}=\big{\|}{\mathsf{P}}_{\breve{\bm{M}}{}}V\big{\|}_{L_{2}}^{2}+\big{\|}{\mathsf{P}}_{\breve{\bm{M}}{}}^{\perp}V\big{\|}_{L_{2}}^{2}=\mathbb{E}[V^{2}]=1.$
(49)

Moreover,

$\langle
G_{k},G_{\mathsf{AMP}}\rangle_{L_{2}}=\lambda\bm{K}_{k,\,\cdot\,}\bm{K}_{\leq
k}^{-1}\mathbb{E}[\breve{\bm{M}}{}V]=\lambda{\bm{e}}_{k}^{\top}\mathbb{E}[\breve{\bm{M}}{}V]=\lambda\langle
M_{k},V\rangle_{L_{2}},$ (50)

where $\bm{K}_{k,\,\cdot\,}$ denotes the $k^{\text{th}}$ row of $\bm{K}_{\leq
k}$, and ${\bm{e}}_{k}$ is the $k^{\text{th}}$ standard basis vector. Because
$\|G_{k}\|_{L_{2}}=\lambda\|M_{k}\|_{L_{2}}$ (see Proposition 3), we may write

$G_{\mathsf{AMP}}=\frac{\langle
M_{k},V\rangle_{L_{2}}}{\|M_{k}\|_{L_{2}}}\frac{G_{k}}{\|G_{k}\|_{L_{2}}}+\|{\mathsf{P}}_{M_{k}}^{\perp}V\|_{L_{2}}\Xi^{(1)},$
(51)

for some Gaussian $\Xi^{(1)}\sim{\sf N}(0,1)$ independent of $G_{k}$. Define
$M_{k}=\tanh(q_{k}+G_{k}+\chi_{{\mathsf{x}}}\sqrt{\gamma_{0}}G_{0})$.222This
is where it is useful that we included the empirical distribution of
${\bm{g}}^{0}$ in the argument to $\mathsf{F}_{{\mathsf{x}},k}^{(1)}$. By
Proposition 3,

$\|M_{k}-M_{k-1}\|_{L_{2}}=\lambda^{-1}\sqrt{K_{k,k}-2K_{k,k-1}+K_{k-1,k-1}}=\lambda^{-1}\sqrt{q_{k}-q_{k-1}}\leq\epsilon(k),$
(52)

where $\epsilon(k)>0$ is a function, depending only on $\lambda,\gamma_{0}$,
satisfying $\epsilon(k)\rightarrow 0$ as $k\rightarrow\infty$. Thus, under
$\mu^{(1)}$ (recalling
$\mu^{(1)}\in{\mathcal{S}}_{{\mathsf{x}},k}^{(1)}(\epsilon)$), we have
$\|U-M_{k}\|_{L_{2}}\leq\epsilon+\epsilon(k)$. Let $\mu^{(2)}$ be the
distribution of $(U,V,M_{k},G_{k},G_{0},\Xi^{(1)})$ under $\mu^{(1)}$. By Eq.
(44), for ${\mathsf{x}}=\mathsf{FMM}$ we may write

$\displaystyle\mathsf{F}^{(1)}_{\mathsf{FMM},k}(\mu^{(1)})=2\lambda\Big{\langle}\frac{\langle
M_{k},V\rangle_{L_{2}}}{\|M_{k}\|_{L_{2}}}\frac{G_{k}}{\|G_{k}\|_{L_{2}}}+\|{\mathsf{P}}_{M_{k}}^{\perp}V\|_{L_{2}}\Xi^{(1)},\,V\Big{\rangle}+\lambda^{2}\mathbb{E}[V]^{2}-\mathbb{E}\Big{[}\frac{V^{2}}{1-U^{2}}\Big{]}-\lambda^{2}(1-\|U\|_{L_{2}}^{2})+2\lambda^{2}\langle
V,U\rangle_{L_{2}}^{2}$ (53) $\displaystyle\quad\leq
2\lambda\Big{\langle}\frac{\langle
M_{k},V\rangle_{L_{2}}}{\|M_{k}\|_{L_{2}}}\frac{G_{k}}{\|G_{k}\|_{L_{2}}}+\|{\mathsf{P}}_{M_{k}}^{\perp}V\|_{L_{2}}\Xi^{(1)},\,V\Big{\rangle}$
$\displaystyle\qquad\qquad\qquad\qquad+\lambda^{2}\mathbb{E}[V]^{2}-\mathbb{E}\Big{[}\frac{V^{2}}{1-U^{2}}\Big{]}-\lambda^{2}(1-\|M_{k}\|_{L_{2}}^{2})+2\lambda^{2}\langle
V,M_{k}\rangle_{L_{2}}^{2}+6\lambda^{2}(\epsilon+\epsilon(k))$
$\displaystyle\quad=:\mathsf{F}_{\mathsf{FMM}}^{(2)}(\mu^{(2)})+6\lambda^{2}(\epsilon+\epsilon(k)),$

where in the inequality we have used that $U\mapsto\|U\|_{L_{2}}^{2}$ and
$U\mapsto\langle V,U\rangle_{L_{2}}^{2}$ are $2$-Lipschitz for
$\|U\|_{L_{2}}\leq 1$ and $\|V\|_{L_{2}}\leq 1$. The final equality is taken
as the definition of $\mathsf{F}_{\mathsf{FMM}}^{(2)}$. Note the
$\mathsf{F}_{\mathsf{FMM}}^{(2)}$ does not, as a function, depend on $k$: the
$k$-dependence occurs only through the distribution of the random variables
$U,V,M_{k},G_{k},\Xi^{(1)}$. Thus, unlike for
$\mathsf{F}_{\mathsf{FMM},k}^{(1)}$, $k$ does not appear in the subscript
$\mathsf{F}_{\mathsf{FMM}}^{(2)}$. Likewise, for ${\mathsf{x}}=\mathsf{AMS}$,
we may write

$\displaystyle\mathsf{F}^{(1)}_{\mathsf{AMS},k}(\mu^{(1)})$
$\displaystyle=2\lambda\Big{\langle}\frac{\langle
M_{k},V\rangle_{L_{2}}}{\|M_{k}\|_{L_{2}}}\frac{G_{k}}{\|G_{k}\|_{L_{2}}}+\|{\mathsf{P}}_{M_{k}}^{\perp}V\|_{L_{2}}\Xi^{(1)},\,V\Big{\rangle}+\lambda^{2}\mathbb{E}[V]^{2}-\mathbb{E}\Big{[}\frac{V^{2}}{1-U^{2}}\Big{]}-\lambda^{2}(1-q_{\infty})$
(54) $\displaystyle=:\mathsf{F}_{\mathsf{AMS}}^{(2)}(\mu^{(2)}).$

In this case, there is no approximation error. For both
${\mathsf{x}}=\mathsf{FMM}$ and ${\mathsf{x}}=\mathsf{AMS}$, we have related
the objective $\mathsf{F}_{{\mathsf{x}},k}^{(1)}$, which is a function of
distributions on a $(2k+4)$-dimensional space, to the objective
$\mathsf{F}_{{\mathsf{x}}}^{(2)}$, which is a function of distributions on a
$6$-dimensional space.

Because, as we have argued above,
$\mu^{(1)}\in{\mathcal{S}}_{{\mathsf{x}},k}^{(1)}(\epsilon)$ implies
$\|U-M_{k}\|_{L_{2}}\leq\epsilon+\epsilon(k)$, we have that
$\mu^{(1)}\in{\mathcal{S}}^{(1)}_{{\mathsf{x}},k}(\epsilon)$ implies
$\mu^{(2)}\in{\mathcal{S}}^{(2)}_{{\mathsf{x}},k}(\epsilon+\epsilon(k))$,
where

$\displaystyle{\mathcal{S}}^{(2)}_{{\mathsf{x}},k}(\epsilon):=\Big{\\{}\mathsf{Law}(V,U,M_{k},G_{k},G_{0},\Xi)\bigm{|}$
$\displaystyle\|V\|_{L_{2}}=1,\;\;\mathbb{P}(|U|>1)=0,\;\;\|U-M_{k}\|_{L_{2}}\leq\epsilon,\,$
(55) $\displaystyle G_{k}\sim{\sf N}(0,K_{kk})\text{ independent of
}G_{0},\Xi\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}{\sf N}(0,1),$
$\displaystyle
M_{k}=\tanh(\gamma_{k}+G_{k}+\chi_{{\mathsf{x}}}\sqrt{\gamma_{0}}G_{0})\Big{\\}},$

In particular, we have shown that

$\limsup_{\epsilon\rightarrow
0}\;\limsup_{k\rightarrow\infty}\;\sup_{\mu\in{\mathcal{S}}^{(1)}_{{\mathsf{x}},k}(\epsilon)}\mathsf{F}^{(1)}_{{\mathsf{x}},k}(\mu)\leq\limsup_{\epsilon\rightarrow
0}\;\limsup_{k\rightarrow\infty}\;\sup_{\mu\in{\mathcal{S}}^{(2)}_{{\mathsf{x}},k}(\epsilon+\epsilon(k))}\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu).$
(56)

###  4.3 Reduction to analysis at state evolution fixed point

Now, we analyze what happens when $k\rightarrow\infty$.

Consider $\mu^{(k)}\in S^{(2)}_{{\mathsf{x}},k}(\epsilon+\epsilon(k))$, and
let $(V,U,M_{k},G_{k},G_{0},\Xi)\sim\mu^{(k)}$. Assume also $\|V\|_{L_{2}}=1$.
Let $K_{\infty}=\gamma_{\infty}-\chi_{{\mathsf{x}}}\gamma_{0}$,
$G_{\infty}=\sqrt{K_{\infty}/K_{kk}}\,G_{k}$, and
$M_{\infty}=\tanh(\gamma_{\infty}+G_{\infty}+\chi_{{\mathsf{x}}}\sqrt{\gamma_{0}}G_{0})$.
Let $\epsilon(k)>0$ denote a quantity satisfying $\epsilon(k)\rightarrow 0$ as
$k\rightarrow\infty$ and which may change at each appearance. Because
$\gamma_{k}\rightarrow\gamma_{\infty}>0$ (see Proposition 3), we have that
$\|G_{k}-G_{\infty}\|_{L_{2}}\leq\epsilon(k)$,
$\|M_{k}-M_{\infty}\|_{L_{2}}\leq\epsilon(k)$, and $\|M_{\infty}\|_{L_{2}}>0$,
whence, using $\|V\|_{L_{2}}=1$,

$\Big{\|}\Big{(}\frac{\langle
M_{k},V\rangle_{L_{2}}}{\|M_{k}\|_{L_{2}}}\frac{G_{k}}{\|G_{k}\|_{L_{2}}}+\|{\mathsf{P}}_{M_{k}}^{\perp}V\|_{L_{2}}\Xi\Big{)}-\Big{(}\frac{\mathbb{E}[M_{\infty}V]}{\|M_{\infty}\|_{L_{2}}}\frac{G_{\infty}}{\|G_{\infty}\|_{L_{2}}}+\|{\mathsf{P}}_{M_{\infty}}^{\perp}V\|_{L_{2}}\Xi\Big{)}\Big{\|}_{L_{2}}\leq\epsilon(k).$
(57)

Thus, if we let $\mu^{(\infty)}$ be the joint distribution of
$(V,U,M_{\infty},G_{\infty},G_{0},\Xi)$, we get
$\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu^{(\infty)})\leq\mathsf{F}^{(2)}(\mu^{(\infty)})+\epsilon(k)$.
Now, define

$\displaystyle{\mathcal{S}}^{(2)}_{{\mathsf{x}},\infty}(\epsilon):=\Big{\\{}\mathsf{Law}(V,U,M_{k},G_{k},W,\Xi)\bigm{|}$
$\displaystyle\|V\|_{L_{2}}=1,\;\;\mathbb{P}(|U|>1)=0,\;\;\|U-M_{\infty}\|_{L_{2}}\leq\epsilon,\,$
(58) $\displaystyle G_{\infty}\sim{\sf N}(0,\lambda^{2}q_{\infty})\text{
independent of }G_{0},\Xi\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}{\sf
N}(0,1),\,$ $\displaystyle
M_{\infty}=\tanh(\gamma_{\infty}+G_{\infty}+\chi_{{\mathsf{x}}}\sqrt{\gamma_{0}}G_{0})\Big{\\}}.$

Using that $K_{\infty}=\lambda^{2}q_{\infty}$ (see Eq. (28) and the definition
of $\bm{K}_{\leq k}$) and the discussion above, we that
$\mu^{(k)}\in{\mathcal{S}}_{{\mathsf{x}},k}^{(2)}(\epsilon+\epsilon(k))$
implies
$\mu^{(\infty)}\in{\mathcal{S}}_{{\mathsf{x}},\infty}^{(2)}(\epsilon+\epsilon(k))$.
(Recall, the $\epsilon(k)$ appearing in the two expressions may be different).
We conclude

$\sup_{\mu\in{\mathcal{S}}^{(2)}_{{\mathsf{x}},k}(\epsilon+\epsilon(k))}\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu)\leq\sup_{\mu\in{\mathcal{S}}^{(2)}_{{\mathsf{x}},\infty}(\epsilon+\epsilon(k))}\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu)+\epsilon(k).$
(59)

Because
${\mathcal{S}}_{{\mathsf{x}},\infty}^{(2)}(\epsilon)\subset{\mathcal{S}}_{{\mathsf{x}},\infty}^{(2)}(\epsilon^{\prime})$
for $\epsilon<\epsilon^{\prime}$, we conclude

$\limsup_{\epsilon\rightarrow
0}\;\limsup_{k\rightarrow\infty}\;\sup_{\mu\in{\mathcal{S}}^{(2)}_{{\mathsf{x}},k}(\epsilon+\epsilon(k))}\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu)\leq\limsup_{\epsilon\rightarrow
0}\sup_{\mu\in{\mathcal{S}}^{(2)}_{{\mathsf{x}},\infty}(\epsilon)}\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu).$
(60)

Combining Eqs. (56), and (60), and (48),

$\limsup_{\epsilon\rightarrow
0}\;\limsup_{k\rightarrow\infty}\;\operatorname*{p-lim\,sup}_{n\rightarrow\infty}\sup_{\begin{subarray}{c}\|{\bm{v}}\|=1\\\
\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\end{subarray}}\mathsf{F}^{(1)}_{{\mathsf{x}},k}({\bm{v}},{\bm{u}};{\bm{M}},{\bm{G}},{\bm{\xi}})\leq\limsup_{\epsilon\rightarrow
0}\sup_{\mu\in{\mathcal{S}}^{(2)}_{{\mathsf{x}},\infty}(\epsilon)}\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu).$
(61)

It now remains to bound the right-hand side of Eq. (61).

###  4.4 Analysis of $\mathsf{F}_{{\mathsf{x}}}^{(2)}$

For $\mu^{(\infty)}\in{\mathcal{S}}_{\mathsf{FMM},\infty}^{(2)}(\epsilon)$, we
have $\|M_{\infty}\|_{L_{2}}^{2}=q_{\infty}$, whence the term
$\lambda^{2}(1-\|M_{\infty}\|_{L_{2}}^{2})$ which appears in the definition of
$\mathsf{F}_{\mathsf{FMM}}^{(2)}(\mu^{(\infty)})$ (see Eq. (53)) is equal to
$\lambda^{2}(1-q_{\infty})$. Thus, we may write in a unified way that for
$\mu^{(\infty)}\in{\mathcal{S}}_{{\mathsf{x}},\infty}^{(2)}$, we have

$\displaystyle\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu^{\infty})$
$\displaystyle=2\lambda\Big{\langle}\frac{\langle
M_{\infty},V\rangle_{L_{2}}}{\|M_{\infty}\|_{L_{2}}}\frac{G_{\infty}}{\|G_{\infty}\|_{L_{2}}}+\|{\mathsf{P}}_{M_{\infty}}^{\perp}V\|_{L_{2}}\Xi,\,V\Big{\rangle}$
(62)
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+\lambda^{2}\mathbb{E}[V]^{2}-\mathbb{E}\Big{[}\frac{V^{2}}{1-U^{2}}\Big{]}-\lambda^{2}(1-q_{\infty})+(1-\chi_{{\mathsf{x}}})2\lambda^{2}\langle
V,M_{\infty}\rangle_{L_{2}}^{2}.$

This representation allows to analyze the cases ${\mathsf{x}}=\mathsf{FMM}$
and ${\mathsf{x}}=\mathsf{AMS}$ simultaneously.

For $\mu^{(\infty)}\in{\mathcal{S}}_{{\mathsf{x}},\infty}^{(2)}(\epsilon)$,
denote

$\rho=\frac{\langle M_{\infty},V\rangle}{\|M_{\infty}\|_{L_{2}}},\qquad
u=\mathbb{E}[V].$ (63)

Introducing dual variables
$\alpha_{\rho},\alpha_{u},\alpha_{v}\in{\mathbb{R}}$, we have

$\displaystyle\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu^{(\infty)})$
$\displaystyle=2\lambda\Big{\langle}\rho\frac{G_{\infty}}{\|G_{\infty}\|_{L_{2}}}+\sqrt{1-\rho^{2}}\,\Xi,\,V\Big{\rangle}_{L_{2}}+\lambda^{2}u^{2}-\mathbb{E}\Big{[}\frac{V^{2}}{1-U^{2}}\Big{]}-\lambda^{2}(1-q_{\infty})+(1-\chi_{{\mathsf{x}}})2\lambda^{2}q_{\infty}\rho^{2}$
(64)
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+\alpha_{\rho}\Big{(}\frac{\langle
M_{\infty},V\rangle}{\|M_{\infty}\|_{L_{2}}}-\rho\Big{)}+\alpha_{u}\Big{(}\mathbb{E}[V]-u\Big{)}+\alpha_{v}\Big{(}\|V\|_{L_{2}}^{2}-1\Big{)}$
$\displaystyle\leq\lambda^{2}u^{2}-\lambda^{2}(1-q_{\infty})+(1-\chi_{{\mathsf{x}}})2\lambda^{2}q_{\infty}\rho^{2}-\alpha_{\rho}\rho-\alpha_{u}u-\alpha_{v}+\mathbb{E}\Big{[}\Theta(G_{\infty},M_{\infty},\Xi,U)\Big{]},$

where $\Theta$ is defined as

$\Theta(g,m,\xi,u):=\sup_{v\in{\mathbb{R}}}\Big{\\{}2\lambda\Big{(}\frac{\rho}{\lambda
q_{\infty}^{1/2}}g+\sqrt{1-\rho^{2}}\,\xi\Big{)}v-\frac{v^{2}}{1-u^{2}}+\frac{\alpha_{\rho}}{q_{\infty}^{1/2}}mv+\alpha_{u}v+\alpha_{v}v^{2}\Big{\\}}.$
(65)

We have used here that $\|G_{\infty}\|_{L_{2}}^{2}=\lambda^{2}q_{\infty}$ and
$\|M_{\infty}\|_{L_{2}}^{2}=q_{\infty}$.

Note that $\Theta(g,m,\xi,u)$ also depends on
$\rho,\alpha_{\rho},\alpha_{u},\alpha_{v}$, but we have left this dependence
implicit to lighten notation. If $\alpha_{v}<1$, then the objective in the
definition of $\Theta$ is strictly concave, whence the supremum is achieved at

$v=\frac{2\lambda\Big{(}\frac{\rho}{\lambda
q_{\infty}^{1/2}}g+\sqrt{1-\rho^{2}}\,\xi\Big{)}+\frac{\alpha_{\rho}m}{q_{\infty}^{1/2}}+\alpha_{u}}{2\Big{(}\frac{1}{1-u^{2}}-\alpha_{v}\Big{)}},$
(66)

which gives the explicit expression

$\Theta(g,m,\xi,u)=\frac{\Big{(}2\lambda\Big{(}\frac{\rho}{\lambda
q_{\infty}^{1/2}}g+\sqrt{1-\rho^{2}}\,\xi\Big{)}+\frac{\alpha_{\rho}m}{q_{\infty}^{1/2}}+\alpha_{u}\Big{)}^{2}}{4\Big{(}\frac{1}{1-u^{2}}-\alpha_{v}\Big{)}}.$
(67)

Note that $u\rightarrow 1/(1/(1-u^{2})-\alpha_{v})$ is Lipschitz in $u$, with
Lipschitz constant bounded away from $\infty$ for $\alpha_{v}$ bounded away
from 1. Thus, almost surely

$\big{|}\Theta(G_{\infty},M_{\infty},\Xi,U)-\Theta(G_{\infty},M_{\infty},\Xi,M_{\infty})\big{|}\leq
L_{\alpha_{v}}\Big{(}2\lambda\Big{(}\frac{\rho}{\lambda
q_{\infty}^{1/2}}G_{\infty}+\sqrt{1-\rho^{2}}\,\Xi\Big{)}+\frac{\alpha_{\rho}M_{\infty}}{q_{\infty}^{1/2}}+\alpha_{u}\Big{)}^{2}|U-M_{\infty}|,$
(68)

for some $L_{\alpha_{v}}<\infty$ when $\alpha_{v}<1$. Because
$G_{\infty}/(\lambda q_{\infty}^{1/2})$ is standard Gaussian and
$M_{\infty}\in[-1,1]$ (and so both have infinitely many moments), we combine
the previous display with Eq. (64) and Cauchy-Schwartz to get that for any
compact set $K\in{\mathbb{R}}^{2}$ and any fixed $\alpha_{v}$,

$\displaystyle\mathsf{F}^{(2)}(\mu^{(\infty)})\leq\min_{(\alpha_{\rho},\alpha_{u})\in
K}\Big{\\{}\lambda^{2}u^{2}$
$\displaystyle-\lambda^{2}(1-q_{\infty})+(1-\chi_{{\mathsf{x}}})2\lambda^{2}q_{\infty}\rho^{2}$
(69)
$\displaystyle-\alpha_{\rho}\rho-\alpha_{u}u-\alpha_{v}+\mathbb{E}\Big{[}\Theta(G_{\infty},M_{\infty},\Xi,M_{\infty})\Big{]}\Big{\\}}+C\epsilon,$

where $C$ depends on $K$ and $\alpha_{v}$ (but not on $\rho,u,\epsilon$), and
we remind the reader that $\mu^{(\infty)}$ satisfies Eq.(63). In particular,
for any compact set $K\in{\mathbb{R}}^{2}$,

$\displaystyle\limsup_{\epsilon\rightarrow
0}\sup_{\mu\in{\mathcal{S}}^{(2)}_{{\mathsf{x}},\infty}(\epsilon)}\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu)\leq\sup_{\rho,u\in[-1,1]}\min_{(\alpha_{\rho},\alpha_{u})\in
K}\mathsf{L}_{{\mathsf{x}}}(\rho,u;\alpha_{\rho},\alpha_{u},\alpha_{v}),$ (70)

where

$\mathsf{L}_{{\mathsf{x}}}(\rho,u;\alpha_{\rho},\alpha_{u},\alpha_{v}):=\lambda^{2}u^{2}-\lambda^{2}(1-q_{\infty})+(1-\chi_{{\mathsf{x}}})2\lambda^{2}q_{\infty}\rho^{2}-\alpha_{\rho}\rho-\alpha_{u}u-\alpha_{v}+\mathbb{E}\Big{[}\Theta(G_{\infty},M_{\infty},\Xi,M_{\infty})\Big{]},$
(71)

and we remind the reader that $\Theta$ depends implicitly on
$\rho,\alpha_{\rho},\alpha_{u},\alpha_{v}$.

We have now reduced the problem to upper-bounding a certain max-min problem of
five variables similar to that derived by Lemma 4.9(a) of [CFM21]. The
remainder of our argument is nearly equivalent to theirs, and in particular,
their proof of [CFM21, Lemma 4.9(b)]. The primary difference between our
argument and theirs has occurred in the proof up to this point, and in
particular, in how this objective was derived: [CFM21] conditions on
stationarity of the TAP free energy at a point (i.e.,
$\nabla{\mathcal{F}}({\bm{m}})=0$). Because the TAP free energy has many
stationary points, there is some subtlety in arguing that the conditional
distribution which results from conditioning on
$\nabla{\mathcal{F}}({\bm{m}})=0$ for a ${\bm{m}}$ chosen _a priori_ reflects
the behavior of the landscape around one of the stationary points of
${\mathcal{F}}$ chosen _a posteriori_. To make this connection, [CFM21] must
invoke sophisticated arguments involving the Kac-Rice formula to control the
number of such points. We condition on arguably a more complicated event— a
full sequence of AMP iterates —but because there is only one sequence of AMP
iterates for each realization of ${\bm{W}}$, we are able to avoid the
difficulties that demanded the use of the Kac-Rice formula.

To analyze this max-min problem, we write

$\mathbb{E}\Big{[}\Theta(G_{\infty},M_{\infty},\Xi,M_{\infty})\Big{]}=\mathbb{E}\left[\frac{4\lambda^{2}(1-\rho^{2})+\Big{(}\frac{2\rho}{q_{\infty}^{1/2}}G_{\infty}+\frac{\alpha_{\rho}M_{\infty}}{q_{\infty}^{1/2}}+\alpha_{u}\Big{)}^{2}}{4\Big{(}\frac{1}{1-M_{\infty}^{2}}-\alpha_{v}\Big{)}}\right],$
(72)

so that

$\mathsf{L}_{{\mathsf{x}}}(\rho,u;\alpha_{\rho},\alpha_{u},\alpha_{v})=(\rho,u,\alpha_{\rho},\alpha_{u})^{\top}{\bm{A}}^{(\alpha_{v})}(\rho,u,\alpha_{\rho},\alpha_{u})^{\top}-\lambda^{2}(1-q_{\infty})-\alpha_{v}+\lambda^{2}\mathbb{E}\left[\Big{(}\frac{1}{1-M_{\infty}^{2}}-\alpha_{v}\Big{)}^{-1}\right],$
(73)

where

${\bm{A}}_{{\mathsf{x}}}^{(\alpha_{v})}=\begin{pmatrix}{\bm{A}}^{(\alpha_{v})}_{{\mathsf{x}},11}&{\bm{A}}^{(\alpha_{v})}_{12}\\\\[5.0pt]
{\bm{A}}^{(\alpha_{v})}_{21}&{\bm{A}}^{(\alpha_{v})}_{22}\end{pmatrix},$ (74)

where

$\displaystyle{\bm{A}}^{(\alpha_{v})}_{{\mathsf{x}},11}$
$\displaystyle=\begin{pmatrix}(1-\chi_{{\mathsf{x}}})2\lambda^{2}q_{\infty}+\mathbb{E}\Big{[}(G_{\infty}^{2}/q_{\infty}-\lambda^{2})\left(\frac{1}{1-M_{\infty}^{2}}-\alpha_{v}\right)^{-1}\Big{]}&0\\\\[5.0pt]
0&\lambda^{2}\end{pmatrix},$ (75)
$\displaystyle{\bm{A}}^{(\alpha_{v})}_{12}={\bm{A}}^{(\alpha_{v})\top}_{21}$
$\displaystyle=\begin{pmatrix}-\frac{1}{2}+\frac{1}{2q_{\infty}}\mathbb{E}\Big{[}G_{\infty}M_{\infty}\Big{(}\frac{1}{1-M_{\infty}^{2}}-\alpha_{v}\Big{)}^{-1}\Big{]}&\frac{1}{2q_{\infty}^{1/2}}\mathbb{E}\Big{[}G_{\infty}\Big{(}\frac{1}{1-M_{\infty}^{2}}-\alpha_{v}\Big{)}^{-1}\Big{]}\\\\[5.0pt]
0&-\frac{1}{2}\end{pmatrix},$ $\displaystyle{\bm{A}}^{(\alpha_{v})}_{22}$
$\displaystyle=\frac{1}{4}\begin{pmatrix}\frac{1}{q_{\infty}}\mathbb{E}\Big{[}M_{\infty}^{2}\Big{(}\frac{1}{1-M_{\infty}^{2}}-\alpha_{v}\Big{)}^{-1}\Big{]}&\frac{1}{q_{\infty}^{1/2}}\mathbb{E}\Big{[}M_{\infty}\Big{(}\frac{1}{1-M_{\infty}^{2}}-\alpha_{v}\Big{)}^{-1}\Big{]}\\\\[5.0pt]
\frac{1}{q_{\infty}^{1/2}}\mathbb{E}\Big{[}M_{\infty}\Big{(}\frac{1}{1-M_{\infty}^{2}}-\alpha_{v}\Big{)}^{-1}\Big{]}&\mathbb{E}\Big{[}\Big{(}\frac{1}{1-M_{\infty}^{2}}-\alpha_{v}\Big{)}^{-1}\Big{]}\end{pmatrix}.$

Letting $b_{\infty}=\mathbb{E}[M_{\infty}^{3}]=\mathbb{E}[M_{\infty}^{4}]$,
and recalling $q_{\infty}=\mathbb{E}[M_{\infty}]=\mathbb{E}[M_{\infty}^{2}]$
(see Proposition 3(v)), we may compute these matrices at $\alpha_{v}=0$:

$\displaystyle{\bm{A}}^{(0)}_{{\mathsf{x}},11}$
$\displaystyle=\begin{pmatrix}(1-\chi_{{\mathsf{x}}})2\lambda^{2}q_{\infty}-\lambda^{2}(1-q_{\infty})+\frac{1}{q_{\infty}}\mathbb{E}\left[G_{\infty}^{2}\left(1-M_{\infty}^{2}\right)\right]&0\\\\[5.0pt]
0&\lambda^{2}\end{pmatrix},$ (76)
$\displaystyle{\bm{A}}^{(0)}_{12}={\bm{A}}^{(0)\top}_{21}$
$\displaystyle=\begin{pmatrix}-\frac{1}{2}+\frac{1}{2q_{\infty}}\mathbb{E}[G_{\infty}M_{\infty}(1-M_{\infty}^{2})]&-\frac{1}{2q_{\infty}^{1/2}}\mathbb{E}[G_{\infty}M_{\infty}^{2}]\\\\[5.0pt]
0&-\frac{1}{2}\end{pmatrix},$ $\displaystyle{\bm{A}}^{(0)}_{22}$
$\displaystyle=\frac{1}{4}\begin{pmatrix}1-b_{\infty}/q_{\infty}&q_{\infty}^{1/2}(1-b_{\infty}/q_{\infty})\\\\[5.0pt]
q_{\infty}^{1/2}(1-b_{\infty}/q_{\infty})&1-q_{\infty}\end{pmatrix}.$

Note that

${\bm{A}}_{22}^{(0)}=\frac{1}{4}\mathbb{E}\left[(1-M_{\infty}^{2})\begin{pmatrix}M_{\infty}/q_{\infty}^{1/2}\\\\[5.0pt]
1\end{pmatrix}\begin{pmatrix}M_{\infty}/q_{\infty}^{1/2}\\\\[5.0pt]
1\end{pmatrix}^{\top}\right]\succ 0.$ (77)

We will further show that
${\bm{A}}_{11}^{(0)}-{\bm{A}}_{12}^{(0)}({\bm{A}}_{22}^{(0)})^{-1}{\bm{A}}_{21}^{(0)}\prec
0$. Using that $G_{\infty}\sim{\sf N}(0,\lambda^{2}q_{\infty})$,
$M_{\infty}=\tanh(\gamma_{\infty}+G_{\infty}+\chi\sqrt{\gamma_{0}}W)$ and that
$\frac{{\rm d}}{{\rm d}y}\tanh(y)=1-\tanh^{2}(y)$, Gaussian integration by
parts gives

$\displaystyle\mathbb{E}[G_{\infty}M_{\infty}]$
$\displaystyle=\lambda^{2}q_{\infty}\mathbb{E}[1-M_{\infty}^{2}]=\lambda^{2}q_{\infty}(1-q_{\infty}),$
(78) $\displaystyle\mathbb{E}[G_{\infty}M_{\infty}^{2}]$
$\displaystyle=2\lambda^{2}q_{\infty}\mathbb{E}[M_{\infty}(1-M_{\infty}^{2})]=2\lambda^{2}q_{\infty}(q_{\infty}-b_{\infty}),$
$\displaystyle\mathbb{E}[G_{\infty}M_{\infty}^{3}]$
$\displaystyle=3\lambda^{2}q_{\infty}\mathbb{E}[M_{\infty}^{2}(1-M_{\infty}^{2})]=3\lambda^{2}q_{\infty}(q_{\infty}-b_{\infty}),$
$\displaystyle\mathbb{E}[G_{\infty}^{2}(1-M_{\infty}^{2})]$
$\displaystyle=\lambda^{2}q_{\infty}-\lambda^{2}q_{\infty}\mathbb{E}[M_{\infty}^{2}]-2\lambda^{2}q_{\infty}\mathbb{E}[G_{\infty}M_{\infty}(1-M_{\infty}^{2})]$
$\displaystyle=\lambda^{2}q_{\infty}-\lambda^{2}q_{\infty}^{2}-2\lambda^{4}q_{\infty}^{2}(1-4q_{\infty}+3b_{\infty}).$

Thus,

$\displaystyle{\bm{A}}^{(0)}_{{\mathsf{x}},11}$
$\displaystyle=\begin{pmatrix}(1-\chi_{{\mathsf{x}}})2\lambda^{2}q_{\infty}-2\lambda^{4}q_{\infty}(1-4q_{\infty}+3b_{\infty})&0\\\\[5.0pt]
0&\lambda^{2}\end{pmatrix},$ (79) $\displaystyle{\bm{A}}_{12}^{(0)}$
$\displaystyle=\frac{1}{2}\begin{pmatrix}-1+\lambda^{2}(1-4q_{\infty}+3b_{\infty})&-2\lambda^{2}q_{\infty}^{1/2}(q_{\infty}-b_{\infty})\\\\[5.0pt]
0&-1\end{pmatrix}.$

Tedious but straightforward algebra gives

${\bm{A}}_{{\mathsf{x}},11}^{(0)}-{\bm{A}}_{12}^{(0)}({\bm{A}}_{22}^{(0)})^{-1}{\bm{A}}_{21}^{(0)}=\begin{pmatrix}c_{1}&q_{\infty}^{1/2}c_{2}\\\\[5.0pt]
q_{\infty}^{1/2}c_{2}&-c_{2}\end{pmatrix},$ (80)

where

$\displaystyle c_{1}$
$\displaystyle=\frac{-(1-q_{\infty})+2\lambda^{2}(1-2q_{\infty}+b_{\infty})^{2}-\lambda^{4}(1-2q_{\infty}+b_{\infty})^{2}(1-3q_{\infty}+2b_{\infty})}{(1-b_{\infty}/q_{\infty})(1-2q_{\infty}+b_{\infty})}-2\chi_{{\mathsf{x}}}\lambda^{2}q_{\infty},$
(81) $\displaystyle c_{2}$
$\displaystyle=\frac{1}{1-2q_{\infty}+b_{\infty}}-\lambda^{2}.$

We have $q_{\infty}>b_{\infty}$ and
$1-2q_{\infty}+b_{\infty}<1-q_{\infty}<1/\lambda^{2}$ (see Proposition 3(v)),
whence $c_{2}>0$. Moreover, the Schur complement is

$c_{1}-q_{\infty}c_{2}^{2}/(-c_{2})=c_{1}+q_{\infty}c_{2}=-q_{\infty}\lambda^{2}(1-\lambda^{2}(1-2q_{\infty}+b_{\infty}))-\frac{(1-\lambda^{2}(1-2q_{\infty}+b_{\infty}))^{2}}{1-b_{\infty}/q_{\infty}}-2\chi_{{\mathsf{x}}}\lambda^{2}q_{\infty}<0.$
(82)

Because $-c_{2}<0$ and $c_{1}+\gamma_{\infty}c_{2}<0$, we conclude that
${\bm{A}}_{{\mathsf{x}},11}^{(0)}-{\bm{A}}_{12}^{(0)}({\bm{A}}_{22}^{(0)})^{-1}{\bm{A}}_{21}^{(0)}\prec
0$.

Because these matrices are continuous in $\alpha_{v}$, we also have
${\bm{A}}_{{\mathsf{x}},11}^{(0)}-{\bm{A}}_{12}^{(0)}({\bm{A}}_{22}^{(0)})^{-1}{\bm{A}}_{21}^{(0)}\prec
0$ for all $\alpha_{v}$ sufficiently small. We thus get that for such
$\alpha_{v}$, the function $(\rho,u)\mapsto\min_{(\alpha_{\rho},\alpha_{u})\in
K}\mathsf{L}_{{\mathsf{x}}}(\rho,u;\alpha_{\rho},\alpha_{u},\alpha_{v})$ is
strictly concave and is maximized at $(\rho,u)=(0,0)$, at which point the
minimization over $(\alpha_{\rho},\alpha_{u})$ is achieved at
$(\alpha_{\rho},\alpha_{u})=(0,0)$. That is, for sufficiently small
$\alpha_{v}$,

$\sup_{\rho,u\in[-1,1]}\min_{(\alpha_{\rho},\alpha_{u})\in
K}\mathsf{L}_{{\mathsf{x}}}(\rho,u;\alpha_{\rho},\alpha_{u},\alpha_{v})=\mathsf{L}_{{\mathsf{x}}}(0,0;0,0,\alpha_{v})=-\lambda^{2}(1-q_{\infty})-\alpha_{v}+\lambda^{2}\mathbb{E}\Big{[}\Big{(}\frac{1}{1-M_{\infty}^{2}}-\alpha_{v}\Big{)}^{-1}\Big{]}.$
(83)

Note that
$\mathsf{L}_{{\mathsf{x}}}(0,0;0,0,0)=-\lambda^{2}(1-q_{\infty})+\lambda^{2}\mathbb{E}[1-M_{\infty}^{2}]=0$,
and, by dominated convergence,
$\partial_{\alpha_{v}}\mathsf{L}_{{\mathsf{x}}}(0,0;0,0,\alpha_{v})\big{|}_{\alpha_{v}=0}=-1+\lambda^{2}\mathbb{E}[(1-M_{\infty}^{2})^{2}]<-1+\lambda^{2}(1-q_{\infty})<0$
(see Proposition 3(v)). Thus, for $\alpha_{v}>0$ sufficiently small, the
right-hand side of (70) is negative. We conclude that for some $c>0$,

$\limsup_{\epsilon\rightarrow
0}\sup_{\mu\in{\mathcal{S}}^{(2)}_{{\mathsf{x}},\infty}(\epsilon)}\mathsf{F}_{{\mathsf{x}}}^{(2)}(\mu)<-c.$
(84)

This completes the proof of Theorem 2(i). Theorem 2(ii) now follows by a
straightforward argument which we present in Appendix B.3.

## Acknowledgements

The author would like to thank Song Mei and Zhou Fan for several useful
discussions and the collaboration that formed the inspiration for this work.
The author would also like to thank Ahmed El Alaoui, Mark Sellke, and Andrea
Montanari for fruitful discussions, in particular on the Sherrington-
Kirkpatrick sampling problem. The author is supported by the Miller Institute
for Basic Research in Science, University of California, Berkeley.

## References

  * [AMS22] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke, _Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization_.
  * [BM10] Mohsen Bayati and Andrea Montanari, _The dynamics of message passing on dense graphs, with applications to compressed sensing_ , 2010 IEEE International Symposium on Information Theory, 2010, pp. 1528–1532.
  * [BMN19] Raphaël Berthier, Andrea Montanari, and Phan-Minh Nguyen, _State evolution for approximate message passing with non-separable functions_ , Information and Inference: A Journal of the IMA 9 (2019), no. 1, 33–79.
  * [Bol14] Erwin Bolthausen, _An iterative construction of solutions of the TAP equations for the Sherrington–Kirkpatrick model_ , Communications in Mathematical Physics 325 (2014), no. 1, 333–366.
  * [CC15] Yuxin Chen and Emmanuel Candes, _Solving random quadratic systems of equations is nearly as easy as solving linear systems_ , Advances in Neural Information Processing Systems (C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, eds.), vol. 28, Curran Associates, Inc., 2015.
  * [CCFM19] Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma, _Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval_ , Mathematical Programming 176 (2019), no. 1, 5–37.
  * [CCM21] Michael Celentano, Chen Cheng, and Andrea Montanari, _The high-dimensional asymptotics of first order methods with random data_.
  * [CFM21] Michael Celentano, Zhou Fan, and Song Mei, _Local convexity of the TAP free energy and AMP convergence for Z2-synchronization_.
  * [CLM16] T. Tony Cai, Xiaodong Li, and Zongming Ma, _Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow_ , The Annals of Statistics 44 (2016), no. 5, 2221 – 2251.
  * [CLS15] Emmanuel J. Candés, Xiaodong Li, and Mahdi Soltanolkotabi, _Phase retrieval via Wirtinger flow: Theory and algorithms_ , IEEE Transactions on Information Theory 61 (2015), no. 4, 1985–2007.
  * [CM21] Michael Celentano and Andrea Montanari, _CAD: Debiasing the Lasso with inaccurate covariate model_.
  * [CMW20] Michael Celentano, Andrea Montanari, and Yuchen Wu, _The estimation error of general first order methods_ , Proceedings of Thirty Third Conference on Learning Theory (Jacob Abernethy and Shivani Agarwal, eds.), Proceedings of Machine Learning Research, vol. 125, PMLR, 09–12 Jul 2020, pp. 1078–1141.
  * [DAM16] Yash Deshpande, Emmanuel Abbe, and Andrea Montanari, _Asymptotic mutual information for the balanced binary stochastic block model_ , Information and Inference: A Journal of the IMA 6 (2016), no. 2, 125–170.
  * [Fer75] Xavier Fernique, _Regularité des trajectoires des fonctions aléatoires gaussiennes_ , Ecole d’Eté de Probabilités de Saint-Flour IV—1974, Springer, 1975, pp. 1–96.
  * [FMM21] Zhou Fan, Song Mei, and Andrea Montanari, _TAP free energy, spin glasses and variational inference_ , The Annals of Probability 49 (2021), no. 1, 1 – 45.
  * [GAS+19] Sebastian Goldt, Madhu Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborová, _Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup_ , Advances in Neural Information Processing Systems (H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Buc, E. Fox, and R. Garnett, eds.), vol. 32, Curran Associates, Inc., 2019.
  * [Gor85] Yehoram Gordon, _Some inequalities for Gaussian processes and applications_ , Israel Journal of Mathematics 50 (1985), no. 4, 265–289.
  * [Gor88] Y. Gordon, _On Milman’s inequality and random subspaces which escape through a mesh in $\mathbb{R}^{n}$_, Geometric Aspects of Functional Analysis (Berlin, Heidelberg) (Joram Lindenstrauss and Vitali D. Milman, eds.), Springer Berlin Heidelberg, 1988, pp. 84–106.
  * [JM13] Adel Javanmard and Andrea Montanari, _State evolution for general approximate message passing algorithms, with applications to spatial coupling_ , Information and Inference: A Journal of the IMA 2 (2013), no. 2, 115–144.
  * [MKUZ19] Stefano Sarao Mannelli, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborova, _Passed and spurious: Descent algorithms and local minima in spiked matrix-tensor models_ , Proceedings of the 36th International Conference on Machine Learning (Kamalika Chaudhuri and Ruslan Salakhutdinov, eds.), Proceedings of Machine Learning Research, vol. 97, PMLR, 09–15 Jun 2019, pp. 4333–4342.
  * [MKUZ20] Francesca Mignacco, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová, _Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification_ , Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, eds.), vol. 33, Curran Associates, Inc., 2020, pp. 9540–9550.
  * [MM21] Léo Miolane and Andrea Montanari, _The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning_ , The Annals of Statistics 49 (2021), no. 4, 2313 – 2335.
  * [MPV87] M. Mezard, G. Parisi, and M.A. Virasoro, _Spin glass theory and beyond: An introduction to the replica method and its applications_ , World Scientific Lecture Notes In Physics, World Scientific Publishing Company, 1987.
  * [MV21a] Andrea Montanari and Ramji Venkataramanan, _Estimation of low-rank matrices via approximate message passing_ , The Annals of Statistics 49 (2021), no. 1, 321 – 345.
  * [MV21b] , _Estimation of low-rank matrices via approximate message passing_ , The Annals of Statistics 49 (2021), no. 1, 321 – 345.
  * [MW22] Andrea Montanari and Yuchen Wu, _Statistically optimal first order algorithms: A proof via orthogonalization_ , 2022.
  * [MWCC20] Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen, _Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution_ , Foundations of Computational Mathematics 20 (2020), no. 3, 451–632.
  * [MZ20] Stefano Sarao Mannelli and Lenka Zdeborová, _Thresholds of descending algorithms in inference problems_ , Journal of Statistical Mechanics: Theory and Experiment 2020 (2020), no. 3, 034004.
  * [Sle62] David Slepian, _The one-sided barrier problem for gaussian noise_ , The Bell System Technical Journal 41 (1962), no. 2, 463–501.
  * [SMBC+19] Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, and Lenka Zdeborová, _Who is afraid of big bad minima? analysis of gradient-flow in spiked matrix-tensor models_ , Advances in Neural Information Processing Systems (H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Buc, E. Fox, and R. Garnett, eds.), vol. 32, Curran Associates, Inc., 2019.
  * [SMBC+20a] Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová, _Complex dynamics in simple neural networks: Understanding gradient flow in phase retrieval_ , Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, eds.), vol. 33, Curran Associates, Inc., 2020, pp. 3265–3274.
  * [SMBC+20b] Stefano Sarao Mannelli, Giulio Biroli, Chiara Cammarota, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová, _Marvels and pitfalls of the Langevin algorithm in noisy high-dimensional inference_ , Phys. Rev. X 10 (2020), 011057.
  * [Sto13] Mihailo Stojnic, _A framework to characterize performance of lasso algorithms_.
  * [Sud71] Vladimir Nikolaevich Sudakov, _Gaussian random processes and measures of solid angles in Hilbert space_ , Doklady Akademii Nauk, vol. 197, Russian Academy of Sciences, 1971, pp. 43–45.
  * [Sud79] Vladimir N Sudakov, _Geometric problems in the theory of infinite-dimensional probability distributions_ , vol. 141, American Mathematical Soc., 1979.
  * [SWW17] Sujay Sanghavi, Rachel Ward, and Chris D. White, _The local convexity of solving systems of quadratic equations_ , Results in Mathematics 71 (2017), no. 3, 569–608.
  * [TAH15] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi, _Precise high-dimensional error analysis of regularized M-estimators_ , 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2015, pp. 410–417.
  * [TAP77] D. J. Thouless, P. W. Anderson, and R. G. Palmer, _Solution of ‘solvable model of a spin glass’_ , The Philosophical Magazine: A Journal of Theoretical Experimental and Applied Physics 35 (1977), no. 3, 593–601.
  * [TOH15] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi, _Regularized linear regression: A precise analysis of the estimation error_ , Proceedings of The 28th Conference on Learning Theory (Paris, France) (Peter Grünwald, Elad Hazan, and Satyen Kale, eds.), Proceedings of Machine Learning Research, vol. 40, PMLR, 03–06 Jul 2015, pp. 1683–1709.
  * [Vil08] C. Villani, _Optimal transport: Old and new_ , Grundlehren der mathematischen Wissenschaften, Springer Berlin Heidelberg, 2008.
  * [VSL+22] Rodrigo Veiga, Ludovic Stephan, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová, _Phase diagram of stochastic gradient descent in high-dimensional two-layer neural networks_.

##  Appendix A Proof of the Sudakov-Fernique post-AMP inequality

The goal of this section is to prove Theorem 1 and Corollary 1. We start by
providing a finite sample comparison inequality, which we call the
_conditional Sudakov-Fernique inequality_ , in Appendix A.1. The Sudakov-
Fernique post-AMP inequality results from approximating the conditional
Sudakov-Fernique inequality in the limit $n\rightarrow\infty$ using AMP state
evolution. We carry out this approximation argument in Appendix A.2.

###  A.1 The conditional Sudakov-Fernique inequality

The conditional Sudakov-Fernique inequality is nothing but the classical
Sudakov-Fernique inequality applied conditional on a set of linear
constraints. Thus, it is not technically a new comparison inequality. Our
insight is to write the conditional inequality in a way which better reveals
its structure and facilitates its application in the context of AMP.

We apply the classical Sudakov-Fernique inequality conditional on a set of
linear-constraints on ${\bm{W}}$ of the form

${\bm{W}}{\bm{R}}=\bm{S},$ (85)

for matrices ${\bm{R}},\bm{S}\in{\mathbb{R}}^{n\times k}$, where ${\bm{R}}$ is
full rank. Given any such matrices, let
${\bm{B}}_{\mathsf{SF}}={\bm{B}}_{\mathsf{SF}}({\bm{R}},\bm{S})\in{\mathbb{R}}^{k\times
k}$ be any solution to the equations

${\bm{R}}^{\top}\bm{S}=({\bm{R}}^{\top}{\bm{R}}){\bm{B}}_{\mathsf{SF}}+{\bm{B}}_{\mathsf{SF}}^{\top}({\bm{R}}^{\top}{\bm{R}}).$
(86)

######  Lemma 2 (Existence of solutions to Eq. (86)).

If ${\bm{R}}^{\top}\bm{S}$ is symmetric (i.e.,
${\bm{R}}^{\top}\bm{S}=\bm{S}^{\top}{\bm{R}}$), then Eq. (86) has solutions.
This occurs, in particular, if there exists a symmetric matrix ${\bm{W}}$ with
${\bm{W}}{\bm{R}}=\bm{S}$.

###### Proof of Lemma 2.

We may take
${\bm{B}}_{\mathsf{SF}}=\frac{1}{2}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{R}}^{\top}\bm{S}$,
where the inverse exists because ${\bm{R}}$ is full-rank. Note that if
${\bm{W}}{\bm{R}}=\bm{S}$ for symmetric ${\bm{W}}$, then
${\bm{R}}^{\top}\bm{S}={\bm{R}}^{\top}{\bm{W}}{\bm{R}}=\bm{S}^{\top}{\bm{R}}$.
∎

The purpose of defining ${\bm{B}}_{\mathsf{SF}}$ is to provide a simple
representation of the distribution of ${\bm{W}}$ conditional on the event
${\bm{W}}{\bm{R}}=\bm{S}$, which we do in the next lemma.

######  Lemma 3.

Let ${\bm{G}}_{\mathsf{SF}}=\bm{S}-{\bm{R}}{\bm{B}}_{\mathsf{SF}}$ for any
${\bm{B}}_{\mathsf{SF}}$ satisfying Eq. (86). Further, let
$\bm{T}_{\mathsf{SF}}={\bm{G}}_{\mathsf{SF}}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{R}}^{\top}$
is the unique matrix satisfying
$\bm{T}_{\mathsf{SF}}{\bm{R}}={\bm{G}}_{\mathsf{SF}}$ and
$\bm{T}_{\mathsf{SF}}{\mathsf{P}}_{{\bm{R}}}^{\perp}=0$. Then

${\bm{W}}{\bm{R}}=\bm{S}\quad\text{implies}\quad{\bm{W}}-{\mathsf{P}}_{{\bm{R}}}^{\perp}{\bm{W}}{\mathsf{P}}_{{\bm{R}}}^{\perp}=\bm{T}_{\mathsf{SF}}+\bm{T}_{\mathsf{SF}}^{\top}.$
(87)

Thus,

$\mathsf{Law}\big{(}{\bm{W}}\mid{\bm{W}}{\bm{R}}=\bm{S}\big{)}=\mathsf{Law}\big{(}\bm{T}_{\mathsf{SF}}+\bm{T}_{\mathsf{SF}}^{\top}+{\mathsf{P}}_{{\bm{R}}}^{\perp}\widetilde{\bm{W}}{}{\mathsf{P}}_{{\bm{R}}}^{\perp}\big{)},$
(88)

where $\widetilde{\bm{W}}{}\sim{\rm GOE}(n)$.

###### Proof of Lemma 3.

If ${\bm{W}}{\bm{R}}=\bm{S}$, then

$\displaystyle{\bm{W}}-{\mathsf{P}}_{{\bm{R}}}^{\perp}{\bm{W}}{\mathsf{P}}_{{\bm{R}}}^{\perp}$
$\displaystyle={\bm{W}}{\mathsf{P}}_{{\bm{R}}}+{\mathsf{P}}_{{\bm{R}}}{\bm{W}}{\mathsf{P}}_{{\bm{R}}}^{\perp}$
(89)
$\displaystyle={\bm{W}}{\bm{R}}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{R}}^{\top}+{\bm{R}}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{R}}^{\top}{\bm{W}}\big{(}{\mathbf{I}}_{n}-{\bm{R}}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{R}}^{\top}\big{)}$
$\displaystyle=\bm{S}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{R}}^{\top}+{\bm{R}}({\bm{R}}^{\top}{\bm{R}})^{-1}\bm{S}^{\top}-{\bm{R}}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{R}}^{\top}\bm{S}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{R}}^{\top}$
$\displaystyle=\bm{S}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{R}}^{\top}+{\bm{R}}({\bm{R}}^{\top}{\bm{R}})^{-1}\bm{S}^{\top}-{\bm{R}}{\bm{B}}_{\mathsf{SF}}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{R}}^{\top}-{\bm{R}}({\bm{R}}^{\top}{\bm{R}})^{-1}{\bm{B}}_{\mathsf{SF}}^{\top}{\bm{R}}^{\top}$
$\displaystyle=\bm{T}_{\mathsf{SF}}+\bm{T}_{\mathsf{SF}}^{\top},$

as desired.

Next, note that
${\mathsf{P}}_{{\bm{R}}}^{\perp}{\bm{W}}{\mathsf{P}}_{{\bm{R}}}^{\perp}$ is
independent of
${\bm{W}}-{\mathsf{P}}_{{\bm{R}}}^{\perp}{\bm{W}}{\mathsf{P}}_{{\bm{R}}}^{\perp}$,
and the occurrence of the event ${\bm{W}}{\bm{R}}=\bm{S}$ is a function of
${\bm{W}}-{\mathsf{P}}_{{\bm{R}}}^{\perp}{\bm{W}}{\mathsf{P}}_{{\bm{R}}}^{\perp}$.
The final distributional claim of the lemma follows. ∎

We can now state the conditional Sudakov-Fernique inequality.

######  Theorem 3 (Conditional Sudakov-Fernique inequality).

Consider ${\bm{R}},\bm{S}\in{\mathbb{R}}^{n\times k}$, and assume ${\bm{R}}$
is full-rank. Let ${\bm{B}}_{\mathsf{SF}}\in{\mathbb{R}}^{k\times k}$,
${\bm{G}}_{\mathsf{SF}},\bm{T}_{\mathsf{SF}}\in{\mathbb{R}}^{n\times k}$ be
random matrices which satisfy Eq. (86) and the conditions of Lemma 3 almost
surely. Define the (random) function
${\bm{g}}_{\mathsf{SF}}:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{n}$ by

${\bm{g}}_{\mathsf{SF}}({\bm{v}}):=\sqrt{n}\,\bm{T}_{\mathsf{SF}}{\bm{v}}+\|{\mathsf{P}}_{{\bm{R}}}^{\perp}{\bm{v}}\|{\mathsf{P}}_{{\bm{R}}}^{\perp}{\bm{\xi}},$
(90)

where ${\bm{\xi}}\sim{\sf N}(0,{\mathbf{I}}_{n})$ independent of everything
else. Then, for any compact set
$K=K({\bm{R}},\bm{S})\subset{\mathbb{R}}^{n+m}$ (which may depend on
${\bm{R}},\bm{S}$) and bounded and continuous
$f:{\mathbb{R}}^{m+n}\times({\mathbb{R}}^{n\times
k})^{2}\rightarrow{\mathbb{R}}$, we have

$\mathbb{P}\left(\sup_{({\bm{v}},{\bm{u}})\in
K}\big{\\{}{\bm{v}}^{\top}{\bm{W}}{\bm{v}}+f({\bm{v}},{\bm{u}};{\bm{R}},\bm{S})\big{\\}}\geq
t\Bigm{|}{\bm{W}}{\bm{R}}=\bm{S}\right)\leq\mathbb{P}\left(\sup_{({\bm{v}},{\bm{u}})\in
K}\Big{\\{}\frac{2}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{SF}}({\bm{v}}),{\bm{v}}\rangle+f({\bm{v}},{\bm{u}};{\bm{R}},\bm{S})\Big{\\}}\geq
t\right).$ (91)

###### Proof of Theorem 3.

By Lemma 3, for fixed ${\bm{R}},\bm{S}\in{\mathbb{R}}^{n\times k}$

$\displaystyle\mathbb{P}\left(\sup_{({\bm{v}},{\bm{u}})\in
S}\big{\\{}{\bm{v}}^{\top}{\bm{W}}{\bm{v}}+f({\bm{v}},{\bm{u}};{\bm{R}},\bm{S})\big{\\}}\geq
t\Bigm{|}{\bm{W}}{\bm{R}}=\bm{S}\right)$ (92)
$\displaystyle\qquad\qquad=\mathbb{P}\left(\sup_{({\bm{v}},{\bm{u}})\in
S}\big{\\{}{\bm{v}}^{\top}{\mathsf{P}}_{{\bm{R}}}^{\perp}\widetilde{\bm{W}}{}{\mathsf{P}}_{{\bm{R}}}^{\perp}{\bm{v}}+\frac{2}{\sqrt{n}}\langle\bm{T}_{\mathsf{SF}}{\bm{v}},{\bm{v}}\rangle+f({\bm{v}},{\bm{u}};{\bm{R}},\bm{S})\big{\\}}\geq
t\Bigm{|}{\bm{W}}{\bm{R}}=\bm{S}\right).$

Because $\widetilde{\bm{W}}{}$ is the only part of the optimization in the
second probability which is random, and it is conditionally distributed ${\rm
GOE}(n)$, by the Sudakov-Fernique inequality (Proposition 1), the right-hand
side of the previous display is bounded by

$\mathrm{RHS}\leq\mathbb{P}\left(\sup_{({\bm{v}},{\bm{u}})\in
S}\Big{\\{}\frac{2}{\sqrt{n}}\|{\mathsf{P}}_{{\bm{R}}}^{\perp}{\bm{v}}\|_{2}\langle{\mathsf{P}}_{{\bm{R}}}^{\perp}{\bm{\xi}},{\bm{v}}\rangle+\frac{2}{\sqrt{n}}\langle\bm{T}_{\mathsf{SF}}{\bm{v}},{\bm{v}}\rangle+f({\bm{v}},{\bm{u}};{\bm{R}},\bm{S})\Big{\\}}\geq
t\right).$ (93)

Note that the objective in the previous display is nothing but
$\frac{2}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{SF}}({\bm{v}}),{\bm{v}}\rangle+f({\bm{v}},{\bm{u}};{\bm{R}},\bm{S})$,
which gives the result. ∎

###  A.2 Sudakov-Fernique post-AMP

Theorem 1 and Corollary 1 follow from Theorem 3 with matrices explicitly
related to the AMP iteration, at the cost of incurring an error which vanishes
as $n\rightarrow\infty$. Our main task is to show this error is small.

###### Proof of Theorem 1.

Recall the ${\bm{M}}\in{\mathbb{R}}^{n\times k}$ is the matrix whose
$s^{\text{th}}$ column is given by ${\bm{m}}^{s-1}$ and
${\bm{G}}\in{\mathbb{R}}^{n\times k}$ is the matrix whose $s^{\text{th}}$
column is given by ${\bm{g}}^{s}$, which are generated by the AMP algorithm
Eq. (13). Let

${\bm{B}}:=\begin{pmatrix}0&{\mathsf{b}}_{11}&{\mathsf{b}}_{21}&\cdots&{\mathsf{b}}_{(k-1)1}\\\\[5.0pt]
0&0&{\mathsf{b}}_{22}&&{\mathsf{b}}_{(k-1)2}\\\\[5.0pt]
\vdots&&\ddots&\ddots&\vdots\\\\[5.0pt]
0&0&&0&{\mathsf{b}}_{(k-1)(k-1)}\\\\[5.0pt] 0&0&\cdots&0&0\end{pmatrix},$ (94)

for ${\mathsf{b}}_{sj}$ defined in Eq. (15). We define two matrix-valued
functions of the random matrix ${\bm{W}}$ and noise ${\bm{g}}^{0}$ given by
$\bm{S}_{\mathsf{AMP}}({\bm{W}},{\bm{g}}^{0})={\bm{M}}$ and
${\bm{R}}_{\mathsf{AMP}}({\bm{W}},{\bm{g}}^{0})={\bm{G}}+{\bm{M}}{\bm{B}}$,
where we recall that ${\bm{G}},{\bm{M}}$ is a function of
${\bm{W}},{\bm{g}}^{0}$ via the AMP iteration (13). Consider any fixed
matrices ${\bm{R}}\in{\mathbb{R}}^{n\times k}$ and
$\bm{S}\in{\mathbb{R}}^{n\times k}$. By the AMP iteration Eq. (13), we may
check inductively the equivalence of events (over ${\bm{W}},{\bm{g}}^{0}$)

$\Big{\\{}\bm{S}_{\mathsf{AMP}}({\bm{W}},{\bm{g}}^{0})=\bm{S},\;{\bm{R}}_{\mathsf{AMP}}({\bm{W}},{\bm{g}}^{0})={\bm{R}}\Big{\\}}=\Big{\\{}{\bm{W}}{\bm{R}}=\bm{S},\;f({\bm{g}}_{0})=\bm{S}_{\,\cdot\,,1}\Big{\\}}.$
(95)

Thus, conditioning on the sequence of AMP iterates
${\bm{m}}^{0},{\bm{m}}^{1},\ldots,{\bm{m}}^{k-1}$ and
${\bm{g}}^{0},{\bm{g}}^{1},\ldots,{\bm{g}}^{k}$ is equivalent to conditioning
on the realization of ${\bm{g}}^{0}$, $\bm{S}_{\mathsf{AMP}}({\bm{W}})$ and
${\bm{R}}_{\mathsf{AMP}}({\bm{W}})$, which by the previous display is
equivalent to conditioning on ${\bm{g}}^{0}$ and a set of linear constraints
on ${\bm{W}}$ of the form handled by Theorem 3.

The key insight is that with high probability over ${\bm{W}},{\bm{g}}^{0}$,
the deterministic matrix ${\bm{B}}$ approximately solves Eq. (86). Precisely,
there exists a random matrix
${\bm{B}}_{\mathsf{SF}}={\bm{B}}_{\mathsf{SF}}({\bm{W}},{\bm{g}}^{0})$ such
that, with probability 1 over ${\bm{W}},{\bm{g}}^{0}$,

${\bm{R}}_{\mathsf{AMP}}^{\top}\bm{S}_{\mathsf{AMP}}=({\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}){\bm{B}}_{\mathsf{SF}}+{\bm{B}}_{\mathsf{SF}}^{\top}({\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}),$
(96)

and

$\|{\bm{B}}_{\mathsf{SF}}-{\bm{B}}\|_{{\rm
op}}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}0,$ (97)

where for compactness of notation, we have removed the arguments from
$\bm{S}_{\mathsf{AMP}}({\bm{W}},{\bm{g}}^{0})$,
${\bm{R}}_{\mathsf{AMP}}({\bm{W}},{\bm{g}}^{0})$. Indeed,

$\frac{1}{n}\Big{(}{\bm{R}}_{\mathsf{AMP}}^{\top}\bm{S}_{\mathsf{AMP}}-{\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}{\bm{B}}-{\bm{B}}{\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}\Big{)}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}0,$
(98)

because, by Proposition 2,

$\frac{1}{n}{\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}=\frac{1}{n}{\bm{M}}^{\top}{\bm{M}}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\bm{K}_{\leq
k},\qquad\frac{1}{n}{\bm{R}}_{\mathsf{AMP}}^{\top}\bm{S}_{\mathsf{AMP}}=\frac{1}{n}{\bm{M}}^{\top}({\bm{G}}+{\bm{M}}{\bm{B}})\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}{\bm{B}}^{\top}\bm{K}_{\leq
k}+\bm{K}_{\leq k}{\bm{B}},$ (99)

where the second convergence uses Gaussian integration by parts: for $1\leq
s\leq t$, we have
$\mathbb{E}[G_{s}M_{t}]=\mathbb{E}[G_{s}f_{t}(G_{0},\ldots,G_{t})]=\sum_{j=1}^{t}K_{sj}{\mathsf{b}}_{sj}$,
with $G_{s},M_{t}$ as in Proposition 2. Thus, we may pick

${\bm{B}}_{\mathsf{SF}}={\bm{B}}+\frac{1}{2}({\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}})^{\dagger}\Big{(}{\bm{R}}_{\mathsf{AMP}}^{\top}\bm{S}_{\mathsf{AMP}}-{\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}{\bm{B}}-{\bm{B}}^{\top}{\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}\Big{)}.$
(100)

Then Eq. (96) holds by definition. Because $\bm{K}_{\leq k}\succ 0$, the
second-to-last display implies Eq. (97).

Now, define ${\bm{G}}_{\mathsf{SF}}$, $\bm{T}_{\mathsf{SF}}$, and
${\bm{g}}_{\mathsf{SF}}({\bm{v}})$ as in Lemma 3 and Theorem 3. In particular,
define

${\bm{G}}_{\mathsf{SF}}=\bm{S}_{\mathsf{AMP}}-{\bm{R}}_{\mathsf{AMP}}{\bm{B}}_{\mathsf{SF}},\quad\bm{T}_{\mathsf{SF}}={\bm{G}}_{\mathsf{SF}}({\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}})^{-1}{\bm{R}}_{\mathsf{AMP}}^{\top},\quad{\bm{g}}_{\mathsf{SF}}({\bm{v}})=\sqrt{n}\,\bm{T}_{\mathsf{SF}}{\bm{v}}+\|{\mathsf{P}}_{{\bm{R}}_{\mathsf{AMP}}}^{\perp}{\bm{v}}\|{\mathsf{P}}_{{\bm{R}}_{\mathsf{AMP}}}^{\perp}{\bm{\xi}},$
(101)

where ${\bm{\xi}}\sim{\sf N}(0,{\mathbf{I}}_{n})$ is the same Gaussian used in
the definition of ${\bm{g}}_{\mathsf{AMP}}({\bm{v}})$ in the statement of the
theorem. Note the inverse
$({\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}})^{-1}$ exists with
probability approaching 1 because
${\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}/n\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\bm{K}_{\geq
k}$ by Proposition 2. By Eq. (97), and because
$\|{\bm{R}}_{\mathsf{AMP}}\|_{{\rm
op}}/\sqrt{n}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\|\bm{K}_{\leq
k}\|_{{\rm op}}^{1/2}$ by Proposition 2, we get
$\|{\bm{G}}/\sqrt{n}-{\bm{G}}_{\mathsf{SF}}/\sqrt{n}\|_{{\rm
op}}\leq(\|{\bm{R}}_{\mathsf{AMP}}\|_{{\rm
op}}/\sqrt{n})\|{\bm{B}}-{\bm{B}}_{\mathsf{SF}}\|_{{\rm
op}}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}0$. We then conclude
that

$\|\bm{T}-\bm{T}_{\mathsf{SF}}\|_{{\rm
op}}\leq\Big{\|}\frac{1}{\sqrt{n}}{\bm{G}}-\frac{1}{\sqrt{n}}{\bm{G}}_{\mathsf{SF}}\Big{\|}_{{\rm
op}}\|({\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}/n)^{-1}\|_{{\rm
op}}\Big{\|}\frac{1}{\sqrt{n}}{\bm{R}}_{\mathsf{AMP}}\Big{\|}_{{\rm
op}}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}0,$ (102)

where we use that
${\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}/n\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\bm{K}_{\leq
k}\succ 0$ has positive definite limit. Finally, note
$\big{\|}{\bm{g}}_{\mathsf{AMP}}({\bm{v}})-{\bm{g}}_{\mathsf{SF}}({\bm{v}})\big{\|}/\sqrt{n}=\big{\|}(\bm{T}{\bm{v}}-\bm{T}_{\mathsf{SF}}{\bm{v}})+\|{\mathsf{P}}_{{\bm{R}}_{\mathsf{AMP}}}^{\perp}{\bm{v}}\|({\mathsf{P}}_{{\bm{R}}_{\mathsf{AMP}}}{\bm{\xi}})/\sqrt{n}\big{\|}\leq\big{(}\|\bm{T}-\bm{T}_{\mathsf{SF}}\|_{{\rm
op}}+\|{\mathsf{P}}_{{\bm{R}}_{\mathsf{AMP}}}{\bm{\xi}}\|/\sqrt{n}\big{)}\|{\bm{v}}\|,$
whence

$\displaystyle\sup_{\|{\bm{v}}\|\leq
R}\Big{|}\frac{2}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{AMP}}({\bm{v}}),{\bm{v}}\rangle-\frac{2}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{SF}}({\bm{v}}),{\bm{v}}\rangle\Big{|}$
$\displaystyle\leq\sup_{\|{\bm{v}}\|\leq
R}2\|{\bm{v}}\|^{2}\Big{(}\|\bm{T}-\bm{T}_{\mathsf{SF}}\|_{{\rm
op}}+\frac{\|{\mathsf{P}}_{{\bm{R}}_{\mathsf{AMP}}}{\bm{\xi}}\|}{\sqrt{n}}\Big{)}$
(103) $\displaystyle\leq 2R^{2}\Big{(}\|\bm{T}-\bm{T}_{\mathsf{SF}}\|_{{\rm
op}}+\frac{\|{\mathsf{P}}_{{\bm{R}}_{\mathsf{AMP}}}{\bm{\xi}}\|}{\sqrt{n}}\Big{)}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}0.$

Now Theorem 1 follows from an application of the conditional Sudakov-Fernique
inequality and the approximation bound in the previous display. Indeed,
applying the conditional Sudakov-Fernique inequality, we have for any fixed
${\bm{R}},\bm{S},{\bm{g}}^{0}$ and any $t\in{\mathbb{R}}$ and $\epsilon>0$,

$\displaystyle\mathbb{P}\left(\sup_{({\bm{v}},{\bm{u}})\in
K}\big{\\{}{\bm{v}}^{\top}{\bm{W}}{\bm{v}}+f({\bm{v}},{\bm{u}};{\bm{R}},\bm{S}-{\bm{R}}{\bm{B}},{\bm{g}}^{0})\big{\\}}\geq
t-\epsilon\Bigm{|}{\bm{R}}_{\mathsf{AMP}}({\bm{W}})={\bm{R}},\bm{S}_{\mathsf{AMP}}({\bm{W}})=\bm{S},{\bm{g}}^{0}\right)$
(104) $\displaystyle\leq\mathbb{P}\left(\sup_{({\bm{v}},{\bm{u}})\in
K}\Big{\\{}\frac{2}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{SF}}({\bm{v}}),{\bm{v}}\rangle+f({\bm{v}},{\bm{u}};{\bm{R}},\bm{S}-{\bm{R}}{\bm{B}},{\bm{g}}^{0})\Big{\\}}\geq
t-\epsilon\right)$
$\displaystyle\leq\mathbb{P}\left(\sup_{({\bm{v}},{\bm{u}})\in
S}\Big{\\{}\frac{2}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{AMP}}({\bm{v}}),{\bm{v}}\rangle+f({\bm{v}},{\bm{u}};{\bm{R}},\bm{S}-{\bm{R}}{\bm{B}},{\bm{g}}^{0})\Big{\\}}\geq
t\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\mathbb{P}\left(\sup_{\|{\bm{v}}\|\leq
R}\Big{|}\frac{2}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{AMP}}({\bm{v}}),{\bm{v}}\rangle-\frac{2}{\sqrt{n}}\langle{\bm{g}}_{\mathsf{SF}}({\bm{v}}),{\bm{v}}\rangle\Big{|}>\epsilon\right).$

Now we marginalize over ${\bm{W}},{\bm{g}}^{0}$ and take $n\rightarrow\infty$,
whence the second term on the right-hand side vanishes. Taking then
$\epsilon\rightarrow 0$ gives Theorem 1. ∎

###### Proof of Corollary 1.

We can prove Corollary 1 viewing ${\bm{x}}$ as fixed, and then marginalizing
over ${\bm{x}}$. Thus, we now consider ${\bm{x}}$ as fixed, and it does not
show up explicitly in the proof.

Corollary 1 holds by exactly the same argument in the proof of Theorem 1,
except with choices of $\bm{S}_{\mathsf{AMP}}$, ${\bm{R}}_{\mathsf{AMP}}$, and
${\bm{B}}$ tailored to the iteration Eq. (22). In particular, now we choose

${\bm{B}}:=\begin{pmatrix}0&\widehat{\mathsf{b}}{}_{1}&0&\cdots&0\\\\[5.0pt]
0&0&\widehat{\mathsf{b}}{}_{2}&&0\\\\[5.0pt]
\vdots&&\ddots&\ddots&\vdots\\\\[5.0pt]
0&0&&0&\widehat{\mathsf{b}}{}_{k-1}\\\\[5.0pt] 0&0&\cdots&0&0\end{pmatrix},$
(105)

and $\bm{S}_{\mathsf{AMP}}({\bm{W}},{\bm{g}}^{0})=\lambda{\bm{M}}$ and
${\bm{R}}_{\mathsf{AMP}}({\bm{W}},{\bm{g}}^{0})={\bm{G}}+\lambda{\bm{M}}{\bm{B}}$,
where ${\bm{M}}$ and ${\bm{G}}$ are as defined in Proposition 3. With these
choices and provided we interpret $\bm{K}_{\leq k}$ as that state evolution
matrix appearing in Proposition 3, the remainder of the proof goes through
verbatim, except that Eq. (98) requires a slightly different justification.
Now we have that ${\bm{B}}$ is a random matrix, but by Proposition 3, it
converges to the deterministic limit

${\bm{B}}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\tilde{\bm{B}}:=\begin{pmatrix}0&{\mathsf{b}}_{1}&0&\cdots&0\\\\[5.0pt]
0&0&{\mathsf{b}}_{2}&&0\\\\[5.0pt] \vdots&&\ddots&\ddots&\vdots\\\\[5.0pt]
0&0&&0&{\mathsf{b}}_{k-1}\\\\[5.0pt] 0&0&\cdots&0&0\end{pmatrix},$ (106)

where
${\mathsf{b}}_{s}=\lambda(1-\mathbb{E}[\tanh^{2}(\gamma_{s}+\sqrt{\gamma_{s}}G)]$,
where $G\sim{\sf N}(0,1)$. Thus,

$\frac{1}{n}{\bm{R}}_{\mathsf{AMP}}^{\top}{\bm{R}}_{\mathsf{AMP}}=\frac{1}{n}\lambda^{2}{\bm{M}}^{\top}{\bm{M}}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\bm{K}_{\leq
k},\qquad\frac{1}{n}{\bm{R}}_{\mathsf{AMP}}^{\top}\bm{S}_{\mathsf{AMP}}=\frac{1}{n}\lambda{\bm{M}}^{\top}({\bm{G}}+\lambda{\bm{M}}{\bm{B}})\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}\tilde{\bm{B}}^{\top}\bm{K}_{\leq
k}+\bm{K}_{\leq k}\tilde{\bm{B}},$ (107)

which implies Eq. (98). The remainder of the proof proceeds verbatim as
before. ∎

##  Appendix B Auxiliary proofs

###  B.1 Proof of Proposition 3

Proposition 3 is equivalent to the state evolution results given in [DAM16,
CFM21, AMS22]. Because we use slightly different notation, we provide some
details here for completeness. As in Section 4, by symmetry we may assume
without loss of generality that ${\bm{x}}=\bm{1}$ and $X=1$.

That $\gamma_{s}>0$ for all $s$ holds by induction. First, $\gamma_{0}>0$ by
assumption. Then, if $\gamma_{s}>0$, also $\gamma_{s+1}>0$, because
$\tanh^{2}(\gamma_{s}+\sqrt{\gamma_{s}}G)$ is positive almost surely. Further
the equation

$\gamma=\lambda^{2}\mathbb{E}[\tanh^{2}(\gamma+\sqrt{\gamma}G)]+\chi_{{\mathsf{x}}}\gamma_{0},$
(108)

has a unique solution positive solution $\gamma_{\infty}>0$: for
${\mathsf{x}}=\mathsf{FMM}$ and $\lambda>1$, this is given by [CFM21,
Proposition A.2], and for ${\mathsf{x}}=\mathsf{AMS}$ and $\lambda>0$, this is
given by [AMS22, Lemma 4.5] (note their $\gamma^{*}$ is our
$\gamma_{\infty}-\gamma_{0}$ and their $t$ is our $\gamma_{0}$). Moreover, by
[DAM16, Lemma 6.1(a)] or [AMS22, Lemma 4.5(a)],
$\gamma\mapsto\lambda^{2}\mathbb{E}[\tanh^{2}(\gamma+\sqrt{\gamma}G)]$ is
strictly increasing and concave in $\gamma$. Thus, $\gamma_{s}$ is strictly
increasing and $\gamma_{s}\rightarrow\gamma_{\infty}$, provided
$\gamma_{0}<\gamma_{\infty}$. For ${\mathsf{x}}=\mathsf{AMS}$, this holds by
Eq. (101), because $\chi_{\mathsf{AMS}}=1$. For ${\mathsf{x}}=\mathsf{FMM}$,
this holds by assumption. Because $\gamma_{s}$ is strictly increasing,
$\bm{\Gamma}_{\leq k}$ is positive definite. Thus, we have established items
(i) and (iv).

Item (v) in the case ${\mathsf{x}}=\mathsf{FMM}$ and $\lambda>1$ is given by
[CFM21, Proposition A.2]. The case ${\mathsf{x}}=\mathsf{AMS}$ is given by
essentially the same argument appearing in [CFM21], which we provide here.
Indeed, consider a scalar observation
$\gamma_{\infty}X+\sqrt{\gamma_{\infty}}G$, with $X\sim{\rm Unif}\\{-1,+1\\}$
and $G\sim{\sf N}(0,1)$ independent. Then $\tanh(Y)=\mathbb{E}[X|Y]$, and its
Bayes risk is given by
$\mathbb{E}[(\tanh(Y)-X)^{2}]=1-\mathbb{E}[\tanh^{2}(Y)]=1-q_{\infty}$. We can
compare this to the risk of the linear estimator $(1+\gamma_{\infty})^{-1}Y$,
whose risk is easily computed to be $1/(1+\gamma_{\infty})\leq
1/(1+\lambda^{2}q_{\infty})$, where the inequality holds by Eq. (28). Because
the $\tanh(Y)$ and $(1+\gamma_{\infty})^{-1}Y$ differ on a set of positive
probability, we get $1-q_{\infty}<1/(1+\lambda^{2}q_{\infty})$, which
rearranges to the first line in the display in item (v). The second two lines
follow from [DAM16, Appendix B.2], also cited in [CFM21, Proposition A.2].

Item (ii) follows from the state evolution result of [BM10], together with
some simplifications specific to the $\mathbb{Z}_{2}$-synchronization model,
as in [DAM16, Eqs. (69),(70)] and [AMS22, Proposition 4.4]. Indeed, with
$\bm{K}_{\leq k}$ as defined in the lemma and using Eq. (23), we have

$\displaystyle K_{s+1,s+1}$
$\displaystyle=\lambda^{2}\mathbb{E}[\tanh(K_{s,s}+\chi_{{\mathsf{x}}}\gamma_{0}+\sqrt{K_{s,s}+\chi_{{\mathsf{x}}}\gamma_{0}}G)].$
(109)

Moreover, as in the proof of [AMS22, Proposition 4.4],

$\displaystyle\mathbb{E}[\tanh(K_{s,s}+\chi_{{\mathsf{x}}}\gamma_{0}+\sqrt{K_{s,s}+\chi_{{\mathsf{x}}}\gamma_{0}}G)\tanh(K_{t,t}+\chi_{{\mathsf{x}}}\gamma_{0}+\sqrt{K_{t,t}+\chi_{{\mathsf{x}}}\gamma_{0}}G)]$
(110) $\displaystyle\qquad\qquad=\mathbb{E}[\tanh(K_{s\wedge t,s\wedge
t}+\chi_{{\mathsf{x}}}\gamma_{0}+\sqrt{K_{s\wedge t,s\wedge
t}+\chi_{{\mathsf{x}}}\gamma_{0}}G)]=K_{s+1,t+1}.$

Thus, $\bm{K}_{\leq k}$, as we have defined it, satisfies the state evolution
recursions as given in [BM10]. (For another instance of this these type of
state evolution simplifications, see Eqs. (4.16) and (4.17) and Proposition
4.4 of [AMS22], which should be compared to the previous two displays). Item
(ii) now follows. Moreover, note that the above two displays are equivalent to
Item (iii). The proof is complete.

###  B.2 Proof of Lemma 1

We first introduce the following notation: for any $\mu\in
W_{2}({\mathbb{R}}\times(-1,1)^{k+1}\times{\mathbb{R}}^{k+2})$, let $\mu_{1}$
denote the marginal of its first two coordinates, and $\mu_{2}$ denotes the
marginal of its last $2k+2$ coordinates. Thus, if
$(V,U,\breve{\bm{M}}{},\breve{\bm{G}}{},G_{0},\Xi)\sim\mu$, then
$(V,U)\sim\mu_{1}$ and $(\breve{\bm{M}}{},\breve{\bm{G}}{},\Xi)\sim\mu_{2}$.
Moreover, throughout the proof, $\epsilon(\cdot)$ will denote a
${\mathbb{R}}_{>0}\cup\\{\infty\\}$ valued function, possibly depending on
$\lambda$ and $\bm{K}_{\leq k}$, with the property that
$\epsilon(\delta)\rightarrow 0$ as $\delta\downarrow 0$. We will also denote
the space $W_{2}({\mathbb{R}}\times(-1,1)^{k+1}\times{\mathbb{R}}^{k+1})$ with
the short-hand $W_{2}$. Moreover, denote
$\widehat{\mu}{}:=\widehat{\mu}{}_{\sqrt{n}{\bm{v}},{\bm{u}},{\bm{M}},{\bm{G}},{\bm{g}}^{0},{\bm{\xi}}}$,
so that $\widehat{\mu}{}_{1}=\widehat{\mu}{}_{\sqrt{n}{\bm{v}},{\bm{u}}}$ and
$\widehat{\mu}{}_{2}=\widehat{\mu}{}_{{\bm{M}},{\bm{G}},{\bm{g}}^{0},{\bm{\xi}}}$.

The continuity property we need is given by the following lemma.

######  Lemma 4.

Consider $\|{\bm{v}}\|\leq 1$ and ${\bm{u}}\in[-1,1]^{n}$. Then there exists
$\mu\in W_{2}({\mathbb{R}}\times(-1,1)^{k+1}\times{\mathbb{R}}^{k+1})$ such
that $\mu_{1}=\widehat{\mu}{}_{1}$, $\mu_{2}=\mathsf{SE}_{{\mathsf{x}},k}$,
and

$\big{|}\mathsf{F}^{(1)}_{{\mathsf{x}},k}(\widehat{\mu}{})-\mathsf{F}^{(1)}_{{\mathsf{x}},k}(\mu)\big{|}\leq\epsilon\big{(}W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)},$
(111)

Moreover, $\mu$ can be chose so that additionally, for
$(U^{(1)},V^{(1)},\breve{\bm{M}}{}^{(1)},\breve{\bm{G}}{}^{(1)},G_{0}^{(1)},\Xi^{(1)})\sim\widehat{\mu}{}$
and
$(U^{(2)},V^{(2)},\allowbreak\breve{\bm{M}}{}^{(2)},\allowbreak\breve{\bm{G}}{}^{(2)},\allowbreak
G_{0}^{(2)},\Xi^{(2)})\sim\mu$,

$\big{|}\big{\|}U^{(1)}-M_{k-1}^{(1)}\big{\|}_{L_{2}}-\big{\|}U^{(2)}-M_{k-1}^{(2)}\big{\|}_{L_{2}}\big{|}\leq
W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k}).$ (112)

###### Proof of Lemma 4.

Throughout the proof, $\epsilon(\,\cdot\,)$ is a function with the properties
described in the lemma, but which may change at each appearance.

Let $\Pi$ be the optimal coupling of $\widehat{\mu}{}_{2}$ and
$\mathsf{SE}_{{\mathsf{x}},k}$ (whose existence is guaranteed by [Vil08,
Theorem 4.1]). By the gluing lemma (see, e.g., [Vil08, pg. 23]), there exist
random variables $U,V$,
$\breve{\bm{M}}{}^{(1)},\breve{\bm{G}}{}^{(1)},G_{0}^{(1)},\Xi^{(1)}$,
$\breve{\bm{M}}{}^{(2)},\breve{\bm{G}}{}^{(2)},G_{0}^{(2)},\Xi^{(2)}$ on a
shared probability space such that
$(U,V,\breve{\bm{M}}{}^{(1)},\breve{\bm{G}}{}^{(1)},G_{0}^{(1)},\Xi^{(1)})\sim\widehat{\mu}{}$
and $(\breve{\bm{M}}{}^{(1)},\breve{\bm{G}}{}^{(1)},\allowbreak
G_{0}^{(1)},\allowbreak\Xi^{(1)},\allowbreak\breve{\bm{M}}{}^{(2)},\allowbreak\breve{\bm{G}}{}^{(2)},G_{0}^{(2)},\Xi^{(2)})\sim\Pi$.
We will show that the result holds for $\mu$ taken equal to the joint
distribution of
$(U,V,\allowbreak\breve{\bm{M}}{}^{(2)},\allowbreak\breve{\bm{G}}{}^{(2)},G_{0}^{(2)},\Xi^{(2)})$
under this coupling.

First observe that the second display of the lemma follows by taking
$U^{(1)}=U^{(2)}=U$ and using that
$\big{\|}M_{k-1}^{(1)}-M_{k-2}^{(2)}\big{\|}_{L_{2}}\leq
W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})$ by the optimality of
the coupling $\Pi$. To derive the first display, observe that we may compute
$\mathsf{F}^{(1)}_{{\mathsf{x}},k}(\widehat{\mu}{})$ by plugging
$U,V,\breve{\bm{M}}{}^{(1)},\breve{\bm{G}}{}^{(1)},G_{0}^{(1)},\Xi^{(1)}$ into
Eq. (44), and we may compute $\mathsf{F}^{(1)}_{{\mathsf{x}},k}(\mu)$ by
plugging
$U,V,\breve{\bm{M}}{}^{(2)},\breve{\bm{G}}{}^{(2)},G_{0}^{(2)},\Xi^{(2)}$ into
Eq. (44), whence

$\displaystyle\big{|}\mathsf{F}^{(1)}_{{\mathsf{x}},k}(\widehat{\mu}{})-\mathsf{F}^{(1)}_{{\mathsf{x}},k}(\mu)\big{|}$
$\displaystyle=2\lambda\big{|}\langle
G_{\mathsf{AMP}}^{(1)},V\rangle_{L_{2}}-\langle
G_{\mathsf{AMP}}^{(2)},V\rangle_{L_{2}}\big{|}\leq
2\lambda\big{\|}G_{\mathsf{AMP}}^{(1)}-G_{\mathsf{AMP}}^{(2)}\big{\|}_{L_{2}},$
(113)

where $G_{\mathsf{AMP}}^{(1)}$ and $G_{\mathsf{AMP}}^{(2)}$ are defined as in
Eq. (43), with respect to
$V,\breve{\bm{M}}{}^{(1)},\breve{\bm{G}}{}^{(1)},\Xi^{(1)}$ and
$V,\breve{\bm{M}}{}^{(2)},\breve{\bm{G}}{}^{(2)},\Xi^{(2)}$, respectively.

Note that
$\lambda^{2}\mathbb{E}\big{[}\breve{\bm{M}}{}^{(2)}\breve{\bm{M}}{}^{(2)\top}\big{]}^{-1}=\bm{K}_{\leq
k}^{-1}$, and because $\bm{K}_{\leq k}\succ 0$,
$\big{\|}\mathbb{E}\big{[}\breve{\bm{M}}{}^{(1)}\breve{\bm{M}}{}^{(1)\top}\big{]}^{-1}-\mathbb{E}\big{[}\breve{\bm{M}}{}^{(2)}\breve{\bm{M}}{}^{(2)\top}\big{]}^{-1}\big{\|}_{{\rm
op}}\leq\varepsilon(\|\breve{\bm{M}}{}^{(1)}-\breve{\bm{M}}{}^{(2)}\|_{L_{2}})\leq\epsilon\big{(}W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)}$.
Similarly,
$\big{\|}\mathbb{E}\big{[}\breve{\bm{M}}{}^{(1)}V\big{]}-\mathbb{E}\big{[}\breve{\bm{M}}{}^{(2)}V\big{]}\big{\|}\leq\epsilon\big{(}W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)}$.
Because also
$\|\breve{\bm{G}}{}^{(1)}-\breve{\bm{G}}{}^{(2)}\|\leq\epsilon\big{(}W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)}$,
repeated application of the Cauchy-Schwartz and triangle inequalities gives

$\big{\|}\breve{\bm{G}}{}^{(1)\top}\mathbb{E}\big{[}\breve{\bm{M}}{}^{(1)}\breve{\bm{M}}{}^{(1)\top}\big{]}^{\dagger}\mathbb{E}\big{[}\breve{\bm{M}}{}^{(1)}V\big{]}-\breve{\bm{G}}{}^{(2)\top}\mathbb{E}\big{[}\breve{\bm{M}}{}^{(2)}\breve{\bm{M}}{}^{(2)\top}\big{]}^{\dagger}\mathbb{E}\big{[}\breve{\bm{M}}{}^{(2)}V\big{]}\big{\|}_{L_{2}}\leq\epsilon\big{(}W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)}.$
(114)

Representing, for $i\in\\{1,2\\}$,
${\mathsf{P}}_{\breve{\bm{M}}{}^{(i)}}^{\perp}V=V-\breve{\bm{M}}{}^{(i)\top}\mathbb{E}\big{[}\breve{\bm{M}}{}^{(i)}\breve{\bm{M}}{}^{(i)\top}\big{]}^{\dagger}\mathbb{E}\big{[}\breve{\bm{M}}{}^{(i)}V\big{]}$,
we can likewise conclude that
$\big{\|}{\mathsf{P}}_{\breve{\bm{M}}{}^{(1)}}^{\perp}V-{\mathsf{P}}_{\breve{\bm{M}}{}^{(2)}}^{\perp}V\big{\|}_{L_{2}}\leq\epsilon\big{(}W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)}$,
whence in fact
$\big{|}\big{\|}{\mathsf{P}}_{\breve{\bm{M}}{}^{(1)}}^{\perp}V\|_{L_{2}}-\|{\mathsf{P}}_{\breve{\bm{M}}{}^{(2)}}^{\perp}V\big{\|}_{L_{2}}\big{|}\leq\epsilon\big{(}W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)}$.
Because also
$\|\Xi^{(1)}-\Xi^{(2)}\|_{L_{2}}\leq\epsilon\big{(}W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)}$
and $\|{\mathsf{P}}_{\breve{\bm{M}}{}^{(2)}}^{\perp}V\big{\|}_{L_{2}}\leq 1$,
we can conclude that

$\big{\|}\|{\mathsf{P}}_{\breve{\bm{M}}{}^{(1)}}^{\perp}V\|_{L_{2}}\Xi^{(1)}-\|{\mathsf{P}}_{\breve{\bm{M}}{}^{(2)}}^{\perp}V\|_{L_{2}}\Xi^{(2)}\big{\|}_{L_{2}}\leq\epsilon\big{(}W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)}.$
(115)

Combining with the previous displays yields the result. ∎

By Proposition 3, as $n\rightarrow\infty$,

$W_{2}\big{(}\widehat{\mu}{}_{{\bm{M}},{\bm{G}},{\bm{g}}^{0},{\bm{\xi}}},\,\mathsf{SE}_{{\mathsf{x}},k}\big{)}\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}0.$
(116)

Now consider ${\bm{v}}\in{\mathbb{R}}^{n}$, ${\bm{u}}\in{\mathbb{R}}^{n}$ with
$\|{\bm{v}}\|\leq 1$ and $\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon$,
and pick $\mu\in
W_{2}({\mathbb{R}}\times(-1,1)^{k+1}\times{\mathbb{R}}^{k+1})$ as in Lemma 4.
Then, for $(U,V,\breve{\bm{M}}{},\breve{\bm{G}}{},G_{0},\Xi)\sim\mu$, we have
$\|V\|_{L_{2}}=\|{\bm{v}}\|=1$ and
$\|U-M_{k-1}\|_{L_{2}}\leq\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}+W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\leq\epsilon+W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})$.
Thus,
$\mu\in{\mathcal{S}}_{{\mathsf{x}},k}^{(1)}\big{(}\epsilon+W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)}$.
Because also
$\mathsf{F}_{{\mathsf{x}},k}^{(1)}({\bm{v}},{\bm{u}};{\bm{M}},{\bm{G}},{\bm{\xi}})\leq\mathsf{F}_{{\mathsf{x}},k}^{(1)}(\mu)+\epsilon(W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k}))$,
we conclude that

$\sup_{\begin{subarray}{c}\|{\bm{v}}\|=1\\\
\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\end{subarray}}\mathsf{F}_{{\mathsf{x}},k}({\bm{v}},{\bm{u}};{\bm{M}},{\bm{G}},{\bm{\xi}})\leq\sup_{\mu\in{\mathcal{S}}_{{\mathsf{x}},k}^{(1)}\big{(}\epsilon+W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\big{)}}\mathsf{F}^{(1)}_{{\mathsf{x}},k}(\mu)+\epsilon(W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})).$
(117)

By Proposition 3,
$W_{2}(\widehat{\mu}{}_{2},\mathsf{SE}_{{\mathsf{x}},k})\stackrel{{\scriptstyle\mathrm{p}}}{{\rightarrow}}=0$
as $n\rightarrow\infty$, we get

$\limsup_{n\rightarrow\infty}\sup_{\begin{subarray}{c}\|{\bm{v}}\|=1\\\
\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\end{subarray}}\mathsf{F}_{{\mathsf{x}},k}({\bm{v}},{\bm{u}};{\bm{M}},{\bm{G}},{\bm{\xi}})\leq\sup_{\mu\in{\mathcal{S}}_{{\mathsf{x}},k}^{(1)}(2\epsilon)}\mathsf{F}^{(1)}_{{\mathsf{x}},k}(\mu).$
(118)

Now taking $k\rightarrow\infty$ followed by $\epsilon\rightarrow 0$, the
result of the lemma follows.

###  B.3 Proof of Theorem 2(ii)

Note that for ${\mathsf{x}}=\mathsf{FMM}$,

$\displaystyle\nabla{\mathcal{F}}_{{\mathsf{x}}}({\bm{m}}^{k-1})$
$\displaystyle=-\frac{\lambda}{n}{\bm{Y}}{\bm{m}}^{k-1}+\frac{1}{n}\tanh^{-1}({\bm{m}}^{k-1})+\frac{\lambda^{2}}{n}(1-Q({\bm{m}}^{k-1})){\bm{m}}^{k-1}$
(119)
$\displaystyle=-\frac{1}{n}({\bm{z}}^{k}-{\bm{z}}^{k-1})+\frac{\lambda^{2}}{n}(1-Q({\bm{m}}^{k-1}))({\bm{m}}^{k-1}-{\bm{m}}^{k-2}).$

By Theorem 2(i), there exists $c,c^{\prime}>0$ such that for any
$\epsilon<c^{\prime}$, there exists large enough $k$ such that, with
probability approaching $1$ as $n\rightarrow\infty$, the TAP free energy is
$c/n$ strongly convex on
$\\{\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\\}\cup[-1,1]^{n}$. Thus,
provided $\|\nabla{\mathcal{F}}_{{\mathsf{x}}}({\bm{m}}^{k-1})\|\leq
c\epsilon/(4\sqrt{n})$, we get that ${\mathcal{F}}_{{\mathsf{x}}}$ has a
unique stationary point ${\bm{m}}^{*}$ on
$\\{\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\\}\cup[-1,1]^{n}$, with
$\|{\bm{m}}^{*}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq(2n/c)\|\nabla{\mathcal{F}}_{{\mathsf{x}}}({\bm{m}}^{k-1})\|/\sqrt{n}\leq\epsilon/2$.
Using that
${\bm{z}}^{s}={\bm{g}}^{s}+\lambda(\langle{\bm{x}},{\bm{m}}^{s-1}\rangle/n){\bm{m}}^{s-1}$,
we have by Proposition 3 that

$\displaystyle\operatorname*{p-lim\,sup}_{n\rightarrow\infty}\frac{1}{\sqrt{n}}\|{\bm{z}}^{k}-{\bm{z}}^{k-1}\|$
$\displaystyle\leq\operatorname*{p-lim}_{n\rightarrow\infty}\Big{\\{}\frac{1}{\sqrt{n}}\|{\bm{g}}^{k}-{\bm{g}}^{k-1}\|+\frac{\lambda^{2}\|{\bm{x}}\|}{\sqrt{n}}\Big{|}\frac{\langle{\bm{x}},{\bm{m}}^{k-1}\rangle}{n}-\frac{\langle{\bm{x}},{\bm{m}}^{k-2}\rangle}{n}\Big{|}\Big{\\}}$
(120)
$\displaystyle=\sqrt{K_{k,k}+K_{k-1,k-1}-2K_{k,k-1}}+|\gamma_{k}-\gamma_{k-1}|=\sqrt{\gamma_{k}-\gamma_{k-1}}+|\gamma_{k}-\gamma_{k-1}|.$

As $k\rightarrow\infty$, the right-hand side converges to 0. Similarly,
letting
$q_{k}=\mathbb{E}[\tanh^{2}(\gamma_{k-1}+\sqrt{\gamma_{k-1}}G)]=(\gamma_{k}-\chi_{{\mathsf{x}}}\gamma_{0})/\lambda^{2}$,
we have

$\operatorname*{p-lim}_{n\rightarrow\infty}(1-Q({\bm{m}}^{k-1}))\frac{\|{\bm{m}}^{k-1}-{\bm{m}}^{k-2}\|}{\sqrt{n}}=(1-q_{k})\sqrt{q_{k}-q_{k-1}},$
(121)

which also goes to 0 as $k\rightarrow\infty$. Thus, for sufficiently large $k$
depending on $\lambda,\gamma_{0},c,\epsilon$, we have
$\|\nabla{\mathcal{F}}_{{\mathsf{x}}}({\bm{m}}^{k-1})\|<c\epsilon/(4\sqrt{n})$
with probability going to 1 as $n\rightarrow\infty$. Thus, we confirmed that
for sufficiently large $k$, ${\mathcal{F}}_{{\mathsf{x}}}$ has a unique
stationary point on
$\\{\|{\bm{u}}-{\bm{m}}^{k-1}\|/\sqrt{n}\leq\epsilon\\}\cup[-1,1]^{n}$ with
high probability. To see that this stationary point must lie also in
$(-1,1)^{n}$, note that as ${\bm{m}}$ converges to the boundary of
$[-1,1]^{n}$, we have $\|\nabla{\mathcal{F}}_{{\mathsf{x}}}({\bm{m}})\|$
diverges to $\infty$, because $\|\tanh^{-1}({\bm{m}})\|$ diverges to $\infty$
and the other terms in $\nabla{\mathcal{F}}_{{\mathsf{x}}}({\bm{m}})$ remain
bounded.

The argument for ${\mathsf{x}}=\mathsf{AMS}$ is nearly equivalent. Now we have

$\displaystyle\nabla{\mathcal{F}}_{{\mathsf{x}}}({\bm{m}}^{k-1})$
$\displaystyle=-\frac{\lambda}{n}{\bm{Y}}{\bm{m}}^{k-1}+\frac{1}{n}\tanh^{-1}({\bm{m}}^{k-1})+\frac{1}{n}{\bm{y}}+\frac{\lambda^{2}}{n}(1-q_{\infty}){\bm{m}}^{k-1}$
(122)
$\displaystyle=-\frac{1}{n}({\bm{z}}^{k}-{\bm{z}}^{k-1})+\frac{\lambda^{2}}{n}(Q({\bm{m}}^{k-1})-q_{\infty}){\bm{m}}^{k-1}+\frac{\lambda^{2}}{n}(1-Q({\bm{m}}^{k-1}))({\bm{m}}^{k-1}-{\bm{m}}^{k-2}).$

The argument then proceeds exactly as before, except we must now deal also
with the term $(\lambda^{2}/n)(Q({\bm{m}}^{k-1})-q_{\infty}){\bm{m}}^{k-1}$,
which we must also show satisfies