Bounding the Error of Markov Network Inference Algorithms

Guy Rom, Amir Globerson

We study the expected errors in the setting suggested by Globerson et al. (2015) of exact and approximate inference algorithms on Markov Networks. We give a lower bound for the exact algorithm on a general graph, and show that it is tight in several cases, using the results of Globerson et al. (2015) and Foster et al. (2017), including chains, trees and 2D grids. We present an upper bound on a poly time approximate inference for general graphs and discuss the meaning of the margin between the recovery performances.