Learning Hard-Constrained Models with One Sample

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 Hcoloring 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 nonsatisfiable 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 ≤ 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 6.45 log d, whereas the problem becomes non-identifiable when k log d.