arbitrarily small (constant) probability, the random SK measure will satisfy
deterministic conditions that will ensure that the learning algorithm succeeds
with high probability given sufficient (polynomial) samples, where this latter
probability is taken just over the samples and the sub-polynomial factor of
the sample complexity depends on the original probability parameter.

To establish Theorem 6.8, we will follow similar reasoning to Theorem 6.6 by
leveraging recent bounds on the operator norm of the covariance matrix. Notice
that the argument actually required control of the _second moment_ matrix of
the measure; in the zero field case, this is identical to the covariance
matrix. With external fields, the covariance matrix has a nontrivial negative
rank-one spike from the mean of the measure. For notation, we write

$\bm{m}=\bm{m}_{\beta,A,\bm{h}}=\mathbb{E}_{X\sim\mu_{\beta,A,\bm{h}}}[X]\in\mathbb{R}^{n}.$

From well-known results in the statistical physics literature, we expect that
$\|\bm{m}\|_{2}^{2}\approx qn$ with very high probability, so the rank-one
spike $\bm{m}\bm{m}^{T}$ cannot be neglected when attempting similar
calculations. In fact, from the variational characterization of eigenvalues,
the second moment matrix will truly be spectrally quite large. We show that
this does not affect the learning guarantees by arguing that $\bm{m}$ will be
roughly orthogonal with the rows of $A$ despite their nontrivial
dependencies141414If $\bm{m}$ were independent of the rows of $\beta A$, this
would be a simple consequence of Gaussian concentration.; this will in turn be
a consequence of the (proof of the) _Thouless-Anderson-Palmer (TAP) equations_
as rigorously established by Talagrand.

We will require the following two results to make this argument precise. Both
can be obtained from the existing spin glass literature; for the interested
reader, we explain how to derive them in Appendix A. The first are bounds on
the covariance matrices for the Sherrington-Kirkpatrick model with external
field given by Brennecke, Xu, and Yau [BXY23].

######  Theorem 6.9.

Let $\mathcal{A}$ satisfy the conditions of 1 and let
$(\beta,\mu,\sigma^{2})\in\mathcal{A}$. Suppose that either:

  1. 1.

(Small Inverse Temperature) It holds that $\overline{\beta}<1/2-\eta$ for some
$\eta>0$.

  2. 2.

(Deterministic Field) It holds that $\overline{\sigma}=0$ (that is, the
external field is deterministic and parallel to $\mathbf{1}$).

Then for any $\delta>0$, there exists
$K_{\ref{thm:cov_bound_external}}(\mathcal{A},\delta,\eta)$ independent of $n$
such that with probability at least $1-\delta$ over $A\sim\mathsf{GOE}(n)$,

$\|\mathrm{Cov}(\mu_{\beta,A,\bm{h}})\|_{\mathsf{op}}\leq
K_{\ref{thm:cov_bound_external}}(\mathcal{A},\delta,\eta).$

We also have the following key theorem which is instrumental in Talagrand’s
proof of the TAP equations [Tal10]:

######  Theorem 6.10.

Let
$\mathcal{A}=\mathcal{A}(\overline{\beta},\underline{h},\overline{h},\underline{\sigma}^{2},\overline{\sigma}^{2})$
satisfy the conditions of 1 with either $\underline{h}>0$ or
$\underline{\sigma}^{2}>0$. There is a constant
$C_{\ref{thm:tap_consequence}}(\mathcal{A})>0$ such that for any
$(\beta,\mu,\sigma^{2})\in\mathcal{A}$, there exists standard Gaussian random
variables $z_{1},\ldots,z_{n}$ such that

$\mathbb{E}_{A,\bm{h},\bm{z}}\left[\max_{i\in[n]}\left|\beta\sum_{j\neq
i}A_{ij}\bm{m}_{j}-\beta^{2}(1-q)\bm{m}_{i}-\beta
z_{i}\sqrt{q}\right|\right]\leq\frac{C_{\ref{thm:tap_consequence}}(\mathcal{A})}{n^{1/4}}.$

######  Remark 6.11.

The Gaussian random variables in the above are not independent of the
disorder, nor are they independent of each other. The key point is that one
can define random variables $z_{1},\ldots,z_{n}$ on the same sample space as
$A,\bm{h}$ such that the above conclusion holds and each $z_{i}$ is marginally
standard normal. The rate in $n$ can also be easily improved to
$n^{1/2-\gamma}$ for arbitrarily small $\gamma>0$ using techniques of
Talagrand, though this is not necessary for our application. We further note
that the requirement on $\underline{h}>0$ or $\underline{\sigma}>0$ is almost
certainly technical and could likely be removed. It arises from a certain
“discontinuity” when $q\to 0$ (see Chapter 1.6 of [Tal10] for more
discussion), even though the claim remains true in the limiting case trivially
since all terms are identically zero.

Again, we defer the proof of this result to Appendix A; it follows with some
moderate effort from existing results in the spin glass literature due to
Talagrand [Tal10]. However, we obtain the following crucial corollary:

######  Corollary 6.12.

Let
$\mathcal{A}=\mathcal{A}(\overline{\beta},\underline{h},\overline{h},\underline{\sigma}^{2},\overline{\sigma}^{2})$
satisfy the conditions of 1 with either $\underline{h}>0$ or
$\underline{\sigma}^{2}>0$. Then for any
$(\beta,\mu,\sigma^{2})\in\mathcal{A}$, and any $\delta>0$, we have151515The
dependence on $\delta$ can be improved by showing a version of Theorem 6.10
for higher powers. However, since we can only take $\delta>0$ constant anyway,
we omit this improvement.

$\Pr_{A,\bm{h}}\left(\max_{i\in[n]}\left|\beta\sum_{j\neq
i}A_{i,j}\bm{m}_{j}\right|\leq\beta\sqrt{2\log(4n/\delta)}+\beta^{2}+\frac{2C_{\ref{thm:tap_consequence}}(\mathcal{A})}{\delta
n^{1/4}}\right)\geq 1-\delta.$

###### Proof.

This follows readily from Theorem 6.10 and standard bounds on the maximum of
Gaussian random variables (no matter how they are correlated). First, we note
that by Markov’s inequality and Theorem 6.10, we have

$\Pr_{A,\bm{h},\bm{z}}\left(\max_{i\in[n]}\left|\beta\sum_{j\neq
i}A_{ij}\bm{m}_{j}-\beta^{2}(1-q)\bm{m}_{i}-\beta
z_{i}\sqrt{q}\right|\geq\frac{2C(\mathcal{A})}{\delta
n^{1/4}}\right)\leq\delta/2.$ (21)

Next, for any $n$ standard normal random variables $z_{1},\ldots,z_{n}$ on
some probability space, we have

$\Pr\left(\max_{i\in[n]}\left|z_{i}\right|\geq\sqrt{2\log(4n/\delta)}\right)\leq
n\Pr(|z_{1}|\geq\sqrt{2\log(4n/\delta)})\leq
2n\cdot\exp(-\log(4n/\delta))=\frac{\delta}{2},$ (22)

by 3.1 and a union bound. Since the complement of these two events imply the
event of the corollary statement by the triangle inequality, union bounding 21
and 22 gives the desired claim, noting that $q,\bm{m}_{i}\in[0,1]$. ∎

With these results in hand, we may formally show that the rows of $\beta\cdot
A$ are typically orthogonal to samples from $\mu_{\beta,A,\bm{h}}$, which is
sufficient to carry out the proof of learnability.

######  Corollary 6.13.

Let
$\mathcal{A}=\mathcal{A}(\overline{\beta},\underline{h},\overline{h},\underline{\sigma}^{2},\overline{\sigma}^{2})$
satisfy the conditions of 1 with either $\underline{h}>0$ or
$\underline{\sigma}^{2}>0$, and also assume one of the two additional
conditions of Theorem 6.9. Then for any
$(\beta,\mu,\sigma^{2})\in\mathcal{A}$, and any $\delta>0$, the following
holds with probability at least $1-\delta$ over $A\sim\mathsf{GOE}(n)$ and
$\bm{h}\sim\mathcal{N}(\mu\cdot\bm{1},\sigma^{2}\cdot I)$.

  1. 1.

It holds that

$\max_{i\in[n]}\|\beta
A_{i}\|_{1}+|h_{i}|\leq\beta\left(\sqrt{n}+\sqrt{\frac{\log(8n/\delta)}{c_{\ref{fact:norm_concentration}}}}\right)+\mu+\sqrt{2\sigma^{2}\ln(8n/\delta)}.$

  2. 2.

For $X\sim\mu_{\beta,A,\bm{h}}$ and any $j\in[n]$, it holds with probability
at least $3/4$ over $X$ that:

$\displaystyle\left|\beta\langle X,A_{j}\rangle+h_{j}\right|$
$\displaystyle\leq
4\beta\left(1+\sqrt{\frac{\log(8n/\delta)}{c_{\ref{fact:norm_concentration}}n}}\right)\cdot\sqrt{K_{\ref{thm:cov_bound_external}}(\mathcal{A},\delta/4,\eta)}$
$\displaystyle+4\beta\sqrt{2\log\left(\frac{16n}{\delta}\right)}+\frac{32C_{\ref{thm:tap_consequence}}(\mathcal{A})}{\delta
n^{1/4}}+\beta^{2}+\mu+\sqrt{2\sigma^{2}\ln\left(\frac{8n}{\delta}\right)}.$

