# Joint parameter estimations for spin glasses

Wei-Kuo Chen⋆ ,  Arnab Sen† and  Qiang Wu‡ School of Mathematics, University
of Minnesota, 127 Vincent Hall 206 Church St. SE Minneapolis, MN 55455
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
(Date: August 28, 2024)

###### Abstract.

Spin glass models with quadratic-type Hamiltonians are disordered statistical
physics systems with competing ferromagnetic and anti-ferromagnetic spin
interactions. The corresponding Gibbs measures belong to the exponential
family parametrized by (inverse) temperature $\beta>0$ and external field
$h\in\mathbb{R}$. Given a sample from these Gibbs measures, a statistically
fundamental question is to infer the temperature and external field
parameters. In 2007, Chatterjee (Ann. Statist. 35 (2007), no. 5, 1931–1946)
first proved that in the absence of external field $h=0$, the maximum
pseudolikelihood estimator for $\beta$ is $\sqrt{N}$-consistent under some
mild assumptions on the disorder matrices. It was left open whether the same
method can be used to estimate the temperature and external field
simultaneously. In this paper, under some easily verifiable conditions, we
prove that the bivariate maximum pseudolikelihood estimator is indeed jointly
$\sqrt{N}$-consistent for the temperature and external field parameters. The
examples cover the classical Sherrington-Kirkpatrick model and its diluted
variants.

###### Key words and phrases:

Spin glasses, Sherrington-Kirkpatrick model, Pseudolikelihood estimator

###### 2020 Mathematics Subject Classification:

Primary: 62F12, 62F10, 82B44.

##  1\. Introduction and Main Results

Ising model possesses the Gibbs measure that belongs to the bivariate
exponential family and takes the form, for ${\sigma}\in\\{-1,+1\\}^{N}$,

$P_{\beta,h}({\sigma})=\frac{1}{Z_{N}(\beta,h)}\exp(\beta\langle{\sigma},J{\sigma}\rangle+h\langle{\sigma},\boldsymbol{1}\rangle),$

where $\beta>0$ is the (inverse) temperature, $h\in\mathbb{R}$ is the external
field, and $J\in\mathbb{R}^{N}\times\mathbb{R}^{N}$ is a real-valued coupling
matrix. In the past decades, estimation problems for the Ising model have
received a great deal of attention from various communities due to its broad
downstream applications, such as in statistics and computer science etc. One
of the major research branches is, if the coupling matrix $J$ is known, about
estimating $\beta$, $h$, or both from a given sample of the Gibbs measure. One
classical approach to this estimation problem is based on the maximum
likelihood method. In the case of mean field Ising model, also known as Curie-
Weiss model, where $J$ is the adjacency matrix of complete graph with proper
scaling, Comets and Gidas [CG91] showed that for $\beta>0$ and $h\neq 0$, the
maximum likelihood estimator (MLE) for $\beta$ given $h$ or vice versa is
always $\sqrt{N}$-consistent. However, joint estimation of $(\beta,h)$ is
impossible. In some cases, maximum likelihood estimation for the Ising model
can be very challenging since it involves the normalizing constant
$Z_{N}(\beta,h)$ whose computation, in particular, is nontrivial for models
with $J$ having both positive and negative entries. For example, in the
setting of spin glass models, the interaction matrix $J$ consists of random
entries; as a result, understanding the limiting behavior of the log-
normalizing constant as $N\to\infty$ is generally a challenging problem and
only a few cases are solvable in the literature. Arguably, one of the most
intriguing results was the famous Parisi formula [Par79, Par80] that provided
a variational representation for this limit established in the seminal work of
Talagand [Tal06]. Nonetheless, it is still a mystery to understand spin glass
models for large but finite $N$.

Due to the intractability of MLE approach, it is desirable to seek for some
other candidate methods that do not involve computing the log-normalizing
constants. To this end, the pseudolikelihood approach [Bes74, Bes75] was
proposed, where the pseudolikelihood function is defined as the product of
conditional distributions such that the normalizing constant gets cancelled
out. In this case, the maximum pseudolikelihood estimator (MPLE) can indeed
alleviate the issue of dealing with a possibly complicated normalizing
constant.

The MPLE approach has been studied a lot recently due to its efficiency and
simplicity. The first work for the Ising-type model was initiated by
Chatterjee [Chat07], where the author set $h=0$ and considered the single-
parameter estimation problem for $\beta>0$. Under the assumption that $J$ has
bounded operator norm and $\liminf_{N\to\infty}N^{-1}\ln Z_{N}(\beta,h)>0$, it
was shown that the MPLE is $\sqrt{N}$-consistency estimation for $\beta$. In
particular, the result includes examples of spin glasses, such as the
Sherrington-Kirkpatrick (SK) model [SK75] and the Hopfield model [Hop82].
Afterwards, the result of [Chat07] was extended to other generalized Ising
models [BM18, MSB22]. All those results have been restricted to the single
parameter estimation setting. As we saw in the Curie-Weiss model, joint
estimation is generally a much more challenging task. In fact, sometimes MPLE
does not be even exist as opposed to the scenario for the single parameter.
Incidentally, extending the single parameter estimation results to the joint
parameters estimation setting was proposed as one of the open problems by
Chatterjee [Chat07]. An attempt to resolve this question was obtained by
Ghosal and Mukherjee [GM20] in the setting of the ferromagnetic Ising model
where $J$ has nonnegative entries and they established a set of sufficient
conditions under which joint estimation for $(\beta,h)$ is possible with
$\sqrt{N}$-consistency.

In this paper, we aim to show that MPLE is a $\sqrt{N}$-jointly consistent
estimator for $(\beta,h)$ allowing $J$ to possess positive and negative
entries. More precisely, the matrix $J$ is a weighted adjacency matrix of a
graph, where the weights are i.i.d. centered random variable with finite third
moment and the graph requires that its averaging degree diverges at least
logarithmically fast and is comparable to the maximum degree. This setting
covers a collection of spin glass models such as the celebrated SK model and
its diluted variants. We show that the validity of our result requires
checking three major conditions: the non-flatness of the free energy, the
boundedness of the operator norm of $J$, and the positivity of the Hessian
matrix of the pseudolikelihood function, see Theorem 1.1. Among them, the
third condition plays a central role and it also appeared in [GM20].
Incidentally, the authors therein verified this positivity condition
critically relying on the nonnegativity assumption of coupling coefficients
which allowed them to use the nonlinear large deviation theory for random
graphs [CD16, BM17, EG18, Chat17]. However, such technique does not seem to
work when the coupling matrix $J$ has both positive and negative entries.
Until now, it remained as a main obstacle to extend joint estimation results
beyond the non-negative coupling coefficients setting. We are able to check
the non-singularity condition with high probability in the setting of random
coupling matrices via the small ball probability arguments [RV08, Ver14].

###  1.1. Notation

Let $\mathcal{G}:=([N],E)$ be a graph with vertex set $[N]=\\{1,2,\ldots,N\\}$
and edge set $E$. Denote by $d_{i}$ and $d$ the _degree_ of vertex $i\in[N]$
and the _average degree_ of $\mathcal{G}$, respectively. In addition,
$d_{\max}:=\max_{i\in[N]}d_{i}$ denotes the _maximum degree_ of $\mathcal{G}$.
Let $G=(g_{ij})_{i,j=1}^{N}$ be a symmetric matrix and vanishes along the
diagonal, _i.e.,_ $g_{ii}=0$ for $i\in[N]$. Set

$\displaystyle J:=\frac{1}{\sqrt{d}}A\circ G,$ (1)

where $\circ$ denotes the Hadmard product and $A$ is the adjacency matrix of
$\mathcal{G}$, that is,

$\displaystyle A_{ij}=\begin{cases}1,\quad\text{if $(i,j)\in E$},\\\
0,\quad\text{if $i=j$ or $(i,j)\notin E$. }\end{cases}$

If $U_{N}$ and $V_{N}$ are two non-negative random variables sampled from some
probability measure $P$, we say $U_{N}=O_{p}(V_{N})$ if
$(U_{N}/V_{N})_{N\geqslant 1}$ is a tight family under $P$, i.e., for each
$\epsilon>0$, there exists $C$ such that

$P(U_{N}/V_{N}\leqslant C)\geqslant 1-\epsilon\ \ \text{ for all }N\geqslant
1.$

The notation $\Omega_{p}$ is defined similarly.

###  1.2. Basic Setting of MPLE

For any $\beta>0,h\in\mathbb{R}$, the Gibbs measure associated to $J$ is
defined as

$\displaystyle P_{\beta,h}({\sigma})=\frac{\exp(\beta\langle
J{\sigma},{\sigma}\rangle/2+h\langle{\sigma},\boldsymbol{1}\rangle)}{Z_{N}(\beta,h)},$
(2)

for all ${\sigma}\in\Sigma_{N}:=\\{-1,+1\\}^{N}$, where

$Z_{N}(\beta,h)=\sum_{{\sigma}\in\Sigma_{N}}\exp(\beta\langle
J{\sigma},{\sigma}\rangle/2+h\langle{\sigma},\boldsymbol{1}\rangle)$

is the normalizing constant, also known as the partition function in
statistical physics. For any $\tau\sim P_{\beta,h}$ and
$f:\Sigma_{N}\to\mathbb{R}$, denote by $\langle f(\tau)\rangle$ the
expectation of $f(\tau)$ with respect to the Gibbs measure. The free energy is
defined as

$\displaystyle F_{N}(\beta,h)=\frac{1}{N}\log Z_{N}(\beta,h).$ (3)

We proceed to formulate the MPLE for $(\beta,h).$ In the sequel, we assume
that $\beta_{0},h_{0}$ are the ground truth parameters and a sample
${\tau}\sim P_{\beta_{0},h_{0}}(\cdot)$. For ${\sigma}\in\\{-1,+1\\}^{N}$, the
_pseudolikelihood function_ is defined as

$\displaystyle L(\beta,h|{\sigma})$
$\displaystyle=\log\prod_{i=1}^{N}P_{\beta,h}(\sigma_{i}|\sigma_{j\neq i})$
$\displaystyle=\sum_{i=1}^{N}\sigma_{i}\Bigl{(}\beta\sum_{j=1}^{N}J_{ij}\sigma_{j}+h\Bigr{)}-\sum_{i=1}^{N}\log\cosh\Bigl{(}\beta\sum_{j\neq
i}J_{ij}\sigma_{j}+h\Bigr{)}-\log 2.$ (4)

Taking the partial derivatives of the pseudolikelihood function w.r.t. the
parameters $\beta,h$, we have the corresponding _score functions_ ,

$\displaystyle S(\beta,h|{\sigma})$ $\displaystyle:=\frac{\partial
L}{\partial\beta}=\sum_{i=1}^{N}m_{i}({\sigma})(\sigma_{i}-\tanh(\beta
m_{i}({\sigma})+h)),$ (5) $\displaystyle Q(\beta,h|{\sigma})$
$\displaystyle:=\frac{\partial L}{\partial
h}=\sum_{i=1}^{N}(\sigma_{i}-\tanh(\beta m_{i}({\sigma})+h)),$ (6)

where

$m_{i}({\sigma}):=\sum_{j=1}^{N}J_{ij}\sigma_{j}=\sum_{j\neq
i}J_{ij}\sigma_{j}.$

We further compute the negative Hessian matrix $H(\beta,h|{\sigma})$ for later
use as

$\displaystyle
H(\beta,h|{\sigma}):=\begin{pmatrix}&\sum_{i=1}^{N}m_{i}({\sigma})^{2}\theta_{i}(\beta,h|{\sigma})^{2}&\sum_{i=1}^{N}m_{i}({\sigma})\theta_{i}(\beta,h|{\sigma})^{2}\\\
&\sum_{i=1}^{N}m_{i}({\sigma})\theta_{i}(\beta,h|{\sigma})^{2}&\sum_{i=1}^{N}\theta_{i}(\beta,h|{\sigma})^{2}\end{pmatrix},$
(7)

where for $i\in[N],$
$\theta_{i}(\beta,h|{\sigma}):=\operatorname{sech}^{2}(\beta
m_{i}({\sigma})+h).$ From a straightforward computation, the determinant of
the Hessian is

$\left|H(\beta,h|{\sigma})\right|=\frac{N^{2}}{2}\widetilde{T}_{N}(\beta,h|{\sigma}),$

where

$\displaystyle\widetilde{T}_{N}(\beta,h|{\sigma}):=\frac{1}{N^{2}}\sum_{i,j\in[N]}\theta_{i}({\sigma})\theta_{j}({\sigma})(m_{i}({\sigma})-m_{j}({\sigma}))^{2}.$
(8)

A quantity accompanied with $\widetilde{T}_{N}(\beta,h|{\sigma})$ is

$\displaystyle
T_{N}(\beta,h|{\sigma}):=\frac{1}{N^{2}}\sum_{i,j\in[N]}(m_{i}({\sigma})-m_{j}({\sigma}))^{2}=\frac{2}{N}\sum_{i\in[N]}(m_{i}({\sigma})-\bar{{m}}({\sigma}))^{2},$
(9)

where

$\bar{{m}}({\sigma}):=\frac{1}{N}\sum_{i\in[N]}m_{i}({\sigma}).$

For notational brevity, we will often suppress the dependence of
$\theta_{i},T_{N},$ and $\widetilde{T}_{N}$ on $\beta$ and $h$.

We assume that the coupling matrix $J$ is given and we have access to a single
sample from the ground truth $P_{\beta_{0},h_{0}}$. Our ultimate aim is to
determine the conditions on the model so that the pseudolikelihood estimator
exists and is consistent. The following theorem presents a set of sufficient
conditions to attend this purpose.

######  Theorem 1.1 (Existence and consistency of MPLE).

Suppose that the coupling matrix $J\in\mathbb{R}^{N\times N}$ is symmetric and
has zeros entries along the diagonal. For fixed $\beta_{0}>0$ and
$h_{0}\in\mathbb{R}$, let ${\tau}\in\\{-1,+1\\}^{N}$ be a sample drawn from
the Gibbs measure $P_{\beta_{0},h_{0}}$. Assume that the following conditions
hold.

  1. $(i)$

Non-flatness of the limiting free energy $:$ There exists some
$0<\beta^{\prime}<\beta_{0}$ such that

$\displaystyle\liminf_{N\to\infty}(F_{N}(\beta^{\prime},h_{0})-F_{N}(0,h_{0}))>0.$

  2. $(ii)$

Boundedness of $J$$:$

$\displaystyle\|J\|=O(1),$

where $\|J\|$ is the operator norm of $J$.

  3. $(iii)$

Positivity of the Hessian $:$ Under $P_{\beta_{0},h_{0}}$,

$\displaystyle\widetilde{T}_{N}({\tau})=\widetilde{T}_{N}(\beta_{0},h_{0}|{\tau})=\Omega_{p}(1).$

Then with $P_{\beta_{0},h_{0}}$-probability tending to one, the MPLE exists,
i.e., the bivariate equation

$\displaystyle(S(\beta,h|{\tau}),Q(\beta,h|{\tau}))=(0,0),$ (10)

has a unique solution
$(\hat{\beta}({\tau}),\hat{h}({\tau}))\in\mathbb{R}^{2}$. Moreover,
$(\hat{\beta}({\tau}),\hat{h}({\tau}))$ is a $\sqrt{N}$-consistent estimator
of the ground truth $(\beta_{0},h_{0})$ in the sense that under
$P_{\beta_{0},h_{0}}$,

$\|(\hat{\beta}({\tau})-\beta_{0},\hat{h}({\tau})-h_{0})\|_{2}=O_{p}(N^{-1/2}).$

Note that this theorem holds for arbitrary real-valued symmetric matrices $J$
with zeros along the diagonal and they do not need to be of the form (1).

