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

CREATORWeiming Feng and Yucheng Fu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE97 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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:

Read the complete text