While this bound looks complicated, we stress that for fixed $\mathcal{A}$ and
$\delta>0$, the bound grows only like $\sqrt{\log n}$ up to constants.

###### Proof of Corollary 6.13.

First, observe by 3.1 and a union bound, we have that

$\Pr\left(\max_{i\in[n]}|h_{i}|\geq\mu+\sqrt{2\sigma^{2}\ln(8n/\delta)}\right)\leq\delta/4.$

We also have by 3.2 and a union bound that

$\Pr\left(\max_{i\in[n]}\|\beta
A_{j}\|_{2}\geq\beta\left(1+\sqrt{\frac{\log(8n/\delta)}{c_{\ref{fact:norm_concentration}}n}}\right)\right)\leq\delta/4.$

We then apply Theorem 6.9 and Corollary 6.12 with error probability $\delta/4$
to conclude that with probability at least $1-\delta$ over
$A\sim\mathsf{GOE}(n)$ and
$\bm{h}\sim\mathcal{N}(\mu\cdot\bm{1},\sigma^{2}\cdot I)$, the following four
events hold:

$\displaystyle\max_{i\in[n]}|h_{i}|\leq\mu+\sqrt{2\sigma^{2}\ln(8n/\delta)}$
$\displaystyle\max_{i\in[n]}\|\beta
A_{j}\|_{2}\leq\beta\left(1+\sqrt{\frac{\log(8n/\delta)}{c_{\ref{fact:norm_concentration}}n}}\right)$
$\displaystyle\|\mathrm{Cov}(\mu_{\beta,A,\bm{h}})\|_{\mathsf{op}}\leq
K_{\ref{thm:cov_bound_external}}(\mathcal{A},\delta/4,\eta)$
$\displaystyle\max_{i\in[n]}\left|\beta\sum_{j\neq
i}A_{i,j}\bm{m}_{j}\right|\leq\beta\sqrt{2\log(16n/\delta)}+\beta^{2}+\frac{8C_{\ref{thm:tap_consequence}}(\mathcal{A})}{\delta
n^{1/4}}.$

Holder’s inequality with the first two inequalities implies the validity of
the first inequality in the theorem statement.

We now show that the second statement holds on this event. We easily compute
for any fixed $j\in[n]$,

$\displaystyle\mathbb{E}_{X}\left[\left|\beta\langle
X,A_{j}\rangle\right|\right]$
$\displaystyle\leq\mathbb{E}_{X}\left[\left|\beta\langle
X-\bm{m},A_{j}\rangle\right|\right]+\left|\beta\sum_{j\neq
i}A_{i,j}\bm{m}_{j}\right|$
$\displaystyle\leq\mathbb{E}_{X}\left[\left|\beta\langle
X-\bm{m},A_{j}\rangle\right|^{2}\right]^{1/2}+\beta\sqrt{2\log(16n/\delta)}+\beta^{2}+\frac{8C_{\ref{thm:tap_consequence}}(\mathcal{A})}{\delta
n^{1/4}}$ $\displaystyle\leq\|\beta
A_{j}\|_{2}\sqrt{\|\mathrm{Cov}(\mu_{\beta,A,\bm{h}})\|_{\mathsf{op}}}+\beta\sqrt{2\log(16n/\delta)}+\beta^{2}+\frac{8C_{\ref{thm:tap_consequence}}(\mathcal{A})}{\delta
n^{1/4}}$
$\displaystyle\leq\beta\left(1+\sqrt{\frac{\log(8n/\delta)}{c_{\ref{fact:norm_concentration}}n}}\right)\cdot\sqrt{K_{\ref{thm:cov_bound_external}}(\mathcal{A},\delta/4,\eta)}+\beta\sqrt{2\log(16n/\delta)}+\beta^{2}+\frac{8C_{\ref{thm:tap_consequence}}(\mathcal{A})}{\delta
n^{1/4}}.$

The stated bound holds with probability at least $3/4$ over
$X\sim\mu_{\beta,A,\bm{h}}$ by applying a triangle inequality to deal with the
$h_{j}$ term on this good event and then Markov’s inequality over
$X\sim\mu_{\beta,A,\bm{h}}$ to deal with the inner product. ∎

After all of these intermediate results, we may now easily conclude Theorem
6.8 in the same way as Theorem 6.6. The only difference is slightly more
bookkeeping for recovery of the external field.

###### Proof of Theorem 6.8.

Corollary 6.13 shows that under the assumptions of the theorem, with
probability at least $1-\delta$ over
$A\sim\mathsf{GOE},\bm{h}\sim\mathcal{N}(\mu\cdot\bm{1},\sigma^{2}\cdot I)$:

  1. 1.

It holds that

$\max_{i\in[n]}\|\beta
A_{i}\|_{1}+|h_{i}|\leq\beta\left(\sqrt{n}+\sqrt{\frac{\log(8n/\delta)}{c_{\ref{fact:norm_concentration}}}}\right)+\mu+\sqrt{2\sigma^{2}\ln(8n/\delta)}\triangleq
C_{1}(\mathcal{A},n,\delta).$

  2. 2.

For $X\sim\mu_{\beta,A,\bm{h}}$ and any $j\in[n]$, it holds with probability
at least $3/4$ over $X$ that:

$\displaystyle\left|\beta\langle X,A_{j}\rangle+h_{j}\right|$
$\displaystyle\leq
4\beta\left(1+\sqrt{\frac{\log(8n/\delta)}{c_{\ref{fact:norm_concentration}}n}}\right)\cdot\sqrt{K_{\ref{thm:cov_bound_external}}(\mathcal{A},\delta/4,\eta)}$
$\displaystyle+4\beta\sqrt{2\log\left(\frac{16n}{\delta}\right)}+\frac{32C_{\ref{thm:tap_consequence}}(\mathcal{A})}{\delta
n^{1/4}}+\beta^{2}+\mu+\sqrt{2\sigma^{2}\ln\left(\frac{8n}{\delta}\right)}\triangleq
C_{2}(\mathcal{A},n,\delta,\eta).$

We may therefore apply Theorem 6.1 with
$C_{\ref{thm:ising_cov}}=C_{2}=O_{\mathcal{A},\delta,\eta}(\sqrt{\log n})$,
which shows that on this event, for any $j\in[n]$ and letting
$\bm{w}^{*}=A_{j}$ and $h^{*}=h_{i}$, we have the lower bounds for any
$(\bm{w},h)$

$\mathbb{E}_{X}\left[\left(\sigma\left(2(\langle\bm{w},X\rangle+h)\right)-\sigma\left(2(\langle\bm{w}^{*},X\rangle+h^{*})\right)\right)^{2}\right]\geq\exp(-O(C_{\ref{thm:ising_cov}}))\cdot\min\\{1,8(w_{j}-w^{*}_{j})^{2}\\}.$

and for any $(\bm{w},h)\in\mathbb{R}^{n-1}\times\mathbb{R}$ such that
$\|\bm{w}-\bm{w}^{*}\|_{\infty}\leq|h-h^{*}|/2n$

$\mathbb{E}_{X}\left[\left(\sigma\left(2(\langle\bm{w},X\rangle+h)\right)-\sigma\left(2(\langle\bm{w}^{*},X\rangle+h^{*})\right)\right)^{2}\right]\geq\exp(-O(C_{\ref{thm:ising_cov}}))\cdot\min\\{1,(h-h^{*})^{2}\\}.$

Let
$\mathcal{C}=\\{(\bm{w},h)\in\mathbb{R}^{n-1}\times\mathbb{R}\mathrel{\mathop{\mathchar
58\relax}}\|(\bm{w},h)\|_{1}\leq C_{1}\\}$ so that each $(\beta
A_{j},h_{j})\in\mathcal{C}$. Let $Z_{1},\ldots,Z_{T}\in\\{-1,1\\}^{n}$ denote
the independent samples from $\mu_{\beta,A,\bm{h}}$. For a fixed node
$i\in[n]$, as usual, write $X_{t}=Z_{t,-i}$ and $Y_{t}=Z_{t,i}$. Standard
uniform convergence bounds (again, see Theorem 26.12 of [SSBD14]) again imply
that for node $i$’s logistic regression problem, with probability at least
$1-\delta^{\prime}$, we have the one-sided deviation bounds

$\sup_{(\bm{w},h)\in\mathcal{C}}\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\ell(2Y_{t}\langle\bm{w},X_{t}\rangle)]-\frac{1}{T}\sum_{t=1}^{T}\ell(2Y_{t}\langle\bm{w},X_{t}\rangle)\leq
O\left(C_{1}\sqrt{\frac{\ln(n/\delta)}{T}}\right).$

