On approximating the f f -divergence between two Ising models
Weiming Feng and Yucheng Fu · 2025
Read On approximating the f f -divergence between two Ising models by Weiming Feng and Yucheng Fu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-05016.txt.
Introduction
Measuring how far apart two probability distributions are is a basic task in statistics and computing. Weiming Feng and one co-author study approximating that gap between two Ising models in a 2025 theoretical computer science paper. Ising models describe interacting binary variables through interaction matrices and external fields.
For a family of chi-alpha divergences, they prove both an algorithm and matching hardness results, so the tractable regime is pinned down. The algorithm extends to many other divergences, including Kullback-Leibler, Rényi, and Jensen-Shannon versions, plus squared Hellinger distance. The work generalises recent results on approximating total variation distance.
Catalog record
| CREATOR | Weiming Feng and Yucheng Fu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-05016
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On approximating the f f -divergence between two Ising models Weiming Feng and Yucheng Fu Abstract The f f -divergence is a fundamental notion that measures the difference between two distributions. In this paper, we study the problem of approximating the f f -divergence between two Ising models, which is a generalization of recent work on approximating the TV-distance. Given two Ising models ν \nu and μ \mu , which are specified by their interaction matrices and external fields, the problem is to approximate the f f -divergence D f ( ν ∥ μ ) D_{f}\left({{\nu}\,\|\,{\mu}}\right) within an arbitrary relative error e ± ε \mathrm{e}^{\pm\varepsilon} . For χ α \chi^{\alpha} -divergence with a constant integer α \alpha , we establish both algorithmic and hardness results. The algorithm works in a parameter regime that matches the hardness result. Our algorithm can be extended to other f f -divergences such as α \alpha -divergence, Kullback-Leibler divergence, Rényi divergence, Jensen-Shannon divergence, and squared Hellinger distance. 1 Introduction Let \nu and \mu be two distributions with the same support \Omega . Let f:\mathbb{R}_{>0}\to\mathbb{R}_{\geq 0} be a convex function such that f(1)=0 and f is strictly convex around 1. The f -divergence of \nu from \mu is defined by \displaystyle D_{f}\left({{\nu}\,\|\,{\mu}}\right)=\mathbf{\mathbf{E}}_{X\sim\mu}\left[f\left(\frac{\nu(X)}{\mu(X)}\right)\right]=\sum_{\sigma\in\Omega}\mu(\sigma)f\left(\frac{\nu(\sigma)}{\mu(\sigma)}\right). (1) The f -divergence is a very general notion that measures the difference between two distributions. For instance, f(x)=\frac{1}{2}|x-1| gives the total variation distance (TV-distance) , f(x)=\frac{1}{2}(x-1)^{2} gives the \chi^{2} - divergence , and f(x)=x\ln x-x+1 gives the Kullback-Leibler (KL) divergence . The Ising model is a fundamental graphical model in statistical physics, probability theory, and machine learning. Let G=(V,E) be a graph. Let J\in\mathbb{R}^{V\times V} be a symmetric interaction matrix such that J_{uv}\neq 0 only if \{u,v\}\in E . Let h\in\mathbb{R}^{V} be the external fields vector . An Ising model specified by (G,J,h) defines a Gibbs distribution \mu with support \Omega=\{-1,+1\}^{V} such that \displaystyle\forall\sigma\in\{-1,+1\}^{V},\quad\mu(\sigma)=\frac{w_{\mu}(\sigma)}{Z_{\mu}}=\frac{\exp\left(\frac{1}{2}\sigma^{T}J\sigma+h^{T}\sigma\right)}{Z_{\mu}},\quad\text{where }Z_{\mu}=\sum_{\sigma\in\{-1,+1\}^{V}}w_{\mu}(\sigma). The function w_{\mu}:\Omega\to\mathbb{R}_{\geq 0} is called the weight function of the Ising model and the normalization factor Z_{\mu} is called the partition function of the Ising model. Recently, the problem of computing the TV-distance between two high-dimensional distributions has received increasing attention. One interesting result [ 5 ] has proved that even for a pair of product distributions (Ising models on an empty graph), the exact computation of TV-distance is #P-hard. Later on, polynomial time approximation algorithms were proposed for product distributions [ 16 , 17 ] . For general Ising models, both algorithmic and hardness results were established [ 7 , 18 ] for approximating the TV-distance. In this paper, we consider a more general problem of approximating the f -divergence between two Ising models. The problem is defined as follows. Problem 1.1 . Approximating the f -divergence for two Ising models. • Input : Two Ising models (G,J^{\nu},h^{\nu}) and (G,J^{\mu},h^{\mu}) specifying two Gibbs distributions \nu and \mu respectively 1 1 1 1.1 assumes that \nu and \mu have the same underlying graph G . This assumption does not lose generality because the definition allows J^{\nu}_{uv} and J^{\mu}_{uv} to be 0 even if \{u,v\}\in E . , a function f defining the f -divergence, and an error bound parameter \varepsilon ; • Output : A number \hat{D}\in\mathbb{R} such that \mathrm{e}^{-\varepsilon}D_{f}\left({{\nu}\,\|\,{\mu}}\right)\leq\hat{D}\leq\mathrm{e}^{\varepsilon}D_{f}\left({{\nu}\,\|\,{\mu}}\right) . A randomized algorithm is said to be an FPRAS (fully polynomial randomized approximation scheme) for 1.1 if it runs in time polynomial in n=|V| and 1/\varepsilon and with probability at least \frac{2}{3} , the output approximates the value of the f -divergence within relative error \mathrm{e}^{\pm\varepsilon} . Our algorithmic result is a reduction from f -divergence approximation to sampling and approximate counting, which are two fundamental computational tasks for the Ising model. There is long-line of research on developing efficient algorithms [ 27 ] for sampling and approximate counting. We assume the following abstract oracles for sampling and approximate counting. Definition 1.2 (sampling and approximate counting oracles) . Let (G,J^{\mu},h^{\mu}) be an Ising model with Gibbs distribution \mu and partition function Z_{\mu} . Let T^{\mathrm{sp}}_{G},T^{\mathrm{ct}}_{G}:\mathbb{R}_{>0}\rightarrow[|V|+|E|,\infty) be two non-increasing functions. Given any error bound \varepsilon>0 , • The sampling oracle for (G,J^{\mu},h^{\mu}) with cost function T^{\mathrm{sp}}_{G} returns a random sample X\in\{-1,+1\}^{V} in time T^{\mathrm{sp}}_{G}(\varepsilon) with d_{\mathrm{TV}}\left({X},{\mu}\right)\leq\varepsilon , where d_{\mathrm{TV}}\left({X},{\mu}\right) is the total variation distance between X and \mu . • The approximate counting oracle for (G,J^{\mu},h^{\mu}) with cost function T^{\mathrm{ct}}_{G} returns a random number \hat{Z}_{\mu} in time T^{\mathrm{ct}}_{G}(\varepsilon) with \mathbf{Pr}\left[\mathrm{e}^{-\varepsilon}Z_{\mu}\leq\hat{Z}_{\mu}\leq\mathrm{e}^{\varepsilon}Z_{\mu}\right]\geq 0.99 . For functions T^{\mathrm{sp}}_{G}(\varepsilon) and T^{\mathrm{ct}}_{G}(\varepsilon) , we add the index G to emphasize that the running time also depends on parameters of graph G such as the number of vertices/edges and the maximum degree. We assume the oracles need to read the whole graph G so that the cost is at least |V|+|E| . We also require the following mild assumption on the Ising models. Definition 1.3 (marginal lower bound) . Let b\geq 0 be a constant. A Gibbs distribution \mu is said to satisfy the b -marginal lower bound if for any \Lambda\subseteq V , any pinning \sigma\in\{-1,+1\}^{\Lambda} , any v\in V\setminus\Lambda , and any c\in\{-1,+1\} , it holds that \mu^{\sigma}_{v}(c)\geq b , where \mu^{\sigma}_{v}(\cdot) denotes the marginal distribution on v projected from \mu conditional on that the configuration on \Lambda is fixed as \sigma . The marginal lower bound condition is a natural and common assumption for the Ising model. The assumption is widely used in the literature of sampling and approximate counting [ 14 ] , learning theory [ 10 ] , and TV-distance approximation [ 18 ] . 1.1 Algorithm and hardness results for \chi^{\alpha} -divergence approximation Let \alpha\geq 1 be a constant integer. The D_{f}\left({{\nu}\,\|\,{\mu}}\right)=D_{\chi^{\alpha}}\left({{\nu}\,\|\,{\mu}}\right) is called the \chi^{\alpha} -divergence if f(x)=\frac{1}{2}|x-1|^{\alpha} . We give the following approximation algorithm for the \chi^{\alpha} -divergence between two Ising models in 1.1 . Given two input Ising models (G,J^{\nu},h^{\nu}) and (G,J^{\mu},h^{\mu}) , define the following family of Ising models on the graph G : \displaystyle\mathcal{F}(\nu,\mu,\alpha)=\left\{\text{Ising model }(G,J^{(k)},h^{(k)})\mid\begin{subarray}{c}\textstyle J^{(k)}\triangleq kJ^{\nu}-(k-1)J^{\mu}\\ \textstyle h^{(k)}\triangleq kh^{\nu}-(k-1)h^{\mu}\end{subarray}\text{ for integer }0\leq k\leq\alpha\right\}. (2) We remark that (G,J^{(1)},h^{(1)}) and (G,J^{(0)},h^{(0)}) are the same as the input Ising models (G,J^{\nu},h^{\nu}) and (G,J^{\mu},h^{\mu}) respectively. The following theorem says that if all Ising models in \mathcal{F} admit sampling and approximate counting oracles, then the \chi^{\alpha} -divergence between two input Ising models can be approximated in polynomial time. Theorem 1.4 . Let \alpha\geq 1 be a constant integer and b\in(0,1) be a constant. There exists an FPRAS that solves 1.1 for \chi^{\alpha} -divergence in time O_{\alpha,b}\left(T^{\mathrm{ct}}_{G}\left(\frac{\eta_{\alpha,b}\cdot\varepsilon}{(n+m)^{\alpha}}\right)+\frac{(n+m)^{2\alpha}}{\varepsilon^{2}}\cdot T^{\mathrm{sp}}_{G}\left(\frac{\eta_{\alpha,b}\cdot\varepsilon^{2}}{(n+m)^{2\alpha}}\right)\right), where n=|V| , m=|E| , and \eta_{\alpha,b}>0 is a small constant depending only on \alpha and b , if two input Ising Gibbs distributions \mu and \nu are both b -marginally bounded and all Ising models in \mathcal{F}(\nu,\mu,\alpha) admit sampling and approximate counting oracles with cost functions T^{\mathrm{sp}}_{G}(\cdot) and T^{\mathrm{ct}}_{G}(\cdot) respectively. Let us consider a simplified case of the Ising model. Suppose G has the max degree \Delta . For an Ising model (G,J,h) , if for any e=\{u,v\}\in E , if J_{uv}=J_{vu}=\frac{\ln\beta}{2} take a unified value. In this case, an Ising model admits sampling and approximate counting oracles with cost function T^{\mathrm{sp}}_{G}(\varepsilon)=\mathrm{poly}(n,\log\frac{1}{\varepsilon}) and T^{\mathrm{ct}}_{G}(\varepsilon)=\mathrm{poly}(n,\frac{1}{\varepsilon}) if one of the following two conditions holds: • Uniqueness condition: \frac{\Delta-2}{\Delta}\leq\beta\leq\frac{\Delta}{\Delta-2} and an arbitrary external field h\in\mathbb{R}^{V} [ 13 ] . • Uniqueness condition or ferromagnetic condition with zero external field: