{"ID":2874215,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.05016","arxiv_id":"2509.05016","title":"On approximating the $f$-divergence between two Ising models","abstract":"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.","short_abstract":"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 sp...","url_abs":"https://arxiv.org/abs/2509.05016","url_pdf":"https://arxiv.org/pdf/2509.05016v1","authors":"[\"Weiming Feng\",\"Yucheng Fu\"]","published":"2025-09-05T11:25:22Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\",\"math.PR\"]","methods":"[]","has_code":false}