HOGWILD!-Gibbs can be PanAccurate
  Asynchronous Gibbs sampling has been recently shown to be fast-mixing and an
accurate method for estimating probabilities of events on a small number of
variables of a graphical model satisfying Dobrushin's
condition~\cite{DeSaOR16}. We investigate whether it can be used to accurately
estimate expectations of functions of {\em all the variables} of the model.
Under the same condition, we show that the synchronous (sequential) and
asynchronous Gibbs samplers can be coupled so that the expected Hamming
distance between their (multivariate) samples remains bounded by $O(\tau \log
n),$ where $n$ is the number of variables in the graphical model, and $\tau$ is
a measure of the asynchronicity. A similar bound holds for any constant power
of the Hamming distance. Hence, the expectation of any function that is
Lipschitz with respect to a power of the Hamming distance, can be estimated
with a bias that grows logarithmically in $n$. Going beyond Lipschitz
functions, we consider the bias arising from asynchronicity in estimating the
expectation of polynomial functions of all variables in the model. Using recent
concentration of measure results, we show that the bias introduced by the
asynchronicity is of smaller order than the standard deviation of the function
value already present in the true model. We perform experiments on a
multi-processor machine to empirically illustrate our theoretical findings.
