MCMC Sampling Classic MCMC sampling: GV,E) Markoy chain X→X+l: pick a uniform random vertex v; update X(v)conditioning on X(N(v)); O(n log n)time when mixing Parallelization: Chromatic scheduler [folklore][Gonzalez et al.,AISTAT'11]: Vertices in the same color class are updated in parallel. ●O△logn)mixing time(△is max degree) "Hogwild!"[Niu,Recht,Re.Wright,NIPS'11][De Sa,Olukotun,Re,ICML'16]: All vertices are updated in parallel,ignoring concurrency issues. ●Wrong distribution!MCMC Sampling G(V,E): v Classic MCMC sampling: Parallelization: • Chromatic scheduler [folklore] [Gonzalez et al., AISTAT’11]: Vertices in the same color class are updated in parallel. • “Hogwild!” [Niu, Recht, Ré, Wright, NIPS’11][De Sa, Olukotun, Ré, ICML’16]: All vertices are updated in parallel, ignoring concurrency issues. pick a uniform random vertex v; update X(v) conditioning on X(N(v)); Markov chain Xt → Xt+1 : O(n log n) time when mixing • O(Δ log n) mixing time (Δ is max degree) • Wrong distribution!