Combined with the two-sided deviation bound Lemma 5.2 for
$(\bm{w}^{*},h^{*})$, we find $T(\varepsilon,\delta^{\prime})\leq
O(C_{1}^{2}\ln(n/\delta^{\prime})/\varepsilon^{2})$. We now may apply Theorem
4.1 to obtain an estimate $\widehat{A}$ satisfying $\|\widehat{A}-\beta
A\|_{\infty}\leq\varepsilon$ with probability at least $1-\delta^{\prime}$
given

$T\geq\frac{O(C_{1}^{2})\exp(O(C_{2}))\log(n/\delta^{\prime})}{\varepsilon^{4}}.$

Setting $\varepsilon=\alpha^{2}/8n^{2}$, the last conclusion of Theorem 4.1
further implies that on the event $\|\widehat{A}-\beta
A\|_{\infty}\leq\varepsilon$, we must also have

$\|\widehat{\bm{h}}-\bm{h}\|_{\infty}\leq 2n\varepsilon=\alpha^{2}/4n.$

By Lemma 3.6, we thus find that

$\mathsf{d}_{TV}(\mu_{\widehat{A},\widehat{\bm{h}}},\mu_{\beta,A,\bm{h}})\leq\frac{\alpha}{2\sqrt{2}}+\frac{\alpha}{2}<\alpha,$

on this event, as claimed. This completes the proof, noting that
$C_{1}=O_{\mathcal{A},\delta}(\sqrt{n})$ and
$C_{2}=O_{\mathcal{A},\delta,\eta}(\sqrt{\log n})$. ∎

##  7 Extensions: Off-Equilibrium and Adversarial Dynamics

In this last section, we demonstrate how our above framework, though quite
elementary, can rather efforlessly lead to significant improvements in the
learning guarantees of other dynamic settings. In Section 7.1, we study the
setting of learning in the $M$-regime, as considered by Dutt, Lokhov, Vuffray,
and Misra [DLVM21]. In this model, the independent samples from the Ising
model one receives are one-step Glauber dynamics started from a uniformly
random configuration in $\\{-1,1\\}^{n}$. This setting is meant to capture the
learning problem of Glauber dynamics far from equilibrium. As was shown by
Dutt, et al., samples in the M-regime appear to be significantly more
informative about the underlying Ising parameters, both in theory and in
practice.

Their main theoretical result is that there exists an algorithm, D-RISE, such
that for Ising models with maximum degree $d$ and maximum edge strength
$\beta$ (with some minimum edge strength $\alpha>0$), the sample complexity of
learning the support scales in the width at most like $\exp(2\beta d)$ per
node [DLVM21]. This provable guarantee is stronger than any known algorithm in
the exponent than any known algorithm in the i.i.d. case from the stationary
measure, and is closer to the information-theoretic scaling lower bound in
this setting of $\exp(\beta d)$ established by Santhanam and Wainwright
[SW12]. Experimentally, Dutt, et al. also show that the scaling of these
algorithms are even better than these theoretical bounds.

Using our simple framework, we show that the gains of learning in the M-regime
are significantly more pronounced. Conceptually, the reason is transparent
within our analysis: with a uniformly random configuration before each Glauber
step, the magnitude of the effective field of the updated site will typically
be of order the $\ell_{2}$ norm of the row of interactions, rather than the
$\ell_{1}$ norm. As in the previous sections, the existence of this typical
event is sufficient to conclude that the population loss in logistic
regression measures the variation from the true interaction vector component-
wise by paying a bound that is exponential in $\beta\sqrt{d}$ rather than
$\beta d$. In particular, this result shows that structure recovery in the
M-regime is _strictly easier_ than learning from i.i.d. samples from the
stationary measure.

In Section 7.2, we will consider a simple model of _adversarial Glauber
dynamics_ , which was recently introduced by Chin, Moitra, Mossel, and Sandon
[CMMS23].161616The exact adversary model considered by Chin, et al., is
strictly stronger than the one we consider here. In their work, adversarial
nodes are allowed to apply an arbitrary update rule, coordinate amongst
themselves, and even update at any time, not just when selected for updating.
In this model, some fraction of nodes are corrupted and may update according
to an arbitrary decision rule at each time they are selected for updating.
Using our framework for sequential block dynamics, it will be straightforward
to show that on bounded degree graphs, if adversarial nodes are _smooth and
local_ , then running logistic regression will nonetheless succeed in
recovering the interaction coefficients for non-corrupted nodes. In
particular, if the identities of corrupted nodes are known, then one can
recover the interactions between non-corrupted nodes. We will make these
notions more precise, but they roughly correspond to somewhat mild constraints
on how adversarial nodes may update. A more refined notion of learning
guarantees under fully adversarial behavior remains an interesting open
question we leave for future work.

Throughout the remainder of this section, we focus on the case with no
external field for simplicity.

###  7.1 Learning in the M-Regime

We now proceed to formally the sample generation process in the so-called
M-regime. In words, the samples in the M-regime are obtained by doing a single
step of Glauber dynamics from a uniformly random initial configuration. The
formal definition is as follows:

######  Definition 7 (M-Regime [DLVM21]).

Let $A\in\mathbb{R}^{n\times n}$ be the interaction matrix of an Ising model.
Samples
$(X_{1},X_{1}^{\prime},i_{1}),\ldots,(X_{T},X_{T}^{\prime},i_{T})\in\\{-1,1\\}^{n}\times\\{-1,1\\}^{n}\times[n]$
from the M-regime from $\mu_{A}$ are obtained as follows. For each $t\geq 1$,

  1. 1.

Sample $X_{t}\sim\\{-1,1\\}^{n}$ uniformly and independently.

  2. 2.

Sample $i_{t}\sim[n]$ uniformly at random, and update the $i_{t}$th coordinate
of $X_{t}$ via 3. Let $X_{t}^{\prime}$ denote the new configuration.

For a node $j\in[n]$, let $I_{j}\subseteq[T]$ denote the set of times $t$
where $i_{t}=j$. Then the samples generated for $j$ are the samples
$(X_{\ell,-j},X^{\prime}_{\ell,j})$ for $\ell\in I_{j}$.171717Note that for
each $\ell\in I_{j}$, the law of $X^{\prime}_{\ell,j}$ conditional on all
other samples is indeed given by 3 conditional on $X_{\ell,-j}$.

We are now ready to state and prove the main result of this subsection:

######  Theorem 7.1.

Let $\mathcal{C}$ be a closed convex set and let $A$ be an Ising model such
that $A_{j}\in\mathcal{C}$ for each $j\in[n]$. Let
$R_{1}\triangleq\max_{\bm{z}\in\mathcal{C}}\|z\|_{1}$ and
$R_{2}\triangleq\max_{j\in[n]}\|A_{j}\|_{2}$. Then given at least

$\frac{O\left(R_{1}^{2}\exp(O(R_{2}))\cdot\log(n/\delta)\right)}{\varepsilon^{4}}$

updates per node from M-regime samples, it holds with probability at least
$1-\delta$ that running logistic regression as in 4 with constraint set
$\mathcal{C}$ for each $j\in[n]$ returns a matrix $\widehat{A}$ such that
$\|A-\widehat{A}\|_{\infty}\leq\varepsilon$.

###### Proof.

Note that by assumption, each $A_{j}$ is feasible for the corresponding
logistic regression problem for node $j$. The result is now essentially
immediate from Corollary 6.3, with simple modifications. For each $j\in[n]$,
and any $\ell\in I_{j}$, the covariance matrix of $X_{\ell,-j}$ is the
identity matrix by the assumption $X_{\ell}$ is uniform on $\\{-1,1\\}^{n}$
and the fact that the updated index is independent of the configuration.
Therefore, the same argument as Corollary 6.3 applies but with the smaller
constraint set $\mathcal{C}$. This argument thus gives the sample complexity
bound for each node of

$\frac{O\left(R_{1}^{2}\exp(O(R_{2}))\cdot\log(n/\delta)\right)}{\varepsilon^{4}}$

to obtain an $\varepsilon$ additive approximation with probability at least
$1-\delta$ for each node. ∎

While quite simple, Theorem 7.1 already implies that with bounded degree
interaction matrices $A$, the sample complexity of recovering the support of
$A$ from samples in the M-regime scales like $\exp(O(\beta\sqrt{d}))$, an
exponential improvement (per node) over what is information-theoretically
possible given samples from the stationary distribution:

######  Corollary 7.2.

Let $A\in\mathbb{R}^{n\times n}$ be an interaction matrix with maximum degree
at most $d$, maximum absolute coefficient at most $\beta>0$, and minimum
nonzero coefficient at least $\alpha>0$. Then, given at least

$\frac{O((\beta d)^{2}\exp(O(\beta\sqrt{d})))\log(n/\delta)}{\varepsilon^{4}}$

M-regime samples per node, running logistic regression for each node with
$\mathcal{C}=\\{\bm{w}\in\mathbb{R}^{n-1}\mathrel{\mathop{\mathchar
58\relax}}\|\bm{w}\|_{1}\leq\beta d\\}$ as in 4 yields $\widehat{A}$ such that
$\|\widehat{A}-A\|_{\infty}\leq\varepsilon$ with probability at least
$1-\delta$.

