Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample
Authors: Rohan Chauhan
Ioannis Panageas
Venue: ICLR 2026 Poster (2026)
Keywords: Ising Model
Truncated Statistics
Pseudo-Likelihood Estimation
Parameter Estimation
Primary area: learning theory

Abstract: 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.

LEARNING THE INVERSE TEMPERATURE OF ISING MODELS UNDER HARD CONSTRAINTS
Rohan Chauhan University of California, Irvine rmchauha@uci.. edu
Joannis Panageas University of California, Irvine ipanagea@uci.. edu
ABSTRACT
We consider the problem of estimating the inverse temperature parameter of an n-dimensional truncated Ising model using single sample. Given a graph G (V; E)) with n vertices, a truncated Ising model is probability distribution over the n-dimensional hypercube { {-1, where each configuration is constrained to lie in a truncation set _ {[1, 1)" and has probability Pr(ar) x exp( Ao) with A being the adjacency matrix of G. We adopt the recent setting of [Galanis al. S0DA' where the truncation set S can be expressed as the set of satisfying assignments of k-SAT formula. Given single sample from a truncated Ising model, with inverse parameter 3", underlying graph G of bounded degree A and S being expressed the set of satisfying assignments of k-SAT formula, we design in nearly (n) time an estimator A that achieves a consistency rate of O /v) with the true parameter 9 for k Z log(d?))
Our estimator is based the maximization of the pseudolikelihood. notion that has received extensive analysis for various probabilistic models without [Chatter- jee, Annals of Statisties '07] or with truncation [Galanis et al. SODA '24]. Our approach generalizes recent techniques from [Daskalakis et al. STOC '19, Gala- nis et al. SODA '24], to confront the more challenging setting of the truncated Ising model.
INTRODUCTION
Markov random fields (MRFs) are common framework for analyzing nigh-dimensional distribu- tions with complex conditional structures. A well-studied example of an MRF and the primary topic of inquiry in this paper is the Ising model (Ising, 1925). a probability measure PG,3, over all assign- 13a. The model is parameterized by a graph G = (V, E) and inverse temperature 3, taking the form JaG.s O exp (Ba AAr), where being the adjacency matrix of G. The simplicity of the Ising model has led to widespread adoption in fields disparate as statistical physics, finance, the social sciences, and computer vision, among others (see (Chat- terjee, 2007; Qin & Zhao, 2011; Harris, 2013; Wang et al., 2015) and the references therein for a brief collection of examples). These applications have, in turn, motivated a substantial body of research on efficient sampling (Bresler, 2015; Lubetzky & Sly, 2013; Sly & Sun, 2012), rigorous testing (Daskalakis et al., 201 2019a), and principled inference of the inverse temperature parameter and interaction matrix (Dagan al., 2020; 2021) under the framework of the Ising model.
ments o in the binary hypercube
Beginning from the work of (Chatterjee, 2007), there has been substantial interest in the task of estimating inverse temperature parameter 8, given only one sample
μG,8 and the graph G, using the maximum pseudolikelihood estimator of (Besag, 1975). This setup subsumes the setting of multi-sample estimation as samples of an Ising model over n nodes is equivalently a single sample of an nf Ising model over i disconnected components of 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 (Daskalakis et al., 2019b; Dagan et al., 2020). Interestingly, despite both static and dynamic phase transitions in model behavior as B varies which can render sampling computationally intractable (NP-hard) (Galanis al., 2016), it remains possible to construct consistent estimators of 3 and the interaction matrix A, provided that 3 0(1) (Dagan et al., 2020; 2021; Daskalakis et al., 2019b; Mukherjee al., 2022a).

---

(a) Low Temperature (8 31)
(b) High Temperature (33 (82)
Figure 1: Two typical spin configurations over the Ising model temperatures 31. .3 with 31 > B2 (equivalently at lower temperature 7j and a higher temperature T2 where T x 1/5). 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 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 the mea- sure remains intact, but also hard constraints: Certain configurations entire regions of the configuration space are excluded from the support of the distribution. Such cand-coostrained models (also called trancated) 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- biological framework for char- acterizing gene and protein expression in cells within organic tissue, relative to their spatial organi- zation. The local relationships between cells are often represented nodes in graph with edges linking cells together that are close in physical space (Eng et al., 2019). Associated with each node is of measurements expression to capture how the relationships between cells impact the pheno- type of a given node. The complex relationship between genes often forces certain configurations of expressions be infeasible. fact, the phenomenon of lateral inhibition can cause a cell expressing gene one to prevent its neighbors from expressing it well, instead causing them to express gene two, as seen in the Notch-Delta pathway (Ghosh Tomlin, 2001). 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 communication networks (Zafer & Modiano, 2006), carrier-sense multiple access networks (Durvy & Thiran, 2006; Durvy al., 2009), and multicasting networks (Karvo et al., 2002; Luen et al., 2006) among others.
outright forbidden, and
In this work, study the problem of parameter estimation in n-dimensional Ising models that hard-constrained to the satisfying assignments CNF (Conjunctive Normal Form), using one sample. This means that have access sample from an Ising model, conditioned that it only takes values in subset S C {=1]" that is represented through the satisfying assignments of k-SAT formula, adopting the framework from (Galanis al., 2024). The choice of the k-SAT framework is motivated by the fundamental observation that any truncation set S C {=1}" can be exactly realized the solution space of such formula, provided the number of clauses is sufficiently large. This representation is particularly advantageous for statistical inference, as the structural parameters, in particular the clause size It and the variable degree, serve natural controls for the complexity of the induced correlations in the analysis of the Maximum Pseudolikclibood Estimator (MPLE).
bounded-degree k-SAT formula expressed in
More generally, learning in truncated MRFs using one multiple samples has been studied in the context discrete product distributions truncated by the set of satisfying assignments of A-SAT formulas (Galanis et al., 2024; 2025), more generally truncated sets with combinatorial struc- ture (Fotakis et al., 2022), the hard-core model. and integer valued spins constrained over proper H H-colorings (Blanca et al., 2018; Bhattacharya & Ramanan, 2021). Our key deviation from the
2

---

aforementioned works stems from the fact that the Ising model is not a product distribution, and common tools used to control the concentration measure on the hypercube do not apply. This, moreover, induces two sources of interdependence, namely from the model itself and from the struc- ture of the truncation set. With this background in mind, we seek to address the following challenge.
Is it possible to efficiently learn discrete distributions with complex dependencies under hard constraints, having access to a single sample?
1.1
OUR RESULTS
Our main contribution is an affirmative answer the previous challenge, by providing a sufficient condition on the k-SAT formula that induces the truncation set, in terms of the maximum degree A of G. We begin by formally defining the class of truncated Ising measures that is the primary inquiry of this work. Given a graph G. with associated adjacency matrix A, and inverse temperature 8 we define the pmf of a truncated Ising model for any o {=13" to be
1
exp (Bor Ao) 1 E S}, Pro.s(o) == Zg.s
(Truncated Ising Model)
where 1 1 E S} captures the indicator function determining if E S and Za.s is renormalization term denoted the partition function. In our case, expressed as the set of satisfying assignments of bounded degree k-SAT formula &n.k.d 4 in constrained normal form. Formally, let @ be formula in conjunctive normal form over variables V = {Vi..... Un} and clause set C, subject to the structural constraints that each clause contains exactly & literals (variables or their negations) and each variable occurs at most clauses. We identify each configuration o E {-1, 1 with a truth 1. A configuration
assignment via the mapping where variable ;; is true if a; = 1 and false if o; a is then said to satisfy & if and only if every clause C E C contains at least one literal that evaluates frue under this assignment. Recall, any subset of the hypercube can be represented as the set of satisfying assignments of degree-d kAS formula, provided that d is sufficiently large.
Our main result- stated below a sufficient condition on the degree of the formula & in terms of the size of each clause k and the maximum degree A of the underlying graph G' of the Ising model, for computationally and statistically efficient estimation of the inverse temperature parameter B.
Theorem 1 (Informal Version of Theorem 2). Let be single sample from truncated, n- dimensional Ising model with inverse temperature f", where the truncation set is captured by the satisfying assignments of a k-SAT formula kn,k,d k.d and the underlying graph G has maximum degree A of order o(n' /9). For n sufficiently large, 3* O(1) and 2 (14A3 + log(d'k: + 1))), there exists an O(S 'n log(n)) - algoorithm which takes as input a and outputs an estimator 3 such that
cA 37
P | 3*|
S
> 99%, for a constant e > O independent of n, A,d,k.
Remark (Consistency). Notice when A is O(1,, our estimate achieves 0(1/ -m))ccoosisstncy matching the minimax rate for parameter estimation. Likewise, the restriction of A be on the order of o(n+ ensures the error of our estimator 3 is asymptotically diminishing and turn con- sistent.
Remark (Lower Bounds). We further note that Galanis et al. (Galanis et al., 2024) recently tablished a lower bound for learning discrete Boolean distributions, demonstrating that estimation poormatiion-hhorettice
impossible when & < log(d) - log(k) + O(1). This result relies on constructing a k-SAT instance with single satisfying assignment. Importantly, this lower bound extends to our setting, implying that our results are optimal up a constant factor when G is graph of bounded degree. While subsequent work (Galanis et al., 2025) has provided tighter bound, those techniques do not immediately translate to our context; the quadratic Hamiltonian induces a rugged energy landscape distinct from boolean product setting, necessitating different analytical tools.
1.2 TECHNICAL OVERVIEW
Given a langle-paramete exponential family like we focus on, a natural approach to estimating the parameter is to find the maximum likelihood estimate. However, the computational intractability of
3

---

the partition function Zp.s for Ising models (see (Galanis et al., 2016) and the references therein)
renders this approach infeasible. In light of these challenges, we utilize the maximum pseudolikeli- hood estimator introduced by (Besag, 1975) and provided below.
B = arg max
II Pr Pra.s(0: --)) = arg min B VE(M)
Σ EE|n]
log (arrrr (ro.s(ooloo-))) = arg min p(;; A, o.)
(MPLE)
We note that the second equality holds due to the monotonicity of the log(.) function. Towards demonstrating the consistency of the maximum pogg--peuuollkkeihhodd estimate B, we follow the first and second derivative paradigm outlined by Chatterjee (Chatterjee, 2007; Daskalakis et al,, 2019b; Galanis et al., 2024; 2025), which involves showing.
Pr V B 2 (3"; A, S O(vn) 2 1 o(1).
.
inf infsE(-B.B)
V (30: 2 ((n/A²) with probability 1 (11 over or ~ Pra..s.
The first condition ensures the derivative of the log-pseudolikellhood objective with respect to the true model parameters B divided by is close to O, which is the value of the gradient of d com- puted at the estimator, which in turn implies 3 is an approximate stationary point of the objective. Moreover, by demonstrating that the second derivative of the objective V A, or) is Q(n/ - strongly convex with probability 1 o(1) over a draw of the truncated Ising model, it implies that approximate stationary points of the objective are close in Euclidean distance to the optimum. These two facts combine to show the proximity of the optimum of the pseudolikelihood objective to 3..
Showing both of these conditions hold simultaneously is made complex due to the highly non- uniform measure induced by conditional dependencies of both the interaction matrix A and the truncation set S. To demonstrate the first condition, we craft upper bounds on the variance of the first derivative of Φ, using the technique of exchangeable pairs pioneered by (Chatterjee, 2007), which, when combined with Chebyshev's 's inequality, implies an upper bound in probability. The primary challenge of this work lies in establishing the second condition. Previous works which used the deterministic structure of the interaction matrix to guarantee the concavity of the objective. By contrast, in our setting, the second derivative governed by the local geometry of the truncation set S in the vicinity of the sample a. The Hessian V3 is computed by summing a function of the local s fields (a) (AA, o). where the support of this sum is limited to the valid neighbors of in S with respect to the Hamming distance"
To show that, with high probability under the truncated Ising model, sample has many neigh- boring configurations at Hamming distance 1, we construct an argument based on the Lovász Lo- cal Lemma (LLL), to guarantee the existence of a large number of satisfying assignments to & that differ from or in exactly one bit. Using this powerful tool, however, requires control of the probabilities of partial spin assignments, which, given the tendency of the Ising model to con- tract into arbitrarily small portions of the hypercube and exhibit long-range correlations, can prove challenging. Counteracting this, our argument conditions on nodes outside of a specially crafted independent set I of the graph G, which preserves the marginal distribution of any given spin Præ. [ar (0), ( 0; I,,,, Rn) despite limited to a small fraction of the support of the mea- sure, and collapses the Ising model into a product measure. To conclude the strong convexity of Ø(: A, or) it remains to show a lower bound on m. ) in probability via a coupling argument which exploits the underlying edge structure of the connectivity graph G.
We additionally note that the recent results on estimating Ising models using the pseudolikelihood approach (Dagan et al., 2020) rely on sophisticated concentration inequalities derived from the fast mixing nature of Glauber dynamics on the Boolean hypercube and their relation to the Gibbs mea- sure in order to conclude the strong convexity of the PL objective and bound the gradient with high probability. In our model, these powerful tools are not applicable due to the fragmented nature of the truncation set, rendering the domain of our measure into disconnected islands and make the Glauber dynamics non-Ergodic; the inequalities only imply concentration within a connected component of S. which may be too small to be informative. We lastly emphasize that our polynomial time algo- rithm does not scale with the size of the truncation set, enabling inference despite S being small with regards the entire hypercube.
'The Hamming distance metric counts the number of differing indices between two vectors. Thus, neigh- hor at Hamming distance is obtained by flipping exactly one index of
4

---

1.3 RELATED WORK
The literature of parameter estimation in Markov Random Fields, and over hard-constrained and truncated measures, is vast. In light of this, we mention a brief collection works relevant to our setting, and defer additional background and discussion to the appendix. Single sample estimation initiated by (Besag, 1975; Chatterjee, 2007) has yielded rich bounty of results ranging from the set- ting of the Ising model (Chatterjee, 2007; Bhattacharya & Mukherjee, 2018; Ghosal & Mukherjee, 2020; Dagan et al., 2020), peer dependent logistic regression (Daskalakis et al., 2019b; Mukher- jee et al., 2022a; Daskalakis et al., 2020), higher order Ising models (Mukherjee et al., 2022b), and robust inference over discrete distributions (Diakonikolas et al., 2021). (Bhattacharyya et al., 2021) demonstrated the feasibility of single-sample learning in the context of the hard-core model, a size-weighted distribution over all independent sets in a graph G; following up on this, (Galanis al., 2024; 2025) studied parameter inference in a product distribution truncated by the satisfying assignments k-SAT formula. The hard-constrained models studied this work are a subset of the literature analyzing efficient parameter estimation and learning in truncated (Daskalakis al., 2019c; 2018; Fotakis et al., 2022; De et al., 2023; Nagarajan & Panageas, 2020) and censored dis- tributions (Lugosi al., 2024; Plevrakis, 2021; Fotakis al., 2021).
PRELIMINARIES
2.1 NOTATION
We denote the set of {1, ........ as [n]. Vectors x E Rd are denoted with boldface, and matrices M Rm*x with capital letters. Given vector
(01, 0o.......... a,,) and subset I C [ni, let ay denote the length-|/ coordinate vector {a, i E [}. and a.; denote the vector a with the i-th element removed. We denote the probability of event AA over the untruncated measure parameterized by 3 as Pr,, and over the truncated Ising measure as (GG,,s(AA = Pr pr [A[S]. We often remove the explicit dependence on S and for clarity of explanation.
We will say estimator å is consistent with rate (f)( (or equivalently (m))-coosistent) with respect to the true parameter 3 there exists an integer ny and a constant C > such that for every no, with probability at least 1 o(1).
1 3 S-
Lastly, we call an entry a, of a to be flippable if both (a,, a-:) and (-o,, a-i) lie in S, and moreover we denote by (or) the indicator of the event that o; of flippable.
2.2 MAXIMUM PSEUDO-LIKELIHOO, ESTIMATION
Towards explicitly computing the (ogg))sseudllkellhooee objective and its associated derivatives, we begin by finding the conditional distributions of the individual spins conditioned on the rest of the assignment, Pra(a, (o_ Notice, when o; is not flippable, the conditional distribution trivially one, while for flippable i, the probability is given by the following:
exp(3m;(orra))
Pra(a;(a-i) cxp(-ām,(o)) cxp(3m;((r) where mi(or) = Σ Aijoj-
j=1
Denoting F(or) to be the set of flippable variables in ar, the negative log pseudo-likelihood objective Φ(3; A, ) can be written explicitly follows:
b(3: A, =
Σ iEF(O)
log (Prs(a.la-i))
(2.1)
= Σ
(log (oxp(_(mm(()) + exp(3m,(o))) tEF(o)
(m,(a)o.)
In the sequel, we drop the reference to A in the pseudo-likeliton likelihood when the interaction matrix is clear. The first and second derívatives of the objective (2.1) with respect to the inverse temperature
5

---

parameter B, denoted by Φ1 (1: V=)(B:A,,), (300(3A,,0) given below:
mi(or²²
(1: = Σ (m/(o)(tanh((mm(())) - -.)), x2(3:0)= iEJ(o)
Σ
cosh cosh (Bm,,o))
(EF(O)
Note that the negative Nog-pseudo-likelliodd is convex the second derivative is always negative (sum of squares).
2.3 AN AUXILIARY LEMMA
In analysis, demonstrating the consistency of estimator, we frequently require the existence of combinatorial objects, such as satisfying assignments to a k-SAT formula or fulfilling specific constraints without their explicit construction. Such existence questions often reduce to avoiding a collection of undesirable events, each of which occurs with low probability and exhibits limited dependence on the others. This setting is naturally addressed using the probabilistic method, and in particular, the Lovász Local Lemma.
Lemma 2.1 (Symmetric Lovász Local Lemma). Given a collection of events (ein) where each event A; satisfies Pr(A.) p and each event is mutually independent from all but at most d other events. If
e. (d 1) S 1,
(Symmetric LLL)
then Pr (N==1 A:) > O, where A, denotes the complement of A, and refers to Euler's number.
3 LEARNING TRUNCATED ISING MODELS
In this section, we prove our main result, i.e., we provide sufficient condition on the "complexity" of the k-SAT formula 4, (and by extension the truncation set S) in terms of the size of the clauses k, the degree of the formula and the maximum degree the graph A for efficient estimation of the inverse temperature parameter B. In advance of proving our result, we lay out some mild assumptions on the interaction matrix A and Ising model JGG,, which have been employed in past works (Galanis al., 2024; 2025; Dagan et al., 2020; Daskalakis et al., 2019b; Chatterjee, 2007; Bhattacharya & Mukherjee, 2018)
Assumption 1. Within our model (Trancated Ising Model), assume
A is the adjacency matrix of a connected graph over n nodes, with maximum degree A be- ing o(n /6) and entries Aig E - } representing positive negative interactions.
The inverse temperature parameter B lies in the open interval (-
The truncation set S is the set of satisfying assignments k-SAT + in conjunctive normal form.
The assumption of graph connectivity ensures that the interaction matrix contains sufficient signal energy for consistent parameter estimation. This requirement plays a role analogous the lower bounds the Frobenius norm of the interaction matrix posited in (Chatterjee, 2007; Daskalakis et al., 201 9b; Bhattacharya & Mukherjee, 2018). Absent such a structural guar- antee, the log-partition function Zs.s may fail to diverge asymptotically with n, which prevents the pseudolikelihood objective from achieving consistency. This pathology is exemplified by the Curie- Weiss model with couplings scaling 1/me; there, the Frobenius norm of the interaction matrix is (1). In contrast, our connectivity and degree assumptions imply that the squared Frobenius norm of A scales as 2(nnA²) which diverges infinity, thereby ensuring the problem is well cell-posed.
Remark (Assumptions).
While general specifications of the Ising model allow for arbitrary coupling strengths A.j R. we restrict the interaction magnitudes to uniform value |A,y 1/A towards isolating the structural component of peer influence. This constraint posits that the social pressure exerted by any single neighbor is functionally equivalent, thereby modeling a "peer effect" (Bertrand et al., 2000; Sacer- dote, 2001; ; Duflo & Saez, 2003) where individual decisions are driven by the collective consensus of the local group rather than the idiosyncratic intensity of specific dyadic relationships. By imposing this homogeneity,
ensure that the model captures the emergent coordination arising from net- work topology and group alignment, rather than being dominated by outliers with arbitrarily strong pairwise connections.

---

The formal version of main result is given follows.
Theorem (Main result). Let be a single sample from truncated, n-dimensional Ising model satisfying Assumption 1. For all k 2 Tog(L+exp(-
12 k+1)), if n. is sufficiently large, there exists an O(A3n log n) time algorithm which takes input a and ouiputs estimator B such that
P |/ 3-1 CA31
2 99%, for a constant c <>> O independent of n, A d,
Remark (The algorithm). We compute 3 in time O log by running projected gradient de- scent (PGD) on the normalized peeppudollikklhooodd objective ((33 σr). Standard results from convex optimization (e.g.. (Boyd & Vandenberghe, 2004)) imply that PGD converges an e-optimal solution in (x (1/e)) iterations, where 6. is the condition number of the objective, that the ratio of the smoothness (i.e., the Lipschitz constant of the gradient) to the strong convexity param- eter. In the sequel (Section 3.3), we demonstrate that the pscudo-likelihood objective is strongly convex with parameter ()n implying the normalized objective is (2 2(1//A))strongg vex. This, combined with an upper bound of 1 on the norm of the normalized gradient of the log-pseudolikelioood, yields the condition number of the objective is x ( Due the sta- tistical limitations of the pseudolikelihood estimator, whose distance from the true parameter 3 can be as large as O(A*/VT). we e 1/vn. Obtaining accuracy of requires O & log n) iterations, each requiring (nn) time, resulting in an overall runtime of O(A log n).
To prove Theorem 2, we begin by explicitly demonstrating how the conditions on the first and second derivatives of the (B3 σ) imply the consistency of the MPLE 3 in Section 3.1. We then establish the conditions on the first derivative in Section 3.2, and the second in Section 3.3.
3.1 ROADMAP FOR PROVING THEOREM 2
In this subsection, we demonstrate the relationship between the derivatives of the (log)- pseudolikelihood and the estimation error |3 8-
Lemma 3.1. Let 3 E (-B, B) be the true parameter of the truncated Ising model pa,s and B be the MPLE. It follows that with probability 1
o(1)
| (3
|/ - - ming $2(3:0)
Proof Sketch. We relate 3 with S*, via smooth interpolation of both the parameter values themselves As the derivative of the pseudolikelihood at is zero, we note that s(1) = 0. The fundamental theorem of calculus implies
Sketch.
((t) = 1,3 + (1 - t),"", and the gradient s(t) (B (z)
-(3 - 3r 3e) = -(1) = l'- s' s((t) = (8 (3)) L/' oz (
The lemma follows from So (3(())) mii-)e(BBBB) (3:30 or) and Φ2 (2(3 2 0.
With this lemma in hand, demonstrating Theorem reduces to showing (B";: ((vr) and (2(3; o = (n)/A3) simultaneously with probability 1 - o(1).
3.2 ANALYSIS OF FIRST MOMENT
The lemma below establishes the upper bound on di (3; o). To demonstrate an upper bound on &1 (1 in probability, we use the technique of exchangeable pairs (Chatterjee, 2007) to construct a bound on its variance. With the variance controlled, we invoke Markov's 's inequality to conclude (1(3; o that concentrates around its mean.
Lemma 3.2 (Upper Bound on 01 σ) in Probability). Fix a constant > O. The log- pseudolikelihood o(3: o) of truncated Ising model fulfilling Assumption 1 satisfies the following upper bound in probability, for all
(12 4B)m
Præ (3:00) S
21
5
7

---

3.3 SECOND DERIVATIVE BOUND
For reference, we recall the expression for the Hessian of the log pseudo-likelihodd,
of)(3:
( cosh (3m; c,(o).
(2(3:
0g²
The primary aim of this section is to demonstrate the following lower bound in probability.
Lemma 3.3 (Lower Bound on (2 or) in Probability). The log pseudolikelihood 6(3; or) of a Ising
model, truncated by a k-SAT formula with k: 2 44 (1+logdd +++1))))+))))) fulfilling Assumption satisfies
(oxppl (x(++xx(-22B))
the following lower bound in for all 3 E (-B, B)
106² (3; nexp(- B) (B(8kd)
(24 + (4488)
Prg-
0²3
0.
We prove this claim in steps, by firstly guaranteeing there linear number of flippable variables U; E V, which contribute to the value the second derivative, and secondly ensuring the value of each term in the sum is bounded below by constant.
3.3.1 ENSURING FLIPPABILITY
Given sample σ, the flippability of variable a, under the kASAT formula & is characterized by the condition that every clause containing o, is satisfied by at least one other variable in the clause. Consequently,
is not flippable if there exists clause C' such that all other variables by E CVa are assigned values that fail to satisfy the clause an antagonistic configuration. Under assumptions, the truncated Ising model may be defined at arbitrarily low temperatures, including values of 3 = ((1) that exceed the critical threshold. In this regime, standard concentration-ol measure tools, such log-Sobolev inequalities or Dobrushin-type conditions, are no longer valid and fail to yield meaningful bounds. This makes it significantly more difficult to lower bound the probability of antagonistic configurations, and, by extension, to bound the probability that given variable is flippable.
Towards providing such bound, we construct an independent set within the graph G, such that the marginal distribution of the spins within J, conditioned on the variables outside of the independent set V I, collapses into product distribution, circumventing the above difficulties. Indeed, the assignment of the remaining nodes ov is given follows, V (a) instead of being random variables, they are now fixed constants.
distribution of σ conditional
with m;
Pro((r)ovyz) & exp 23
VV (o)o)) Σ m EET
where m, (((a)= Σ Agj
JEVV
One of the issues that arises from conditioning our graphical model on V is the natural truncation of the k-CNF formula d; erasing the variables outside of the independent set from & transforms into a new formula d', which contains only variables from I. An inherent concern in the selection of the independent set is the presence of clauses in T' containing only few variables, i.e., of size o(k), which can significantly skew the marginal distributions away from uniformity. To address this, we show that there exists an independent set C that intersects a linear fraction of the variables in every clause, ensuring sufficient coverage and mitigating this issue.
Lemma 3.4. Let G be graph with maximun degree A of order o(n. /60 and & be a k-SAT formula. If k > 1043 3 (1 + log (og(dk=²)), then there exists an independent set C V such that V', t truncated on V I, a Xk-SAT formula where X 1/4A3.
Proof Sketch. To begin, we describe an algorithm that maps bijections of the vertex set to indepen- dent sets in the graph G. Formally, given a map p V [n], we construct an independent set by selecting all vertices E V such that p(u) p(v) for all (()). This selection criterion ensures that no two adjacent vertices are included in the set, as any edge {u, v} E E prevents both u and v from satisfying the condition simultaneously.
8

---

Under the uniform measure over all maps p. the event that vertex is selected into the independent set depends only on the relative rankings under p of v and its neighbors. This locality implies that for any pair of vertices u, E V with graph distance d(u, v) 3, the corresponding selection events are independent. Leveraging this property, for each clause C, we can extract a subset C' C C consisting of variables whose neighborhoods are pairwise disjoint, implying the event of selection for all elements u E C' are mutually independent, yielding the selection events for all variables in C" mutually independent. This allows us to treat the number of selected variables in C" 7u as sum of independent Bernoulli random variables, enabling the use of Chernoff bounds, and consequently, we obtain an exponential upper bound on the probability of the bad event that |C n I| < Al.
To establish bound on k in terms of d and A that ensures the existence of marking with the de- sired properties, we invoke the symmetric version of the Lovász Local Lemma (Lemma 2.1). Each variable appears in at most d other clauses, and the bad event corresponding to a variable's inclusion in the independent set depends only on the configuration of variables within its two-hop neighbor- hood. Since this neighborhood contains most A + 1 variables, each bad event is dependent on at most kd( + 1) others. By the symmetric Lovász Local Lemma, that the associated condition is met, then with positive probability, there exists independent set satisfying the required condition.s
sufficiently large so
exp (- 8(A2 + +1) +1) (kd(A² + +1) < 1.
When A 2,ifk logg(ddhh (2): A satisfies this requirement, completing the proof.
Armed with the guarantee that the truncated k-SAT formula &' contains sufficient number of vari- ables each clause, we relate the flippability a given variable v; to the satisfiability of select clauses solely through elements of the independent set I. Indeed, sufficient condition for vari- able u, to be flippable is that every clause containing v, is satisfied by at least one variable in the independent set T. We capture this requirement using the following indicator function:
s)( = 1 (every clause containing j is satisfied by some i E 1}.
This reformulation particularly valuable because translates the notion of flippability, which originally depends on the full joint distribution of the Ising model at arbitrary inverse temperature B, into condition over the structure of the product distribution induced by the independent. As the selection of can be made independently of the spin configuration and is governed by local rules (e.g., via randomized greedy selection based on random bijections), the probability that 8, (or = 1 can be effectively analyzed using standard concentration inequalities such Chernoff bounds, enabling explicit probabilistic guarantees on the flippability variables, despite the tendencies of the underlying Ising model exhibiting long-range dependencies.
To this end, we now establish a sufficient condition on k that ensures all variables are flippable with constant probability.
Lemma 3.5. Given a sample a Pr S. such that the k-SAT formula t which induces the (runcation set S, satisfies the following clause size bound
413 + log(d 11) k 2
log(1 [ + exp(-213
"Then for A 2 5, there exists independent set 1 following Lemma 3.4 such that
Pre- ((s;,)(s;(a) = 1|/ VjEV\I.
Moreover, for any set V C I we can find a collection of R C V with |R] Z |V'1/22d)2 that are neighborhood disjoint in the interaction graph of &b such that for all subcollections {i1,..., tt) C R,
Pr ,9 (o) lle,, (a) 1,..., C._ (0) = =1] 1/2.
This term scales
28 A (d)

---

3.3.2 BOUNDING THE MAGNETIZATIONS
now remains to demonstrate that the squared magnetizations mo( are bounded below with constant probability over a draw of the truncated Ising model. We begin by providing a conditional lower bound (o).
Lemma 3.6. The magnetizations, mi(o)= following relation.
= =Eje(n) A of the truncated Ising model satisfy the
exp(-B)
E3
Pro (eg(a) =
A
This lower bound is only non-trivial when both realizations (a; (3) and (ai, -7)) are feasible under the truncation set, ie ()) 1; likewise, this term only contributes to the Φ2 σr) if e = 1. Towards maximizing the second derivative, we wish to select sequence of edges (i,j) such that both (or = and ey(ar) = 1, that is, both endpoints are flippable. As each element i; E has at least one neighbor in V \ I, and the graph has maximum degree A, I' S I of size ['' > x such that no two elements I' share any common neighbors. With this independent set /', define vertex bijection h V V as follows. For each I', assign h(v) to be a unique neighbor of v in V. T. For vertices outside /', we assign the remaining mappings arbitrarily, while maintaining the constraint that h remains bijection V. Using Lemma 3.6 and the above bijection h, we can find lower bound on the entire conditional second derivative.
construct subset
Lemma 3.7. Over the truncated Ising model, given a bijection h V - V defined by the above procedure, the conditional second derivative satisfies the following first moment bound.
12 exp( B) Ex (m((6))((0(00)))) 2
2A (4kd))
Establishing Lemma 3.3 Armed with the lower bound on the conditional expectation of 62 (3; or), obtain our final lower bound we control the variance Ex= Eg- (m] with the method of exchangeable pairs, in similar fashion to Lemma 3.2. We then apply Chebyshev's inequality to the conditional variance obtain our bound probability.
CONCLUSION AND FUTURE WORK
In this paper, we present an affirmative answer the challenge of single sample learning the trun- cated Ising model, at all temperatures 3 E ((1), giving sufficient condition for the truncation set to ensure consistent inference, and extending the existing framework beyond boolean product dis- tributions. Towards this goal, we craft concentration inequalities for the first and second derivatives of the pogg-seuuolikklbooodd via local connectivity arguments over the domain.
The present work opens the door to important future questions (i) Given the above framework, does analyzing measures with random Hamiltonians, like those of the Sherrington SheriintoonKKrkkaatroo Kirkpatrick model, alleviate the dependence graphical models apply to the constrained setting? (iii) Is there a way to simultaneously remove the 166 assumption on the maximum degree of the graph while improving the rate of consistency?
A? (ii) Do logistic regression techniques used estimate untruncated
ACKNOWLEDGMENTS
Joannis Panageas is supported by NSF grant CCF-2454115. Part of this work was done while Rohan Chauhan was visiting Archimedes AI.
10

---

REFERENCES
Marianne Bertrand, Erzo FP Luttmer, and Sendhil Mullainathan. Network effects and welfare cul- tures. The quarterly journal of economics, 11503):011-1055, 2000.
Julian Besag. Statistical analysis of non-lattice data. Journal of the Royal Statistical Society Series D: The Statistician, (4(3):179-195 1975.
Bhaswar B Bhattacharya and Sumit Mukherjee. Inference in ising models, 2018.
Bhaswar B. Bhattacharya and Kavita Ramanan. Parameter estimation for undirected graphical mod- cls with hard constraints, 2021. URL https: /ttp/vxxvv/v///////////////aa org.///iiooroooooooe http//a////00 2008 09925.
Arnab Bhattacharyya, Rathin Desai, Sai Ganesh Nagarajan, and Ioannis Panageas. Efficient statistics for sparse graphical models from truncated samples. In International Conference on Artificial Intelligence and Statistics, pp. 1450-1458. PMI.R, 2021.
Antonio Blanca, Zongehen Chen, Daniel Stefankovië, and Eric Vigoda. Structure learning of h- colorings. In Algorithmic Learning Theory. pp. 152-185, PMLR, 2018.
Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press,
Cambridge, UK. 2004.
Guy Bresler. Efficiently learning ising models on arbitrary graphs. In Proceedings of the forty- seventh annual ACM symposium on Theory of computing, pp- 771-782, 2015.
Sébastien Bubeck
Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):21-335,
Sourav Chatterjee. Estimation in spin glasses: A first step. 2007.
Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis Kandiros. Learning ising models from one or multiple samples, 2020. URL 09370.
abs/2004.
Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Surbhi Goel, and Anthimos Vardis Kandiros. Statistical estimation from dependent data, 2021. URL https: //tttpps/axxxx /ttp//..xx///////////./ abs/ 2ts/2207.09773
Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis. Efficient statistics, in high dimensions, from truncated samples. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 639-649. IEEE, 2018
Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath. Testing ising models, 2019a.
URL www.tttsss//aatti http://wwwwwooo....o/oooooo
oowooorggoooo... abs /1ls/11122 21.66...00 03147.
Constantinos Daskalakis, Nishanth Dikkala, and Ioannis Panageas. Regression from dependent ob- servations. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, pp. 881-889, 2019b.
Constantinos
Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Compu- tationally and statistically efficient truncated regression. In Conference on learning theory, pp- 955-960. PMLR, 2019c.
Constantinos Daskalakis. Nishanth Dikkala, and loannis Panageas. Logistic-regressionn with peer- group effects via inference in higher order ising models, 2020. URL wwt.h:t/////attti abs/2000 08259.
Anindya De. Shivam Nadimpalli, and Rocco A Servedio. Testing convex truncation. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4050-4082 SIAM, 2023.
Ilias Diakonikolas, Daniel M Kane, Alistair Stewart, and Yuxin Sun. Outlier-robust learning of ising models under dobrushin's 's condition. In Conference on Learning Theory, pp. 1645-1682, PMLR, 2021.
11

---

Esther Duflo and Emmanuel Saez. The role of information and social interactions in retirement plan decisions: Evidence from a randomized experiment. The Quarterly journal of economics, 118(3): 815-842, 2003.
Mathilde Durvy and Patrick Thiran. A packing approach compare slotted and non-slotted medium access control. In Proceedings of IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications, 2006.
Mathilde Durvy, Olivier Dousse, and Patrick Thiran. On the faimess of large esma networks. IEEE (770):099-1114, 2009.
Journal on Selected Areas in Communications,
Chee-Huat Linus Eng. Michael Lawson Qian Zhu, Ruben Dries, Noushin Koulena, Yodai Takei, Jina Yun, Christopher Cronin, Christoph Karp. Guo-Cheng Yuan, et al. Transcriptome-scall super-resolved imaging in tissues by ma seqfish+. Nature, 568(7751):235 239, 2019.
Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos. Efficient algorithms for learning from coarse labels. In Conference on Learning Theory, pp. 2060-2079. PMLR, 2021.
Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos, Efficient parameter estimation of truncated boolean product distributions, 2022. URL https://p/// /ttx/aaxivv///// paaxxiv.oreee orgg /2tp://bbb/200/000//
Alan Frieze and Michat Karoński. Introduction to random graphs. Cambridge University Press, 2015.
Andreas Galanis, Daniel Stefankovic, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic ising and hard-core models. Combinatorics, Probability and Computing, http:/
5004)5500-559 February 2016. ISSN 1469-2163. doi: 10.10177499634443350000000 URL
Andreas Galanis, Alkis Kalavasis, and Anthimos Vardis Kandiros. Learning hurd-constrained mod- els with one sample. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp- 3184-3196. SIAM, 2024.
Andreas Galanis, Leslie Ann Goldberg, and Xusheng Zhang. One-shot learning for k-sat, 2025. abs 2502 07135.
URL
Heidi Gebauer, Tibor Szabó, and Gábor Tardos. The local lemma is asymptotically tight for sat. Journal of the ACM (JACM), 63(5):1-32, 2016.
Promit Ghosal and Sumit Mukherjee. Joint estimation parameters in ising model. 2020.
Ronojoy Ghosh and Claire Tomlin. Lateral inhibition through delta-notch signaling: piecewise affine hybrid model. In International Workshop on Hybrid Systems: Computation and Control, pp. 232-246. Springer, 2001.
Heng Guo, Mark Jerrum, and Jingeheng Liu. Uniform sampling through the lovász local lemma. Journal of the ACM (JACM), 66(3):1-31, 2019.
Linus Hamilton, Frederic Koehler, and Ankur Moitra. Information theoretic properties of markov random fields, and their algorithmic applications. Advances in Neural Information Processing Systems, 30, 2017.
Kathleen Mullan Harris. The add health study: Design and accomplishments. 2013.
Erst Ising. Beitrag zur theorie des ferromagnetismus. Zeitschrifi für Physik, 31(1):253-258, 1925.
Jouni Karvo, Samuli Aalto, and Jorma Virtamo. Blocking probabilities of multi-layer multicast streams. In Workshop on High Performance Switching and Routing, Merging Optical and IP Technologie, pp. 268-277, 277. IEEE, 2002.
Eyal Lubetzky and Allan Sly. Cutoff for the ising model the lattice. Inventiones mathematicae, 191:719-755, 2013.
Brad Luen, Kavita Ramanan, and Ilze Ziedins. network with controls. 2006.
Nonmonotonicity of phase transitions in a loss
12

---

Gábor Lugosi, Mihalis G Markakis, and Gergely Neu. On the hardness of learning from censored and nonstationary demand. INFORMS Journal on Optimization, 6(2):63-8) 83, 2024.
Somabha Mukherjee, Ziang Niu, Sagnik Halder, Bhaswar B. Bhattacharya, and George Michai- lidis. High dimensional logistic regression under network dependence, 2022a. URL https: / //arxiv.org abs 22100.1111.. 03200.
Somabha Mukherjee, Jaesung Son, and Bhaswar B Bhattacharya. Estimation in tensor ising models. Information and Inference: Journal of the IMA, (4)4:4457-11000 2022b.
Sai Ganesh Nagarajan and Ioannis Panageas. On the analysis of em for truncated mixtures of two gaussians. In Algorithmic Learning Theory, pp. 634 659. PMLR, 2020.
Lars Onsager. Crystal statistics. i. two-dimensional model with order-disorder transition, Phys- ical review, 65(3-4):117, 1944.
Orestis Plevrakis. Learning from censored and dependent data: The case of linear dynamics. In Conference on Learning Theory, pp. 3771-3787. PMLR, 2021.
Peiwei Qin and Jieyu Zhao. A polynomial-time algorithm for image segmentation using ising mod- els. In 2011 Seventh International Conference on Natural Computation, volume 2, pp. 932-935. IEEE, 2011.
Bruce Sacerdote. Peer effects with random assignment: Results for dartmouth roommates. The Quarterly journal of economics, 116(2):681-704, 2001.
Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 361- 369. IEEE, 2012.
Michel Talagrand. Spin glasses: a challenge for mathematicians: cavity and mean field models, volume 46. Springer Science & Business Media, 2003.
Michel Talagrand. Mean field models for spin glasses: Volume Basic examples, volume 54. Springer Science & Business Media, 2010.
Yu Wang, Guanqun Cao, Shiwen Mao, and R. Mark Nelms. Analysis of solar generation and weather data in smart grid with simultaneous inference of nonlinear time series. 2015 IEEE Conference Computer Communications Workshops, INFOCOM Workshops, Hong Kong, China, April 26 May 1, 2015, pp. 600-605. IEEE, 2015.
Murtaza Zafer and Eytan Modiano. Blocking probability and channel assignment in wireless net- works. ieee transactions Wireless communications, 5(4):869-88) 879, 2006.
13

---

Contents
A Related Work and Additional Background
14
A.1
Conjunctive Norm Formulae
15
A.2
Exchangeable Pairs
15
Algorithm For Maximizing the Pseudo-Likelihood
16
Omitted Proofs of Section 3.1 (Proof of Theorem 2)
17
D Omitted Proofs in Section 3.2 (Proof of Lemma 3.2)
17
E Omitted Proofs of Section 3.3 (Strong Convexity of the Pseudo-L Houdoo-ikelihood)
19
E.1 Proof of Lemma 3.4
19
E.2 Proof of Lemma 3.5
22
E.3 Proof of Lemmas 3.6 & 3.7
24
E,4 Proof of Lemma 3.3
25
Applications
28
A RELATED WORK AND ADDITIONAL BACKGROUND
The Ising model originated as a mathematical model of ferromagnetism on subgraphs of the lat- tice 2d, capturing local interactions in physical systems. Ising solved the one-dimensional case in his thesis (Ising, 1925), while Onsager later resolved the two-dimensional case (Onsager, 1944), revealing a continuous phase transition between ferromagnetic and paramagnetic states. Beyond low dimensions, the Ising model also serves as foundational example of spin glasses, aiding both condensed matter physics and probability theory in understanding complex magnetic materials and high-dimensional correlated loss landscapes (Talagrand, 2003; 2010).
Our inquiry into the Ising model will be statistical nature, concerning the consistent estimation of the inverse temperature parameter under the presence of truncation using a single sample. Despite the seeming simplicity of this task, the presence of phase transitions yields to be theoretically impossible in certain regimes; difficulties our task is our graph G, by extension interaction tensor A, is arbitrary (although of somewhat bounded degree), and thus our results hold in regime that is neither fully locally connected or mean-field, The first work to prove such a result was (Chatterjee, 2007), who via use of the technique of exchangeable pairs, variation Stein's inequality to prove variance bounds, was able to demonstrate the consistency of the maximum pseudolikelihood estimate derived from single sample(an objective that will expounded on the sequel) given the log partition function FG,3.R log( 3., is diverges with in the large data limit. As an example, when this seemingly innoucous assumption is not upheld, under the mean field Curie-Weiss model, i.e.
results stand in light of these challenges. One of the primary
Prew(a)
Zg exp
Σ i.jE/m]
n 0;03
(Curie-Werl Weiss)
consistent estimation impossible, as simple calculus yields that limn-+00 FG,B.n = O()). More- over, if 3 diverges to infinity with the psuedolikelihood objective ceases to be strongly concave, collapsing the Fisher information, and rendering estimation impossible. Beyond the estimation of the inverse temperature, (Mukherjee al., 2022b) was able to extend the regime of Chatterjee (Chat- terjec, 2007), demonstrating results for the joint estimation of the inverse temperature and the external field h. Viewing the task of estimating the inverse temperature structure estimation
14

---

parametric class of interaction matrices, i.e parameterized by B. (Dagan et al., 2020) generalized this setting to provide learning guarantees for large classes of parametric spaces, relying on a clever use of conditioning use Dobrushin's 's condition at all constant temperatures.
Beyond single sample learning, viewing the Ising model as a Markov random field, there is a larger body of work devoted to structure learning of the graph underlying the model using multiple sam- ples. In a breakthrough work Bresler (Bresler, 2015), demonstrated how to effciently estimate the strength of links in the graph underlying the Ising model by way of bounding the marginal influ- ence each node recieves. Building on this, (Hamilton et al., 2017) generalized this work to subsume models with higher order interaction terms and multiple possible spin states.
A parallel line of work has also investigated the feasibility of learning Markov random fields under hard-constrained distributions with single sample. This line of work commenced with (Bhat- tacharya & Ramanan, 2021) studying the fugacity parameter of the hard core model, i.e. prob- ability distribution over independent sets over graph E {0, 1)", where o, = 1 indicates the node is included in the independent set
(V; E) represented by binary vectors
Pr N (o) ZG.
II 1fau o. S 1}.
(Hard Core Model)
(u,0)EE
Following up on this (and closer to our setting), (Galanis et al.. 2024) considered the feasibility of learning boolean product distributions over truncated portions of the boolean hypercube, making use of the tilted-k-SAT model over S C {0, 13"", where defined to be the set of solutions of fixed bounded degree k-CNE formula T.
Pro(or) Zg cxp
3 os iEjm]
1fo e s}
(Tilted K-SAT)
Lastly, there has been a substantial amount of interest constrained normal form formulae. The literature is degree setting, it is well known from (Gebauer et al., 2016) that the satisfiability threshold d S 2h/2), that is the regime of the degree parameter with respect to the clause size is guaranteed to have a solution, coincides with the ability to apply the Lovascz Local Lemma (Guo et al., 2019), powerful application of the probabilistic method. Moreover, there has been substantial inquiry into random k-CNF formulae and their solutions, as function of the clause density is the number of clauses in the formula and the multitude of other phase transitions governing the intrinsic geometry of the solution space, i.e. how do solutions cluster together and what can be said about local connections between them. Our results in both settings, take hold in the Lovascz Local Lemma regime where a solution under an average draw has many neighbors comminng-distame one away in S C 1)
and we only recount the literature, pertinent to setting. In the bounded-
m/n, where m
As first step towards estimating the inverse temperature, our work lays the statistical groundwork to guarantee there exists an objective whose objective yields consistent estimator for / and an algorithm to efficiently find it. This can be seen as a generalization of both regimes, as the Ising model with external field generalizing the tilted-k-SAT model by introducing quadratic interaction term and extending the external field i to be an arbitrary vector in the n 1-sphere, i.e ||h||2 S 1, rather than the all ones vector. Beyond deterministic truncation, results are the first to hold the broader class solution sets under random truncation.
A.1 CONJUNCTIVE NORM FORMULAE
Conjunctive normal form (CNF) is a canonical way of expressing Boolean formulas as conjunction of disjunctions, or cquivalently, as an "AND" of "OR" clauses. Each clause is a disjunction of literals, where a literal is either Boolean variable or its negation. A CNF formula is said to be a C-CNF formula (or a k-SAT instance) if every clause contains exactly & literals. For example, (x) V - V ax)) A (-#1 V V 25)) is 3-CNF formula with two clauses.
A.2 EXCHANGEABLE PAIRS
In the context of the Ising model, the method of exchangeable pairs provides a powerful technique for obtaining nonasymptotic variance bounds for functions of the boolean hypercube. In the context
15

---

of the Ising model HG.8, given function f (-111) R, to bound Var, the exchangeable pairs method constructs pair (a, such that (ar o') (o's σ)) and the transition from to o is obtained via a single-site Glauber dynamics step (in our case truncated Glauber dynamics expanded on in the sequel).
Concretely, let o' be obtained by resampling the spin at a uniformly chosen site accord- ing to the conditional distribution Pre,a(: dv) Then (a, ) is exchangeable pair. Let Flo, o [[f(o) f(o')) "oo')loss -i... The variance of f can be bounded via
1 (ar,(f) - 2 -(o))
Under Lipschitz continuity with respect to the Hamming distance, this expression can be further bounded by quantities involving local influences and conditional variances, allowing for the control (f)) in terms of the geometry of G and the interaction strengths Aij-
B ALGORITHM FOR MAXIMIZING THE PSEUDO-LIKER SEEUDO-LIKELIHOOO
In this section, we present a polynomial-time algorithm for optimizing the pscudo-likelihood ob- jective using projected gradient descent. To guarantee convergence the optimum, we rely on the following lemma from (Bubeck et al., 2015).
Lemma B.1 ((Bubeck et al., 2015) Theorem 3.10). Let f be a- otsstroggy convex and X- smooth on the convex X. Then projected gradient descent with step-size 1) = 1/2, satisfies for t 2 O.
| x 113 exp(at/A)]] x" 1
Therefore, setting R = ||x] - x" 2|2 and / = 2(A/a)((ogg())) R)) - log(()) guarantees that ||x, - xx x"112 S
Given the 2(n/A3)-stroan >-stonn convexity of the pseudolikelihood function (Lemma 3.3) and the 1-
Lipschitz continuity of its gradient, we apply projected gradient descent (PGD) with step size to obtain a 1/ /n-acurrate estimate of the MPLE. The algorithm presented Algorithm
Algorithm Projected Gradient Descent
1: Input: Vector sample a, Magnetizations m.(o) E, Jj k-SAT Formula + 2n,k.d
2: Output: Maximum Pseudolikelihood Estimate 3
3: Initialize: 5 = 0, grad = +00 = flippable indices F(a)
4: for i in [1....,.] n do
5: if (-oi, a- is satisfying assignment of & then
6:
F((r) - F(r)
7: end if
8: end for
9: t+0 0
while Igrad] vī
do
11:
grad - EieF(o) (m:(o)(a; (an)()"m,;o)))
12:
ge+1 + 8O ngrad
13:
t t
14:
if ge+ < B then
ge+1 +- --B
16:
end if
if ge+1
then
18:
ge+ + B
end
20: end while
return 8,
16

---

C OMITTED PROOFS OF SECTION 3.1 (PROOF OF THEOREM 2)
In this section, we give proof of Theorem 2, in the process demonstrating Lemma 3.1.
Proof of Theorem 2. Recall the first and second derivative bounds proved in Lemma 3.2 and Lemma 3.3, respectively
Prg. (3)(3 (12 4B)n
(3: σ)
nexp( B)
(24 8B)
2 1- and Præ
2
03
(8kkd))
n
The union bound implies that the event A (ar evn, minse(-B.an)) B, Φ2(0;; B) 2 {(m/A3) occurs with probability o(1).
((()) (0;(0;;
To conclude the claim, we relate 3 with 3*, through smooth interpolation of both the parameter values themselves ((t) = t + (1 - -)33" and the gradient s(t) = (3 (3((t)); Via the chain rule, we notice that st) = (3 -)(()))))) The fundamental theorem of calculus implies
-(3 = s(0) = f. s'(f)dt = - J. (3(());
The log pseudolikelihood is a convex objective, 22(3:0) 2 0, for all 3 E (-B, B) and a A yielding.
3"11"111133 ,o)l (8 (8- o2(B(1);
2 - 3²)
min 32(3:0).
BE( BB
Rearranging this expression and using the fact that o E A.
(B))
A3 (v7) for all a E A.
|B - 1 Be(BBBB 22 (2(3:0
S 0
Recalling that A with probability 1 o(1) proves the desired claim.
D OMITTED PROOFS IN SECTION 3.2 (PROOF OF LEMMA 3.2)
In this section, we provide a proof of the upper bound in probability for the first derivative of the sog-sseudllikelhoodd objective, restated below for reference.
Lemma 3.2. Fix constant 8 > O. The log peeudolikkelihood c(3: o) of a truncated Ising model fulfilling Assumption 1 satisfies the following upper bound probability, for all 9 E R.
(12 4B)m
Prş |6 (3;o)
21
8
Proof. To begin, we demonstrate our upper bound in probability over the first derivative of the log- pseudolikelihood ((3; or), showing this concentration inequality via the technique of exchangeable pairs introduced by (Chatterjee, 2007). Define the anti-symmetric function, F
R.
F(T,T')
Σ (mi(T) m.(T'))(T -1) (E(N]
Let drawn from the Ising model truncated by き. We construct a new assignment a', via taking one-step of the Glauber dynamics over the Markov random field induced by the Ising model; in other words, we select coordinate J [n]] at random and fix a'_, := O-J and redraw the remaining coordinate o'y from the conditional distribution Præ(-la->), The value of F on (a,a') simplifies as,
= m d'j)
17

---

Define the function f(or as the conditional expectation of F(o, o') with respect to that is
f(a) = E., (F(o,
mi(a)(o, B(osloo-)))
sE|n]
Σ
- (an)(o--tnn(33m(((0
n iEJ
03 (3:0)
To show prove the desired result, it suffices to show bound on the second moment of f(r). Observe that (ar o') is indeed an exchangeable pair as
[x[s(a)²) Ba,, Bs, Moreover, the anti-symmetrie nature of F(o,, o') implies Eg.(f(o")F(o''oo - F(o o')]. These facts combine to recast Es as follows,
Eg [(()) Eg.
2 Es.J -(o)
o a' then this expression rendered trivially zero, and hence we need only analyse the case when of -os. If the redrawn coordinate / is selected from the set of flippable indices, this probability is,
exp(-o,,m,(oo)
(r( exp(-Bm,(or) + exp(3m,(a))
-rod
and when & F(or) ) this probability is zero. Using the definitions of f(x) and F(T, 7') above, this expression is simplified as follows, where (+) (-o;, -i).
2 E,
Σ iEF(o)
(f(o) - F(o,
Σ iEF(o)
(s(r) 1(o (() (a)
Tr
n (EF(O)
Bound on Tie We now bound each of term in the above expression, beginning with Tı: where flippable. The Taylor expansion of (()(() centered (( yields,
0f do,
(ww, o-:)) max 2 Of wE[-1,11 do,
(f(a()) f(o)) < la, of")
((w, o):)..
max wE[-1,1]
where is point along the line with endpoints and (
The partial derivative of f(o) with respect to o, evaluated at a spin configuration T E S is
os (T) - Σ (1- cosh 2 (Bm,
AA,
my(T) + (r, tanh((m,(T))) 0m,(T)
0o:
0o;
JEF(T)
The assumptions on G implies (m,(T)) < for all values of i E I. Furthermore, ccosh(-) 2 1. yielding the following bound on the rescaled first term.
- (mait))+
BAj
Σ jEF(T)
Lizy cosh c (Bmx(T))
mz(T)
Σ
[BArmm(TT]
(+())))()))
@m)((a)) do:
Likewise,
Aji implies a bound on the second term.
(T) - tanh(33 (T)
@m,(T) 0o, < 2|A
< [(T, tanh(3m,(7)))
0o:
18

---

Combining these two bounds yields
0f
Tul = max we - do,
(ww, a-i))
max wc[-1,1] n
(mi((w;a=:)))
E
+ 2|A
(+ttbET(a))
1+
Σ
m
(fl))EF(o))
(6 + 2B)
Bound T2: Recall [m:(or] < for all E 7 and or (-1,1)]171) and |tanh())] S 1, IR.
Then
T2d (m,
<
Putting together the pieces: We are now ready construct our final bound on Ez(f(o)3)
Ea(
EB, - ((o'))
Es
Σ Ti(T2xe;(o)) iE!
2n
(12 + 4B)
<
2n
(6
2B)
Recalling the relationship between ((r) and
0g 73
the claim follows directly.
E OMITTED PROOFS OF SECTION 3.3 (STRONG CONVEXITY OF THE PSEUDO-LIKELIHOOO)
The primary aim of this section is proving Lemma 3.3, recounted here for convenience.
Lemma 3.3. The log-pseudolkkelihodd o(3; σ)) of Ising model, truncated by k-SAT formula with 1 > (1 fulfilling Assumption satisfies the following lower bound in probability for Tox(pexp(22B))
all 8 E B).
(5:(3:0) O) 82B
nexp(-DD
(24 + 8B) no.1
Præ-
38kkd)
Towards this goal, provide proof of Lemma 3.4 in Section E. Lemma 3.5 in Section E.2, and Lemmas 3.6 3.7 Section E.3 before concluding Lemma 3.3 in Section E.4.
E. PROOF LEMMA 3.4
The proof of this lemma proceeds by defining explicit, algorithmic correspondence between bijections p + [n] and independent sets /. This mapping induces measure μo over bijections, which in turn defines a distribution over the resulting independent sets. We analyze this distribution to bound the probability that a randomly generated independent set contains fewer than Al elements in some clause- "bad event." Applying the Lovász Local Lemma, show that with positive probability, none of these bad events occur, implying the existence an independent set that satisfies the desired clause-wise coverage property.
19

---

E.1.1 THE ALGORITHM
Given bijection p [n], we provide simple algorithm for finding an independent set detailed formally below. To bound the probability of bad events, that fewer than Al elements from a clause are included the independent set under the uniform measure over bijections Pp, we must ensure that the inclusion of distant vertices into the independent set occurs in independent manner. This form of spatial independence is crucial for applying the Lovász Local Lemma, and is established in the following lemma.
Algorithm Independent Set in Graph Based on Random Ordering
Require: Graph G = E) with V [n]
Ensure: Set S of selected vertices
1: Sample a random permutation p V - [n]
2: function INDEDGESET())
3: Initialize S 4- 0
4: for all E do
5: if p(u) > (ax)) p(v) then
6:
S SU {u}
7: end if
8: end for
9: return
10: end function
11:
return IndEdgeSet(p)
Lemma F.1. Fix two vertices u.v E V such d(u, v) 3, over the graph G induced by
A. Over the uniform measure of orderings p V - 'n), 1'p- the indicator random variables 1fu belongs to IndEdgeSet(p)) and 16 belongs to IndEdgeSet(p)) are independent, that is
Pr Pra,Ku. Ku, IndEdgeSet(p)) Pru.ltu e IndEdgeSet( Pr E IndEdgeSet(p))
Moreover, the probability a given node v lies in I is
1
Pr KV IndEdgeSet(p)) <
A 1+1
Proof. The event that vertex w E V lies in IndEdgeSet(p) depends fundamentally on the structure of the bijection p. Specifically,
{w E IndEdgeSet(p))) = p(w)=
{ > max
p(i)). (EN(
}
where (w) denotes the neighbors of the graph.
The joint probability, under the uniform measure Me over all bijections that two distinct vertices and both belong to the set IndEdgeSet(p).
Prp, [u E I and I] Pr p(u)
p(w), p(v) NEN(u))
max p(u') WEN((e)
depends only on the relative ordering of the values of on the set {u, U (N)) which has size at most 2A + 2. Morcover, since d(u, v) 2 3, the neighborhoods (u) and N(o) are disjoint.
Towards computing this probability, observe that, there are [N)))] permutations of {u} U (u) in which u appears first, and similarly there are [N(v)] permutations of {u} U ((v) in which appears first. All orderings over fu U v U Nu)) U N(v)), which place u, first among their respective neighbors are shuffles of existing orderings of {u UuU N(u)) and {u (()) Counting combinations, there are ((N)))++N()))+)) ways to interleave the two sets (u))N(() and (e)UN(m)
[N(a)]+1 while preserving their internal orderings, implying the number of permuations satisfying the above condition is:
(IN(w)) + (N( +2) [N(u)] +1
IN(w)) [N(0)] (IVV(w) + (N()) + 2) +1)
20

---

As the total number of permutations of the relevant elements is (IN(u)) + [N( + 2)1. the joint probability is:
Pry, [u, v IndEdgeSet(p)] = (1 + ()( +1)
similar argument yields that for single vertex v there are (())!/(N()) + = 1/(N(n) + permutations placing first in relative order among its neighbors. This implies the probability over the uniform measure over bijections that v belongs to the induced independent set is:
Pr [w E IndEdgeSet] = Præp p(u)
max p(i) NN +1
1
JEN(u)
The desired conclusion follows by combining the expressions for the single and joint probabilities.
In advance of proving Lemma 3.4, we introduce an important tool that relates arbitrary collection of potentially correlated random variables to independently and identically distributed variables, which will enable the use of Chernoff bounds in the sequel.
Lemma E.2 ((Frieze & Karoński, 2015) Section 23.9). Suppose that (Yihie()) are independent random variables and that {Xi]iEmm are random variables so that for any real and E [n]]. holds that
Pr[X, 2 t|X,,... X 2
Pr[y 2 t).
Then, for uny real I,
Pr[X1 + +.. Xn 2 Pr(yi + Yn 2 2].
Armed with this background, we now prove Lemma 3.4, recounted here for reference.
Lemma 3.4. Let G be graph with maximum degree o(n)/6) and be a k-SAT formula. k > 1043 (1++ + log(dk then there exists an independent set I C V such that V' & truncated on I, a Ak- SAT formula where X = 1/4A
Proof. To begin, consider clause C E C, and select maximal collection of neighborhood disjoint variables C' S C. In other words, we require that for all i.j J E C", d(i,j) 2 3. The maximum size of two-hop neighborhood of given point is at most A + 1, implying the size of C' is least +/(A++1) Denote the function (c(p) = (IndEdgeSet(p) nCH. As each pair of elements in C' is least distance 3 apart from each other, Lemma E. implies the following bound the expectation of fc(p).
Ep,()(( Ex,
Σ Pro, (u E 1]
(A + () + +1
e,EC'
Moreover, this directly implies that for all 4, that for Y, ~ Bem(1/(A + 1))
[r[ E (1)1 E e,,,...,
7)) Pr(Y; 2 t
Given this information, we use Chernoff bounds find an upper bound on the event Pr(Yi + Yn 2 k/(2(42 + 1) + 1))], and use this to in turn bound (fc
Prup
so(0)
k
Pr
Y
4
(2(A + A 1))
(2(A
() 1))
k
Pr
Σ Y
(2(A
1) + 1))
Le
Pr
Σ Y - E
Σ Yu LeiEC'
5 (1-
Σ Yo LV.EC'
LVEC
k 8(A + 1) +1)
exp
21

---

To construct final bound on & in terms of d and A ensure that marking satisfying our desired conditions exists, we use the symmetric version of the Lovascz Local Lemma. Each variable appears in at most d other clauses, and the event of selection into the independent set relies its Á + neighbors which lie in its two-hop neighborhood. This implies the degree of the dependency graph of + is kd( 2 1).
2xexp exp
(kd(A² +))
(8(A2
1) +1)
exp
8(A22 + 1](A 11)
2e(kd[(2 + 1))
k
< < - log(
-lg-log(kdll (ool 2 + 1)))
8(A² 1) + 1)
8(1 + log(kd) + 33) 1)(A + 1)
The independent / induces a smaller CNF, D K, (V", with clauses C" Ucec Cn each which has at least k/(2 + 2A) variables, concluding the desired claim.
E.2 PROOF OF LEMMA 3.5
In this section, our aim to show Lemma 3.5. We accomplish this goal in two steps, first demonstrat- ing each variable outside the independent set is flippable with probability 1 6, where 5 E (0, 1) and second demonstrating each variable inside the independent set is flippable with probability at least 1/2.
Proceeding, we introduce the version of the Lovascz Local Lemma that will be used in bound of sc(or)
Lemma E.3 ((Guo et al., 2019)). Suppose that p(or) is product distribution over o' 11 Let Ag be an event determined by the elements of a, and denote B(S) Aies A,. Then if there exists vector such that (0, 1) and
Pr(A,) S II (1 (1-2)) (H.))E
then
Pr(B(S)) 2 II (1);
iES
Moreover, let E an event determined by some of the coordinates of a and let I(E) = (i E S var(A,) var(E) + 0}. We then see that
(E)(S)((S)) S (E)
II (1 (1-x))
(EI(E)NS
Lemma E.4. Given sample Pr where 8 (-B, B) and that the S-SAT formula &b which induces the truncation set S, satisfies the following clause size bound
k N 3 + (ogg(kk +1))
log(1 1 +
3 'Then for A there exists an independent set following Lemma 3.4 such that
Præ.s(s,(o)) 1] 1/2 VVEV
Proof. Towards establishing the desired claim, we first need a bound on k with respect to d to ensure the use of Lemma E.3 (the asymmetric LLL). For any assignment T E [-1,1][V/1 define 4 (VT C7) as the CNF formula obtained via truncation the partial assignment that is the assignment that removes clauses satisfied by 7 and removes literals from T from the remaining
TThis term scales
28 A kd)
22

---

clauses. Notice, the set of clauses C' within e' are merely the union of all clauses C over all d7, that is
=== C'U C
FE|-1.1)IvA1
implying a bound that would guarantee satisfying assignment for d', would in turn ensure the existence of the satisfiability of all ΦT.
Moreover, recall for any independent set I, conditioned the variables outside of the independent set V/I, the Ising model collapses into a product distribution.
exp (8 Ejev Aujooo) ei(or
Pro(arlov/il
GET exp { []EEV A1,0,) + exp (38EeeV/1 Anjo)
This directly implies
exp(13))
exp(2|
min Prolo, = ovyrl exp(3A) + exp(-3A) 1 exp(2)31) xE(-1,1)
For each clause C² C", the event {C' is not satisfied) depends dk variables which lic in at most d clauses. Following the setup of Lemma E.3, we set xrC") = 1/(D + 1), D = d2k; and notice
1+Hog(d*k+1) k' 2 1og(1+exp(-2181)
exp(2
D
D
1
exp(2|31) +1
D+1
D+1
D
(D+ < (1 exp( -1))1)))
D+1
e(d + 1) < cxxx -
1 log(d < /' log(1 + expl
1 + log (2* +1) <
log exp( 1))
Counting combinations, there is only way to assign all the variable in C' such that the clause not satisfying. The worst case probability a clause C" takes any given configuration under the untruncated distribution jı is at most
exp(2) W 1 (++ex((2 exp((
Prpg (clause C' not satisfied]
For every pinning 7 E 1-1,1 we can equivalently find a upper bound for the probability that (s) = 0}, under the conditional distribution, i.e. given a E Sr. where S, the set of satisfying assignments of & where Øv/r is pinned to T.
Pro(si(o) 0]=
Σ
Pr (s = 0/a E S.|Pralo Sz]
rE( rE(-1,1)
max
Pr Prag(ss((r) = 0|o Sr]
rel +E(-1,11iv
Pr [=]( =0/(1-
1
exp(2|3) K 1 1 exp(2131
ed
D+1
23

---

The final inequality derives from of Lemma E.3, relating probabilities between the truncated and untruncated distributions. We lastly rearrange for to derive the final result.
exp(2131)
Pra[s:(o)] (1 8))12112 ed
1 cxp(2
exp(2]31) W
ed
1 1 exp((11)
log(d) k (log(1 cxp(2 - 2 log(6)
+ log(d) log(
log(1 + exp(2 - 2 S k'
Lastly, to guarantee there are a sufficient number of flippable variables in the independent set itself, we use the following result from (Galanis et al., 2024) to find lower bound on the number of variables within the independent set that are flippable under a product distribution.
Lemma E.5 (Lemma 15 16 (Galanis al., 2024)). Consider a formula 4' 2n aa with k' > llogddk))+
Alog(1+e P) and an associated product measure May over the hypercube {-1,1}", such that each variable is set to independenlyy with probability (exp(r))/(1 + exp(7)). Then for each variable 0;
Prylo; is not flippable] S 1/2.
Moreover, can find collection of R S [m] with |R] 2 n/ n2(22d)² that are neighborhood disjoint in the interaction graph of the k-SAT formula op' such that for all subcollections (i1,..., it) C R,
Pr, [ec. = 1/e,, (o) (o)
This in turn implies, with probubility EiER e((o) 2 |R|/3.
over the choice of a Pro.s. holds that
The second half of Lemma 3.5 then follows from this corresponding results in (Galanis et al., 2024). To relate these results our setting, observe that under our product distribution, the probability that any variable is set to one at most e e-B/(1 /(1 + e eBB), and the true marginals may in fact be more balanced. Consequently, the conditions of their result are satisfied in our regime.
E.3 PROOF OF LEMMAS & 3.7
For reference, recall the expression for the Hessian of the log ngeudo-likelihode
PO(3:0)
(
Φ2(3;0)
cosh ((m;(((m) ci(o).
0,32
Towards demonstrating (2( a(n) with probability o(1 for all f3 E (- B), we provide a lower bound of the conditional mean of the magnetization the flippable variables via proving Lemma 3.6.
Proof of Lemma 3.6. For all E {-1,1}", consider (Eiyy Agoi + Aty)² and (Engy Anoi 2. If Eit3 Anoi and Aij have the same sign, the first term least A2, and the opposite sign,
24

---

the second is at least Alj. This implies that
33- (m)
Σ
Eg- (m)(())))(())=
=ning((()))(PP(((((0 = =x]
xE{0,1)
>
Σ
A min #E(-1,1)
foo [|o-);;-0 = =r))Prsles(o)
(E(0,1)
42
2 2
exp
-
8*
Σ
A (r)-le =
A
2 exp(-B)Pra--ee =1]
2
This result provides a lower bound for dz2 (3; σ in terms scaled elements of the interaction matrix Asj. To maximize this lower bound, we wish to select columns h(i) for each row ensure the value Aa(i) as large as possible. To this end, consider an injective mapping h h V V. The requirement that || S and ||a:]|2 2 c, implies the existence of a edge A,j for each row such that Aij > e'. Moreover, due to the connectivity of the graph, we can select subset I' C I of size at least / > n/A?, with an unique neighbor h(t) E V/I, where Ang(a) 2 d. Outside of I', we assign partners arbitrarily making sure to keep h(i) a bijection. Towards this goal, we present proof of Lemma 3.7.
Proof of Lemma 3.7. We begin by constructing a set R of variables that are disjoint in both the incidence graph of the k SAT formula and the graph G. A simple greedy algorithm that lects a point arbitrarily, deletes its 2-hop neighbors in both graphs and recurses has size at least n/(2k' 2) 2 This implies the sum of conditional magnetizations takes the following form.
Σ Ex fm (o)):(o))lo--m m(]l ER
E3
-
Pro- (er(or) lle,, (o) L,..., Ci. (a) =
Eg. [m (a))
2
IER
exp(- - B)
Pr (o)
n exp( B1 5)
A A(4kdA)2
Note the last inequality comes from Lemma 15, and the fact that s;(or) S Ee(o))
E.4 PROOF LEMMA 3.3
Armed with the tools from the previous section we now prove Lemma 3.3.
Proof of Lemma 3.3. We begin by expanding m,(a) into its component parts, namely
()(
Σ
Agos
+ Alncs +2
Σ Aijoz Amci)nn
(T((1)
jzh(1)
Cancelling common factors implies that
Eg.
2
Σ
Σ
Anjo
Aua()) (on())
Eg. (onc)) (onco)o(aa))
((.))eF(())
jzh(())
25

---

We merely sum over the flippable indices, when (b()) is not flippable, the term bb(i) Es (on()) l -()) collapses. Denoting (a( 2 (Efze Awa;) Ase and recalling [3-(os/ar=)) = tanh (5 m/ (o)), yields the following simplified version of the above expression.
(v))o)(a) (aNcs - tanh (aco) (L.))
Σ
aim to prove this concentration inequality via the technique exchangeable pairs introduced by (Chatterjee, 2007). Consider, again, the anti-symmetrric function, F S x x R
1 - (V)) yaccn (T) T/),
F(T, T
and an assignment drawn from the Ising model truncated by We construct a new assignment o', via taking one-step of the Glauber dynamics over the Markov random field. The value of F on (a, o') simplifies as,
F(o, a') (0)
Define the function f(or as the conditional expectation of F(or, o') with respect to that is
f(o) = E (F(o,o')(o)
Van(e ( (B(slo-))
- -
tan)((
iEF(o)
To show prove the desired result, it suffices to show a bound on the second moment of f(rr). Observe that (ar, a') indeed an exchangeable pair as
[f()) = Eg (((o) B3- Bo-rlf(o"" o)).
Moreover, the anti-symmetric nature of o'), implies Es- Es-r1/(o""F((''o))) EE F(( These facts combine to recast Eg. [f(or] as follows,
Eg [f = E3- (:l(f((((FF(ooot = Es _ff(('))((oooo))
1
2 E (
o = o' then this expression is rendered trivially zero, and hence we need only analyse the case when of =o.. the redrawn coordinate I is selected from the set of flippable indices, this probability is,
P.(or) exp(- (1,,mmm (xp(5=m;(o))
Pr(o - F(o))
and when & F(o) this probability is zero. Using the definitions of f(or) and F(T, T') above, this expression is simplified as follows, where (i)) = (-o,, o..)
2 E,
Σ (f(o) F(0
n (EF(()
1
(f(a) f(o f(""")))))))())))))))))) manh( (p.))(
n
(EF(a)
1
Σ TrT
n
SEF(G)
Bound on Tia We now bound each of term in the above expression, beginning with Tıa where i flippable. The Taylor expansion of (()( centered at f( yields,
05 ((w, o-))) max 2. 0S. =E[-1,1] Oo,
(((a()) f(a) s lo; - ,(") max
((w, o=))),
1 do;
26

---

where is point along the line with endpoints and or o()).
The partial derivative of f(or) with respect to o; evaluated at a spin configuration T E S
1 Σ 0f (T) - 0o:
(
1
3" AnG)s
(T) (T) tanh(8' ((())()))
(Usno)(T)
cosh (osh"(8*ma (8*m)(((T)))
Oa;
JEF(TT
The assumption ||A||0o < 1 implies (m;(T)) S for all values of [ni] and {-1,1)"
Furthermore, ccoh(-))
) 2 1. yielding the following bound on the rescaled first term.
8 AR
Σ jEF((T
1==j
Σ
(()
Σ ((A()E)(T)
18t AnGr)(ma))(T)
(jEFIN()= ((T)
(2g 00.
can be quickly seen that this value is at most (2 + 2B). Likewise, bound on the second term.
2A implies a
(T; - tanh(3" ma)) (T)) (yy(C)((T)
(UjuCo(T)
tanh(8 ()))())))))))))))) <1(T;
$ 4|Ancnd
0o:
0a:
Combining these two bounds yields
0f
Tal $ 2 max we[ wE[-1.11
((w, o-i))
Oo:
2 (2+
Σ
4|Anosal
max =E[-1,1]
JEF())
2 ((2 2B) +4)
(12 + 4B)
Bound on T2x: Recall (o)) < for all [m] and E (-1,1}" and [anh(x)) 1, Va R.
Then
T2 (us(a) (a) tanh( ma(e) (a (a)) 54 4
Putting together the pieces: We are now ready to construct our final bound on Ez- (f(
Ez- (}(())))))
2 Eg, ((f(o) ((o'))(ooo'')
n
2n Eg.
Σ
TTTTace((o))
(24 + 8B)
n
This directly implies that
(
27
Eg-
Σ
(o) - -
m
Eg. [m((o)c((0)(oxxx))
1=1
27

---

Applying Chebyshev's inequality to this term, yields bound in probability that the second deriva- tive deviates far from its conditional mean.
Prg-
(o(eel(())
Σ
Bg. [m(())e(()(oomc)))
2 11 1.1
(24 + 8B)
nt
==1
(24 + 8B)
Præ-
Eg- Σ m Σ
2 n2 0.55
n
t=1
i=1
exp (1 - 5)
(24 + 8B)
Pra-
(o)
12 0.55
A(4kdA)²
n.
i=1
2nexp( - (1 - 8)
Præ-
(((o))
2 1 - 11)
((4idA)2
i=1
F APPLICATIONS
In this brief section, we establish connection between the notion fatness, as introduced in the context of truncated Boolean product distributions (Fotakis al., 2021), and the Ising measure conditioned on the solutions to a K-CNF formula. Specifically, we show that this truncated Ising measure satisfies the combinatorial conditions required for fatness, thereby extending the fatness framework beyond the setting of product distributions. We recound the definition of an a-fat dis- tribution below.
Definition 1 (o-fat Distributions (Fotakis al., 2021)), A truncated boolean distribution Ds is a-fat if for all coordinates E [n] there exists some a > such that
Ds (21. (i I:.
2
Corollary F.1. Given an Ising model Pra,s, satisfying Assumption 1, whose measure is truncated to the solutions S of a k-SAT formula such that
2 (033((333)) + log( dd 1))),
then the distribution is fat, i.e.
Pros)(-o,,0-)E }/8 for all i [n].
Proof. This is direct consequence of Lemma 3.5.
28


Reviews:
[{"review_id": "3Z60tN0kOl", "reviewer": "Reviewer_ean9", "summary": "The paper considers a truncated Ising model, where an Ising model on a graph G of size $n$ with inverse temperature $\\beta$ is sampled and samples are accepted only based on satisfiable assignments for a $k$-SAT formula. The main question is can you learn inverse temperature parameter $\\beta$ from a single sample from this truncated model. \n\nAuthors show that one can learn the inverse temperature parameter up to an error of $\\Delta^3/\\sqrt{n}$ when the number of clauses in the k-SAT formula exceeds $\\tilde{O}({\\Delta^3})$ and the inverse temperature is in a bounded interval around $0$. Authors main key ideas are by doing a MLE estimate for $\\beta$ on the pseudo likelihood which is the product of likelihood of Glauber flip of every variable conditioned on all others.  1) First, the error in the MLE estimate is bounded by ratio of the magnitude of the first derivative and the minimum second derivative of the log pseudo likelihood. So authors proceed to show that the numerator is small and lower bound the second derivative.  2) Concentration due to exchangeable pairs take care of the concentration of the first derivative which has to be close to zero for the stationary point with a deviation of $\\sqrt{n}$  and the lower bound on the second derivative is at least n/\\Delta^3. \n3) Key issue is that second derivative's lower bound is non trivial only if there are linear number of flippable variables - variable coordinates that can be flipped from the sample without violating $k-SAT$ constraints. Clever trick is that authors show that there is a large enough independent set in the graph such that it encapsulates linear number of variables and conditioning on the rest, the probability of variables in the independent set factorizes. Then it is easy to show that some variable from the independent set will satisfy the clause in which another fixed variable is in with constant probability. This ensures there are enough flipped variables which contributes then to the lower bound on the second derivative.", "questions": "I have asked all my questions in the weakness section.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Paper considers a very non trivial Ising model with a truncation on the set of satisfiable boolean assignments in a K-SAT formula. Then authors use the Glauber flip based pseudo likelihood to do the MLE estimation of inverse temperature beta from a single sample. \n\nTechniques are quite novel compared to classical results on single sample learning of un-truncated Ising models and other recent works. specifically the independence set finding algorithm that truncates the k-SAT formula with some guarantees used a clean and elegant version of Lovasz Local Lemma. The trick of creating a conditional product distribution and arguing about flippability of variables that lower bound the second derivative is also pretty neat.", "weaknesses": "1) My main concern is that Section 3.3.1 starts with arguments ensuring enough variables are flippable. However, there is only a small two line comment of how it is related to second derivative lower bounding. So the reader is forced to look in the supplement as to why this issue is prominent. lemma 3.7 in the supplement shows why enough of such flippable variables are important. It is important to include that argument (in a sketch form) at the beginning of Section 3.3.1 \n\n2) Where does the constraint (or what steps in the proof contribute): $\\Delta \\sim o(n^{1/6}) $ comes from precisely ? \n\n3) After an independent set is chosen, then the rest of the argument about flippability splits into two parts - one is flippability of variables within the independent set and outside. It seems like the first one directly follows from prior work ? So the main novelty is in the construction of the independent set and the argument for flippability of variables outside it ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2V4R38R18L", "reviewer": "Reviewer_fnoj", "summary": "This paper studies the problem of learning the inverse temperature of a truncated Ising model from one data sample. The Ising model is constrained to lie within a specific set (referred to as that satisfying the k-SAT formula). The authors provide various practical scenarios to motivate this setting. The theoretical results hinge on the analysis of the maximum pseudolikelihood estimator and demonstrate its consistency.", "questions": "1. What is meant by ${\\cal O}(\\Delta^3 n \\log n)$-Algorithm?\n2. The theoretical bound in Theorem 2 becomes tighter with increasing $n$--suggesting that the estimator is likely to perform better when estimating a larger Ising model with a single sample. Could you elaborate on this aspect? Shouldn't the estimation problem become 'harder' with increasing 'n'?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Theoretical arguments are well-stated (although there are some key definitions are missing; see Weaknesses section). The theoretical analysis is based on establishing guarantees on the first order and second order gradients of the pseudolikelihood estimator relative to the inverse temperature function. The novelty is (seemingly) claimed in terms of establishing the bound on the second order derivative in Lemma 3.3.", "weaknesses": "1. The key definition of $k$-SAT formula or how it leads to a hard constraint on the Ising model is not defined with sufficient rigor. Therefore, I could not fully understand why this particular setting was of interest.\n2. The novelty within the theoretical results should be emphasized better- some results seem to be simple extensions of previous works, while others are novel. The distinction between the two should be elucidated.\n3. While I appreciate the theoretical flavor of this work, some effort into making the theoretical results interpretable for practitioners would have improved this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HrRPH4d9JE", "reviewer": "Reviewer_2qpS", "summary": "At a high-level this can be seen as a paper that combines learning ising models from one sample with learnign with truncations. More specifically, the paper studies one-sample estimation of the inverse temperature $\\beta$ for a truncated Ising models where the state space is the satisfying set $S$ of a bounded-degree $k$-SAT formula. The estimator is the standard maximum pseudolikelihood (MPLE), optimized by projected gradient descent. The analysis shows the MPLE gradient concentrates at $\\beta^*$ (via exchangeable pairs) and that the normalized log-pseudolikelihood is strongly convex w.h.p. The latter is the challenging part, and requires proving the existence of a linear number of flippable coordinates using an independent-set/LLL argument, under large enough $k$.", "questions": "- My main question is around the choice of $k$ being justified. As a follow-up, which of their techniques would extend to more interesting settings?\n- It would be helpful if the authors describe which dependencies are necessary and tight, and which are loose. Especially $\\Delta$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper presents a novel setting, that seems somewhat motivated.\n- The analysis requires new techniques to prove strong convexity, which involves circumventing a few challenges.\n- The paper is generally well-written, and easy to follow. It also does a good job of covering related work.", "weaknesses": "- The paper could do with a bit more motivation for the setting, and in particular $k$-SAT, since it seems more of a purely theoretical pursuit.\n- The clause-size requirement $k \\gtrsim e^{2B}\\Delta^3(\\log d+\\log k)$ is quite large. In bounded-degree regimes, such $k$ pushes the truncation toward an LLL-like easy regime where $|S|/2^n = 1-o(1)$. The constraint can become somewhat vacuous, making the setting not clear.\n- The assumptions and dependencies seem a bit loose or proof technique specific. For example, Assumption $A_{ij}\\in{\\pm 1/\\Delta}$ and $\\Delta=o(n^{1/6})$ feels stronger than necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TbvVQLNbXa", "reviewer": "Reviewer_ymcN", "summary": "This paper considers the problem of estimating the inverse temperature parameter of a Ising model constrained to the satisfying assignments of a $k$-SAT formula, from 1 sample. \n\nThe graph and formula are given, and the graph is assumed to have bounded degree $\\Delta$, and for the SAT formula the number of clauses is assumed large relative to the degree of the graph and the formula, $\\Omega(\\Delta^3\\log(dk+1))$. The main result is an efficient (nearly linear-time) algorithm using the maximum pseudolikelihood estimator, which learns $\\beta$ within $O(\\Delta^3/\\sqrt n)$ with high probability. There is an exponential dependence on the size $B$ of $\\beta$.\n\n(Note that the setting of \"learning under 1 sample\" encomposses the setting of learning under multiple ($N$) samples, by simply defining a graph and constraints that are disjoint copies of the original, giving the natural $1/\\sqrt{N}$ scaling in error.)", "questions": "Does the theory work in the case where different weights are allowed on the edges? Needing $A_{ij}\\in \\{\\pm \\frac 1\\Delta\\}$ is quite limiting. It would be much more general to allow all $|A_{ij}|\\le \\frac 1\\Delta$. \n\nIt's necessary for Theorem 2 to exclude the empty graph (where the model is the same under every temperature). Is it sufficient to exclude the empty graph or is there a missing condition?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem of learning graphical models is an important problem. This paper follows a line of work on learning the Ising model, where a natural generalization is to consider a model truncated by hard constraints. SAT formulas provide a natural family of constraints. The pseudolikelihood estimator is a widely used estimator for its computation efficiency, and this paper gives guarantees for it in a constrained setting.\n\nThe work is technically novel, as learning a model under constraints requires new techniques compared to learning without constraints. To bound error in the pseudo-likelihood estimator it suffices to (1) upper bound the first derivative of the log pseudo-likelihood using the technique of exchangeable pairs and (2) lower-bounding the Hessian. The latter is the main challenge, and is done by (a) constructing a linear-sized independent set such that conditioned on the variables outside, the variables inside become a product distribution (ignoring the constraints), and such that the restricted constraints still have large-enough clause sizes, ensured using the Lovasz Local Lemma; this product structure means there are a large number of flippable variables which (b) each contribute to the Hessian by at least a constant, lower bounded by lower-bounding the squared magnetizations of the neighbors of each $i$. \n\nThe proof sketch does a good job of conveying the main ideas of the proof at a high level.", "weaknesses": "I find this to be an interesting learning theory paper, but my main concern is whether it is appropriate for the general machine learning audience at NeurIPS. A theoretical CS conference may be a better fit. In particular, the fact the problem considered is solely that of learning the temperature, rather than the entire model, makes the problem quite niche. \n\nThe title is somewhat misleading, as the only parameter that is being learned is the temperature. I suggest \"Learning the temperature of an Ising model under hard constraints\".\n\nThe paper only deals with the case of bounded-degree graphs, and so does not apply to mean-field type models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)