Approximating the total variation distance between spin systems

Weiming Feng, Hongyang Liu, Minji Yang
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1974-2025, 2025.

Abstract

Spin systems form an important class of undirected graphical models. For two Gibbs distributions $\mu$ and $\nu$ induced by two spin systems on the same graph $G = (V, E)$, we study the problem of approximating the total variation distance $d_{\mathrm{TV}}\left({\mu},{\nu}\right)$ with an $\epsilon$-relative error. We propose a new reduction that connects the problem of approximating the TV-distance to sampling and approximate counting. Our applications include the hardcore model and the antiferromagnetic Ising model in the uniqueness regime, the ferromagnetic Ising model, and the general Ising model satisfying the spectral condition. Additionally, we explore the computational complexity of approximating the total variation distance $d_{\mathrm{TV}}\left({\mu_S},{\nu_S}\right)$ between two marginal distributions on an arbitrary subset $S \subseteq V$. We prove that this problem remains hard even when both $\mu$ and $\nu$ admit polynomial-time sampling and approximate counting algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-feng25a, title = {Approximating the total variation distance between spin systems}, author = {Feng, Weiming and Liu, Hongyang and Yang, Minji}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {1974--2025}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/feng25a/feng25a.pdf}, url = {https://proceedings.mlr.press/v291/feng25a.html}, abstract = {Spin systems form an important class of undirected graphical models. For two Gibbs distributions $\mu$ and $\nu$ induced by two spin systems on the same graph $G = (V, E)$, we study the problem of approximating the total variation distance $d_{\mathrm{TV}}\left({\mu},{\nu}\right)$ with an $\epsilon$-relative error. We propose a new reduction that connects the problem of approximating the TV-distance to sampling and approximate counting. Our applications include the hardcore model and the antiferromagnetic Ising model in the uniqueness regime, the ferromagnetic Ising model, and the general Ising model satisfying the spectral condition. Additionally, we explore the computational complexity of approximating the total variation distance $d_{\mathrm{TV}}\left({\mu_S},{\nu_S}\right)$ between two marginal distributions on an arbitrary subset $S \subseteq V$. We prove that this problem remains hard even when both $\mu$ and $\nu$ admit polynomial-time sampling and approximate counting algorithms.} }
Endnote
%0 Conference Paper %T Approximating the total variation distance between spin systems %A Weiming Feng %A Hongyang Liu %A Minji Yang %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-feng25a %I PMLR %P 1974--2025 %U https://proceedings.mlr.press/v291/feng25a.html %V 291 %X Spin systems form an important class of undirected graphical models. For two Gibbs distributions $\mu$ and $\nu$ induced by two spin systems on the same graph $G = (V, E)$, we study the problem of approximating the total variation distance $d_{\mathrm{TV}}\left({\mu},{\nu}\right)$ with an $\epsilon$-relative error. We propose a new reduction that connects the problem of approximating the TV-distance to sampling and approximate counting. Our applications include the hardcore model and the antiferromagnetic Ising model in the uniqueness regime, the ferromagnetic Ising model, and the general Ising model satisfying the spectral condition. Additionally, we explore the computational complexity of approximating the total variation distance $d_{\mathrm{TV}}\left({\mu_S},{\nu_S}\right)$ between two marginal distributions on an arbitrary subset $S \subseteq V$. We prove that this problem remains hard even when both $\mu$ and $\nu$ admit polynomial-time sampling and approximate counting algorithms.
APA
Feng, W., Liu, H. & Yang, M.. (2025). Approximating the total variation distance between spin systems. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:1974-2025 Available from https://proceedings.mlr.press/v291/feng25a.html.

Related Material