In particular, if $\varepsilon<\alpha/2$, then

$\text{supp}(A)=\\{(i,j)\in[n]^{2}\mathrel{\mathop{\mathchar
58\relax}}|\widehat{A}_{i,j}|\geq\alpha/2\\}.$

Thus, given at least $O((\beta
d)^{2})\exp(O(\beta\sqrt{d}))\log(n/\delta)/\alpha^{4}$ updates for each node,
with probability at least $1-\delta$, one may recover the support of $A$.

###### Proof.

It is well-known that the second claim is a consequence of the first; it is
clear that if the minimum nonzero edge strength is at least $\alpha>0$, then
if $\|A-\widehat{A}\|_{\infty}<\alpha/2$, the absolute value of $\widehat{A}$
for each edge must be at least $\alpha/2$ while the value for each nonedge
must be strictly smaller. Thresholding thus recovers the true support of $A$.

Observe that each row is indeed feasible for the logistic regression problem
by the assumption on the degree and maximum absolute coefficient condition.
Moreover, under our assumptions, each row of $A$ has $\ell_{2}$ norm at most
$\beta\sqrt{d}$ since

$\|A_{j}\|_{2}\leq\sqrt{\|A_{j}\|_{1}\|A_{j}\|_{\infty}}\leq\sqrt{\beta^{2}d}=\beta\sqrt{d}.$

to obtain an $\varepsilon$ additive approximation with probability at least
$1-\delta$ for each node. Applying Theorem 7.1 gives the conclusion. ∎

Returning to the setting of the Sherrington-Kirkpatrick model, we also easily
obtain that in the M-regime, there is effectively no “low-temperature” regime
for learning:

######  Corollary 7.3.

Let $\overline{\beta}\geq 0$ be fixed and let
$\mathcal{C}=\\{\bm{w}\in\mathbb{R}^{n-1}\mathrel{\mathop{\mathchar
58\relax}}\|\bm{w}\|_{1}\leq 2\overline{\beta}\sqrt{n}$. Then with probability
$1-o(1)$ over $A\sim\mathsf{GOE}(n)$, the following holds: for any
$\beta\leq\overline{\beta}$, it holds with probability at least $1-\delta$
that, given at least

$\frac{O\left(\overline{\beta}^{2}\cdot
n\cdot\exp(O(\overline{\beta})))\cdot\log(n/\delta)\right)}{\varepsilon^{4}}$

M-regime samples per node of the SK model $\mu_{\beta,A}$, running logistic
regression 4 for each node with constraint set $\mathcal{C}$ returns
$\widehat{A}$ such that $\|\widehat{A}-\beta A\|_{\infty}\leq\varepsilon$.

###### Proof.

By 3.2 and a union bound, we see that with probability at least $1-o(1)$ that
$\|\beta A_{j}\|_{2}\leq 2\beta$ and then by Cauchy-Schwarz, $\|\beta
A_{j}\|_{1}\leq 2\beta\sqrt{n}$. As such, each row of $\beta A$ is feasible
for the stated logistic regression problem, and applying Theorem 7.1 gives the
stated conclusion. ∎

To reiterate, the key observation is that since the M-regime returns well-
behaved samples regardless of the structural features of the Ising model, the
learning problem becomes _much_ easier statistically. While the actual Ising
model may exhibit challenging correlations at the level of Gibbs measure, the
samples used for learning do not reflect them, and thus the learning
guarantees need not either.

###  7.2 Adversarial Glauber Dynamics

We now turn to the learnability of adversarial Glauber dynamics.

######  Definition 8.

Let $A\in\mathbb{R}^{n\times n}$ be the interaction matrix for an Ising model
$\mu_{A}$. Let $C\subseteq[n]$ denote a subset of corrupted nodes and let
$H=[n]\setminus C$ denote the honest nodes. Then given an initial
configuration $X_{0}\in\\{-1,1\\}^{n}$, $\gamma$-smooth and local adversarial
Glauber dynamics proceeds as follows. For each $t\geq 1$:

  1. 1.

Sample $i_{t}\sim[n]$ uniformly at random.

  2. 2.

If $i_{t}\in H$, then $X_{t}$ is obtained from $X_{t-1}$ by updating the
$i_{t}$th coordinate of $X_{t-1}$ via the conditional measure in 3 given
$X_{t}$.

  3. 3.

If $i_{t}\in C$, then $X_{t}$ is obtained by $X_{t-1}$ by updating the
$i_{t}$th coordinate according to any distribution $\mathcal{D}_{i_{t},t}$ on
$\\{-1,1\\}$ that (i) depends only on
$X_{0,\mathcal{N}(i_{t})},\ldots,X_{t-1,\mathcal{N}(i_{t})}$, and (ii)
satisfies $\mathcal{D}_{i_{t},t}(\varepsilon)\geq\gamma$ for
$\varepsilon\in\\{-1,1\\}$.

In words, $\gamma$-smooth and local adversarial Glauber dynamics are such that
honest nodes update according to regular Glauber dynamics, while corrupt nodes
can update according to any randomized policy that depends only on the history
of spins _in their neighborhood_ (locality), and constrained to put at least
$\gamma$ mass on each possibility (smoothness).

Again, our main result of this subsection shows that $\gamma$-smooth and local
dynamics cannot meaningfully affect the learning guarantees of logistic
regression for the honest nodes:

######  Theorem 7.4.

Let $A\in\mathbb{R}^{n\times n}$ be the interaction matrix for an Ising model
$\mu_{A}$ with maximum degree at most $d$ and $\ell_{1}$ width $\lambda$.
Consider any $\gamma$-smooth and local adversarial Glauber dynamics and run
logistic regression as in 4 for each node. Then given at least

$\tilde{O}\left(\frac{\lambda^{2}\exp(O(\lambda))\log(n/\delta)}{\varepsilon^{4}\gamma^{O(d)}}\right)$

samples for each node, it holds with probability at least $1-\delta$ that the
logistic regression output $\widehat{w}_{j}$ for each _honest_ node $j\in H$
obtains a $\varepsilon>0$ additive approximation of $A_{j}$.

###### Sketch of Theorem 7.4.

The proof is very similar to that of Proposition 5.8 and considers likelihood
ratios. For convenience, suppose node $n$ is an honest node; our first goal is
to show that a similar conclusion to Proposition 5.8 holds. Formally, one can
show the following:

######  Claim 7.1.

Assume the conditions of Theorem 7.4 and suppose node $n$ is honest. Fix any
$X_{0}\in\\{-1,1\\}^{n}$ and history of $\gamma$-smooth and local adversarial
Glauber dynamics up to time $0$ (which we denote $\mathcal{F}_{0}$ after
reindexing). Let $Z=(X_{\tau_{1},-n},X_{\tau_{1},n})$ be the configuration at
the next update time of node $n$ (as in 5 after reindexing). For simplicity,
write $X=X_{\tau_{1},-i}\in\\{-1,1\\}^{n-1}$.

Then there exists a constant $c>0$ such that for all $j\neq n$, and any
$(\bm{w},h)\in\mathbb{R}^{n-1}\times\mathbb{R}$,

$\mathbb{E}_{X}\left[\left(\sigma\left(2(\langle\bm{w},X\rangle+h)\right)-\sigma\left(2(\langle\bm{w}^{*},X\rangle+h^{*})\right)\right)^{2}\bigg{|}\mathcal{F}_{0}\right]\geq
c\gamma^{O(d)}\exp(-O(\lambda))\min\\{1,8(w_{j}-w_{j}^{*})^{2}\\}.$

We merely sketch the proof as it is very similar to Proposition 5.8: consider
any $j\neq[n]$, honest or not. As in that proof, let $\mathcal{P}$ denote the
sequence of updates before the next update of $n$ and let
$\mathcal{P}^{\prime}$ denote the sequence of updates replacing the last
occurrence of $j$ with $*$ (if one exists).

As in Proposition 5.8, it then suffices to show that with constant probability
over $\mathcal{P}^{\prime}$, it holds that $j$ was indeed updated in
$\mathcal{P}$ and that the likelihood ratio of $X_{j}=\varepsilon$ conditional
on $\mathcal{P}^{\prime}$ is bounded above and below. The former holds with
probability at least $1/2$, so it suffices to control the likelihood ratio
with probability at least $3/4$ and take a union bound. By writing out and
factorizing the likelihood of $\mathcal{P}^{\pm}$ as in Proposition 5.8, we
note that the likelihood ratio of each node update after the last update of
$j$ given the true configuration with $X_{j}=\pm 1$ is controlled as follows:

  1. 1.

If node $k\in\mathcal{N}(j)^{c}$ is updated, the likelihood ratio is $1$ by
locality as the update rule does not depend on the value of $X_{j}$.

  2. 2.

If node $k\in C\cap\mathcal{N}(j)$ is updated, the likelihood ratio is at most
$1/\gamma$ by smoothness.

  3. 3.

