# Learning Hard-Constrained Models with One Sample††thanks: A preliminary
version of the paper will appear in the Proceedings of the 2024 Annual ACM-
SIAM Symposium on Discrete Algorithms (SODA _’24_). For the purpose of Open
Access, the authors have applied a CC BY public copyright licence to any
Author Accepted Manuscript version arising from this submission. All data is
provided in full in the results section of this paper.

Andreas<EMAIL_ADDRESS>
University of Oxford
Alkis<EMAIL_ADDRESS>
Yale University
Anthimos Vardis<EMAIL_ADDRESS>
MIT

###### Abstract

We consider the problem of single-sample learning, i.e., the problem of
estimating the parameters of a distribution (Markov Random Field) using a
single sample. Previous work has mainly focused on soft-constrained
distributions, such as the Ising model, where remarkably it has been shown
that efficient single-sample learning is always possible for sparse graphs.

Here, we focus instead on single-sample learning of _hard_ -constrained
distributions. As our main running examples, we use the $k$-SAT, the proper
coloring models and the general $H$-coloring models (graph homomorphisms), for
which we obtain both positive and negative results. In contrast to the soft-
constrained case, we show in particular that single-sample estimation is not
always possible, and that the existence of an estimator is related to the
existence of non-satisfiable instances.

Following the approach of Chatterjee for soft-constrained distributions
(Annals of Statistics, 2007), our algorithms are based on the classical
pseudo-likelihood estimator. The main difficulty in our setting is that the
accuracy of the estimator is not driven by the sufficient statistics of the
distribution (which facilitated previous analyses). Instead, we show variance
bounds for the estimator using more involved coupling techniques inspired, in
the case of $k$-SAT, by Moitra’s sampling algorithm (JACM, 2019); our positive
results for single-sample learning for proper $q$-colorings and $H$-colorings
build on this new coupling approach. Our impossibility results are based on
constructing satisfiable instances which are either uniquely satisfiable or
enforce with high probability a particular value to the statistic determining
the distribution; in both cases, the distribution becomes insensitive to the
underlying parameters.

Using these methods, in the case of $q$-colorings on graphs with maximum
degree $d$, we show that a linear-time estimator exists when $q>d+1$, whereas
the problem is non-identifiable when $q\leq d+1$. For general $H$-colorings,
we show that standard conditions that guarantee sampling, such as Dobrushin’s
condition, are insufficient for one-sample learning; on the positive side, we
provide a condition that is sufficient to guarantee linear-time learning and
obtain applications for proper colorings and permissive models. For the
$k$-SAT model on formulas with maximum degree $d$, the picture for single-
sample learning is more intriguing, and we show a linear-time estimator when
$k\gtrsim 6.45\log d$, whereas the problem becomes non-identifiable when
$k\lesssim\log d$.

##  1 Introduction

Markov Random Fields (MRFs) are a standard framework for studying high-
dimensional distributions with conditional independence structure, represented
via a graph structure (typically an undirected graph or hypergraph). The most
well-studied example of an MRF is the Ising model which, in its simplest form,
is parameterised by a real number $\beta$ (corresponding to the so-called
_inverse temperature_ in statistical physics). Given a graph $G=(V,E)$ with
$n=|V|$, the Ising model corresponds to the probability distribution
$\mu_{G,\beta}$ on all possible assignments $x\in\\{-1,1\\}^{n}$, with
$\mu_{G,\beta}(x)\propto\exp(\beta x^{\top}Jx)$, where $J$ is the adjacency
matrix of $G$.

There has been an extensive amount of work on undestanding the complexity of
sampling and learning of MRFs. In the particular case of the Ising model,
there is an excellent understanding of the computational complexity of
sampling, see [SS12, GŠV16, EKZ22, CE22, EAMS22, AJK+22, KLR22, CLV23].
Analogously, in the computational learning theory community, there have been
major developments in understanding the efficiency of various statistical
tasks, including hypothesis testing [DDK19, GLP18] and learning from multiple
samples [Bre15, VMLC16, KM17].

Starting from the seminal work of Chatterjee [Cha07], there has been
significant interest in single-sample learning. In the context of single-
sampling learning for the Ising model, we are given the graph $G$ and a single
sample $\sigma$ from $\mu_{G,\beta}$, and the goal is to learn the value of
$\beta$. Surprisingly, on bounded-degree graphs $G$, single-sample learning is
always possible for any value of $\beta$ provided that $|\beta|=O(1)$; more
precisely, it is possible to compute $\hat{\beta}$ such that
$|\hat{\beta}-\beta|=O(1/\sqrt{n})$ with high probability over the choice of
the random sample $x$, see [Cha07, GM20] and [BM18, DDDVK20] for various
refinements/generalisations of this result for multi-parametered Ising
distributions. These positive results come in sharp contrast with known
results in the literature about the complexity of sampling, where phase
transition phenomena render standard sampling approaches inefficient (such as
Glauber dynamics) or even make approximate sampling NP-hard (when $\beta<0$),
see [SS12, GŠV16]. All the aforementioned results for single-sample learning
have mainly focused on variants of the Ising model [Cha07, DDDVK20, DDP19,
MHBM21, MSB20], which are soft-constrained, i.e., every possible assignment
$x\in\\{-1,1\\}^{n}$ has non-zero weight in the underlying distribution.

In this paper, we consider instead the case of hard-constrained distributions
where some assignments have zero weights. Canonical examples in this class are
the $k$-SAT and proper $q$-colorings models which have been extensively
studied in terms of sampling/inference (see Section 1.3). Our main results
show that for both of these problems the picture for single-sample learning is
more intriguing (compared to what one might expect from prior work on soft-
constrained learning or sampling), switching from efficiently solvable to
impossible (unidentifiable) depending on the values of $k,q$ relative to the
degree $d$. We also investigate the more general setting of $H$-colorings
where we show impossibility results for single-sample learning in regimes
where sampling is possible. We nevertheless propose a natural condition under
which efficient estimation is possible and apply it to obtain estimators for a
large class of models.

###  1.1 Results for $k$-SAT

In the vanilla version of the $k$-SAT model, the MRF distribution is over the
set of the satisfying assignments of a given $k$-SAT formula $\Phi$; here, we
consider the variant (see, e.g., [AP03]) where one of the truth assignments is
biased according to a parameter $\beta$. More precisely, let
$\Phi=\Phi_{n,k,d}$ denote a $k$-SAT formula with $n$ variables, where every
clause contains $k$ distinct literals and every variable is contained in at
most $d$ clauses. We identify $1$ with True and $0$ with False and denote by
$\Omega=\Omega(\Phi)\subseteq\\{0,1\\}^{n}$ the set of satisfying assignments
of $\Phi$ (i.e., $\Omega$ consists of all the assignments to the variables
that satisfy all the clauses of $\Phi$). Then, for a parameter
$\beta\in\mathbb{R}$, the MRF for the $k$-SAT model gives to each
$\sigma\in\Omega$ a weight that depends on the number of variables set to 1,
specifically

$\mathop{\bf Pr\/}_{\Phi,\beta}[\sigma]\propto\mathrm{e}^{\beta
C(\sigma)}\mbox{ for all $\sigma\in\Omega(\Phi)$},$ (1)

where $C(\sigma)$ is the number of variables set to 1 under $\sigma$. This
tilted SAT model has been studied in more applied settings as “weighted model
counting” [CD08, SBK05, CFM+14, CFMV15, GSS08]. We will refer to the
distribution in (1) as the _hard-SAT_ distribution444There is also a
“soft”-SAT distribution, known also as permissive SAT, which is over the space
of all possible assignments $\\{0,1\\}^{n}$, where the weight of an assignment
depends on the number of unsatisfied clauses. The soft-version can viewed as a
version of the tensor Ising model and is therefore covered by the results of
[MSB20]. .

A recent breakthrough of Moitra [Moi19] gave an algorithm for approximately
sampling from the degree-$d$ hard-SAT model (when $\beta=0$) when $k\geq
60\log d$, by exploiting in a clever way connections with the Lovász Local
Lemma (LLL)555This efficient sampling threshold has been improved in
subsequent works [FGYZ21, FHY21, JPV22, HWY23a]. See [HWY23a] for a reference
which achieves a fast uniform sampler when $k\gtrsim 5\log d$..

Our first main result is a single-sample estimator for the hard-SAT model when
roughly $k\geq 6.45\log d$ (as $\beta\rightarrow 0$), and an impossibility
result when roughly $k\leq\log d$. We say that a real $\hat{\beta}$ is a
$\delta$-estimate of a real $\beta$ if $|\hat{\beta}-\beta|\leq\delta$.

######  Theorem 1 (Parameter Estimation of Hard-SAT).

Let $d,k\geq 3$ be integers.

  * •

For $k\leq\log d-\log k+\Theta(1)$, there exists a formula $\Phi=\Phi_{n,k,d}$
with a unique satisfying assignment, i.e., it is impossible to estimate
$\beta^{\star}$ from a sample $\sigma\sim\mathop{\bf Pr\/}_{\Phi,\beta^{*}}$.

  * •

Let $B,\epsilon>0$ be arbitrary constants. Then, for all
$k\geq\frac{6.45\log(dk)+\Theta(1)}{\log(1+\mathrm{e}^{-B})}$ and
$|\beta^{\star}|\leq B$ , there exists an algorithm that, on input
$\Phi=\Phi_{n,k,d}$ and a sample $\sigma\sim\mathop{\bf
Pr\/}_{\Phi,\beta^{*}}$, outputs in linear time an
$O(\frac{1}{\sqrt{n}})$-estimate666We use $O(1)$ to denote a constant
depending only on $d,k,B,\epsilon$. $\hat{\beta}_{\sigma}$ for $\beta^{*}$
with probability $\geq 1-\epsilon$ over the choice of $\sigma$, i.e.,
$\mathop{\bf
Pr\/}_{{\Phi,\beta^{\star}}}\left[\big{|}\hat{\beta}_{\sigma}-{\beta^{\star}}\big{|}=O(1/{\sqrt{n})}\right]\geq
1-\epsilon$.

At a technical level, the proof of this result poses various challenges
compared to prior work in soft-constrained models. In particular, we develop a
general technique, based on a coupling inspired by [Moi19], in order to show
that the (negative) pseudo-likelihood objective is strongly convex. For the
non-identifiability result above the LLL regime we refer to Lemma 13 and for
the efficient algorithm we refer to Section 3 for a proof sketch.

###  1.2 Results for $q$-colorings and general $H$-colorings

We next consider the $q$-colorings model and, more generally, the
$H$-colorings model. These were previously studied in the context of single-
sample learning by Bhattacharya and Ramanan [BR21], where they introduced a
condition (the Rainbow Condition) and obtained an efficient estimator for
learning the hardcore model (weighted independent sets). Here, we first
investigate their condition as well as other standard conditions in the
literature (such as Dobrushin’s condition), and show that for general
$H$-colorings models they are insufficient for single-sample learning. Then,
building on the work of [BR21], we show that a variant of the Rainbow
Condition, which we call the 2-Rainbow Condition, is in fact sufficient to
imply single-sample learning. We then combine this result with an adaptation
of the coupling technique that we developed for the case of $k$-SAT to
conclude a linear-time estimator for $q$-colorings and permissive models.

##### Definitions.

In the $H$-coloring problem, we have a (fixed) graph $H$ on the set of
vertices $[q]=\\{1,\ldots,q\\}$ which might contain self-loops. Given a graph
$G=(V(G),E(G))$ with $n$ vertices, an _$H$ -coloring_ of $G$ is an assignment
$\sigma\in[q]^{n}$ of colors to $V(G)$ such that $(\sigma_{u},\sigma_{v})\in
E(H)$ whenever $(u,v)\in E(G)$. In words, two colors can be adjacent in a
valid coloring of $G$ if and only if they are neighboring in $H$. The proper
$q$-coloring model can be viewed as a special case of this framework with
$H=K_{q}$ (the clique on $q$ vertices), i.e., no monochromatic edges are
allowed in the coloring $\sigma$. For the learning problem, we consider the
space $\Omega^{H}_{G}\subseteq[q]^{V(G)}$ of all the $H$-colorings of the
graph $G$, weighted according to the counts of the different colors using a
vector of parameters
$\boldsymbol{\beta}=(\beta_{1},\ldots,\beta_{q})\in\mathbb{R}^{q}$. More
precisely, the MRF for the $H$-coloring model over $\Omega^{H}_{G}$ is given
by

$\mathop{\bf
Pr\/}_{G,H,\boldsymbol{\beta}}[\sigma]\propto\exp\bigg{(}\sum_{i=1}^{q}\beta_{i}c_{i}(\sigma)\bigg{)}\mathbf{1}\\{\sigma\in\Omega^{H}_{G}\\},$
(2)

where, for $i\in[q]$ and $\sigma\in[q]^{V(G)}$, $c_{i}(\sigma)$ is the number
of nodes in $G$ with color $i$.777Note that the sum of $c_{i}(\sigma)$ over
$i\in[q]$ is $|V(G)|$ and so we can assume that $\beta_{q}=0$ without loss of
generality.  Our goal is, given a single sample $\sigma\sim\mathop{\bf
Pr\/}_{G,H,\boldsymbol{\beta}^{\star}}$, to efficiently compute a good
estimate $\widehat{\boldsymbol{\beta}}$ for $\boldsymbol{\beta}^{\star}$ in
$L_{2}$ norm.

Before proceeding, let us briefly comment on the structure of the colorings
probability distribution. The vertex-based weightings we consider in this work
(weighting each color individually) are analogous to the vertex-based
weighting of the hard-core model (where, for an independent set $I$, a vertex
$v$ contributes a factor of $\lambda$ if $v\in I$, and 1 otherwise) or the
Ising model “with external fields” (where the weight of an Ising configuration
also depends on the spin counts). Analogously weighted models have also been
studied in various contexts, e.g., weighted $H$-colorings have been studied in
approximate sampling and graph limits. We also remark that, at the level of
generality we consider here, the vertex-based weighting of the distributions
is not much different conceptually than having edge-based interactions as in
the Ising model (e.g., having weights on the adjacency matrix of $H$); for
example, on regular graphs vertex weights can also be viewed as edge weights.
The important aspect of the distributions we consider, in either the vertex-
based or edge-based weight formulation, is that one hard codes the zeros in
the adjacency matrix of $H$ (so that adjacency of certain pairs of colors is
ruled out).

####  1.2.1 Negative results for $H$-colorings

We study various conditions that exist in the literature for uniqueness and
learnability of Gibbs distributions and show that they are not sufficient to
guarantee (even) identifiability of the parameters for general $H$-coloring
models.

For instance, we consider the Dobrushin and Dobrushin-Shloshman conditions
[Dob68]. These are well-studied conditions and are known to imply efficient
sampling (via fast mixing of the heat bath Glauber dynamics) [Hay06]. Notably,
[BCŠV18] shows that structure learning for $H$-colorings with multiple samples
is possible when the DS condition holds true. We show that neither of these
conditions suffices for learning from a single sample. Also, we investigate
the Rainbow Condition, introduced in [BR21], which is defined as follows:
suppose $\sigma\in\Omega_{G}^{H}$ is a proper $H$-coloring of $G$. Fix
$r\in[q-1]$ and let us denote by $u_{r}(\sigma)\in[n]$ the number of vertices
$v$ of $G$ that can be re-colored under $\sigma$ by color $r$ while keeping
the colors of all the other vertices (i.e., $V\backslash\\{v\\}$) the same.
The Rainbow Condition roughly requires that for all colors $r\in[q-1]$,
$u_{r}(q)=\Omega(n)$ with probability $1-o(1)$. We show that Rainbow Condition
also fails to imply one-sample learnability. Our main negative result follows.

######  Theorem 2 (Negative Results for Parameter Estimation for
$H$-colorings).

The following hold for any integer $n\geq 1$.

  * •

(Dobrushin fails) There exists a tuple $(G=G_{n},H=H_{q})$ and parameters
$\boldsymbol{\beta_{1}},\boldsymbol{\beta_{2}}\in\mathbb{R}^{q}$ with
$\|\boldsymbol{\beta_{1}}-\boldsymbol{\beta_{2}}\|_{\infty}=\Theta(1)$ such
that the $H$-coloring model with these $2$ parameters satisfies Dobrushin’s
condition (see Definition 19) but
$\mathrm{KL}(P_{\boldsymbol{\beta_{1}}}\parallel
P_{\boldsymbol{\beta_{2}}})=O(n^{2}\exp(-n))$.

  * •

(Dobrushin-Shlosman fails) There exists a tuple $(G=G_{n},H=H_{q})$ and
parameters $\boldsymbol{\beta_{1}},\boldsymbol{\beta_{2}}\in\mathbb{R}^{q}$
with $\|\boldsymbol{\beta_{1}}-\boldsymbol{\beta_{2}}\|_{\infty}=\Theta(1)$
such that the $H$-coloring model with these $2$ parameters satisfies
Dobrushin-Shlosman’s condition (see Definition 19) but
$\mathrm{KL}(P_{\boldsymbol{\beta_{1}}}\parallel
P_{\boldsymbol{\beta_{2}}})=0$.

  * •

(Rainbow Condition fails) There exists a tuple $(G=G_{n},H=H_{q})$ such that
the $H$-coloring model with any parameter
$\boldsymbol{\beta}\in\mathbb{R}^{q}$ satisfies the Rainbow Condition (see
Definition 22) but for any
$\boldsymbol{\beta_{1}},\boldsymbol{\beta_{2}}\in\mathbb{R}^{q}$,
$\mathrm{KL}(P_{\boldsymbol{\beta_{1}}}\parallel
P_{\boldsymbol{\beta_{2}}})=0$.

Appendix B contains the proofs of the above collection of negative results
about the one-sample learnability of $H$-colorings. Given the above results,
it is interesting to investigate whether an efficient single-sample algorithm
exists for $H$-colorings under mild conditions. This is the context of the
upcoming section, where we show that a natural variant of the Rainbow
Condition is sufficient for learning.

####  1.2.2 Positive results for $H$-colorings