######  Remark 1.2.

Under different assumptions, Ghosal-Mukherjee [GM20] obtained similar
existence and consistency results as Theorem 1.2, where the matrix $J$ has
nonnegative entries and uniformly bounded row sums. Our proof for the
consistency part in Theorem 1.1 is similar to that of [GM20]*Theorem 1.2.
However, the approach for the existence part in the same theorem does not
apply to our setting.

######  Remark 1.1.

If $h=0$, Theorem 1.1 reduces to the single parameter estimation problem for
$\beta$ studied in [Chat07] and it was known that the conditions (i) and (ii)
imply the invertibility of the corresponding score function analogous to
(iii). However, in the joint estimation problem, (i) and (ii) are not enough
to imply (iii) as can be seen in the Curie-Weiss model.

###  1.3. Main Results

Our work considers the setting of the disordered spin system, namely, $G$ is a
symmetric matrix of independent random entries. The main result establishes
three major theorems that validate the conditions (i), (ii), and (iii) in
Theorem 1.1 individually with high probability. As a consequence, we conclude
that the pseudolikelihood estimator exists and is $\sqrt{N}$-consistent in the
joint estimation problem. To state our main results, we begin by introducing
the following assumption on the graph structure $\mathcal{G}$.

######  Assumption 1.3.

For the underlying graph $\mathcal{G}=([N],E)$, we assume the average degree
$d$ and the maximum degree $d_{\max}$ satisfy

  1. $(i)$

$d\gg\log N$,

  2. $(ii)$

$d_{\max}\leqslant Cd$,

where $C>0$ is a constant independent of $N.$

Heuristically, the above condition specifies that the underlying graph can
neither be too sparse nor have some vertices with very large degrees. Recall
that a random variable $X$ is $\kappa^{2}$-subgaussian if $\mathbb{E}X=0$ and
$\mathbb{E}e^{sX}\leqslant e^{\kappa^{2}s^{2}/2}$ for all $s\in\mathbb{R}.$ We
say that $G=(g_{ij})_{i,j\in[N]}$ is a symmetric $\kappa^{2}$-subgaussian
matrix with vanishing diagonal if its upper triangular entries are independent
$\kappa^{2}$-subgaussian. Now we state the first result that verifies the non-
flatness of the free energy in temperature.

######  Theorem 1.4.

Suppose that $G$ is a symmetric $\kappa^{2}$-subgaussian matrix with vanishing
diagonal and Assumption 1.3 $(i)$ is in force. Then for any $\beta>0$ and
$h\in\mathbb{R}$, there exist positive constants $c_{0},c,K$ independent of
$N$ such that

$\mathbb{P}\bigl{(}F_{N}(\beta,h)-F_{N}(0,h)\leqslant c_{0}\bigr{)}\leqslant
K\exp(-cN).$

The next result establishes the bounednedness of the operator norm $J$.

######  Theorem 1.5.

Suppose that $G$ is a symmetric $\kappa^{2}$-subgaussian matrix with vanishing
diagonal and Assumption 1.3 holds. Then there exist constants $C,K>0$,
depending on $\kappa$, such that

$\mathbb{P}(\left\|J\right\|\geqslant C)\leqslant K\exp(-d/\log N).$

As we shall see below, the proofs for these two theorems are not too
difficult, which borrow some standard ideas and results from the treatment of
the Ising model as well as the concentration inequalities for sparse random
matrices [BvH16, CDG23]. The much more difficult component of this work lies
on the verification of the strict positivity of the Hessian stated below.

######  Theorem 1.6.

Suppose that $G$ is a symmetric random matrix with vanishing diagonal so that
its upper triangular entries satisfy

$\displaystyle\text{$(g_{ij})_{i>j}$ are independent with}\
\operatorname{\mathds{E}}{g_{ij}}=0,\,{\operatorname{\mathds{E}}[g_{ij}^{2}]}=1,\,\text{and}\,\operatorname{\mathds{E}}|g_{ij}|^{3}\leqslant
B,$ (11)

where $B>0$ is some finite constant independent of $N$. Furthermore, suppose
that Assumption 1.3 $(i)$ is satisfied and $d\to\infty$ as $N\to\infty$. Then
there exist positive constants $c_{0},c$, and $K$ such that

$\mathbb{P}\bigl{(}\min_{{\sigma}}\widetilde{T}_{N}({\sigma})\leqslant
c_{0}\bigr{)}\leqslant K\exp(-cN).$

For the sample ${\tau}$ from ground truth $P_{\beta_{0},h_{0}}$, obviously
$\widetilde{T}_{N}({\tau})\geqslant\min_{{\sigma}}\widetilde{T}_{N}({\sigma})$
holds. The above theorem suggests that $\widetilde{T}_{N}({\tau})\leqslant
c_{0}$ holds with exponentially decaying annealed probability.

######  Remark 1.7.

If the minimization is over a continuous sphere
$S_{N}:=\\{{\sigma}\in\mathbb{R}^{N}:\|{\sigma}\|^{2}=N\\}$ instead of
discrete cube $\\{-1,+1\\}^{N}$, then the statement of Theorem 1.6 is not true
any more. For example, if $J$ is nonsingular with probability one, which, in
particular, holds for the SK model, then we take ${\sigma}^{*}=\gamma
J^{-1}\mathbf{1}$ for $\gamma:=N^{-1/2}\left\|J^{-1}\mathbf{1}\right\|$, so
that $m({\sigma}^{*})=\gamma\mathbf{1}$ and consequently,

$\widetilde{T}_{N}({\sigma}^{*})\leqslant T_{N}({\sigma}^{*})=0.$

Therefore, we always have

$\min_{{\sigma}\in S_{N}}\widetilde{T}_{N}({\sigma})=0.$

As of now, with high probability, all three conditions in Theorem 1.1 have
been verified under varying assumptions. Putting them all together, we obtain
the asserted joint estimation for $(\beta,h).$

######  Theorem 1.8.

For $\beta_{0}>0$ and $h_{0}\in\mathbb{R}$, suppose ${\tau}\sim
P_{\beta_{0},h_{0}}$. Suppose that

  1. $(1)$

$G$ is a symmetric $\kappa^{2}$-subgaussian random matrix with vanishing
diagonal,

  2. $(2)$

Assumption 1.3 holds.

Then with $\mathbb{P}$-probability tending to one, the bivariate MPLE,
$(\hat{\beta}({\tau}),\hat{h}({\tau})),$ is jointly $\sqrt{N}$-consistent.

######  Example 1.9.

Letting the upper triangular entries of $G$ being i.i.d. standard Gaussian,
Theorem 1.8 covers the classical SK model, for which $\mathcal{G}$ is a
complete graph so that $d_{\max}=d=N-1\gg\log N$ satisfying Assumption 1.3.
Another example is the diluted SK model, where $\mathcal{G}$ is a sparse
Erdös-Rényi random graph $\mathcal{G}=G(N,p_{N})$ with $p_{N}\gg{\log N}/{N}$.

###  1.4. Proof Sketches

Theorem 1.1 consists of existence and consistency parts. The latter follows
from a standard Delta method argument similar to [GM20]*Theorem 1.2. For
existence, note that if the pseudolikelihood function diverges to the negative
infinity as $|\beta|+|h|\to\infty$, then it has a unique maximizer (i.e., the
MPLE exists) as it is already strictly concave thanks to the condition (iii).
Almost the entirety of the proof of existence part is devoted to showing this
divergence. We prove that this is indeed true if
$(\tau_{i},m_{i}(\tau))_{i\in[N]}$ contains all possible signs. We then show
that this property holds w.h.p. under the assumptions $(i)$ and $(ii)$. Even
though this is intuitively clear since the spins and the fields $m_{i}$ should
not be in favor of certain choices of signs overwhelmingly, proving it
rigorously takes some effort. The key role is played by a general
concentration result, see Lemma 2.1 below, which says that for $\tau\sim
P_{\beta,h}$ and any suitably Lipschitz function $f$, the linear statistics
$N^{-1}\sum_{i=1}^{N}f(\tau_{i},\tau_{i}m_{i}(\tau))$ stays around its
conditional mean $N^{-1}\sum_{i=1}^{N}\langle
f(\tau_{i},\tau_{i}m_{i}(\tau))|\tau_{l},\forall l\neq i\rangle.$ As an
immediate consequence, our lemma implies the concentration for the score
functions $S(\beta,h|\tau)$ and $Q(\beta,h|\tau)$ (see Corollary 2.2 below),
which was previously established in [Chat07] using Stein’s method for
exchangeable pairs. Our result holds for more general functions and its proof
relies on the cavity argument instead.

For Theorem 1.4, it suffices to show that
$\operatorname{\mathds{E}}F_{N}(\beta,h)$ is strictly increasing in $\beta>0$
since this quantity is concentrated. To this end, we first show that the
expected free energy is universal in the sense that
$\operatorname{\mathds{E}}F_{N}(\beta,h)$ is asymptotically the same between
Gaussian and subgaussian matrices with proper matching moments. Now for the
free energy with Gaussian disorder, one can use the Gaussian integration by
parts and then a standard cavity computation to write

$\displaystyle\partial_{\beta}\operatorname{\mathds{E}}F(\beta,h)$
$\displaystyle=\frac{\beta^{2}}{2}\Bigl{(}1-\frac{2}{Nd}\sum_{(i,j)\in
E}\operatorname{\mathds{E}}\langle\sigma_{i}^{1}\sigma_{j}^{1}\sigma_{i}^{2}\sigma_{j}^{2}\rangle\Bigr{)}$
$\displaystyle=\frac{\beta^{2}}{2}\Bigl{(}1-\frac{2}{Nd}\sum_{(i,j)\in
E}\operatorname{\mathds{E}}\bigl{\langle}\tanh(\beta
m_{i}(\sigma)+h)\sigma_{j}\bigr{\rangle}^{2}\Bigr{)}.$

The crucial observation that we will establish below is that with high
probability, if ${\sigma}\sim P_{\beta,h}(\cdot)$, then there exists a vertex
subset $U=U({\sigma})\subseteq[N]$ that is of linear size and the fields
$(m_{i}({\sigma}))_{i\in U}$ are uniformly bounded by an absolute constant.
Additionally, each $i\in U$ satisfies $d_{i}\geqslant d/4$. Using these, we
readily see that $\partial_{\beta}\mathbb{E}F(\beta,h)\geqslant c$ for some
universal constant $c$ as long as $\beta$ is small enough and yields non-
flatness of $F_{N}(\beta,h)$. The proof of Theorem 1.5 follows
straightforwardly by using the asymptotic results [BvH16] and the
concentration bound [CDG23] for the operator norm of sparse subgaussian
matrices.

The proof of Theorem 1.6 is the central ingredient of this work. For
simplicity, let us sketch an argument to show that

$\mathbb{P}\bigl{(}\min_{{\sigma}}T_{N}({\sigma})\leqslant
c_{0}\bigr{)}\leqslant K\exp(-cN).$

We will prove the above by taking a union bound over the spin configuration
${\sigma}\in\\{-1,1\\}^{N}$. Notice that

$T_{N}({\sigma})=\frac{2}{N}\sum_{i\in[N]}(m_{i}({\sigma})-\bar{{m}}({\sigma}))^{2}=\frac{2}{N}\inf_{\gamma\in\mathbb{R}}\left\|{m}({\sigma})-\gamma\boldsymbol{1}\right\|_{2}^{2},$
(12)

It is easy to check using Markov inequality that
$\|{m}({\sigma})\|_{\infty}\leqslant M:=2^{N}$ with probability at least
$1-C(1.5)^{-N}$. On this event, the infimum over $\gamma$ in (12) can be
restricted to the interval $[-M,M]$, which can further be approximated by
taking minima over an $\epsilon$-net $\mathcal{D}$ of size
$O(2^{N}\varepsilon^{-1})$ for small but constant $\epsilon>0$. Therefore, it
suffices to show that uniformly for any ${\sigma}\in\\{-1,1\\}^{N}$ and any
$\gamma\in\mathcal{D}$,

$\mathbb{P}\bigl{(}\left\|{m}({\sigma})-\gamma\boldsymbol{1}\right\|_{2}\leqslant
c_{1}\sqrt{N}\bigr{)}\leqslant K10^{-N}$ (13)

for appropriate positive constant $c_{1}$. The event on the left-hand side can
immediately be recognized as a small ball probability event. Had the entries
of $J$ been independent, the local fields $m_{i}({\sigma})$ were independent.
In that case, we can use the standard small ball probability result (e.g.,
Berry-Esseen theorem) for the linear combinations of independent random
variables to infer that for each $i$, the probability that
$|m_{i}({\sigma})-\gamma|<c_{1}$ is at most $1/10$ for sufficiently small
$c_{1}$ and then tensorizes the bound to obtain (13). However, since $J$ is
symmetric, $m_{i}({\sigma})$ are not independent anymore and the tensorization
breaks down.

To overcome this obstacle, we borrow an idea from [Ver14]. We only use the
randomness of a principal submatrix of $J$ of linear size while conditioning
out the rest of the entries. Let $T\subset[N]$ be the set of the row (and the
column) indices belonging to this principal submatrix, which we denote by
$J_{T}$. Dealing with this smaller matrix instead of $J$ has the critical
advantage that the entries of $J_{T}$ are independent (as long as
$|T|\leqslant N/2$). We can then apply the previous small ball probability
argument for $J_{T}\sigma_{T}$. However, successfully implementing this
strategy requires that the matrix $J_{T}$ is not too sparse in the sense that
in the graph $\mathcal{G}$ the number of edges between each vertex of $T$ and
$[N]\setminus T$ tends to $\infty$ as $N\to\infty$. We apply Erdös’
probabilistic method to guarantee the existence of such a ‘good’ deterministic
set $T$ provided $\mathcal{G}$ satisfies Assumption 1.3$(i)$ and $d\to\infty$
as $N\to\infty$. This gives the lower bound for
$\min_{{\sigma}}T_{N}({\sigma})$.

The original term $\widetilde{T}_{N}({\sigma})$ has an additional complication
since $\theta_{i}({\sigma}):=\operatorname{sech}^{2}(\beta m_{i}({\sigma})+h)$
can be small if $m_{i}({\sigma})$ is big. However, it can be shown that with
overwhelming probability, there exists a (random) linear subset of indices of
$T$ satisfying $|m_{i}({\sigma})|\leqslant C$, which then yields the lower
bound for $\min_{{\sigma}}\widetilde{T}_{N}({\sigma})$ as it follows from the
previous step that the local fields $(m_{i}({\sigma}))_{i\in T}$ have
sufficient variability.

###  1.5. Structure of the paper.

In the order their statements appear, the proofs for Theorems 1.1, 1.4, 1.5,
and 1.6 are accordingly located in Sections 2, 3, 4, and 5.

###  1.6. Acknowledgements.

W-KC is partly supported by NSF grants DMS-1752184 and DMS-2246715 and Simons
Foundation grant 1027727. He also thanks the hospitality of National Center
for Theoretical Sciences in Taiwan during his visit between May 6-10, 2024,
where part of this work was completed. AS is partly supported by Simons
Foundation MP-TSM-00002716. QW and AS would like to thank Sumit Mukherjee for
helpful discussions.

##  2\. Proof of Theorem 1.1

The proof of Theorem 1.1 contains the existence and consistency of the MPLE.
The latter is deferred to Section 2.3. For the existence part, as mentioned in
the proof sketches, it suffices to show that the pseudolikelihood function
diverges to negative infinity at infinity. We verify this property in Section
2.2 based on a number of lemmas established in the following subsection.

###  2.1. Auxiliary Lemmas

Let $\beta>0$ and $h\in\mathbb{R}$. Let $f(x,y)$ be defined on
$\\{-1,1\\}\times\mathbb{R}$. For any $i\in[N]$ and ${\sigma}\in\Sigma_{N},$
set