If node $k\in H\cap\mathcal{N}(j)$, the likelihood ratio is bounded by
$\exp(O(|A_{i,j}|))$ by Lemma 5.6.

Let $N_{k}$ denote the number of times node $k$ is updated after the last
update of $j$. Then the likelihood ratio of $X_{j}$ given
$\mathcal{P}^{\prime}$ is bounded by

$\exp\left(O\left(\sum_{k\in\mathcal{N}(j)\cap
H}N_{k}|A_{ij}|\right)\right)\cdot\gamma^{-O(\sum_{k\in
C\cap\mathcal{N}(j)}N_{k})}.$

As in Proposition 5.8, by Markov’s inequality, we have with probability at
least $3/4$ over $\mathcal{P}^{\prime}$ that

$\displaystyle\sum_{k\in\mathcal{N}(j)\cap H}N_{k}|A_{ij}|\leq 8\lambda$
$\displaystyle\sum_{k\in\mathcal{N}(j)\cap C}N_{k}\leq 8d.$

Combining the previous two displays gives bound on the likelihood ratio, and
following the rest of the argument in Proposition 5.8 gives the stated
conclusion of the claim. At this point, we may apply the uniform martingale
bounds of Theorem 5.5 with the bound of 7.1 to the meta-theorem Theorem 4.1 to
obtain the result. ∎

##  8 Conclusions and Open Questions

In this work, we have shown that logistic regression can efficiently learn
Ising models under more general conditions than previously known. Our analysis
identifies refined structural conditions that more accurately reflect the
statistical and computational hardness of learning specific Ising models in a
variety of regimes. We conclude with a few interesting open directions:

######  Question 2.

What is the sample complexity of learning from dynamics where one only
observes updates when the configuration changes?

Note that in Theorem 5.1, as well as the prior work of Bresler, Gamarnik, and
Shah [BGS18] and Dutt, Lokhov, Vuffray, and Misra [DLVM21], we have assumed
that the indices of vertices that are chosen for updating at each time are
observed regardless of whether their value actually changes. In practice, it
is much more likely that one only observes the _changes_ in configurations and
possibly the clock of updating. One expects that an appropriately debiased
version of logistic regression may succeed but would likely need new ideas.

######  Question 3.

Can one remove the extraneous $\mathsf{poly}(\log\log n)$ term from Theorem
5.1?

Recall that this term arises from applying the contraction principle for
sequential Rademacher complexity, and it appears open whether this factor is
necessary in general. But for the more structured processes we consider here,
it may be possible to give a more direct argument avoiding these bounds or the
use of sequential Rademacher complexity altogether.

######  Question 4.

Can one extend the results of Section 6 to general mixed $p$-spin models in
the entire high-temperature regime?

We expect that our general results should extend to Markov random fields with
higher-order interactions without much effort. However, the specific case of
mixed $p$-spin models may exhibit an interesting regime where reducing
learning to appropriate moment bounds, rather than dynamical notions, may be
provably necessary. Anari, Jain, Koehler, Pham, and Vuong [AJK+23] have shown
that one can learn very high-temperature $p$-spin models since entropy
factorization holds, but this certainly cannot extend to the entire high-
temperature regime: unlike the SK model (which corresponds to $p=2$), general
mixed $p$-spin models exhibit _shattering_ in an interval of the high-
temperature (replica-symmetric) regime, which provably prevents fast mixing
and thus entropy factorization (see, e.g. [AJ23, AMS23, GJK23]). It is not
clear to us whether shattering precludes the weaker condition of boundedness
of appropriate moment matrices (with respect to an appropriate norm) with no
external field.

######  Question 5.

Can one obtain more refined guarantees for learning from dishonest dynamics,
possibly under extra assumptions?

Note that our result Theorem 7.4 only ensures that dishonest updates, under
some constraints, cannot affect the recovery of honest nodes given enough
samples. Beyond improving the sample complexity given there, it would be
interesting to understand whether these constraints can be relaxed. Under some
additional modelling conditions, it may also be possible to identify corrupt
nodes or otherwise minimize their influence. For instance, one may hope to
argue that if one cannot identify a corrupt node while learning from dynamics,
then the set of corrupt nodes must “hide” in a sense that enables improved
recovery guarantees. While it is possible to show that one cannot obtain such
a guarantee in the exact setting we have considered, perhaps imposing other
restrictions could allow for improved guarantees. See, for instance, Alon,
Mossel, and Pemantle [AMP20] and subsequent work for the related problem of
detecting corruption in graphs under somewhat different conditions.

