On approximating the $f$-divergence between two Ising models
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912573087023104 |
|---|---|
| author | Feng, Weiming Fu, Yucheng |
| author_facet | Feng, Weiming Fu, Yucheng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05016 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On approximating the $f$-divergence between two Ising models Feng, Weiming Fu, Yucheng Data Structures and Algorithms Machine Learning Probability 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. |
| title | On approximating the $f$-divergence between two Ising models |
| topic | Data Structures and Algorithms Machine Learning Probability |
| url | https://arxiv.org/abs/2509.05016 |