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 [DSOR16]. We investigate whether it can be used to accurately estimate expectations of functions of 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 [DDK17, GLP17, GSS18], 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 multiprocessor machine to empirically illustrate our theoretical findings.
Author-feedback response: Author response did clarify many of my concerns. Thus, I increased my rating. But please make sure to clarify"synchronous Gibbs sampling" (by either renaming to traditional "sequential" or properly defining).  -----------------------------------------------------------------------------------------------------------  This paper attempts to analyze asynchronous Gibbs sampling for models satisfying Dobrushin’s condition. The paper builds upon previous seminal work by Chris De Sa et al. (2016). Informally, the key idea behind all the results in the paper is to try to show that sequential and asynchronous chains are similar. In particular, they begin by showing that expected Hamming distance between an asynchronous Gibbs chain and its sequential version starting from the state is small at any time. Using this they could bound the bias in estimating the expected value of polynomials of the random variables. Their bounds improved upon previous results. Finally, some empirical studies on simple test cases were provided. Comments: 1. The writing and clarity of paper can be improved. The paper should be scanned for consistency and confusing order of symbols. The main confusion arises from nomenclature used. Please correct me if I am wrong, does synchronous sampling mean sequential sampling in this paper? To me synchronous sampling means sampling all variables together and updating the state and this strategy is known to not work for many cases (one example below). I think that in the paper, this is not the case, rather it refers to sequential sampling and my review is based on this assumption. Also, in Theorem 1 (borrowed from Chris De Sa et al. 2016), on one hand, its labeled as “Mixing Time of Synchronous Gibbs Sampling” but on the other hand, theorem statement says “mixing time of HOGWILD!-Gibbs”. Please fix/clarify this. 2. With the assumptions of asynchronicity mentioned in the paper, consider a trivial 2D Ising model (this example can be generalized to the Ising model on an n-dimensional torus). I believe the following read-write sequence …, R_1, R_2, W_1, W_2, R1, R2, W2, W1 … is possible. To elaborate, in this case, all processors read the current state and then both writes are completed before next reads. But, we know the stationary distribution of this sampler in closed form and it’s different from the target Ising distribution. (c.f. Neumann, A.U., and Derrida, B., 1988. Finite-size scaling study of dynamical phase transitions in two-dimensional models: Ferromagnet, symmetric and non-symmetric spin glasses. Journal de Physique, 49(10), pp.1647-1656 and Zaheer, M., Wick, M., Tristan, J.B., Smola, A. and Steele, G., 2016, May. Exponential stochastic cellular automata for massively parallel inference. In Artificial Intelligence and Statistics (pp. 966-975).) Can you please explain what assumption of your result is broken by this example that I am missing? 3. The experiments were basic, but verifying the claim. The experiments can be made more interesting by analyzing corner cases (like the example above) or testing limits of asynchronicity etc.  Overall, the paper takes a step in our understanding of asynchronous Gibbs sampling. The proof strategies are mostly standard, but improving the writing/presentation and providing extensive empirical evaluations would strengthen the paper a lot, making it a nice contribution to the field.  Minor Comments/Typos: 1. Apologies for nit-picking: In the introduction section, in my humble opinion the contribution section is too long (It’s ok for a journal paper, but quite a stretch for an 8 page NIPS paper). My personal preference is to limit the contributions in the introduction to major points at a high level. The details about how the obtained results are an improvement over previous work can be part of the main text. 2. A lot of space in the experiment section can be saved. This can allow you to write more details about the proof techniques in the main paper. 3. Line 141: ... condition is alpha < 1. <=> ... condition if alpha < 1. 4. Eq(10)-(11) in appendix: Placement of \alpha is confusing wrt log.