On approximating the f-divergence between two Ising models

2025/09/05 by Feng, Weiming, Fu, Yucheng
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Probability (math.PR)

paper · doi:10.48550/arxiv.2509.05016

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 e^{± ε}. 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.

Citations

• Sampling and Identity-Testing Without Approximate Tensorization of Entropy
• Approximating the Total Variation Distance between Gaussians
• Algorithms and Hardness for Estimating Statistical Similarity
• Approximating the total variation distance between spin systems
• Computational Explorations of Total Variation Distance
• Rapid Mixing at the Uniqueness Threshold
• On the tensorization of the variational distance
• Sharp bounds on aggregate expert error
• A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata
• On Deterministically Approximating Total Variation Distance
• Total Variation Distance Meets Probabilistic Inference
• Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
• Neural Estimation of Statistical Divergences
• Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
• Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning
• On Computing the Total Variation Distance of Hidden Markov Models
• Testing Ising Models
• Efficiently learning Ising models on arbitrary graphs
• The computational hardness of counting in two-spin models on d-regular graphs
• Correlation Decay up to Uniqueness in Spin Systems

Related

• Computing Marginal and Conditional Divergences between Decomposable Models with Applications
• A Tight Lower Bound for the Hellinger Distance with Given Means and Variances
• Tight Lower Bounds for α-Divergences Under Moment Constraints and Relations Between Different α
• Minimum divergence estimators, maximum likelihood and exponential families
• Joint Range of f-divergences