$\displaystyle L_{i}({\sigma})$ $\displaystyle=\langle
f(\tau_{i},\tau_{i}m_{i}(\tau))|\tau_{l}=\sigma_{l},\forall l\neq i\rangle$
$\displaystyle=\frac{e^{\beta m_{i}({\sigma})+h}f(1,m_{i}({\sigma}))+e^{-\beta
m_{i}({\sigma})-h}f(-1,-m_{i}({\sigma}))}{e^{\beta
m_{i}({\sigma})+h}+e^{-\beta m_{i}({\sigma})-h}},$

where $\langle\cdot\rangle$ is the Gibbs expectation with respect to $\tau\sim
P_{\beta,h}.$ Our first lemma establishes the following concentration for the
linear statistics of $(\tau_{i},\tau_{i}m_{i}(\tau))_{i\in[N]}.$

######  Lemma 2.1.

Let ${\tau}$ be sampled from $P_{\beta,h}$ for some $\beta>0$ and
$h\in\mathbb{R}$. Assume that $f(x,y)$ be defined on
$\\{-1,1\\}\times\mathbb{R}$ and satisfies $\|f\|_{\infty}\leqslant 1,$
$\|\partial_{y}f\|_{\infty}<\infty$, and
$\|\partial_{y}^{2}f\|_{\infty}<\infty.$ For any $N\geqslant 1,$ we have that

$\displaystyle\Bigl{\langle}\Bigl{(}\sum_{i=1}^{N}\bigl{(}f(\tau_{i},\tau_{i}m_{i}({\tau}))-L_{i}({\tau})\bigr{)}\Bigr{)}^{2}\Bigr{\rangle}$
$\displaystyle\leqslant 4N+C_{1}N\|J\|+\frac{C_{2}}{2}N\|J\|^{2},$ (14)

where

$\displaystyle C_{1}$ $\displaystyle:=2\beta+\|\partial_{y}f\|_{\infty},$
$\displaystyle C_{2}$
$\displaystyle:=2\beta+5\beta^{2}+2\beta\|\partial_{y}f\|_{\infty}+\|\partial_{y}^{2}f\|_{\infty}.$

As an immediate corollary of this lemma with $f(x,y)=y$ and $f(x,y)=x$, we
have

######  Corollary 2.2 (Second moment bounds for score functions).

Assume that $\|J\|=O(1).$ Then there exists a constant $C$ such that

$\langle(S(\beta,h|{\tau}))^{2}\rangle\leqslant CN,\ \
\langle(Q(\beta,h|{\tau}))^{2}\rangle\leqslant CN,$

where $S$ and $Q$ are defined in (5) and (6).

###### Proof of Lemma 2.1.

Let distinct $i,j\in[N]$ be fixed. Set

$m_{j}^{(i)}({\sigma}):=\sum_{k\neq i,j}J_{jk}\sigma_{k}$

and $L^{(i)}_{j}({\sigma})$ is same as $L_{j}({\sigma})$ with
$m_{j}({\sigma})$ replaced by $m_{j}^{(i)}({\sigma})$. Since $L_{i}(\tau)$ is
the expectation of $f(\tau_{i},\tau_{i}m_{i}({\tau}))$ conditionally on
$(\tau_{l})_{l\neq i}$, we have

$\displaystyle\bigl{\langle}\bigl{(}f(\tau_{i},\tau_{i}m_{i}({\tau}))-L_{i}({\tau})\bigr{)}\bigl{(}f(\tau_{j},\tau_{j}m_{j}({\tau}))-L_{j}^{(i)}({\tau})\bigr{)}\bigr{\rangle}=0,$

which implies

$\displaystyle\bigl{\langle}\bigl{(}f(\tau_{i},\tau_{i}m_{i}({\tau}))-L_{i}({\tau})\bigr{)}\bigl{(}f(\tau_{j},\tau_{j}m_{j}({\tau}))-L_{j}({\tau})\bigr{)}\bigr{\rangle}$
$\displaystyle=\bigl{\langle}c_{ij}({\tau})(f(\tau_{i},\tau_{i}m_{i}({\tau}))-L_{j}({\tau}))\bigr{\rangle},$

where

$c_{ij}({\tau}):=L_{j}^{(i)}({\tau})-L_{j}({\tau}).$

Now, using Taylor expansion,

$\displaystyle\bigl{|}L_{j}^{(i)}({\tau})-L_{j}({\tau})+J_{ij}\partial_{J_{ij}}L_{j}({\tau})\bigr{|}$
$\displaystyle\leqslant\frac{J_{ij}^{2}}{2}\max_{J_{ij}\in\mathbb{R}}\bigl{|}\partial_{J_{ij}}^{2}L_{j}({\tau})\bigr{|}.$

Here,

$\displaystyle\partial_{J_{ij}}L_{j}({\tau})$ $\displaystyle=\frac{e^{\beta
m_{j}({\tau})+h}\partial_{y}f(1,m_{j}({\tau}))+e^{-\beta
m_{j}({\sigma})-h}\partial_{y}f(-1,-m_{j}({\tau}))}{e^{\beta
m_{j}({\tau})+h}+e^{-\beta m_{j}({\tau})-h}}$
$\displaystyle+\beta\frac{e^{\beta
m_{j}({\tau})+h}f(1,m_{j}({\tau}))-e^{-\beta
m_{j}({\tau})-h}f(-1,-m_{j}({\tau}))}{e^{\beta m_{j}({\tau})+h}+e^{-\beta
m_{j}({\tau})-h}}$ $\displaystyle-\beta\frac{e^{\beta
m_{j}({\tau})+h}f(1,m_{j}({\tau}))+e^{-\beta
m_{j}({\tau})-h}f(-1,-m_{j}({\tau}))}{e^{\beta m_{j}({\tau})+h}+e^{-\beta
m_{j}({\tau})-h}}\tanh(\beta m_{j}({\tau})+h)$

and

$\displaystyle|\partial_{J_{ij}}L_{j}({\tau})|$ $\displaystyle\leqslant
C_{1}:=2\beta+\|\partial_{y}f\|_{\infty}.$

Since $\partial_{J_{ij}}L_{j}({\tau})$ is independent of $i,$ it follows that

$\displaystyle\Bigl{|}\sum_{i\neq
j}J_{ij}\partial_{J_{ij}}L_{j}({\tau})\Bigr{|}=\Bigl{|}\sum_{i,j=1}^{N}J_{ij}\partial_{J_{ij}}L_{j}({\tau})\Bigr{|}$
$\displaystyle\leqslant C_{1}N\|J\|.$

On the other hand, since

$\displaystyle|\partial_{J_{ij}}^{2}L_{j}({\tau})|$ $\displaystyle\leqslant
C_{2}:=2\beta+5\beta^{2}+2\beta\|\partial_{y}f\|_{\infty}+\|\partial_{y}^{2}f\|_{\infty},$

we have

$\displaystyle\Bigl{|}\sum_{i\neq
j}J_{ij}^{2}\partial_{J_{ij}}^{2}L_{j}({\tau})\Bigr{|}=\Bigl{|}\sum_{i,j=1}^{N}J_{ij}^{2}\partial_{J_{ij}}^{2}L_{j}({\tau})\Bigr{|}$
$\displaystyle\leqslant C_{2}\sum_{i,j=1}^{N}J_{ij}^{2}=C_{2}{\bf
1}^{T}(J\circ J){\bf 1}\leqslant C_{2}N\|J\circ J\|\leqslant C_{2}N\|J\|^{2}.$

From these, we arrive at

$\displaystyle\sum_{i\neq j}|c_{ij}({\tau})|\leqslant
C_{1}N\|J\|+\frac{C_{2}}{2}N\|J\|^{2}$

and thus,

$\displaystyle\sum_{i\neq
j}\bigl{\langle}\bigl{(}f(\tau_{i},\tau_{i}m_{i}({\tau}))-L_{i}({\tau})\bigr{)}\bigl{(}f(\tau_{j},\tau_{j}m_{j}({\tau}))-L_{j}({\tau})\bigr{)}\bigr{\rangle}$
$\displaystyle\leqslant C_{1}N\|J\|+\frac{C_{2}}{2}N\|J\|^{2}.$

This readily yields our assertion. $\blacksquare$

Let $0<\delta<M$ be fixed. Let $\rho$ be a nonnegative twice differentiable
function on $\mathbb{R}$ with $\rho\equiv 1$ on $(\delta,\infty)$, $\rho\equiv
0$ on $(-\infty,0)$, and
$\|\rho^{\prime}\|_{\infty},\|\rho^{\prime\prime}\|_{\infty}<\infty$. Also,
let $\bar{\rho}$ be a nonnegative twice differentiable function on
$\mathbb{R}$ with $\bar{\rho}\equiv 1$ on $(-\infty,-\delta)$,
$\bar{\rho}\equiv 0$ on $(0,\infty)$, and
$\|\bar{\rho}^{\prime}\|_{\infty},\|\bar{\rho}^{\prime\prime}\|_{\infty}<\infty.$
Define $f(x,y)=x\rho(y)$ and $\bar{f}(x,y)=x\bar{\rho}(y).$ Set

$\displaystyle\Delta(x,z)$ $\displaystyle=f(x,xz)-\frac{e^{\beta
z+h}f(1,z)+e^{-\beta z-h}f(-1,-z)}{e^{\beta z+h}+e^{-\beta z-h}},$
$\displaystyle\bar{\Delta}(x,z)$ $\displaystyle=\bar{f}(x,xz)-\frac{e^{\beta
z+h}\bar{f}(1,z)+e^{-\beta z-h}\bar{f}(-1,-z)}{e^{\beta z+h}+e^{-\beta z-h}}.$

Our next lemma establishes some useful bounds for the difference on the left-
hand side of (14) associated to $f$ and $\bar{f}$ defined above.

######  Lemma 2.3.

We have that

$\displaystyle\Delta(1,z)\geqslant 0,\,\,\forall
z\in\mathbb{R}\,\,\mbox{and}\,\,\Delta(1,z)\geqslant\frac{1}{1+e^{2\beta
M+2h}},\,\,\forall\delta\leqslant z\leqslant M,$ (15)
$\displaystyle\Delta(-1,z)\geqslant 0,\,\,\forall
z\in\mathbb{R}\,\,\mbox{and}\,\,\Delta(-1,z)\leqslant-\frac{1}{1+e^{-2\beta\delta-2h}},\,\,\forall\delta\leqslant
z\leqslant M,$ (16) $\displaystyle\bar{\Delta}(1,z)\geqslant 0,\,\,\forall
z\in\mathbb{R}\,\,\mbox{and}\,\,\bar{\Delta}(1,z)\geqslant\frac{1}{1+e^{-2\beta\delta+2h}},\,\,\forall-M\leqslant
z\leqslant-\delta,$ (17) $\displaystyle\bar{\Delta}(-1,z)\leqslant
0,\,\,\forall
z\in\mathbb{R}\,\,\mbox{and}\,\,\bar{\Delta}(-1,z)\leqslant-\frac{1}{1+e^{2\beta
M-2h}},\,\,\forall-M\leqslant z\leqslant-\delta.$ (18)

###### Proof.

Computing directly yields that for any $z\in\mathbb{R},$

$\displaystyle\Delta(1,z)=\frac{\rho(z)+\rho(-z)}{1+e^{2\beta z+2h}}\geqslant
0,\quad\Delta(-1,z)=-\frac{\bar{\rho}(z)+\bar{\rho}(-z)}{1+e^{-2\beta
z-2h}}\leqslant 0,$
$\displaystyle\bar{\Delta}(1,z)=\frac{\bar{\rho}(z)+\bar{\rho}(-z)}{1+e^{2\beta
z+2h}}\geqslant
0,\quad\bar{\Delta}(-1,z)=-\frac{\bar{\rho}(z)+\bar{\rho}(-z)}{1+e^{-2\beta
z-2h}}\leqslant 0.$

If $\delta\leqslant z\leqslant M,$ then

$\displaystyle\Delta(1,z)$ $\displaystyle=\frac{1}{1+e^{2\beta
z+2h}}\geqslant\frac{1}{1+e^{2\beta M+2h}},$ $\displaystyle\Delta(-1,z)$
$\displaystyle=-\frac{1}{1+e^{-2\beta
z-2h}}\leqslant-\frac{1}{1+e^{-2\beta\delta-2h}}.$

Also, if $-M\leqslant z\leqslant-\delta,$

$\displaystyle\bar{\Delta}(1,z)$ $\displaystyle=\frac{1}{1+e^{2\beta
z+2h}}\geqslant\frac{1}{1+e^{-2\beta\delta+2h}},$
$\displaystyle\bar{\Delta}(-1,z)$ $\displaystyle=-\frac{1}{1+e^{-2\beta
z-2h}}\leqslant-\frac{1}{1+e^{2\beta M-2h}}.$

$\blacksquare$

For a given ${\sigma}\in\\{-1,+1\\}^{N}$ and for $M>\delta>0,$ let

$\displaystyle I_{\delta,M}^{+}({\sigma})$
$\displaystyle:=\\{i:\delta\leqslant\sigma_{i}m_{i}({\sigma})\leqslant M\\},$
$\displaystyle I_{\delta,M}^{-}({\sigma})$
$\displaystyle:=\\{i:-M\leqslant\sigma_{i}m_{i}({\sigma})\leqslant-\delta\\}.$

The third lemma shows that if these two sets are linear large and
$\Delta(\sigma_{r},\sigma_{r}m_{r}(\sigma))$ and
$\bar{\Delta}(\sigma_{r},\sigma_{r}m_{r}(\sigma))$ for $1\leqslant r\leqslant
N$ are small on average, then there exist four coordinates, on which the pair
$(\sigma_{r},m_{r}(\sigma))$ must take all possible signs.

######  Lemma 2.4.

Assume that there exist some $0<\delta<M$ and $\varepsilon>0$ such that for
some $N\geqslant 4$ and ${\sigma}\in\\{-1,+1\\}^{N}$, the following
inequalities are satisfied

$\displaystyle|I_{\delta,M}^{+}({\sigma})|\geqslant\varepsilon N,$
$\displaystyle\,\,|I_{\delta,M}^{-}({\sigma})|\geqslant\varepsilon N,$ (19)
$\displaystyle\Bigl{|}\frac{1}{N}\sum_{r=1}^{N}\Delta(\sigma_{r},\sigma_{r}m_{r}({\sigma}))\Bigr{|}$
$\displaystyle\leqslant\frac{\varepsilon}{2}\min\Bigl{(}\frac{1}{1+e^{2\beta
M+2h}},\frac{1}{1+e^{2\beta M-2h}}\Bigr{)},$ (20)
$\displaystyle\Bigl{|}\frac{1}{N}\sum_{r=1}^{N}\bar{\Delta}(\sigma_{r},\sigma_{r}m_{r}({\sigma}))\Bigr{|}$
$\displaystyle\leqslant\frac{\varepsilon}{2}\min\Bigl{(}\frac{1}{1+e^{-2\beta\delta+2h}},\frac{1}{1+e^{-2\beta\delta-2h}}\Bigr{)},$
(21)

where $\Delta$ and $\bar{\Delta}$ are defined in Lemma 2.3. Then there exist
distinct $i,j,k,l\in[N]$ such that

$\displaystyle\sigma_{i}=1,\ \delta\leqslant m_{i}({\sigma})\leqslant M,$ (22)
$\displaystyle\sigma_{j}=-1,\ -M\leqslant m_{j}({\sigma})\leqslant-\delta,$
(23) $\displaystyle\sigma_{k}=-1,\ \delta\leqslant m_{k}({\sigma})\leqslant
M,$ (24) $\displaystyle\sigma_{l}=1,\ -M\leqslant
m_{l}({\sigma})\leqslant-\delta.$ (25)

