**Abstract**

Maximum Likelihood learning of graphical models is not possible in problems
where inference is intractable. In such settings it is common to use approximate
inference (e.g. Loopy BP) and maximize the so-called "surrogate" likelihood objective.
We examine the effect of using different approximate inference methods
and, therefore, different surrogate likelihoods, on the accuracy of parameter estimation.
In particular, we consider methods that utilize a control parameter to trade
computation for accuracy. We demonstrate empirically that cheaper, but worse
quality approximate inference methods should be used in the small data setting as
they exhibit smaller variance and are more robust to model mis-specification.