HOGWILD!-Gibbs can be PanAccurate
This work provides theoretical guarantees for using asynchronous methods in probabilistic inference, which could speed up computations in machine learning applications, though it is incremental as it builds on prior results on fast-mixing Gibbs sampling.
The paper investigates whether asynchronous Gibbs sampling can accurately estimate expectations of functions of all variables in a graphical model, showing that under Dobrushin's condition, the bias grows logarithmically with the number of variables and is smaller than the standard deviation for polynomial functions.
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(τ\log n),$ where $n$ is the number of variables in the graphical model, and $τ$ 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.