We consider the problem of estimating the parameters of a Markov Random Field
with hard-constraints using a single sample. As our main running examples, we
use the $k$-SAT and the proper coloring models, as well as general $H$-coloring
models; for all of these 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.
Our algorithms are based on the pseudo-likelihood estimator. We show variance
bounds for this estimator using coupling techniques inspired, in the case of
$k$-SAT, by Moitra's sampling algorithm (JACM, 2019); our positive results for
colorings build on this new coupling approach. For $q$-colorings on graphs with
maximum degree $d$, we give a linear-time estimator 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 general 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$, we provide a
linear-time estimator when $k\gtrsim 6.45\log d$, whereas the problem becomes
non-identifiable when $k\lesssim \log d$.

使用单个样本估计具有硬约束的马尔可夫随机场的参数，算法基于伪似然估计器，对于 $k$-SAT 和 proper coloring 模型以及一般的 $H$-coloring 模型，不仅获得了正面结果，还获得了负面结果。

学习带单样本硬约束的模型

Learning Hard-Constrained Models with One Sample

The objective of generative model inversion is to identify a size-$n$ latent
vector that produces a generative model output that closely matches a given
target. This operation is a core computational primitive in numerous modern
applications involving computer vision and NLP. However, the problem is known
to be computationally challenging and NP-hard in the worst case. This paper
aims to provide a fine-grained view of the landscape of computational hardness
for this problem. We establish several new hardness lower bounds for both exact
and approximate model inversion. In exact inversion, the goal is to determine
whether a target is contained within the range of a given generative model.
Under the strong exponential time hypothesis (SETH), we demonstrate that the
computational complexity of exact inversion is lower bounded by $\Omega(2^n)$
via a reduction from $k$-SAT; this is a strengthening of known results. For the
more practically relevant problem of approximate inversion, the goal is to
determine whether a point in the model range is close to a given target with
respect to the $\ell_p$-norm. When $p$ is a positive odd integer, under SETH,
we provide an $\Omega(2^n)$ complexity lower bound via a reduction from the
closest vectors problem (CVP). Finally, when $p$ is even, under the exponential
time hypothesis (ETH), we provide a lower bound of $2^{\Omega (n)}$ via a
reduction from Half-Clique and Vertex-Cover.

生成模型反演问题的计算复杂性上界，包括精确反演和近似反演中的新的若干复杂性下界，以及使用约化方法从 $k$-SAT 问题得出的强指数时间假设 (SETH) 下的精确反演的计算复杂性的下界。