The main goal of this section is to give a condition for general $H$-colorings
that (i) will allow us to obtain an efficient single-sample learning
algorithm, and (ii) is sufficiently mild to allow for a wide range of
applications. Indeed, we use this to obtain a tight phase transition for the
single-sample learnability of proper $q$-colorings (a result which was not
known by prior work) and obtain efficient algorithms for the generic class of
permissive models.

Let us first introduce the aforementioned condition, which we call _2-Rainbow
Condition_. Suppose $\sigma\in\Omega_{G}^{H}$ is a proper $H$-coloring of an
$n$-vertex graph $G$ and denote by $u_{rq}(\sigma)$ the number of vertices $v$
of $G$ that can be re-colored in $\sigma$ with both colors $r$ and $q$ (i.e.,
setting $\sigma(v)=r$ and $\sigma(v)=q$ while keeping the rest of $\sigma$ the
same still yield proper $H$-colorings of $G$). We say that $H$ satisfies the
2-Rainbow Condition (with constant $\delta>0$) on graphs $G$ of maximum degree
$d$ if for all colors $r\in[q-1]$, $u_{rq}(\sigma)$ is lower bounded with
probability close to 1 (as $n$ grows), i.e.,

$\mathop{\bf Pr\/}_{G,H,\boldsymbol{\beta}^{*}}\big{[}u_{rq}(\sigma)\geq\delta
n\mbox{ for all }r\in[q-1]\big{]}=1-o(1).$ (3)

We note that this condition is a two-coloring refinement of the Rainbow
Condition, introduced by [BR21], which as we showed in Theorem 2 does not
suffice for learning $H$-colorings.

The following result builds on related ideas to that of Theorem 1. We sketch
its proof in Section 4 and give the full proof in Section C.1. In the
statement below, we use $O(1)$ to denote a constant depending only on
$q,d,\delta,B,\epsilon$.

######  Theorem 3.

(Parameter Estimation for $H$-colorings). Let $q,d\geq 2$ be integers and
$B,\epsilon>0$ be reals. Consider an $H$-coloring model with parameter
$\boldsymbol{\beta}^{*}\in[-B,B]^{q}$ that satisfies the 2-Rainbow Condition
with constant $\delta>0$ (see (3)) on max-degree $d$ graphs.

There exists a linear-time algorithm that, on input $G$ and a sample
$\sigma\sim\mathop{\bf Pr\/}_{G,H,\boldsymbol{\beta}^{\star}}$, outputs a
$O(\frac{1}{\sqrt{n}})$-estimate $\widehat{\boldsymbol{\beta}}_{\sigma}$ for
$\boldsymbol{\beta}^{\star}$ w.p. $1-\epsilon$ over $\sigma$, i.e.,
$\mathop{\bf
Pr\/}_{G,H,\boldsymbol{\beta^{\star}}}\left[\big{\|}\widehat{\boldsymbol{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}}\big{\|}_{2}=O(\frac{1}{\sqrt{n}})\right]\geq
1-\epsilon.$

As applications of our general algorithmic result for $H$-colorings, we show
that efficient single-sample learning of proper $q$-colorings is possible when
$q>d+1$. More to that, we can invoke one of the hard instances of Theorem 2 to
show that this threshold is tight. Our result is hence a sharp phase
transition for the problem of learning proper $q$-colorings with a single-
sample: we show that if $q\geq d+2$, then estimation is possible with the
standard minimax rate. In contrast, if $q\leq d+1$, we can construct a
sequence of graphs $\\{G_{n}\\}_{n=1}^{\infty}$, where estimating the true
$\boldsymbol{\beta^{\star}}$ is impossible. The following Corollary formalizes
these claims. As mentioned earlier, we use $O(1)$ to denote a constant
depending only on $q,d,\delta,B,\epsilon$.

######  Corollary 4.

(Parameter Estimation for Proper $q$-Colorings). Let $q,d\geq 2$ be integers
and $B,\epsilon>0$.

  * •

For $q\leq d+1$, there exists a sequence of graphs $\\{G_{n}\\}_{n}$ with max
degree $d$ such that for any
$\boldsymbol{\beta_{1}},\boldsymbol{\beta_{2}}\in\mathbb{R}^{q}$, it holds
that the KL divergence between $\mathop{\bf
Pr\/}_{G_{n},{\boldsymbol{\beta_{1}}}}$ and $\mathop{\bf
Pr\/}_{G_{n},{\boldsymbol{\beta_{2}}}}$ is 0, i.e., it is impossible to
estimate the parameter vector from a sample from the proper $q$-coloring
model.

  * •

For $q>d+1$ and $\bm{\beta}^{*}\in[-B,B]^{q}$, there exists a linear-time
algorithm that, on input $G$ with max degree $d$ and a sample
$\sigma\sim\mathop{\bf Pr\/}_{G,\boldsymbol{\beta}^{\star}}$, outputs an
$O(\frac{1}{\sqrt{n}})$-estimate $\widehat{\boldsymbol{\beta}}_{\sigma}$ for
$\boldsymbol{\beta}^{\star}$ with probability $1-\epsilon$ over $\sigma$,
i.e., $\mathop{\bf
Pr\/}_{G,\boldsymbol{\beta^{\star}}}\left[\|\widehat{\boldsymbol{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}}\|_{2}=O(\frac{1}{\sqrt{n}})\right]\geq
1-\epsilon.$

This result is in contrast to structure learning with multiple samples
[BCŠV18], where the problem is identifiable in the tree uniqueness region
(i.e., when $q>d$). The algorithmic part of Corollary 4 can be proven using
our main result about parameter estimation for $H$-coloring distributions from
one sample and so we refer to Appendix C for its proof. In particular, the
case $q>d+1$ is handled in Section C.2 and the case $q\leq d+1$ appears in
Theorem 23.

Also, we show how to apply our result to the general class of permissive
models, i.e., the setting where there is an unconstrained color $r$ (connected
in $H$ to all the vertices, including itself).

######  Corollary 5 (Parameter Estimation for Permissive Models).

Let $q,d\geq 2$ be integers, $B,\epsilon>0$ be reals and
$\boldsymbol{\beta^{\star}}\in[-B,B]^{q}$. Let $H$ be a connected graph that
has an unconstrained color.

There exists a linear-time algorithm that, on input $G$ with max degree $d$
and a sample $\sigma\sim\mathop{\bf Pr\/}_{G,H,\boldsymbol{\beta}^{\star}}$,
outputs an $O(\frac{1}{\sqrt{n}})$-estimate
$\widehat{\boldsymbol{\beta}}_{\sigma}$ for $\boldsymbol{\beta}^{\star}$ with
probability $1-\epsilon$ over the choice of $\sigma$, i.e., $\mathop{\bf
Pr\/}_{G,H,\boldsymbol{\beta^{\star}}}\left[\big{\|}\widehat{\boldsymbol{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}}\big{\|}_{2}=O(\frac{1}{\sqrt{n}})\right]\geq
1-\epsilon.$

The proofs of these two statements (for $q$-coloring with $q>d+1$ and
permissive models) require careful coupling arguments that resemble that for
the hard-SAT model. We sketch the main idea in Section 4.1 and give the
details into Section C.2 and Section C.3.

We further remark that, as we showed in Theorem 2, the Rainbow Condition
considered in [BR21] is not sufficient to conclude these three results
(Theorem 3, Corollary 4 and 5).

###  1.3 Related Work

##### Parameter Estimation in Graphical Models.

Single-sample statistical estimation [Bes74, BN18, DDDVK20] has a long line of
work: [Cha07, BM18, GM20, DDDVK20] study the Ising model, [DDP19], [MHBM21]
and [KDD+21] study Linear and/or Logistic Regression, [MSB20] studies the
Tensor Ising model and [DKSS21] designs robust algorithms for Ising models
under Dobrushin’s condition. In a related direction, [DDDJ19] studies
statistical learning theory questions from one dependent sample. Finally,
[BR21] studies hard-constrained models, as we do.

Estimation questions in graphical models with multiple samples have been also
extensively studied: [Bre15] was the first work to obtain polynomial time
algorithms for learning Ising models on bounded degree graphs. Improved
guarantees where obtained in [HKM17, VMLC16, KM17]. Moreover, [DDK19, GLP18]
focus on the testing problem for Ising models. For hard constrained models,
[BCŠV18] studied structure learning for $H$-colorings with multiple samples
and [BDNP21] studies truncated sparse Graphical models. We remark that our
hard-constrained models are special cases of truncated/censored distributions,
by considering truncations of discrete product measures (as in [FKT20]) when
the set has some special combinatorial structure. For instance, in our hard
SAT model, we consider a truncated Boolean product distribution where the set
contains all the satisfying assignments of a known CNF formula. Designing
efficient algorithms for truncated [DGTZ18, DGTZ19, NP20, KTZ19, FKT20, FKT22,
DNS23, HN23] and censored [FKKT21, CDDK22, Ple21] problems has recently gained
attention from the computational learning theory community.

Close to our hard-constrained setting, [BCŠV18] initiated the study of
structure learning for $H$-colorings with multiple samples. For proper
$q$-colorings, they showed that in the tree uniqueness region ($q>d$) the
problem is identifiable and there exists an efficient structure learning
algorithm, while when $q\leq d$, the problem is not identifiable.

The work of [BR21] is the closest to our paper. [BR21] also studied hard-
constrained models. In particular, they provided an MPL-based algorithm for
the hardcore model (distribution over independent sets of a graph) and studied
sufficient conditions for single-sample learnability for general
$H$-colorings. For the latter model, they introduced the Rainbow Condition
(see Definition 22), a property that in general does not imply single-sample
learnability (as we show in Theorem 2).

##### Sampling from Hard-Constrained Distributions.

The hard-SAT model (and its soft-SAT analogue) are standard across computer
scientists [AP03, MS06, Gao08, GGGY21], mathematicians [Tal01] and physicists
[MZ96]. Extensive work has been done in the area of efficiently finding and
uniformly sampling satisfying assignments for SAT formulae; we refer to
[Bec91, MT10, Moi19, CMM23, HWY23b, ACO08, BH22, CO10, GGGHP22, FGYZ21, GJL19,
JPV22] and the references therein. For the proper $q$-coloring problem, the
sampling problem has been also studied quite well, see e.g., [Jer95, Vig00,
Mol02, FV07, GŠV15, CDM+19, CLV21, CGŠV21, BCC+22]. $H$-colorings are a
fundamental concept in theoretical computer science, dating back to [HN90],
and have been extensively studied in terms of counting and sampling [DG00,
GKP02, DGGJ04, GGJ16].

##  2 Overview: the Pseudo-Likelihood Objective

Our parameter estimation algorithms are based on the Maximum Pseudo-Likelihood
(MPL) estimator (introduced by Besag [Bes74]), which we now define. For a
vector $\sigma=(\sigma_{1},\ldots,\sigma_{n})$ and $i\in[n]$, we let
$\sigma_{-i}$ denote the induced assignment on $[n]\backslash\\{i\\}$ and
denote by $(\sigma_{i}=x,\sigma_{-i})$ the assignment that agrees with
$\sigma$ on $[n]\backslash\\{i\\}$ and assigns the value $x$ to $i$.

######  Definition 6.

Given a discrete random vector $\sigma=(\sigma_{1},...,\sigma_{n})$ whose
joint distribution is parametrized by a $q$-dimensional vector $\bm{\beta}$
lying in a region $\mathcal{R}\subseteq\mathbb{R}^{q}$, the MPL estimate of
$\bm{\beta}$ is defined as

$\widehat{\bm{\beta}}_{n}=\widehat{\bm{\beta}}_{n}(\sigma)=\operatorname*{argmin}_{\bm{\beta}\in\mathcal{R}}\phi(\bm{\beta},\sigma),\mbox{
where }\phi(\bm{\beta},\sigma)=-\log\prod_{i\in[n]}f_{i}(\bm{\beta},\sigma),$
(4)

and $f_{i}(\bm{\beta},\sigma)$ is the conditional probability of $\sigma_{i}$
given $(\sigma_{-i})$, viewed as a function of $\bm{\beta}$.

To argue about the consistency of the MPL estimate, the strategy devised by
Chatterjee was to argue via the first/second derivatives. Namely, for
$\phi_{1}=\nabla_{\bm{\beta}}\phi$ and $\phi_{2}=\nabla^{2}_{\bm{\beta}}\phi$,
the key is to establish the following bounds (with $\mathbf{I}_{q}$ being the
$q$-dimensional identity matrix):

$\displaystyle\mbox{(i)}\ \mathop{\bf
E\/}_{\sigma}\left[\left\|\phi_{1}(\bm{\beta^{*}};\sigma)\right\|_{2}^{2}\right]=O(n)\mbox{
where $\sigma\sim\mathop{\bf Pr\/}_{\Phi,\beta^{*}}$},$ (5)
$\displaystyle\mbox{(ii)}\inf_{\bm{\beta}\in\mathcal{R}}\phi_{2}(\bm{\beta};\sigma)\succcurlyeq\Omega(n)\mathbf{I}_{q}\mbox{
with probability $1-o(1)$ over $\sigma\sim\mathop{\bf
Pr\/}_{\Phi,\beta^{*}}$}.$

Intuitively, the first-derivative condition in (i) says that, for most
$\sigma$, the (pseudo)likelihood is large for $\bm{\beta}$ close to
$\bm{\beta}^{*}$, while the convexity condition in (ii) ensures that deviating
substantially from ${\bm{\beta}}^{*}$ will cause a substantial loss in the
(pseudo)likelihood probability for most $\sigma\sim\mathop{\bf
Pr\/}_{\Phi,\beta^{*}}$.

Among the two conditions, it turns out that the most challenging to establish
in our hard-constrained setting is (ii), the second derivative; previous
analyses relied on the fact that the second derivative was essentially the
statistic determining the distribution (e.g., in the case of $k$-SAT that
would be $C(\sigma)$ determining the weight of $\sigma$).

Prior work on soft-constrained models [Cha05, BM18, DDDVK20] has often relied
on sophisticated concentration inequalities to establish strong convexity. In
contrast, our proof is based on exploiting the combinatorial structure of the
problem and hence we provide more direct arguments. In particular, one of the
main contributions of this work is the development of a general coupling
technique to handle the strong-convexity condition in (ii). Namely, we
construct a suitable coupling between $\sigma$ and a sequence of i.i.d. random
variables, which then enables us to lower-bound the second derivative using
standard Chernoff bounds. The details of constructing this coupling depend on
the model (with $k$-SAT being more involved), but at a high-level the overall
strategy is to greedily extract disjoint neighbourhoods to ensure
independence/concentration; this extraction requires more effort for $k$-SAT
but comes more naturally for our colorings results (with a fair bit of
technical work in both cases).

##  3 Proof of Theorem 1

To formulate the MPL estimate for $k$-SAT, consider a formula $\Phi$ with
variable set $[n]=\\{1,\ldots,n\\}$ and a satisfying assignment
$\sigma\in\Omega(\Phi)$. Recall that $C(\sigma)$ denotes the number of true
variables under $\sigma$; for $j\in\\{0,1\\}$, we extend this notation and let
$C(x,\sigma_{-i})$ denote the number of true variables in the assignment
obtained from $\sigma$ by setting the variable $i$ to $x$. We say that a
variable $i\in[n]$ is flippable in $\sigma$ if flipping the value of $i$ under
$\sigma$ while keeping the assignment of the remaining variables the same is
still a satisfying assignment of $\Phi$. For a non-flippable $i$ we have
$\mathop{\bf Pr\/}_{\Phi,\beta}[\sigma_{i}|\sigma_{-i}]=1$, whereas for a
flippable $i$ we have $\mathop{\bf
Pr\/}_{\Phi,\beta}[\sigma_{i}|\sigma_{-i}]=\tfrac{\mathrm{e}^{\beta
C(\sigma)}}{\mathrm{e}^{\beta C(0,\sigma_{-i})}+\mathrm{e}^{\beta
C(1,\sigma_{-i})}}$. Hence, we can write the _negative_ log-pseudo-likelihood
function for $k$-SAT, denoted by $\phi$ henceforth, as

$\phi(\beta;\sigma)=-\sum_{i\in[n]}\log\mathop{\bf
Pr\/}_{\Phi,\beta}[\sigma_{i}|\sigma_{-i}]=\sum_{i\in\mathcal{F}(\sigma)}\left(\log\left(e^{\beta
C(1,\sigma_{-i})}+e^{\beta C(0,\sigma_{-i})}\right)-\beta C(\sigma)\right),$
(6)

where $\mathcal{F}(\sigma)$ denotes the set of flippable variables in
$\sigma$.

We next show consistency of the MPL estimate using the two conditions in (5).
The Lemma below establishes (the easier) condition (i).

######  Lemma 7.

For $\Phi=\Phi_{n,k,d}$ with $\Omega(\Phi)\neq\emptyset$ and
$\beta\in\mathbb{R}$, it holds that $\mathop{\bf
E\/}\big{[}(\phi_{1}(\beta;\sigma))^{2}\big{]}\leq kdn$, where the expectation
is over $\sigma\sim\mathop{\bf Pr\/}_{\Phi,\beta}$.

###### Proof Sketch..

For $i\in[n]$ and $\sigma\in\Omega(\Phi)$, let $x_{i}$ denote a sample from
$\mathop{\bf Pr\/}_{\Phi,\beta}[\cdot\mid\sigma_{-i}]$ and $\sigma^{(i)}$ be
the assignment obtained from $\sigma$ by setting the value of $i$ to $x_{i}$.
From (6), we obtain that

$\phi_{1}(\beta;\sigma)=\sum_{i\in[n]}\Big{(}\mathop{\bf
E\/}_{x_{i}}[C(x_{i},\sigma_{-i})]-C(\sigma)\Big{)},$ (7)

see Lemma 14 for details. Note that the terms in the sum corresponding to
variables $i$ that are not flippable in $\sigma$ are equal to 0.

Let $I$ denote a uniform variable from $[n]$ and let $f(\sigma)=\mathop{\bf
E\/}_{I}[C(\sigma)-C(\sigma^{(I)})|\sigma]$. Using the exchangeable pairs
technique of Chatterjee [Cha05, Cha07], we show in the Appendix that

