Learning Ising Models under Hard Constraints using One Sample

We consider the problem of estimating the 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(\beta\mathbf{\sigma}^\top A_G \mathbf{\sigma})$ with $A_G$ 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$-CNF 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$-CNF formula, we design in nearly $\mathcal{O}(n)$ time an estimator $\hat{\beta}$ that is $\mathcal{O}(\Delta^3/\sqrt{n})$-consistent with the true parameter $\beta^\*$ for $k \gtrsim \log(d^2 k)\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.