###### Proof.

Since $|I_{\delta,M}^{+}({\sigma})|\geqslant\varepsilon N,$ we readily see
that either $\sigma_{i}=1,\delta\leqslant m_{i}({\sigma})\leqslant M$ or
$\sigma_{j}=-1,-M\leqslant m_{j}({\sigma})\leqslant-\delta$ for some $i,j.$ If
$\sigma_{i}=1$ and $\delta\leqslant m_{i}({\sigma})\leqslant M$ for all $i\in
I_{\delta,M}^{+}({\sigma})$, then from (15) and
$|I_{\delta,M}^{+}({\sigma})|\geqslant\varepsilon N,$ we arrive at

$\displaystyle\frac{1}{N}\sum_{r=1}^{N}\Delta(\sigma_{r},\sigma_{r}m_{r}({\sigma}))$
$\displaystyle\geqslant\frac{\varepsilon}{1+e^{2\beta M+2h}},$

contradicting (20). If $\sigma_{j}=-1$ and $-M\leqslant
m_{j}({\sigma})\leqslant-\delta$ for all $j\in I_{\delta,M}^{+}({\sigma})$,
then from (18) and $|I_{\delta,M}^{+}({\sigma})|\geqslant\varepsilon N,$

$\displaystyle\frac{1}{N}\sum_{r=1}^{N}\bar{\Delta}(\sigma_{r},\sigma_{r}m_{r}({\sigma}))$
$\displaystyle\leqslant-\frac{\varepsilon}{1+e^{2\beta M-2h}},$

contradicting (20) again. Hence, we see that there exist distinct $i,j$ such
that (22) and (23) hold. Similarly, the assumption
$|I_{\delta,M}^{-}({\sigma})|\geqslant\varepsilon N$ implies that either
$\delta_{k}=1,-M\leqslant m_{k}({\sigma})\leqslant-\delta$ or
$\delta_{l}=-1,\delta\leqslant m_{l}({\sigma})\leqslant M$ for some $k,l.$ If
$\sigma_{k}=1$ and $-M\leqslant m_{k}({\sigma})\leqslant-\delta$ for all $k\in
I_{\delta,M}^{-}({\sigma}),$ then from (17) and
$|I_{\delta,M}^{-}({\sigma})|\geqslant\varepsilon N$

$\displaystyle\frac{1}{N}\sum_{r=1}^{N}\bar{\Delta}(\sigma_{r},\sigma_{r}m_{r}({\sigma}))$
$\displaystyle\geqslant\frac{\varepsilon}{1+e^{-2\beta\delta+2h}},$

contradicting (21). Finally, if $\sigma_{l}=-1$ and $\delta\leqslant
m_{l}({\sigma})\leqslant M$ for all $l\in I_{\delta,M}^{-}({\sigma}),$ then
from (16) and $|I_{\delta,M}^{-}({\sigma})|\geqslant\varepsilon N$

$\displaystyle\frac{1}{N}\sum_{r=1}^{N}\Delta(\sigma_{r},\sigma_{r}m_{r}({\sigma}))$
$\displaystyle\leqslant-\frac{\varepsilon}{1+e^{-2\beta\delta-2h}},$

contradicting (21). Therefore, there must exist distinct $k,l$ such that (24)
and (25) hold. This completes our proof. $\blacksquare$

We have seen that from Lemma 2.1, the inequalities (20) and (21) hold with
high probability as $N$ tends to infinity. Our next goal will be to validate
the assumption (19), which relies on the following lemma.

######  Lemma 2.5 (Positivity of the Hamiltonian).

Let ${\tau}\sim P_{\beta,h}(\cdot)$ for some $\beta>0$ and $h\in\mathbb{R}$.
If

$\liminf_{N\to\infty}(F_{N}(\beta^{\prime},h)-F_{N}(0,h))>0$

for some $0<\beta^{\prime}<\beta,$ then there exists some $\delta>0$ such that

$\limsup_{N\to\infty}\frac{1}{N}\log
P_{\beta,h}\Bigl{(}\frac{1}{N}\sum_{i=1}^{N}\tau_{i}m_{i}({\tau})<\delta\Bigr{)}<0.$

###### Proof.

For any $\delta>0$, by the Markov inequality,

$\displaystyle
P_{\beta,h}\Bigl{(}\frac{1}{N}\sum_{i=1}^{N}\tau_{i}m_{i}({\tau})<\delta\Bigr{)}$
$\displaystyle\leqslant e^{\lambda
N\delta}\operatorname{\mathds{E}}_{\beta,h}\Bigl{(}\exp\Bigl{(}-\lambda\sum_{i=1}^{N}\tau_{i}m_{i}({\tau})\Bigr{)}\Bigr{)}$
$\displaystyle=e^{\lambda N\delta}Z_{N}(\beta-\lambda,h)(Z_{N}(\beta,h))^{-1}$
$\displaystyle=e^{\lambda
N\delta+N\left(F_{N}(\beta-\lambda,h)-F_{N}(\beta,h)\right)}.$

Using the convexity of $F_{N}$ in $\beta$, we have that for
$\lambda\in(0,\beta)$,

$\displaystyle F_{N}(\beta,h)-F_{N}(\beta-\lambda,h)$
$\displaystyle\geqslant\frac{\partial}{\partial\beta}F_{N}(\beta-\lambda,h)\lambda\geqslant\frac{F_{N}(\beta-\lambda,h)-F_{N}(0,h)}{\beta-\lambda}\lambda.$

Form the given assumption, letting
$\delta=2^{-1}\liminf_{N\to\infty}(F_{N}(\beta^{\prime},h)-F_{N}(0,h))$ and
$\lambda=\beta-\beta^{\prime}$ completes our proof. $\blacksquare$

Finally, we show that the assumption (19) holds with high probability.

######  Lemma 2.6.

Suppose ${\tau}\sim P_{\beta,h}(\cdot)$ for $\beta>0,h\in\mathbb{R}$ and the
condition $(i)$ in Theorem 1.1 holds, then there exist $\varepsilon>0$ and
$0<\delta<M$ such that w.h.p., the following inequalities hold,

$\displaystyle|I_{\delta,M}^{+}({\tau})|\geqslant\varepsilon
N\,\,\mbox{and}\,\,|I_{\delta,M}^{-}({\tau})|\geqslant\varepsilon N.$

###### Proof.

Let us begin with the following notations. For a given ${\sigma}$ and
$0<\delta<M$, let

$I_{M}({\sigma}):=\\{i\in[N]:\left|m_{i}({\sigma})\right|\leqslant M\\}$

and

$\displaystyle
I^{+}({\sigma}):=\\{i\in[N]:\sigma_{i}m_{i}({\sigma})>0\\},\,\,I^{-}({\sigma}):=\\{i\in[N]:\sigma_{i}m_{i}({\sigma})<0\\},$
$\displaystyle
I_{\delta}^{+}({\sigma}):=\\{i\in[N]:\sigma_{i}m_{i}({\sigma})\geqslant\delta\\},\,\,I_{\delta}^{-}({\sigma}):=\\{i\in[N]:\sigma_{i}m_{i}({\sigma})\leqslant-\delta\\}.$

We will abbreviate the above notations by
$I_{M},I^{+},I^{-},I_{\delta}^{+},I_{\delta}^{-}$ when the configuration is
the sample ${\tau}$. By Markov inequality, we readily have

$\displaystyle\left|I_{M}^{c}\right|\leqslant\frac{\sum_{i\in[N]}m_{i}({\tau})^{2}}{M^{2}}\leqslant\frac{\left\|J\right\|^{2}N}{M^{2}}.$
(26)

From (26) and the Cauchy-Schwarz inequality,

$\displaystyle\sum_{i\in
I^{c}_{M}}|m_{i}({\tau})|\leqslant|I^{c}_{M}|^{1/2}\Bigl{(}\sum_{i=1}^{N}|m_{i}({\tau})|^{2}\Bigr{)}^{1/2}\leqslant|I^{c}_{M}|^{1/2}\|J\|\sqrt{N}\leqslant\frac{N\|J\|^{2}}{M}.$
(27)

Combining (26) with Lemma 2.5, there exist $\varepsilon>0$ and $0<\delta<M$
such that w.h.p., we have $|I_{\delta,M}^{+}({\tau})|\geqslant\varepsilon N$.

Next, we focus on $I_{\delta,M}^{-}({\tau})$. Notice that

$\displaystyle S(\beta,h|{\tau})$
$\displaystyle=\sum_{i\in[N]}m_{i}({\tau})(\tau_{i}-\tanh(\beta
m_{i}({\tau})+h))$ $\displaystyle=\sum_{i\in
I^{c}_{M}}m_{i}({\tau})(\tau_{i}-\tanh(\beta m_{i}({\tau})+h))$ (28)
$\displaystyle\quad\quad+\sum_{i\in I_{M}\cap
I^{+}}m_{i}({\tau})(\tau_{i}-\tanh(\beta m_{i}({\tau})+h))$ (29)
$\displaystyle\quad\quad+\sum_{i\in I_{M}\cap
I^{-}}m_{i}({\tau})(\tau_{i}-\tanh(\beta m_{i}({\tau})+h)).$ (30)

For (28), using (27), for any $\varepsilon^{\prime}>0$, one can choose $M$
sufficiently such that

$\sum_{i\in I_{M}}m_{i}({\tau})(\tau_{i}-\tanh(\beta
m_{i}({\tau})+h))\leqslant\varepsilon^{\prime}N.$

Now for (29), we have

$\displaystyle\sum_{i\in I_{M}\cap I^{+}}m_{i}({\tau})(\tau_{i}-\tanh(\beta
m_{i}({\tau})+h))$ $\displaystyle\geqslant\sum_{i\in I_{M}\cap
I^{+}}m_{i}({\tau})\tau_{i}(1-\tanh(|\beta m_{i}({\tau})|+|h|))$
$\displaystyle\geqslant c\Bigl{(}\sum_{i\in
I^{+}}m_{i}({\tau})\tau_{i}-\sum_{i\in
I^{c}_{M}}\left|m_{i}({\tau})\right|\Bigr{)},$

where $c=1-\tanh(|\beta|M+|h|)>0$. By Lemma 2.5, we have w.h.p., $\sum_{i\in
I^{+}}m_{i}({\tau})\tau_{i}\geqslant 2\eta N$ for some $\eta>0$. Using (27),
one can make $\sum_{i\in I_{M}}\left|m_{i}({\tau})\right|\leqslant\eta N$ by
choosing $M$ large enough. Therefore, $\eqref{eq:term2}$ is bounded from below
by $\eta N$ w.h.p.

Finally, for $\delta>0$, we write (30) as

$\displaystyle\sum_{i\in I_{M}\cap I^{-}}m_{i}({\tau})(\tau_{i}-\tanh(\beta
m_{i}({\tau})+h))$ $\displaystyle=\sum_{i\in
I^{-}_{\delta,M}({\tau})}m_{i}({\tau})(\tau_{i}-\tanh(\beta m_{i}({\tau})+h))$
$\displaystyle+\sum_{i\in
I_{M}:-\delta\leqslant\tau_{i}m_{i}({\tau})<0}m_{i}({\tau})(\tau_{i}-\tanh(\beta
m_{i}({\tau})+h)).$

Since $\left|\tau_{i}-\tanh(\beta m_{i}({\tau})+h)\right|\leqslant 2$, it
follows that

$\displaystyle\sum_{i\in
I^{-}_{\delta,M}({\tau})}m_{i}({\tau})(\tau_{i}-\tanh(\beta
m_{i}({\tau})+h))\geqslant-2M|I^{-}_{\delta,M}({\tau})|.$

Similarly,

$\sum_{i\in
I_{M}:-\delta\leqslant\tau_{i}m_{i}({\tau})<0}m_{i}({\tau})(\tau_{i}-\tanh(\beta
m_{i}({\tau})+h))\geqslant-2\delta N.$

Thus

$\sum_{i\in I_{M}\cap I^{-}}m_{i}({\tau})(\tau_{i}-\tanh(\beta
m_{i}({\tau})+h))\geqslant-2M|I^{-}_{\delta,M}({\tau})|-2\delta N.$

Putting the bounds for all three terms together with
$\varepsilon^{\prime}=\eta/4$ and $\delta=\eta/8$, we have w.h.p.

$\displaystyle
S(\beta,h|{\tau})\geqslant\frac{\eta}{2}N-2M|I^{-}_{\delta,M}|.$

It now follows from the concentration bound of $S(\beta,h|{\tau})$ established
in Corollary 2.2 that w.h.p.,

$|I^{-}_{\delta,M}({\tau})|\geqslant\frac{\eta}{4M}N.$

$\blacksquare$

###  2.2. Proof of Theorem 1.1: Existence of the MPLE

Before we turn to the proof for the existence part of the MPLE in Theorem 1.1,
we establish the following lemma first.

######  Lemma 2.7.

Let ${\tau}\in\\{-1,+1\\}^{N}$ be a sample from the unknown ground truth
$P_{\beta_{0},h_{0}}$. The maximum pseudolikelihood estimator
$(\hat{\beta}({\tau}),\hat{h}({\tau}))$ exists if ${\tau}$ satisfies the
following property: there exist distinct $i,j,k,l\in[N]$ such that

$\displaystyle\begin{split}&\tau_{i}=1,m_{i}({\tau})>0,\,\,\tau_{j}=-1,m_{j}({\tau})<0,\\\
&\tau_{k}=-1,m_{k}({\tau})>0,\,\,\tau_{l}=1,m_{l}({\tau})<0.\end{split}$ (31)

###### Proof.

Note that if ${\tau}$ satisfies (31), then obviously
$\widetilde{T}_{N}({\tau})>0$. From (8), the pseudolikelihood function is
strictly concave on $\mathbb{R}^{2}$. Thus, to prove the existence of the
maximum pseudolikelihood estimator, it suffices to show that

$\displaystyle\limsup_{|\beta|+|h|\to\infty}L(\beta,h|{\tau})=-\infty.$

To this end, noting that

$\displaystyle L(\beta,h|{\tau})+\log 2$
$\displaystyle=\sum_{i=1}^{N}\Big{(}\tau_{i}(\beta
m_{i}({\tau})+h)-\log\cosh(\beta m_{i}({\tau})+h)\Big{)}$
$\displaystyle\leqslant\sum_{i=1}^{N}\Big{(}|\beta
m_{i}({\tau})+h|-\log\cosh(\beta m_{i}({\tau})+h)\Big{)}$

and each term in the above sum is nonpositive, it is enough to show that given
${\tau}$, for any $K>0$, there exists some $C>0$ such that the following
statement holds: for any $(\beta,h)\in\mathbb{R}^{2}$ with
$|\beta|+|h|\geqslant C,$ there exists some $a=a(\beta,h)\in[N]$ such that

$\tau_{a}(\beta m_{a}({\tau})+h)-\log\cosh(\beta m_{a}({\tau})+h)\leqslant-K.$

Assume that $i,j,k,$ and $l$ satisfy (31). For each
$(\beta,h)\in\mathbb{R}^{2},$ we select $a$ according to the following rules.
First, let $\eta=\min_{a\in\\{i,j,k,l\\}}|m_{a}({\tau})|>0$.

  * •

If $\beta,h\neq 0$, let $a\in\\{i,j,k,l\\}$ be such that

$\text{sign}(m_{a}({\tau}))=\text{sign}(\beta
h)\,\,\text{and}\,\,\tau_{a}=-\text{sign}(h).$

Then

$\tau_{a}(\beta m_{a}({\tau})+h)=-\left|\beta
m_{a}({\tau})\right|-\left|h\right|\leqslant-|\beta|\eta-|h|.$

  * •