## References

  * [ABXY22] Arka Adhikari, Christian Brennecke, Changji Xu, and Horng-Tzer Yau.  Spectral gap estimates for mixed $p$-spin models at high temperature.  arXiv preprint arXiv:2208.07844, 2022.
  * [AG22] Ahmed El Alaoui and Jason Gaitonde.  Bounds on the covariance matrix of the Sherrington-Kirkpatrick model.  arXiv preprint arXiv:2212.02445, 2022.
  * [AJ23] Gérard Ben Arous and Aukosh Jagannath.  Shattering versus metastability in spin glasses.  Communications on Pure and Applied Mathematics, pages 1–38, 2023.
  * [AJK+23] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong.  Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses.  CoRR, abs/2307.10466, 2023.
  * [AMP20] Noga Alon, Elchanan Mossel, and Robin Pemantle.  Distributed Corruption Detection in Networks.  Theory Comput., 16:1–23, 2020.
  * [AMS22] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke.  Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 323–334. IEEE, 2022.
  * [AMS23] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke.  Shattering in Pure Spherical Spin Glasses.  arXiv preprint arXiv:2307.04659, 2023.
  * [AV13] Animashree Anandkumar and Ragupathyraj Valluvan.  Learning loopy graphical models with latent variables: Efficient methods and guarantees.  The Annals of Statistics, pages 401–435, 2013.
  * [BB19] Roland Bauerschmidt and Thierry Bodineau.  A very simple proof of the LSI for high temperature spin systems.  Journal of Functional Analysis, 276(8):2582–2588, 2019.
  * [BBK21] Enric Boix-Adserà, Guy Bresler, and Frederic Koehler.  Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 417–426. IEEE, 2021.
  * [BDR21] Adam Block, Yuval Dagan, and Alexander Rakhlin.  Majorizing Measures, Sequential Complexities, and Online Learning.  In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 587–590. PMLR, 2021.
  * [BGS18] Guy Bresler, David Gamarnik, and Devavrat Shah.  Learning Graphical Models from the Glauber Dynamics.  IEEE Trans. Inf. Theory, 64(6):4072–4080, 2018.
  * [BK20] Guy Bresler and Mina Karzand.  Learning a tree-structured Ising model in order to make predictions.  The Annals of Statistics, 48(2):713 – 737, 2020.
  * [BKM19] Guy Bresler, Frederic Koehler, and Ankur Moitra.  Learning restricted Boltzmann machines via influence maximization.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 828–839. ACM, 2019.
  * [BMS13] Guy Bresler, Elchanan Mossel, and Allan Sly.  Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms.  SIAM J. Comput., 42(2):563–578, 2013.
  * [BMV08] Andrej Bogdanov, Elchanan Mossel, and Salil P. Vadhan.  The Complexity of Distinguishing Markov Random Fields.  In Ashish Goel, Klaus Jansen, José D. P. Rolim, and Ronitt Rubinfeld, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings, volume 5171 of Lecture Notes in Computer Science, pages 331–342. Springer, 2008.
  * [Bre15] Guy Bresler.  Efficiently Learning Ising Models on Arbitrary Graphs.  In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 771–782. ACM, 2015.
  * [BRO17] Ludovica Bachschmid-Romano and Manfred Opper.  A statistical physics approach to learning curves for the inverse Ising problem.  Journal of Statistical Mechanics: Theory and Experiment, 2017(6):063406, jun 2017.
  * [BSXY22] Christian Brennecke, Adrien Schertzer, Changji Xu, and Horng-Tzer Yau.  The Two Point Function of the SK model without External Field at High Temperature.  arXiv preprint arXiv:2212.14476, 2022.
  * [BXY23] Christian Brennecke, Changji Xu, and Horng-Tzer Yau.  Operator Norm Bounds on the Correlation Matrix of the SK Model at High Temperature.  arXiv preprint arXiv:2307.12535, 2023.
  * [Cel22] Michael Celentano.  Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy.  CoRR, abs/2208.09550, 2022.
  * [CL68] Chao-Kong Chow and Chao-Ning Liu.  Approximating discrete probability distributions with dependence trees.  IEEE Transactions on Information Theory, 14(3):462–467, 1968.
  * [CMMS23] Byron Chin, Ankur Moitra, Elchanan Mossel, and Colin Sandon.  The Power of an Adversary in Glauber Dynamics.  arXiv preprint arXiv:2302.10841, 2023.
  * [CMT15] Pietro Caputo, Georg Menz, and Prasad Tetali.  Approximate tensorization of entropy at high temperature.  In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 24, pages 691–716, 2015.
  * [DDDK21] Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis Kandiros.  Learning Ising models from one or multiple samples.  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 161–168. ACM, 2021.
  * [DDK18] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath.  Testing Ising Models.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1989–2007. SIAM, 2018.
  * [DKSS21] Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, and Yuxin Sun.  Outlier-Robust Learning of Ising Models Under Dobrushin’s Condition.  In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 1645–1682. PMLR, 2021.
  * [DLVM21] Arkopal Dutt, Andrey Y. Lokhov, Marc Vuffray, and Sidhant Misra.  Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Mamoitrae Learning Research, pages 2914–2925. PMLR, 2021.
  * [DMR20] Luc Devroye, Abbas Mehrabian, and Tommy Reddad.  The minimax learning rates of normal and Ising undirected graphical models.  Electronic Journal of Statistics, 14:2338–2361, 2020.
  * [DP21] Constantinos Daskalakis and Qinxuan Pan.  Sample-optimal and efficient learning of tree Ising models.  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 133–146. ACM, 2021.
  * [DS87] Roland L Dobrushin and Senya B Shlosman.  Completely analytical interactions: Constructive description.  Journal of Statistical Physics, 46:983–1014, 1987.
  * [EKZ22] Ronen Eldan, Frederic Koehler, and Ofer Zeitouni.  A Spectral Condition for Spectral Gap: Fast Mixing in High-Temperature Ising Models.  Probability Theory and Related Fields, 182(3-4):1035–1051, 2022.
  * [FMM21] Zhou Fan, Song Mei, and Andrea Montanari.  TAP free energy, spin glasses and variational inference.  The Annals of Probability, 49(1):1 – 45, 2021.
  * [FV17] Sacha Friedli and Yvan Velenik.  Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction.  Cambridge University Press, 2017.
  * [GJK23] David Gamarnik, Aukosh Jagannath, and Eren C Kızıldağ.  Shattering in the Ising Pure $p$-spin Model.  arXiv preprint arXiv:2307.07461, 2023.
  * [GKK19] Surbhi Goel, Daniel M. Kane, and Adam R. Klivans.  Learning Ising Models with Independent Failures.  In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 1449–1469. PMLR, 2019.
  * [GKK20] Surbhi Goel, Adam R. Klivans, and Frederic Koehler.  From Boltzmann Machines to Neural Networks and Back Again.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [Goe20] Surbhi Goel.  Learning Ising and Potts Models with Latent Variables.  In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 3557–3566. PMLR, 2020.
  * [HKM17] Linus Hamilton, Frederic Koehler, and Ankur Moitra.  Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications.  In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 2463–2472, 2017.
  * [KDDC23] Anthimos Vardis Kandiros, Constantinos Daskalakis, Yuval Dagan, and Davin Choo.  Learning and Testing Latent-Tree Ising Models Efficiently.  In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 1666–1729. PMLR, 2023.
  * [KHR23] Frederic Koehler, Alexander Heckett, and Andrej Risteski.  Statistical Efficiency of Score Matching: The View from Isoperimetry.  In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
  * [KM17] Adam R. Klivans and Raghu Meka.  Learning Graphical Models Using Multiplicative Weights.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 343–354. IEEE Computer Society, 2017.
  * [LP17] David A. Levin and Yuval Peres.  Markov Chains and Mixing Times, volume 107.  American Mathematical Soc., 2017.
  * [MM09] Marc Mézard and Thierry Mora.  Constraint satisfaction problems and neural networks: A statistical physics perspective.  Journal of Physiology-Paris, 103(1-2):107–113, 2009.
  * [MMS21] Ankur Moitra, Elchanan Mossel, and Colin Sandon.  Learning to Sample from Censored Markov Random Fields.  In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 3419–3451. PMLR, 2021.
  * [MS09] Andrea Montanari and Amin Saberi.  Convergence to Equilibrium in Local Interaction Games.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 303–312. IEEE Computer Society, 2009.
  * [Pan13] Dmitry Panchenko.  The Sherrington-Kirkpatrick Model.  Springer Science & Business Media, 2013.
  * [Par80] Giorgio Parisi.  A sequence of approximated solutions to the S-K model for spin glasses.  Journal of Physics A: Mathematical and General, 13(4):L115, apr 1980.
  * [PSBR20] Adarsh Prasad, Vishwak Srinivasan, Sivaraman Balakrishnan, and Pradeep Ravikumar.  On Learning Ising Models under Huber’s Contamination Model.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [RS17] Alexander Rakhlin and Karthik Sridharan.  On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities.  In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, volume 65 of Proceedings of Machine Learning Research, pages 1704–1722. PMLR, 2017.
  * [RST15] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning via sequential complexities.  J. Mach. Learn. Res., 16:155–186, 2015.
  * [RWL10] Pradeep Ravikumar, Martin J Wainwright, and John D Lafferty.  High-Dimensional Ising Model Selection Using $\ell_{1}$-Regularized Logistic Regression.  The Annals of Statistics, pages 1287–1319, 2010.
  * [SK75] David Sherrington and Scott Kirkpatrick.  Solvable model of a spin-glass.  Phys. Rev. Lett., 35:1792–1796, Dec 1975.
  * [SS12] Allan Sly and Nike Sun.  The Computational Hardness of Counting in Two-Spin Models on $d$-Regular Graphs.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 361–369. IEEE Computer Society, 2012.
  * [SSBD14] Shai Shalev-Shwartz and Shai Ben-David.  Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014.
  * [SW12] Narayana P. Santhanam and Martin J. Wainwright.  Information-theoretic limits of selecting binary graphical models in high dimensions.  IEEE Trans. Inf. Theory, 58(7):4117–4134, 2012.
  * [Tal10] Michel Talagrand.  Mean Field Models for Spin Glasses: Volume I: Basic Examples, volume 54.  Springer Science & Business Media, 2010.
  * [Tal11] Michel Talagrand.  Mean Field Models for Spin Glasses: Volume II: Advanced Replica-Symmetry and Low Temperature.  Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge / A Series of Modern Surveys in Mathematics. Springer Berlin Heidelberg, 2011.
  * [Ver18] Roman Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science.  Number 47 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
  * [VML20] Marc Vuffray, Sidhant Misra, and Andrey Y. Lokhov.  Efficient Learning of Discrete Graphical Models.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [VMLC16] Marc Vuffray, Sidhant Misra, Andrey Y. Lokhov, and Michael Chertkov.  Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models.  In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2595–2603, 2016.
  * [Wai19] Martin J. Wainwright.  High-Dimensional Statistics: A Non-Asymptotic Viewpoint.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
  * [WSD19] Shanshan Wu, Sujay Sanghavi, and Alexandros G. Dimakis.  Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 8069–8079, 2019.
  * [ZKKW20] Huanyu Zhang, Gautam Kamath, Janardhan Kulkarni, and Zhiwei Steven Wu.  Privately Learning Markov Random Fields.  In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 11129–11140. PMLR, 2020.

##  Appendix A Deferred Proofs

We now provide the deferred proofs of Theorem 6.9 and Theorem 6.10 for the
interested reader. As mentioned, the former is essentially the main result of
[BXY23], while the second can be obtained from the proof of the TAP equations
of Talagrand [Tal10]. To begin, we require the following simple fact that
holds under the AT line showing that the $q$ parameter in 17 remains well-
behaved at high-temperature.

######  Lemma A.1.

Let $\mathcal{A}$ satisfy 1 and suppose
$(\beta,\mu,\sigma^{2})\in\mathcal{A}$. Then it holds that

$\frac{\partial}{\partial\beta}q(\beta,\mu,\sigma^{2})\leq
C_{\ref{lem:q_derivative}}(\mathcal{A})$

for some finite constant $C_{\ref{lem:q_derivative}}(\mathcal{A})>0$ that
holds uniformly on $\mathcal{A}$.

###### Proof.

We follow the argument of Lemma 1.7.5 of Talagrand [Tal10], which is stated
for $\beta\leq 1/2$ but holds under 1. Let $f(x)=\tanh^{2}(x)$. Fixing
$\mu,\sigma^{2}$, define $F(\beta,q)=\mathbb{E}_{h,z}[f(\beta z\sqrt{q}+h)]$
so that $q$ satisfies $q(\beta)=F(\beta,q(\beta))$. Letting
$f(x)=\tanh^{2}(x)$, implicit differentiation implies

