Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910021834506240 |
|---|---|
| author | Chauhan, Rohan Panageas, Ioannis |
| author_facet | Chauhan, Rohan Panageas, Ioannis |
| contents | We consider the problem of estimating inverse temperature parameter $β$ of an $n$-dimensional truncated Ising model using a single sample. Given a graph $G = (V,E)$ with $n$ vertices, a truncated Ising model is a probability distribution over the $n$-dimensional hypercube $\{-1,1\}^n$ where each configuration $\mathbfσ$ is constrained to lie in a truncation set $S \subseteq \{-1,1\}^n$ and has probability $\Pr(\mathbfσ) \propto \exp(β\mathbfσ^\top A\mathbfσ)$ with $A$ being the adjacency matrix of $G$. We adopt the recent setting of [Galanis et al. SODA'24], where the truncation set $S$ can be expressed as the set of satisfying assignments of a $k$-SAT formula. Given a single sample $\mathbfσ$ from a truncated Ising model, with inverse parameter $β^*$, underlying graph $G$ of bounded degree $Δ$ and $S$ being expressed as the set of satisfying assignments of a $k$-SAT formula, we design in nearly $O(n)$ time an estimator $\hatβ$ that is $O(Δ^3/\sqrt{n})$-consistent with the true parameter $β^*$ for $k \gtrsim \log(d^2k)Δ^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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_20993 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample Chauhan, Rohan Panageas, Ioannis Machine Learning Data Structures and Algorithms We consider the problem of estimating inverse temperature parameter $β$ of an $n$-dimensional truncated Ising model using a single sample. Given a graph $G = (V,E)$ with $n$ vertices, a truncated Ising model is a probability distribution over the $n$-dimensional hypercube $\{-1,1\}^n$ where each configuration $\mathbfσ$ is constrained to lie in a truncation set $S \subseteq \{-1,1\}^n$ and has probability $\Pr(\mathbfσ) \propto \exp(β\mathbfσ^\top A\mathbfσ)$ with $A$ being the adjacency matrix of $G$. We adopt the recent setting of [Galanis et al. SODA'24], where the truncation set $S$ can be expressed as the set of satisfying assignments of a $k$-SAT formula. Given a single sample $\mathbfσ$ from a truncated Ising model, with inverse parameter $β^*$, underlying graph $G$ of bounded degree $Δ$ and $S$ being expressed as the set of satisfying assignments of a $k$-SAT formula, we design in nearly $O(n)$ time an estimator $\hatβ$ that is $O(Δ^3/\sqrt{n})$-consistent with the true parameter $β^*$ for $k \gtrsim \log(d^2k)Δ^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. |
| title | Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.20993 |