If $\beta\neq 0,h=0$, let $a\in\\{i,j,k,l\\}$ be such that
$\tau_{a}=-\text{sign}(\beta m_{a}({\tau}))$. Then

$\tau_{a}(\beta
m_{a}({\tau})+h)=-\left|\beta\right|\left|m_{a}({\tau})\right|\leqslant-|\beta|\eta.$

  * •

If $\beta=0,h\neq 0$, similarly let $a\in\\{i,j,k,l\\}$ with
$\tau_{a}=-\text{sign}(h)$. Then

$\tau_{a}(\beta m_{a}({\tau})+h)=-\left|h\right|.$

From these and noting that $\log\cosh(x)\geqslant 0$ for all $x\in\mathbb{R}$,
we readily see that for any $(\beta,h)\in\mathbb{R}^{2},$

$\displaystyle\tau_{a}(\beta m_{a}({\tau})+h)-\log\cosh(\beta
m_{a}({\tau})+h)\leqslant\tau_{a}(\beta m_{a}({\tau})+h)$
$\displaystyle\leqslant-\max(|h|,|\beta|\eta).$

Now for each $K>0,$ our proof is completed by letting $C=K(1/\eta+1).$
$\blacksquare$

We now turn to the proof for the existence of the MPLE in Theorem 1.1. From
Lemma 2.7, we only need to verify that w.h.p., the sample ${\tau}\sim
P_{\beta_{0},h_{0}}$ satisfies (31). To do this, we will check that w.h.p.,
the assumptions in Lemma 2.4 are satisfied. Now, from Lemma 2.6, we already
proved that there exist $\varepsilon>0$ and $0<\delta<M$ such that w.h.p.,

$|I_{\delta,M}^{+}({\tau})|,|I_{\delta,M}^{-}({\tau})|\geqslant\varepsilon N.$

On the other hand, by Lemma 2.1 with $f(x,y)=x\rho(y)$ and
$f(x,y)=x\bar{\rho}(y)$ and with the operator norm bound in the condition (ii)
stated in Theorem 1.1, we have

$\Big{\langle}\Big{(}\sum_{r=1}^{N}\Delta(\tau_{r},\tau_{r}m_{r}({\tau}))\Big{)}^{2}\Big{\rangle}\leqslant
CN,\quad\Big{\langle}\Big{(}\sum_{r=1}^{N}\bar{\Delta}(\tau_{r},\tau_{r}m_{r}({\tau}))\Big{)}^{2}\Big{\rangle}\leqslant
CN$

for some constant $C$. Thus, it follows that the assumptions (20) and (21) of
Lemma 2.4 are satisfied w.h.p., validating the conclusion of Lemma 2.4, which
implies (31) and completes our proof.

###  2.3. Proof of Theorem 1.1: Consistency of MPLE

We begin with a simple lemma:

######  Lemma 2.8.

Fix $\beta>0$ and $h\in\mathbb{R}$. Let ${\sigma}\in\\{-1,+1\\}^{N}$. Suppose
that $\|J\|=O(1)$ and $\widetilde{T}_{N}({\sigma})\geqslant c.$ Then there
exists a constant $M>0$, which depends only on $c,\beta,h,$ and $\|J\|$ such
that

$\frac{1}{N^{2}}\sum_{i,j\in
I_{M}({\sigma})}(m_{i}({\sigma})-m_{j}({\sigma}))^{2}\geqslant\frac{c}{2},$

where $I_{M}({\sigma})=\\{i\in[N]:|m_{i}({\sigma})|\leqslant M\\}.$

###### Proof.

Let $M$ be sufficiently large such that $\beta M>|h|$. We have

$\displaystyle\frac{1}{N^{2}}\sum_{i,j\in
I_{M}({\sigma})}(m_{i}({\sigma})-m_{j}({\sigma}))^{2}$
$\displaystyle\geqslant\frac{1}{N^{2}}\sum_{i,j\in
I_{M}({\sigma})}\theta_{i}({\sigma})\theta_{j}({\sigma})(m_{i}({\sigma})-m_{j}({\sigma}))^{2}$
$\displaystyle\geqslant c-\frac{1}{N^{2}}\sum_{\\{i,j\\}\cap
I_{M}^{c}({\sigma})\neq\emptyset}\theta_{i}({\sigma})\theta_{j}({\sigma})(m_{i}({\sigma})-m_{j}({\sigma}))^{2}$
$\displaystyle\geqslant c-\frac{\operatorname{sech}^{2}(\beta
M-|h|)}{N^{2}}\sum_{i,j}(m_{i}({\sigma})-m_{j}({\sigma}))^{2}.$

On the other hand,

$\displaystyle\frac{1}{N^{2}}\sum_{i,j}(m_{i}({\sigma})-m_{j}({\sigma}))^{2}\leqslant\frac{2}{N}\sum_{i}m_{i}({\sigma})^{2}\leqslant
2\|J\|^{2}.$

Combining these two estimates, the lemma follows that if we choose $M$ large
enough to satisfy $2\operatorname{sech}^{2}(\beta M-|h|)\|J\|^{2}\leqslant
c/2$. $\blacksquare$

The proof for the consistency of MPLE in Theorem 1.1 proceeds as follows. For
notational clarity, we will make the dependence of the quantities $\theta_{i}$
and $\widetilde{T}_{N}$ on parameters $\beta$ and $h$ explicit throughout the
proof. Let ${\tau}\sim P_{\beta_{0},h_{0}}$. For $(\beta,h)\in\mathbb{R}^{2}$,
let $\lambda_{1}(\beta,h|{\tau})\geqslant 0$ be the minimum eigenvalue of the
negative Hessian matrix, $H(\beta,h|{\tau})$. Note that

$\displaystyle\lambda_{1}(\beta,h|{\tau})$
$\displaystyle\geqslant\frac{\left|H(\beta,h|{\tau})\right|}{\mathrm{Tr}(H(\beta,h|{\tau}))}=\frac{\frac{1}{2}\sum_{i,j=1}^{N}\theta_{i}(\beta,h|{\tau})\theta_{j}(\beta,h|{\tau})(m_{i}({\tau})-m_{j}({\tau}))^{2}}{\mathrm{Tr}(H(\beta,h|{\tau}))},$
(32)

where $\theta_{i}(\beta,h|{\tau})=\operatorname{sech}^{2}(\beta
m_{i}({\tau})+h)$. To bound the right hand side of (32) from below, we note

$\displaystyle\sum_{i,j=1}^{N}\theta_{i}(\beta,h|{\tau})\theta_{j}(\beta,h|{\tau})(m_{i}({\tau})-m_{j}({\tau}))^{2}$
$\displaystyle\geqslant\operatorname{sech}^{4}(\beta M+|h|)\sum_{i,j\in
I_{M}({\tau})}(m_{i}({\tau})-m_{j}({\tau}))^{2}$

for any $M>0$. Also, note that since $\theta_{i}(\beta,h|{\tau})\leqslant 1$
and $\sum_{i=1}^{N}m_{i}^{2}({\tau})\leqslant\|J\|^{2}N,$

$\mathrm{Tr}(H(\beta,h|{\tau}))=\sum_{i=1}^{N}\theta_{i}(\beta,h|{\tau})(m_{i}^{2}({\tau})+1)\leqslant
N(1+C^{2}).$

Therefore, we obtain

$\displaystyle\lambda_{1}(\beta,h|{\tau})\geqslant\frac{\operatorname{sech}^{4}(\beta
M+|h|)}{2(1+C^{2})N}\sum_{i,j\in
I_{M}({\tau})}(m_{i}({\tau})-m_{j}({\tau}))^{2}.$ (33)

This yields the following locally uniform lower bound for
$\lambda_{1}(\beta,h|{\tau})$ that for any $M>0$, there exist some positive
$r,\eta>0$ such that

$\displaystyle\inf_{\left\|\beta-\beta_{0},h-h_{0}\right\|\leqslant
r}\lambda_{1}(\beta,h|{\tau})\geqslant\frac{\eta}{N}\sum_{i,j\in
I_{M}({\tau})}(m_{i}({\tau})-m_{j}({\tau}))^{2}.$ (34)

Next, we construct an interpolation between the pseudolikelihood estimator and
the ground truth by letting

$\displaystyle\beta(t)=t\hat{\beta}+(1-t)\beta_{0}\,\,\mbox{and}\,\,h(t)=t\hat{h}+(1-t)h_{0}$

for $t\in[0,1].$ Set $f:[0,1]\to\mathbb{R}$ as

$\displaystyle
f(t)=(\hat{\beta}-\beta_{0})S(\beta(t),h(t)|{\tau})+(\hat{h}-h_{0})Q(\beta(t),h(t)|{\tau}).$

Since $Q(\hat{\beta},\hat{h}|{\tau})=0$ and $R(\hat{\beta},\hat{h}|{\tau})=0$,
it is clear

$\displaystyle\left|f(1)-f(0)\right|=\bigl{|}(\hat{\beta}-\beta_{0})S(\beta_{0},h_{0}|{\tau})+(\hat{h}-h_{0})Q(\beta_{0},h_{0}|{\tau})\bigr{|}.$

By Corollary 2.2, we have

$S(\beta_{0},h_{0}|{\tau}),Q(\beta_{0},h_{0}|{\tau})=O_{p}(\sqrt{N}).$

Applying the Cauchy-Schwarz inequality, we deduce

$\displaystyle\left|f(1)-f(0)\right|=O_{p}(\sqrt{N}Y_{N}),$ (35)

where $Y_{N}:=\|(\hat{\beta}-\beta_{0},\hat{h}-h_{0})\|_{2}$.

Now to bound $Y_{N}$, we need to control $\left|f(1)-f(0)\right|$. For any
$t\in[0,1]$, the derivative of $f$ is bounded from below by

$\displaystyle f^{\prime}(t)$
$\displaystyle=(\hat{\beta}-\beta_{0},\hat{h}-h_{0})H(\beta(t),h(t)|{\tau})(\hat{\beta}-\beta_{0},\hat{h}-h_{0})^{T}$
$\displaystyle\geqslant\lambda_{1}(\beta(t),h(t)|{\tau})Y_{N}^{2}.$

From the fact $\|(\beta(t)-\beta_{0},h(t)-h_{0})\|_{2}=tY_{N}$ and the uniform
lower bound (34), we obtain

$\displaystyle f(1)-f(0)$
$\displaystyle=\int_{0}^{1}f^{\prime}(t)dt\geqslant\int_{0}^{\min\big{(}1,\frac{r}{Y_{N}}\big{)}}f^{\prime}(t)dt$
$\displaystyle\geqslant\min\big{(}1,\frac{r}{Y_{N}}\big{)}\frac{\eta
Y_{N}^{2}}{N}\sum_{i,j\in I_{M}({\tau})}(m_{i}({\tau})-m_{j}({\tau}))^{2}.$
(36)

From the assumption (iii) of Theorem 1.1, it follows that given
$\varepsilon>0$, there exists $c>0$ such that with
$P_{\beta_{0},h_{0}}$-probability at least $1-\varepsilon/2$, we have
$\widetilde{T}_{N}(\beta_{0},h_{0}|{\tau})\geqslant c$. Furthermore, thanks to
Lemma 2.8, we can find $M$ such that on the same event,

$\frac{1}{N^{2}}\sum_{i,j\in
I_{M}({\tau})}(m_{i}({\tau})-m_{j}({\tau}))^{2}\geqslant\frac{c}{2}.$

On the other hand, (35) implies that there exists $C$ such that

$|f(1)-f(0)|\leqslant C\sqrt{N}Y_{N}$

with $P_{\beta_{0},h_{0}}$-probability at least $1-\varepsilon/2$. Since both
of the conditions hold simultaneously with probability at least
$1-\varepsilon$, it now follows from (2.3) that with probability at least
$1-\varepsilon$,

$\displaystyle\min(Y_{N},r)\leqslant\frac{2C}{\eta c\sqrt{N}}.$

Since $r$ is independent of $N$, it follows that $Y_{N}=O_{p}(\sqrt{N})$ as
claimed.

##  3\. Proof of Theorem 1.4

To prove the Theorem 1.4, we first establish the following universality result
in Lemma 3.1, which shows that the free energies associated with the
subgaussian matrix $G=(g_{ij})_{1\leqslant i,j\leqslant N}$ is close to that
associated to the standard Gaussian disorder. For any $x=(x_{e})_{e\in E}$,
set

$\displaystyle
F_{x}(\beta,h):=\frac{1}{N}\ln\sum_{{\sigma}\in\\{-1,+1\\}^{N}}e^{\beta
H_{x}({\sigma})+h\sum_{i=1}^{N}\sigma_{i}},$

where

$H_{x}({\sigma}):=\frac{1}{\sqrt{d}}\sum_{(i,j)\in
E}x_{ij}\sigma_{i}\sigma_{j}.$

Note that $F_{g}(\beta,h)=F_{N}(\beta,h).$ Let $z=(z_{e})_{e\in E}$ be i.i.d.
standard normal independent of $g.$

######  Lemma 3.1.

There exists a universal constant $C$ independent of $N,d,\beta,h$ such that

$\displaystyle\left|\operatorname{\mathds{E}}F_{g}(\beta,h)-\operatorname{\mathds{E}}F_{z}(\beta,h)\right|$
$\displaystyle\leqslant\frac{C\beta^{3}}{\sqrt{d}}.$

###### Proof.

For $0\leqslant t\leqslant 1$, define

$\displaystyle\phi(t)=\frac{1}{N}\operatorname{\mathds{E}}\ln e^{\beta
H_{N,t}({\sigma})},$

where

$\displaystyle H_{N,t}({\sigma})$
$\displaystyle:=\sqrt{t}H_{g}({\sigma})+\sqrt{1-t}H_{z}({\sigma})+h\sum_{i=1}^{N}\sigma_{i}.$

Then

$\displaystyle\phi^{\prime}(t)$
$\displaystyle=\frac{\beta}{2N}\Bigl{(}\frac{\operatorname{\mathds{E}}\langle
H_{g}({\sigma})\rangle_{t}}{\sqrt{t}}-\frac{\operatorname{\mathds{E}}\langle
H_{z}({\sigma})\rangle_{t}}{\sqrt{1-t}}\Bigr{)}=\frac{\beta}{2N\sqrt{d}}\operatorname{\mathds{E}}\Bigl{[}\sum_{(i,j)\in
E}\frac{\langle
g_{ij}\sigma_{i}\sigma_{j}\rangle_{t}}{\sqrt{t}}-\sum_{(i,j)\in
E}\frac{\langle z_{ij}\sigma_{i}\sigma_{j}\rangle_{t}}{\sqrt{1-t}}\Bigr{]}.$

Here from the Gaussian integration by parts in the Gaussian disorder,

$\displaystyle\frac{\operatorname{\mathds{E}}\langle
z_{ij}\sigma_{i}\sigma_{j}\rangle_{t}}{\sqrt{1-t}}$
$\displaystyle=\frac{\beta}{\sqrt{d}}\operatorname{\mathds{E}}\bigl{\langle}1-\sigma_{i}^{1}\sigma_{j}^{1}\sigma_{i}^{2}\sigma_{j}^{2}\bigr{\rangle}_{t}.$

On the other hand, from the approximate Gaussian integration by parts in the
disorder $g$ (see, for example, [carmona2006universality]), there exists an
absolute constant $C$ independent of anything else such that

$\displaystyle\Bigl{|}\frac{\operatorname{\mathds{E}}\langle
g_{ij}\sigma_{i}\sigma_{j}\rangle_{t}}{\sqrt{t}}-\frac{\beta}{\sqrt{d}}\operatorname{\mathds{E}}\bigl{\langle}1-\sigma_{i}^{1}\sigma_{j}^{1}\sigma_{i}^{2}\sigma_{j}^{2}\bigr{\rangle}_{t}\Bigr{|}\leqslant\frac{C\beta^{2}}{d}.$