$\displaystyle q^{\prime}(\beta)=\frac{\frac{\partial
F}{\partial\beta}(\beta,q(\beta))}{1-\frac{\partial F}{\partial
q}(\beta,q(\beta))}$ $\displaystyle=\frac{\mathbb{E}[z\sqrt{q}f^{\prime}(\beta
z\sqrt{q}+h]}{1-\frac{\beta\mathbb{E}[zf^{\prime}(\beta
z\sqrt{q}+h)]}{2\sqrt{q}}}$ $\displaystyle=\frac{\beta
q\mathbb{E}[f^{\prime\prime}(\beta
z\sqrt{q}+h)]}{1-\beta^{2}\mathbb{E}[f^{\prime\prime}(\beta z\sqrt{q}+h)]/2},$

where $f^{\prime\prime}(x)=\frac{2-4\sinh^{2}(x)}{\cosh^{4}(x)}$ and the last
line follows from applying Gaussian integration by parts on $z$. Since
$|f^{\prime\prime}(x)|\leq 2$ and we assume $\beta$ is bounded on
$\mathcal{A}$ (and $q\in[0,1]$), it suffices to show that the denominator is
bounded below by a constant depending on $\mathcal{A}$. But this is clear
since

$\frac{\beta^{2}}{2}\mathbb{E}\left[\frac{2-4\sinh^{2}(\beta
z\sqrt{q}+h)}{\cosh^{4}(\beta
z\sqrt{q}+h)}\right]\leq\beta^{2}\mathbb{E}\left[\frac{1}{\cosh^{4}(\beta
z\sqrt{q}+h)}\right]\leq 1-\delta(\mathcal{A})$

for some constant $\delta(\mathcal{A})>0$ where the last step is given by 20
and continuity recalling $\mathcal{A}$ is compact. ∎

The main consequence we require is the following:

######  Lemma A.2 (see e.g. Talagrand, Lemma 1.7.5 of [Tal10]).

Let $\mathcal{A}$ satisfy 1 and suppose
$(\beta,\mu,\sigma^{2})\in\mathcal{A}$. Let $\beta_{-}=\beta\sqrt{1-1/n}$.
Then

$|q(\beta_{-},\mu,\sigma^{2})-q(\beta,\mu,\sigma^{2})|\leq\frac{\beta
C_{\ref{lem:q_derivative}}(\mathcal{A})}{n}.$

###### Proof.

We have

$\displaystyle|q(\beta_{-},\mu,\sigma^{2})-q(\beta,\mu,\sigma^{2})|$
$\displaystyle=\left|\int_{\beta_{-}}^{\beta}q^{\prime}(x)\mathrm{d}x\right|$
$\displaystyle\leq|\beta-\beta_{-}|C_{\ref{lem:q_derivative}}$
$\displaystyle=\beta(1-\sqrt{1-1/n})C_{\ref{lem:q_derivative}}$
$\displaystyle\leq\frac{\beta C_{\ref{lem:q_derivative}}}{n},$

where we use the fact that $\sqrt{1-x}\geq 1-x$ for $x\in[0,1]$. ∎

To state the next intermediate results, we require the following notation.

######  Definition 9.

Given the Sherrington-Kirkpatrick measure $\mu_{\beta,A,\bm{h}}$ as in 18, let
$\sigma^{1},\sigma^{2},\dots\in\\{-1,1\\}^{n}$ denote independent samples from
$\mu_{\beta,A,\bm{h}}$. Let

$R_{1,2}\triangleq\frac{1}{n}\sum_{i=1}^{n}\sigma^{1}_{i}\sigma^{2}_{i}$

denote the overlap of $\sigma^{1},\sigma^{2}$.

Finally, let $\nu=\nu_{n,\beta,\mu,\sigma^{2}}$ denote the measure on
$(\\{-1,1\\}^{n})^{\otimes\mathbb{N}}$ defined by

$\nu\triangleq\mathbb{E}_{A\sim\mathsf{GOE}(n),\bm{h}\sim\mathcal{N}(\mu\cdot\bm{1},\sigma^{2}I)}[\mu^{\otimes
N}_{A,\beta,\bm{h}}(\cdot)],$

where $\mu^{\otimes\mathbb{N}}$ denotes the product measure on countably many
independent samples from $\mu$.

Next, we require the following result of Talagrand as stated by Brennecke, Xu,
and Yau [BXY23]:

######  Theorem A.3 (Theorem 13.7.1 of [Tal10], see also Theorem 2.1 of
[BXY23]).

Suppose $\mathcal{A}$ satisfies 1. Then there exists a constant
$K=K(\mathcal{A})$ such that for any $(\beta,\mu,\sigma^{2})\in\mathcal{A}$,
it holds that

$\nu\left(\exp\left(\frac{n(R_{1,2}-q(\beta,\mu,\sigma^{2}))^{2}}{K}\right)\right)\leq
2.$

Equivalently, the random variable $\sqrt{n}(R_{1,2}-q(\beta,\mu,\sigma^{2}))$
is subgaussian on $\mathcal{A}$ with uniformly bounded subgaussian norm.

###### Proof.

From Talagrand (Theorem 13.7.1 of [Tal10]) and Theorem 2.1 of [BXY23], it is
shown that for any $(\beta,\mu,\sigma^{2})$ satisfying 19 and 20, the random
variable $\sqrt{n}(R_{1,2}-q)$ is subgaussian under $\nu$ with locally bounded
subgaussian norm. That is, for each such
$(\beta,\mu,\sigma^{2})\in\mathcal{A}$, there exists constants
$K=K(\beta,\mu,\sigma^{2})$ and $\delta=\delta(\beta,\mu,\sigma^{2})>0$ such
that for any $(\beta^{\prime},\mu^{\prime},\sigma^{\prime 2})$ satisfying 19
and 20 such that $\|(\beta^{\prime},\mu^{\prime},\sigma^{\prime
2})-(\beta,\mu,\sigma^{2})\|_{\infty}\leq\delta$, for
$\nu_{n,\beta^{\prime},\mu^{\prime},\sigma^{\prime 2}}$ it holds that

$\nu\left(\exp\left(\frac{n(R_{1,2}-q(\beta^{\prime},\mu^{\prime},\sigma^{\prime
2}))^{2}}{K}\right)\right)\leq 2.$

A standard compactness argument then implies the uniform bound for any
$\mathcal{A}$ satisfying 1: for each $(\beta,\mu,\sigma^{2})\in\mathcal{A}$,
form the associated nontrivial open set with corresponding subgaussian
constant. This collection of open sets covers $\mathcal{A}$, and since
$\mathcal{A}$ is compact, there is a finite subcover. Simply taking the
largest parameter $K=K(\mathcal{A})<\infty$ over this subcover completes the
proof. ∎

With these preliminaries, we can return to the proof of Theorem 6.9.

######  Theorem A.4 (Theorem 6.9, restated).

Let $\mathcal{A}$ satisfy the conditions of 1 and let
$(\beta,\mu,\sigma^{2})\in\mathcal{A}$. Suppose that either:

  1. 1.

(Small Inverse Temperature) It holds that $\overline{\beta}<1/2-\eta$ for some
$\eta>0$.

  2. 2.

(Deterministic Field) It holds that $\overline{\sigma}=0$ (that is, the
external field is deterministic and parallel to $\mathbf{1}$).

Then for any $\delta>0$, there exists
$K_{\ref{thm:cov_bound_external}}(\mathcal{A},\delta,\varepsilon)$ independent
of $n$ such that with probability at least $1-\delta$ over
$A\sim\mathsf{GOE}(n)$,

$\|\mathrm{Cov}(\mu_{\beta,A,\bm{h}})\|_{\mathsf{op}}\leq
K_{\ref{thm:cov_bound_external}}(\mathcal{A},\delta,\varepsilon).$

###### Proof.

The main result of Brennecke, Xu, and Yau (Theorem 1.4 of [BXY23]) shows for
any $\delta>0$ and $(\beta,\mu,\sigma^{2})\in\mathcal{A}$, and for large
enough $n\geq n(\mathcal{A},\delta)$, there exists a constant
$K_{1}(\mathcal{A},\delta)>0$ such that with probability at least $1-\delta$,
it holds that

$\|\text{Cov}(\mu_{\beta,A,\bm{h}})\|_{\mathsf{op}}\leq
2\cdot(\|L^{-1}\|_{\mathsf{op}}+K_{1}(\mathcal{A},\delta)),$

where $L$ is the matrix defined by

$L\triangleq\text{diag}((\bm{1}-\bm{m}^{2}_{\beta,A,\bm{h}})^{-1})+\beta^{2}(1-q)I-\beta
A,$

where we interpret $\bm{y}^{p}$ to be the entrywise $p$th powers of a vector.
In comparison the the stated result in [BXY23], the fact that this bound holds
uniformly over fixed $(\beta,\mu,\sigma^{2})\in\mathcal{A}$ is because the
estimate in Theorem A.3 holds uniformly over $\mathcal{A}$ under 1, and the
constants above depend just on these parameters.

In the case of deterministic field, it is further shown in Proposition 1.4 of
[BXY23] that for any $\delta>0$, it holds for all $n\geq n(\delta)$ with
probability at least $1-\delta$ that $\|L^{-1}\|_{\mathsf{op}}\leq
K_{2}(\mathcal{A},\delta)$. By replacing $\delta$ with $\delta/2$ and taking a
union bound, we deduce the desired conclusion for all large enough $n\geq
n(\delta)$. For smaller $n$, we may take the trivial upper bound of $n$.

In the case where $\beta\leq 1/2-\eta$ for some $\eta>0$ with arbitrary
Gaussian field, a more direct argument suffices since for any
$\eta^{\prime}>0$, $\|A\|_{\mathsf{op}}\geq 2+\eta^{\prime}$ with
exponentially small probability in $n$ by standard bounds on the operator norm
of GOE matrices (see Lemma 4.12 of El Alaoui, Montanari, and Sellke [AMS22]
for details). It follows on the complementary event181818Here, we use the
standard notation for Loewner order: $A\preceq B\iff B-A$ is positive semi-
definite. that

