# Learning Hard-Constrained Models with One Sample arXiv: https://arxiv.org/abs/2311.03332 · HTML: https://mlsanity.com/paper/2311.03332/ ## Key facts - Cited by 7 papers in the map (data through 14 Oct 2026). - Builds on 47 of its 84 references that are in the map. - First posted on arXiv 6 Nov 2023. ## Builds on (most cited first, 30 of 47) - [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014) - [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022) - [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017) - [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018) - [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020) - [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016) - [Efficient Truncated Statistics with Unknown Truncation](https://mlsanity.com/paper/1908.01034/) (2019) - [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017) - [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021) - [Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains](https://mlsanity.com/paper/2203.04163/) (2022) - [Distribution-Aware Sampling and Weighted Model Counting for SAT](https://mlsanity.com/paper/1404.2984/) (2014) - [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021) - [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021) - [Learning from weakly dependent data under Dobrushin's condition](https://mlsanity.com/paper/1906.09247/) (2019) - [Efficient Parameter Estimation of Truncated Boolean Product Distributions](https://mlsanity.com/paper/2007.02392/) (2020) - [Optimal Learning of Mallows Block Model](https://mlsanity.com/paper/1906.01009/) (2019) - [Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion](https://mlsanity.com/paper/2011.02075/) (2020) - [On the Analysis of EM for truncated mixtures of two Gaussians](https://mlsanity.com/paper/1902.06958/) (2019) - [Regression from Dependent Observations](https://mlsanity.com/paper/1905.03353/) (2019) - [Uniform Sampling through the Lov'asz Local Lemma](https://mlsanity.com/paper/1611.01647/) (2016) - [Learning from Censored and Dependent Data: The case of Linear Dynamics](https://mlsanity.com/paper/2104.05087/) (2021) - [Statistical Estimation from Dependent Data](https://mlsanity.com/paper/2107.09773/) (2021) - [Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods](https://mlsanity.com/paper/2202.08907/) (2022) - [On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization](https://mlsanity.com/paper/2103.07459/) (2021) - [Testing Convex Truncation](https://mlsanity.com/paper/2305.03146/) (2023) - [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022) - [Sampling Constraint Satisfaction Solutions in the Local Lemma Regime](https://mlsanity.com/paper/2011.03915/) (2020) - [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022) - [Optimal Single Sample Tests for Structured versus Unstructured Network Data](https://mlsanity.com/paper/1802.06186/) (2018) - [Fast sampling and counting k-SAT solutions in the local lemma regime](https://mlsanity.com/paper/1911.01319/) (2019) ## Built on by (most cited first, 7 of 7) - [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024) - [Smoothed Analysis of Learning from Positive Samples](https://mlsanity.com/paper/2504.10428/) (2025) - [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025) - [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025) - [Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample](https://mlsanity.com/paper/2509.20993/) (2025) - [One-Shot Learning for k-SAT](https://mlsanity.com/paper/2502.07135/) (2025) - [Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue](https://mlsanity.com/paper/2607.22889/) (2026) ## Abstract (arXiv) 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≤ 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 kgtrsim 6.45log d, whereas the problem becomes non-identifiable when klesssim log d.