Consequently,

$\displaystyle|\phi^{\prime}(t)|$
$\displaystyle\leqslant\frac{C\beta^{3}|E|}{2d^{3/2}N}=\frac{C\beta^{3}}{\sqrt{d}}$

and this completes our proof. $\blacksquare$

We also establish the following concentration result for the free energy
$F_{N}(\beta,h)$ for later use.

######  Proposition 3.2.

Assume that $(g_{e})_{e\in E}$ is a collection of independent
$\kappa^{2}$-subgaussian random variables. For $t>0$, we have

$\displaystyle\mathbb{P}\bigl{(}|F_{N}(\beta,h)-\operatorname{\mathds{E}}F_{N}(\beta,h)|\geqslant
t\bigr{)}$ $\displaystyle\leqslant 2\exp\Bigl{(}-\min\Bigl{(}\frac{(\ln
2)Nt^{2}}{2\beta^{2}\kappa^{2}},\frac{\sqrt{d\ln
2}Nt}{2\beta\kappa}\Bigr{)}\Bigr{)}.$

###### Proof.

Denote $f_{N}(\beta,h):=NF_{N}(\beta,h).$ Let $(g_{i})_{1\leqslant
i\leqslant|E|}$ be an enumeration of $(g_{e})_{e\in E}.$ We introduce the
following filtration $\mathcal{F}_{k}=\sigma(g_{k}:1\leqslant k\leqslant|E|)$
for $1\leqslant k\leqslant|E|$ and $\mathcal{F}_{0}=\emptyset.$ For each
$1\leqslant k\leqslant|E|,$ define the martingale difference

$\displaystyle X_{k}$
$\displaystyle:=\operatorname{\mathds{E}}\bigl{[}f_{N}(\beta,h)\big{|}\mathcal{F}_{k}\bigr{]}-\operatorname{\mathds{E}}\bigl{[}f_{N}(\beta,h)\big{|}\mathcal{F}_{k-1}\bigr{]}.$

Then $\operatorname{\mathds{E}}[X_{k}|\mathcal{F}_{k-1}]=0$ and

$\displaystyle\sum_{k=1}^{|E|}X_{k}$
$\displaystyle=f_{N}(\beta,h)-\operatorname{\mathds{E}}\bigl{[}f_{N}(\beta,h)\bigr{]}.$

Fix $k$. Let $\tilde{f}_{N}(\beta,h)$ be the same as $f_{N}(\beta,h)$ with
$g_{k}=0$ and $\langle\cdot\rangle_{k}$ is the corresponding Gibbs
expectation. Then

$\displaystyle X_{k}$
$\displaystyle=\operatorname{\mathds{E}}\bigl{[}f_{N}(\beta,h)-\tilde{f}_{N}(\beta,h)\big{|}\mathcal{F}_{k}\bigr{]}-\operatorname{\mathds{E}}\bigl{[}f_{N}(\beta,h)-\tilde{f}_{N}(\beta,h)\big{|}\mathcal{F}_{k-1}\bigr{]}$
$\displaystyle=\operatorname{\mathds{E}}\bigl{[}\ln\bigl{\langle}\exp\bigl{(}\beta
g_{k}\sigma_{e}/\sqrt{d}\bigr{)}\bigr{\rangle}_{k}\big{|}\mathcal{F}_{k}\bigr{]}-\operatorname{\mathds{E}}\bigl{[}\ln\bigl{\langle}\exp\bigl{(}\beta
g_{k}\sigma_{e}/\sqrt{d}\bigr{)}\bigr{\rangle}_{k}\big{|}\mathcal{F}_{k-1}\bigr{]}$
$\displaystyle\leqslant\beta
d^{-1/2}\operatorname{\mathds{E}}\bigl{[}|g_{k}|\big{|}\mathcal{F}_{k}\bigr{]}+\beta
d^{-1/2}\operatorname{\mathds{E}}\bigl{[}|g_{k}|\big{|}\mathcal{F}_{k-1}\bigr{]}$
$\displaystyle\leqslant\frac{\beta|g_{k}|}{\sqrt{d}}+\frac{\beta\operatorname{\mathds{E}}|g_{k}|}{\sqrt{d}},$

where $\sigma_{e}=\sigma_{i}\sigma_{j}$ and $e=(i,j)$ is the $k$-th edge in
the enumeration. From the fact that $g_{k}$ is $\kappa^{2}$-subgaussian and
Jensen’s inequality, we have

$\displaystyle\operatorname{\mathds{E}}\bigl{[}e^{\frac{|X_{k}|}{A}}\big{|}\mathcal{F}_{k-1}\bigr{]}$
$\displaystyle\leqslant\operatorname{\mathds{E}}\exp\left(\frac{\beta|g_{k}|}{A\sqrt{d}}+\frac{\beta\operatorname{\mathds{E}}|g_{k}|}{A\sqrt{d}}\right)$
$\displaystyle\leqslant\exp\left(\frac{\beta^{2}\kappa^{2}}{2A^{2}d}+\frac{\beta\operatorname{\mathds{E}}|g_{k}|}{A\sqrt{d}}\right)$
$\displaystyle\leqslant\exp\left(\frac{\beta^{2}\kappa^{2}}{2A^{2}d}\right)\operatorname{\mathds{E}}\exp\left(\frac{\beta|g_{k}|}{A\sqrt{d}}\right)=e^{\frac{\beta^{2}\kappa^{2}}{A^{2}d}}=e^{\ln
2}=2,$

provided

$\displaystyle A^{2}\equiv\frac{1}{\ln 2}\cdot\frac{\beta^{2}\kappa^{2}}{d}.$

Hence, from Bernstein’s inequality,

$\displaystyle\mathbb{P}\Bigl{(}\sum_{k=1}^{|E|}X_{k}\geqslant t\Bigr{)}$
$\displaystyle\leqslant\exp\Bigl{(}-\min\Bigl{(}\frac{t^{2}}{4|E|A^{2}},\frac{t}{2A}\Bigr{)}\Bigr{)}.$

and thus, using $|E|=2^{-1}\sum_{i\in[N]}d_{i}=2^{-1}Nd,$

$\displaystyle\mathbb{P}\left(\sum_{k=1}^{|E|}X_{k}\geqslant Nt\right)$
$\displaystyle\leqslant\exp\Bigl{(}-\min\Bigl{(}\frac{N^{2}t^{2}}{4|E|A^{2}},\frac{Nt}{2A}\Bigr{)}\Bigr{)}$
$\displaystyle=\exp\Bigl{(}-\min\Bigl{(}\frac{(\ln
2)dN^{2}t^{2}}{4\beta^{2}\kappa^{2}|E|},\frac{\sqrt{d\ln
2}Nt}{2\beta\kappa}\Bigr{)}\Bigr{)}$
$\displaystyle=\exp\Bigl{(}-\min\Bigl{(}\frac{(\ln
2)Nt^{2}}{2\beta^{2}\kappa^{2}},\frac{\sqrt{d\ln
2}Nt}{2\beta\kappa}\Bigr{)}\Bigr{)}.$

$\blacksquare$

###### Proof of Theorem 1.4.

From the Gaussian integration by parts, we have

$\displaystyle\partial_{\beta}\operatorname{\mathds{E}}F_{z}(\beta,h)$
$\displaystyle=\frac{\beta}{N}\operatorname{\mathds{E}}\bigl{\langle}H_{z}({\sigma})\bigr{\rangle}$
$\displaystyle=\frac{\beta^{2}}{Nd}\Bigl{(}|E|-\sum_{(i,j)\in
E}\operatorname{\mathds{E}}\langle\sigma_{i}^{1}\sigma_{j}^{1}\sigma_{i}^{2}\sigma_{j}^{2}\rangle\Bigr{)}=\frac{\beta^{2}}{2}\Bigl{(}1-\frac{2}{Nd}\sum_{(i,j)\in
E}\operatorname{\mathds{E}}\langle\sigma_{i}^{1}\sigma_{j}^{1}\sigma_{i}^{2}\sigma_{j}^{2}\rangle\Bigr{)},$

where by a slight abuse of notation, $\langle\cdot\rangle$ stands for the
Gibbs expectation associated to the free energy $F_{z}(\beta,h)$. Under the
given assumption, we could have the following result formally stated and
proved in Proposition 5.8. It implies that there exist positive $M$ and $c$
such that for any $N\geqslant 1$ and ${\sigma}\sim P_{\beta,h},$ if we define
$U=U({\sigma})\subseteq[N]$ as

$U=\big{\\{}i:|m_{i}({\sigma})|\leqslant M,\ d_{i}\geqslant d/4\big{\\}},$

then w.h.p., $|U|\geqslant cn$.

Notice that

$\displaystyle\langle\sigma_{i}\sigma_{j}\rangle$
$\displaystyle=\bigl{\langle}\tanh(\beta
m_{i}({\sigma})+h)\sigma_{j}\bigr{\rangle}.$

We have

$\displaystyle\langle\sigma_{i}\sigma_{j}\rangle$
$\displaystyle=\langle\tanh(\beta m_{i}({\sigma})+h)\sigma_{j};i\in
U\rangle+\langle\tanh(\beta m_{i}({\sigma})+h)\sigma_{j};i\in U^{c}\rangle$
$\displaystyle\leqslant\tanh(\beta M+h)\bigl{\langle}I(i\in
U)\bigr{\rangle}+\langle I(i\in U^{c})\rangle$ $\displaystyle=1-(1-\tanh(\beta
M+h))\langle I(i\in U)\rangle.$

From the definition of $U$, it follows that w.h.p.,

$\displaystyle\sum_{(i,j)\in E}I(i\in U)$
$\displaystyle\geqslant\frac{1}{2}\sum_{i\in U}d_{i}\geqslant\frac{cdN}{8}.$

Therefore, we have w.h.p.,

$\displaystyle\frac{2}{Nd}\sum_{(i,j)\in E}\langle\sigma_{i}\sigma_{j}\rangle$
$\displaystyle\leqslant\frac{2}{Nd}\Bigl{(}|E|-(1-\tanh(\beta
M+|h|))\Bigl{\langle}\sum_{(i,j)\in E}I(i\in U)\Bigr{\rangle}\Bigr{)}$
$\displaystyle\leqslant 1-(1-\tanh(\beta
M))\frac{2}{Nd}\cdot\frac{cdN}{8}=1-(1-\tanh(\beta M))\frac{c}{4},$

which implies that there exists a constant $c^{\prime}>0$ such that

$\displaystyle\partial_{\beta}\operatorname{\mathds{E}}F_{z}(\beta,h)$
$\displaystyle\geqslant\beta^{2}c^{\prime}>0.$

Hence,

$\displaystyle\partial_{\beta}\operatorname{\mathds{E}}F_{g}(\beta,h)$
$\displaystyle\geqslant\beta^{2}c^{\prime}-\frac{C\beta^{3}}{\sqrt{d}}.$ (37)

Finally, from the concentration of the free energy in the Proposition 3.2 and
the Lemma 3.1, we have

$\displaystyle\liminf_{N\to\infty}\bigl{(}F_{g}(\beta,h)-F_{g}(0,h)\bigr{)}$
$\displaystyle=\liminf_{N\to\infty}\bigl{(}\operatorname{\mathds{E}}F_{z}(\beta,h)-\operatorname{\mathds{E}}F_{z}(0,h)\bigr{)}$
$\displaystyle=\liminf_{N\to\infty}\int_{0}^{\beta}\partial_{t}\operatorname{\mathds{E}}F_{z}(t,h)dt$
$\displaystyle\geqslant\liminf_{N\to\infty}(\beta-\beta_{0})\partial_{t}\operatorname{\mathds{E}}F_{z}(\beta_{0},h)>0$

for $\beta_{0}<\beta,$ where the last inequality used the fact that
$\partial_{t}\operatorname{\mathds{E}}F_{z}(t,h)$ is a nondecreasing function
in $t$ as well as (37). The asserted exponential tail probability is
guaranteed by Proposition 3.2.

$\blacksquare$

##  4\. Proof of Theorem 1.5

We first establish the bound for the expected operator norm of
$J=\frac{1}{\sqrt{d}}A\circ G$. It relies on the following fundamental result
in [BvH16]*Corollary 3.3, which we recall as follows.

######  Lemma 4.1 ([BvH16]*Corollary 3.3).

Consider the $N\times N$ symmetric random matrix $X$ whose entries
$X_{ij}:=b_{ij}g_{ij}$ for $i\geqslant j$, where $b_{ij}\in\mathbb{R}$ and
$g_{ij}$ are independent centered subgaussian. Then

$\operatorname{\mathds{E}}\left\|X\right\|\lesssim\max_{i}\sqrt{\sum_{j}b_{ij}^{2}}+\sqrt{\log
N}\cdot\max_{ij}\left|b_{ij}\right|.$

Appling this result in our setting for the matrix $J$, it immediately gives
the following lemma.

######  Lemma 4.2.

If the entries of the symmetric matrix $G$ are independent centered
subgaussian random variables, then we have for a universal constant $C>0$ such
that

$\operatorname{\mathds{E}}\left\|J\right\|\leqslant C\left(\sqrt{\frac{\log
N}{d}}+\sqrt{\frac{d_{\rm{max}}}{d}}\right).$

###### Proof.

The proof is immediate after applying the Corollary 3.3 in [BvH16].
$\blacksquare$

Now it can be seen that under the Assumption 1.3, we have
$\operatorname{\mathds{E}}\left\|J\right\|=O(1)$. To complete the proof of
Theorem 1.5, the rest is to prove the following concentration results for
$\left\|J\right\|$.

######  Lemma 4.3.

If the entries of the symmetric matrix $G$ are independent centered
$\kappa^{2}$-subgaussian random variables for some $K\geqslant 1$, then we
have for some universal constant $C>0$,

$\mathbb{P}(\left|\left\|J\right\|-\operatorname{\mathds{E}}\left\|J\right\|\right|\geqslant
t)\leqslant 2\exp\left(-\frac{Cdt^{2}}{\kappa^{4}\log(Nd)}\right).$

The major ingredient for the proof of Lemma 4.3 is the following concentration
result for subgaussian matrices appeared in [CDG23]. We include this result
for reader’s convenience.

######  Lemma 4.4 ([CDG23]*Proposition A.1).

Let $\boldsymbol{X}:=(X_{1},\ldots,X_{d})$ be a vector of independent
$K$-subgaussian random variables for some $K\geqslant 1$. Let
$f:\mathbb{R}^{d}\to\mathbb{R}$ be a convex 1-Lipschitz function. Then for
$s\geqslant 0$,

$\mathbb{P}(\left|f(\boldsymbol{X})-\operatorname{\mathds{E}}f(\boldsymbol{X})\right|\geqslant
s)\leqslant 2\exp\left(-\frac{cs^{2}}{K^{2}\log d}\right),$

where $c>0$ is some universal constant. Moreover,
$\operatorname{\mathds{E}}f(\boldsymbol{X})$ can be replaced by any median of
$f(\boldsymbol{X})$.

###### Proof of Lemma 4.3.

We will apply the result [CDG23]*Proposition A.1 for subgaussian random matrix
to complete the proof. Note that in our setting, the operator norm is
obviously a convex function. On the other hand, since for general matrices
$A,B$,

$\left|\left\|A\right\|-\left\|B\right\|\right|\leqslant\left\|A-B\right\|_{F},$

where $\left\|\cdot\right\|_{F}$ denotes the Frobenius norm. This implies the
Lipschitz property of the operator norm. There are in total $Nd$ many nonzero
entries in $J$, then directly from [CDG23]*Proposition A.1,

