Learning Hard-Constrained Models with One Sample
Andreas Galanis, Alkis Kalavasis, Anthimos Vardis Kandiros · Society for Industrial and Applied Mathematics eBooks · 2024
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.