$\tfrac{1}{n^{2}}\mathop{\bf
E\/}_{\sigma}\left[\left(\phi_{1}(\beta;\sigma)\right)^{2}\right]=\tfrac{1}{2}\mathop{\bf
E\/}_{\sigma,I}\big{[}(f(\sigma)-f(\sigma^{(I)}))(C(\sigma)-C(\sigma^{(I)})\big{]}.$
(8)

It is not hard to observe now that, for any $i\in[n]$,
$|C(\sigma)-C(\sigma^{(i)})|\leq 1$ and $|f(\sigma)-f(\sigma^{(i)})|\leq kd/n$
(for $\tau=\sigma^{(i)}$ and a variable $j\in[n]$, the quantities
$S_{j}=C(\sigma)-C(\sigma^{(j)})$ and $T_{j}=C(\tau)-C(\tau^{(j)})$ can only
differ if the variable $j$ is in some clause with variable $i$). This yields
that the right-hand side in (8) is $\leq dk/n$, implying the lemma. ∎

The proof for condition (ii) is more involved and is where we will need to use
the regime of $k$ in Theorem 1. We start by writing $\phi_{2}$, the second
derivative of $\phi$. Analogously to (7), with $x_{i}\sim\mathop{\bf
Pr\/}_{\Phi,\beta}(\cdot\mid\sigma_{-i})$, we show in Lemma 14 that

$\mbox{$\phi_{2}(\beta;\sigma)=\sum_{i\in[n]}\mathop{\bf
Var\/}_{x_{i}}[C(x_{i},\sigma_{-i})]$}.$ (9)

It will be useful to have a more combinatorial expression for $\phi_{2}$.
Observe that if variable $i$ is not flippable in $\sigma$, then there is a
unique way to set it if $\sigma_{-i}$ is fixed and hence $\mathop{\bf
Var\/}_{x_{i}}[C(x_{i},\sigma_{-i})]=0$. On the other hand, if $i$ is
flippable in $\sigma$, we have $\mathop{\bf
Var\/}_{x_{i}}[C(x_{i},\sigma_{-i})]=\tfrac{\mathrm{e}^{\beta}}{(\mathrm{e}^{\beta}+1)^{2}}$.
So,

$\phi_{2}(\beta;\sigma)=\frac{\mathrm{e}^{\beta}}{(\mathrm{e}^{\beta}+1)^{2}}\sum_{i\in[n]}e_{i}(\sigma),$
(10)

where $e_{i}(\sigma)$ is the indicator of the event that variable $i$ is
flippable in $\sigma$ (i.e., _every_ clause where a literal for $i$ appears is
satisfied by some variable $j\neq i$ in $\sigma$). Condition (ii) in (5)
therefore amounts to showing that $\sum_{i\in[n]}e_{i}(\sigma)=\Omega(n)$ with
high probability over the choice of $\sigma$.

###  3.1 The coupling

Our technique for lower-bounding the right-hand side of (9) (with high
probability over the choice of $\sigma$) is inspired by so-called spatial-
correlation properties studied in approximate sampling. For convenience,
consider the graph $G_{\Phi}$ with vertex set $[n]$ where two variables $i$
and $j$ are connected by an edge when they appear together in a clause (either
positively or negatively). In settings where sampling is possible, it is
reasonable to expect that $\sigma_{i}$ and $\sigma_{j}$ are almost independent
from each other when $i$ and $j$ are far away in $G_{\Phi}$, and hence
potentially $e_{i}(\sigma)$ and $e_{j}(\sigma)$ will be almost independent as
well (since these only depend on the one-step neighbourhood of the variables).

There are a couple of caveats in applying this strategy for single-sample
learning. First, in the approximate sampling setting, the standard techniques
require typically even stronger correlation properties (rather than variable-
to-variable correlations, one needs to control instead variable-to-sets
correlations). Here, we want to avoid the stronger properties to go beyond the
sampling regime, and approach instead the satisfiability threshold (this
arises not only for the case of $k$-SAT but also for colorings and
$H$-colorings). Second, the most natural implementation of this approach does
not quite work in our setting since instead of $\sigma_{i}$ and $\sigma_{j}$,
we are actually interested in the events $e_{i}(\sigma)$ and $e_{j}(\sigma)$.
Conditioning on $\sigma_{i}$ affects only one in $k$ literals for each of the
$\leq d$ clauses that $i$ appears, so it is unlikely to matter much and one
can hope to show the effect to die off based on what has not been revealed.
Instead, the most natural way to condition on $e_{i}(\sigma)$ is to reveal the
assignment of all variables that share a clause with $i$; unfortunately this
opens up the possibility of a cascading effect where variables get biased from
what has been revealed and that potentially reaches $j$.

Despite these caveats, it is still useful to start with the sampling idea of
Moitra for $k$-SAT [Moi19]. There, the key insight was to approximate the
marginals of a carefully selected subset of the variables , the so-called
marked variables. The following is based on the technique of [Moi19, Lemma
3.1] using the Lovász Local Lemma (LLL), the proof is given in Section A.4.

For $x,y\in(0,1)$, let $\mathrm{KL}(x\parallel
y)=x\ln(x/y)+(1-x)\ln((1-x)/(1-y))$. Let $\lambda\in(0,1/2)$ be the solution
to $\mathrm{KL}(\lambda\parallel 1/2)\log_{2}e=\lambda/2$, so that
$2/\lambda\approx 6.45$.

######  Lemma 8.

Suppose $k\geq(2/\lambda)\log(dk)+\Theta(1)$. Consider a formula
$\Phi=\Phi_{n,k,d}$. Then, there is a marking of the variables,
$\mathcal{M}:[n]\to\\{\text{marked, unmarked}\\}$, such that each clause $c$
in the formula has at least $\lambda k$ marked and at least $\lambda k$
unmarked variables.

A key feature of the separation into marked and unmarked variables is that, no
matter how we set the marked variables, the resulting formula is still
satisfiable (as long as $k\gtrsim(2/\lambda)\log d$ thanks to the existence of
the unmarked variables) using again the LLL; in fact, Moitra showed that for
$\beta=0$ the marginal probability that a marked variable takes the value 1 is
close to 1/2. We obtain an analogue of this property in the weighted setting,
in fact we show the following Lemma (here, $\Phi^{\prime}$ should be regarded
as a subformula of $\Phi$ obtained by setting some marked variables, possibly
all, in an arbitrary way).

######  Lemma 9.

Fix a formula $\Phi^{\prime}$ with maximum degree $d$ and set of variables
corresponding to the set $[n]$, where every clause has at least $\lambda k$
and at most $k$ variables, where
$k\geq\tfrac{2\log(dk)+\Theta(1)}{\lambda\log(1+\mathrm{e}^{-\beta})}$.

For $i\in[n]$, let $e_{i}(\sigma)$ be the event that $i$ is flippable in
$\sigma\sim\mathop{\bf Pr\/}_{\Phi,\beta}$. Then $\mathop{\bf
Pr\/}_{\Phi,\beta}[e_{i}(\sigma)=1]\geq 1/2$.

At this stage, a natural approach to show the $\Omega(n)$ lower bound on
$\phi_{2}$ would be to establish that for the marked variables $S$ it holds
that $\sum_{i\in S}e_{i}(\sigma)=\Omega(n)$, since under any conditioning of
the marked variables one can apply the lower bound in Lemma 9. Unfortunately,
the cascading issue explained earlier persists since to determine
$e_{i}(\sigma)$ we need to reveal the assignment of all neighbors of variable
$i$ and this gets in the way of extracting some conditional independence among
marked variables.

The observation now that simplifies things significantly is that we only need
to lower bound $e_{i}(\sigma)$, so we can instead consider the indicator
$g_{i}(\sigma)$ of the event that each clause $c$ where $i$ appears is
satisfied by some _marked_ variable other than $i$. Note that $e_{i}(\sigma)$
is 1 if each clause is satisfied by some variable other than $i$ and hence
trivially $e_{i}(\sigma)\geq g_{i}(\sigma)$. The benefit is twofold: (i) in
the setting of Lemma 16 we can still show that $\mathop{\bf
Pr\/}_{\Phi,\beta}[g_{i}(\sigma)=1]\geq 1/2$, and more crucially (ii) to
determine $g_{i}(\sigma)$ we only need to reveal marked variables in clauses
where $i$ appears, allowing us to pick an appropriate subset of conditionally
independent marked variables using a greedy approach. With these ideas, we
show the following Lemma in Section A.6.

######  Lemma 10.

Consider a formula $\Phi=\Phi_{n,k,d}$ with
$k\geq\tfrac{2\log(dk)+\Theta(1)}{\lambda\log(1+\mathrm{e}^{-\beta})}$.

Then, there is a subset of the variables $R\subseteq[n]$ with $|R|\geq
n/(2kd)^{2}$ such that, with probability $1-\mathrm{e}^{-\Omega(n)}$ over the
choice of $\sigma\sim\mathop{\bf Pr\/}_{\Phi,\beta}$, it holds that
$\sum_{i\in R}g_{i}(\sigma)\geq|R|/3$.

###  3.2 Putting everything together

###### Proof of Theorem 1..

We prove the statement for the existence of the estimator, the impossibility
part is covered by Lemma 13 in Section A.1.

Let $B,\epsilon>0$ be arbitrary constants and let
$k\geq\tfrac{6.45\log(dk)+\Theta(1)}{\log(1+\mathrm{e}^{-B})}$ and
$|\beta^{*}|\leq B$. Since since $2/\lambda<6.45$, we have that both Lemmas 8
and 10 apply. From Lemma 7, we have that

$\mathop{\bf
E\/}_{\sigma}\left[\left(\phi_{1}(\beta^{*};\sigma)\right)^{2}\right]\leq
dkn,\mbox{ where the expectation is over $\sigma\sim\mathop{\bf
Pr\/}_{\Phi,\beta^{*}}$.}$ (11)

Recall also from $\eqref{equation:hard-sat 2nd derivative}$ that
$\phi_{2}(\beta;\sigma)=\tfrac{\mathrm{e}^{\beta}}{(\mathrm{e}^{\beta}+1)^{2}}\sum_{i\in[n]}e_{i}(\sigma)$
and, from Section 3.1, $e_{i}(\sigma)\geq g_{i}(\sigma)$. Using the crude
bound
$\tfrac{\mathrm{e}^{\beta}}{(\mathrm{e}^{\beta}+1)^{2}}\geq\tfrac{1}{\mathrm{e}^{2B}(\mathrm{e}^{2B}+1)^{2}}\triangleq\delta$
for $|\beta|\leq 2B$, we conclude from Lemma 10 that for all
$k\geq\tfrac{8\log d+\log k+\Theta(1)}{\log(1+\mathrm{e}^{-B})}$, it holds
that

$\mathop{\bf Pr\/}_{\Phi,\beta^{*}}\Big{[}\min_{\beta:|\beta|\leq
2B}\phi_{2}(\beta;\sigma)\leq\delta
n/(4kd)^{2}\Big{]}=\mathrm{e}^{-\Omega(n)}.$ (12)

Consider the event
$\mathcal{A}=\\{\sigma\in\Omega(\Phi):\,\big{|}\phi_{1}(\beta^{\star};\sigma)\big{|}\leq
2dk\sqrt{n/\epsilon},\ \min_{\beta:|\beta|\leq
2B}\phi_{2}(\beta;\sigma)\geq\delta n/(4kd)^{2}\\}$, and note that by a union
bound using (11) and (12) it holds that $\mathop{\bf
Pr\/}_{\Phi,\beta^{*}}[\mathcal{A}]\geq 1-\epsilon/2-o(1)\geq 1-\epsilon$ for
all sufficiently large $n$.

Fix arbitrary $\sigma\in\mathcal{A}$ and let $\widehat{\beta}_{\sigma}$ be an
MPL estimate corresponding to $\sigma$ so that
$\phi_{1}(\widehat{\beta}_{\sigma},\sigma)=0$. For $t\in[0,1]$, let
$\beta_{\sigma}(t)=t\widehat{\beta}_{\sigma}+(1-t)\beta^{\star}$ and
$h_{\sigma}(t)=(\widehat{\beta}_{\sigma}-\beta^{\star})\phi_{1}(\beta_{\sigma}(t);\sigma)$
for $t\in[0,1]$. Note that $h_{\sigma}(1)=0$ and
$h_{\sigma}^{\prime}(t)=(\widehat{\beta}_{\sigma}-\beta^{\star})^{2}\phi_{2}(\beta_{\sigma}(t);\sigma)$,
so

$-(\widehat{\beta}_{\sigma}-\beta^{\star})\phi_{1}(\beta^{\star};\sigma)=h_{n}(1)-h_{n}(0)=(\widehat{\beta}_{\sigma}-\beta^{\star})^{2}\int_{0}^{1}\phi_{2}(\beta_{\sigma}(t);\sigma)\,\mathrm{d}t.$

Note that $\phi_{2}(\beta;\sigma)\geq 0$ for every $\beta$ (cf. (9)), so we
obtain

$\big{|}\widehat{\beta}_{\sigma}-\beta^{\star}\big{|}\big{|}\phi_{1}(\beta^{\star};\sigma)\big{|}\geq(\widehat{\beta}_{\sigma}-\beta^{\star})^{2}\bigg{|}\int_{0}^{\min\\{1,B/|\widehat{\beta}_{\sigma}-\beta^{\star}|\\}}\phi_{2}(\beta_{\sigma}(t);\sigma)dt\bigg{|}.$
(13)

For $0\leq t\leq B/|\widehat{\beta}_{\sigma}-\beta^{\star}|$, we have that
$|\beta_{\sigma}(t)|\leq 2B$. Hence, since $\sigma\in\mathcal{A}$, (13) gives
that $2dk\sqrt{n/\epsilon}\geq\frac{\delta
n}{(4kd)^{2}}\min\\{|\widehat{\beta}_{\sigma}-\beta^{\star}|,B\\}$. Therefore,
for all sufficiently large $n$, we obtain that
$|\widehat{\beta}_{\sigma}-\beta^{\star}|\leq M/\sqrt{n}$, where
$M=\tfrac{(4kd)^{3}}{\delta\sqrt{\epsilon}}$, finishing the proof. ∎

##  4 Proof sketch for $H$-colorings

In this section, we discuss the proof of Theorem 3 and Corollaries 4 and 5.

We start with the main challenges for proving that the MPL estimate (4) is
consistent for $H$-coloring models that satisfy the $2$-Rainbow Condition (3).
As per the discussion in Section 2, we focus on bounding the second derivative
of the Pseudo-likelihood function $\phi$. We follow the notation of [BR21]
where a similar framework was introduced for studying the Rainbow Condition.

Consider a graph $G$ with vertex set $[n]$, $H$ with vertex set $[q]$ and
$\bm{\beta}^{*}=(\beta_{1},\ldots,\beta_{q})$. Assume w.l.o.g.888Since
$\sum_{i=1}^{q}c_{i}(\sigma)=n$, the parameter vector
$\bm{\beta}^{\star}=(\beta_{1},\ldots,\beta_{q})$ induces the same
distribution as $(\beta_{1}-\beta_{q},\ldots,\beta_{q}-\beta_{q})$. that
$\beta_{q}=0$, so we are interested in estimating the $q-1$ parameters
$\beta_{1},\ldots,\beta_{q-1}$ using a sample $\sigma\sim\mathop{\bf
Pr\/}_{G,H,\boldsymbol{\beta}}$, cf. (2). For a node $u\in[n]$ and $s\in[q]$,
define $Q_{\sigma}(u,s)$ to be $1$ if assigning the color $s$ to node $u$ and
keeping the colors of other nodes according to $\sigma$ results in a proper
coloring, and set $Q_{\sigma}(u,s)=0$ otherwise. For $v\in[n]$ and $r\in[q]$,
let us define $\theta_{\sigma}(v,\cdot)$ to be the distribution induced on $v$
conditioned on $\sigma_{-v}$, i.e., $\mathop{\bf
Pr\/}_{G,H,\bm{\beta}}(\mid\sigma_{-u})$. Namely, for a color $r\in[q]$ we
have
$\theta_{\sigma}(v,r)=\frac{\mathrm{e}^{\beta_{r}}Q_{\sigma}(v,r)}{\sum_{s=1}^{q}\mathrm{e}^{\beta_{s}}Q_{\sigma}(v,s)}$.
Then, the second derivative of $\phi$ at $\bm{\beta}$ can be computed as

$\displaystyle\phi_{2}(\boldsymbol{\beta};\sigma)=\sum_{v=1}^{n}\left(\mathrm{diag}(O_{\sigma}(v))-O_{\sigma}(v)O_{\sigma}(v)^{\top}\right)\,,$
(14)

where
$O_{\sigma}(v)=(\theta_{\sigma}(v,1),\ldots,\theta_{\sigma}(v,q-1))^{\top}$ is
a $(q-1)$-dimensional vector. Our goal is to show that
$\phi_{2}(\bm{\beta};\sigma)$ is strongly convex. The natural strategy would
be to show that each of the matrices in that sum has lower bounded
eigenvalues. However, in many interesting scenarios, these matrices are low
rank. Thus, our strategy will be to instead argue that for every vector in
$\mathbb{R}^{q-1}$, there are $\Omega(n)$ matrices in the sum such that this
vector does not belong in their nullspace. In particular, we establish the
following inequality, whose proof can be found in Section C.1.

######  Lemma 11.

Let $v\in[n]$ and $\sigma\in\Omega^{H}_{G}$ and suppose that
$Q_{\sigma}(v,q)=1$. Let
$\mathcal{I}(\sigma)=\\{r\in[q-1]:Q_{\sigma}(v,r)=1\\}.$ Then, for any
$\mathbf{x}=(x_{1},\ldots,x_{q-1})\in\mathbb{R}^{q-1}$, it holds that

$\mathbf{x}^{\top}\left(\mathrm{diag}(O_{\sigma}(v))-O_{\sigma}(v)O_{\sigma}(v)^{\top}\right)\mathbf{x}\geq\bigg{(}\frac{\min_{s\in[q]}\mathrm{e}^{\beta_{s}}}{\sum_{s=1}^{q}\mathrm{e}^{\beta_{s}}}\bigg{)}^{2}\sum_{r\in\mathcal{I}(\sigma)}x_{r}^{2}.$

Intuitively, the lemma asserts that the matrix in the sum of (14) preserves
all coordinates corresponding to colors $r$ with $Q(v,r)=1$, provided that
$Q(v,q)=1$. The 2-Rainbow Condition says that, with probability $1-o(1)$ over
the choice of $\sigma$, for an arbitrary color $r\in[q-1]$, it holds that
$u_{rq}(\sigma)=\Omega(n)$. This translates into
$Q_{\sigma}(v,r)Q_{\sigma}(v,q)=1$ for $\Omega(n)$ vertices $v\in[n]$ yielding
that $\bm{x}^{\top}\phi_{2}(\bm{\beta};\sigma)\bm{x}\geq K(\beta)x_{r}^{2}$
for all $\bm{x}\in\mathbb{R}^{q-1}$. Summing over $r\in[q-1]$ gives that
$\phi_{2}(\bm{\beta};\sigma)\succcurlyeq\Omega(n)\mathbf{I}_{q-1}$. Since this
holds with probability $1-o(1)$ over the choice of $\sigma$, the proof for
Theorem 3 can be completed analogously to the proof of Theorem 1 given
earlier, see Section C.1 for details.

###  4.1 Application to proper $q$-Colorings and permissive $H$-colorings

We now discuss how we can establish the 2-Rainbow Condition (see (3)) to
obtain Corollary 4 and Corollary 5. We actually focus on the case of the
proper $q$-coloring model, the idea for permissive $H$-coloring models is
similar.

Let $G=(V,E)$ be a graph of maximum degree $d$ with $V=[n]$, and assume that
$q\geq d+2$. For simplicity, let us fix $r\in[q-1]$ and denote for every node
$i\in[n]$, $e_{i}^{rq}(\sigma)=Q_{\sigma}(i,r)Q_{\sigma}(i,q)$. In words,
$e_{i}^{rq}(\sigma)$ is equal to 1 if assigning color $r$ or $q$ to node $i$
while keeping the other vertices colored as in $\sigma$ results in a proper
coloring; otherwise is 0. Note that
$u_{rq}(\sigma)=\sum_{i=1}^{n}e_{i}^{rq}(\sigma)$.

Our goal is to show that $u_{rq}(\sigma)=\Omega(n)$ for any color $r\in[q-1]$
with high probability over $\sigma.$ Analogously to the hard-SAT case, such
sums exhibit non-trivial correlations which are hard to analyze and
concentration results are unfortunately not known for such models. Our
solution will again be to construct a coupling, in order to “extract” as much
independence as possible. In particular, let $R\subseteq V$ be a maximal
subset of nodes that forms a 2-hop independent set of $G$, i.e., distinct
$v,w\in R$ have disjoint neighborhoods. We can pick $R$ greedily; using that
$G$ has maximum degree $d$, we have that $|R|\geq n/(d+1)^{2}$.

The key to establish the 2-Rainbow Condition for $q\geq d+2$ is to show the
following lemma, whose proof is given in Section C.2. The proof is quite
delicate and requires careful use of the assumption $q\geq d+2$.

######  Lemma 12.

Suppose $q\geq d+2$ and consider a color $r\in[q-1]$. Let $G$ be a graph of
maximum degree $d$ and $R=\\{v_{1},\ldots,v_{t}\\}$ be a subset of vertices
with mutually disjoint neighborhoods. Then, for any $k\in[t]$,

$\mathop{\bf
Pr\/}_{G,\boldsymbol{\beta^{\star}}}[e_{v_{k}}^{rq}(\sigma)=1|e_{v_{1}}^{rq}(\sigma)=x_{1},\ldots,e_{v_{k-1}}^{rq}(\sigma)=x_{k-1}]\geq\frac{1}{1+q^{d+1}\mathrm{e}^{\|\boldsymbol{\beta}^{\star}\|_{1}d}},$

for any values $x_{1},\ldots,x_{k-1}$ of the random variables
$e_{v_{1}}^{rq},\ldots,e_{v_{k-1}}^{rq}$ which are consistent with at least
one proper $q$-coloring of $G$.

Using the “conditional independence” property of Lemma 12, analogously to
Lemma 10, it is not hard to couple $\\{e_{v}^{rq}\\}_{v\in R}$ with
independent i.i.d. random variables $\\{\tau_{v}\\}_{v\in R}$ with
$\mathop{\bf Pr\/}[\tau_{v}=1]=\Omega(1)$. This yields that
$u_{rq}(\sigma)=\Omega(n)$ with probability $1-\mathrm{e}^{-\Omega(n)}$ over
$\sigma$, establishing therefore the 2-Rainbow Condition (cf. (3)). The proof
of Corollary 4 is given in Section C.2.

###  4.2 Negative Results for $H$-colorings

Dobrushin’s and Dobrushin-Shlosman’s (DS) condition are well-studied
properties for graphical models [Dob68] that are known to imply fast mixing
and hence efficient sampling [Hay06]. Furthermore, the work of [BCŠV18] showed
that, under the DS condition, there exists an efficient structure learning
algorithm for $H$-colorings. Perhaps surprisingly as we show in Theorem 2
neither of these conditions suffices even for identifiability for single
sample learning of $H$-colorings. In this Section, we discuss how to construct
such hard instances.

The instance that showcases the insufficiency of Dobrushin’s condition assumes
that $G$ is a star graph with node $v$ in the middle and leaves
$u_{1},...,u_{n}$ and $H$ contains $q+1$ vertices so that color 1 is allowed
to be adjacent to any other color and all other colors are only allowed to be
adjacent to 1. Hence, the only valid $H$-colorings are
$A=\\{\sigma:\sigma_{v}=1,\sigma_{u_{i}}>1,\forall i\in[n]\\}$ and
$B=\\{\sigma:\sigma_{v}>1,\sigma_{u_{i}}=1,\forall i\in[n]\\}$. Assume that
the Hamiltonian counts the appearances of color 1. It is not hard to show that
event $B$ has exponentially small probability of occuring (by picking $\beta$
sufficiently small) and $\mathop{\bf Var\/}(c_{1}(\sigma)|\sigma\in A)=0$.
Then, the law of total variance implies that $\mathop{\bf
Var\/}(c_{1}(\sigma))$ is of order $\exp(-n)$ for sufficiently small choices
of $\beta$. Hence, one can then show that the KL divergence between two models
with parameters $\beta_{1}$ and $\beta_{2}$ is exponentially small in $n$,
while $|\beta_{1}-\beta_{2}|$ is lower bounded by a constant. This implies
that parameter estimation is impossible. Moreover, one can verify that this
instance satisfies Dobrushin’s condition. For the formal statement, see
Theorem 20.

In a similar manner we can design an instance that satisfies DS condition but
where parameter estimation is not possible (Theorem 21). We pick $G$ to be a
cycle with $2n$ nodes $u_{1},\ldots,u_{2n}$ and $H$ contains $q=3$ vertices
and has edge set $E=\\{(1,2),(1,3)\\}$. Let
$A=\\{u_{1},u_{3},\ldots\\},B=\\{u_{2},u_{4},\ldots\\}$ be the even and odd
vertices. The valid $H$-colorings of $G$ will have $\sigma_{A}=1$ and
$\sigma_{B}\in\\{2,3\\}$ or $\sigma_{B}=1$ and $\sigma_{A}\in\\{2,3\\}$.
Suppose the Hamiltonian is of the form $\beta c_{1}(\sigma)$. Then, all valid
$H$-colorings have exactly $n$ vertices of color $1$. Thus $\mathop{\bf
Var\/}[c_{1}(\sigma)]=0$ for all $\beta$, which means that learning $\beta$ is
impossible. One can also verify that the DS condition holds true for this
instance.

## References

  * [ACO08] Dimitris Achlioptas and Amin Coja-Oghlan.  Algorithmic barriers from phase transitions.  In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 793–802. IEEE, 2008.
  * [AJK+22] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong.  Entropic independence: optimal mixing of down-up random walks.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1418–1430, 2022.
  * [AP03] Dimitris Achlioptas and Yuval Peres.  The threshold for random k-sat is 2k (ln 2-o (k)).  In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 223–231, 2003.
  * [BCC+22] Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda.  On mixing of markov chains: Coupling, spectral independence, and entropy factorization.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3670–3692. SIAM, 2022.
  * [BCŠV18] Antonio Blanca, Zongchen Chen, Daniel Štefankovič, and Eric Vigoda.  Structure learning of h-colorings.  In Algorithmic Learning Theory, pages 152–185. PMLR, 2018.
  * [BDNP21] Arnab Bhattacharyya, Rathin Desai, Sai Ganesh Nagarajan, and Ioannis Panageas.  Efficient statistics for sparse graphical models from truncated samples.  In International Conference on Artificial Intelligence and Statistics, pages 1450–1458. PMLR, 2021.
  * [Bec91] József Beck.  An algorithmic approach to the lovász local lemma. i.  Random Structures & Algorithms, 2(4):343–365, 1991.
  * [Bes74] Julian Besag.  Spatial interaction and the statistical analysis of lattice systems.  Journal of the Royal Statistical Society: Series B (Methodological), 36(2):192–225, 1974.
  * [BFFSZ19] Róbert Busa-Fekete, Dimitris Fotakis, Balázs Szörényi, and Manolis Zampetakis.  Optimal learning of mallows block model.  In Conference on Learning Theory, pages 529–532. PMLR, 2019.
  * [BH22] Guy Bresler and Brice Huang.  The algorithmic phase transition of random k-sat for low degree polynomials.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 298–309. IEEE, 2022.
  * [BM18] Bhaswar B Bhattacharya and Sumit Mukherjee.  Inference in Ising models.  2018\.
  * [BN18] Guy Bresler and Dheeraj Nagaraj.  Optimal single sample tests for structured versus unstructured network data.  In Conference On Learning Theory, pages 1657–1690. PMLR, 2018.
  * [BR21] Bhaswar B Bhattacharya and Kavita Ramanan.  Parameter estimation for undirected graphical models with hard constraints.  IEEE Transactions on Information Theory, 67(10):6790–6809, 2021\.
  * [Bre15] Guy Bresler.  Efficiently learning Ising models on arbitrary graphs.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 771–782, 2015.
  * [CD08] Mark Chavira and Adnan Darwiche.  On probabilistic inference by weighted model counting.  Artificial Intelligence, 172(6-7):772–799, 2008.
  * [CDDK22] Davin Choo, Yuval Dagan, Constantinos Daskalakis, and Anthimos Vardis Kandiros.  Learning and testing latent-tree Ising models efficiently.  arXiv preprint arXiv:2211.13291, 2022.
  * [CDM+19] Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle.  Improved bounds for randomly sampling colorings via linear programming.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2216–2234. SIAM, 2019.
  * [CE22] Yuansi Chen and Ronen Eldan.  Localization schemes: A framework for proving mixing bounds for markov chains.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 110–122. IEEE, 2022.
  * [CFM+14] Supratik Chakraborty, Daniel J. Fremont, Kuldeep S. Meel, Sanjit A. Seshia, and Moshe Y. Vardi.  Distribution-aware sampling and weighted model counting for sat.  In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014.
  * [CFMV15] Supratik Chakraborty, Dror Fried, Kuldeep S. Meel, and Moshe Y. Vardi.  From weighted to unweighted model counting.  In International Joint Conference on Artificial Intelligence, 2015\.
  * [CGŠV21] Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda.  Rapid mixing for colorings via spectral independence.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1548–1557. SIAM, 2021.
  * [Cha05] Sourav Chatterjee.  Concentration inequalities with exchangeable pairs.  Stanford University, 2005.
  * [Cha07] Sourav Chatterjee.  Estimation in spin glasses: A first step.  The Annals of Statistics, 35(5):1931–1946, 2007.
  * [CLV21] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1537–1550, 2021.
  * [CLV23] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Rapid mixing of glauber dynamics up to uniqueness via contraction.  SIAM Journal on Computing, 52(1):196–237, 2023.
  * [CMM23] Zongchen Chen, Nitya Mani, and Ankur Moitra.  From algorithms to connectivity and back: finding a giant component in random k-sat.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3437–3470. SIAM, 2023.
  * [CO10] Amin Coja-Oghlan.  A better algorithm for random k-sat.  SIAM Journal on Computing, 39(7):2823–2864, 2010.
  * [DDDJ19] Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Siddhartha Jayanti.  Learning from weakly dependent data under dobrushin’s condition.  In Conference on Learning Theory, pages 914–928. PMLR, 2019.
  * [DDDVK20] Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis Kandiros.  Estimating Ising models from one sample.  arXiv e-prints, pages arXiv–2004, 2020.
  * [DDK19] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath.  Testing Ising models.  IEEE Transactions on Information Theory, 65(11):6829–6852, 2019\.
  * [DDP19] Constantinos Daskalakis, Nishanth Dikkala, and Ioannis Panageas.  Regression from dependent observations.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 881–889, 2019.
  * [DG00] Martin Dyer and Catherine Greenhill.  The complexity of counting graph homomorphisms.  Random Structures & Algorithms, 17(3-4):260–289, 2000.
  * [DGGJ04] Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, and Mark Jerrum.  The relative complexity of approximate counting problems.  Algorithmica, 38:471–500, 2004.
  * [DGTZ18] Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis.  Efficient statistics, in high dimensions, from truncated samples.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 639–649. IEEE, 2018.
  * [DGTZ19] Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis.  Computationally and statistically efficient truncated regression.  In Conference on Learning Theory, pages 955–960. PMLR, 2019.
  * [DKSS21] Ilias Diakonikolas, Daniel M Kane, Alistair Stewart, and Yuxin Sun.  Outlier-robust learning of Ising models under dobrushin’s condition.  In Conference on Learning Theory, pages 1645–1682. PMLR, 2021.
  * [DNS23] Anindya De, Shivam Nadimpalli, and Rocco A Servedio.  Testing convex truncation.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4050–4082. SIAM, 2023.
  * [Dob68] PL Dobruschin.  The description of a random field by means of conditional probabilities and conditions of its regularity.  Theory of Probability & Its Applications, 13(2):197–224, 1968\.
  * [EAMS22] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke.  Sampling from the sherrington-kirkpatrick gibbs measure via algorithmic stochastic localization.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 323–334. IEEE, 2022.
  * [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\.
  * [FGYZ21] Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang.  Fast sampling and counting k-sat solutions in the local lemma regime.  Journal of the ACM (JACM), 68(6):1–42, 2021.
  * [FHY21] Weiming Feng, Kun He, and Yitong Yin.  Sampling constraint satisfaction solutions in the local lemma regime.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1565–1578, 2021.
  * [FK16] Alan Frieze and Michal Karoński.  Introduction to random graphs.  Cambridge University Press, 2016.
  * [FKKT21] Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos.  Efficient algorithms for learning from coarse labels.  In Conference on Learning Theory, pages 2060–2079. PMLR, 2021.
  * [FKT20] Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos.  Efficient parameter estimation of truncated boolean product distributions.  In Conference on Learning Theory, pages 1586–1600. PMLR, 2020.
  * [FKT22] Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos.  Perfect sampling from pairwise comparisons.  arXiv preprint arXiv:2211.12868, 2022.
  * [FV07] Alan Frieze and Eric Vigoda.  A survey on the use of markov chains to randomly sample colourings.  Oxford Lecture Series in Mathematics and its Applications, 34:53, 2007.
  * [Gao08] Yong Gao.  Phase transitions and complexity of weighted satisfiability and other intractable parameterized problems.  In AAAI, pages 265–270, 2008.
  * [GGGHP22] Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Andrés Herrera-Poyatos.  Fast sampling of satisfying assignments from random $k$-sat.  arXiv preprint arXiv:2206.15308, 2022.
  * [GGGY21] Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan Yang.  Counting solutions to random cnf formulas.  SIAM Journal on Computing, 50(6):1701–1738, 2021.
  * [GGJ16] Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum.  Approximately counting h-colorings is $\backslash$#bis-hard.  SIAM Journal on Computing, 45(3):680–711, 2016.
  * [GJL19] Heng Guo, Mark Jerrum, and Jingcheng Liu.  Uniform sampling through the lovász local lemma.  Journal of the ACM (JACM), 66(3):1–31, 2019.
  * [GKP02] Leslie Ann Goldberg, Steven Kelk, and Mike Paterson.  The complexity of choosing an h-colouring (nearly) uniformly at random.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 53–62, 2002.
  * [GLP18] Reza Gheissari, Eyal Lubetzky, and Yuval Peres.  Concentration inequalities for polynomials of contracting Ising models.  Electronic Communications in Probability, 23:1–12, 2018.
  * [GM20] Promit Ghosal and Sumit Mukherjee.  Joint estimation of parameters in Ising model.  2020\.
  * [GSS08] Carla Gomes, Ashish Sabharwal, and Bart Selman.  Model counting.  Frontiers in Artificial Intelligence and Applications, 185, 01 2008\.
  * [GŠV15] Andreas Galanis, Daniel Štefankovič, and Eric Vigoda.  Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region.  Journal of the ACM (JACM), 62(6):1–60, 2015.
  * [GŠV16] Andreas Galanis, Daniel Štefankovič, and Eric Vigoda.  Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models.  Combinatorics, Probability and Computing, 25(4):500–559, 2016.
  * [Hay06] Thomas P Hayes.  A simple condition implying rapid mixing of single-site dynamics on spin systems.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 39–46. IEEE, 2006.
  * [HKM17] Linus Hamilton, Frederic Koehler, and Ankur Moitra.  Information theoretic properties of markov random fields, and their algorithmic applications.  Advances in Neural Information Processing Systems, 30, 2017.
  * [HN90] Pavol Hell and Jaroslav Nešetřil.  On the complexity of h-coloring.  Journal of Combinatorial Theory, Series B, 48(1):92–110, 1990.
  * [HN23] William He and Shivam Nadimpalli.  Testing junta truncation.  arXiv preprint arXiv:2308.13992, 2023.
  * [HWY23a] Kun He, Chunyang Wang, and Yitong Yin.  Deterministic counting Lovász local lemma beyond linear programming.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3388–3425, 2023.
  * [HWY23b] Kun He, Kewen Wu, and Kuan Yang.  Improved bounds for sampling solutions of random cnf formulas.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3330–3361. SIAM, 2023.
  * [Jer95] Mark Jerrum.  A very simple algorithm for estimating the number of k-colorings of a low-degree graph.  Random Structures & Algorithms, 7(2):157–165, 1995.
  * [JPV22] Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong.  Towards the sampling lovász local lemma.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 173–183. IEEE, 2022.
  * [KDD+21] Vardis Kandiros, Yuval Dagan, Nishanth Dikkala, Surbhi Goel, and Constantinos Daskalakis.  Statistical estimation from dependent data.  In International Conference on Machine Learning, pages 5269–5278. PMLR, 2021.
  * [KLR22] Frederic Koehler, Holden Lee, and Andrej Risteski.  Sampling approximately low-rank Ising models: MCMC meets variational methods.  In Conference on Learning Theory, pages 4945–4988. PMLR, 2022.
  * [KM17] Adam Klivans and Raghu Meka.  Learning graphical models using multiplicative weights.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 343–354. IEEE, 2017.
  * [KSZ22] Alkis Kalavasis, Konstantinos Stavropoulos, and Emmanouil Zampetakis.  Learning and covering sums of independent random variables with unbounded support.  Advances in Neural Information Processing Systems, 35:25185–25197, 2022.
  * [KTZ19] Vasilis Kontonis, Christos Tzamos, and Manolis Zampetakis.  Efficient truncated statistics with unknown truncation.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1578–1595. IEEE, 2019.
  * [MHBM21] Somabha Mukherjee, Sagnik Halder, Bhaswar B Bhattacharya, and George Michailidis.  High dimensional logistic regression under network dependence.  arXiv preprint arXiv:2110.03200, 2021.
  * [Moi19] Ankur Moitra.  Approximate counting, the lovász local lemma, and inference in graphical models.  Journal of the ACM (JACM), 66(2):1–25, 2019.
  * [Mol02] Michael Molloy.  The glauber dynamics on colourings of a graph with high girth and maximum degree.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 91–98, 2002.
  * [MS06] Andrea Montanari and Devavrat Shah.  Counting good truth assignments of random k-sat formulae.  arXiv preprint cs/0607073, 2006.
  * [MSB20] Somabha Mukherjee, Jaesung Son, and Bhaswar B Bhattacharya.  Estimation in tensor Ising models.  arXiv preprint arXiv:2008.12882, 2020.
  * [MT10] Robin A Moser and Gábor Tardos.  A constructive proof of the general lovász local lemma.  Journal of the ACM (JACM), 57(2):1–15, 2010.
  * [MZ96] Rémi Monasson and Riccardo Zecchina.  Entropy of the k-satisfiability problem.  Physical review letters, 76(21):3881, 1996.
  * [NP20] Sai Ganesh Nagarajan and Ioannis Panageas.  On the analysis of em for truncated mixtures of two gaussians.  In Algorithmic Learning Theory, pages 634–659. PMLR, 2020.
  * [Ple21] Orestis Plevrakis.  Learning from censored and dependent data: The case of linear dynamics.  In Conference on Learning Theory, pages 3771–3787. PMLR, 2021.
  * [SBK05] Tian Sang, Paul Beame, and Henry A. Kautz.  Performing bayesian inference by weighted model counting.  In AAAI Conference on Artificial Intelligence, 2005.
  * [SS12] Allan Sly and Nike Sun.  The computational hardness of counting in two-spin models on d-regular graphs.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 361–369. IEEE, 2012.
  * [Tal01] Michel Talagrand.  The high temperature case for the random k-sat problem.  Probability Theory and Related Fields, 119(2):187–212, 2001.
  * [Vig00] Eric Vigoda.  Improved bounds for sampling colorings.  Journal of Mathematical Physics, 41(3):1555–1569, 2000.
  * [VMLC16] Marc Vuffray, Sidhant Misra, Andrey Lokhov, and Michael Chertkov.  Interaction screening: Efficient and sample-optimal learning of Ising models.  Advances in neural information processing systems, 29, 2016.

##  Appendix A Remaining proofs for the Hard-SAT Model

###  A.1 Proof of non-identifiability

In this section, we establish the impossibility part of Theorem 1. We
construct instances $\Phi$ with a single satisfying assignment, and therefore
for any $\beta$, the probability distribution $\mathop{\bf Pr\/}_{\Phi,\beta}$
is a point mass on the unique satisfying assignment. The following lemma shows
the construction.

######  Lemma 13 (Non-Identifiable Hard-SAT).

Let $k,d$ be integers with $d=(k+1)2^{k-1}$. There exists a sequence of
formulae $(\Phi_{n,k,d})$ such that for each $n$ $\Phi_{n,k,d}$ has a unique
satisfying assignment.

###### Proof.

Let us consider $n$ variables $x_{1},\ldots,x_{n}$. For $i\in[n]$, define
$f(i)=i\mod(n+1)$ and let

$\Psi_{i}\triangleq(x_{f(i+1)}\lor\ldots\lor
x_{f(i+k-1)})\land(\overline{x}_{f(i+1)}\lor\ldots\lor
x_{f(i+k-1)})\ldots\land(\overline{x}_{f(i+1)}\lor\ldots\lor\overline{x}_{f(i+k-1)})\,.$

Namely, $\Psi_{i}$ contains $2^{k-1}$ clauses, corresponding to all possible
combinations of the set of $k-1$ variables $x_{f(i+1)},\ldots x_{f(i+k-1)}$.
Let $\Psi_{i}^{\prime}$ be the formula obtained by $\Psi_{i}$ by appending the
literal $x_{i}$ to each clause. We consider the formula
$\Phi=\land^{n}_{i=1}\Psi_{i}^{\prime}\cdots\land\Psi_{n}^{\prime}$ obtained
by taking together all the $\Psi_{i}^{\prime}$ for $i\in[n]$. Then the only
assignment that satisfies $\Phi$ is by setting all $n$ variables equal to
True. Moreover, it holds that any clause has size $k$ and the degree of any
variable is $d=(k+1)2^{k-1}$. ∎

###  A.2 Derivatives of Pseudo-Likelihood Objective for Hard-SAT

Our algorithm will rely on minimizing the negative pseudo-likelihood (NPL)
objective $\phi(\cdot;\sigma)$, as defined in (4). In this section, we
explicitly compute the first and second derivatives of this function.

######  Lemma 14 (Derivatives of NPL).

Consider a formula $\Phi=\Phi_{n,k,d}$ with $\Omega(\Phi)\neq\emptyset$, and
let $\sigma\in\Omega(\Phi)$. Let $\phi(\beta;\sigma_{1})$ be the negative log-
pseudo-likelihood of the Hard-SAT distribution defined from (6). For a
variable $i\in[n]$, denote by $x_{i}$ the r.v. sampled from $\mathop{\bf
Pr\/}(\cdot\mid\sigma_{-i})$. Then,

$\phi_{1}(\beta;\sigma)=\sum_{i\in[n]}\left(\mathop{\bf
E\/}_{x_{i}}[C(x_{i},\sigma_{-i})]-C(\sigma)\right),\quad\mbox{ and
}\quad\phi_{2}(\beta;\sigma)=\sum_{i\in[n]}\mathop{\bf
Var\/}_{x_{i}}[C(x_{i},\sigma_{-i})].$ (15)

###### Proof.

Recall that $\mathop{\bf
Pr\/}_{\Phi,\beta}[\sigma]=\frac{\exp(\beta\sum_{j\in[m]}C(\sigma))1\\{\sigma\in\Omega\\}}{Z(\beta)}$.
The first step is to study, for any $i\in[n]$, the conditional probability of
the value of a single variable $\sigma_{i}$ given the rest $\sigma_{-i}$.

Recall that $\mathcal{F}(\sigma)\subseteq[n]$ is the set of flippable
variables under $\sigma$ and that

$\phi(\beta;\sigma)=-\sum_{i\in[n]}\log\mathop{\bf
Pr\/}_{\Phi,\beta}[\sigma_{i}|\sigma_{-i}]=\sum_{i\in\mathcal{F}(\sigma)}\left(\log\left(e^{\beta
C(1,\sigma_{-i})}+e^{\beta C(0,\sigma_{-i})}\right)-\beta
C(\sigma_{i},\sigma_{-i})\right)\,.$ (6)

Computing the derivative of $\phi$ with respect to $\beta$

$\displaystyle\phi_{1}(\beta;\sigma)$
$\displaystyle=\sum_{i\in\mathcal{F}(\sigma)}\left(\frac{C(1,\sigma_{-i})e^{\beta
S(1,\sigma_{-i})}+C(0,\sigma_{-i})e^{\beta S(0,\sigma_{-i})})}{e^{\beta
C(1,\sigma_{-i})}+e^{\beta C(0,\sigma_{-i})}}-C(\sigma)\right)$ (16)
$\displaystyle=\sum_{i\in[n]}\left(\mathop{\bf
E\/}_{x_{i}}[C(x_{i},\sigma_{-i})]-C(\sigma)\right),$

which shows the expression for $\phi_{1}(\beta;\sigma)$ given in (15).
Moreover, differentiating (16) with respect to $\beta$ gives the expression
for $\phi_{2}(\beta;\sigma)$ given in (15). ∎

###  A.3 Expectation of 1st Hard-SAT Derivative

We next give the full proof of Lemma 7, which we restate here for convenience.
See 7

###### Proof.

Let us define

$F(\sigma,\sigma^{\prime})=C(\sigma)-C(\sigma^{\prime})\,,~{}~{}~{}\sigma,\sigma^{\prime}\in\\{0,1\\}^{n}\,,$

where $C(\sigma)$ is the number of variables set to true in $\sigma$. Consider
an assignment $\sigma\in\\{0,1\\}^{n}$ and choose a coordinate $I\in[n]$
uniformly at random and replace the $I$-th coordinate of $\sigma$ by a random
sample drawn from the conditional distribution $\mathop{\bf
Pr\/}_{\Phi,\beta}(\cdot\mid\sigma_{-i})$. Let $\sigma^{(I)}$ be the resulting
assignment. Moreover, consider the function $f$ defined by

$f(\sigma)=\mathop{\bf E\/}_{I}[F(\sigma,\sigma^{(I)})|\sigma]=\mathop{\bf
E\/}_{I}[C(\sigma)-C(\sigma^{(I)})|\sigma],$

Denoting by $x_{i}\sim\mathop{\bf Pr\/}_{\Phi,\beta}(\cdot\mid\sigma_{-i})$,
we can rewrite this as

$f(\sigma)=\frac{1}{n}\sum_{i\in[n]}\big{(}C(\sigma)-\mathop{\bf
E\/}_{x_{i}}[C(x_{i},\sigma_{-i})|\sigma_{-i}]\big{)}=-\frac{1}{n}\phi_{1}(\beta;\sigma),$
(17)

where the second equality follows from the expression for $\phi_{1}$ given in
(15). Notice that

$f(\sigma)=\frac{1}{n}\sum_{i\in[n]}\sigma_{i}-\mathop{\bf
E\/}_{x_{i}}[x_{i}]\,,$

We observe that $(\sigma,\sigma^{(I)})$ is an exchangeable pair, i.e., we have
that

$\mathop{\bf E\/}_{\sigma}[f(\sigma)^{2}]=\mathop{\bf
E\/}_{\sigma}[f(\sigma)f(\sigma)]=\mathop{\bf
E\/}_{\sigma,I}[f(\sigma)F(\sigma,\sigma^{(I)})]=\mathop{\bf
E\/}_{\sigma,I}[f(\sigma^{(I)})F(\sigma^{(I)},\sigma)]\,.$

Since $F$ is anti-symmetric, i.e.,
$F(\sigma,\sigma^{\prime})=-F(\sigma^{\prime},\sigma)$, we have that

$\mathop{\bf E\/}_{\sigma}[f(\sigma)^{2}]=\frac{1}{2}\mathop{\bf
E\/}_{\sigma,I}[(f(\sigma)-f(\sigma^{(I)}))F(\sigma,\sigma^{(I)})]\,.$ (18)

Combining (17) and (18), we obtain that

$\frac{1}{n^{2}}\mathop{\bf
E\/}_{\sigma}\left[\left(\phi_{1}(\beta;\sigma)\right)^{2}\right]=\frac{1}{2}\mathop{\bf
E\/}_{\sigma,I}[(f(\sigma)-f(\sigma^{(I)}))(C(\sigma)-C(\sigma^{(I)})].$ (8)

Observe now that, for any $i\in[n]$, $|C(\sigma)-C(\sigma^{(i)})|\leq 1$ and
$|f(\sigma)-f(\sigma^{(i)})|\leq kd/n$. The former inequality is immediate,
while for the latter it suffices to note that, for $\tau=\sigma^{(i)}$ and a
variable $j\in[n]$, the quantities $S_{j}=C(\sigma)-C(\sigma^{(j)})$ and
$T_{j}=C(\tau)-C(\tau^{(j)})$ can only differ if the variable $j$ is in some
clause with variable $i$). This yields that the right-hand side is $O(1/n)$,
implying the Lemma. ∎

###  A.4 Marking

We next give the proof of Lemma 8. See 8

###### Proof.

We choose each variable to be marked or unmarked with probability $1/2$
independently. Consider the $m$ bad events, one for each clause $c$, that $c$
does not have enough marked or unmarked variables. Then, by the Chernoff-
Hoeffding Theorem, we have that

$\mathop{\bf Pr\/}[c\text{ is bad}]\leq 2e^{-k\mathrm{KL}(\lambda\parallel
1/2)}=2^{1-k\mathrm{KL}(\lambda\parallel 1/2)\log_{2}e},$

where recall that $\mathrm{KL}(p\parallel
q)=p\ln\frac{p}{q}+(1-p)\ln\frac{1-p}{1-q}$. By the Lovász Local Lemma, if

$4e(kd+1)\leq 2^{k\mathrm{KL}(\lambda\parallel 1/2)\log_{2}e},$

then there exists an assignment of marked and unmarked variables that
satisfies the constraints. By taking logs in the above inequality and since
$\lambda$ satisfies $\mathrm{KL}(\lambda\parallel 1/2)\log_{2}e=\lambda/2$,
the result follows. ∎

###  A.5 Probability lower bounds using the LLL

In this section, we prove Lemma 9; in fact, we will show a slight
strengthening of it, see Lemma 16 below, which will be more suitable for the
upcoming proof of Lemma 10 in Section A.6.

We begin by stating the following version of the LLL for $k$-SAT formulas.

######  Lemma 15 ([GJL19]).

Let $\Phi$ be a SAT formula with set of variables $V$ and set of clauses
$\mathcal{C}$. For $\beta\in\mathbb{R}$, let $\mu_{\beta}$ be the product
distribution on $\\{0,1\\}^{V}$ where each variable of $\Phi$ is set to 1
independently with probability
$\tfrac{\mathrm{e}^{\beta}}{1+\mathrm{e}^{\beta}}$.

Suppose there is a function $x:\mathcal{C}\to(0,1)$ such that for all
$c\in\mathcal{C}$ we have that

$\mathop{\bf Pr\/}_{\mu_{\beta}}[c\textnormal{ is unsatisfied}]\leq
x(c)\prod_{b\in\Gamma(c)}(1-x(b))\,.$

Then, $\Phi$ has at least one satisfying assignment. Moreover, suppose that
$E$ is an event that is completely determined by the assignment of some set
$S$ of the variables, and let $\Gamma(E)$ denote all the clauses that contain
any of the variables in S. Then, $\mathop{\bf
Pr\/}_{\Phi,\beta}[E]\leq\mathop{\bf
Pr\/}_{\mu_{\beta}}[E]\prod_{b\in\Gamma(E)}(1-x(b))^{-1}$.

The above Lemma follows from Lemma 27 of [GJL19] by setting $S=m$ and by
picking the bad event to be the event that clause $i$ is unsatisfied. We are
now ready to prove the following strengthening of Lemma 9.

######  Lemma 16.

Fix a formula $\Phi$ with max degree $d$ and set of variables corresponding to
the set $[n]$, where every clause has at least $\lambda k$ and at most $k$
variables. Suppose that
$k\geq\tfrac{2\log(dk)+\Theta(1)}{\lambda\log(1+\mathrm{e}^{-\beta})}$ and
consider a marking $\mathcal{M}:[n]\mapsto\\{\text{marked, unmarked}\\}$ of
the variables.

For $i\in[n]$ and $\sigma\sim\mathop{\bf Pr\/}_{\Phi,\beta}$, suppose that all
clauses that contain $x_{i}$ have at least $\lambda k$ marked and $\lambda k$
unmarked variables. Let $g_{i}(\sigma)$ be the indicator of the event that
every clause $c$ containing $i$ is satisfied in $\sigma$ by a marked variable
other than $i$. Then $\mathop{\bf Pr\/}_{\Phi,\beta}[g_{i}(\sigma)=1]\geq
1/2$.

###### Proof of Lemmas 9 and 16..

We are going to use Lemma 15 in order to upper bound $\mathop{\bf
Pr\/}_{\Phi,\beta}[g_{i}(\sigma)=0]$. For every clause $c$, we set
$x(c)=\frac{1}{D+1}$ with $D=d^{2}k$ and check the condition of the asymmetric
LLL, i.e., that $\mathop{\bf Pr\/}_{\mu_{\beta}}[c\textnormal{ is
unsatisfied}]\leq x(c)\prod_{b\in\Gamma(c)}(1-x(b))$, where $\mu_{\beta}$ is
the product distribution where each variable is set to 1 independently with
probability $\tfrac{\mathrm{e}^{\beta}}{1+\mathrm{e}^{\beta}}$. For
$k\geq\frac{2\log(dk)+\Theta(1)}{\lambda\log(1+\mathrm{e}^{-\beta})}$, we have

$\mathrm{e}(d^{2}k+1)\leq(1+\mathrm{e}^{-\beta})^{\lambda k}\mbox{ and hence
}\bigg{(}\frac{\mathrm{e}^{\beta}}{1+\mathrm{e}^{\beta}}\bigg{)}^{\lambda
k}\leq\frac{1}{D+1}\left(\frac{D}{1+D}\right)^{D},$ (19)

which establishes the LLL condition since $|\Gamma(c)|\leq D=d^{2}k$.

We can apply now Lemma 15. Namely, we first have the bound

$\mathop{\bf Pr\/}_{\mu_{\beta}}\big{[}g_{i}(\sigma)=0\big{]}=\mathop{\bf
Pr\/}_{\mu_{\beta}}[\exists~{}\text{clause containing $i$ not satisfied by a
marked variable}]\leq
d\cdot\left(\frac{\mathrm{e}^{\beta}}{1+\mathrm{e}^{\beta}}\right)^{\lambda
k-1}.$

Now since the event $g_{i}(\sigma)=0$ is completely determined by $\leq dk$
variables (those that share a variables with $i$), and we have at most
$D=d^{2}k$ clauses that contain such a variable, we get that

$\mathop{\bf Pr\/}_{\Phi,\beta}\big{[}g_{i}(\sigma)=0\big{]}\leq\mathop{\bf
Pr\/}_{\mu_{\beta}}\big{[}g_{i}(\sigma)=0\big{]}\left(1-\frac{1}{D+1}\right)^{-D}\leq\mathrm{e}d\left(\frac{\mathrm{e}^{\beta}}{1+\mathrm{e}^{\beta}}\right)^{\lambda
k-1},$

using that $(1-\tfrac{1}{D+1})^{-D}\leq\mathrm{e}$. For $k\geq\frac{\log
d+\Theta(1)}{\lambda\log(1+\mathrm{e}^{-\beta})}$, we therefore have that
$\mathop{\bf Pr\/}_{\Phi,\beta}[g_{i}(\sigma)=0]\leq 1/2$, implying the
desired result. ∎

###  A.6 Proofs for the coupling

We will use the following lemma.

######  Lemma 17 (see, e.g., [FK16, Section 23.9]).

Suppose that $\\{Y_{i}\\}_{i\in[n]}$ are independent random variables and that
$\\{X_{i}\\}_{i\in[n]}$ are random variables so that for any real $t$ and
$i\in[n]$, it holds that $\mathop{\bf Pr\/}[X_{i}\geq t\mid X_{1},\ldots
X_{i-1}]\geq\mathop{\bf Pr\/}[Y_{i}\geq t]$. Then, for any real $t$,

$\mathop{\bf Pr\/}[X_{1}+\cdots+X_{n}\geq t]\geq\mathop{\bf
Pr\/}[Y_{1}+\cdots+Y_{n}\geq t].$

We are now ready to prove Lemma 10, which we restate here for convenience. See
10

###### Proof.

Consider a marking of the variables
$\mathcal{M}:[n]\rightarrow\\{\text{marked, unmarked}\\}$ such that every
clause that at least $\lambda k$ marked and $\lambda k$ unmarked variables
whose existence is guaranteed by Lemma 8. Consider the graph $G$ whose
vertices are the variables of $\Phi$, where two vertices are adjacent if the
corresponding variables appear in the same clause of $\Phi$. Note that $G$ has
maximum degree $dk$. Let $R=\\{i_{1},\ldots,i_{r}\\}$ be a maximal subset of
the vertices of $G$ whose neighbourhoods are mutually disjoint; note that the
greedy algorithm to pick such a subset $R$ (by picking an arbitrary vertex
into $R$, deleting its 2-hop neighbors, and recursing) implies that $r\geq
n/(1+kd)^{2}\geq n/(2kd)^{2}$.

Let $\sigma\sim\mathop{\bf Pr\/}_{\Phi,\beta}$. We will show that for
$t=1,\ldots,r$, it holds that

$\mathop{\bf
Pr\/}_{\Phi,\beta}[g_{i_{t}}(\sigma)=1|g_{i_{1}}(\sigma),\ldots,g_{i_{t-1}}(\sigma)]\geq
1/2.$ (20)

By Lemma 17 and standard Chernoff bounds, we obtain that $\sum_{i\in
R}g_{i}(\sigma)\geq|R|/3$ with probability $1-\mathrm{e}^{-\Omega(n)}$ over
the choice of $\sigma\sim\mathop{\bf Pr\/}_{\Phi,\beta}$.

To prove (20), consider arbitrary $t=1,\ldots,r-1$. For $i\in[n]$, let
$\mathcal{M}_{i}$ denote the marked variables that are neighbors of $i$, and
let $U_{t}=\cup^{t-1}_{j=1}\mathcal{M}_{i_{j}}$ be the set of marked variables
that are neighbors of the variables $i_{1},\ldots,i_{t-1}$. Let us condition
on $\sigma_{U_{t-1}}=\tau$, i.e., that the restriction of the assignment
$\sigma$ on $U_{t-1}$ is given by $\tau$. Let $\Phi_{\tau}$ be the formula
obtained by $\Phi$ by setting the variables in $U_{t-1}$ according to $\tau$,
i.e., removing literals that are not satisfied by the partial assignment
$\tau$ and removing clauses that are already satisfied by $\tau$. Note that
every every clause of $\Phi$ has at least $\lambda^{*}k$ unmarked variables by
the marking $\mathcal{M}$, and $\tau$ only sets marked variables (the set
$U_{t}$), so every clause in $\Phi_{\tau}$ has at least $\lambda^{*}k$
variables.

By the law of total probability and the fact that
$g_{i_{1}},\ldots,g_{i_{t-1}}$ are deterministic functions of
$\sigma_{U_{t}}$, we have that

$\displaystyle\mathop{\bf Pr\/}[g_{i_{t}}=1|g_{i_{1}},\ldots,g_{i_{t-1}}]$
$\displaystyle=\sum_{\tau\in\\{0,1\\}^{U_{t}}}\mathop{\bf
Pr\/}[\sigma_{U_{t}}=\tau|g_{i_{1}},\ldots,g_{i_{t-1}}]\mathop{\bf
Pr\/}[g_{i_{t}}=1|\sigma_{U_{t}}=\tau].$ (21)

Conditioning on $\sigma_{U_{t}}=\tau$ results in a formula with at least
$\lambda^{*}k$ variables in every clause. We have also picked $i_{t}$ so that
it does not have any common neighbors with $i_{1},\ldots,i_{t-1}$. Thus, the
marked neighbors $\mathcal{M}_{i_{t}}$ of $i_{t-1}$ have not been set by the
conditioning $\sigma_{U_{t}}=\tau$. Hence, by Lemma 16, we have that

$\mathop{\bf Pr\/}_{\Phi,\beta}[g_{i_{k+1}}(\sigma)=1|\sigma_{U_{k}}=\tau]\geq
1/2\mbox{ for all $\tau\in\\{0,1\\}^{U_{t}}$}.$

Plugging this bound into (21) gives (20) as wanted, completing therefore the
proof of the Lemma. ∎

##  Appendix B Insufficient conditions for parameter estimation for
$H$-colorings

In this section, we show that various natural well-studied conditions in the
graphical models literature do not suffice for parameter estimation for
$H$-colorings.

We will use the following lemma, which is standard for exponential families
[BFFSZ19, KSZ22].

######  Lemma 18.

Let $P_{\boldsymbol{\beta}}$ denote a distribution with parameter
$\boldsymbol{\beta}\in\mathbb{R}^{q}$ and density proportional to
$e^{\langle\boldsymbol{\beta},\boldsymbol{H}(\sigma)\rangle}$ for
$\sigma\in\Omega$, where $\boldsymbol{H}:\Omega\to\mathbb{R}^{q}$. Then, for
$\boldsymbol{\beta},\boldsymbol{\gamma}\in\mathbb{R}^{q}$, there is
$\xi\in(0,1)$ such that

$\mathrm{KL}(P_{\boldsymbol{\beta}}\parallel
P_{\boldsymbol{\gamma}})=\frac{1}{2}\mathop{\bf Var\/}_{\sigma\sim
P_{\boldsymbol{\beta}+\xi(\boldsymbol{\gamma}-\boldsymbol{\beta})}}\left[\langle\boldsymbol{\gamma}-\boldsymbol{\beta},\boldsymbol{H}(\sigma)\rangle\right].$

###### Proof.

Consider the free energy function $F:\mathbb{R}^{q}\to\mathbb{R}$ with
$F(\boldsymbol{\beta})=\log\left(\sum_{\sigma\in\Omega}e^{\langle\boldsymbol{\beta},\boldsymbol{H}(\sigma)\rangle}\right)$.
Define the function $g:[0,1]\to\mathbb{R}$ with
$g(t)=F(\boldsymbol{\beta}+t(\boldsymbol{\gamma}-\boldsymbol{\beta}))$. Then,
we have that

$\displaystyle
g^{\prime}(t)=\frac{\sum_{\sigma\in\Omega}\langle\boldsymbol{\gamma}-\boldsymbol{\beta},\boldsymbol{H}(\sigma)\rangle
e^{\langle\boldsymbol{\beta}+t(\boldsymbol{\gamma}-\boldsymbol{\beta}),\boldsymbol{H}(\sigma)\rangle}}{\sum_{\sigma\in\Omega}e^{\langle\boldsymbol{\beta}+t(\boldsymbol{\gamma}-\boldsymbol{\beta}),\boldsymbol{H}(\sigma)\rangle}}=\mathop{\bf
E\/}_{\sigma\sim
P_{\boldsymbol{\beta}+t(\boldsymbol{\gamma}-\boldsymbol{\beta})}}\left[\langle\boldsymbol{\gamma}-\boldsymbol{\beta},\boldsymbol{H}(\sigma)\rangle\right]\,.$
$\displaystyle g^{\prime\prime}(t)=\mathop{\bf Var\/}_{\sigma\sim
P_{\boldsymbol{\beta}+t(\boldsymbol{\gamma}-\boldsymbol{\beta})}}\left[\langle\boldsymbol{\gamma}-\boldsymbol{\beta},\boldsymbol{H}(\sigma)\rangle\right]\,.$

By Taylor’s theorem, there exists $\xi\in(0,1)$ such that
$g(1)-g(0)-g^{\prime}(0)=\frac{g^{\prime\prime}(\xi)}{2}$. Therefore

$\displaystyle\mathrm{KL}(P_{\boldsymbol{\beta}}\parallel
P_{\boldsymbol{\gamma}})$ $\displaystyle=\mathop{\bf E\/}_{\sigma\sim
P_{\boldsymbol{\beta}}}\ln\frac{P_{\boldsymbol{\beta}}(\sigma)}{P_{\boldsymbol{\gamma}}(\sigma)}=F(\boldsymbol{\gamma})-F(\boldsymbol{\beta})-\mathop{\bf
E\/}_{\sigma\sim\boldsymbol{\beta}}\left[\langle\boldsymbol{\gamma}-\boldsymbol{\beta},\boldsymbol{H}(\sigma)\rangle\right]$
$\displaystyle=g(1)-g(0)-g^{\prime}(0)=\frac{g^{\prime\prime}(\xi)}{2}=\frac{1}{2}\mathop{\bf
Var\/}_{\sigma\sim
P_{\boldsymbol{\beta}+\xi(\boldsymbol{\gamma}-\boldsymbol{\beta})}}\left[\langle\boldsymbol{\gamma}-\boldsymbol{\beta},\boldsymbol{H}(\sigma)\rangle\right],\qed$

We next recall the standard Dobrushin and Dobrushin-Shlosman (DS) conditions
[Dob68].

######  Definition 19 (Dobrushin and Dobrushin-Shlosman Conditions).

Let $H$ be an arbitrary constraint graph and let $G=(V,E)$ be an $H$-colorable
graph. For $u,w\in V$, let

$\displaystyle T_{w}$
$\displaystyle=\\{(\tau,\tau_{w}):\tau,\tau_{w}\in[q]^{V}\mbox{ such that
}\tau(z)=\tau_{w}(z)\mbox{ for all }z\neq w\\},$ $\displaystyle R_{vw}$
$\displaystyle=\max_{(\tau,\tau_{w})\in S_{w}\subseteq
T_{w}}\big{\|}\pi_{v}(\cdot\mid\tau(\mathcal{N}(v))),\pi_{v}(\cdot\mid\tau_{w}(\mathcal{N}(v)))\big{\|}_{\mathrm{TV}},$

where $S_{w}$ is the set of configurations such that the conditional
distributions $\pi_{v}(\cdot|\tau(\mathcal{N}(v)))$ and
$\pi_{v}(\cdot|\tau_{w}(\mathcal{N}(v)))$ are well-defined. Then,

  * •

$\pi_{G}$ satisfies Dobrushin’s uniqueness condition if $\max_{v\in
V}\sum_{w\in\mathcal{N}(v)}R_{vw}<1$.

  * •

$\pi_{G}$ satisfies Dobrushin-Shlosman’s uniqueness condition if $\max_{v\in
V}\sum_{w\in V}R_{wv}<1$.

First, we show that Dobrushin’s condition is not sufficient for learning.

######  Theorem 20 (Dobrushin does not suffice).

For any integers $n,q\geq 3$, there exist graphs $(G=G_{n},H=H_{q})$ and
parameters $\beta_{1}<\beta_{2}$ where $\beta_{2}-\beta_{1}$ is a sufficiently
small constant such that the H-coloring model $\mathop{\bf Pr\/}_{G,H,\beta}$
satisfies Dobrushin’s condition for any $\beta\in(\beta_{1},\beta_{2})$ but
for any $v\in V(G_{n})$ and any $i\in[n]$, it holds that

$\mathop{\bf
Var\/}_{\sigma\sim{G,H,\beta}}(c_{1}(\sigma))=O(n^{2}\exp(-n))\mbox{ for
$\beta\in(\beta_{1},\beta_{2})$}\,,$

and, consequently

$\mathrm{KL}(P_{\beta_{1}}\parallel P_{\beta_{2}})=O(n^{2}\exp(-n))\,.$

###### Proof.

Let $G_{n}$ be a star graph with a node $v$ in the middle and leaves
$u_{1},\ldots,u_{n}$. The set of colors is $[q+1]$ and the constraint graph
$H$ has edge set $E=\\{(1,i):i>1\\}$. In other words, color $1$ is allowed to
be adjacent to any other color, and all other colors are only allowed to be
adjacent to $1$. It is clear that the set of valid colorings is $A\cup B$
where

$A=\left\\{\sigma_{v}=1,\sigma_{u_{i}}>1,~{}\forall
i\in[n]\right\\},\quad~{}~{}B=\left\\{\sigma_{v}>1,\sigma_{u_{i}}=1,~{}\forall
i\in[n]\right\\}\,.$

For simplicity, assume that $\beta$ is a sufficiently small constant (to be
specified later). Then, the event $B$ has exponentially small (in $n$)
probability of occurring. In particular, under $\sigma\in B$, we have that
$c_{1}(\sigma)=n$ and $\mathop{\bf Pr\/}[\sigma\in
B]=\frac{q\exp(n\beta)}{q^{n}\exp(\beta)+q\exp(n\beta)}$. Since we would like
that $q^{n-1}\exp(-n\beta)>\exp(cn)$, for some constant $c>0$, we have to pick
$\beta$ a sufficiently small constant. Thus, we can focus without loss of
generality on the event $A$. Since $c_{1}(\sigma)=1$ for all $\sigma\in A$, it
follows that $\mathop{\bf Var\/}(c_{1}(\sigma)|\sigma\in A)=0$. By the law of
total variance, this implies that $\mathop{\bf Var\/}(c_{1}(\sigma))$ will be
exponentially small for small enough $\beta$. This means that learning $\beta$
is impossible in this regime.

To be more specific, we have that

$\mathop{\bf Var\/}(c_{1}(\sigma))=\mathop{\bf E\/}_{\sigma}[\mathop{\bf
Var\/}_{\sigma_{v}}(c_{1}(\sigma)|\sigma_{-v})]+\mathop{\bf
Var\/}_{\sigma}(\mathop{\bf E\/}_{\sigma_{v}}[c_{1}(\sigma)|\sigma_{-v}])\,.$

By the above discussion, the first term will be 0. For the second one, note
that $\mathop{\bf E\/}_{\sigma_{v}}[c_{1}(\sigma)|\sigma_{-v}]$ is a random
variable that is equal to $n$ with probability at most $\exp(-cn)$ and $1$
with probability at least $1-\exp(-cn)$. This implies that the second term of
the formula is upper bounded by $Cn^{2}\exp(-cn)$, by picking $c$ sufficiently
large and some positive constant $C$. Since the above calculations hold for
any parameter $\beta$ that is sufficiently small, we can invoke Lemma 18 and
get that

$\mathrm{KL}(P_{\beta_{1}}\parallel P_{\beta_{2}})=O(n^{2}\exp(-n))\\\ ,$

while $|\beta_{1}-\beta_{2}|$ is lower bounded by a constant. This implies
that retrieving the true parameter is not possible.

Now, let us compute the Dobrushin matrix of this distribution. The only non-
zero entries will be $R_{vu_{i}}$ and $R_{u_{i}v}$. Let us start with
$R_{vu_{i}}$ first. Notice that the value of some $u_{j}$ for $j\neq i$
already determines the conditional distribution of $\sigma_{u}$. In
particular, if $u_{j}>1$ then $\sigma_{u}=1$ and if $u_{j}=1$ then
$\sigma_{u}$ is uniform in $\\{2,\ldots,q+1\\}$. Thus, changing $u_{i}$ will
not change the conditional distribution of $\sigma_{v}$, which means
$R_{vu_{i}}=0$. Now consider $R_{u_{i}v}$. Notice that $v$ is the only
neighbor of $u_{i}$, hence it is the only one that matters in the conditional
distribution. If $\sigma_{v}=1$, then the conditional distribution of
$\sigma_{u_{i}}$ is uniform on $\\{2,\ldots,q+1\\}$. If $\sigma_{v}>1$, then
$\sigma_{u}=1$ necessarily. Thus, $R_{u_{i}v}=1-1/q$. We conclude that this
distribution satisfies Dobrushin’s condition with $\alpha=1-1/q$, regardless
of the value of $\beta$. ∎

Our next goal is to investigate whether the Dobrushin-Shlosman’s condition is
sufficient for learning.

######  Theorem 21 (Dobrushin-Shloshman does not suffice).

For any $n\in\mathbb{N}$, there exist graphs $(G=G_{n},H=H_{q})$ and
parameters $\beta_{1}<\beta_{2}$ where $\beta_{2}-\beta_{1}$ is a sufficiently
small constant such that the H-coloring model $\mathop{\bf Pr\/}_{G,H,\beta}$
satisfies Dobrushin-Shlosman’s condition for any
$\beta\in(\beta_{1},\beta_{2})$ but for any $v\in V(G_{n})$ and any $\beta$,
it holds that $\mathop{\bf Var\/}_{\sigma\sim{G,H,\beta}}(c_{1}(\sigma))=0$.
Consequently, $\mathrm{KL}(P_{\beta_{1}}\parallel P_{\beta_{2}})=0$.

###### Proof.

Let $G_{n}$ be a cycle with $2n$ nodes $u_{1},\ldots,u_{2n}$. Suppose
$q=\\{1,2,3\\}$ and $H$ has edge set $E=\\{(1,2),(1,3)\\}$. Let
$A=\\{u_{1},u_{3},\ldots\\},B=\\{u_{2},u_{4},\ldots\\}$ be the even and odd
vertices. Then, it is clear that the valid $H$-colorings of $G_{n}$ will have
$\sigma_{A}=1$ and $\sigma_{B}\in\\{2,3\\}$ or $\sigma_{B}=1$ and
$\sigma_{A}\in\\{2,3\\}$. Suppose the Hamiltonian is of the form $\beta
c_{1}(\sigma)$. Then, all valid $H$-colorings have exactly $n$ vertices of
color $1$. Thus $\mathop{\bf Var\/}[c_{1}(\sigma)]=0$ for all $\beta$, which
implies $\mathrm{KL}(P_{\beta_{1}}\parallel P_{\beta_{2}})=0$ by Lemma 18. Let
us calculate the Dobrushin matrix. The only non-zero entries have the form
$R_{u_{i}u_{i+1}}$. Notice that the value of $u_{i-1}$ completely determines
the conditional distribution of $\sigma_{u_{i}}$ regardless of the value of
$\sigma_{u_{i+1}}$. Thus, $R_{u_{i}u_{i+1}}=0$, which means that both
Dobrushin and Dobrushin-Shlossman are satisfied in this example. ∎

Finally we will investigate the Rainbow condition proposed by [BR21].

######  Definition 22 (Average-degree & Rainbow Condition).

The sequence of graphs $(G_{n})_{n\in\mathbb{N}}$ has uniformly bounded
average degree. Moreover, for any color $r\in[q-1]$ of $H$, it holds that

$\lim_{\epsilon\to 0}\liminf_{n\to\infty}\mathop{\bf Pr\/}_{\sigma\sim
G_{n},H,\beta}[u_{r}^{n}(\sigma)>\epsilon n]=1\,,$ (22)

where $u_{r}^{n}(\sigma)$ is the number of vertices in $G_{n}$ whose neighbors
are assigned colors in $\sigma$ that lie in the $H$-neighborhood of $r$ (i.e.,
a vertex $v$ contributes to $u_{r}^{n}(\sigma)$ if it can be recolored to $r$
while keeping the colors of other vertices the same).

This condition was investigated by [BR21]. We will show that this condition is
not sufficient, already in the case of proper $q$-colorings on maximum degree
$d$ graphs (note that the Rainbow Condition is easily seen to be satisfied
when $q\geq d+1$).

######  Theorem 23 (Regime $q\leq d+1$).

Fix $q\geq 2$ and let
$\boldsymbol{\beta^{*}}=(\beta_{1}^{*},\ldots,\beta_{q}^{*})\in\mathbb{R}^{q}$
with $\beta_{q}^{*}=0$.

There exists a sequence of graphs $\\{G_{n}\\}_{n\in\mathbb{N}}$ with maximum
degree $d$ and number of colors $q=d+1$, such that for any
$\boldsymbol{\beta_{1}},\boldsymbol{\beta_{2}}\in\mathbb{R}^{q}$,
$\mathrm{KL}\left(\mathop{\bf
Pr\/}_{G_{n},\boldsymbol{\beta_{1}}}\parallel\mathop{\bf
Pr\/}_{G_{n},\boldsymbol{\beta_{2}}}\right)=0$.

###### Proof.

For a vector $\boldsymbol{\beta}\in\mathbb{R}^{q}$ (with $\beta_{q}=0$),
define the free-energy function

$F(\boldsymbol{\beta})=\ln\bigg{(}\sum_{\sigma\in\Omega_{G_{n}}}e^{\sum_{s=1}^{q-1}\beta_{s}c_{s}(\sigma)}\bigg{)}.$

We also use the notation $P_{\boldsymbol{\beta}}$ for the distribution with
parameter $\boldsymbol{\beta}$ and $\sigma\sim\boldsymbol{\beta}$ when
$\sigma$ is sampled from that distribution. We can use Lemma 18 which relates
the KL divergence between two hard constraint models with different
parameters. We get that, for
$\boldsymbol{\beta},\boldsymbol{\gamma}\in\mathbb{R}^{q}$, it holds that

$\mathrm{KL}(P_{\boldsymbol{\beta}}\parallel
P_{\boldsymbol{\gamma}})=\frac{1}{2}\mathop{\bf
Var\/}_{\sigma\sim\boldsymbol{\beta}+\xi(\boldsymbol{\gamma}-\boldsymbol{\beta})}\left[\sum_{s=1}^{q-1}(\gamma_{s}-\beta_{s})c_{s}(\sigma)\right]\,,$
(23)

for some $\xi\in(0,1)$. We next define such a family of graphs where this
variance is $0$.

Assume $n$ is a multiple of $q$, and let $G_{n}$ be a graph consisting of
$n/q$ cliques of size $q$. Clearly, for each coloring $\sigma$ of $G_{n}$ and
for any $r\in[q]$ we have $c_{r}(\sigma)=n/q$. Hence, the random variable
$\sum_{s=1}^{q-1}(\gamma_{s}-\beta_{s})c_{s}(\sigma)$ appearing in (23) is a
constant, regardless of the values of the parameters $\boldsymbol{\beta}$ of
the model. This gives that $\mathrm{KL}(P_{\boldsymbol{\beta}}\parallel
P_{\boldsymbol{\gamma}})=0$ for any $\boldsymbol{\beta},\boldsymbol{\gamma}$
and, hence, estimation is impossible for this family of graphs. ∎

##  Appendix C Parameter Estimation for the $H$-Coloring Model

In this section, we prove Theorem 3 and then Corollaries 4 and 5.

###  C.1 Algorithm for the $H$-Coloring Model Under 2-Rainbow Condition

Let $G$ be a graph with max degree $d$ and vertex set $[n]$. Let $H$ be a
graph with vertex set $[q]$ and let
$\boldsymbol{\beta}^{\star}=(\beta_{1}^{\star},\ldots,\beta_{q}^{\star})\in\mathbb{R}^{q}$
be a vector of parameters with $\beta_{q}^{\star}=0$ (cf. Footnote 7). Our
goal is to learn $(\beta_{1}^{*},\ldots,\beta_{q-1}^{*})$ from a single sample
$\sigma\sim\mathop{\bf Pr\/}_{G,H,\bm{\beta}^{*}}$. We assume that $H$
satisfies the 2-Rainbow condition on max degree $d$ graphs (though this will
not be important until the proof of Theorem 3.)

To do this, we utilize the Maximum Pseudo-Likelihood Estimator (MPL) (cf.
Definition 6), which was formulated in the $H$-coloring setting by [BR21].
Namely, they showed that the first derivative of the negative pseudo-
likelihood function $\phi(\boldsymbol{\beta};\sigma)$ is given by
$\phi_{1}(\boldsymbol{\beta};\sigma)=(\phi_{1}^{(r)}(\boldsymbol{\beta};\sigma))_{r\in[q]}$,
where for a color $r\in[q]$

$\displaystyle\phi_{1}^{(r)}(\boldsymbol{\beta};\sigma)=c_{r}(\sigma)-\sum_{u=1}^{n}\frac{e^{\beta_{r}}Q(v,r)}{\sum_{s=1}^{q}e^{\beta_{s}}Q(v,s)},$

where, recall from Section 4, for a vertex $v\in[n]$, $s\in[q]$ and
$\sigma\in\Omega_{G}$, we set $Q_{\sigma}(v,s)=1$ if assigning the color $s$
to $v$ while keeping the colors of other nodes according to $\sigma$ results
in a proper coloring, and otherwise we set $Q_{\sigma}(u,s)=0$. The following
lemma was proved in [BR21] and upper-bounds the first derivative when
evaluated at the parameter $\boldsymbol{\beta^{\star}}$.

######  Lemma 24 ([BR21, Lemma 5.1]).

Let $d\geq 2$ be an integer, $B>0$ be a real and $H$ be a $q$-vertex graph.
There exists $L>0$ such that for any $n$-vertex graph $G$ with max degree $d$
and $\Omega^{H}_{G}\neq\emptyset$, for
$\boldsymbol{\beta}=(\beta_{1},\ldots,\beta)\in[-B,B]^{q}$ with $\beta_{q}=0$
it holds that $\mathop{\bf
E\/}\big{[}\|\phi_{1}(\beta;\sigma)\|^{2}_{2}\big{]}\leq Ln$ where the
expectation is over $\sigma\sim\mathop{\bf Pr\/}_{G,H,\boldsymbol{\beta}}$.

We next proceed to formulate the second derivative of $\phi$. Recall from
Section 4 that
$O_{\sigma}(v)=(\theta_{\sigma}(u,1),\ldots,\theta_{\sigma}(u,q-1))^{\top}$
denotes the $(q-1)$-dimensional vector with
$\theta_{\sigma}(u,r)=\frac{\mathrm{e}^{\beta_{r}}Q_{\sigma}(v,r)}{\sum_{s=1}^{q}\mathrm{e}^{\beta_{s}}Q_{\sigma}(v,s)}$.
Then, it holds that (see [BR21] for details)

$\phi_{2}(\boldsymbol{\beta};\sigma)=\sum_{v=1}^{n}\left(\mathrm{diag}(O_{\sigma}(v))-O_{\sigma}(v)O_{\sigma}(v)^{\top}\right).$
(14)

We next give the proof of the inequality in Lemma 11 which we restate here for
convenience. See 11

###### Proof.

By the Cauchy-Schwarz inequality, we have

$\displaystyle\bigg{(}\sum_{s=1}^{q-1}\theta_{\sigma}(v,s)x_{s}\bigg{)}^{2}$
$\displaystyle\leq\bigg{(}\sum_{s=1}^{q-1}\theta_{\sigma}(v,s)x_{s}^{2}\bigg{)}\bigg{(}\sum_{s=1}^{q-1}\theta_{\sigma}(v,s)\bigg{)}=\bigg{(}\sum_{s=1}^{q-1}\theta_{\sigma}(v,s)x_{s}^{2}\bigg{)}\bigg{(}1-\frac{\mathrm{e}^{\beta_{q}}}{\sum_{s=1}^{q}\mathrm{e}^{\beta_{s}}Q_{\sigma}(v,s)}\bigg{)}.$

Thus, using the fact that $\beta_{q}=0$,

$\displaystyle\mathbf{x}^{\top}\left(\mathrm{diag}(O_{\sigma}(v))-O_{\sigma}(v)O_{\sigma}(v)^{\top}\right)\mathbf{x}$
$\displaystyle=\sum_{s=1}^{q-1}\theta_{\sigma}(v,s)x_{s}^{2}-\bigg{(}\sum_{s=1}^{q-1}\theta_{\sigma}(v,s)x_{s}\bigg{)}^{2}\geq\frac{\min_{s\in[q]}\mathrm{e}^{\beta_{s}}}{\sum_{s}\mathrm{e}^{\beta_{s}}}\bigg{(}\sum_{s=1}^{q-1}\theta_{\sigma}(v,s)x_{s}^{2}\bigg{)}.$

Now, we have

$\sum_{s=1}^{q-1}\theta_{\sigma}(v,s)x_{s}^{2}\geq\sum_{r\in\mathcal{I}}\theta_{\sigma}(v,r)x_{r}^{2}\geq\min_{s\in[q-1]}\theta_{\sigma}(v,s)\sum_{r\in\mathcal{I}(\sigma)}x_{r}^{2},$

where the last inequality follows since we know that $\theta_{\sigma}(v,r)\neq
0$ for all $r\in\mathcal{I}(\sigma)$. After observing that
$\min_{s\in[q-1]}\theta_{\sigma}(v,s)\geq\frac{\min_{s\in[q]}\mathrm{e}^{\beta_{s}}}{\sum_{s}\mathrm{e}^{\beta_{s}}Q_{\sigma}(v,s)}\geq\frac{\min_{s\in[q]}\mathrm{e}^{\beta_{s}}}{\sum_{s}\mathrm{e}^{\beta_{s}}}$,
we therefore obtain the inequality in the lemma. ∎

Hence, each term in the second derivative sum preserves some directions of a
vector $\mathbf{x}$. We now use this to prove that $\phi$ is strongly convex.
Recall that $u_{rq}(\sigma)=\sum_{i=1}^{n}Q_{\sigma}(i,r)Q_{\sigma}(i,q)$.

######  Lemma 25.

Let $\sigma\in\Omega_{G}^{H}$ and suppose there exists $\delta>0$ such that
$u_{rq}(\sigma)\geq\delta n$ for all $r\in[q-1]$. Then,
$\phi_{2}(\boldsymbol{\beta};\sigma)\succcurlyeq\delta
n\Big{(}\frac{\min_{s\in[q]}\mathrm{e}^{\beta_{s}}}{\sum_{s=1}^{q}\mathrm{e}^{\beta_{s}}}\Big{)}^{2}\mathbf{I}_{q-1}.$

###### Proof.

Let $\mathbf{x}\in\mathbb{R}^{q-1}$ be an arbitrary vector. We have that

$\displaystyle\mathbf{x}^{\top}\phi_{2}(\boldsymbol{\beta};\sigma)\mathbf{x}$
$\displaystyle=\sum_{v=1}^{n}\mathbf{x}^{\top}\left(\mathrm{diag}(O_{\sigma}(u))-O_{\sigma}(u)O_{\sigma}(u)^{\top}\right)\mathbf{x}\,.$

Define $\mathcal{I}_{v}(\sigma)=\\{r\in[q-1]:Q_{\sigma}(v,r)=1\\}$, and
$U_{q}=\\{v\in[n]:Q_{\sigma}(v,q)=1\\}$. Then, since every matrix in the sum
is positive definite, by applying Lemma 11, we have that

$\displaystyle\mathbf{x}^{\top}\phi_{2}(\boldsymbol{\beta};\sigma)\mathbf{x}\geq\sum_{v\in
U_{q}}\mathbf{x}^{\top}\left(\mathrm{diag}(O_{\sigma}(v))-O_{\sigma}(v)O_{\sigma}(v)^{\top}\right)\mathbf{x}\geq\bigg{(}\frac{\min_{s\in[q]}\mathrm{e}^{\beta_{s}}}{\sum_{s=1}^{q}\mathrm{e}^{\beta_{s}}}\bigg{)}^{2}\sum_{v\in
U_{q}}\sum_{r\in\mathcal{I}_{v}}x_{r}^{2}.$

Now, by definition $u_{rq}(\sigma)=\left|\\{v\in V:v\in
U_{q},\mathcal{I}_{v}(\sigma)\ni r\\}\right|$. Thus,

$\displaystyle\mathbf{x}^{\top}\phi_{2}(\boldsymbol{\beta};\sigma)\mathbf{x}\geq\left(\frac{\min_{s\in[q]}\mathrm{e}^{\beta_{s}}}{\sum_{s=1}^{q}\mathrm{e}^{\beta_{s}}}\right)^{2}\sum_{r=1}^{q-1}u_{rq}(\sigma)x_{r}^{2}\geq\delta
n\left(\frac{\min_{s\in[q]}\mathrm{e}^{\beta_{s}}}{\sum_{s=1}^{q}\mathrm{e}^{\beta_{s}}}\right)^{2}\|\mathbf{x}\|_{2}^{2},$

finishing the proof. ∎

We next give the proof of Theorem 3 which we restate here for convenience.
Recall that the 2-Rainbow Condition asserts that there is a constant
$\delta>0$ such that

$\mathop{\bf Pr\/}_{G,H,\boldsymbol{\beta}^{*}}\big{[}u_{rq}(\sigma)\geq\delta
n,~{}\forall r\in[q-1]\big{]}=1-o(1).$ (3)

See 3

###### Proof.

For $t\in[0,1]$, let
$\boldsymbol{\beta}(t)=t\hat{\boldsymbol{\beta}}_{\sigma}+(1-t)\boldsymbol{\beta^{\star}}$
and
$h(t)=(\boldsymbol{\hat{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}})\phi_{1}(\boldsymbol{\beta}(t);\sigma)$.
Since $\hat{\boldsymbol{\beta}}_{\sigma}$ maximizes $\phi$, we have that
$\phi_{1}(\hat{\boldsymbol{\beta}};\sigma)=0$ and hence $h(1)=0$.

For any $\boldsymbol{\beta}\in[-2B,2B]^{q}$, we have the crude bound
$\left(\frac{\min_{s\in[q]}\mathrm{e}^{\beta_{s}}}{\sum_{s=1}^{q}\mathrm{e}^{\beta_{s}}}\right)^{2}\geq
C=1/(q^{2}\mathrm{e}^{8B})$. Define the set of colorings

$\mathcal{A}=\left\\{\sigma\in\Omega_{G}^{H}:\|\phi_{1}(\boldsymbol{\beta};\sigma)\|_{2}\leq\sqrt{2Ln/\epsilon}~{}~{}\text{
and
}~{}\min_{\boldsymbol{\beta}\in[-2B,2B]^{q}}\lambda_{\min}(\phi_{2}(\boldsymbol{\beta};\sigma)\geq
C\delta n\right\\},$

and note that, from Lemmas 24 and 25 (combined with a union bound), it holds
that $\mathop{\bf Pr\/}_{G,H,\boldsymbol{\beta}^{*}}[A]\geq
1-\epsilon/2-o(1)\geq 1-\epsilon$ for all sufficiently large $n$.

Consider $\sigma\in\mathcal{A}$. We have from Cauchy-Schwarz inequality that

$\displaystyle\big{\|}\hat{\boldsymbol{\beta}}_{\sigma}$
$\displaystyle-\boldsymbol{\beta^{\star}}\big{\|}_{2}\big{\|}\phi_{1}(\boldsymbol{\beta^{\star}};\sigma)\big{\|}_{2}$
$\displaystyle\geq\big{|}(\boldsymbol{\hat{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}})L(\boldsymbol{\beta^{\star}})\big{|}=|h_{n}(1)-h_{n}(0)|=\left|\int_{0}^{1}h_{n}^{\prime}(t)\mathrm{d}t\right|=\left|\int_{0}^{1}(\hat{\boldsymbol{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}})^{\top}\phi_{2}(\boldsymbol{\beta}(t);\sigma)(\hat{\boldsymbol{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}})\mathrm{d}t\right|$

Note that $\phi_{2}(\boldsymbol{\beta};\sigma)\succcurlyeq 0$ for every
$\beta$ (cf. (14)), so with
$\ell=\|\hat{\boldsymbol{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}}\|_{2}$ we
obtain

$\big{\|}\hat{\boldsymbol{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}}\big{\|}_{2}\big{\|}\phi_{1}(\boldsymbol{\beta^{\star}};\sigma)\big{\|}_{2}\
\geq\bigg{|}\int_{0}^{\min\\{1,B/\ell\\}}(\hat{\boldsymbol{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}})^{\top}\phi_{2}(\boldsymbol{\beta}(t);\sigma)(\hat{\boldsymbol{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}})\mathrm{d}t\bigg{|}.$
(24)

For $0\leq t\leq B/\ell$, we have that
$\boldsymbol{\beta}_{\sigma}(t)\in[-2B,2B]^{q}$. Hence, since
$\sigma\in\mathcal{A}$, (24) gives that $\sqrt{2Ln/\epsilon}\geq C\delta
n\min\\{\ell,B\\}$. Therefore, for all sufficiently large $n$, we obtain that
$\|\hat{\boldsymbol{\beta}}_{\sigma}-\boldsymbol{\beta^{\star}}\|_{2}=\ell\leq
M/\sqrt{n}$, where $M=\sqrt{2L/C^{2}\delta^{2}\epsilon}$, finishing the proof.
∎

###  C.2 Application of Theorem 3 to proper $q$-colorings

Let $\boldsymbol{\beta^{\star}}\in\mathbb{R}^{q}$ and $G$ be a graph of max
degree $d$ with vertex set $[n]$. In order to prove the positive part of
Corollary 4, we need to establish the 2-Rainbow Condition (cf. (3)). For a
coloring $\sigma\sim\mathop{\bf Pr\/}_{G,\boldsymbol{\beta^{\star}}}$ and
$i\in[n],r\in[q]$, define the random variable
$e^{rq}_{i}(\sigma)=Q(i,q)Q(i,r)$, in other words, $e^{rq}_{i}(\sigma)=1$ if
assigning $\sigma_{i}=r$ or $\sigma_{i}=q$ while keeping the other vertices
colored according to $\sigma$ results in a proper coloring. By definition of
$u_{rq}(\sigma)$, we have $u_{rq}(\sigma)=\sum_{i=1}^{n}e_{i}^{rq}(\sigma)$.

Let $R\subseteq V$ be a maximal subset of nodes that forms a 2-hop independent
set of $G$, i.e., distinct $v,w\in R$ have disjoint neighborhoods. We can pick
$R$ greedily; using that $G$ has maximum degree $d$, we have that $|R|\geq
n/(d+1)^{2}$. See 12

###### Proof.

Let $\Omega_{x}$ be the subset of proper $q$-colorings that are consistent
with $x=(x_{1},\ldots,x_{k-1})$. Let $\Omega_{x}^{+}$ be the subset of
$\Omega_{x}$ containing all $\sigma$ with $e^{rq}_{v_{k}}(\sigma)=1$ and
similarly, $\Omega_{x}^{-}$ be the subset containing all $\sigma$ with
$e^{rq}_{v_{k}}(\sigma)=0$.

We will construct a mapping $g:\Omega_{x}^{-}\mapsto\Omega_{x}^{+}$ as
follows. Let $\sigma\in\Omega_{x}^{-}$ and let $\mathcal{N}_{v_{k}}$ be the
set of neighbors of $v_{k}$ in $G$. Denote by $B$ the neighbors
$j\in\mathcal{N}_{v_{k}}$ such that $\sigma_{j}=r$ or $\sigma_{j}=q$. Since
$e^{rq}_{v_{k}}(\sigma)=0$, $B$ is nonempty. We will produce a proper
$q$-coloring $\sigma^{\prime}$ by changing the colors of the nodes in $B$. To
do this, first erase the colors of the nodes in $B$, while keeping the rest of
the colors as in $\sigma$. We will iteratively assign colors to the nodes in
$B$, each time ensuring that the color chosen does not appear in any neighbors
of that node that have not been erased. Pick a node $j\in B$. Let
$m=|\mathcal{N}_{j}\cap B|$ and
$m^{\prime}=|\mathcal{N}_{j}\cap(B\cup\\{v_{k}\\})^{c}|$. Since $v_{k}$ is a
neighbor of $j$, we have that $m+m^{\prime}+1\leq d$, which means that
$m^{\prime}\leq d-1-m\leq q-3-m$ . Thus, we have at least $m+3\geq 3$
available colors for $j$ that do not conflict with any colors assigned to
vertices in $\mathcal{N}_{j}\cap(B\cup\\{v_{k}\\})^{c}$. Let $s$ be one of
these colors that is not equal to $r$ or $q$. We set $\sigma^{\prime}(j)=s$
and remove $j$ from $B$. This process can be carried out for all nodes in $B$,
each time coloring a node with a color different than $q$ and $r$, while
maintaining the property that the coloring produced so far is proper. Thus, in
the end, we set $\sigma^{\prime}(v_{k})=q$ and $g(\sigma)=\sigma^{\prime}$,
and by definition no neighbor of $v_{k}$ is colored with $r$ or $q$ in
$\sigma^{\prime}$. Furthermore, we only changed the colors of neighbors of
$v_{k}$. Since $v_{1},\ldots,v_{k-1}$ do not share any neighbors with $v_{k}$
(by definition of the set $R$), $\sigma^{\prime}$ is still consistent with the
assignment
$e_{v_{1}}^{rq}(\sigma)=x_{1},\ldots,e_{v_{k-1}}^{rq}(\sigma)=x_{k-1}$. In
other words, we just showed that $g(\sigma)\in\Omega_{x}^{+}$.

Since $g$ only changes the colors of $v_{k}$ and its neighbors, we have that
for any $\sigma^{\prime}\in\Omega_{x}^{+}$, the subset of $\Omega_{x}^{-}$
that is mapped to $\sigma^{\prime}$ under $g$ has size
$|g^{-1}(\sigma^{\prime})|\leq q^{d+1}$. Furthermore, if
$\sigma^{\prime}=g(\sigma)$, then

$\exp\bigg{(}\sum_{s=1}^{q}\beta_{s}^{\star}c_{s}(\sigma)\bigg{)}\leq\exp(\|\boldsymbol{\beta^{\star}}\|_{1}d)\exp\bigg{(}\sum_{s=1}^{q}\beta_{s}^{\star}c_{s}(\sigma^{\prime})\bigg{)}.$

These observations yield that

$\displaystyle\mathop{\bf
Pr\/}_{G_{n},\boldsymbol{\beta^{\star}}}[e_{v_{k}}=1|e_{v_{1}}^{rq}(\sigma)=x_{1},\ldots,e_{v_{k-1}}^{rq}(\sigma)=x_{k-1}]$
$\displaystyle=\frac{\sum_{\sigma\in\Omega_{x}^{+}}\exp\left(\sum_{s=1}^{q}\beta_{s}^{\star}c_{s}(\sigma)\right)}{\sum_{\sigma\in\Omega_{x}^{+}}\exp\left(\sum_{s=1}^{q}\beta_{s}^{\star}c_{s}(\sigma)\right)+\sum_{\sigma\in\Omega_{x}^{-}}\exp\left(\sum_{s=1}^{q}\beta_{s}^{\star}c_{s}(\sigma)\right)}\,,$

and the right-hand side is at least

$\frac{\sum_{\sigma\in\Omega_{x}^{+}}\exp\left(\sum_{s=1}^{q}\beta_{s}^{\star}c_{s}(\sigma)\right)}{\sum_{\sigma\in\Omega_{x}^{+}}\exp\left(\sum_{s=1}^{q}\beta_{s}^{\star}c_{s}(\sigma)\right)+q^{d}e^{\|\boldsymbol{\beta^{\star}}\|_{1}d}\sum_{\sigma\in\Omega_{x}^{+}}\exp\left(\sum_{s=1}^{q}\beta_{s}^{\star}c_{s}(\sigma)\right)}\geq\frac{1}{1+q^{d+1}e^{\|\boldsymbol{\beta}^{\star}\|_{1}d}}.\qed$

We are now ready to complete the proof of Corollary 4, which we restate here.
See 4

###### Proof.

The impossibility part for $q\leq d+1$ has already been shown in Theorem 23 in
Appendix B. So we focus on the statement for the existence of the estimator
when $q\geq d+2$.

From Theorem 3, it suffices to show that in the regime $q\geq d+2$, the
2-Rainbow condition (cf. (3)) is satisfied on graphs $G$ of max degree $d$,
i.e., we want to show that there exists $\delta>0$ such that for all
$r\in[q-1]$, it holds that $\mathop{\bf
Pr\/}_{G,\boldsymbol{\beta}^{\star}}[u_{rq}(\sigma)\geq\delta n]=1-o(1)$,
where $u_{rq}(\sigma)$ is the number of vertices that can be colored by either
$r$ or $q$ while still being a proper $q$-coloring.

Let $R=\\{v_{1},....,v_{t}\\}$ be a maximal 2-hop independent set (i.e., the
vertices in $R$ have mutually disjoint neighborhoods), so that $t\geq
n/(d+1)^{2}$. Then, for distinct colors $r$ and $q$, we have the lower bound
$u_{rq}(\sigma)\geq\sum^{t}_{k=1}e^{rq}_{v_{k}}(\sigma)$. By the “conditional
independence” property of Lemma 12, we have by an application of Lemma 17 that
the sum stochastically dominates the sum $\sum^{t}_{i=1}\tau_{i}$ where
$\\{\tau_{i}\\}$ is a family of 0-1 random variables with $\mathop{\bf
Pr\/}[\tau_{i}=1]=p$, where
$p=\frac{1}{1+q^{d+1}\mathrm{e}^{\|\boldsymbol{\beta}^{\star}\|_{1}d}}$. By
standard Chernoff bounds, for $\delta=p/(4d)^{2}$ it follows that
$u_{rq}(\sigma)\geq\delta n$ with probability $1-\mathrm{e}^{-\Omega(n)}$ over
the choice of $\sigma$. This completes the proof. ∎

###  C.3 Application of Theorem 3 to Permissive Models

In this section, we prove Corollary 5. See 5

###### Proof.

As in the case of proper $q$-colorings, the result will follow by applying
Theorem 3. We only need to establish the 2-Rainbow Condition, i.e., that for
any color $r$ it holds that $u_{rq}(\sigma)=\Omega(n)$ with probability
$1-o(1)$ over the choice of $\sigma$. The proof of this is very similar to
that of Corollary 4, once we prove a suitable analogue of the “conditional
independence” property of Lemma 12.

Let $G=(V,E)$. Suppose that the unconstrained color of $H$ is $j$. For a
vertex $v$ of $G$, the key is to consider the indicator $e_{v}(\sigma)$ of the
event that all neighbors of $v$ get the unconstrained color $j$. Then, since
color $j$ is unconstrained, for any color $r\in[q]$, we have the lower bound
$u_{rq}(\sigma)\geq\sum_{v\in V}e_{v}(\sigma)$. It remains therefore to lower
bound the latter sum.

Analogously now to proper colorings, consider a maximal set
$R=\\{v_{1},\ldots,v_{t}\\}$ of vertices with mutually disjoint neighborhoods;
we have that $t\geq n/(d+1)^{2}$. Then, for $k=1,\ldots,t$, it holds that

$\mathop{\bf Pr\/}_{G,H,\bm{\beta}^{*}}[e_{v_{k}}(\sigma)=1\mid
e_{v_{1}},\ldots,e_{v_{k-1}}(\sigma)]\geq p^{d}\,,~{}\mbox{ where
~{}}p=\frac{e^{\beta_{j}^{\star}}}{\sum_{s=1}^{q}e^{\beta_{s}^{\star}}}.$ (25)

To prove (25), we will show that for any vertex $w$, conditioned on any
coloring of its neighborhood, the probability that $w$ gets the unconstrained
color $j$ is at least $p$. Assuming this for the moment, the probability that
all neighbours of $v_{k}$ get $j$ is at least $p^{d}$. Since the conditioning
on $e_{v_{1}},\ldots,e_{v_{k-1}}$ is completely determined by the coloring of
the neighborhoods of $v_{1},\ldots,v_{k-1}$ and $v_{k}$ does not have a
neighbor in any of these (by the choice of $R$), the bound on the conditional
probability in (25) follows. Using (25), we can now invoke Lemma 17
analogously to the proper $q$-colorings case to conclude that
$u_{rq}(\sigma)\geq\sum^{t}_{i=1}e_{v_{i}}(\sigma)\geq\delta n$ with
probability $1-\mathrm{e}^{-\Omega(n)}$ over the choice of $\sigma$, where
$\delta=p^{d}/(8d)^{2}$.

To finish the proof of the 2-Rainbow Condition, it remains to show the
intermediate fact that we used in the proof of (25), i.e., for a vertex $w$
with neighbors $w_{1},\ldots,w_{d}$, it holds that

$\mathop{\bf
Pr\/}_{G,H,\bm{\beta}^{*}}[\sigma_{w}=j\mid\sigma_{w_{1}}=x_{1},\ldots,\sigma_{w_{d}}=x_{d}]\geq
p$ (26)

for any choice of colors $x_{1},\ldots,x_{d}$ (which are consistent with some
$H$-coloring of $G$). To see (26), let $x=(x_{1},\ldots,x_{d})$ and denote by
$\Omega_{x}$ the set of all valid $H$-colorings $\sigma$ such that
$\sigma_{w_{1}}=x_{1},\ldots,\sigma_{w_{d}}=x_{d}$. For $s\in[q]$, denote
further by $\Omega^{s}_{x}$ those $H$-colorings in $\Omega_{x}$ where
$\sigma_{w}=s$, so that $\\{\Omega^{s}_{x}\\}_{s=1}^{q}$ is a partition of
$\Omega_{x}$. It follows that

$\mathop{\bf
Pr\/}_{G,H,\bm{\beta}^{*}}[\sigma_{w}=j\mid\sigma_{w_{1}}=x_{1},\ldots,\sigma_{w_{d}}=x_{d}]=\frac{\sum_{\sigma\in\Omega^{j}_{x}}\exp\left(\sum_{i=1}^{q-1}\beta_{i}^{\star}c_{i}(\sigma)\right)}{\sum_{s=1}^{q}\sum_{\sigma\in\Omega^{s}_{x}}\exp\left(\sum_{i=1}^{q-1}\beta_{i}^{\star}c_{i}(\sigma)\right)}.$
(27)

Now, for any $s\neq j$, define the mapping
$g_{s}:\Omega^{s}_{x}\mapsto\Omega^{j}_{x}$ by setting for $v\in V$

$g_{s}(\sigma)_{v}=\left\\{\begin{array}[]{ll}j&\text{ , if $v=w$},\\\
\sigma_{v}&\text{ , otherwise.}\end{array}\right.$

Since the color $j$ is unconstrained, $g(\sigma)$ is a valid $H$-coloring and
$g_{s}(\sigma)\in\Omega^{j}_{x}$; also $g_{s}$ is injective. Now, suppose that
$g_{s}(\sigma)=\sigma^{\prime}$, we have

$\exp\bigg{(}\sum_{i=1}^{q-1}\beta_{i}^{\star}c_{i}(\sigma)\bigg{)}=\exp(\beta^{\star}_{s}-\beta^{\star}_{j})\exp\bigg{(}\sum_{i=1}^{q-1}\beta_{i}^{\star}c_{i}(\sigma^{\prime})\bigg{)},$

since $\sigma$ and $\sigma^{\prime}$ only differ in the color of node $k$.
Using the injectivity of $g_{s}$, it thererefore follows that

$\sum_{\sigma\in\Omega^{s}_{x}}\exp\bigg{(}\sum_{i=1}^{q-1}\beta_{i}^{\star}c_{i}(\sigma)\bigg{)}\leq\exp(\beta^{\star}_{s}-\beta^{\star}_{r})\sum_{\sigma\in\Omega^{j}_{x}}\exp\bigg{(}\sum_{i=1}^{q-1}\beta_{i}^{\star}c_{i}(\sigma)\bigg{)}.$

Using this to upper-bound the sums in the denominator of (27) for all $s\neq
j$, we obtain (26) after observing that $p=\frac{1}{1+\sum_{s\neq
j}\exp(\beta^{\star}_{s}-\beta^{\star}_{j})}$. This finishes the proof of
Corollary 5. ∎