Learning Ising Models under Hard Constraints using One Sample
Rohan Chauhan, Ioannis Panageas · 2025
Read Learning Ising Models under Hard Constraints using One Sample by Rohan Chauhan, Ioannis Panageas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-20993.txt.
Introduction
Estimating the temperature-like parameter of an Ising model from a single snapshot sounds impossible, yet constraints can make it feasible. Rohan Chauhan and Ioannis Panageas study that estimation in a 2025 paper accepted for ICLR 2026. Their model is a truncated Ising model with hard constraints.
Configurations of spins are restricted to a truncation set, here the satisfying assignments of a k-SAT formula. Only one sample from the distribution is given. The authors build on a recent setting by Galanis and co-authors, where such constraint sets were introduced. Learning the inverse temperature from one constrained sample serves physics and counting problems alike. The paper develops the theory of when a single observation carries enough information.
Catalog record
| CREATOR | Rohan Chauhan, Ioannis Panageas |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-20993
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning Ising Models under Hard Constraints using One Sample Rohan Chauhan, Ioannis Panageas Abstract We consider the problem of estimating inverse temperature parameter β \beta of an n n -dimensional truncated Ising model using a single sample. Given a graph G = ( V , E ) G=(V,E) with n n vertices, a truncated Ising model is a probability distribution over the n n -dimensional hypercube { − 1 , 1 } n \{-1,1\}^{n} where each configuration σ \mathbf{\sigma} is constrained to lie in a truncation set S ⊆ { − 1 , 1 } n S\subseteq\{-1,1\}^{n} and has probability Pr ( σ ) ∝ exp ( β σ ⊤ A σ ) \Pr(\mathbf{\sigma})\propto\exp(\beta\mathbf{\sigma}^{\top}A\mathbf{\sigma}) with A A being the adjacency matrix of G G . We adopt the recent setting of [Galanis et al. SODA’24], where the truncation set S S can be expressed as the set of satisfying assignments of a k k -SAT formula. Given a single sample σ \mathbf{\sigma} from a truncated Ising model, with inverse parameter β \beta , underlying graph G G of bounded degree Δ \Delta and S S being expressed as the set of satisfying assignments of a k k -SAT formula, we design in nearly 𝒪 ( n ) \mathcal{O}(n) time an estimator β ^ \hat{\beta} that is 𝒪 ( Δ 3 / n ) \mathcal{O}(\Delta^{3}/\sqrt{n}) -consistent with the true parameter β \beta for k ≳ log ( d 2 k ) Δ 3 . 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. Contents 1 Introduction Markov random fields (MRFs) are a common framework for analyzing high-dimensional distributions with complex conditional independence structures. A well-studied example of an MRF and the primary topic of inquiry in this paper is the Ising model Isi 25 , a probability measure \mu_{G,\beta} , over all assignments \bm{\sigma} in the binary hypercube \{-1,1\}^{n} . The model is parameterized by a graph G=(V,E) and inverse temperature \beta , and taking the form \mu_{G,\beta}\propto\exp\left(\beta\bm{\sigma}^{\top}A\bm{\sigma}\right) , with A being the adjacency matrix of G . The simplicity of the Ising model has led to widespread adoption in fields as disparate as statistical physics, finance, the social sciences, and computer vision, among others (see Cha 07 ; QZ 11 ; Har 13 ; WCMN 15 and the references therein for a brief collection of examples). These applications have, in turn, motivated a substantial body of research on efficient sampling Bre 15 ; LS 13 ; SS 12 , rigorous testing DDK 19 , and principled inference of the inverse temperature parameter and interaction matrix DDDK 20 ; DDD+ 21 under the framework of the Ising model. Beginning from the work of Cha 07 , there has been substantial interest in the task of estimating inverse temperature parameter \beta , given only one sample \bm{\sigma}\sim\mu_{G,\beta} and the graph G , using the maximum pseudolikelihood estimator of Bes 75 . This setup subsumes the setting of multi-sample estimation as \ell samples of an Ising model over n nodes is equivalently a single sample of an n\ell Ising model over \ell disconnected components of a graph. This line of work is driven by the inherent technical constraints of network data, wherein it is often impractical to obtain independent observations of the same network responses DDP 19 ; DDDK 20 . Interestingly, despite both static and dynamic phase transitions in model behavior as \beta varies which can render sampling computationally intractable (NP-hard) GSV 16 , it remains possible to construct consistent estimators of \beta and the interaction matrix A , provided that \beta=\mathcal{O}(1) DDDK 20 ; DDD+ 21 ; DDP 19 ; MNH+ 22 . + + + + - - - + - + - + + + - + + - + + + - + - - - + - - + (a) Low Temperature (\beta=\beta_{1}) - - - + + + + + - - - + - + - + + - + + + - - + + - - + - - (b) High Temperature (\beta=\beta_{2}) Figure 1 : Two typical spin configurations over the Ising model at temperatures \beta_{1},\beta_{2} with \beta_{1}\gg\beta_{2} (equivalently at a lower temperature T_{1} and a higher temperature T_{2} where T\propto 1/\beta ). Each node has spin +1 or spin -1 . The left panel shows the configuration at a lower temperature, with alignment producing large domains of positive and negative spin assignments, while the right panel exhibits a more disordered pattern. In many real-world applications, however, we face not only soft constraints, which influence the model behavior by introducing correlations or dependencies, while the full support of the measure remains intact, but also hard constraints: Certain configurations are outright forbidden, and entire regions of the configuration space are excluded from the support of the distribution. Such hard-constrained models (also called truncated ) arise naturally in applications involving high-dimensional, interconnected systems with strict feasibility requirements, one particularly notable example of which arises in the context of spatial transcriptomics—a biological framework for characterizing gene and protein expression in cells within organic tissue, relative to their spatial organization. The local relationships between cells are often represented as nodes in a graph with edges linking cells together that are close in physical space ( ELZ+ 19 ) . Associated with each node is a set of measurements of expression to capture how the relationships between cells impact the phenotype of a given node. The complex relationship between genes often forces certain configurations of expressions to be infeasible . In fact, the phenomenon of lateral inhibition can cause a cell expressing gene one to prevent its neighbors from expressing it as well, instead causing them to express gene two, as seen in the Notch-Delta pathway GT 01 . The hard constraints discussed in the above setting are not unique to spatial transcriptomics and are also commonly found in the context of channel assignments in communication networks ( ZM 06 ) , carrier-sense multiple access networks ( DT 06 ; DDT 09 ) , and multicasting networks ( KAV 02 ; LRZ 06 ) among others. In this work, we study the problem of parameter estimation in n -dimensional Ising models that are hard-constrained to the satisfying assignments of a bounded-degree k -SAT formula \Phi expressed in CNF (Conjunctive Normal Form), using one sample. This means that we have access to a sample from an Ising model, conditioned that it only takes values in a subset S\subset\{\pm 1\}^{n} that is represented through the satisfying assignments of a k -SAT formula, adopting the framework from GKK 24 . Learning in truncated MRFs using one or multiple samples has been studied in the context of discrete product distributions truncated by the set of satisfying assignments of k -SAT formulas GKK 24 ; GGZ 25 , more generally by truncated sets with combinatorial structure FKT 22