$L\succeq I-\beta A\succeq
I-(1/2-\eta)(2+\eta^{\prime})I\succeq\frac{\eta}{2}I$

if we choose $\eta=\eta^{\prime}$, for instance. For large enough $n\geq
n(\delta,\eta)$, this event occurs with probability at least $1-\delta$, and
replacing $\delta$ with $\delta/2$ and taking a union bound yields the desired
conclusion in this case. Again, for all $n\leq n(\delta,\eta)$, one may simply
take the trivial upper bound of $n$. ∎

We now turn to the proof of Theorem 6.10. To prove it, we require the
following notation: for an index $i\in[n]$, we consider the Sherrington-
Kirkpatrick measures $\mu^{(i)}_{\beta,A,\bm{h}}$ where we remove the $i$th
spin. That is, for $\bm{x}\in\\{-1,1\\}^{[n]\setminus\\{i\\}}$

$\mu^{(j)}_{\beta,A,\bm{h}}(\bm{x})\propto\exp\left(\beta\bm{x}^{T}A_{[n]\setminus\\{i\\},[n]\setminus\\{i\\}}\bm{x}+\sum_{j\neq
i}h_{j}x_{j}\right).$

We note that for each $j\in[n]$, the measure $\mu_{\beta,A,\bm{h}}^{(j)}$ has
the law of the Sherrington-Kirkpatrick measure on $n-1$ sites with inverse
temperature $\beta_{-}=\beta\sqrt{1-1/n}$ and
$A^{\prime}\sim\mathsf{GOE}(n-1)$ due to the normalization. Of course, these
subsystems are highly correlated across $j\in[n]$ since they share the bulk of
the original $\mathsf{GOE}(n)$ matrix. With this notation, we write
$\bm{m}^{(j)}\in\mathbb{R}^{[n]\setminus\\{j\\}}$ to denote the mean vector of
the measure $\mu^{(j)}_{\beta,A,\bm{h}}$, i.e. for $i\neq j$,

$\bm{m}^{(j)}_{i}=\mathbb{E}_{\bm{x}\sim\mu^{(j)}_{\beta,A,\bm{h}}}[x_{i}].$

We are now ready to give the proof of Theorem 6.10, which we restate for
convenience:

######  Theorem A.5 (Theorem 6.10, restated).

Let
$\mathcal{A}=\mathcal{A}(\overline{\beta},\underline{h},\overline{h},\underline{\sigma}^{2},\overline{\sigma}^{2})$
satisfy the conditions of 1 with
$\max\\{\underline{h},\underline{\sigma^{2}}\\}>0$. There is a constant
$C_{\ref{thm:tap_consequence}}(\mathcal{A})>0$ such that for any
$(\beta,\mu,\sigma^{2})\in\mathcal{A}$, there exists standard Gaussian random
variables $z_{1},\ldots,z_{n}$ such that

$\mathbb{E}_{A,\bm{h},\bm{z}}\left[\max_{i\in[n]}\left|\beta\sum_{j\neq
i}A_{ij}\bm{m}_{j}-\beta^{2}(1-q)\bm{m}_{i}-\beta
z_{i}\sqrt{q}\right|\right]\leq\frac{C_{\ref{thm:tap_consequence}}(\mathcal{A})}{n^{1/4}}.$

###### Proof.

We rely on several facts established by Talagrand. First, Talagrand (proof of
Lemma 1.7.6, [Tal10]) shows that there exists a standard Gaussian $z=z_{n}$
defined on the same probability space as $A,\bm{h}$ such that

$\mathbb{E}_{A,\bm{h},z}\left[\left(z\sqrt{q}-\sum_{i<n}A_{i,n}\bm{m}^{(n)}_{i}\right)^{4}\right]\leq\frac{3}{q^{2}}\mathbb{E}_{A,\bm{h},z}\left[\mathbb{E}_{\sigma^{1},\sigma^{2}\sim\mu^{(n)}_{\beta,A,\bm{h}}}\left[\left(R^{-}_{1,2}-q\right)^{4}\right]\right].$

Here, we write $R_{1,2}^{-}$ to denote
$\frac{1}{n-1}\sum_{i=1}^{n-1}\sigma^{1}_{i}\sigma^{2}_{i}$ since these
samples are from the cavity measure on the first $n-1$ spins. We now replace
$q$ with $q_{-}=q(\beta_{-},\mu,\sigma^{2})$:

$\mathbb{E}_{A,\bm{h},z}\left[\mathbb{E}_{\sigma^{1},\sigma^{2}\sim\mu^{(n)}_{\beta,A,\bm{h}}}\left[\left(R^{-}_{1,2}-q\right)^{4}\right]\right]\leq
8\mathbb{E}_{A,\bm{h},z}\left[\mathbb{E}_{\sigma^{1},\sigma^{2}\sim\mu^{(n)}_{\beta,A,\bm{h}}}\left[\left(R^{-}_{1,2}-q_{-}\right)^{4}\right]\right]+8(q-q_{-})^{4},$

where we use the simple inequality $(x+y)^{4}\leq 8x^{4}+8y^{4}$. But since
$\mu_{\beta,A,\bm{h}}^{(n)}$ has the same law as
$\mu_{\beta_{-},A^{\prime},\bm{h}}$ where $A^{\prime}\sim\mathsf{GOE}(n-1)$ as
described above, we may apply Theorem A.3 to see that there a constant
$K_{1}(\mathcal{A})$ such that

$\mathbb{E}_{A,\bm{h},z}\left[\mathbb{E}_{\sigma^{1},\sigma^{2}\sim\mu^{(n)}_{\beta,A,\bm{h}}}\left[\left(R^{-}_{1,2}-q_{-}\right)^{4}\right]\right]\leq\frac{K_{1}(\mathcal{A})}{n^{2}}.$

Finally, applying Lemma A.2 and combining these inequalities implies that
there is some constant $K_{2}(\mathcal{A})$ such that

$\mathbb{E}_{A,\bm{h},z}\left[\left(z\sqrt{q}-\sum_{i<n}A_{i,n}\bm{m}^{(n)}_{i}\right)^{4}\right]\leq\frac{K_{2}(\mathcal{A})}{n^{2}};$
(23)

here, we also use the fact that our assumption on $\mathcal{A}$ ensures that
$q\geq c(\mathcal{A})>0$ for some constant $c(\mathcal{A})$.

Next, Talagrand (proof of Theorem 1.7.7 on page 78 of [Tal10]) shows that
under these same conditions, it holds that

$\mathbb{E}_{A,\bm{h},z}\left[\left(\beta\sum_{i=1}^{n-1}A_{i,n}\bm{m}_{i}-\beta^{2}(1-q)\bm{m}_{n}-\beta\sum_{i=1}^{n-1}A_{i,n}\bm{m}^{(n)}_{i}\right)^{4}\right]\leq\frac{K_{3}(\mathcal{A})}{n^{2}}$
(24)

for some other constant $K_{3}(\mathcal{A})>0$. Combining 23 and 24 with the
same inequality $(x+y)^{4}\leq 8(x^{4}+y^{4})$ implies that

$\mathbb{E}_{A,\bm{h},z}\left[\left(\beta\sum_{i=1}^{n-1}A_{i,n}\bm{m}_{i}-\beta^{2}(1-q)\bm{m}_{n}-\beta
z\sqrt{q}\right)^{4}\right]\leq\frac{K_{4}(\mathcal{A})}{n^{2}}.$

The same argument holds for each index $j\in[n]$, so we may find standard
normal variables $z_{1},\ldots,z_{n}$ on the same probability space where the
previous display holds for each $j\in[n]$. It finally follows by symmetry that

$\displaystyle\mathbb{E}_{A,\bm{h},z}$
$\displaystyle\left[\max_{i\in[n]}\left(\beta\sum_{j\neq
i}A_{i,j}\bm{m}_{j}-\beta^{2}(1-q)\bm{m}_{i}-\beta
z_{i}\sqrt{q}\right)^{4}\right]$
$\displaystyle\leq\mathbb{E}_{A,\bm{h},z}\left[\sum_{i\in[n]}\left(\beta\sum_{j\neq
i}A_{i,j}\bm{m}_{j}-\beta^{2}(1-q)\bm{m}_{i}-\beta
z_{i}\sqrt{q}\right)^{4}\right]$
$\displaystyle\leq\frac{K_{4}(\mathcal{A})}{n},$

and Jensen’s inequality implies that

$\mathbb{E}_{A,\bm{h},z}\left[\max_{i\in[n]}\left|\beta\sum_{j\neq
i}A_{i,j}\bm{m}_{j}-\beta^{2}(1-q)\bm{m}_{i}-\beta
z_{i}\sqrt{q}\right|\right]\leq\frac{K_{4}(\mathcal{A})^{1/4}}{n^{1/4}}.$

∎