Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample

arXiv:2509.20993v2 Announce Type: replace-cross
Abstract: We consider the problem of estimating inverse temperature parameter $beta$ of an $n$-dimensional truncated Ising model using a single sample. Given a graph $G = (V,E)$ with $n$ vertices, a truncated Ising model is a probability distribution over the $n$-dimensional hypercube ${-1,1}^n$ where each configuration $mathbf{sigma}$ is constrained to lie in a truncation set $S subseteq {-1,1}^n$ and has probability $Pr(mathbf{sigma}) propto exp(betamathbf{sigma}^top Amathbf{sigma})$ with $A$ being the adjacency matrix of $G$. We adopt the recent setting of [Galanis et al. SODA’24], where the truncation set $S$ can be expressed as the set of satisfying assignments of a $k$-SAT formula. Given a single sample $mathbf{sigma}$ from a truncated Ising model, with inverse parameter $beta^*$, underlying graph $G$ of bounded degree $Delta$ and $S$ being expressed as the set of satisfying assignments of a $k$-SAT formula, we design in nearly $O(n)$ time an estimator $hat{beta}$ that is $O(Delta^3/sqrt{n})$-consistent with the true parameter $beta^*$ for $k gtrsim log(d^2k)Delta^3.$
Our estimator is based on the maximization of the pseudolikelihood, a notion that has received extensive analysis for various probabilistic models without [Chatterjee, Annals of Statistics ’07] or with truncation [Galanis et al. SODA ’24]. Our approach generalizes recent techniques from [Daskalakis et al. STOC ’19, Galanis et al. SODA ’24], to confront the more challenging setting of the truncated Ising model.