On approximating the $f$-divergence between two Ising models
This work addresses a fundamental computational problem in statistical physics and machine learning for researchers dealing with Ising models, though it is incremental as it generalizes prior work on TV-distance.
The paper tackles the problem of approximating the f-divergence between two Ising models within a relative error, establishing algorithmic and hardness results for specific divergences like χ^α-divergence, with the algorithm matching the hardness regime and extending to other divergences.
The $f$-divergence is a fundamental notion that measures the difference between two distributions. In this paper, we study the problem of approximating the $f$-divergence between two Ising models, which is a generalization of recent work on approximating the TV-distance. Given two Ising models $ν$ and $μ$, which are specified by their interaction matrices and external fields, the problem is to approximate the $f$-divergence $D_f(ν\,\|\,μ)$ within an arbitrary relative error $\mathrm{e}^{\pm \varepsilon}$. For $χ^α$-divergence with a constant integer $α$, 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$-divergences such as $α$-divergence, Kullback-Leibler divergence, Rényi divergence, Jensen-Shannon divergence, and squared Hellinger distance.