$\mathbb{P}(\left|\left\|J\right\|-\operatorname{\mathds{E}}\left\|J\right\|\right|\geqslant
t)\leqslant 2\exp\left(-\frac{Cdt^{2}}{\kappa^{4}\log(Nd)}\right).$

$\blacksquare$

Now we put the above two lemmas together to complete the proof of Theorem 1.5.

###### Proof of Theorem 1.5.

Using the Assumption 1.3, it is easy to see that
$\operatorname{\mathds{E}}\left\|J\right\|=O(1)$ from Lemma 4.2. On the other
hand, since $d\gg\log d$, the r.h.s in the concentration bound of Lemma 4.3
can be bounded as follows,

$2\exp\left(-\frac{Cdt^{2}}{K^{2}\log(Nd)}\right)\leqslant
2\exp\left(-\frac{Cdt^{2}}{K^{2}\log(N)}\right).$

Using $d\gg\log N$ in the Assumption 1.3, we have the desired results.
$\blacksquare$

##  5\. Proof of Theorem 1.6

The proof of Theorem 1.6 uses a linear size set of the vertices of
$\mathcal{G}$ with all of its vertices having at least $cd$ many neighbors
outside the set. We start by showing that such a set always exists.

For a subset of vertices $Q\subseteq[N]$, denote by $d^{\mathrm{out}}_{i}(Q)$
the number of neighbors of $i$ outside $Q$ in $\mathcal{G}$, i.e.,

$d^{\mathrm{out}}_{i}(Q)=|\\{j\in Q^{c}:(i,j)\in E\\}|.$

######  Definition 5.1.

For $\delta>0,k\geqslant 1$, we call a subset of vertices $T\subseteq[N]$ of
$\mathcal{G}$ $(\delta,k)$-good if $|T|\geqslant\delta N$ and
$d^{\mathrm{out}}_{i}(T)\geqslant k$ for all $i\in T$.

The following lemma guarantees the existence of a _good_ set $T$ under the
assumption of $d_{\max}\leqslant Cd$.

######  Lemma 5.2.

Let $\mathcal{G}$ be any graph on $N\geqslant 2$ vertices such that
$d_{\max}\leqslant Cd$. There exists a subset $T\subseteq[N]$ that is
$(1/(16C),d/4)$-good.

To establish this lemma, we need an elementary result that states that given a
graph $\mathcal{G}$, we can always find a good expander subset $S\subseteq[N]$
with a large number of outgoing edges, see, e.g. [AS08]*Theorem 2.2.2.

######  Lemma 5.3.

Let $\mathcal{G}=([N],E)$ be a graph with $N\geqslant 2$ vertices. Then there
exists $S\subseteq[N]$ with $|S|=\lfloor{N}/{2}\rfloor$ and
$\left|E(S,S^{c})\right|\geqslant\left|E\right|/{2}={Nd}/{4}$, where
$E(S,S^{c})=\\{(i,j)\in E:i\in S,j\in S^{c}\\}$ and $d$ is the total average
degree.

###### Proof.

Let $\ell=\lfloor{N}/{2}\rfloor$. Choose a random set $U\subseteq[N]$ with
$|U|=\ell$ uniformly at random from the set of all subsets of $[N]$ of size
$\ell$. Note that for each $e\in E,$

$\mathbb{P}(e\in
E(U,U^{c}))=1-\frac{{\binom{\ell}{2}}+{\binom{N-\ell}{2}}}{{\binom{N}{2}}}\geqslant\frac{1}{2}.$

Since we can write

$|E(U,U^{c})|=\sum_{e\in E}\mathds{1}_{\\{e\in E(U,U^{c})\\}},$

it follows from the linearity of expectation that
$\mathbb{E}|E(U,U^{c})|\geqslant|E|/2.$ Therefore, there exists a
(deterministic) subset $S$ of size $\ell$ such that
$|E(S,S^{c})|\geqslant|E|/2,$ as claimed. $\blacksquare$

###### Proof of Lemma 5.2.

Fix a subset $S$ as guaranteed by the previous lemma. Let

$\displaystyle T=\Bigl{\\{}i\in
S:d^{\mathrm{out}}_{i}(S)\geqslant\frac{d}{4}\Bigr{\\}},$

which contains the vertices in $S$ with at least ${d}/{4}$ many outgoing edges
to $S^{c}$. Now let $I$ be a uniform random variable on $S$. Write

$\displaystyle\frac{1}{\left|S\right|}\sum_{i\in
S}d^{\mathrm{out}}_{i}(S)=\operatorname{\mathds{E}}d^{\mathrm{out}}_{I}(S)$
$\displaystyle\leqslant\max_{i\in
S}d^{\mathrm{out}}_{i}(S)\cdot\mathbb{P}(I\in T)+\frac{d}{4}\mathbb{P}(I\notin
T)$ $\displaystyle\leqslant Cd\mathbb{P}(I\in T)+\frac{d}{4}(1-\mathbb{P}(I\in
T)).$

Note that since

$\frac{1}{\left|S\right|}\sum_{i\in
S}d^{\mathrm{out}}_{i}(S)=\frac{E(S,S^{c})}{|S|}\geqslant\frac{Nd/4}{\lfloor
N/2\rfloor}\geqslant\frac{d}{2},$

we have

$\frac{1}{2}\leqslant(C-1/4)\mathbb{P}(I\in T)+\frac{1}{4}.$

It follows that

$\mathbb{P}(I\in T)\geqslant\frac{1/4}{C-1/4}\geqslant\frac{1}{4C},$

which implies $\left|T\right|\geqslant{\left|S\right|}/{(4C)}={N}/{(16C)}$.
Furthermore, for each $i\in T$, we have $d^{\mathrm{out}}_{i}(T)\geqslant
d^{\mathrm{out}}_{i}(S)\geqslant d/4$. This completes the proof of Lemma 5.2.
$\blacksquare$

From now on, for the rest of Section 5, we fix a $(1/(16C),d/4)$-good subset
$T$ as ensured by Lemma 5.2. We employ a union bound over
${\sigma}\in\\{-1,+1\\}^{N}$ to prove Theorem 1.6; the heart of the proof lies
the following crucial uniform bound on the $\ell_{2}$-deviation of
${m}({\sigma})$ from a constant vector.

######  Proposition 5.4.

Under the same conditions of Theorem 1.6, there exist positive constants
$\delta$ and $K$ such that for any $N\geqslant 1$,
${\sigma}\in\\{-1,+1\\}^{N}$, and $\gamma\in\mathbb{R}$, we have

$\displaystyle\mathbb{P}\Bigl{(}\min_{A\subseteq
T:|A|\geqslant\frac{\left|T\right|}{2}}\left\|{m}_{A}({\sigma})-\gamma\boldsymbol{1}_{A}\right\|_{2}\leqslant\delta\sqrt{N}\Bigr{)}\leqslant\frac{K}{10^{N}},$
(38)

where $m_{A}({\sigma}):=(m_{i}({\sigma}))_{i\in A}$ and
$\boldsymbol{1}_{A}:=(1)_{i\in A}$.

We first see how this proposition implies that $T_{N}({\sigma})$ is bounded
away from zero uniformly in ${\sigma}$ with high probability, which is a
weaker form of Theorem 1.6. The proof of Proposition 5.4 is deferred to
Subsection 5.1.

######  Proposition 5.5.

Under the same conditions of Theorem 1.6, there exist positive constants
$c_{1},c$, and $K$ such that for any $N\geqslant 1,$

$\mathbb{P}\bigl{(}\min_{{\sigma}}T_{N}({\sigma})\leqslant
c_{1}\bigr{)}\leqslant K\exp(-cN).$

###### Proof.

First, for any $M>0,$ if $\max_{{\sigma}}|\bar{m}({\sigma})|\leqslant M,$ we
can write

$\displaystyle\frac{1}{N}\min_{{\sigma}}\sum_{i\in[N]}(m_{i}({\sigma})-\bar{m}({\sigma}))^{2}$
$\displaystyle=\frac{1}{N}\min_{{\sigma}}\left\|{m}({\sigma})-\bar{m}({\sigma})\boldsymbol{1}\right\|_{2}^{2}$
$\displaystyle=\frac{1}{N}\min_{{\sigma}}\inf_{\gamma\in[-M,M]}\left\|{m}({\sigma})-\gamma\boldsymbol{1}\right\|_{2}^{2},$

which implies that

$\displaystyle\mathbb{P}\Bigl{(}\frac{1}{N}\min_{{\sigma}}\inf_{\gamma\in\mathbb{R}}\bigl{\|}{m}({\sigma})-\gamma\boldsymbol{1}\bigr{\|}_{2}^{2}\leqslant
c_{1}\Bigr{)}$
$\displaystyle\leqslant\mathbb{P}\left(\max_{{\sigma}}\left|\bar{m}({\sigma})\right|>M\right)$
$\displaystyle+\mathbb{P}\Bigl{(}\frac{1}{N}\min_{{\sigma}}\inf_{\gamma\in[-M,M]}\left\|{m}({\sigma})-\gamma\boldsymbol{1}\right\|_{2}^{2}\leqslant
c_{1}\Bigr{)}.$

To bound the two probabilities on the right-hand side, first of all, note that

$\left|\bar{m}({\sigma})\right|=\Bigl{|}\frac{1}{N}\sum_{i\in[N]}m_{i}({\sigma})\Bigr{|}\leqslant\frac{1}{N}\sum_{i,j\in[N]}\left|J_{ij}\right|,$

by Markov’s inequality, for a large constant $M=2^{N}$,

$\displaystyle\mathbb{P}\left(\max_{{\sigma}}\left|\bar{m}({\sigma})\right|>M\right)$
$\displaystyle\leqslant\frac{\sum_{i,j\in[N]}\operatorname{\mathds{E}}\left|J_{ij}\right|}{NM}$
$\displaystyle=\frac{d\operatorname{\mathds{E}}\left|J\right|}{2^{N}}\leqslant\frac{C}{1.5^{N}}.$

As for the second probability, consider an arbitrary partition
$\mathcal{D}=(e_{i})_{i\in[2M]}$ of $[-M,M]$ with
$|e_{i}-e_{i-1}|<\varepsilon$ for $i\in[2M]$. From this,

$\frac{1}{N}\min_{{\sigma}}\inf_{\gamma\in[-M,M]}\left\|{m}({\sigma})-\gamma\boldsymbol{1}\right\|_{2}^{2}\geqslant\frac{1}{N}\min_{{\sigma}}\inf_{\gamma\in\mathcal{D}}\left\|{m}({\sigma})-\gamma\boldsymbol{1}\right\|_{2}^{2}-\varepsilon^{2}.$

and thus,

$\mathbb{P}\Bigl{(}\frac{1}{N}\min_{{\sigma}}\inf_{\gamma\in[-M,M]}\left\|{m}({\sigma})-\gamma\boldsymbol{1}\right\|\leqslant
c_{1}\Bigr{)}\leqslant\mathbb{P}\Bigl{(}\frac{1}{N}\min_{{\sigma}}\inf_{\gamma\in\mathcal{D}}\left\|{m}({\sigma})-\gamma\boldsymbol{1}\right\|\leqslant
c_{1}+\varepsilon^{2}\Bigr{)}.$

Applying Proposition 5.4 with $\varepsilon^{2}+c_{1}=\delta^{2}$, we have that
for any ${\sigma}$ and $\gamma\in\mathcal{D}$,

$\mathbb{P}(\left\|{m}({\sigma})-\gamma\boldsymbol{1}\right\|_{2}\leqslant\delta\sqrt{N})\leqslant\mathbb{P}\Bigl{(}\min_{A\subseteq
T:|A|\geqslant\frac{\left|T\right|}{2}}\left\|{m}_{A}({\sigma})-\gamma\boldsymbol{1}_{A}\right\|_{2,A}\leqslant\delta\sqrt{N}\Bigr{)}\leqslant\frac{K}{10^{N}}.$

Finally taking union bound over ${\sigma}$ and $\gamma$ yields

$\mathbb{P}\Bigl{(}\min_{{\sigma}}\inf_{\gamma\in\mathcal{D}}\left\|{m}({\sigma})-\gamma\boldsymbol{1}\right\|\leqslant\delta\sqrt{N}\Bigr{)}\leqslant
c^{\prime}\cdot 10^{-N}\cdot 2^{N}\cdot M,$

completing our proof. $\blacksquare$

###  5.1. Proof of Proposition 5.4

The proof of Proposition 5.4 relies on certain small-ball probability
estimates. To this end, we first recall the following classical small-ball
probability result for the linear combination of independent random variables.

######  Lemma 5.6 ([RV08]*Corollary 2.9).

Let $\xi_{1},\ldots,\xi_{n}$ be independent centered random variables with
variances at least 1 and third moments bounded by $B$. Then for any
$\boldsymbol{a}\in\mathbb{R}^{n}$ and $\varepsilon>0$, one has

$\sup_{v\in\mathbb{R}}\mathbb{P}\Bigl{(}\Bigl{|}\sum_{k=1}^{n}a_{k}\xi_{k}-v\Bigr{|}\leqslant\varepsilon\Bigr{)}\leqslant\sqrt{\frac{2}{\pi}}\frac{\varepsilon}{\left\|\boldsymbol{a}\right\|_{2}}+C_{0}B\Bigl{(}\frac{\left\|\boldsymbol{a}\right\|_{3}}{\left\|\boldsymbol{a}\right\|_{2}}\Bigr{)},$

where $C_{0}$ is some absolute constant.

We also need the following tensorization result.

######  Lemma 5.7 ([RV08]*Lemma 2.2).

Let $\zeta_{1},\ldots\zeta_{n}$ be independent random variables. Assume that
there exist constants $K$ and $\varepsilon_{0}>0$ such that for each $i$,
$\mathbb{P}(\left|\zeta_{i}\right|<\varepsilon)\leqslant K\varepsilon$ for all
$\varepsilon\geqslant\varepsilon_{0}$. Then there exists an absolute constant
$C_{1}$ depending only on $K$ and $\varepsilon_{0}$ such that

$\mathbb{P}\Bigl{(}\sum_{i=1}^{n}\zeta_{i}^{2}<\varepsilon^{2}n\Bigr{)}\leqslant(C_{1}K\varepsilon)^{n}$

for all $\varepsilon\geqslant\varepsilon_{0}$.

Our goal is to combine Lemma 5.6 and Lemma 5.7 to establish some small-ball
probability estimate for the vector ${m}({\sigma})$. However, because the
matrix $J$ is symmetric, the random variables
$m_{1}({\sigma}),m_{2}({\sigma}),\ldots,m_{N}({\sigma})$ are not independent.
To circumvent this obstacle, we will make use of the fact that the entries in
any off-diagonal block sub-matrices of $J$ are independent. In particular, we
shall work with the sub-matrix $D_{2}$ of $J$ defined on the block $T\times
T^{c}$, where $T$ is a $(1/(16C),d/4)$-good subset as in Lemma 5.2. With this
choice of $T$, we partition the vertex set as $[N]=T\cup([N]\setminus T)$ and
accordingly write
${\sigma}=({\sigma}^{(1)},{\sigma}^{(2)})\in\\{-1,+1\\}^{T}\times\\{-1,+1\\}^{[N]\setminus
T}$. Similarly we represent $J$ (after possible permutation of the $N$
vertices) in the following block form,

Figure 1. Block decomposition of matrix $J$, where $D_{1}$ is a
$\left|T\right|\times\left|T\right|$ matrix with row and column index set $T$,
while $D_{2}$ has row index set $T$ and column index set $[N]\setminus T$. It
can be seen that the entries in the block $D_{2}$ are independent from each
other.

$\displaystyle J=\begin{pmatrix}D_{1}&D_{2}\\\ D_{2}^{T}&*\end{pmatrix},$ (39)

