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

We consider the problem of estimating inverse temperature parameter β 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,1n where each configuration σ is constrained to lie in a truncation set S subseteq -1,1n and has probability Pr(σ) propto exp(βσ^top Aσ) 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 σ from a truncated Ising model, with inverse parameter β^*, 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β that is O(Delta3/√n)-consistent with the true parameter β^* for k gtrsim log(d2k)Delta3. 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.