提出计算两个伊辛模型间f散度的高效近似算法
On approximating the $f$-divergence between two Ising models
- 设计了在特定参数下逼近f散度的算法
- 对χ^α散度给出可计算与难计算的边界
- 适用于多种常见散度，如KL、Rényi等
f-散度是衡量两个概率分布差异的基本概念。本文研究了两个伊辛模型间f-散度的近似问题，这是近期关于总变差距离近似工作的推广。给定由相互作用矩阵和外部场定义的两个伊辛模型ν和μ，目标是在任意相对误差ε范围内近似f-散度D_f(ν ‖ μ)。针对χ^α散度（α为常数整数），本文建立了算法与复杂性下界结果，且算法适用的参数范围与下界相匹配。该方法可拓展至其他f-散度，包括α-散度、KL散度、Rényi散度、Jensen-Shannon散度及平方Hellinger距离。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。