where $D_{1}\in\mathbb{R}^{\left|T\right|\times\left|T\right|}$ and
$D_{2}\in\mathbb{R}^{\left|T\right|\times(N-\left|T\right|)}$, also see the
visualization in Figure 1. Let $r_{i}$ be the number of non-zero elements in
the $i$-th row of $D_{2}$. Note that $r_{i}$ is same as
$d^{\mathrm{out}}_{i}(T)$ for $i\in T$. It follows from the definition of $T$,

$\displaystyle\frac{d}{4}\leqslant r_{i}\leqslant Cd.$ (40)

Under the above decomposition,

$\quad(D_{2}{\sigma}^{(2)})_{i}=\sum_{j\in[N]\setminus
T}J_{ij}\sigma_{j},\,\,\forall i\in T,$

it can be readily seen that the coordinates in $D_{2}{\sigma}^{(2)}$ are now
independently from each other. We now use this property and the bound in (40)
to establish the desired small ball probability estimates and use them to
further prove the Proposition 5.4.

###### Proof of Proposition 5.4.

Recall that $A=(a_{ij})_{i,j}$ is the adjacency matrix of $\mathcal{G}.$
First, as we have explained above that $(D_{2}{\sigma}^{(2)})_{i\in
T}=(\langle\boldsymbol{a}_{i},\boldsymbol{g}_{i}\rangle)_{i\in T}$ has
independent coordinates and proper moment assumptions, where

$\displaystyle\boldsymbol{a}_{i}$
$\displaystyle:=d^{-1/2}(a_{i,\left|T\right|+1}\sigma_{\left|T\right|+1},\ldots,a_{i,N}\sigma_{N}),$
$\displaystyle\boldsymbol{g}$
$\displaystyle:=(g_{i,|T|+1},g_{i,|T|+2,},\ldots,g_{i,N}).$

Recall that (40) implies

$r_{i}=\left|\\{j\in[N]\setminus T:a_{ij}=1\\}\right|\in[d/4,Cd].$

In addition, since

$\displaystyle\left\|\boldsymbol{a}_{i}\right\|_{2}^{2}=\frac{r_{i}}{d}\,\,\text{and}\,\,\left\|\boldsymbol{a}_{i}\right\|_{3}^{3}=\frac{r_{i}}{d^{3/2}},$

we have

$\left\|\boldsymbol{a}_{i}\right\|_{2}\in[1/2,\sqrt{C}]\,\,\text{and}\,\,\Bigl{(}\frac{\left\|\boldsymbol{a}_{i}\right\|_{3}}{\left\|\boldsymbol{a}_{i}\right\|_{2}}\Bigr{)}^{3}=\frac{1}{\sqrt{r_{i}}}\leqslant\frac{2}{\sqrt{d}}.$

By Lemma 5.6, we have that for any $i\in T$ and $\varepsilon>0$

$\sup_{v\in\mathbb{R}}\mathbb{P}\bigl{(}\bigl{|}(D_{2}{\sigma}^{(2)})_{i}-v\bigr{|}\leqslant\varepsilon\bigr{)}\lesssim\varepsilon.$

Combining with Lemma 5.7, there exists a constant $\delta>0$ such that for any
$A\subseteq T$ with
$\left|A\right|\geqslant\left|T\right|/{2}\geqslant{N}/(32C)$, we have

$\sup_{\boldsymbol{v}\in\mathbb{R}^{\left|A\right|}}\mathbb{P}\bigl{(}\bigl{\|}(D_{2}{\sigma}^{(2)})_{i\in
A}-\boldsymbol{v}\bigr{\|}_{2}^{2}\leqslant\delta^{2}N\bigr{)}\lesssim
10^{-N}.$

Recall ${m}_{A}({\sigma})=(m_{i}({\sigma}))_{i\in A}$. Using the previous
decomposition of $J$ in (39), we observe that

$\left\|{m}_{A}({\sigma})-\gamma\boldsymbol{1}\right\|_{2}^{2}\geqslant\bigl{\|}(D_{1}{\sigma}^{(1)}+D_{2}{\sigma}^{(2)})_{i\in
A}-\gamma\boldsymbol{1}_{A}\bigr{\|}_{2}^{2}.$

Then

$\displaystyle\mathbb{P}\bigl{(}\left\|{m}_{A}({\sigma})-\gamma\boldsymbol{1}_{A}\right\|_{2}^{2}\leqslant\delta^{2}N\bigr{)}$
$\displaystyle\leqslant$
$\displaystyle\mathbb{P}\bigl{(}\bigl{\|}(D_{1}{\sigma}^{(1)}+D_{2}{\sigma}^{(2)})_{i\in
A}-\gamma\boldsymbol{1}_{A}\bigr{\|}_{2}^{2}\leqslant\delta^{2}N\bigr{)}$
$\displaystyle=$
$\displaystyle\operatorname{\mathds{E}}_{D_{1}}\Bigl{[}\mathbb{P}\bigl{(}\bigl{\|}(D_{1}{\sigma}^{(1)}+D_{2}{\sigma}^{(2)})_{i\in
A}-\gamma\boldsymbol{1}_{A}\bigr{\|}_{2}^{2}\leqslant\delta^{2}N\big{|}(D_{1}{\sigma}^{(1)})_{i\in
A}\bigr{)}\Bigr{]}$ $\displaystyle\leqslant$
$\displaystyle\operatorname{\mathds{E}}_{D_{1}}\Bigl{[}\sup_{\boldsymbol{v}\in\mathbb{R}^{\left|A\right|}}\mathbb{P}\bigl{(}\bigl{\|}(D_{2}{\sigma}^{(2)}\bigr{\|}_{i\in
A}-\boldsymbol{v}\bigr{\|}_{2}^{2}\leqslant\delta^{2}N\bigr{)}\Bigr{]}$
$\displaystyle\leqslant$
$\displaystyle\sup_{\boldsymbol{v}\in\mathbb{R}^{\left|A\right|}}\mathbb{P}\bigl{(}\bigl{\|}(D_{2}{\sigma}^{(2)})_{i\in
A}-\boldsymbol{v}\bigr{\|}_{2}^{2}\leqslant\delta^{2}N\bigr{)}\leqslant\frac{K}{10^{N}}$

for some constant $K$. Since $A$ is arbitrary subset of $T$ with
$\left|A\right|\geqslant\left|T\right|/2$, we have

$\displaystyle\mathbb{P}\left(\min_{A\subseteq
T:|A|\geqslant\frac{\left|T\right|}{2}}\left\|{m}_{A}({\sigma})-\gamma\cdot\boldsymbol{1}_{A}\right\|_{2}\leqslant\delta\sqrt{N}\right)\leqslant\frac{K}{10^{N}}.$

$\blacksquare$

###  5.2. Proof of Theorem 1.6

In this section, we will complete the proof of Theorem 1.6. First, we prove
the following result that states that with high probability, for each
${\sigma}$, the variables $m_{i}({\sigma})$ are bounded for at least half of
the indices in $T$.

######  Proposition 5.8.

Assume $d_{\max}\leqslant Cd$. There exist constants $M,K>0$ such that the
following event

$\min_{{\sigma}}|\\{i\in T:|m_{i}({\sigma})|\leqslant
M\\}|\geqslant\frac{|T|}{2}$

occurs with probability at least $1-K\cdot 10^{-N}$.

###### Proof.

Consider the matrix $J_{T}:=(D_{1},D_{2})$, where $D_{1},D_{2}$ were defined
in (39). Note that for each fixed ${\sigma}$,

$m_{T}({\sigma})=J_{T}{\sigma}=D_{1}{\sigma}^{(1)}+D_{2}{\sigma}^{(2)},$

Decompose $D_{1}$ as

$D_{1}=D_{1}^{+}+D_{1}^{-},$

where

$(D_{1}^{+})_{ij}:=\begin{cases}(D_{1})_{ij},&\text{if $i<j$,}\\\ 0,&\text{if
$i\geqslant
j$,}\end{cases}\,\,\text{and}\,\,(D_{1}^{-})_{ij}:=\begin{cases}(D_{1})_{ij},&\text{if
$i>j$,}\\\ 0,&\text{if $i\leqslant j$.}\end{cases}$

Accordingly, we have the decomposition for $J_{T}=J_{T}^{+}+J_{T}^{-}$ with

$J_{T}^{+}:=(D_{1}^{+},D_{2})\,\,\text{and}\,\,J_{T}^{-}:=(D_{1}^{-},\boldsymbol{0}).$

In this way, it can be seen that the entries in $J_{T}^{+}$ are independent
and so are the entries of $J_{T}^{-}$. We let
$m_{T}^{+}({\sigma}):=J_{T}^{+}{\sigma}$ and
$m_{T}^{-}({\sigma}):=J_{T}^{-}{\sigma}$, whose coordinates are now
independent. For $i\in T$, notice

$\displaystyle\operatorname{\mathds{E}}m_{i}^{\pm}({\sigma})=0\,\,\text{and}\,\,\operatorname{Var}(m_{i}^{\pm}({\sigma}))=\operatorname{\mathds{E}}[(m_{i}^{\pm}({\sigma}))^{2}]\leqslant\frac{d_{i}}{d}\leqslant
C.$

The last inequality in the variance bound used the assumption
$d_{\max}\leqslant Cd$ and the independence among the entries of
$J_{T}^{+},J_{T}^{-}$. Consequently, from Chebyshev’s inequality, we have that
for $i\in T$,

$\mathbb{P}\Bigl{(}\left|m_{i}^{\pm}({\sigma})\right|\geqslant\frac{M}{2}\Bigr{)}\leqslant\frac{4C}{M^{2}}.$

Next, set

$\displaystyle B^{+}_{{\sigma}}:=\Bigl{\\{}i\in
T,\Big{|}\left|m_{i}^{+}({\sigma})\right|\leqslant\frac{M}{2}\Bigr{\\}}\,\,\text{and}\,\,B^{-}_{{\sigma}}:=\Bigl{\\{}i\in
T,\Big{|}\left|m_{i}^{-}({\sigma})\right|\leqslant\frac{M}{2}\Bigr{\\}}.$

Evidently,

$\left|B_{{\sigma}}^{+}\right|\sim\mathrm{Binomial}\left(\left|T\right|,p\right)\,\,\text{and}\,\,\left|B_{{\sigma}}^{-}\right|\sim\mathrm{Binomial}\left(\left|T\right|,p\right),$

where $p$ is some constant with $p\geqslant 1-{4C}/{M^{2}}$. Now, by the
binomial concentration, one can choose sufficiently large $M$ such that

$P\Bigl{(}\left|B_{{\sigma}}^{+}\right|,\left|B_{{\sigma}}^{-}\right|\geqslant\frac{4}{5}\left|T\right|\Bigr{)}\geqslant
1-\frac{K}{20^{N}}$

for some constant $K>0$ independent of $N.$ Let
$B_{{\sigma}}:=B_{{\sigma}}^{+}\cap B_{{\sigma}}^{-}$. Using the identity

$|B_{{\sigma}}|=|B_{{\sigma}}^{+}|+|B_{{\sigma}}^{-}|-|B_{{\sigma}}^{+}\cup
B_{{\sigma}}^{-}|,$

with probability at least $1-K/20^{N}$,

$\left|B_{{\sigma}}\right|\geqslant\frac{4}{5}\left|T\right|+\frac{4}{5}\left|T\right|-\left|T\right|\geqslant\frac{1}{2}\left|T\right|,$

which readily implies that

$\displaystyle\left|m_{i}({\sigma})\right|\leqslant\left|m_{i}^{+}({\sigma})\right|+\left|m_{i}^{-}({\sigma})\right|\leqslant\frac{M}{2}+\frac{M}{2}=M$

for $i\in B_{{\sigma}}$ and as a consequence,

$|\\{i\in T:|m_{i}({\sigma})|\leqslant M\\}|\geqslant\frac{|T|}{2}.$

Finally, applying union bound with resepct to ${\sigma}\in\\{-1,+1\\}^{N}$
leads to the desired result. $\blacksquare$

We proceed to establish the proof of Theorem 1.6 via this proposition.

###### Proof of Theorem 1.6.

For each fixed ${\sigma}$, let

$B_{{\sigma}}=\\{i\in T:\left|m_{i}({\sigma})\right|\leqslant M\\}.$

By Proposition 5.8, there exist a constant $M>0$ sufficiently large such that
with probability at least $1-K/10^{N}$, we have
$\min_{{\sigma}}\left|B_{{\sigma}}\right|\geqslant{\left|T\right|}/{2}\geqslant{N}/{(32C)}$.
Consequently, for $i\in B_{{\sigma}}$

$\theta_{i}({\sigma})=\operatorname{sech}(\beta m_{i}({\sigma})+h)\geqslant
c^{\prime\prime}:=\operatorname{sech}(\beta M+|h|).$

Note that

$\displaystyle\widetilde{T}_{N}({\sigma})$
$\displaystyle\geqslant\frac{1}{N^{2}}\sum_{i,j\in
B_{{\sigma}}}(m_{i}({\sigma})-m_{j}({\sigma}))^{2}\theta_{i}({\sigma})\theta_{j}({\sigma})$
$\displaystyle\geqslant\frac{(c^{\prime\prime})^{2}}{N^{2}}\sum_{i,j\in
B_{{\sigma}}}(m_{i}({\sigma})-m_{j}({\sigma}))^{2}$
$\displaystyle=\frac{2(c^{\prime\prime})^{2}}{N}\sum_{i\in
B_{{\sigma}}}(m_{i}({\sigma})-\bar{m}_{B_{{\sigma}}}({\sigma}))^{2},$

where $\bar{m}_{B_{{\sigma}}}({\sigma})$ is the average of
${m}_{B_{{\sigma}}({\sigma})}({\sigma}).$ Therefore, on the event
$|B_{{\sigma}}|\geqslant\left|T\right|/{2}$, we have

$\displaystyle\widetilde{T}_{N}({\sigma})$
$\displaystyle\geqslant\frac{2(c^{\prime\prime})^{2}}{N}\inf_{\gamma\in[-M,M]}\sum_{i\in
B_{{\sigma}}}(m_{i}({\sigma})-\gamma)^{2}$
$\displaystyle\geqslant\frac{2(c^{\prime\prime})^{2}}{N}\inf_{\gamma\in[-M,M]}\min_{A\subseteq
T:|A|\geqslant|T|/2}\sum_{i\in A}(m_{i}({\sigma})-\gamma)^{2}$
$\displaystyle\geqslant\frac{2(c^{\prime\prime})^{2}}{N}\inf_{\gamma\in\mathcal{D}}\min_{A\subseteq
T:|A|\geqslant|T|/2}\Bigl{(}\left\|{m}_{A}({\sigma})-\gamma\cdot\boldsymbol{1}\right\|_{2}-\frac{\delta\sqrt{N}}{2}\Bigr{)}_{+}^{2},$
(41)

where $\mathcal{D}$ is an arbitrary partition of $[-M,M]$ with mash
$(\delta/2)$ and $|\mathcal{D}|\leqslant 10M\delta^{-1}$. Applying Proposition
5.4 for a fixed $\gamma$ and ${\sigma}$ in (41) and then taking a union bound
over $\gamma\in\mathcal{D}$ and ${\sigma}$, we obtain, for
$c_{0}=(c^{\prime\prime})^{2}\delta^{2}/2$,

$\displaystyle\mathbb{P}\bigl{(}\min_{{\sigma}}\widetilde{T}_{N}({\sigma})\leqslant
c_{0}\bigr{)}\leqslant K10^{-N}+|\mathcal{D}|2^{N}\cdot K10^{-N}.$

The proof of Theorem 1.6 now immediately follows. $\blacksquare$

## References